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.