Foundation of Cryptography

Notes on Foundation of Cryptography given by HITSZ in 2024 Fall (R6 Fall).
This page is a replica of the book Foundation of Cryptography (Zeroth Edition)- Yanagi Chiaki
This page will be complete in 2025-01 as planned.

Preface

Cryptography is the backbone of secure communication, standing as a guard over the vast sea of information that flows through digital networks. This book, Foundation of Cryptography, represents a journey through cryptographic principles and practices, from ancient ciphers to modern encryption standards, written for educational purpose.

In the early chapters, I set out to cover the traditional ciphers that laid the foundation of cryptographic thought. These include methods like the Caesar and Vigenère ciphers, through which we can see the evolution from simple substitution techniques to more intricate, polyalphabetic systems. This historical perspective offers a window into the ingenuity that humans have applied to secure their messages, long before the era of electronic computation.

As we advance, we delve into the mathematics underpinning modern cryptographic systems. These sections cover essential concepts, from group and field theory to the properties of modular arithmetic, laying the groundwork for understanding block ciphers like DES and AES. Block ciphers epitomize the classical idea of secure communication in the digital age. By exploring both the design and structural strengths of these ciphers, we gain an appreciation for the balance of speed and security that they provide.

The book further explores advanced topics, such as stream ciphers, which offer efficiency in resource-limited environments, and public-key cryptography, which enables secure communication between parties who have never met. By studying algorithms like RSA and Elliptic Curve Cryptography (ECC), readers will grasp how public-key systems use mathematical complexity to protect data, even in open networks. In addition to explaining the algorithms themselves, I have highlighted the pivotal role that number theory plays in ensuring that these systems are both secure and efficient.

In later chapters, I address the importance of cryptographic protocols and standards that enable a range of secure interactions, including hashing, digital signatures, and secure multi-party computation. These tools extend the applications of cryptography beyond confidentiality, enabling data integrity, authentication, and non-repudiation. By covering topics like HMAC and digital signatures with RSA and DSA, this book illustrates how cryptography safeguards not just messages but also the identities of the people who send them.

Security, as this book emphasizes, is not a static property. Cryptographic algorithms and protocols must be continually reassessed as computational power grows and new attack methods emerge. I discuss cryptanalysis techniques to shed light on the vulnerabilities that cryptographers strive to eliminate. This approach is complemented by insights into contemporary issues, such as zero-knowledge proofs, homomorphic encryption, and threshold cryptography—topics that reveal the cutting-edge of the field.

Throughout this work, my goal has been to make cryptography accessible while honoring its complexity. Each chapter is structured to guide readers from basic principles to more sophisticated concepts, with some examples that reinforce understanding and encourage independent exploration. I hope the student readers just like me will find both practical value and intellectual inspiration within these pages.

Cryptography, in essence, is a field of trust, a pursuit of mathematical rigor to enable secure, open communication in an increasingly interconnected world. May this book inspire the next generation of cryptographers to carry on this mission.

Contents

Left out. You can access it on the left of this page.

Part I Cryptography Starts Here

Wise encryption methods love to go back here.

Chapter 1 Introduction to Cryptography

Chapter 2 Traditional Cipher

Permutation Cipher

The password alphabet keeps unchanged. Generally, there is a defined permutation $\sigma$ on the alphabet set.

Given a plaintext, let us say,
$$this is the largest stone in the quarry$$
We fill it into a matrix. Padding may be needed to fill each item in the matrix. (& is the padding mark in the example below)
$$\begin{bmatrix} t&h&i&s&i&s\\t&h&e&l&a&r\\g&e&s&t&s&t\\o&n&e&i&n&t\\h&e&q&u&a&r\\r&y&\&&\&&\&&\&\\\end{bmatrix}$$
Then we define a permutation $\sigma = (145)(36)$ and perform it on the matrix,
$$\begin{bmatrix} t&h&i&s&i&s\\t&h&e&l&a&r\\g&e&s&t&s&t\\o&n&e&i&n&t\\h&e&q&u&a&r\\r&y&\&&\&&\&&\&\\\end{bmatrix}\xrightarrow[]{\sigma}\begin{bmatrix} i&h&s&t&s&i\\a&h&r&t&l&e\\s&e&t&g&t&s\\n&n&t&o&i&e\\a&e&r&h&u&q\\\&&y&\&&r&\&&\&\\\end{bmatrix}$$
Finally the ciphertext should be
$$ihstsiahrtlesetgtsnntoieaerhuqyr$$
To decrypt a ciphertext, $\sigma^{-1}=(154)(36)$ should be used for mapping the cipher matrix to the plain matrix.

Substitution Cipher

The alphabet is changed through a substitution $s:\Sigma\rightarrow\Gamma$,

Monoalphabetic Substitution Cipher
For a letter in $\Sigma$, it will always be substituted to a special string in $\Gamma$. We then call it Monoalphabetic Substitution Cipher.

Caesar Cipher and Affine Cipher are Monoalphabetic Substitution Ciphers.

Caesar Cipher
Caesar Cipher is a type of substitution cipher in which each letter in the plaintext is replaced by a letter some fixed number of positions down the alphabet.
If this fixed number is 23, we will have the following encryption table.

Plain	$ABCDEFGIJKLMNOPQRSTUVWXYZ$
Cipher	$XYZABCDEFGIJKLMNOPQRSTUVW$

If the plaintext is $$THE~QUICK~BROWN~FOX~JUMPS~OVER~THE~LAZY~DOG$$
Then the ciphertext will be $$QEB~NRFZH~YOLTK~CLU~GRJMP~LSBO~QEB~IXWV~ALD$$ and vice versa.

To sum up, for a letter $x$, the encryption function is $E(x)= (x+n) \mod 26$, the decryption function is $D(x)= (x-n) \mod 26$.

