RSA (cryptosystem): Difference between revisions

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
(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 {{nowrap|1=''n'' = ''pq''}}.
#* ''n'' is used as the [[Modular arithmetic|modulus]] for both the public and private keys. Its length, usually expressed in bits, is the [[key length]].
# Compute {{nowrap|1=''φλ''(''n'') = lcm(''φλ''(''p''), ''φλ''(''q'')) = (''p''[[least common 1)multiple|lcm]](''qp'' − 1) = ''n'' − (''p'' +, ''q'' − 1)}}, where ''φλ'' is [[EulerCarmichael's totient function]]. This value is kept private.
# Choose an integer ''e'' such that {{nowrap|1 < ''e'' < ''φλ''(''n'')}} and {{nowrap|1=[[greatest common divisor|gcd]](''e'', ''φλ''(''n'')) = 1}}; i.e., ''e'' and ''φλ''(''n'') are [[coprime]].
# Determine ''d'' as {{nowrap|''d'' ≡ ''e''<sup>−1</sup> (mod ''φλ''(''n''))}}; i.e., ''d'' is the [[modular multiplicative inverse]] of ''e'' (modulo ''φλ''(''n'')).
::* This is more clearly stated as: solve for ''d'' given {{nowrap|''d''⋅''e'' ≡ 1 (mod ''φλ''(''n''))}}.
::* ''e'' having a short [[bit-length]] and small [[Hamming weight]] results in more efficient encryption – most commonly {{nowrap|1=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 ''φλ''(''n'') must also be kept secret because they can be used to calculate ''d''.
 
* An alternative, used by [[PKCS1|PKCS#1]], is to choose ''d'' matching {{nowrap|''de'' ≡ 1 (mod ''λ'')}} with {{nowrap|1=''λ'' = lcm(''p'' − 1, ''q'' − 1)}}, where lcm is the [[least common multiple]]. Using ''λ'' instead of ''φ''(''n'') allows more choices for ''d''. ''λ'' can also be defined using the [[Carmichael function]], ''λ''(''n'').
Alternatively, as in the original RSA paper,<ref name=rsa /> the [[Euler totient function]] {{nowrap|1=''φ''(''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.186-4.pdf#page=62 FIPS 186-4] 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 Server-Aided 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, Springer-Verlag, New York, 1987. [[Neal Koblitz]], Second edition, 1994. p. 94</ref><ref>"common factors in (''p'' − 1) and (''q'' − 1)",Viktor Dukhovni, openssl-dev Digest, Vol 9, Issue 4, https://www.mail-archive.com/openssl-dev%40openssl.org/msg39736.html, https://www.mail-archive.com/openssl-dev%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 [[PKCS1|PKCS#1]] choose ''e'' and compute ''d'' instead.<ref name="rsa" /><ref>{{Cite web|url=http://www.ietf.org/rfc/rfc3447.txt|title=Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1|last=Johnson|first=J.|last2=Kaliski|first2=B.|date=February 2013|website=www.ietf.org|publisher=Network Working Group|access-date=9 March 2016}}</ref>
 
===Example===
# Compute {{nowrap|1=''n'' = ''pq''}} giving
#: <math>n = 61\times 53 = 3233</math>
# Compute the [[totient]] of the product as {{nowrap|1=φ''λ''(''n'') = [[least common multiple|lcm]](''p'' − 1)(, ''q'' − 1)}} giving
#: <math>\varphilambda(3233) = \operatorname{lcm}(6160, - 1)(53 - 152) = 3120780</math>
# Choose any number {{nowrap|1 < ''e'' < 3120780}} that is [[coprime]] to 3120780. Choosing a prime number for ''e'' leaves us only to check that ''e'' is not a divisor of 3120780.
#: Let <math>e = 17</math>
# Compute ''d'', the [[modular multiplicative inverse]] of {{nowrap|''e'' (mod ''φλ''(''n''))}} yielding,
#: <math>d = 2753413</math>
#: Worked example for the modular multiplicative inverse:
#: <math>d \times e \;bmod \operatorname{mod}\; \varphilambda(n) = 1</math>
#: <math>2753413 \times 17 \; \operatorname{mod}\;bmod 3120780 = 1</math>
 
The '''public key''' is ({{nowrap|1=''n'' = 3233}}, {{nowrap|1=''e'' = 17}}). For a padded [[plaintext]] message ''m'', the encryption function is
:<math>c(m) = m^{17} \; \operatorname{mod}\;bmod 3233</math>
 
The '''private key''' is ({{nowrap|1=''n'' = 3233}}, {{nowrap|1=''d'' = 2753413}}). For an encrypted [[ciphertext]] ''c'', the decryption function is
:<math>m(c) = c^{2753413} \; \operatorname{mod}\;bmod 3233</math>
 
For instance, in order to encrypt {{nowrap|1=''m'' = 65}}, we calculate
:<math>c = 65^{17} \; \operatorname{mod}\;bmod 3233 = 2790 </math>
 
To decrypt {{nowrap|1=''c'' = 2790}}, we calculate
:<math>m = 2790^{2753413} \; \operatorname{mod}\;bmod 3233 = 65 </math>
 
Both of these calculations can be computed efficiently using the [[square-and-multiply algorithm]] for [[modular exponentiation]]. In real-life 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\; \operatorname{mod}\;bmod (p-1) = 2753 \; \operatorname{mod}\;bmod (61-1) = 53 \\
d_q = {} &d \;bmod \operatorname{mod}\;(q-1) = 2753 \; \operatorname{mod}\;bmod (53-1) = 49 \\
q_\text{inv} = {} &q^{-1} \; \operatorname{mod}\;bmod p = 53^{-1} \; \operatorname{mod}\;bmod 61 = 38 \\
\Rightarrow {} &(q_\text{inv} \times q) \; \operatorname{mod}\;bmod p = 38 \times 53 \; \operatorname{mod}\;bmod 61= 1
\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} \; \operatorname{mod}\;bmod p = 2790^{53} \; \operatorname{mod}\;bmod 61 = 4 \\
m_2 &= c^{d_q} \; \operatorname{mod}\;bmod q = 2790^{49} \; \operatorname{mod}\;bmod 53 = 12 \\
h &= (q_\text{inv} \times (m_1 - m_2)) \; \operatorname{mod}\;bmod p = (38 \times -8) \; \operatorname{mod}\;bmod 61 = 1 \\
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{\philambda(pq)}.</math>
 
Since <math>\phi{{nowrap|1=''λ''(''pq'') = lcm(''p'' - 1)(, ''q'' - 1)</math>}} is, by construction, divisible by both {{nowrap|p − 1}} and {{nowrap|q − 1}}, we can write
: <math>ed - 1 = h(p - 1) = k(q - 1)</math>
for some nonnegative integerintegers ''h'' and ''k''.
 
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^{e ded} = m^{(ed - 1)} m = m^{h(p - 1)(q} - 1)}m = \left(m^{p - 1}\right)^{h(q - 1)}m \equiv 1^{h(q - 1)}m \equiv m \pmod{p}</math>
 
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^{e ded} = m^{(ed - 1)} m = m^{h(p - 1)k(q - 1)} m = \left(m^{q - 1}\right)^{h(pk - 1)}m \equiv 1^{h(pk - 1)}m \equiv m \pmod{q}</math>
 
This completes the proof that, for any integer ''m'', and integers ''e'', ''d'' such that <math>e d \equiv 1 \pmod{\philambda(pq)}</math>,
: <math>\left(m^e\right)^d \equiv m \pmod{pq}.</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 {{nowrap|1=''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 {{nowrap|1 = ''ed'' = 1 + ''h''φ(''n'')}} for some non-negative integer ''h''. ''Assuming'' that ''m'' is relatively prime to ''n'', we have
: <math>m^{ed} = m^{1 + h\varphi(n)} = m \left(m^{\varphi(n)}\right)^{h} \equiv m (1)^{h} \equiv m \pmod{n} </math>
 
where the second-last 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 theorem|Carmichael'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 {{nowrap|1/''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 \textpmod{ (mod }p - 1\text{)}</math>,
* <math>d_Q = d \textpmod{ (mod }q - 1\text{)}</math> and
* <math>q_\text{inv} = q^{-1} \textpmod{ (mod }p\text{)}</math>.
 
These values allow the recipient to compute the exponentiation {{nowrap|1=''m'' = ''c''<sup>''d''</sup> (mod ''pq'')}} more efficiently as follows:
* <math>m_1 = c^{d_P} \textpmod{ (mod }p\text{)}</math>
* <math>m_2 = c^{d_Q} \textpmod{ (mod }q\text{)}</math>
* <math>h = q_\text{inv}(m_1 - m_2) \textpmod{ (mod }p\text{)}</math> (if <math>m_1 < m_2</math> then some libraries compute ''h'' as <math>q_\text{inv}\left[\left(m_1 + \left\lceil \frac{q}{p} \right\rceil p\right) - m_2\right] \textpmod{ (mod }p\text{)}</math>)
* <math>m = m_2 + hq\,</math>
 
The security of the RSA cryptosystem is based on two mathematical problems: the problem of [[integer factorization|factoring 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 needed|date=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 {{nowrap|lcm(''p'' − 1)(, ''q'' − 1)}} which allows the determination of ''d'' from ''e''. No polynomial-time method for factoring large integers on a classical computer has yet been found, but it has not been proven that none exists. ''See [[integer factorization]] for a discussion of this problem''.
 
Multiple polynomial quadratic sieve (MPQS) can be used to factor the public modulus ''n''. The time taken to factor 128-bit and 256-bit ''n'' on a desktop computer {{nowrap|(Processor: Intel Dual-Core i7-4500U 1.80GHz)}} are respectively 2 seconds and 35 minutes.