UNREASONABLE EFFECTIVENESS OF NUMBER THEORY
11
given by a number in the same range, calculated as follows
E =
Ms
mod r . (6)
Decrypting E is accomplished by calculating
El
mod r, where the decrypting
exponent t is given by
ts = 1 mod (j)(r) , (7)
i.e., ts = kj(r) + 1 for some k. With such at,
El
=
Mst
=M
k
^
( r ) + 1
mod r .
which, according to Euler's theorem, give the message M back.
So far, so good and - theoretically - trivial. The trick in public-key
encryption is to choose r as the product of two very large primes, each say 200
digits long. (There is no paucity of such primes, and enough for all
foreseeable purposes can be easily ferreted out from the jungle of composites
in the
10200
neighborhood.)
Now, with a composite r, prescription (7), so easily written down,
becomes practically impossible to apply because j)(r) can be calculated only
if the factors of r are known - and this knowledge is not published. In modern
parlance, the mapping (6) is a trap-door function.
A trap-door function is, as the name implies, a (mathematical) function
that is easy to calculate in one direction but very hard to calculate in the
opposite direction. For example, it takes a modern computer only
microseconds to multiply two 100-digit numbers. By contrast, to decompose
a 200-digit number, having two 100-digit factors, into its factors can take
"forever," even on the fastest computers available in 1992 and using the most
efficient factoring algorithms known today [3].
On the other hand, knowing the factors of r, as the legitimate recipient of
the encrypted message E does, j(r) can be easily calculated and decrypting
becomes possible. The decrypting exponent t is obtained by Euclid's
algorithm [7] or by solving (7) directly:
t s s * ^ " "
1
mod (j)(r) .
Previous Page Next Page