Affine Cipher
Each letter is enciphered with the function $(ax + b) \mod m$, where b is the magnitude of the shift.
Generally, $(a,m)=1$. This property keeps that the inverse of $a$ exists, where $1=a^{-1}\mod m$.
To sum up, for a letter $x$, the encryption function is $E(x)= (ax+b) \mod m$, the decryption function is $D(x)= a^{-1}(x-b) \mod m$.

Polyalphabetic Substitution Cipher
For a letter in $\Sigma$, it will be substituted to a string in $\Gamma$, but may not always the same. We then call it Polyalphabetic Substitution Cipher.

Vigenère Cipher and Hill Cipher are Polyalphabetic Substitution Ciphers.

Vigenère Cipher
Vigenère Cipher is a type of substitution cipher where each letter of the plaintext is encoded with a different Caesar Cipher, whose increment is determined by the corresponding letter of another text, called the key.
If the plaintext is $$THE~QUICK~BROWN~FOX~JUMPS~OVER~THE~LAZY~DOG$$ and the key is $LION$.
Here, we should extend the key to $LIONLIONLION…$ until it is enough to encrypt the whole plaintext.
Then the ciphertext will be $$EPS~DFQQX~MZCJY~NCK~UCACD~WJRC~BVR~WINL~OWU$$
To sum up, for a letter $x$, the encryption function is $E_K(x_i)= (x_i+k_i) \mod 26$, the decryption function is $D_K(x_i)= (x_i-k_i) \mod 26$.

Hill Cipher
The key of Hill Cipher is a matrix.
$\textbf{c} = \textbf{p} \times \textbf{K}\mod 26$, where the dimension of $\textbf{c}$ , $\textbf{p}$ is $1\times n$. $\textbf{K}$ is an $n\times n$ key matrix where $(|\textbf{K}|, 26) = 1$.
Conversely, $\textbf{p}=\textbf{c}\times \textbf{K}^{-1}\mod 26$.
Here, let $\textbf{p}=\begin{bmatrix} C&Y&B&E&R \end{bmatrix}=\begin{bmatrix} 2&24&1&4&17 \end{bmatrix}$.
Then let $$\textbf{K}=\begin{bmatrix} 10 & 5 & 12 & & \\ 3 & 14& 21 & & \\8 & 9 & 11 & & \\&&&11&8\\&&&3&7\end{bmatrix}$$
We will have $\textbf{c} = \textbf{p} \times \textbf{K}\mod 26 = \begin{bmatrix} 22&17&19&17&21 \end{bmatrix}=\begin{bmatrix} W&R&T&R&V \end{bmatrix}$

Enigma Cipher

An Enigma Cipher $E$ is performed on an Enigma machine, which is consisted of a plugboard $P$ with at most 13 pairs of wire to perform letter swap(e.g. connect) $p$ and $g$, then $p$ will be regarded as $g$ when hitting the keyboard and $g$ will be regarded as $p$ when the lamp displays, 3 rotatable alphabet wheels from left to right $L,M,R$ and a reflector $U$.

Due to the algebra expression is complicated, the work process will be shown in examples.

A typical encryption process is as following.
0. Pre-defined Enigma settings are known.(How to set $P,L,M,R$)
1. Define a communication code, let it be $psv$.
2. Use the Enigma machine with the pre-defined state, input the communication code 2 times.
You get $atcdvt$.
3. Reset Enigma machine, keep the plugboard $P$ unchanged, but set $L,M,R$ to $p,s,v$
4. Then input the message, let it be $nacht$.
You get $kxnwp$.
5. At last, $atcdvtkxnwp$ will be sent out.

A typical decryption process is as following.
0. Pre-defined Enigma settings are known.(How to set $P,L,M,R$ )
1. To find the communication code, input the sequence (6 letters) until a certain string repetition is found.
You get $psvpsv$.
2. Reset Enigma machine, keep the plugboard $P$ unchanged, but set $L,M,R$ to $p,s,v$
3. Then input the remaining part, $kxnwp$.
You get $nacht$.

Properties of some Traditional Cipher

Monoalphabetic Substitution Cipher is easy to be cracked through letter frequency analysis. For example, in English, e has the highest frequency 12.7%. If the ciphertext is a common text, then we can guess the letter with the highest frequency is very possible to be the letter e in plaintext. 2-letter group, 3-letter group also have their frequency ranking.
Generally, the longer the ciphertext is, the better this method will perform.

Polyalphabetic Substitution Cipher can be tried to crack using index of coincidence.
For a plaintext without lexical meaning, the possibility of a certain letter’s appearance is $\frac{1}{26}$. If we select 2 English sentences, the probability that the letters on the same position (e.g. the 5-th letter) are the same is about $0.065$. Different from two random sentences, which probability is also $\frac{1}{26}$.

