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.