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
where
and 
,
, 
, 
, 
,
and 
are all primes. In this case,
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.
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
Cite this as:
Weisstein, Eric W. "RSA Encryption." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/RSAEncryption.html