For a language $L$, there are $n$ letters in the alphabet, then we define `index of coincidence’ $IC=\sum\limits_{i=1}^{n}p_i^2$.

Due to the text in real world are finite. We use unbiased estimated $IC_u=\sum\limits_{i=1}^n\frac{x_i(x_i-1)}{L(L-1)}$, $x_i$ shows how many times the letter labelled $i$ appears. $L$ is the length of the ciphertext.

If Monoalphabetic Substitution Cipher is applied, the $IC$ of plaintext should be the same as the $IC$ of ciphertext.

Let two strings be $x=x_1x_2x_3\cdots x_p$ and $y=y_1y_2y_3\cdots y_q$. The probability of $a=b$, where $a$ is a random letter in $x$ and $b$ randomly in $y$, is defined as $MI$. $f_i$ shows how many times the letter labelled $i$ appears in $x$. $y:h$ means shift the letters in $y$ with $h$ increment. $F_i$ shows how many times the letter labelled $i$ appears in $y:h$. Then, $$MI(x,y:h)=\frac{\sum\limits_{i=0}^{n}f_iF_i}{pq}$$

Vigenère Cipher Cracking
Here is a part of the cipher text used Vigenère Cipher:$$c=lvktwvgvgnodttqifqqmubujglevmbkhziczglcsphwe…$$
To crack this message, we should know what the key is. Here we use index of coincidence. The index of the first letter in the string is 1.
Suppose the key length is 1. Then we should get the string $$s_{1_1}=c[x] \textup{ for } x = 1k+1,k\in\mathbb{N}=lvktwvgvgnodttqifqqmubujglevmbkhziczglcsphwe…$$
Calculate the $IC$,
$$IC_{1_1}=0.0418$$
It is not consistent with $0.065$, so the key length is not 1.


Suppose the key length is 2. Then we should get the string
$$s_{2_1}=c[x] \textup{ for } x = 2k+1,k\in\mathbb{N}=lkwggotqfquugemkzcgcpw…$$
$$s_{2_2}=c[x] \textup{ for } x = 2k+2,k\in\mathbb{N}=vtvvndtiqmbjlvbhizlshe…$$ Calculate the $IC$, then the average.
$$IC_{2_1}=0.0427,IC_{2_2}=0.0411,IC_2=0.0419$$
It is not consistent with $0.065$, so the key length is not 2.
Suppose the key length is 3. Then we should get the string
$$s_{3_1}=c[x] \textup{ for } x = 3k+1,k\in\mathbb{N}=ltgntiqbgvkigsw…$$
$$s_{3_2}=c[x] \textup{ for } x = 3k+2,k\in\mathbb{N}=vwvotfmulmhclpe…$$
$$s_{3_3}=c[x] \textup{ for } x = 3k+3,k\in\mathbb{N}=kvgdqqujebzzch…$$ Calculate the $IC$, then the average.
$$IC_{3_1}=0.0417,IC_{3_2}=0.0417,IC_{3_3}=0.0424,IC_3=0.0419$$
It is not consistent with $0.065$, so the key length is not 3.
$$\cdots$$
Suppose the key length is 7. Then we should get the string }
$$s_{7_1}=c[x] \textup{ for } x = 7k+1,k\in\mathbb{N}=lvqbmzw…$$
$$s_{7_2}=c[x] \textup{ for } x = 7k+2,k\in\mathbb{N}=vgiubge…$$
$$s_{7_3}=c[x] \textup{ for } x = 7k+3,k\in\mathbb{N}=knfjkl…$$
$$\cdots$$
$$s_{7_7}=c[x] \textup{ for } x = 7k+7,k\in\mathbb{N}=gtuvch…$$
Calculate the $IC$, then the average.
$$IC_{7_1}=0.0674,IC_{7_2}=0.0677,IC_{7_3}=0.0621,\cdots IC_{7_7}=0.0634,IC_7=0.0657$$
It is consistent with $0.065$, so the key length is 7.
Then caluculate the $MI$.
There are $C_7^2\times 26=546$ $MI$ values,$$MI(s_{7_1},s_{7_2}:0),MI(s_{7_1},s_{7_2}:1),\cdots MI(s_{7_1},s_{7_2}:25)$$$$\cdots$$$$MI(s_{7_6},s_{7_7}:0),MI(s_{7_6},s_{7_7}:1),\cdots MI(s_{7_6},s_{7_7}:25)$$
Let $k=k_1k_2k_3k_4k_5k_6k_7$.
If $MI(s_{n_p},s_{n_q}:h)$ nears 0.065, it means $k_p – k_q = h\mod 26$.
After a hard calculation and finding. You can find all formulas like this: $k_p – k_q = h\mod 26$.
Finally, $k=k_1[k_1+5][k_1+23][k_1+6][k_1+10][k_1+22][k_1+20]$.
You can guess the key using English words. If failed, then use brute force at the complexity $26$ until the plaintext is founded.

The key is $$infosec$$
The plaintext is $$differentialprivacyisthestateoftheartgoalfor…$$

Hill Cipher is hard to crack only using statistical tools on cipertexts. But suppose we have got several cipher-plain pairs, this will be easy.

Hill Cipher Cracking

We know a lot of cipher-plain pairs.
$\textbf{C} = \textbf{P} \times \textbf{K}\mod 26$, where the dimension of $\textbf{C}$ , $\textbf{P}$ is $n\times n$. $\textbf{K}$ is an $n\times n$ key matrix where $(|\textbf{K}|, 26) = 1$.
Conversely, $\textbf{P}=\textbf{C}\times \textbf{K}^{-1}\mod 26$.
More detailed  $$\textbf{P}=\begin{bmatrix} \textbf{p}_1\\\textbf{p}_2\\\vdots\\\textbf{p}_n \end{bmatrix},\textbf{C}=\begin{bmatrix} \textbf{c}_1\\\textbf{c}_2\\\vdots\\\textbf{c}_n \end{bmatrix}$$
Then $$\textbf{K}=\textbf{P}^{-1}\textbf{C}\mod 26$$
Mind that $|\textbf{P}|\neq 0$, meaning that we need to know at least $n$ pairs of cipher-plain pairs.

Part II Cryptography Develops Here

We can not just protect the encrypting algorithms any more.

Chapter 3 Block Cipher: DES

Give the plaintext in binary form, and break them into blocks with the same length. Each block will be transformed into cipher blocks using the pre-defined key.
Block Cipher is divided into two types, one is symmetric block cipher, the other is asymmetric block cipher. To emphasize, when we say block cipher, it always means symmetric block cipher.
Block cipher is used to enhance the confidential level of data, and still can be used to create pseudorandom numbers, stream cipher, validation code and hash functions.
It is fast when encrypting and decrypting with high confidential level, and is supported by lots of chips.

The Design of Block Cipher

1. The block length should be long enough.
2. Key space should be large enough.
3. The encryption pipeline is complicate.
4. The encryption and decryption process is easy to compute.
5. No data expansion and compression.

For an $n$ block-size block cipher, different keys decide different transformations. For a given key $k$, the encryption transformation $E_K$ is a transformation on $GF(2^n)$, and the decryption transformation is the inverse transformation of the encryption transformation.
If the key length is $t$, the key space is scaled $2^t$. So we should keep $2^t\leq 2^n!$, otherwise the encryption transformation will not be injective.

Diffusion: 1 bit’s change in the plaintext affects lots of bit’s change in the ciphertext.
Confusion: Get the relation among plaintext, key and ciphertext complicated. But invertible properties should be kept.
To sum up, a secure cipher should have non-linear calculation process.

Production Cipher: Through the combination of diffusion and confusion, the cipher will be stronger. And this cipher is friendly for hardwares.

SPN(Substitution Permutaiton Network)
Substitution acts as a confusion part. And the permutation acts as a diffusion part. This network has avalanche effect.

The Design of Round Function

To enhance the security level of a cipher method, we may use lots of rounds to encrypt the plaintext. Mind that it is not wise to say: the more rounds, the better. To keep the encryption and decryption easy, we sometimes just use 1 function to do this, this function is called Round Function.
Round Functions should have the following properties:

1. Non-Linear: This is the most important part, which improves the security level.
2. Invertible: Can be used both in encryption process and decryption process.
3. Performance: A round can be seen as an atomic operation, it should be designed with high performance.
4. Avalanched : It should have avalanche effect.

The Design of Sub-key

Bacause we have a lot of rounds to do some calculation for an encryption, it will be easy if we use different keys during these calculations. But too many keys are hard to remember. So we use sub-keys to tackle this problem.
Sub-key : A series of key generated from a key, usually called the seed key, using a sub-key generating algorithm.
Sub-key Generation Algorithms should have these properties:

1.Easy, Fast
2.Seed key should contribute the same weight on the sub-keys generated.
3.No weak keys, or just several easy to find weak keys.

DES

Data Encryption Standard: IBM’s Lucifer, the first encryption standard.

The plain blocks and the cipher blocks have the length 64.
The key length is 56, weak key exists.
The combination of diffusion and confusion is applied. 16 round of S-P process.

The structure of DES

//TODO PICTURE

1. 64 bit plain block was first divided into two parts using $IP = 58,50,42,34,26,18,10,2,\cdots$. It means the first bit in $L_0$ is the 58th bit in the plaintext.
2. Then the 16 rounds of encryption.
   $L_0R_0=IP(p)$
   $L_i=R_{i-1}\quad i = 1,2,\cdots,16$
   $R_i=L_{i-1}\oplus F(R_{i-1},K_i)\quad i = 1,2,\cdots,16$
   $c=IP^{-1}(R_{16}L_{16})$

Details in DES

More detailed, sub-key generation and the $F$ function, or the Feistel function work as the followings.
//TODO PICTURES
Before function $PC_1$, it deletes the parity check digits, those are bit 8, 16, 24, 32, 40, 48, 56, 64.
In successive rounds, both halves are rotated left by one or two bits ([1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1] in their round order), and then 48 sub-key bits are selected by Permuted Choice 2 (PC-2)—24 bits from the left half, and 24 from the right.
$PC1$ and $PC2$ is left out.
Function $E$ is defined as:

[
32 1  2  3  4  5
4  5  6  7  8  9
8  9  10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1 
] 

thus expand 32 bits into 48 bits.

$F(R_{i-1},k_i)=P(S(E(R_{i-1})\oplus K_i))$
Function $P$ is defined as:

[
16 7  20 21 29 12 28 17
1  15 23 26 5  18 31 10
2  8  24 14 32 27 3  9
19 13 30 6  22 11 4 25
]

which shuffles the positions.
S boxes changes 6 bits into 4 bits. Box $S1$ is defined as:

14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

Different boxes have their values.
An input “011011” has outer bits “01” and inner bits “1101”; noting that the first row is “00” and the first column is “0000”, the corresponding output for S-box S1 would be “0101” (=5), the value in the second row, 14th column.

Decryption of DES

From the encryption process, we still have the decryption process.
$L_{16}R_{16}=IP^{-1}(c)$
$R_{i-1}=L_{i}\quad i = 1,2,\cdots,16$
$L_{i-1}=R_{i}\oplus F(L_{i},K_i)\quad i = 1,2,\cdots,16$
$p=IP(L_0R_0)$

Cryptanalysis of DES

Complementation property:$E_k(p)=c\Leftrightarrow E_{\bar k}(\bar p)=\bar c$. This property means that 1 trial tests 2 keys. If $c_1=E_k(p)$, $c_2=E_k(\bar p)$, then we know $\bar c_2=E_{\bar k}(p)$,thus 2 keys can be tested.

Weak keys in DES

Given a seed key $k$, if the 16 sub-keys are all the same. Then $k$ is called a weak key. For a weak key $k$, we have $E_k(E_k(p))=p$,$D_k(D_k(p))=p$. There are only 4 weak keys:

0101010101010101
1F1F1F1FE0E0E0E0
E0E0E0E01F1F1F1F
FEFEFEFEFEFEFEFE

Given a seed key $k$, if the 8 sub-keys are all the same, the other 8 are also the same at a different value. Then $k$ is called a semi weak key. Here $E_{k_2}(E_{k_1}(p))=E_{k_1}(E_{k_2}(p))=p$ .

There are also quarter weak keys and eighth weak keys.

Multiple DES

Use multiple DES with different keys to encrypt increases the security level.
However, 2DES is not a great choice. $c=E_{k_2}(E_{k_1}(p))$, then $D_{k_2}(c)=E_{k_1}(p)$, it is in fact a 57 bit encryption. 3DES will be better.

Chapter 4 Block Cipher: AES

Brief Abstract Algebra

Group
A group $G$ is a set equipped with a binary operation, denoted by $( \circ )$, satisfying the following properties:
Closure: \( \forall g, h \in G \), \( g \circ h \in G \)
Associativity: \( \forall g_1, g_2, g_3 \in G \), \( (g_1 \circ g_2) \circ g_3 = g_1 \circ (g_2 \circ g_3) \)
Identity Element: There exists an element \( e \in G \) such that \( g \circ e = g = e \circ g \) for all \( g \in G \)
Inverse Element: For each element \( g \in G \), there exists an element \( g’ \in G \) such that \( g \circ g’ = e \)

If $G$ is finite, the group is called a finite group, and the number of elements in $G$ is called the order of the group, denoted $|G|$.

Abelian Group: If the operation $\circ$ is commutative, i.e., $g \circ h = h \circ g$ for all $g, h \in G $, the group is called an Abelian group.

Subgroups: If $ H \subseteq G $ is a subset of $G$ that forms a group under the same operation, then $H$ is called a subgroup of $G$ .

Cyclic Groups: A group $G$ is called cyclic if there exists an element \( a \in G \) such that every element of \( G \) can be written as \( a^n \) for some integer \( n \). The element \( a \) is called a generator of the group.

Ring
A ring \( R \) is a set equipped with two binary operations, addition \( + \) and multiplication \( \times \), satisfying the following properties:

\( R \) forms an Abelian group under addition.
Multiplication is closed, associative, and distributes over addition.

If the multiplication in \( R \) is commutative, and if there exists a multiplicative identity, and does not hold zero factors. Then the ring is called a Integral Domain.

Field
A field \( F \) is a set with two binary operations, addition and multiplication, satisfying:

\( F \) forms an Abelian group under addition.
The nonzero elements of \( F \) form an Abelian group under multiplication.
Distributive property: \( a \times (b + c) = (a \times b) + (a \times c) \)

Galois Field

Galois Field must have the order $p^n$ where $p$ is a prime, this field is then called $GF(p^n)$. It is a finite group.
$GF(2^n)$ is used widely in cryptography.

$GF(p)$ is defined as the modulo calculations on the set $\mathbb{Z}_p = \{0,1,\cdots,p-1\}$

Polynomial Operations On Galois Field
An n-ordered polynomial is defined as $$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0$$where $a_n\neq 0$. If $a_n=1$, then it is called the monic polynomial.

Given two polynomials:
\[f(x) = \sum_{i=0}^{n} a_i x^i \quad \text{and} \quad g(x) = \sum_{i=0}^{m} b_i x^i\]
with \( n \geq m \), the sum and product are defined as:

$$\begin{align*} (f + g)(x) &= \sum_{i=0}^{m} (a_i + b_i)x^i + \sum_{i=m+1}^{n} a_i x^i \\ (f \times g)(x) &= \sum_{i=0}^{m+n} c_i x^i, \quad \text{where} \, c_i = \sum_{j=0}^{i} a_j b_{i-j}\end{align*}$$

Now, let us take a look at division on a Galois field. For a $n$-ordered polynomial $f(x)$ and a $m$-ordered polynomial $g(x)$ where $m\leq n$, we define $f(x)\div g(x)=q(x) \textbf{ with the remainder } r(x)$, where $r(x)$ is a polynomial with an order less than $m$. We then say $f(x)\mod g(x)=r(x)$. When $r(x)=0$, then we say $g(x)$ is a factor of $f(x)$, denoted $g(x)|f(x)$.

Irreducible Polynomials
A polynomial \( f(x) \) over a field \( F \) is called irreducible if it cannot be factored into two non-constant polynomials over \( F \). The polynomial is also called prime polynomial.

For AES, in $GF(2^8)$, $x^8+x^4+x^3+x+1$ is a prime polynomial.

Modulo Calculations of polynomials
When a polynomial calculation is done, let the coefficients $a_i$ become $a_i \mod p$. All results $f(x)$ can not be higher than the order $p-1$, otherwise we substitute it with the remainder of $f(x)\div g(x)$, where $g(x)$ is a prime polynomial with the order $p$.

AES

AES encryption uses four different functions:
Nibble substitution (NS)
Shift row (SR)
Mix columns (MC)
Add round key (Ak)

For decryption, the functions used are:
Add round key (Ak)
Inverse nibble substitution (INS)
Inverse shift row (ISR)
Inverse mix columns (IMC)


AES Encryption and Decryption Algorithm
Using the symbols for these functions, the AES encryption and decryption algorithms can be expressed as:
\[\text{Encryption: } Ak_2 \circ SR \circ NS \circ Ak_1 \circ MC \circ SR \circ NS \circ Ak_0\]
\[\text{Decryption: } Ak_0 \circ INS \circ ISR \circ IMC \circ Ak_1 \circ INS \circ ISR \circ Ak_2\]

Data Structure

To simplify the process, we use the following configurations:
Key size = 16 bits (AES uses 128/192/256 bits)
Number of rounds = 2 (AES uses 10/12/14 rounds)
Plaintext block size = 16 bits (AES uses 128 bits)
Ciphertext block size = 16 bits (AES uses 128 bits)
The following matrix represents the state during AES encryption:

$$\begin{bmatrix}b_0b_1b_2b_3 & b_8b_9b_Ab_B \\b_4b_5b_6b_7 & b_Cb_Db_Eb_F\end{bmatrix}=\begin{bmatrix}S_{0,0} & S_{0,1} \\S_{1,0} & S_{1,1}\end{bmatrix}$$

Each round of encryption involves the following operations: Nibble substitution, Shift row, Mix columns, and Add round key. Shown as below:
$$ \begin{bmatrix}S_{0,0} & S_{0,1} \\S_{1,0} & S_{1,1}\end{bmatrix}\underset{NS}{\overset{{S}}{\rightarrow}}\begin{bmatrix}S_{0,0} & S_{0,1} \\S_{1,0} & S_{1,1}\end{bmatrix}\underset{SR}{\overset{{(24)}}{\rightarrow}}\begin{bmatrix}S_{0,0} & S_{0,1} \\S_{1,0} & S_{1,1}\end{bmatrix}\underset{MC}{\overset{{S}}{\rightarrow}}\begin{bmatrix}S_{0,0} & S_{0,1} \\S_{1,0} & S_{1,1}\end{bmatrix}\underset{AK}{\overset{{r_i}}{\bigoplus}}\begin{bmatrix}S_{0,0} & S_{0,1} \\S_{1,0} & S_{1,1}\end{bmatrix}$$

For NS:
We have an S-Box and an Inv-S-Box defined as below:
$$\begin{bmatrix}9&4 &A &B \\D&1 &8 &5 \\6& 2&0 &3 \\C& E& F&7\end{bmatrix},\begin{bmatrix}A&5 &9 &B \\1&7 &8 &F \\6&0 &2 &3 \\C&4 &D &E\end{bmatrix}$$
The first 2 bits in the block of a state is considered as column index and the latter 2 is row index. For example:
$$ \begin{bmatrix}8 & 1 \\A & C\end{bmatrix}\underset{NS}{\rightarrow}\begin{bmatrix}6 & 4 \\0 & C\end{bmatrix}$$

For SR:
Just a simple position shift:
$$ \begin{bmatrix}6 & 4 \\0 & C\end{bmatrix}\underset{SR}{\rightarrow}\begin{bmatrix}6 & 4 \\C & 0\end{bmatrix}$$

For MC:
Calculation in $GF(16)$:
$$ \begin{bmatrix}S'{0,0} & S'{0,1} \\S'{1,0} & S'{1,1}\end{bmatrix}= \begin{bmatrix}1 & 4 \\4 & 1\end{bmatrix} \begin{bmatrix}S_{0,0} & S_{0,1} \\S_{1,0}& S_{1,1}\end{bmatrix}$$

The inverse transformation is defined as:
$$ \begin{bmatrix}S_{0,0} & S_{0,1} \\S_{1,0} & S_{1,1}\end{bmatrix}= \begin{bmatrix}9 & 2 \\2 & 9\end{bmatrix} \begin{bmatrix}S'{0,0} & S'{0,1} \\S'{1,0}& S'{1,1}\end{bmatrix}$$

An example for the calculation in $GF(16)$:
$$ \begin{bmatrix}3 & 4 \\7 & 3\end{bmatrix}= \begin{bmatrix}1 & 4 \\4 & 1\end{bmatrix} \begin{bmatrix}6 & 4 \\C & 0\end{bmatrix}$$

For AK:
We have pre-defined keys $w_0$ and $w_1$. Then $$w_2=w_0\oplus RCON(1)\oplus NS(w_1)$$
$$w_3=w_2\oplus w_1$$
$$w_4=w_2\oplus RCON(2)\oplus NS(w_3)$$
$$w_5=w_4\oplus w_3$$
where $RCON(i)=[x^{i+2}\mod (x^4+x+1),0000]$, forming a 8 bit byte.

Suppose we have the key $2D55$, then $w_0 = 00101101$ and $w_1 = 01010101$.
$$w_2 = 00101101\oplus RCON(1)\oplus NS(01010101) = 00101101\oplus10000000\oplus00010001 = 10111100$$
$$w_3 = 10111100\oplus01010101 = 11101001$$
$$w_4 = 10111100\oplus RCON(2)\oplus NS(10011110) = 10111100\oplus00110000\oplus00101111 = 10100011$$
$$w_5 = 10100011\oplus11101001 = 01001010$$

Detailed AES Encryption Structure

The AES encryption process is repeated for multiple rounds depending on the key length:
10 rounds for 128-bit keys
12 rounds for 192-bit keys
14 rounds for 256-bit keys
For the rounds, $AK,NS,SR,MC$ is performed and for the last round, it is $AK,NS,SR,AK$.

Encryption:

State = plaintext
State = AK(State, Key_0)
for i in range(1,N): # 1,2,3,…,N-1
    State = NS(State, SBox)
    State = SR(State)
    State = MC(State)
    State = AK(State, Key_i)
State = NS(State, SBox)
State = SR(State)
State = AK(State, Key_N)
ciphertext = State

This is S-Box:

63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76
CA 82 C9 7D FA 59 47 F0 AD D4 A2 AF 9C A4 72 C0
B7 FD 93 26 36 3F F7 CC 34 A5 E5 F1 71 D8 31 15
04 C7 23 C3 18 96 05 9A 07 12 80 E2 EB 27 B2 75
09 83 2C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F 84
53 D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CF
D0 EF AA FB 43 4D 33 85 45 F9 02 7F 50 3C 9F A8
51 A3 40 8F 92 9D 38 F5 BC B6 DA 21 10 FF F3 D2
CD 0C 13 EC 5F 97 44 17 C4 A7 7E 3D 64 5D 19 73
60 81 4F DC 22 2A 90 88 46 EE B8 14 DE 5E 0B DB
E0 32 3A 0A 49 06 24 5C C2 D3 AC 62 91 95 E4 79
E7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08
BA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8A
70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9E
E1 F8 98 11 69 D9 8E 94 9B 1E 87 E9 CE 55 28 DF
8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16

The inverse S-Box is left out here.

Let us take a look at a round in formal AES: now we have 16 bytes loaded in the blocks,\
$$\begin{bmatrix} A_0 & A_4 & A_8 & A_{12}\\ A_1 & A_5 & A_9 & A_{13}\\ A_2 & A_6 & A_{10} & A_{14}\\ A_3 & A_7 & A_{11} & A_{15}\\\end{bmatrix}\underset{NS}{\overset{S-Box}{\rightarrow}}\begin{bmatrix} B_0 & B_4 & B_8 & B_{12}\\B_1 & B_5 & B_9 & B_{13}\\B_2 & B_6 & B_{10} & B_{14}\\B_3 & B_7 & B_{11} & B_{15}\end{bmatrix}\underset{SR}{\overset{Byte Shift 0,1,2,3}{\rightarrow}}\begin{bmatrix} B_0 & B_4 & B_8 & B_{12}\\B_5 & B_9 & B_{13} & B_{1}\\B_{10} & B_{14} & B_{2} & B_{6}\\B_{15} & B_3 & B_{7} & B_{11}\end{bmatrix}$$
S-Box is a $16\times 16$ matrix. Performed per block.
MC: Calculations on Galois Field $GF(256)$
$$\begin{bmatrix}B_0 & B_4 & B_8 & B_{12}\\B_5 & B_9 & B_{13} & B_{1}\\B_{10} & B_{14} & B_{2} & B_{6}\\B_{15} & B_3 & B_{7} & B_{11}\end{bmatrix}\times\begin{bmatrix}2 & 3 & 1 & 1\\1 & 2 & 3 & 1\\1 & 1 & 2 & 3\\3 & 1 & 1 & 2\end{bmatrix}=\begin{bmatrix}C_0 & C_4 & C_8 & C_{12}\\C_1 & C_5 & C_9 & C_{13}\\C_2 & C_6 & C_{10} & C_{14}\\C_3 & C_7 & C_{11} & C_{15}\end{bmatrix}$$
Add Round Key:
$$Sub\_key\bigoplus\begin{bmatrix}C_0 & C_4 & C_8 & C_{12}\\C_1 & C_5 & C_9 & C_{13}\\C_2 & C_6 & C_{10} & C_{14}\\ C_3 & C_7 & C_{11} & C_{15}\end{bmatrix}=New State$$
There are 11 sub-keys in AES-128, 13 in AES-192, 15 in AES-256. For 11 sub-keys, there are 128 bits or 16 bytes or a DWORD (in x86) in a sub-key. We store all sub-keys in an array $W$, whose scale is 11 DWORDs (176B).
The keys are generated as below:
//TODO PICTURE
Where $RCON(i)$ for $i=0$ to $i=16$ is 0x8d, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36, 0x6c, 0xd8, 0xab, 0x4d, 0x9a.

AES was designed with the following considerations in mind:
Diffusion: Compared to DES, AES achieves full diffusion in just two rounds.
S-box Construction: The S-box is built using a clear and simple algebraic method to avoid any suspicion of backdoors.
Key Expansion: AES uses a nonlinear mixing of the key bits, providing both balance and asymmetry.
Security Margin: AES-128 provides a sufficient security margin, as the best known attacks reach up to 6 rounds, while AES has 10 rounds (AES-128).

AES offers multiple security benefits:

No Weak Keys: AES encryption and decryption processes are asymmetric, ensuring that weak keys cannot exist.
Resistance to Differential and Linear Cryptanalysis: AES was specifically designed to resist these attacks.
Exhaustive Key Search: An exhaustive key search attack on AES-128 would require an average of $2^{127}$ AES operations, which is computationally infeasible.

AES and DES share some similarities, but they also have notable differences.

Chapter 5 Modes On Block Cipher

Electronic Codebook (ECB)

The simplest mode of operation:
Encryption: Encrypts one 64-bit plaintext block at a time, with the same key for each block.
   Suitable for short message encryption.

Advantages:
   Simple to implement.
   Different plaintext blocks can be encrypted in parallel, especially in hardware, where the speed is very fast.

Disadvantages:
   The same plaintext block corresponds to the same ciphertext block, which cannot hide statistical patterns in plaintext.
   Cannot resist substitution attacks.
   Under the same key, the same plaintext block will always produce the same ciphertext block, making it vulnerable to replay attacks.

Cipher Block Chaining (CBC)

   Encryption: Encrypts one plaintext block at a time, with a key for each block. The input for the encryption algorithm is the current plaintext block XORed with the previous ciphertext block.

   The ciphertext is related to all previous plaintext blocks; each plaintext block is related to the current and the previous ciphertext block. This allows for random decryption of the ciphertext.

CBC Initialization Vector (IV)

For the first plaintext block, since there is no feedback ciphertext, an IV (Initialization Vector) needs to be pre-set in the register. Then both the sender and receiver must use the same IV. The IV does not need to be kept secret. Only its integrity should be guaranteed.

Encryption and Decryption Process

Encryption:
$$C_i=E_k(P_i\oplus C_{i-1})$$
//TODO PICTURE

Decryption:
$$P_i=D_k(C_i)\oplus C_{i-1}$$
//TODO PICTURE

CBC Padding

Padding to a whole byte. For example, if there are 5 bits in a byte, then we should pad for 3 bits. Specially, if there are 8 bits in a byte, seemingly no padding needed, we also add another 8 bits to pad it. At least one padding byte is appended.

CBC Padding Standard – PKCS #7 Padding Scheme

This padding scheme splits the original data into fixed-length blocks and calculates the difference between the final block and the block length in bytes.
    If the difference is zero, a new block is added, fully filled with the block length in bytes `10′.
    Otherwise, the difference is padded with the corresponding byte value, suppose that there are 4 bytes needed to be padded. Then we pad 04 04 04 04.

