===Key generation=== The keys for the RSA algorithm are generated in the following way: # Choose two distinct [[prime number]]s ''p'' and ''q''. #* ''p'' and ''q'' are kept secret. # Compute 'n'' = ''pq'' public n = private p * private q n is keylength bits long. # Compute ''λ''(''n''), where ''λ'' is Carmichael's totient function. Since ''n'' = ''pq'', ''λ''(''n'') = lcm(''λ''(''p''),''λ''(''q'')), and since ''p'' and ''q'' are prime, ''λ''(''p'') = ''φ''(''p'') = ''p'' − 1 where φ is the Euler totient function, and likewise ''λ''(''q'') = ''q'' − 1. Hence ''λ''(''n'') = lcm(''p'' − 1, ''q'' − 1) private lambda(n) is calculated and has a number of relevant algebraic identities associated #* The lcm may be calculated through the Euclidean algorithm, since lcm(''a'',''b'') = ''|ab|''/gcd(''a'',''b''). # Choose an integer ''e'' such that 1 < ''e'' < ''λ''(''n'') and gcd(''e'', ''λ''(''n'')) = 1; that is, ''e'' and ''λ''(''n'') are coprime. #* ''e'' having a short bit-length and small Hamming weight results in more efficient encryption -- the most commonly chosen value for ''e'' is 2**16 + 1 = 65,537. The smallest (and fastest) possible value for ''e'' is 3, but such a small value for ''e'' has been shown to be less secure in some settings. #*''e'' is released as part of the public key. public e is often a very simple reused constant # Determine ''d'' as ''d'' ≡ ''e''**−1 (mod ''λ''(''n'')); that is, ''d'' is the modular multiplicative inverse of ''e'' modulo ''λ''(''n''). #* This means: solve for ''d'' the equation ''d''⋅''e'' ≡ 1 (mod ''λ''(''n'')); ''d'' can be computed efficiently by using the Extended Euclidean algorithm, since, thanks to ''e'' and ''λ''(''n'') being coprime, said equation is a form of Bézout's identity, where ''d'' is one of the coefficients. #* ''d'' is kept secret as the ''private key exponent''. The ''public key'' consists of the modulus ''n'' and the public (or encryption) exponent ''e''. The ''private key'' consists of the private (or decryption) exponent ''d'', which must be kept secret. ''p'', ''q'', and ''λ''(''n'') must also be kept secret because they can be used to calculate ''d''. In fact, they can all be discarded after ''d'' has been computed. Okay! I removed all the wiki markup!