===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''

# Compute ''λ''(''n''), where ''λ'' is [[Carmichael's totient function]]. Since ''n'' = ''pq'', ''λ''(''n'') = [[least common multiple|lcm]](''λ''(''p''),''λ''(''q'')), and since ''p'' and ''q'' are prime, ''λ''(''p'') = ''[[Euler totient function|φ]]''(''p'') = ''p'' − 1 and likewise ''λ''(''q'') = ''q'' − 1. Hence ''λ''(''n'') = lcm(''p'' − 1, ''q'' − 1). 

#* ''λ''(''n'') is kept secret.

#* The lcm may be calculated through the [[Euclidean algorithm]], since lcm(''a'',''b'') = ''|ab|''/gcd(''a'',''b'').

# Choose an integer ''e'' such that {{nowrap|1 < ''e'' < ''λ''(''n'')}} and {{nowrap|1=[[greatest common divisor|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 {{snd}} the most commonly chosen value for ''e'' is {{nowrap|1=2¹⁶ + 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.<ref name="Boneh99">

{{cite journal

 | url = http://crypto.stanford.edu/~dabo/abstracts/RSAattack-survey.html

 | last = Boneh | first = Dan

 | title = Twenty Years of attacks on the RSA Cryptosystem

 | journal = [[Notices of the American Mathematical Society]]

 | volume = 46 | issue = 2

 | pages = 203–213 | year = 1999

}}</ref>

#*''e'' is released as part of the public key.

# Determine ''d'' as {{nowrap|''d'' ≡ ''e''⁻¹ (mod ''λ''(''n''))}}; that is, ''d'' is the [[modular multiplicative inverse]] of ''e'' modulo ''λ''(''n'').

#* This means: solve for ''d'' the equation {{nowrap|''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.<ref>Applied Cryptography, John Wiley & Sons, New York, 1996. [[Bruce Schneier]], p. 467</ref>