RSA Encryption

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


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

 de=1 (mod phi(n))

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).

To decode, the receiver (who knows d) computes

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

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


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




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


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


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", C. P. "Fast Factoring Integers by SVP Algorithms." Cryptology ePrint Archive: Report 2021/232. 1 Mar 2021., 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.

Subject classifications