Symmetric Key Cryptography

Sixth rule C. 68 is sexy, Φ is beautiful, 10,213,223 is cool (it describes itself when you read it), but the most important numbers are not 0, i, π, e, or N_A. It is indeed primarily your girlfriend’s number, then her mom’s number, and finally her lawyer’s number, Apocalypse, Anawim, #justtothepoint.

Cryptography is the practice and study of techniques to secretly obscure, store or communicate messages so uninvited outsiders cannot read the message. It involves two steps: encryption, in which the message is obscured, distorted, and cannot be read, and decryption, in which the original message is recovered from the obscured form, typically in plain English.

A cypher is a scheme for changing or replacing a letter (a syllable, a number, etc.) in the message with a different letter or character following a pre-established mapping, called the encryption mapping.

Plaintext is usually ordinary readable text before it is encrypted into ciphertext or, in other words, readable text after it is decrypted. The mapping is bijective so ciphertexts can be converted back to the plain text using an inverse mapping, called the decryption mapping.

Symmetric-Key Cryptography

Symmetric key cryptography is any cryptographic algorithm that is based on a shared key that is used to encrypt or decrypt text, i.e., both the sender (Alice) and the receiver use the same key for encryption and decryption.

The mappings most commonly used in cryptography are algebraic, and therefore it previously require the message to be numerical. We will use the simple rule “A” or “a” = 0, “B” or “b” = 1, “C” or “c” = 2, and so on. However, ASCII is one standard way to encode a text written in English into integers.

This is the code in Python that digitalized “MySecretMessage” as [15, 1, 21, 7, 5, 20, 7, 22, 15, 7, 21, 21, 3, 9, 7], encrypt it using the Caesar Algorithm, decrypt it, then rebuild the text from the list of digits.

def digitalize_message(text):
# Convert a message into an array or list of digits
    numbers = []
    for char in text: # It iterates over the message.
        if char.isalpha(): # It returns True if the character is an alphabet letter.
            number = ord(char.lower()) - 97
            numbers.append(number)
        else:
            numbers.append(char)
    return numbers
    
def convert_to_text(numbers):
# Reconstruct the message from the list of digits.
    letters = ''
    for num in numbers: # It iterates over the list of digits.
        if isinstance(num, int): # If it a digit, then it converts it into a letter
            letter = chr(num + 65)
            letters += letter
        else:
            letters += num
    return letters
    
def caesar_encrypt(text, a):
    numbers = digitalize_message(text) # 1st Digitalize the message.
    transformed_list = []
    for x in numbers:
        transformed_x = (x + a) % 26 # 2nd Encrypt the message using Caesar
        transformed_list.append(transformed_x)
    return transformed_list
    
def caesar_dencrypt(coded_text, a):
    transformed_list = []
    for x in coded_text:
        transformed_x = (x - a) % 26  # Decrypt the message using Caesar
        transformed_list.append(transformed_x)
    original_text = convert_to_text(transformed_list)
    return original_text
    
text = "MySecretMessage"
print(text)
coded_text = caesar_encrypt(text, 3)
print(coded_text)
print(convert_to_text(coded_text))
original_text = caesar_dencrypt(coded_text, 3)
print(original_text)

It returns:    MySecretMessage
[15, 1, 21, 7, 5, 20, 7, 22, 15, 7, 21, 21, 3, 9, 7]
PBVHFUHWPHVVDJH
MYSECRETMESSAGE

Caesar cipher is one of the earliest and simplest methods of encryption technique where each letter is replaced by another letter some fixed number of positions later in the alphabet, historically three. This fixed number is the key of a Caesar cipher.

When at the end of the alphabet, the letter will wrap around to the beginning, so it can be represented using modular arithmetic, and the encryption can be described as E_n(x) = (x + n) mod 26 -Encryption of a letter x by a shift n where the alphabet has 26 characters-, and the decryption D_n(x) = (x - n) mod 26.

This method is super easy to use and implement compared to other algorithms, but both parties must keep the key secure. Besides, this method has only 26 encryption keys, that is quite easy to break through brutal force by hackers.