CBC Mode: Advantages and Disadvantages

Advantages:
   Hides the pattern of plaintext data. The chaining mechanism prevents tampering with the data, such as replay, embedding, or deletion attacks.
   Can be used to create a message authentication code (MAC) for data integrity verification.

Disadvantages:
   If an error occurs in one plaintext block, the decryption of subsequent ciphertext blocks will be affected, though after decryption, only the block with the error will be incorrect, while subsequent blocks will be correctly restored.
   If an error occurs in one ciphertext block when transferring, the block $P_i$ and $P_{i+1}$ will be incorrect, while subsequent blocks will be correctly restored.

Incorrect IV usage, like where IV increments linearly, makes CBC mode vulnerable to attacks. Even though distinct IVs are used, this version of CBC is not CPA-secure (Chosen Plaintext Attack). That is to say IV should be unpredictable.

Chained CBC Mode is a stateful variant of CBC used in SSL 3.0 and TLS 1.0, which encrypts a concatenated message in CBC mode. However, it is still not CPA-secure because the IVs selected for encrypting are coming from the last cipher block in the previous encryption.

Padding Attack

An attacker can modify the ciphertext and learn about the underlying plaintext by observing how decryption handles padding errors. This method leaks bits of the plaintext.
An attacker can systematically alter the padding of a ciphertext block and force the decryption algorithm to reveal information about the plaintext, byte by byte.

