RSA (cryptosystem): Difference between revisions

→‎Operation: clarify text, link to further section instead of direct to CRT, add missing space
(Undid revision 762152811 by 84.241.198.57 (talk): if (m^e)^d was m^e, then RSA decryption would do nothing at all)
(→‎Operation: clarify text, link to further section instead of direct to CRT, add missing space)
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''.
 
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''))}}. However, butcomputing it''d'' modulo ''φ''(''n'') will sometimes yield a private exponent ''d''result 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 optimizationoptimized decryption method [[#Using the Chinese remainder algorithm|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|''n'' − 1}} = {{nowrap|''pq'' − 1}} = {{nowrap|(''p'' − 1)(''q'' − 1) + (''p'' − 1) + (''q'' − 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>