Historical Ciphers & Modular Arithmetic (Symmetric Cryptography) Summary

Summary of Historical Ciphers & Modular Arithmetic (Symmetric Cryptography)

These are my complete notes for Historical Ciphers & Modular Arithmetic in Symmetric Cryptography.

I color-coded my notes according to their meaning - for a complete reference for each type of note, see here (also available in the sidebar). All of the knowledge present in these notes has been filtered through my personal explanations for them, the result of my attempts to understand and study them from my classes and online courses. In the unlikely event there are any egregious errors, contact me at jdlacabe@gmail.com.

Table Of Contents

II.I Substitution Cipher.

II.IV Shift/Caesar Cipher.

II.II Modular Arithmetic Basics.

II.V Affine Cipher.

II.III Integer Rings.

II. Historical Ciphers & Modular Arithmetic.

II.I Substitution Cipher.

# Historical Cipher: A cipher that was used before the development of modern cryptography, operating on letters instead of bits/bytes. Every one of these ciphers are easily crackable, from the Enigma Code to the Caesar Cipher.

# C. Rule 7. Substitution Cipher

A historical cipher, operating purely on letters, in which every plaintext letter is replaced by a fixed ciphertext letter. It is just scrambling the letters, nothing more.

The Keyspace is 26!, or 2^88, as each plaintext letter that maps to a ciphertext letter decreases the remaining number of possible letters. Thus, a brute-force attack would be out of the question for modern computers.

Since the different letters of the English alphabet have different frequencies, and these frequencies are preserved even after scrambling (just different letters will have the frequencies), Letter Frequency Analysis can be conducted as an attack on the substitution cipher, making it rather simple.

This is an example of a cipher/algorithm in which an Analytical Attack is most effective.

II.II Modular Arithmetic Basics.

# C. Rule 8. Modular Arithmetic:

Mathematical Definition:

(a, r, m) ∈ ℤ
m > 0

If m|(a − r), then a ≡ r mod m

ℤ = The set of all integers.
a = The chosen number.
r = The remainder.
m = The modulus, the highest possible number in the set.
'mod m' = The modulus/remainder operator, which represents the usage of modular arithmetic, with all numbers represented by their remainder with respect to m.

Explanation:

Since the bulk of cryptographic computations are performed in finite sets, special mathematical tools are needed. In particular, Modular Arithmetic is the basis for all modern cryptosystems, and many historical ones as well.

Modular arithmetic is a system of simplifying a number in terms of a given modulus, the highest number in a set. Any number greater than the modulus is rewritten using the modulus operator (or remainder operator, see below), in effect 'wrapping' the number around the modulus, with respect to the difference between the number and any multiple of the modulus, known as the remainder.

The preferred multiple for finding the remainder (indeed, the exact one that would be found by division (see two paragraphs below)) is the greatest one lower than the number, but any will work - see Rule 10, Equivalence Classes.

For example, with a modulus of 12, 61 would be represented as 1 mod 12.

The process of finding the modular equivalent of a number is simple: divide the chosen number by the modulus, and find the remainder. The remainder will then be the coefficient in front of the modulus operator. All numbers smaller than the modulus are rendered ordinarily, without the mod operator.

# C. Rule 9. Modular Arithmetic: Computation of the Remainder.

To find the remainder when m and a are large, burdensome numbers, there is an exact, algorithmic definition:

Mathematical Definition:

(a, m) ∈ ℤ
0 ≤ r < m

a = q × m + r
Thus, a - r = q × m

m|(a − r)

ℤ = The set of all integers.
a = The chosen number.
q = The quotient, which produces a multiple of the modulus.
r = The remainder.
m = The modulus, the highest possible number in the set.

The final equation is precisely the same as what was discovered before, and q is not involved whatsoever - all that matters is the remainder.

# C. Rule 10. Equivalence Classes:

While 12 ≡ 3 mod 9, it is equally true that 12 ≡ 21 mod 9, and that 12 ≡ -6 mod 9. This is because, while the remainders may not exactly be the difference between 'a' (12) and the highest multiple of m lesser than a (9), they all still return true in the formula of Rule 8:

