|
1(mod f(n)) with public key e and totient function (PL) f(n)
coprime(have only unity as common factor). The message-sender converts
the message to number, M, makes public n, e
and sends E
Me (mod m). In
decoding, the receiver (knowing d computes E
d
(Me)d
Med
MN f(n)+1
M (mod n), for integer N. To "crack" (decode) the code,
d must be discovered, requiring factoring of
n, since f = (p - 1)(q - 1). The
sender should arrange that p ± 1, q ± 1 are divisible
by large primes -- else, Pollard p-1 factoring (PL) or Williams p+1 factoring
might easily factor n. Also desirable to choose
f(f(n)) large, and divisble by
large primes. Repeated use of this encription may lead to cracking if a unit
of Z/f(n)Z has small order, where Z/sZ is the ring
of integers (PL) between 0 and s - 1
under addition and multiplication mod(s. (However, Meijer in 1996
suggested ways of avoiding this.) Under RSA, the sender's identity can be validated w/o
revealing his/her private code.