Feature Column

From Euclid to public-key codes 4

From Euclid 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:

  • If two integers m and n are relatively prime, then there exist integers s and t such that


    For example, for 65 and 18 the Euclidean Algorithm produces s = 5 and t = 18:


Applying this algorithm to the numbers k and (p - 1)(q - 1) gives numbers s and t with




This is how the secret key s is calculated. This number is the mod (p - 1)(q - 1) multiplicative inverse of k since ks=(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 phi(n). Since 11 is prime, all the numbers less than 11 are relatively prime to 11, so phi(11) = 10, and similarly phi(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 phi(12) = 4.
  • If N=pq with p and q prime numbers, then phi(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 phi(N) here is:

Now the calculation can be finished using this theorem and phi(N) = (p - 1)(q - 1):

(z^k)^s=z^(ks)=z^[(p-1)(q-1)t+1]=z^[phi(N)t+1]=(z^phi(N))^t)z^1=z(mod N)

Back to the previous codes page.

Back to the first codes page.

Welcome to the
Feature Column!

These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Read more . . .

Search Feature Column

Feature Column at a glance

Show Archive

Browse subjects