TOPICS
Search

RSA Encryption


A public-key cryptography algorithm which uses prime factorization as the trapdoor one-way function. Define

 n=pq
(1)

for p and q primes. Also define a private key d and a public key e such that

 de=1 (mod phi(n))
(2)
 (e,phi(n))=1,
(3)

where phi(n) is the totient function, (a,b) denotes the greatest common divisor (so (a,b)=1 means that a and b are relatively prime), and a=b (mod m) is a congruence. Let the message be converted to a number M. The sender then makes n and e public and sends

 E=M^e (mod n).
(4)

To decode, the receiver (who knows d) computes

 E^d=(M^e)^d=M^(ed)=M^(Nphi(n)+1)=M (mod n),
(5)

since N is an integer. In order to crack the code, d must be found. But this requires factorization of n since

 phi(n)=(p-1)(q-1).
(6)

Both p and q should be picked so that p+/-1 and q+/-1 are divisible by large primes, since otherwise the Pollard p-1 factorization method or Williams p+1 factorization method potentially factor n easily. It is also desirable to have phi(phi(pq)) large and divisible by large primes.

It is possible to break the cryptosystem by repeated encryption if a unit of Z/phi(n)Z has small field order (Simmons and Norris 1977, Meijer 1996), where Z/sZ is the ring of integers between 0 and s-1 under addition and multiplication (mod s). Meijer (1996) shows that "almost" every encryption exponent e is safe from breaking using repeated encryption for factors of the form

p=2p_1+1
(7)
q=2q_1+1,
(8)

where

p_1=2p_2+1
(9)
q_1=2q_2+1,
(10)

and p, p_1, p_2, q, q_1, and q_2 are all primes. In this case,

phi(n)=4p_1q_1
(11)
phi(phi(n))=8p_2q_2.
(12)

Meijer (1996) also suggests that p_2 and q_2 should be of order 10^(75).

Using the RSA system, the identity of the sender can be identified as genuine without revealing his private code.


See also

Congruence, Public-Key Cryptography, RSA Number

Explore with Wolfram|Alpha

References

Coutinho, S. C. The Mathematics of Ciphers: Number Theory and RSA Cryptography. Wellesley, MA: A K Peters, 1999.Flannery, S. and Flannery, D. In Code: A Mathematical Journey. Profile Books, 2000.Honsberger, R. Mathematical Gems III. Washington, DC: Math. Assoc. Amer., pp. 166-173, 1985.Meijer, A. R. "Groups, Factoring, and Cryptography." Math. Mag. 69, 103-109, 1996.Rivest, R. L. "Remarks on a Proposed Cryptanalytic Attack on the MIT Public-Key Cryptosystem." Cryptologia 2, 62-65, 1978.Rivest, R.; Shamir, A.; and Adleman, L. "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems." MIT Memo MIT/LCS/TM-82, 1977.Rivest, R.; Shamir, A.; and Adleman, L. "A Method for Obtaining Digital Signatures and Public Key Cryptosystems." Comm. ACM 21, 120-126, 1978.RSA Laboratories. "The RSA Factoring Challenge" http://www.rsa.com/rsalabs/node.asp?id=2092.Schnorr, C. P. "Fast Factoring Integers by SVP Algorithms." Cryptology ePrint Archive: Report 2021/232. 1 Mar 2021. https://eprint.iacr.org/2021/232.Simmons, G. J. and Norris, M. J. "Preliminary Comments on the MIT Public-Key Cryptosystem." Cryptologia 1, 406-414, 1977.

Referenced on Wolfram|Alpha

RSA Encryption

Cite this as:

Weisstein, Eric W. "RSA Encryption." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/RSAEncryption.html

Subject classifications