TOPICS

# RSA Encryption

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

 (1)

for and primes. Also define a private key and a public key such that

 (2)
 (3)

where is the totient function, denotes the greatest common divisor (so means that and are relatively prime), and is a congruence. Let the message be converted to a number . The sender then makes and public and sends

 (4)

To decode, the receiver (who knows ) computes

 (5)

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

 (6)

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

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

 (7) (8)

where

 (9) (10)

and , , , , , and are all primes. In this case,

 (11) (12)

Meijer (1996) also suggests that and should be of order .

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

Congruence, Public-Key Cryptography, RSA Number

## Explore with Wolfram|Alpha

More things to try:

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

RSA Encryption

## Cite this as:

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