Leonhard Euler and cryptography
Leonhard Euler was a Swiss mathematician, physicist and astronomer.
Euler was probably the most prolific mathematician of all time, having produced nearly 900 publications and works and made fundamental contributions to the most diverse fields of mathematics.
His contribution to number theory is important for cryptography, particularly for the introduction of the Euler function and the proof of the Fermat-Euler theorem, which form the basis of the RSA code today.
Euler’s life
Euler was born in Basel on April 15, 1707, son of Paul Euler, a Protestant pastor, and Marguerite Brucker. Two sisters, Anna Maria and Maria Magdalena, were born after him.
Paul Euler was a friend of the Bernoulli family and of Johann Bernoulli, one of Europe’s most famous mathematicians, who had much influence on Leonhard.
Euler entered the University of Basel as a 13-year-old and graduated with a degree in philosophy. At that time, he also received mathematics lessons from Johann Bernoulli, who had discovered his enormous talent.
Euler’s father wanted his son to become a theologian and made him study Greek and Hebrew, but Bernoulli convinced him that his destiny was mathematics instead.
The years that followed were marked by work, travels, and meetings in a historical period dense with sociopolitical changes, especially in Europe.
After several moves between Russia and Germany, Euler’s eyesight deteriorated considerably, until he became completely blind in his right eye in 1735, caused a brain fever.
As the political situation in Russia stabilized, Catherine the Great, who came to power in 1766, invited him to St. Petersburg. He accepted and returned to the motherland, where he remained until his death on September 18, 1783.
Euler’s theorem
Euler’s Theorem is a fundamental result in number theory, with significant implications in the field of public key cryptography, particularly in the RSA encryption algorithm, and is closely related to Euler’s Totient Function, often referred to as φ(n).
Euler’s Theorem states that for any integer a and n that are coprime (i.e., mcd(a, n) = 1), the following congruence aφ(n) ≡ 1(mod n) holds, where φ(n) is Euler’s totient function, which counts the number of integers up to n that are coprime with n.
To understand Euler’s Theorem in depth, it is essential to first understand Euler’s Totient function, the concept of modular arithmetic, and the notion of coprimality.
The Totient function
Euler’s function associates with a positive integer n the number of prime integers with n and less than n (including one); otherwise called the p such that mcd(n, p) = 1.
This is a basic function of number theory, intervening in many theorems such as the Fermat-Euler theorem, as well as being one of the basic ingredients of RSA encryption.
For example, for n = 6 the Euler function is worth 2 because the integers prime with 6 and less than 6 are only 1 and 5; for n = 7 the function is worth 6 because since 7 is prime all numbers preceding it are prime with 7.
Application in cryptography
Euler’s theorem is particularly significant in the RSA encryption algorithm, which is a widely used public-key cryptosystem.
RSA is based on the difficulty of factoring large composite numbers and uses the properties of Euler’s totient function and modular arithmetic.
In RSA, two large prime numbers p and q are chosen and their product n = pq is used as the module for both the public and private keys. The total φ(n) is calculated as φ(n) = (p-1)(q-1).
A public exponent e is chosen such that e<φ(n) and mcd(e, φ(n)) = 1. The private exponent d is then computed as the modular multiplicative inverse of e module φ(n), i.e., ed ≡ 1(mod φ(n)).
The public key is (e, n) and the private key is (d, n).
To encrypt a message M, the sender computes the ciphertext C as: C ≡ Me (mod n).
To decrypt ciphertext C, the receiver computes the original message M as: M ≡ Cd (mod n).
To decipher the ciphertext C, the receiver computes the original message M as: M ≡ Cd (mod n).
Euler’s Theorem guarantees that this decryption process works correctly because: Med ≡ M (mod n).
Given this ed ≡ 1 (mod φ(n), there exists an integer k such that: ed = 1 + kφ(n).
Thus, Med = M1+kφ(n) = M (Mφ(n))k ≡ M1k = M (mod n).
This demonstrates the correctness and security of the RSA algorithm, supported by Euler’s Theorem.
A life for mathematics: the legacy of Euler
Euler was undoubtedly the greatest purveyor of “mathematical designations,” offering his name to an impressive number of formulas, theorems, methods, criteria, relations, and equations, and he also made important contributions to physics and in particular to classical and celestial mechanics.
A total of 886 publications by Euler exist. Much of the mathematical symbology still in use today was introduced by Euler, for example i for imaginary unit, Σ as a symbol for summation, f(x) to denote a function, and the letter π to denote pi.
In the world of cryptography, and applied mathematics in general, he is certainly credited with making a fundamental contribution to the birth of RSA cryptography, an essential element of the security of our time.