14,443
edits
(→Example: fmt) 
(consistently use λ(n) instead of φ(n), as most practical RSA implementations do, except for historical discussion (and the JS code, for now); also use \bmod and \pmod instead of ugly TeX hacks) 

# Compute {{nowrap1=''n'' = ''pq''}}.
#* ''n'' is used as the [[Modular arithmeticmodulus]] for both the public and private keys. Its length, usually expressed in bits, is the [[key length]].
# Compute {{nowrap1=''
# Choose an integer ''e'' such that {{nowrap1 < ''e'' < ''
# Determine ''d'' as {{nowrap''d'' ≡ ''e''<sup>−1</sup> (mod ''
::* This is more clearly stated as: solve for ''d'' given {{nowrap''d''⋅''e'' ≡ 1 (mod ''
::* ''e'' having a short [[bitlength]] and small [[Hamming weight]] results in more efficient encryption – most commonly {{nowrap1=2<sup>16</sup> + 1 = 65,537}}. However, much smaller values of ''e'' (such as 3) have been shown to be less secure in some settings.<ref name="Boneh">
{{cite journal
::*''d'' is kept 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 modulus ''n'' and the private (or decryption) exponent ''d'', which must be kept secret. ''p'', ''q'', and ''
Alternatively, as in the original RSA paper,<ref name=rsa /> the [[Euler totient function]] {{nowrap1=''φ''(''n'') = (''p'' − 1)(''q'' − 1)}} can be used instead of ''λ''(''n'') for calculating the private exponent ''d''. This works because ''φ''(''n'') is always divisible by ''λ''(''n''), and thus any ''d'' satisfying {{nowrap''d''⋅''e'' ≡ 1 (mod ''φ''(''n''))}} also satisfies {{nowrap''d''⋅''e'' ≡ 1 (mod ''λ''(''n''))}}, but it will sometimes yield a private exponent ''d'' that is larger than necessary (i.e.{{nowrap''d'' > ''λ''(''n'')}}) . Most RSA implementations will accept exponents generated using either method (if they use the private exponent ''d'' at all, rather than using the optimization based on the [[Chinese remainder theorem]] described below), but some standards like [http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.1864.pdf#page=62 FIPS 1864] may require that {{nowrap''d'' < ''λ''(''n'')}}. Any "oversized" private exponents not meeting that criterion may always be reduced modulo ''λ''(''n'') to obtain a smaller equivalent exponent.
Since any common factors of {{nowrap(''p'' − 1)}} and {{nowrap(''q'' − 1)}} are present in the factorisation of {{nowrap''pq'' − 1}},<ref>"Further Attacks ON ServerAided RSA Cryptosystems", James McKee and Richard Pinch, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.33.1333</ref> it is recommended that {{nowrap(''p'' − 1)}} and {{nowrap(''q'' − 1)}} have only very small common factors, if any besides the necessary 2.<ref name="rsa" /><ref>A Course in Number Theory and Cryptography, Graduate Texts in Math. No. 114, SpringerVerlag, New York, 1987. [[Neal Koblitz]], Second edition, 1994. p. 94</ref><ref>"common factors in (''p'' − 1) and (''q'' − 1)",Viktor Dukhovni, openssldev Digest, Vol 9, Issue 4, https://www.mailarchive.com/openssldev%40openssl.org/msg39736.html, https://www.mailarchive.com/openssldev%40openssl.org/msg39725.html</ref>
Note: The authors of the original RSA paper carry out the key generation by choosing ''d'' and then computing ''e'' as the [[modular multiplicative inverse]] of ''d'' (modulo ''φ''(''n'')). Since it is beneficial to use a small value for ''e'' (i.e. 65,537) in order to speed up the encryption function, current implementations of RSA, such as [[PKCS1PKCS#1]] choose ''e'' and compute ''d'' instead.<ref name="rsa" /><ref>{{Cite weburl=http://www.ietf.org/rfc/rfc3447.txttitle=PublicKey Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1last=Johnsonfirst=J.last2=Kaliskifirst2=B.date=February 2013website=www.ietf.orgpublisher=Network Working Groupaccessdate=9 March 2016}}</ref>
===Example===
# Compute {{nowrap1=''n'' = ''pq''}} giving
#: <math>n = 61\times 53 = 3233</math>
# Compute the [[totient]] of the product as {{nowrap1=
#: <math>\
# Choose any number {{nowrap1 < ''e'' <
#: Let <math>e = 17</math>
# Compute ''d'', the [[modular multiplicative inverse]] of {{nowrap''e'' (mod ''
#: <math>d =
#: Worked example for the modular multiplicative inverse:
#: <math>d \times e \
#: <math>
The '''public key''' is ({{nowrap1=''n'' = 3233}}, {{nowrap1=''e'' = 17}}). For a padded [[plaintext]] message ''m'', the encryption function is
:<math>c(m) = m^{17} \
The '''private key''' is ({{nowrap1=''n'' = 3233}}, {{nowrap1=''d'' =
:<math>m(c) = c^{
For instance, in order to encrypt {{nowrap1=''m'' = 65}}, we calculate
:<math>c = 65^{17} \
To decrypt {{nowrap1=''c'' = 2790}}, we calculate
:<math>m = 2790^{
Both of these calculations can be computed efficiently using the [[squareandmultiply algorithm]] for [[modular exponentiation]]. In reallife situations the primes selected would be much larger; in our example it would be trivial to factor ''n'', 3233 (obtained from the freely available public key) back to the primes ''p'' and ''q''. ''e'', also from the public key, is then inverted to get ''d'', thus acquiring the private key.
The values ''d''<sub>''p''</sub>, ''d''<sub>''q''</sub> and ''q''<sub>inv</sub>, which are part of the private key are computed as follows:
: <math>\begin{align}
d_p = {} &d
d_q = {} &d \
q_\text{inv} = {} &q^{1} \
\Rightarrow {} &(q_\text{inv} \times q) \
\end{align}</math>
Here is how ''d''<sub>''p''</sub>, ''d''<sub>''q''</sub> and ''q''<sub>inv</sub> are used for efficient decryption. (Encryption is efficient by choice of a suitable ''d'' and ''e'' pair)
: <math>\begin{align}
m_1 &= c^{d_p} \
m_2 &= c^{d_q} \
h &= (q_\text{inv} \times (m_1  m_2)) \
m &= m_2 + h \times q = 12 + 1 \times 53 = 65
\end{align}</math>
We want to show that {{nowrap''m<sup>ed</sup>'' ≡ ''m'' (mod ''pq'')}} for every integer ''m'' when ''p'' and ''q'' are distinct prime numbers and ''e'' and ''d'' are positive integers satisfying
: <math>e d \equiv 1 \pmod{\
Since
: <math>ed  1 = h(p  1) = k(q  1)</math>
▲for some nonnegative integer ''h''.
To check whether two numbers, like ''m<sup>ed</sup>'' and ''m'', are congruent mod ''pq'' it suffices (and in fact is equivalent) to check they are congruent mod ''p'' and mod ''q'' separately. (This is part of the [[Chinese remainder theorem]], although it is not the significant part of that theorem.) To show {{nowrap''m<sup>ed</sup>'' ≡ ''m'' (mod ''p'')}}, we consider two cases: {{nowrap''m'' ≡ 0 (mod ''p'')}} and {{nowrap''m'' <math>\not\equiv</math> 0 (mod ''p'')}}.
In the first case, ''m'' is a multiple of ''p'', thus ''m<sup>ed</sup>'' is a multiple of ''p'', so {{nowrap''m<sup>ed</sup>'' ≡ 0 ≡ ''m'' (mod ''p'')}}. In the second case
: <math>m^{
where we used [[Fermat's little theorem]] to replace ''m''<sup>''p''−1</sup> mod ''p'' with 1.
In the first case ''m<sup>ed</sup>'' is a multiple of ''q'', so {{nowrap''m<sup>ed</sup>'' ≡ 0 ≡ ''m'' (mod ''q'')}}. In the second case
: <math>m^{
This completes the proof that, for any integer ''m'', and integers ''e'', ''d'' such that <math>e d \equiv 1 \pmod{\
: <math>
===Proof using Euler's theorem===
Although the original paper of Rivest, Shamir, and Adleman used Fermat's little theorem to explain why RSA works, it is common to find proofs that rely instead on [[Euler's theorem]].
We want to show that {{nowrap''m<sup>ed</sup>'' ≡ ''m'' (mod ''n'')}}, where {{nowrap1=''n'' = ''pq''}} is a product of two different prime numbers and ''e'' and ''d'' are positive integers satisfying {{nowrap''ed'' ≡ 1 (mod ''φ''(''n''))}}. Since ''e'' and ''d'' are positive, we can write {{nowrap1
: <math>m^{ed} = m^{1 + h\varphi(n)} = m
where the secondlast congruence follows from [[Euler's theorem]].
More generally, for any ''e'' and ''d'' satisfying {{nowrap''ed'' ≡ 1 (mod ''λ''(''n''))}}, the same conclusion follows from [[Carmichael function#Carmichael's theoremCarmichael's generalization of Euler's theorem]], which states that {{nowrap''m''<sup>''λ''(n)</sup> ≡ 1 (mod ''n'')}} for all ''m'' relatively prime to ''n''.
When ''m'' is not relatively prime to ''n'', the argument just given is invalid. This is highly improbable (only a proportion of {{nowrap1/''p'' + 1/''q'' − 1/(''pq'')}} numbers have this property), but even in this case the desired congruence is still true. Either {{nowrap''m'' ≡ 0 (mod ''p'')}} or {{nowrap''m'' ≡ 0 (mod ''q'')}}, and these cases can be treated using the previous proof.
For efficiency many popular crypto libraries (like [[OpenSSL]], [[Java (programming language)Java]] and [[.NET]]) use the following optimization for decryption and signing based on the [[Chinese remainder theorem]]. The following values are precomputed and stored as part of the private key:
* <math>p</math> and <math>q</math>: the primes from the key generation,
* <math>d_P = d \
* <math>d_Q = d \
* <math>q_\text{inv} = q^{1} \
These values allow the recipient to compute the exponentiation {{nowrap1=''m'' = ''c''<sup>''d''</sup> (mod ''pq'')}} more efficiently as follows:
* <math>m_1 = c^{d_P} \
* <math>m_2 = c^{d_Q} \
* <math>h = q_\text{inv}(m_1  m_2) \
* <math>m = m_2 + hq\,</math>
The security of the RSA cryptosystem is based on two mathematical problems: the problem of [[integer factorizationfactoring large numbers]] and the [[RSA problem]]. Full decryption of an RSA ciphertext is thought to be infeasible on the assumption that both of these problems are hard, i.e., no efficient algorithm exists for solving them. Providing security against ''partial'' decryption may require the addition of a secure [[padding (cryptography)padding scheme]].{{Citation neededdate=January 2009}}
The [[RSA problem]] is defined as the task of taking ''e''th roots modulo a composite ''n'': recovering a value ''m'' such that {{nowrap''c'' ≡ ''m''<sup>''e''</sup> (mod ''n'')}}, where {{nowrap(''n'', ''e'')}} is an RSA public key and ''c'' is an RSA ciphertext. Currently the most promising approach to solving the RSA problem is to factor the modulus ''n''. With the ability to recover prime factors, an attacker can compute the secret exponent ''d'' from a public key {{nowrap(''n'', ''e'')}}, then decrypt ''c'' using the standard procedure. To accomplish this, an attacker factors ''n'' into ''p'' and ''q'', and computes {{nowraplcm(''p'' − 1
Multiple polynomial quadratic sieve (MPQS) can be used to factor the public modulus ''n''. The time taken to factor 128bit and 256bit ''n'' on a desktop computer {{nowrap(Processor: Intel DualCore i74500U 1.80GHz)}} are respectively 2 seconds and 35 minutes.
