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

    ms+nt=1

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

    65x5-18x18=1

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

ks-(p-1)(q-1)t=1

or

ks=(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 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.