Padding Attack Process:

After learning the padding length, the attacker can progressively decrypt the entire block by systematically modifying the ciphertext until valid padding is produced.
The encryption process in CBC mode is represented as: \[C_0 = IV \quad C_i = E_k(P_i \oplus C_{i-1})\]

For decryption: \[P_i = D_k(C_i) \oplus C_{i-1}\]

By manipulating the ciphertext block $C_{i-1}$, the attacker aims to obtain $P_i$. The attack is carried out by modifying $C_{i-1}$ and observing the decryption result.
If the decryption produces an error, this indicates that the padding is incorrect, and the attacker continues making modifications to infer the correct padding and eventually decrypt the plaintext.
The attacker starts by modifying the last byte of the ciphertext and checks if the padding is valid.  Firstly, alter the first byte of $C_{n-1}$, denoted $C_{n-1}[0]$ to $C’_{n-1}[0]=C_{n-1}\oplus$0x10. Then the receiver will decrypt it to $P’_{n}[0]=D_k(C_n)[0]\oplus C’_{n-1}[0]$=$D_k(C_n)[0]\oplus C_{n-1}[0]\oplus$ 0x10 $=P_{n}[0]\oplus$ 0x10. Then if the padding is invalid, this reveals information about the padding length 16. Otherwise deduction of the final byte of the plaintext is needed, let us say alter the second byte of $C_{n-1}$. After decryption, if the padding is invalid, this reveals information about the padding length 15 otherwise further deduction of the final byte of the plaintext is needed.
After getting the padding length $L$, then we alter the last $L$ bytes in $C_{n-1}$ as:
$$C’_{n-1}[i]=C_{n-1}[i]\oplus P_n[i]\oplus (L+1)$$
Then the receiver will get $P’_{n}[i]=D_k(C_n)[i]\oplus C’_{n-1}[i]=P_{n}[i]\oplus P_{n}[i]\oplus (L+1)=L+1$.
Then for the last [$L+1$]-th byte, perform the alteration. $C’_{n-1}[15-L]=C_{n-1}[15-L]\oplus X$. Then $P’_{n}[15-L]=P_{n}[15-L]\oplus X$. There is an unique $X$ in 0x00 to 0xFF such that $P’_{n}[15-L]=L+1$, making the receiver unable to find a padding error. Then we can say $P_{n}[15-L]=(L+1)\oplus X$.