An easy improvement is an affine cipher, the encryption mapping is as follows, x → ax + b(mod n), and decryption, y → a^-1y -a^-1b(mod n) where gcd(a, n) = 1.

y = ax + b(mod n) ⇒ ax = y - b (mod n) ⇒ [gcd(a, n) = 1, so a has an inverse in ℤ_n] x = a^-1(y - b) = a^-1y - a^-1b.

Public Key Cryptography

Diffie–Hellman key exchange is a mathematical method of securely exchanging cryptographic keys over a public and therefore, insecure channel. It was an incredible breakthrough in cryptography that showed that private keys could be securely exchanged in plain sight.

Alice and Bob want to talk or, even better, share a treasure 📦 to each other securely, but they have to assume that a malicious actor, Eve (as in “eavesdropper”) has access to the channel as well. Let’s try to figure out how Alice could send a treasure to Bob.

1. Alice stores the treasure in a locked box for which she only has the key to open it.
2. A courier service delivers 🚚 the box to Bob.
3. Bob places a second lock on the box for which he only has the key to open it, then sends it back to Alice.
4. Alice removes her lock and sends the box back to Bob.
5. Finally, Bob removes the final lock, his lock, and takes the treasure.

Description of the protocol

1. Alice and Bob agree on a natural number n and a generating element g of a finite cyclic group G = ⟨g⟩ where |G| = n. This is done before the rest of the protocol take place and it is assumed to be known by everyone.
2. Alice picks a random natural number a, 1 < a < n. She sends the element g^a to Bob, Alice →g^a→ Bob.
3. Bob picks another random natural number b, 1 < b < n (n should be big enough so a and b are likely different). He sends the element g^b to Alice, Bob →g^b→ Alice.
4. Alice and Bob compute the elements (g^b)^a, (g^a)^b respectively, so Alice and Bob are now both in possession of g^ab which can serve as the shared secret key.

This method is know as the the Diffie-Hellman Key Exchange, but the back-and-forth nature of this exchange can make the process very slow. Besides, what if the courier instead of bringing the box to Bob, the courier himself places a lock on the box, claiming it is Bob's lock, and return it to Alice. She may be fooled, then she removes her lock leaving the courier's lock on the box!!

This is where RSA comes to play. Bob shares with everyone (chests with open locks) his public key. Then, when Alice sends a message or treasure to Bob, it locked the message with Bob's public key or public lock, hence only Bob's private key is capable of unlocking it.

Implementation RSA

1. First, Bob and Alice agree on a natural number n (= p·q), that is, the cycle group ℤ_n, |ℤ_n| = n, m is the plaintext message.
2. Alice must choose a public key “e” and a private key “d” so that m^de≡m (mod n).
3. If Bob wants to send a plaintext message m to Alice securely, then he needs to encrypts m by the formula S ≡ m^e (mod n), and send the ciphertext S to Alice.
4. To decrypt it, Alice computes, S^d ≡ (m^e)^d ≡ m^de ≡ m (mod n), the original plaintext message sent by Bob. Since d is Alice's secret, only Alice can decrypt it.

To create a public and private key for RSA, Alice selects an integer e such that gcd(e, Φ(n)) = 1 (in other words, e ∈ ℤ_Φ(n)*)

Then, using the Euclidean algorithm (gcd(e, Φ(n)) = 1), Alice computer her private key d where de + kΦ(n) = 1 for some k ∈ ℤ ↭ [By construction, n = pq, Φ(n) = lcm(Φ(p), Φ(q)), and since p and q are primes, Φ(n) = lcm(p-1, q-1)] Φ(n) = lcm(p-1, q-1) =[de + kΦ(n) = 1] ed -1 = h(p-1) = k(q-1) for some non-negative integers h and k.

To check (m^e)^d ≡ m (mod pq) for ever integer m (p, q distinct prime numbers), it suffices to check that they are congruent mod p and mod q separately (the case mod q is completely analogous) and then applied the Chinese Remainder Theorem, Let m and n be relatively prime positive integers. For all integers a and b, the pair of congruences x ≡ a (mod m), x ≡ b (mod n) has a solution, and this solution is uniquely determined modulo mn.

