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.