This method is highly efficient and allows the attacker to decrypt each plaintext byte with an average of 128 attempts per byte.

The same attack technique can be applied to non-final blocks of the ciphertext. The attacker modifies previous ciphertext blocks to turn them into the last block during decryption and then applies the same padding attack method to reveal the plaintext.

Cipher Feedback (CFB) Mode

In CFB mode:
   Encryption: The input is a 64-bit shift register initialized with an IV (Initialization Vector).
   Decryption: The received ciphertext is XORed with the output of the encryption function to retrieve the plaintext.
   Unlike CBC, the ciphertext is not directly added to the plaintext; instead, it is fed back into the key generation process.

Advantages:
   Suitable for converting block ciphers into stream ciphers.
   Can obscure plaintext patterns and detect modifications to ciphertext.

Disadvantages:
   Sensitive to transmission errors and may propagate errors.
   Requires an IV, and both the key and IV must be frequently updated.
   Cannot process multiple plaintext blocks in parallel.

Output Feedback (OFB) Mode

In OFB mode:

   Encryption: The block cipher acts as a key stream generator. The output of the encryption algorithm is fed back to the input, and the resulting key stream is XORed with the plaintext.

   OFB mode does not propagate errors and can handle transmission errors better than CBC or CFB.

Advantages:
   Solves the error propagation issue present in CBC and CFB modes.

