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 (zk)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):
(zk)s
= zk · s
= z[(p - 1)(q - 1) · t + 1]
= z[(N) · t + 1 ]
= (z(N))t ·z1
= z (mod N).
Back to the previous codes page.
Back to the first codes page.
© copyright 1999, American Mathematical Society.