Editing RSA cryptosystem (section)

==Operation==
The RSA algorithm involves four steps: [[Key (cryptography)|key]] generation, key distribution, encryption, and decryption.

A basic principle behind RSA is the observation that it is practical to find three very large positive integers {{mvar|e}}, {{mvar|d}}, and {{mvar|n}}, such that for all integers {{mvar|m}} ({{math|0 &le; ''m'' &lt; ''n''}}), both <math>(m^e)^d</math> and <math>m</math> have the same [[Euclidean division|remainder]] when divided by <math>n</math> (they are [[Modular arithmetic#Congruence|congruent modulo]] <math>n</math>):<math display="block">(m^e)^d \equiv m \pmod{n}.</math>However, when given only {{mvar|e}} and {{mvar|n}}, it is extremely difficult to find {{mvar|d}}.

The integers {{mvar|n}} and {{mvar|e}} comprise the public key, {{mvar|d}} represents the private key, and {{mvar|m}} represents the message. The [[modular exponentiation]] to {{mvar|e}} and {{mvar|d}} corresponds to encryption and decryption, respectively.

In addition, because the two exponents [[Exponentiation#Identities and properties|can be swapped]], the private and public key can also be swapped, allowing for message [[Digital signature|signing and verification]] using the same algorithm.

===Key generation===
The keys for the RSA algorithm are generated in the following way:
# Choose two large [[prime number]]s {{mvar|p}} and {{mvar|q}}.
#* To make factoring harder, {{mvar|p}} and {{mvar|q}} should be chosen at random, be both large and have a large difference.<ref name="rsa"/> For choosing them the standard method is to choose random integers and use a [[primality test]] until two primes are found.
#* {{mvar|p}} and {{mvar|q}} are kept secret.
# Compute {{math|1=''n'' = ''pq''}}.
#* {{mvar|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]].
#* {{mvar|n}} is released as part of the public key.
# Compute {{math|''&lambda;''(''n'')}}, where {{mvar|&lambda;}} is [[Carmichael's totient function]]. Since {{math|1=''n'' = ''pq'', ''&lambda;''(''n'') = [[least common multiple|lcm]](''&lambda;''(''p''),&nbsp;''&lambda;''(''q''))}}, and since {{mvar|p}} and {{mvar|q}} are prime, {{math|1=''&lambda;''(''p'') = ''[[Euler totient function|&phi;]]''(''p'') = ''p'' − 1}}, and likewise {{math|1=''&lambda;''(''q'') = ''q'' − 1}}. Hence {{math|1=''&lambda;''(''n'') = lcm(''p'' − 1, ''q'' − 1)}}.
#* The {{math|1=lcm}} may be calculated through the [[Euclidean algorithm]], since {{math|1=lcm(''a'',&nbsp;''b'') = {{sfrac|{{abs|''ab''}}|gcd(''a'',&nbsp;''b'')}}}}.
#* {{math|''&lambda;''(''n'')}} is kept secret.
# Choose an integer {{mvar|e}} such that {{math|1 &lt; ''e'' &lt; ''&lambda;''(''n'')}} and {{math|1=[[greatest common divisor|gcd]](''e'', ''&lambda;''(''n'')) = 1}}; that is, {{mvar|e}} and {{math|''&lambda;''(''n'')}} are [[coprime]].
#* {{mvar|e}} having a short [[bit-length]] and small [[Hamming weight]] results in more efficient encryption{{snd}} the most commonly chosen value for {{mvar|e}} is {{math|1=2<sup>16</sup> + 1 = {{val|65,537}}}}. The smallest (and fastest) possible value for {{mvar|e}} is 3, but such a small value for {{mvar|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>
#* {{mvar|e}} is released as part of the public key.
# Determine {{mvar|d}} as {{math|1=''d'' ≡ ''e''<sup>−1</sup> (mod ''&lambda;''(''n''))}}; that is, {{mvar|d}} is the [[modular multiplicative inverse]] of {{mvar|e}} modulo {{math|''&lambda;''(''n'')}}.
#* This means: solve for {{mvar|d}} the equation {{math|1=''de'' ≡ 1 (mod ''&lambda;''(''n''))}}; {{mvar|d}} can be computed efficiently by using the [[extended Euclidean algorithm]], since, thanks to {{mvar|e}} and {{math|''&lambda;''(''n'')}} being coprime, said equation is a form of [[Bézout's identity]], where {{mvar|d}} is one of the coefficients.
#* {{mvar|d}} is kept secret as the ''private key exponent''.
The ''public key'' consists of the modulus {{mvar|n}} and the public (or encryption) exponent {{mvar|e}}. The ''private key'' consists of the private (or decryption) exponent {{mvar|d}}, which must be kept secret. {{mvar|p}}, {{mvar|q}}, and {{math|''&lambda;''(''n'')}} must also be kept secret because they can be used to calculate {{mvar|d}}. In fact, they can all be discarded after {{mvar|d}} has been computed.<ref>Applied Cryptography, John Wiley & Sons, New York, 1996. [[Bruce Schneier]], p. 467.</ref>

{{anchor|OriginalWithPhiN}}In the original RSA paper,<ref name=rsa /> the [[Euler totient function]] {{math|1=''&phi;''(''n'') = (''p'' − 1)(''q'' − 1)}} is used instead of {{math|''&lambda;''(''n'')}} for calculating the private exponent {{mvar|d}}. Since {{math|''&phi;''(''n'')}} is always divisible by {{math|''&lambda;''(''n'')}}, the algorithm works as well. The possibility of using [[Euler totient function]] results also from [[Lagrange's theorem (group theory)|Lagrange's theorem]] applied to the [[multiplicative group of integers modulo n|multiplicative group of integers modulo ''pq'']]. Thus any {{mvar|d}} satisfying {{math|1=''d''⋅''e'' ≡ 1 (mod ''&phi;''(''n''))}} also satisfies {{math|1=''d''⋅''e'' ≡ 1 (mod ''&lambda;''(''n''))}}. However, computing {{mvar|d}} modulo {{math|''&phi;''(''n'')}} will sometimes yield a result that is larger than necessary (i.e. {{math|1=''d'' &gt; ''&lambda;''(''n'')}}). Most of the implementations of RSA will accept exponents generated using either method (if they use the private exponent {{mvar|d}} at all, rather than using the optimized decryption method [[#Using the Chinese remainder algorithm|based on the Chinese remainder theorem]] described below), but some standards such as [https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-4.pdf#page=63 FIPS&nbsp;186-4] (Section B.3.1) may require that {{math|''d'' &lt; ''&lambda;''(''n'')}}. Any "oversized" private exponents not meeting this criterion may always be reduced modulo {{math|''&lambda;''(''n'')}} to obtain a smaller equivalent exponent.

{{anchor|CryptoStrengthOfPQ}}Since any common factors of {{math|(''p'' − 1)}} and {{math|(''q'' − 1)}} are present in the factorisation of {{math|''n'' − 1}} = {{math|''pq'' − 1}} = {{math|(''p'' − 1)(''q'' − 1) + (''p'' − 1) + (''q'' − 1)}},<ref>{{cite web|title=Further Attacks on Server-Aided RSA Cryptosystems |first1=James |last1=McKee |first2=Richard |last2=Pinch |citeseerx=10.1.1.33.1333 |year=1998|url=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=64294c404088b69a519614510b8d12b4809a6b10}}</ref>{{self published inline|date=December 2023|reason=This paper is not from a journal and may not have been peer-reviewed}} it is recommended that {{math|(''p'' − 1)}} and {{math|(''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>{{cite mailing list |title=common factors in (''p'' − 1) and (''q'' − 1) |first=Viktor |last=Dukhovni |mailing-list=openssl-dev |url=https://mta.openssl.org/pipermail/openssl-dev/2015-July/002266.html |date=July 31, 2015}}</ref>{{Failed verification|date=April 2022}}<ref>{{cite mailing list |title=common factors in (''p'' − 1) and (''q'' − 1) |first=Viktor |last=Dukhovni |mailing-list=openssl-dev |url=https://mta.openssl.org/pipermail/openssl-dev/2015-August/002277.html |date=August 1, 2015}}</ref>{{Failed verification|date=April 2022}}

Note: The authors of the original RSA paper carry out the key generation by choosing {{mvar|d}} and then computing {{mvar|e}} as the [[modular multiplicative inverse]] of {{mvar|d}} modulo {{math|''&phi;''(''n'')}}, whereas most current implementations of RSA, such as those following [[PKCS1|PKCS#1]], do the reverse (choose {{mvar|e}} and compute {{mvar|d}}). Since the chosen key can be small, whereas the computed key normally is not, the RSA paper's algorithm optimizes decryption compared to encryption, while the modern algorithm optimizes encryption instead.<ref name="rsa" /><ref>{{Cite IETF |rfc=3447 |title=Public-Key Cryptography Standards (PKCS) #1: RSA Cryptography Specifications Version 2.1 |last=Johnson |first=J. |last2=Kaliski |first2=B. |date=February 2003 |publisher=Network Working Group |access-date=9 March 2016}}</ref>

===Key distribution===
Suppose that [[Alice and Bob|Bob]] wants to send information to [[Alice and Bob|Alice]]. If they decide to use RSA, Bob must know Alice's public key to encrypt the message, and Alice must use her private key to decrypt the message.

To enable Bob to send his encrypted messages, Alice transmits her public key {{math|(''n'', ''e'')}} to Bob via a reliable, but not necessarily secret, route. Alice's private key {{math|(''d'')}} is never distributed.

===Encryption===
After Bob obtains Alice's public key, he can send a message {{mvar|M}} to Alice.

To do it, he first turns {{mvar|M}} (strictly speaking, the un-padded plaintext) into an integer {{mvar|m}} (strictly speaking, the [[Padding (cryptography)|padded]] plaintext), such that {{math|0 &le; ''m'' &lt; ''n''}} by using an agreed-upon reversible protocol known as a [[#Padding schemes|padding scheme]]. He then computes the ciphertext {{mvar|c}}, using Alice's public key {{mvar|e}}, corresponding to

<math display="block">c \equiv m^e \pmod{n}.</math>

This can be done reasonably quickly, even for very large numbers, using [[modular exponentiation]]. Bob then transmits {{mvar|c}} to Alice. Note that at least nine values of {{mvar|m}} will yield a ciphertext {{mvar|c}} equal to
{{mvar|m}},{{efn|Namely, the values of {{mvar|m}} which are equal to −1, 0, or 1 modulo {{mvar|p}} while also equal to −1, 0, or 1 modulo {{mvar|q}}. There will be more values of {{mvar|m}} having {{math|1=''c'' = ''m''}} if {{math|''p''&nbsp;−&nbsp;1}} or {{math|''q''&nbsp;−&nbsp;1}} has other divisors in common with {{math|''e''&nbsp;−&nbsp;1}} besides 2 because this gives more values of {{mvar|m}} such that <math>m^{e-1} \bmod p = 1</math> or <math>m^{e-1} \bmod q = 1</math> respectively.}} but this is very unlikely to occur in practice.

===Decryption===
Alice can recover {{mvar|m}} from {{mvar|c}} by using her private key exponent {{mvar|d}} by computing

<math display="block">c^d \equiv (m^e)^d \equiv m \pmod{n}.</math>

Given {{mvar|m}}, she can recover the original message {{mvar|M}} by reversing the padding scheme.

===Example===
Here is an example of RSA encryption and decryption:{{efn|The parameters used here are artificially small, but one can also [[b:Cryptography/Generate a keypair using OpenSSL|OpenSSL can also be used to generate and examine a real keypair]].}}

# Choose two distinct prime numbers, such as
#: <math>p = 61</math> and <math>q = 53</math>.
# Compute {{math|1=''n'' = ''pq''}} giving
#: <math>n = 61\times 53 = 3233.</math>
# Compute the [[Carmichael's totient function]] of the product as {{math|1=''&lambda;''(''n'') = [[least common multiple|lcm]](''p'' − 1, ''q'' − 1)}} giving
#: <math>\lambda(3233) = \operatorname{lcm}(60, 52) = 780.</math>
# Choose any number {{math|1 &lt; ''e'' &lt; 780}} that is [[coprime]] to 780. Choosing a prime number for {{mvar|e}} leaves us only to check that {{mvar|e}} is not a divisor of 780.
#: Let <math>e = 17</math>.
# Compute {{mvar|d}}, the [[modular multiplicative inverse]] of {{math|''e'' (mod ''&lambda;''(''n''))}}, yielding<br /><math display="block">d = 413,</math> as <math>1 = (17 \times 413) \bmod 780.</math>

The '''public key''' is {{math|1=(''n'' = 3233, ''e'' = 17)}}. For a padded [[plaintext]] message {{mvar|m}}, the encryption function is
<math display="block">\begin{align}
 c(m) &= m^{e} \bmod n \\
      &= m^{17} \bmod 3233.
\end{align}</math>

The '''private key''' is {{math|1=(''n'' = 3233, ''d'' = 413)}}. For an encrypted [[ciphertext]] {{mvar|c}}, the decryption function is
<math display="block">\begin{align}
 m(c) &= c^{d} \bmod n \\
      &= c^{413} \bmod 3233.
\end{align}</math>

For instance, in order to encrypt {{math|1=''m'' = 65}}, one calculates
<math display="block">c = 65^{17} \bmod 3233 = 2790.</math>

To decrypt {{math|1=''c'' = 2790}}, one calculates
<math display="block">m = 2790^{413} \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 {{math|1=''n'' = 3233}} (obtained from the freely available public key) back to the primes {{mvar|p}} and {{mvar|q}}. {{mvar|e}}, also from the public key, is then inverted to get {{mvar|d}}, thus acquiring the private key.

Practical implementations use the [[Chinese remainder theorem]] to speed up the calculation using modulus of factors (mod ''pq'' using mod ''p'' and mod ''q'').

The values {{mvar|d<sub>''p''</sub>}}, {{mvar|d<sub>''q''</sub>}} and {{mvar|q<sub>inv</sub>}}, which are part of the private key are computed as follows:
<math display="block">\begin{align}
           d_p &= d \bmod (p-1) = 413 \bmod (61 - 1) = 53, \\
           d_q &= d \bmod (q-1) = 413 \bmod (53 - 1) = 49, \\
  q_\text{inv} &= q^{-1} \bmod p = 53^{-1} \bmod 61 = 38 \\
               &\Rightarrow (q_\text{inv} \times q) \bmod p = 38 \times 53 \bmod 61 = 1.
\end{align}</math>

Here is how {{mvar|d<sub>''p''</sub>}}, {{mvar|d<sub>''q''</sub>}} and {{mvar|q<sub>inv</sub>}} are used for efficient decryption (encryption is efficient by choice of a suitable {{mvar|d}} and {{mvar|e}} pair):
<math display="block">\begin{align}
  m_1 &= c^{d_p} \bmod p = 2790^{53} \bmod 61 = 4, \\
  m_2 &= c^{d_q} \bmod q = 2790^{49} \bmod 53 = 12, \\
    h &= (q_\text{inv} \times (m_1 - m_2)) \bmod p = (38 \times -8) \bmod 61 = 1, \\
    m &= m_2 + h \times q = 12 + 1 \times 53 = 65.
\end{align}</math>

===Signing messages===
Suppose [[Alice and Bob|Alice]] uses [[Alice and Bob|Bob]]'s public key to send him an encrypted message. In the message, she can claim to be Alice, but Bob has no way of verifying that the message was from Alice, since anyone can use Bob's public key to send him encrypted messages. In order to verify the origin of a message, RSA can also be used to [[digital signature|sign]] a message.

Suppose Alice wishes to send a signed message to Bob. She can use her own private key to do so. She produces a [[cryptographic hash function|hash value]] of the message, raises it to the power of {{mvar|d}} (modulo {{mvar|n}}) (as she does when decrypting a message), and attaches it as a "signature" to the message. When Bob receives the signed message, he uses the same hash algorithm in conjunction with Alice's public key. He raises the signature to the power of {{mvar|e}} (modulo {{mvar|n}}) (as he does when encrypting a message), and compares the resulting hash value with the message's hash value. If the two agree, he knows that the author of the message was in possession of Alice's private key and that the message has not been tampered with since being sent.

This works because of [[exponentiation]] rules:
<math display="block">h = \operatorname{hash}(m),</math>
<math display="block">(h^e)^d = h^{ed} = h^{de} = (h^d)^e \equiv h \pmod{n}.</math>

Thus the keys may be swapped without loss of generality, that is, a private key of a key pair may be used either to:
# Decrypt a message only intended for the recipient, which may be encrypted by anyone having the public key (asymmetric encrypted transport).
# Encrypt a message which may be decrypted by anyone, but which can only be encrypted by one person; this provides a digital signature.