Obviously, x = m^ed, we will prove that m^ed ≡ m (mod p), m^ed ≡ m (mod q).

If m ≡ 0 (mod p), m is a multiple of p ⇒ m^ed is a multiple of p ⇒ m^ed ≡ 0 (mod p) and we are done.

m^ed ≡ m^ed-1m ≡ m^h(p-1)m ≡ $(m^{p-1})^hm$ ≡ 1^hm ≡ m (mod p). The most important step is that m^p-1 ≡ 1 (mod p) by Fermat’s little theorem (a^p ≡ a (mod p) or a^p-1 ≡ 1 (mod p))

m^ed ≡ m^ed-1m ≡ m^k(q-1)m ≡ $(m^{q-1})^km$ ≡[Fermat’s little theorem] 1^hm ≡ m (mod q).

Proof using Euler’s theorem

Euler’s totient function counts the positive integers up to a given integer n that are relatively prime to n. Euler’s theorem. If n is a positive integer, and a, n are coprime (gcd(a, n) = 1), then a^Φ(n) ≡ 1 (mod n).

m^de ≡ m^1-kΦ(n) ≡ m(m^Φ(n))^-k ≡[By Euler’s Theorem. If m is not relatively prime to n, this argument is invalid, but improvable. This case can be treated using the previous proof.] m(1)^-k ≡ m (mod n)

Since Eve knows e and n, can she calculate d? That’s relatively easy if she knows Φ(n). The totient function is multiplicative. Φ(1) = 1, and if gcd(a, b) = 1 ⇒ Φ(ab)=Φ(a)Φ(b)), so Φ(n) is easy to compute if one has a prime factorization of n and nearly impossible otherwise.

How do we create a secure Φ(n)? Let’s pick two large primes p and q with 45 digits plus, n = pq ⇒ Φ(n) = Φ(pq) = Φ(p)Φ(q) = [p and q are primes] (p - 1)(q - 1). In other words, knowing the factorization of n as pq, it’s very easy to compute Φ(n), otherwise it is is nearly impossible, Alice needs to keep her primes secret.

Example.

1. Suppose Bob wants to send the message m = 50 to Alice. Select two large prime numbers, e.g., 53 and 59 or 61 and 53.
2. Calculate n = x · y, e.g., 3127 or 3233.
3. Compute the totient function: Φ(n) = (x -1)(y -1), e.g., Φ(n) = 52·58 = 3016 or 3120.
4. Select an integer e that is co-prime to Φ(n) -gcd(e, Φ(n))=1- and 1 < e < Φ(n), e.g, e = 3 or 17.
5. Alice uses the Euclidean algorithm to calculate d such that e·d ≡ 1 mod Φ(n), e.g., e = 3, Φ(n) = 3016, 3016 = 1005·3 + 1 ⇒ 1 = 3016 -(1005)3 ⇒ 1 ≡ -(1005)e (mod 3016) ⇒ d ≡ -1005 ≡ 2011 (mod 3016)
6. Encryption. Bob knows m = 50, n = 3127, and e = 3 ⇒ he would encrypt the message m = 50 by calculating m^e ≡ 50³ ≡ 3047 (mod 3127)
7. Decryption: S^d ≡ 3047²⁰¹¹ ≡ 50 (mod 3127)😀, m = 50.

Bibliography

1. NPTEL-NOC IITM, Introduction to Galois Theory.
2. Algebra, Second Edition, by Michael Artin.
3. LibreTexts, Abstract and Geometric Algebra, Abstract Algebra: Theory and Applications (Judson).
4. Field and Galois Theory, by Patrick Morandi. Springer.
5. Michael Penn (Abstract Algebra), and MathMajor.
6. Contemporary Abstract Algebra, Joseph, A. Gallian.
7. Andrew Misseldine: College Algebra and Abstract Algebra.