Disadvantages:
   Difficult to detect if the ciphertext has been tampered with.
   Requires strict synchronization between the sender and receiver.

Counter (CTR) Mode

CTR mode is widely used in ATM network security and IPSec applications. The encryption process involves generating a counter value that is incremented for each block of plaintext and then XORed with the plaintext to produce the ciphertext.

Hardware Efficiency:
CTR mode supports parallel processing of multiple plaintext (or ciphertext) blocks during encryption (or decryption).

Software Efficiency:
CTR mode can take advantage of parallel computing architectures such as pipelining, multi-instruction dispatch per clock cycle, and SIMD instructions to enhance performance.

Random Access:
CTR mode allows for random access to any block of plaintext or ciphertext.

Simplicity:
Unlike ECB and CBC modes, CTR mode only requires the implementation of an encryption algorithm without a corresponding decryption algorithm.

No Padding:
CTR mode does not require padding since it can handle plaintext blocks of arbitrary length. When the last block is not a full block, only the required bits are XORed with the generated keystream.

Comparison of Block Cipher Modes

Mode	Advantages	Disadvantages
1.ECB	Simple, supports parallel processing, Cannot hide plaintext patterns, no error propagation	Cannot hide plaintext patterns, vulnerable to active attacks
2.CBC	Resistant to active attacks, suitable for long messages	Cannot process blocks in parallel, error propagation
3.CFB	Resistant to active attacks, can convert block ciphers to streamciphers, can encrypt data smaller than block size	Cannot process blocks in parallel, error propagation
4.OFB	Can convert block ciphers to stream ciphers, supports data smaller than block size	Vulnerable to active attacks, difficult to detect tampering
5.CTR	Supports parallel processing, no padding needed, fast hardware and software	Vulnerable to active attacks

Chapter 6 Introduction to Cryptography

Chapter 7 Introduction to Cryptography

Chapter 8 Introduction to Cryptography

Chapter 9 Introduction to Cryptography

Chapter 10 Introduction to Cryptography

Chapter 11 Introduction to Cryptography