Euler: The Father of Mathematics and Layer of Internet Security

Euler: One of The Fathers of Mathematics And Creators of a Foundation of Internet Security

For me, Leonhard Euler is one of the fathers of modern 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 and in the security of the Internet.

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

Because of Euler’s Theory, we can state that:

In the following p, q, p′ and q′ are all prime numbers. If so we have the following truths:

The first of these is the foundation of RSA:

Let’s take a simple example of g=3, p=11, x=101:

It is these little bits of magic, that support methods such as RSA. The coding to prove these is here:

and the code is:

import random

from Crypto.Util.number import getPrime
from Crypto.Random import get_random_bytes

import sys
import sympy

primebits=16

if (len(sys.argv)>1):
  primebits=int(sys.argv[1])

if primebits>48: primebits=48

while (True): 
  p_1 = getPrime(primebits, randfunc=get_random_bytes)
  q_1= getPrime(primebits, 
  randfunc=get_random_bytes)
  p=2*p_1+1
  q=2*q_1+1
  if (sympy.isprime(p) and sympy.isprime(q)): break;

g=3
x=random.randint(0,2**512)

n=p*q

res1=pow(g,x,n)

res2=pow(g,x % (n),n)

print (f"p={p}, q={q}, p'={p_1}, q'={q_1}, n={n}")

print (f"\ng^x (mod n)={res1}\ng^(x (mod n)) (mod n) ={res2}")
if (res1==res2): print(" The same")
else: print(" Not the same")

res2=pow(g,x % (p_1*q_1),n)

print (f"\ng^x (mod n)={res1}\ng^(x (mod (p'q'))) (mod n) ={res2}")
if (res1==res2): print(" The same")
else: print(" Not the same")

res2=pow(g,x % ((p-1)*(q-1)),n)

print (f"\ng^x (mod n)={res1}\ng^(x (mod (p-1)(q-1))) (mod p) ={res2}")
if (res1==res2): print(" The same")
else: print(" Not the same")

res1=pow(g,x,p)
res2=pow(g,x % (p-1),p)

print (f"\ng^x (mod p)={res1}\ng^(x (mod p-1)) (mod p) ={res2}")
if (res1==res2): print(" The same")
else: print(" Not the same")

A sample run is:

p=116099, q=126839, p'=58049, q'=63419, n=14725881061

g^x (mod n)=2833123105
g^(x (mod n)) (mod n) =10920218514
 Not the same

g^x (mod n)=2833123105
g^(x (mod (p'q'))) (mod n) =2833123105
 The same

g^x (mod n)=2833123105
g^(x (mod (p-1)(q-1))) (mod p) =2833123105
 The same

g^x (mod p)=75307
g^(x (mod p-1)) (mod p) =75307
 The same

And here is the code:

Conclusions

It’s real shame that our kids know little of Leonhard Euler, or even of John Napier, but can tell you about Newton and Einstein. Both Euler and Napier have helped fixed the core flaws of the Internet, and continue to do so. If there is a Maths teacher at school who is struggling to show the relavent of logarithms in the class, there is no better example than the thing that saved the Internet: the Diffie Hellman key exchange method. Without that, the Internet could be one big spying network.

And did you known that Napier’s constant (2.718281828459) of e is named after Euler (‘E’uler’s constant)?

Go fall in love with numbers!