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

## Mopping up: how do you calculate the private key, and what makes it
work?

The number *k* was chosen to be relatively prime to
(*p* - 1)(*q* - 1).
In Book VII of the *Elements* (Proposition 1 and
Proposition 2) Euclid gives a
process which we now call the
Euclidean Algorithm. This process, essentially repeated long division,
can be used (The Extended Euclidean Algorithm)
to produce the numbers *s* and *t* which
enter into the following very useful fact:
Applying this algorithm to the numbers *k* and
(*p* - 1)(*q* - 1) gives numbers *s* and *t*
with

*k · s* - (*p* - 1)(*q* - 1)· *t* = 1
or

*k · s* = (*p* - 1)(*q* - 1)· *t* + 1.
This is how the secret key *s* is calculated.
This number is the mod (*p* - 1)(*q* - 1) multiplicative inverse of *k*
since *k · s* = (*p* - 1)(*q* - 1)· *t* + 1
= 1 (mod (*p* - 1)(*q* - 1)).

To understand why *s*
undoes *k*, i.e. why (*z*^{k})^{s}
= *z* (mod *N*) it helps to know about the Euler Phi-function.

- The Euler Phi-function assigns to an integer
*n* the number of
numbers less than *n* and relatively prime to *n*.
(The number 1 is counted!) The number *s* is
written (*n*). Since 11 is prime,
all the numbers less than 11 are relatively prime to 11, so
(11) = 10, and similarly
(*p*) = *p* - 1 for
any prime *p*. The only numbers
less than 12 which are relatively prime to 12 are 1, 5, 7 and 11,
so (12) = 4.
- If
*N*= *p* · *q* with *p*
and *q* prime numbers, then (*N*) = (*p* - 1)(*q* - 1).

This can be checked by counting the number of numbers less than
*N* which have a factor in common with *N*.

The importance of (*N*) here is:
- Euler's Theorem: For any integers
*z* and *N* which
are relatively prime,
*z*^{(N)} = 1 (mod *N*).

Now the calculation can be finished, using this theorem and (*N*) = (*p* - 1)(*q* - 1):
(*z*^{k})^{s}
= *z*^{k · s}
= *z*^{[(p - 1)(q - 1) · t + 1]}
= *z*^{[(N) · t + 1 ]}
= (*z*^{(N)})^{t} ·*z*^{1}
= z (mod *N*).

Back to the previous codes page.
Back to the first codes page.

© copyright 1999, American Mathematical Society.