Editing RSA cryptosystem (section)

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