e-MATH
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 importance of phi(N) here is: Now the calculation can be finished, using this theorem and phi(N) = (p - 1)(q - 1):

(zk)s = zk · s = z[(p - 1)(q - 1) · t + 1] = z[phi(N) · t + 1 ] = (zphi(N))t ·z1 = z (mod N).


Back to the previous codes page.

Back to the first codes page.



© copyright 1999, American Mathematical Society.