Simple substitution ciphers

Simple substitution ciphers are a foundational cryptographic method where each letter in the plaintext is replaced by a letter from a shuffled alphabet. This method is straightforward yet introduces the basic concept of encrypting a message to make it unreadable to unintended recipients.

How It Works

• The cipher operates by creating a one-to-one mapping between the standard alphabet and a mixed alphabet. Each letter from the plaintext is substituted according to this mapping to produce the ciphertext.

• For instance, if the letter 'A' maps to 'L', 'B' to 'M', and so on, the word "HELLO" might be encrypted as "XYZZY" given a specific mapping.

Historical Context: The Caesar Cipher

• Caesar cipher is an early form of simple substitution cipher. In a Caesar cipher, the alphabet is shifted a fixed number of places. For example, with a shift of three, 'A' becomes 'D', 'B' becomes 'E', and so forth.

• This cipher is named after Julius Caesar, who is historically noted to have used it for confidential communications.

Vulnerabilities: Frequency Analysis

• A significant part of the discussion on simple substitution ciphers involves their vulnerability to frequency analysis. This method of cryptanalysis leverages the fact that certain letters and combinations of letters appear more frequently than others in a given language.

• For example, in English, 'E' is the most common letter, and pairs like 'TH' are common bigram. By analyzing the frequency of letters and letter pairs in the ciphertext, a cryptanalyst can begin to deduce the original mappings and decrypt the message.

Despite their vulnerability, simple substitution ciphers played a crucial role in the early development of cryptographic methods. They introduced the principle of altering plaintext to secure its contents, laying the groundwork for more complex and secure ciphers. The ease with which these ciphers can be broken underscores the need for advancements in cryptographic techniques, leading to the development of more sophisticated encryption algorithms.

Divisibility

At its core, the concept of divisibility is straightforward yet powerful. An integer b is said to divide another integeraif there exists an integer c such that a = bc.

Ex: We have 847 | 485331, since 485331 = 847 · 573. On the other hand, 355 !/ 259943, since when we try to divide 259943 by 355, we get a remainder of 83. More precisely, 259943 = 355 · 732 + 83, so 259943 is not an exact multiple of 355.

This simple relationship forms the backbone of much more complex mathematical structures encountered in cryptography.

Greatest Common Divisor (GCD)

The greatest common divisor of a and b is, as its name suggests, the largest positive integerdsuch thatd | aandd | b. The greatest common divisor of a and b is denoted gcd(a, b). If there is no possibility of confusion, it is also sometimes denoted by (a, b). If a and b are both 0, then gcd(a, b) is NOT DEFINED.

Ex: Calculation of gcd (748, 2024)

Not Efficient Approach: Making lists of all the positive divisors of 748 and of 2024.

Divisors of 748 = {1, 2, 4, 11, 17, 22, 34, 44, 68, 187, 374, 748},

Divisors of 2024 = {1, 2, 4, 8, 11, 22, 23, 44, 46, 88, 92, 184, 253, 506, 1012, 2024}.

Efficient Approach: Division with remainder, which is simply the method of “long division”. Thus, if a and b are positive integers and if you attempt to divide a by b, you will get a quotient q and a remainder r, where the remainder r is smaller than b.

Finding GCD with Division

1. According to the definition, we can say a = bq + r and 0 ≤ r < b. The values q and r are unique for given a and b.

2. Start by dividing a by b to get the remainder r. Any common divisor of a and b is also a divisor of r, and any common divisor of b and r is a divisor of a. This means the GCD of a and b can be equated to the GCD of b and r. So;

   gcd(a, b) = gcd(b, r)

3. Repeat the process, dividing b by r to get another quotient and remainder, reducing the remainder each time until r = 0. The final value gcd(s, 0) = s is equal to the gcd(a, b).

We illustrate with an example and then describe the general method, which goes by the name Euclidean algorithm.

2024 = 748 · 2 + 528

748 = 528 · 1 + 220

528 = 220 · 2 + 88

220 = 88 · 2 + 44 ⇾ gcd(2024, 748) = 44

88 = 44 · 2 + 0

The Euclidean Algorithm

Let a and b be positive integers with a ≥ b. The following algorithm computes gcd(a, b) in a finite number of steps.

The Discrete Logarithm Problem

The DLP arises in the context of finite fields, particularly Fp​, which is a field with a prime number of elements p. For a given prime p and a primitive element g in Fp​, the DLP involves finding an exponent x such that:

g ^ x ≡ h ( mod p )

Here, g is a primitive root for Fp​, and h is a nonzero element of Fp​. The exponent x that satisfies this equation is known as the discrete logarithm of h the base g, denoted by;

Mathematical Representation

• Primitive Element g: A primitive element g of Fp​ is such that every nonzero element of Fp​ can be expressed as a power of g. By Fermat's little theorem;

and no smaller power of g equals 1.

• Discrete Logarithm x: The discrete logarithm problem seeks the integer x satisfying;

• If such an x exists, there are actually infinitely many solutions, since;

for any integer k, due to the periodic nature implied by Fermat’s little theorem.

The discrete logarithm x is thus defined modulo p−1, acknowledging the cyclic nature of the powers of g in Fp​.

Diffie-Hellman Key Exchange

Alice and Bob need to securely share a secret key over an insecure channel monitored by Eve. Diffie and Hellman proposed using the discrete logarithm problem's complexity as a possible solution to this challenge.

Mathematical Representation of the Algorithm

1. Public Parameter Creation

Alice and Bob start by choosing a large prime number p and a nonzero integer g modulo p and share them in public.

2. Private Computations

Next, Alice selects a secret integer a, and Bob chooses a secret integer b. They use their secret integers to compute:

3. Public Exchange of Values

Alice sends to Bob ⇾ A,

Bob sends to Alice ⇾ B

4. Further Private Computations

Bob and Alice again use their secret integers to compute:

The values that they compute are the same. (A′ = B′)

Current guidelines suggest that Alice and Bob choose a prime p having approximately 1000 bits (i.e., p ≈ 21000) and an element g whose order is prime and approximately p/2. Then Eve will face a truly difficult task. However, Eve can solve the DLP (Discrete Logarithm Problem), then she can compute Alice and Bob’s secret exponents a and b from the intercepted values A and B, and then it is easy for her to compute their shared key gab. (Needs to compute only one of a and b.) But the converse is less clear. Suppose that Eve has an algorithm that efficiently solves the DHP (Diffie-Hellman Problem). Can she use it to also efficiently solve the DLP?

The ElGamal Public Key Cryptosystem

Although Diffie-Hellman algorithm provides a method of publicly sharing a secret random key, it does not enough to being a public key cryptosystem. The most natural development of a public key cryptosystem following the Diffie–Hellman is a system described by Taher ElGamal in 1985. The ElGamal public key encryption algorithm is based on the DLP and is closely related to Diffie–Hellman key exchange.

Mathematical Representation

1. Public Parameter Creation

A trusted party chooses and publishes a large prime p and an element g (instead of Alice and Bob) modulo p of large (prime) order.

2. Key Creation

2.1 Alice chose private key 1 =< a =< p-1.

2.2 Computes A = g ^ a (mod p).

2.3 Alice publishes the public key A.

3. Encryption

3.1 Bob chooses plaintext m.

3.2 Bob chooses random temporary key k.

3.3 Uses Alice's public key A to compute c1 = g ^ k (mod p)

and c2 = m A^k (mod p).

3.4 Bob sends ciphertext (c1, c2) to Alice.

4. Decryption

Alice compute m with:

References

An Introduction to Mathematical Cryptography

The Euclidean Algorithm