Cryptology

We see now some applications of Euler's theorem in the field of Cryptology, the science of secure messages. The aim of cryptography is to send messages across a channel so that only the intended recipient of the message can read it.

The message to be sent is called the plaintext message. The disguised message is called the ciphertext. The plaintext and the ciphertext are both written using alphanumeric characters. Characters can include the familiar alphabetic characters a, A, ..., Z, z and also digits, punctuation marks, and blanks. A cryptosystem, or cipher, is characterized by two parts: encryption, the process of transforming a plaintext message to a ciphertext message, and decryption, the reverse transformation of changing a ciphertext message into a plaintext message.

Symmetric (or private key) encryption algorithms encrypt and decrypt with the same key. Asymmetric (or Public-key encryption) encryption algorithms encrypt and decrypt with different keys: Data is encrypted with a public key and decrypted with a private key.

An early cryptological system, called the Caesar cipher, was employed by Julius Caesar in the Gallic wars. Julius Caesar used a cipher that simply shifted each letter in the alphabet three letters to the right in this way (A → D, B → E, etc.). This is an example of a shift cipher, sometimes called a Caesar cipher, in which each letter is shifted by a fixed number, k, of places in the alphabet. This is equivalent to representing each letter from A to Z by the “numbers” 1, 2, 3, ..., 25 and the cipher merely replaces a given letter X by the letter X + k. In the cipher adopted by Ceaser

to 1, i.e. A, corresponds 1 + 3 = 4, thus D, to B = 2 corresponds 2 + 3 = 5 which is E and so on. If we try now to cipher the letter X which corresponds to 24 we get 24 + 3 = 27 which does not correspond to any letter. To avoid this inconvenient, and be able to assign all letters of the alphabet we operate mod 26.

Accepting the notational convention: a mod n is the remainder when a is divided by n; in this way 27 mod 26 = 1 and 1 corresponds to A. Analogously for Y = 25 and 28 ≡ 2 mod 26, yielding the B letter.

That is there is a bijective function on the set of the Alphabet letters which can be inverted by the receiver to decipher the crypted message. This is equivalent to say that function (4.11) is a bijection on the set ℤ₂₆ = {[1], [2], ..., [26]}. We can invert 4.11 obtaining x ≡ y − 3 (mod 21). So if y = 4 is the cipher text which corresponds to D, we have x ≡ 1 mod 21, so the original message is x = 1 which is A.

Inspired by this result we can choose different enciphering functions, for example

now if we take a = 5 and b = 3, then the letter D which is x = 4, is ciphered to 5x + 3 = 23 (mod 21) thus 23 ≡ 2 (mod 21), and y = 2 is letter B.

We must be careful when chosing a, because as we said the enciphering must be biunique, which is equivalent to say that the equation ax + b ≡ y mod 26 must have a unique solution. By taking b to the right side we have the equivalente equation ax ≡ y − b mod 26. We have seen the condition for the existence of such an unique solution of this equation is (a,26) = 1 (see Proposition 4.18). This condition guarantees a to have an inverse a⁻¹ mod 26 and consequently by multiplying both sides of the equation by a⁻¹

which is the inverse function to decipher the message.

Public-Key Systems: RSA

The RSA encryption system by Rivest, Shamir, and Adleman, is the most popular asymmetric encyption algorithm. It is based on the difficulty of factoring large numbers and on (Euler’s theorem of 1760) to make this work. We begin by choosing two distinct prime numbers, which we label as p and q, and we form the product

This is the heart of the matter: the value of n is the publick key, but the values of p and q are secret, they make the private key. The larger the value of n, the more secure this system will be, since breaking the code relies on knowing the prime factors p and q of n. Next we choose e to be relatively prime to the product φ(n) = (p − 1)(q − 1); that is, e is defined by (e, φ(n)) = 1.

The exponential enciphering operation is y ≡ x^e (mod n).

We suppose the message x to satisfy the following condition: x < n.

The first requirement. For the second is enough to chunk the original message into smaller pieces.

The receiver who got the ciphertext y can decipher it in the following way: since e is relatively prime to φ(n), it is invertible modulo φ(n); we call its inverse d.

At this point we affirm that the plaintext x can be recovered by the inverse mapping

Proof. Since y ≡ x^e (mod n) elevating to the power d we have

to conclude that y ≡ x^e (mod n) is enough to prove that

We use now Euler’s theorem, under the conditions (x,n) = 1 (this is always possible to attain: if x is not relatively prime to n add a letter to it), and x < n. We have

by definition d is the inverse of e mod φ(n) i.e. ed ≡ 1 mod φ(n) which means in other words, there exists an integer k such that ed = 1 + kφ(n). Thus we can write

By Euler’s theorem, x^φ(n) ≡ 1 (mod n), if we both sides of the congruence by k we have

then by multiplying both members of this equality by x we get

thus

by adding up (4.12) and (4.13) we completed the proof.□

Authentication of signatures with the RSA system

The RSA cryptosystem, allows one to solve of an important problem which is more and more relevant in this era of telecommunications: the problem of digitally authenticating a signature. If Bob receives a message from a person signing herself Alice, how can he be sure the sender was actually Alice? The certainty may be achieved as follows. Alice writes her message M₁, putting at the end her signature F; to authenticate the signature, Alice adds after the message M₁ the message

where d_A is her private key, that is, the key known only to her, because only she knows the factorisation of her public key n_A. Then she sends Bob the message M consisting of the two messages M₁ and M₂ as usual, that is, raising M₁ and M₂ to the power e_B and reducing them modulo n_B.

On receiving the message, Bob reads it using her private key d_B. Deciphering message M₁, she learns that the message was sent by Alice, because the message is signed with Alice’s signature F. But was really Alice, and not someone else, who used that signature? Here the section M₂ of the message gives an answer. Indeed, it consists of some undecipherable characters, which nevertheless contain the proof of the authenticity of the signature. Now Bob, to verify the authenticity, has to proceed as follows. To decipher M₂ she cannot use her private key d_B, which would be useless, as the original message F was enciphered raising it not to the power e_B but to d_A. Instead, Bob uses Alice’s public key e_A. In this way she obtains Alice’s signature F, because

This signature has to be authentic, as only Alice knows her private key. If what appeared were not Alice’s signature F, the message would have been a fake. Basically, to authenticate a signature, the sender uses her private key, rather than the public keys of the receiver.