**From Euclid and Euler to public-key codes**

## How does a public-key code work?

The RSA system works as follows. You pick two large primes
*p* and *q*, and publish their product *N*,
your ``modulus,''
along with a number *k* chosen to be relatively prime
to (*p* - 1) · (*q* - 1).
Need to review?
relatively prime

The combination (*N*,
*k*) is your **public key**. If correspondent X
wants to send you a message, X first converts it
to numerical form in some standard way, and breaks that
numerical message into blocks of length less than the length
of *N*. So the message now looks like

*a*,*b*,...
where each of *a*, *b*, etc. is a number less than *N*.
Now X encrypts the message by raising each number to the
power *k* (mod *N*):

*a* --> *A* = *a*^{k} (mod *N*)
*b* --> *B* = *b*^{k} (mod *N*)

...

and sends you the message *A*,*B*,...

Need to review?
congruence mod *N*

Meanwhile you have calculated your **secret key** (*N*,
*s*), where *N* is your public modulus and
*s* is the multiplicative inverse of *k*
(mod (*p* - 1)(*q* - 1)). More about this calculation below.
This choice of *s* guarantees that for any number *z*

(*z*^{k})^{s} = z (mod *N*)
so that raising each of the transmitted numbers to the power *s*
will undo the encryption:

*A* --> *A*^{s} (mod *N*) = *a*
*B* --> *B*^{s} (mod *N*) = *b*

...

(since the numbers *a*, *b*, etc. are smaller than *N*,
the congruence specifies them exactly). Then the original message
can be easily reconstructed.

Note that the secret key cannot be constructed from the public
key without the knowledge of the factorization
*N* = *p* · *q*. Otherwise there is no way to
access the number (*p* - 1)(*q* - 1) used in the
calculation. If *N* is large enough, for a stranger to discover your
factorization could take, with today's best methods, practically speaking
forever.

On to the next codes page.
Back to the previous codes page.

Back to the first codes page.

© copyright 1999, American Mathematical Society.