14,443
edits
(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]] {{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''))}}. However,
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 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>