12 ≡ 3 mod 9, 3 is a valid remainder since 9|(12−3)
12 ≡ 21 mod 9, 21 is a valid remainder since 9|(12−21)
12 ≡ −6 mod 9, −6 is a valid remainder since 9|(12−(−6))

The set of all values that behave 'equivalently' for a particular modulus, in that they can be simplified down to the smallest possible positive number for r, form what is known as an Equivalence Class, an infinite set/series of values.

For 3 mod 9, the equivalence class of r values is an infinite set, a partial series of which is as follows:
{..., -24, -15, -6, 3, 12, 21, 30, ...}

If any of these values were to be substituted in for r (3) in 3 mod 9, it would be equivalent, the same value, because of the mod operator.

Note: There are 'm' equivalence classes for each possible remainder (0 through m-1), which collectively contain all possible integers. The difference between any two neighboring values in an equivalence class will be the modulus, as shown above.

# C. Rule 11. Modular Reduction:

Because any value in an equivalence class acts the same with regard to the mod operator of a given modulus, then substitutions in mathematical operations that use the modulus operator can be performed, simplifying them.

Take (13 × 16) - 8, with modulus 5. While the full number can be computed (200) and an answer derived from there (0 mod 5), that is lame and time-consuming. A much cooler, faster, 21st century means of solving the problem is to substitute in for each term the simplest member of their respective equivalence classes:

13 mod 5 has a remainder of 3, and so 3 is the simplest term.
16 mod 5 has a remainder of 1, and so 1 is the simplest term.
8 mod 5 has a remainder of 3, and so 3 is the simplest term.

Therefore, the same calculation can be performed with simply (3 × 1) - 3, which returns 0 mod 5, the same answer as before, but found much easier-ly.

Note that this substitution trick does not equally extend to all mathematical operations. Exponentials, for example, cannot be simplified with the modulus:

For the problem 3⁸ mod 7, the exponent '8' cannot be simplfied down to 1 mod 7, and the entire problem to 3 mod 7. Exponents simply cannot have the substitution performed.

