Thank Euclid For Your Online Security!

Thank Euclid For Your Online Security!

Around 325 BC, Eulicid wrote his Elements treatise and created the foundations of geometry — now known as Euclidean geometry. And, so, we must also thank Euclid our online security, as Euclidean methods often provide a core in public key encryption. One of the most well-known implementations is within the RSA method, and where we use Euclidian methods to solve complex equations, along with Fermat’s Little Theorem:

One of the most predominant methods with Euclidean methods, and is the efficient calculation of the largest common factor (gcd — greatest common denominator) between two numbers. For example:

gcd(27,15) = 3

gcd(27,13) =1

With this, in cryptography, we often focus on making sure that two values do not share the same factor, and thus often use gcd(a,b)=1. Another widely used method is known as the Extended Euclidean method, and where we find a solution for:

a.x+b.y=gcd(a,b)

With this, we know the values of a and b and want to discover x and y. In this case, gcd(a,b) defines the greatest common denominator between a and b, and if a and b do not share a factor, gcd(a,b) will be 1.

For example, if a=5 and b=6, we can use the Extended Euclidean method (xgcd()) with:

import libnum
a=5
b=6
(x,y,r) = libnum.xgcd(a,b)
print (x,y,r)

This gives:

-1 1 1

In this case, we have −1(5)+1(6)=1 and which is true. If we now try b=8, we get a result of:

-3 2 1

This gives us −3(5)+2(8)=1 and which is true.

RSA and Extended Euclidian

One of the best usages of the Extended Euclidian method is in RSA encryption. For this, we take two prime numbers (p and q) and determine the public modulus (N):

N = p.q

Next we compute PHI:

PHI = (p-1) . (q-1)

We then pick our encryption exponent (e) to not share a factor with PHI, then compute the decryption exponent (d) with:

d.e = 1 (mod PHI)

This is in the form of the Extended Euclidian method, and where we can compute:

(d,_,r) = libnum.xgcd(e,PHI)

The code to implement this is:

>>> e=7
>>> p=97
>>> q=101
>>> N=p*q
>>> PHI=(p-1)*(q-1)
>>> import libnum
>>> print (libnum.gcd(e,PHI))
1
>>> (d,_,r) = libnum.xgcd(e,PHI)
>>> print (d,r)
2743 1
>>> print (d*e % PHI)
1

We can now encrypt and decrypt with these values:

>>> M=5
>>> C=pow(M,e,N)
>>> print (C)
9546
>>> Rec=pow(C,d,N)
>>> print (Rec)
5

Determine k-th root of n (mod p)

We can use the Extended Euclidian method to determine the k-th root of a value (n) modulo p. With this, we have the form of:

and if gcd(k,p−1)=1, there exists a solution of m and t in:

This is in the form of the Extended Euclidian method, and the solution is then [1]:

The code to find the value of m and the root is then [here]:

import sys
from libnum import xgcd
def findnroot(n,k,p):
    (m,s,v) = xgcd(k,p-1)
    if (v==1):
        return(pow(n,m,p))

A few examples of these are [here]:

2nd root of 5 (mod 11) = None
3rd root of 5 (mod 11) = 3
4th root of 5 (mod 11) = None
5th root of 5 (mod 11) = None
6th root of 5 (mod 11) = None
7th root of 5 (mod 11) = 4
8th root of 5 (mod 11) = None
9th root of 5 (mod 11) = 9
10th root of 5 (mod 11) = None

3³ (mod 11) gives you 5, and 4⁷ (mod 11) gives 5. Notice, there are a few that do not give any roots, as there is no basic solution for that root. This is either because there is no root, or that the gcd(k,n-1) is not equal to 1.

Some simple code uses the Extended Euliclidian method for the root is [here]:

import sys
from libnum import xgcd

def findnroot(n,k,p):
    (m,s,v) = xgcd(k,p-1)
    if (v==1):
        return(pow(n,m,p))
        
p=17
n=2
if (len(sys.argv)>1):
    n=int(sys.argv[1])
if (len(sys.argv)>2):
    p=int(sys.argv[2])
    
for root in range(2,p):
    if (root>50): break
    v=findnroot(n,root,p)
    if (root==2): print(f"{root}nd root of {n} (mod {p}) = {v}")
    elif (root==3): print(f"{root}rd root of {n} (mod {p}) = {v}")
    else: print(f"{root}th root of {n} (mod {p}) = {v}")

Conclusions

And there you go … thank Euclid for your online security!