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) =…