For all exponentials, simplification into smaller components (using the 2nd Holy Property of Exponents, Math Rule 66 ([[[[[)) must be performed to simplify. For ex.: 3⁸ = (3²)⁴ = (9)⁴ = (2)⁴ = 16 mod 7 = 2 mod 7, which is the answer.

Operations where equivalence class substitutions are allowed:

Multiplication
Addition
Substraction

Operations where equivalence class substitutions are banned:

Exponentials
Division

# C. Rule 12. When getting a result in modular arithmetic, always simplify down to the smallest positive member of the equivalence class for your final answer.

II.III Integer Rings.

# Integer Ring: A set of elements which can have basic arithmetic operations performed upon them, such as addition and multiplication, so that the natural properties expected of addition and multiplication all hold. There are ring definitions/interpretations of polynomials, matrixes, and modular arithmetic (Rule 13). Rings are a fundamental part of Ring Theory, a field of Abstract algebra. ([[[[[[)

# C. Rule 13. Algebraic Modular Arithmetic:

Modular Arithmetic can be defined in the form of an integer ring:

The integer ring ℤ_m consists of the following characteristics:

1. The set ℤ_m = {0, 1, ..., m-1}

2. Two arithmetic operators, "+" and "×", hold for all (a, b, c, d) ∈ ℤ_m that:
i) a + b ≡ c mod m
ii) a × b ≡ d mod m

There are many overshadowing rules that every ring has to fulfill, seen in the section "RULES OF THE RING" below.

# RULES OF THE RING:

These following rules hold true for all integer rings in general, not just modular arithmetic.

The ring should be closed: if any two numbers from the set are multiplied or added together, the result must be in the ring. This is ensured by the modulus operator.

Addition and multiplication are associative properties: For all (a, b, c) ∈ ℤ_m, a + (b + c) = (a + b) + c, and a × (b × c) = (a × b) × c.

Addition:

Addition is commutative for all (a, b) ∈ ℤ_m: a + b = b + a.

There is an additive neutral element, 0. For all elements a ∈ ℤ_m, it holds that a + 0 ≡ a mod m.

The additive inverse always exists: for any element a in the ring, there is always a negative element '-a' such that a + (-a) ≡ 0 mod m, the neutral element.

Multiplication

There is a multiplicative neutral element, 1: For all elements a ∈ ℤ_m, it holds that a × 1 ≡ a mod m.

The Multiplicative Inverse exists only for some elements: For a ∈ ℤ, the inverse a⁻¹ is defined such that a × a⁻¹ ≡ 1 mod m. The nature of most inverses and the reasons for their occasional nonexistence are outlined in Rules 14 & 15.

If there exists an inverse for a, then, a rare usage of division in the modular ring becomes possible: the element a⁻¹ can be divided by, as a divisor, since b/a ≡ b × a⁻¹ mod m.

The distributive property holds for all ring operations. For all (a, b, c) ∈ ℤ_m, a × (b + c) = (a × b) + (a × c).

# C. Rule 14. To determine if an inverse exists for a specific 'a' of a specific modulus, simply find the gcd (Greatest Common Divisor) of the two values:

If gcd(a, m) = 1, then there exists a⁻¹, and a & m are said to be "relatively prime", or "coprime".

If gcd(a, m) ≠ 1, then there does NOT exist a⁻¹.

If m is prime, then gcd(a, m) will always equal to 1, for all nonzero 'a' values, and thus every 'a' value will have an inverse in those rings. The inverse of an integer completely depends on the ring, and thus the modulus.

# C. Rule 15. Finding the Multiplicative Inverse of a has the following formula (as described in Rule of the Ring #7):

a × a⁻¹ ≡ 1 mod m

Though the multiplicative inverse of a is literally shown as a⁻¹, it is almost never the actual reciprocal of a. The reason for this is simple: All reciprocals other than -1 and 1 are not integers, and are thus not included in the set.

Take a = 2, for example. The supposed inverse '1/2' is incorrect, because it is not included in the set. A different inverse must be found specific to the modulus; if the modulus were 3, then an inverse of '2' would work:

2 × 2 ≡ 1 mod 3

II.IV Shift/Caesar Cipher.

# C. Rule 16. Shift Cipher:

Mathematical Definition:

(x, y, k) ∈ ℤ₂₆

Encryption: e_k(x) ≡ (x + k) mod 26

Decryption: d_k(y) ≡ (y - k) mod 26

x = Plaintext message.
y = Ciphertext.
k = The Key fed into the encryption and decryption functions.
ℤ₂₆ = A ring of the first 26 integers (including 0), matching the 26 characters of the alphabet.
e_k(x) = Encryption function, a mathematical formula that converts x into y.
d_k(y) = Decryption function, a mathematical formula that converts y into x.
mod 26 = The modulus/remainder operator, which represents the usage of modular arithmetic, with all numbers represented by their remainder with respect to 26.

Explanation:

A simplified form or special case of the Substitution cipher, the Shift Cipher (or Caesar Cipher) merely shifts every plaintext letter however many so positions rightward in the alphabet, wrapping around when it reaches the end (modular arithmetic!). This is occasionally known as the "ROT" Cipher, and the most well-known example is ROT13, which shifts rightward precisely halfway through the alphabet.

As a generic example, with a key of 1, some shifts would be as follows:

a -> b
b -> c
...
z -> a

As shown, once the alphabet reaches letter (26 - k) + 1, or the position in the ring ℤ₂₆ (26 - k) (since the set begins at 0), the shift returns to the front of the alphabet.

It should be obvious to all this is an extremely unsecure cryptosystem, with a keyspace of only 26. It is vulnerable to both letter frequency analysis (explained in Rule 7) and brute-force attacks (Rule 5).

# C. Rule 17. Vigenère Cipher

Mathematical Definition:

(x, y, k, l) ∈ ℤ₂₆

Encryption: e_k(x) ≡ (x_i + k_{i mod l}) mod 26

Decryption: d_k(y) ≡ (y_i - k_{i mod l}) mod 26

x = Plaintext message.
y = Ciphertext.
k = The Key/codeword fed into the encryption and decryption functions, which, like the plaintext, is a series of letters (represented by their numerical value, 0-25) that are used by their i position.
i = The position in the string of both the key and the plaintext.
l = The length of the codeword.
ℤ₂₆ = A ring of the first 26 integers (including 0), matching the 26 characters of the alphabet.
e_k(x) = Encryption function, a mathematical formula that converts x into y.
d_k(y) = Decryption function, a mathematical formula that converts y into x.
mod 26 = The modulus/remainder operator, which represents the usage of modular arithmetic, with all numbers represented by their remainder with respect to 26.

Explanation:

A mere variation of the Shift cipher, in which the shift for each letter is determined by a secret code word 'c', which has 'l' letters. Each character in the code word c represents a number of shifts rightward according to its cipher.

The letters of the code word are denoted as (c₀, c₁, ..., c_{l - 1}), and as the keys, they are also represented as (k₀, k₁, ..., k_{l - 1}), respectively.

The encryption function works as follows: Each character in the plaintext string 'x' is applied a rightward shift according to it's respective letter (identical position) in the key text (a cyclic shift, if the addition of the key letter produces a number greater than 26).

This dictates that the length of the code word must be the same or larger than that of the actual code itself, which is somewhat inefficient for longer plaintexts. E.g., |x| ≤ l.

The decryption function, of course, is just the opposite of the encryption function, moving each character of the ciphertext backward by the value in the positional counterpart of the code word 'c'.

II.V Affine Cipher.

# C. Rule 18. Affine Cipher:

Mathematical Definition:

(x, y, a, b) ∈ ℤ₂₆
K = (a, b)

Encryption: e_k(x) ≡ ((a × x) + b) mod 26

Decryption: d_k(y) ≡ (a⁻¹ × (y - b)) mod 26

x = Plaintext message.
y = Ciphertext.
K = (symbol not depicted) The key, which has been split into two parts: a and b.
a = The multiplied value of the key. The number of possible 'a' values is limited by the necessity of the inverse (for the decryption function), as explained below.
a⁻¹ = The inverse of a, necessary for the decryption function.
b = The "shift parameter" value of the key, only in addition and subtraction operations. There are 26 possible values for b, explained below.
ℤ₂₆ = A ring of the first 26 integers (including 0), matching the 26 characters of the alphabet.
e_k(x) = Encryption function, a mathematical formula that converts x into y.
d_k(y) = Decryption function, a mathematical formula that converts y into x.
mod 26 = The modulus/remainder operator, which represents the usage of modular arithmetic, with all numbers represented by their remainder with respect to 26.

Explanation:

The Affine Cipher is an attempted improvement of the shift cipher, done by complicating the encryption function through the addition of multiple parameters, but is still extremely easy to break. The affine cipher is performed by splitting the key into two parts:

K = (a, b)

The number of possible b values in the system is 26, as it is merely the shift parameter (as shown in the definition equations).

The number of possible a values is limited by the condition explicated in Rule 14, with m = 26: only when gcd(a, 26) = 1 is 'a' an inverse, and thus contributive to the number of possible values. Counting all possible values of a (1, 3, 5, 7, 9, ...), all odd numbers 1-26 other than 13, produces an end result of 12 possible 'a' values.

The keyspace, being (#a) × (#b), is therefore 312. This remains very easy to break using a brute-force attack (Rule 5).

Furthermore, letter frequency also remains preserved (since any of a particular character (plaintext) will always be converted to another specific character (ciphertext), despite the minute differences in the encryption function), so a letter frequency analysis attack is also applicable.

Though multiple encryption will not increase the security of an affine cipher, it will for other ciphers, such as the Data Encryption Standard (see Rule 43).

# C. Rule 19. Always, as a rule of life, write denominators as (x)⁻¹ instead of as below a line. With the importance of the inverse operation, it always critical to recognize all divisors as being inverses of their variable. 1/a = a⁻¹.

# C. Rule 20. Note: You can ALWAYS derive the decryption function from the encryption function in mathematical definitions of basic ciphers/algorithms. Just know that the encryption function is equal to y and the decryption function is equal to x, and you can simply isolate the appropriate variable to find whichever function you wish.

Also recall that the mod operator will simply remain in place - it can be practically ignored until the end of the isolation, with it not playing a part in moving variables from side to side and whatnot.