In learning Cryptography, there will be many equations that one will use repeatedly (and should memorize). This is my attempt to pool every Cryptography equation I come across in my notes/studies. The equations are listed by order of when they appear in the notes, rather than any connection to one another. This page goes beyond simple equation collection to incorporate all mathematical definitions of different systems/algorithms in Cryptography, which tend to reference matematical 'processes', without the use of an equation.
Note that there may be some overlap between this page and other topic equation pages, such as Electrical Engineering. Equations used in mathematics are found here, while those used in electrical engineering are found here.
In the unlikely event there are any egregious errors in this page, contact me at jdlacabe@gmail.com.
List of Cryptography Equations
Table Of Contents
# Symmetric Cryptography
# I.III Cryptanalysis Basics.
# BRUTE-FORCE ATTACK/EXHAUSTIVE KEY SEARCH:
A brute-force attack checks for every ki ∈ K whether dki == x.
If the equality holds, a possible correct key is found; if not, proceed with the next key.
x = The plaintext.
y = The ciphertext.
K = {k1 ,..., kκ }, the key space of all possible keys ki.
dki = The decryption function, being fed a possible key at index i.
# II.II Modular Arithmetic Basics.
# MODULAR ARITHMETIC:
(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.
# MODULAR ARITHMETIC - REMAINDER:
(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 that of the previous modular arithmetic equation; the following mathematical deduction demonstrates how q is irrelevant to the end result - all that matters is the remainder.
# II.III Integer Rings.
# ALGEBRAIC MODULAR ARITHMETIC:
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
Modular Arithmetic can be defined in the form of an integer ring, seen above. Every ring has to fulfill several rules, described 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 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.
- 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 C. 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).
Addition:
Multiplication:
# II.IV Shift/Caesar Cipher.
# SHIFT CIPHER:
(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.
ℤ26 = A ring of the first 26 integers (including 0), matching the 26 characters of the alphabet.
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.
# VIGENÈRE CIPHER:
(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 used by their i position.
i = The position in the string of both the key and the plaintext.
l = The length of the codeword.
ℤ26 = A ring of the first 26 integers (including 0), matching the 26 characters of the alphabet.
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.
# II.V Affine Cipher.
# AFFINE CIPHER:
(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 = (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.
ℤ26 = A ring of the first 26 integers (including 0), matching the 26 characters of the alphabet.
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.
# III.I Introduction to Stream Ciphers.
# STREAM CIPHERS:
(xi, yi, si) ∈ ℤ2
Encryption: esi(xi) ≡ (xi + si) mod 2
Decryption: dsi(yi) ≡ (yi + si) mod 2
xi = The Plaintext bit at index i.
yi = The Ciphertext bit at index i.
si = The "Key Stream" at index i, equivalent to 'k' (as in past ciphers). Here, it is the Key (at index i) fed into the encryption and decryption functions.
ℤ2 = A ring of the first 2 integers: {0, 1}.
esi(xi) = Encryption function, a mathematical formula that converts each x bit into a y bit.
dsi(yi) = Decryption function, a mathematical formula that converts each y bit into an x bit.
mod 2 = The modulus/remainder operator with respect to 2. Numbers can only be 0 or 1 in this reality.
# III.II Random Number Generation.
# PSEUDO RANDOM NUMBER GENERATORS (PRNG):
si+1 = f(si)
s0 = The initial seed value, which may be an actual TRNG.
f(si) = The 'randomizer' function, which performs whatever upon the seed in order to computationally randomize it.
# CRYPTOGRAPHICALLY SECURE PSEUDORANDOM NUMBER GENERATORS (CSPRNG):
Similar to the PRNG, with the added requirement of unpredictability:
Given n output bits (si, si+1, ..., si+(n-1)), it is computationally infeasible to construct si+n.
# LINEAR CONGRUENTIAL GENERATOR (LCG):
(A, B, si) ∈ ℤm
Key K = (A, B)
Si + 1 ≡ ((A × Si) + B) mod m
Si + 1 = The following value in the keystream, which is recursively using the value of the previous bit in the keystream (along with the key) to calculate the new value. It is exactly ⌈log2 m⌉ (bit-length of m) bits long.
S0 = The initial seed value, which may have been created using a TRNG. It is exactly ⌈log2 m⌉ (bit-length of m) bits long.
Si = The Key Stream at index i. It is exactly ⌈log2 m⌉ (bit-length of m) bits long.
ℤm = A ring of m integers.
A = The multiplied value of the key. It is exactly ⌈log2 m⌉ (bit-length of m) bits long.
B = The "shift parameter" value of the key, only used for the addition operation. It is exactly ⌈log2 m⌉ (bit-length of m) bits long.
mod m = The modulus/remainder operator, which represents the usage of modular arithmetic, with all numbers represented by their remainder with respect to m.
# III.III Linear Feedback Shift Registers.
# LINEAR FEEDBACK SHIFT REGISTERS (LFSR):
The equation depends on the specific characteristics of the LFSR. Specifically, the number of flip-flops, the number of mod 2 functions, and which flip-flops have mod 2 functions. The following formula applies to all LFSR's and is fully explained/derived in C. Rule 29:
(Si, Pj) ∈ ℤ2
(i, j) ∈ ℤm
$$S_{m+1} \equiv \left( \sum_{j=0}^{m-1} S_{i+j} \times P_{j} \right) \mod 2$$
m = The number of flip-flops in the LFSR. This number determines both the length of the state register and the period (see C. Rule 31) of the output sequence.
i = The offset in the shift register, e.g., the number bit of the key stream that is being found. This is why it is ∈ ℤm - it can go no greater than value m.
j = The index variable for each individual flip-flop, which have the potential to contribute to the feedback path, as determined by the feedback coefficient.
Sm + 1 = The next output bit into the keystream produced by the LFSR after shifting.
Si + j = The bit held by a particular flip-flop j, at a specific offset in the shift register i. This is the value being inputted into the multiplier function from the flip-flop.
Pj = The feedback coefficient of flip-flop j. Either 0 or 1.
mod 2 = The modulus/remainder operator with respect to 2. Numbers can only be 0 or 1 in this reality.
