How Euler Secured The World

How Euler Secured The World

Leonhard Euler is defined as the father of mathematics. He lived from 1707 to 1783, and had a stunning research career, including contributions to mechanics, music and fluid dynamics. His shadow thus looms large over our modern world, including within cryptography.

One of his great theorems defined that:

aᴺ⁻¹≡1 (mod N)

The key factor here is that a and N should not share the same factors. We often define this as gcd(a,N)=1, and where gcd() is the greatest common denominator. If we use a few values of a and N we see [Try]:

>>> print 6**(6) % 7
1
>>> print 7**(10) % 11
1
>>> print 3**(16) % 17
1

We can also use two values for N, such as p and q, and where the power becomes (p-1)(q-1) [Try]:

>>> print 3**(16*10) % (17*11)
1
>>> print 5**(22*10) % (23*11)
1

RSA

Over the past 40 years or so, the RSA (Rivest, Shamir and Adelman) method has been a core technique in proving identity and also in passing secrets. It uses a trap-door method, and where a public and a private work together, and where one can encrypt and the other can decrypt.

With public encryption, when we want to prove identity — the ownership of a secret that only we know — we encrypt something with our private key, and then others can prove this signing with our public key. This is common where Bob wants to prove his identity to Alice, and where Alice has a trusted version of his public key.

If we want to pass a secret, we would encrypt something with the public key of the other side, and then they can decrypt with their private key. This is a common method in key exchange, and where Bob and Alice can negotiate the same secret key.

The core of the RSA method, though, is built around Euler’s Theorem, and which defines that:

aᵠ≡1 (mod N)

and where N=pq and φ=(p−1)(q−1)

If we try a value of a=3, p=7 and q=11, a and N are co-prime, thus the result is 1 [Try]:

a=	3
p=	7
q=	11
PHI=	60
----------
N and a are co-prime, and this should work
----------
Result of a^{PHI} (mod N)= 1

If we try a value of a=3, p=8 and q=9, a and N are NOT co-prime (as the share a common factor of 3), thus the result will not be 1 [Try]:

a=	3
p=	8
q=	9
PHI=	56
----------
This will not work as N and a are not co-prime
----------
Result of a^{PHI} (mod N)= 9

An outline of the code used is:

import sys

p=101
q=103
a=7

def gcd(a, b):
    
	while( b != 0 ):
		Remainder = a % b;
		a = b;
		b = Remainder;
	return a;

N=p*q 
PHI=(p-1)*(q-1)

res = gcd(N,a)

val = a** (PHI) % N

print "a=\t",a
print "p=\t",p
print "q=\t",q
print "PHI=\t",PHI
print "----------"

if (res>2): 
	print "This will not work as N and a are not co-prime"
else:
	print "N and a are co-prime, and this should work"
print "----------"
print "Result of a^{PHI} (mod N)=",val

Here is an overview of how the RSA method works:

Conclusions

Isn’t Euler’s theorem so simple and so beautiful. In an online world that needs more trust, public key encryption comes to our rescue, and we must say thank you to Euler for the past 40 years of service in his magical theorem?

As I sit in John Napier’s Tower — and remember the person who created logarithms and which provide such a core around discrete logarithms in cryptography — I also remember that Napier’s constant (2.718281828459) was given the name of e after Euler’s (‘E’uler’s constant).