Image for post
Image for post

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:

Image for post
Image for post

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

Image for post
Image for post

The first of these is the foundation of RSA:

Image for post
Image for post

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

Image for post
Image for post

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 randomfrom Crypto.Util.number import getPrime
from Crypto.Random import get_random_bytes
import sys
import sympy
primebits=16if (len(sys.argv)>1):
primebits=int(sys.argv[1])
if primebits>48: primebits=48while (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*qres1=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=14725881061g^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!

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles…

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Prof Bill Buchanan OBE

Written by

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. EU Citizen. Auld Reekie native. Old World Breaker. New World Creator.

ASecuritySite: When Bob Met Alice

This publication brings together interesting articles related to cyber security.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store