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.
Summary of Historical Ciphers & Modular Arithmetic (Symmetric Cryptography)
Table Of Contents
II. Historical Ciphers & Modular Arithmetic.
II.I Substitution Cipher.
Because these ciphers do not operate on bits (and thus do not have keys structured in the form of binary strings with fixed lengths), the relation between keyspace and keybit-length as detailed in Rule 6 does not apply to these ciphers does not apply to these ciphers.
#
C. Rule .
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 of appearance (see the image below), 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 cracking the cipher rather simple.
This is an example of a cipher/algorithm in which an Analytical Attack (see Rule 9) is most effective.
.png)
A generalized distribution of letters in the english language. In substitution ciphers, the frequencies remain the same, with only the letters that represent them changing. Courtesy of Wikimedia.
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 of appearance (see the image below), 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 cracking the cipher rather simple.
This is an example of a cipher/algorithm in which an Analytical Attack (see Rule 9) is most effective.
II.II Modular Arithmetic Basics.
#
C. Rule .
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 operator / 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. As shown in the mathematical definition, any chosen number greater than the modulus is rewritten using the modulus operator (a.k.a. the remainder operator) with respect to the difference between the number and any multiple (see Rule 12) of the modulus, known as the remainder.
The best example for understanding modular arithmetic is something most are already familiar with: time on a clock. On clocks, the highest number is 12, and going any higher just loops back to the beginning. In effect, a clock is a modular arithmetic system using a set of {1, 2, ... 12} with a modulus of 12. 13 hours, for example, would be represented as 1 mod 12, using the modulus operator as specified in the mathematical definition.
The process of finding the modular equivalent of a number (in relation to an already known modulus/set) is simple: divide the chosen number by the modulus, and find the remainder (see Rule 12). The remainder will then be placed as the coefficient in front of the modulus operator. All numbers smaller than the modulus are rendered ordinarily, without the mod operator. For example, the modular representation of 4 in the clock example (mod 12) is just 4.
Using modular representation is a bit jarring at first, as it effectively 'wraps' the chosen number around the modulus, but frequent use (as it is used in practically every cryptosystem) will make it second nature to the beginning cryptographer.
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 operator / 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. As shown in the mathematical definition, any chosen number greater than the modulus is rewritten using the modulus operator (a.k.a. the remainder operator) with respect to the difference between the number and any multiple (see Rule 12) of the modulus, known as the remainder.
The best example for understanding modular arithmetic is something most are already familiar with: time on a clock. On clocks, the highest number is 12, and going any higher just loops back to the beginning. In effect, a clock is a modular arithmetic system using a set of {1, 2, ... 12} with a modulus of 12. 13 hours, for example, would be represented as 1 mod 12, using the modulus operator as specified in the mathematical definition.
The process of finding the modular equivalent of a number (in relation to an already known modulus/set) is simple: divide the chosen number by the modulus, and find the remainder (see Rule 12). The remainder will then be placed as the coefficient in front of the modulus operator. All numbers smaller than the modulus are rendered ordinarily, without the mod operator. For example, the modular representation of 4 in the clock example (mod 12) is just 4.
Using modular representation is a bit jarring at first, as it effectively 'wraps' the chosen number around the modulus, but frequent use (as it is used in practically every cryptosystem) will make it second nature to the beginning cryptographer.
# Cyclic Shift/Cyclical Shift: A fancy term essentially just denoting the usage of modular arithmetic in a particular context, with sets wrapping around once they reach an overflow value and whatnot.
#
C. Rule .
Modular Arithmetic: Computation of the Remainder.
Mathematical Definition:
(a, m) ∈ ℤ
a = (q × m) + r
Thus, a - (q × m) = 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.
Explanation:
To find the remainder in a modular arithmetic system (see Rule 11) when only the chosen number and the modulus (a and m) are known, there is an exact, algorithmic definition. Note that there are two unknown variables in this equation - the quotient and the remainder (q & r). As such, the quotient will have to be determined first in order to find the remainder.
Any integer will work for the quotient (as a result of equivalence classes, which will be discussed later in Rule 13), but the preferred quotient will be the one that produces the preferred multiple (once multiplied with m), which will then produce the smallest positive remainder (known as the preferred remainder).
This is just a complicated way of saying that there is a particular quotient value that, when multiplied by the modulus, will produce a remainder with the chosen value that will allow for the modular representation (the Rule 11 equation with the modulus operator) to be in its most simplified form. The specificities of how this "preferred muliple" (formed by the quotient and the modulus) functions are elaborated upon below.
The preferred multiple of the modulus for finding the remainder is the greatest multiple lower than the chosen number, allowing for the remainder to be as small as possible: 0 ≤ r < m. Thus, the preferred multiple is mathematically the greatest (q × m) lower than a, which means finding the correct q given that m is a constant.
The difference between the preferred multiple and the chosen number is the smallest positive remainder, which is thus the preferred remainder.
For example, with a modulus of 12, 61 would be represented as 1 mod 12, since 61 has a remainder of 1 in relation to 60, the highest multiple of 12 below 61 (meaning that 60 is the preferred multiple). With respect to a clock, this means that 61 hours after 12 A.M. would be either 1 A.M. or 1 P.M., exactly which can be determined by mod 2 of the remainder (0 for A.M.; 1 for P.M.).
As stated before, any quotient/multiple of the modulus will work for the equation (if with a larger remainder) - see Rule 13, Equivalence Classes. The preferred multiple just allows for the most simplified version of a modular representation (see Rule 15), which will be the one used in practical applications of modular arithmetic. This preferred multiple is also the one that would be most easily determined by division, as described in Rule 11.
Mathematical Definition:
(a, m) ∈ ℤ
a = (q × m) + r
Thus, a - (q × m) = 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.
Explanation:
To find the remainder in a modular arithmetic system (see Rule 11) when only the chosen number and the modulus (a and m) are known, there is an exact, algorithmic definition. Note that there are two unknown variables in this equation - the quotient and the remainder (q & r). As such, the quotient will have to be determined first in order to find the remainder.
Any integer will work for the quotient (as a result of equivalence classes, which will be discussed later in Rule 13), but the preferred quotient will be the one that produces the preferred multiple (once multiplied with m), which will then produce the smallest positive remainder (known as the preferred remainder).
This is just a complicated way of saying that there is a particular quotient value that, when multiplied by the modulus, will produce a remainder with the chosen value that will allow for the modular representation (the Rule 11 equation with the modulus operator) to be in its most simplified form. The specificities of how this "preferred muliple" (formed by the quotient and the modulus) functions are elaborated upon below.
The preferred multiple of the modulus for finding the remainder is the greatest multiple lower than the chosen number, allowing for the remainder to be as small as possible: 0 ≤ r < m. Thus, the preferred multiple is mathematically the greatest (q × m) lower than a, which means finding the correct q given that m is a constant.
The difference between the preferred multiple and the chosen number is the smallest positive remainder, which is thus the preferred remainder.
For example, with a modulus of 12, 61 would be represented as 1 mod 12, since 61 has a remainder of 1 in relation to 60, the highest multiple of 12 below 61 (meaning that 60 is the preferred multiple). With respect to a clock, this means that 61 hours after 12 A.M. would be either 1 A.M. or 1 P.M., exactly which can be determined by mod 2 of the remainder (0 for A.M.; 1 for P.M.).
As stated before, any quotient/multiple of the modulus will work for the equation (if with a larger remainder) - see Rule 13, Equivalence Classes. The preferred multiple just allows for the most simplified version of a modular representation (see Rule 15), which will be the one used in practical applications of modular arithmetic. This preferred multiple is also the one that would be most easily determined by division, as described in Rule 11.
#
C. Rule .
Equivalence Classes:
While 12 ≡ 3 mod 9, it is equally true that 12 ≡ 21 mod 9, and that 12 ≡ -6 mod 9. Although these remainders may not be the preferred remainder of 3 (see Rule 12), they all still return true in the Modular Arithmetic formula (see Rule 11):
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 given remainder values can all be simplified down to their smallest possible positive number using the preferred multiple of the modulus, as detailed in Rule 12. Thus, all of these modular representations are inherently equal as they all have the same 'root' preferred remainder. The set of all remainder values that behave 'equivalently' for a particular modulus 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.
While 12 ≡ 3 mod 9, it is equally true that 12 ≡ 21 mod 9, and that 12 ≡ -6 mod 9. Although these remainders may not be the preferred remainder of 3 (see Rule 12), they all still return true in the Modular Arithmetic formula (see Rule 11):
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 given remainder values can all be simplified down to their smallest possible positive number using the preferred multiple of the modulus, as detailed in Rule 12. Thus, all of these modular representations are inherently equal as they all have the same 'root' preferred remainder. The set of all remainder values that behave 'equivalently' for a particular modulus 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 .
Modular Reduction:
Because any value in an equivalence class acts the same with regard to the mod operator of a given modulus, then substitutions can be made in mathematical operations that use the modulus operator, 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 extend equally to all mathematical operations. Exponentials, for example, cannot be simplified with the modulus:
For the problem 3⁸ mod 7, the exponent '8' cannot be simplified down to 1 mod 7. Exponents simply cannot have the substitution performed, while the base can (as shown in the example below).
For all exponentials, simplification into smaller components (using the 2nd Holy Property of Exponents - see 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 (for the exponent itself, not including the base)
Division
Because any value in an equivalence class acts the same with regard to the mod operator of a given modulus, then substitutions can be made in mathematical operations that use the modulus operator, 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 extend equally to all mathematical operations. Exponentials, for example, cannot be simplified with the modulus:
For the problem 3⁸ mod 7, the exponent '8' cannot be simplified down to 1 mod 7. Exponents simply cannot have the substitution performed, while the base can (as shown in the example below).
For all exponentials, simplification into smaller components (using the 2nd Holy Property of Exponents - see 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 (for the exponent itself, not including the base)
Division
#
C. Rule .
When getting a result in modular arithmetic, always simplify down to the smallest positive member of the equivalence class (see Rule 13) for your final answer. Whether for a homework/test answer or for 'in-the-field' cryptography work, it is convention to use the most simplified version of the class.
II.III Integer Rings.
#
C. Rule .
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 such 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.
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 such 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 those pertaining to 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, which always pulls the number back into the set to a value below m.
- 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 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. It is used to define the additive inverse.
- 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.
- There is a multiplicative neutral element, 1: For all elements a ∈ ℤm, it holds that a × 1 ≡ a mod m. It is used to define the multiplicative inverse.
- 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 the Inverse Rules - see Rule 17 & Rule 18.
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).
Addition:
Multiplication:
#
C. Rule .
Multiplicative Inverse Eligibility Test:
To determine if an inverse exists for a specific 'a' of a particular 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 that ring. The inverse of an integer completely depends on the ring, and thus the modulus.
To determine if an inverse exists for a specific 'a' of a particular 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 that ring. The inverse of an integer completely depends on the ring, and thus the modulus.
#
C. Rule .
Application of Multiplicative Inverses:
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 (under part 1 of the ring definition given in Rule 16).
Take a = 5, for example. The supposed inverse '1/5' is incorrect in any context, because it is not included in the set. A different inverse must be found specific to the modulus. For example, if the modulus were 7, then (as the given values pass the multiplicative eligibility test of Rule 17) the true multiplicative inverse can be found:
5 × 5⁻¹ ≡ 1 mod 7
5 × 3 ≡ 1 mod 7
5⁻¹ = 3
As shown above, when used in regards to algebraic rings, the concept of an 'inverse' bears no relation to its common usage in representing reciprocals.
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 (under part 1 of the ring definition given in Rule 16).
Take a = 5, for example. The supposed inverse '1/5' is incorrect in any context, because it is not included in the set. A different inverse must be found specific to the modulus. For example, if the modulus were 7, then (as the given values pass the multiplicative eligibility test of Rule 17) the true multiplicative inverse can be found:
5 × 5⁻¹ ≡ 1 mod 7
5 × 3 ≡ 1 mod 7
5⁻¹ = 3
As shown above, when used in regards to algebraic rings, the concept of an 'inverse' bears no relation to its common usage in representing reciprocals.
#
C. Rule .
Always, as a rule of life, write denominators as (x)⁻¹ (instead of as below a line). With the importance of the inverse operation, it is always critical to recognize all denominators as just being inverses of their values. 1/a = a⁻¹.
II.IV Shift/Caesar Cipher.
#
C. Rule .
Shift Cipher:
Mathematical Definition:
(x, y, k) ∈ ℤ26
Encryption: ek(x) ≡ (x + k) mod 26
Decryption: dk(y) ≡ (y - k) mod 26
x = Plaintext message.
y = Ciphertext.
k = The Key fed into the encryption and decryption functions. Here, it represents the number of times that the characters of the plaintext are shifted rightward, using the alphabet as the set. Variations may use an expanded set, including numbers and special characters.
ℤ26 = A ring of the first 26 integers (including 0), matching the 26 characters of the alphabet. See Subsection II.III for an explanation of rings.
ek(x) = Encryption function, a mathematical formula that converts x into y.
dk(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. Variations may use an expanded set, including numbers or special characters, in which case the '26' would change accordingly.
Explanation:
A simplified form or special case of the Substitution Cipher (Rule 10), 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 (short for "rotate"), 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 (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 (previously explained in relation to Substitution Ciphers - see Rule 10) and brute-force attacks (see Rule 8).
Mathematical Definition:
(x, y, k) ∈ ℤ26
Encryption: ek(x) ≡ (x + k) mod 26
Decryption: dk(y) ≡ (y - k) mod 26
x = Plaintext message.
y = Ciphertext.
k = The Key fed into the encryption and decryption functions. Here, it represents the number of times that the characters of the plaintext are shifted rightward, using the alphabet as the set. Variations may use an expanded set, including numbers and special characters.
ℤ26 = A ring of the first 26 integers (including 0), matching the 26 characters of the alphabet. See Subsection II.III for an explanation of rings.
ek(x) = Encryption function, a mathematical formula that converts x into y.
dk(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. Variations may use an expanded set, including numbers or special characters, in which case the '26' would change accordingly.
Explanation:
A simplified form or special case of the Substitution Cipher (Rule 10), 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 (short for "rotate"), 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 (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 (previously explained in relation to Substitution Ciphers - see Rule 10) and brute-force attacks (see Rule 8).
#
C. Rule .
Vigenère Cipher
Mathematical Definition:
(x, y, k, l) ∈ ℤ26
Encryption: ek(x) ≡ (xi + ki mod l) mod 26
Decryption: dk(y) ≡ (yi - ki 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 referred to by their i position. The key may have less, more, or the same number of characters as the plaintext (see 'l').
i = The position in the string of the plaintext, and regardless of the length of l (as a result of the mod operator), the key.
mod l = 'l' represents the length of the codeword. The mod operator functions such that if there are less characters in the codeword than in the plaintext, then the codeword characters will wrap around so that they can continue being used to produce ciphertext indefinitely.
ℤ26 = A ring of the first 26 integers (including 0), matching the 26 characters of the alphabet. See Subsection II.III for an explanation of rings.
ek(x) = Encryption function, a mathematical formula that converts x into y.
dk(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 codeword 'c', which has 'l' characters. Each character in the code word c represents a number of shifts rightward according to the numerical value. For example, 'a' would represent a rightward shift of zero places, while 'z' would represent a shift of 25 places.
The encryption function works as follows: Each character in the plaintext string 'x' is applied a rightward shift according to its respective letter (identical position) in the key text. This is a cyclic shift (see definition), for if the addition of the key-character value produces a number greater than 26, then the alphabet will wrap around to the beginning. For example, the plaintext character 'z' plus the codeword character 'b' will produce the ciphertext character 'a'. An interesting side-effect of this is that if the keytext is just a string of 'a' ("aaaaaaaa"), then the ciphertext will be identical to the plaintext.
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'.
Because of the way the equation is written, the key does not necessarily need to have the same number of characters as the plaintext. The mod operator on the 'l', the number of characters in the codeword, causes any short codeword to wrap around to account for any longer plaintext strings. For example, for a plaintext of "lingonberry" and a codeword of "sup", the mod operator would cause the codeword to effectively become "supsupsupsu", accounting for each character of the plaintext. Likewise, any codeward longer than the plaintext has any characters beyond the length of the plaintext ignored.
For each value of i within l, the characters of the codeword are mathematically denoted as {c0, c1, ..., cl - 1}, and the keys are similarly represented as {k0, k1, ..., kl - 1}.
Mathematical Definition:
(x, y, k, l) ∈ ℤ26
Encryption: ek(x) ≡ (xi + ki mod l) mod 26
Decryption: dk(y) ≡ (yi - ki 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 referred to by their i position. The key may have less, more, or the same number of characters as the plaintext (see 'l').
i = The position in the string of the plaintext, and regardless of the length of l (as a result of the mod operator), the key.
mod l = 'l' represents the length of the codeword. The mod operator functions such that if there are less characters in the codeword than in the plaintext, then the codeword characters will wrap around so that they can continue being used to produce ciphertext indefinitely.
ℤ26 = A ring of the first 26 integers (including 0), matching the 26 characters of the alphabet. See Subsection II.III for an explanation of rings.
ek(x) = Encryption function, a mathematical formula that converts x into y.
dk(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 codeword 'c', which has 'l' characters. Each character in the code word c represents a number of shifts rightward according to the numerical value. For example, 'a' would represent a rightward shift of zero places, while 'z' would represent a shift of 25 places.
The encryption function works as follows: Each character in the plaintext string 'x' is applied a rightward shift according to its respective letter (identical position) in the key text. This is a cyclic shift (see definition), for if the addition of the key-character value produces a number greater than 26, then the alphabet will wrap around to the beginning. For example, the plaintext character 'z' plus the codeword character 'b' will produce the ciphertext character 'a'. An interesting side-effect of this is that if the keytext is just a string of 'a' ("aaaaaaaa"), then the ciphertext will be identical to the plaintext.
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'.
Because of the way the equation is written, the key does not necessarily need to have the same number of characters as the plaintext. The mod operator on the 'l', the number of characters in the codeword, causes any short codeword to wrap around to account for any longer plaintext strings. For example, for a plaintext of "lingonberry" and a codeword of "sup", the mod operator would cause the codeword to effectively become "supsupsupsu", accounting for each character of the plaintext. Likewise, any codeward longer than the plaintext has any characters beyond the length of the plaintext ignored.
For each value of i within l, the characters of the codeword are mathematically denoted as {c0, c1, ..., cl - 1}, and the keys are similarly represented as {k0, k1, ..., kl - 1}.
II.V Affine Cipher.
#
C. Rule .
Affine Cipher:
Mathematical Definition:
(x, y, a, b) ∈ ℤ26
K = (a, b)
Encryption: ek(x) ≡ ((a × x) + b) mod 26
Decryption: dk(y) ≡ (a⁻¹ × (y - b)) mod 26
x = Plaintext message.
y = Ciphertext.
K = 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, used only in addition and subtraction operations. There are 26 possible values for b, explained below.
ℤ26 = A ring of the first 26 integers (including 0), matching the 26 characters of the alphabet. See Subsection II.III for an explanation of rings.
ek(x) = Encryption function, a mathematical formula that converts x into y.
dk(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. However, it 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, as a result of the inverse in the decryption function, is limited by the condition explicated in the multiplicative inverse eligibility test of Rule 17, with m being 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 (see Rule 8).
Furthermore, letter frequency also remains preserved (since every instance of a particular plaintext character will be converted into the same corresponding ciphertext character, despite the minute differences in the encryption function), so a letter frequency analysis attack is also applicable.
Though multiple encryption (i.e., running the ciphertext produced by encryption function back into the encryption function to encrypt it again) will not increase the security of an affine cipher, it will for other ciphers, such as the Data Encryption Standard (see Rule 46).
Mathematical Definition:
(x, y, a, b) ∈ ℤ26
K = (a, b)
Encryption: ek(x) ≡ ((a × x) + b) mod 26
Decryption: dk(y) ≡ (a⁻¹ × (y - b)) mod 26
x = Plaintext message.
y = Ciphertext.
K = 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, used only in addition and subtraction operations. There are 26 possible values for b, explained below.
ℤ26 = A ring of the first 26 integers (including 0), matching the 26 characters of the alphabet. See Subsection II.III for an explanation of rings.
ek(x) = Encryption function, a mathematical formula that converts x into y.
dk(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. However, it 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, as a result of the inverse in the decryption function, is limited by the condition explicated in the multiplicative inverse eligibility test of Rule 17, with m being 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 (see Rule 8).
Furthermore, letter frequency also remains preserved (since every instance of a particular plaintext character will be converted into the same corresponding ciphertext character, despite the minute differences in the encryption function), so a letter frequency analysis attack is also applicable.
Though multiple encryption (i.e., running the ciphertext produced by encryption function back into the encryption function to encrypt it again) will not increase the security of an affine cipher, it will for other ciphers, such as the Data Encryption Standard (see Rule 46).
#
C. Rule .
Note: You can ALWAYS derive the decryption function from the encryption function 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.
In doing so, always recall that dividing by a variable (as can occur when dividing both sides as a part of the isolation process) makes that variable into its inverse, as foretold in the lesson of Rule 19 and as demonstrated in the mathematical definition of Rule 22.
Know that when doing any algebra with an encryption/decryption equation, the mod operator will simply remain in place on whichever side it was on originally. The mod can be effectively ignored until the end of the isolation process, with it not playing a part in the moving of variables from side to side and whatnot. It will continue to act upon whichever variables are on its side of the equation.
In doing so, always recall that dividing by a variable (as can occur when dividing both sides as a part of the isolation process) makes that variable into its inverse, as foretold in the lesson of Rule 19 and as demonstrated in the mathematical definition of Rule 22.
Know that when doing any algebra with an encryption/decryption equation, the mod operator will simply remain in place on whichever side it was on originally. The mod can be effectively ignored until the end of the isolation process, with it not playing a part in the moving of variables from side to side and whatnot. It will continue to act upon whichever variables are on its side of the equation.
.svg){kind=link}