{"id":1195,"date":"2024-11-07T20:00:00","date_gmt":"2024-11-07T11:00:00","guid":{"rendered":"https:\/\/www.yanagichiaki.jp\/?p=1195"},"modified":"2024-11-21T16:21:03","modified_gmt":"2024-11-21T07:21:03","slug":"foundation-of-cryptography","status":"publish","type":"post","link":"https:\/\/yanagichiaki.jp\/index.php\/2024\/11\/07\/foundation-of-cryptography\/","title":{"rendered":"Foundation of Cryptography"},"content":{"rendered":"\n

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<\/strong>
This page will be complete in 2025-01 as planned.<\/p>\n\n\n\n

Preface<\/h2>\n\n\n\n

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.<\/p>\n\n\n\n

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\u00e8re 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.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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\u2014topics that reveal the cutting-edge of the field.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

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.<\/p>\n\n\n\n

Contents<\/h2>\n\n\n\n

Left out. You can access it on the left of this page.<\/p>\n\n\n\n

Part I Cryptography Starts Here<\/h2>\n\n\n\n

Wise encryption methods love to go back here.<\/p>\n\n\n\n

Chapter 1 Introduction to Cryptography<\/h3>\n\n\n\n\n\n\n\n

Chapter 2 Traditional Cipher<\/h3>\n\n\n\n

Permutation Cipher<\/h4>\n\n\n\n

The password alphabet keeps unchanged. Generally, there is a defined permutation $\\sigma$ on the alphabet set.<\/p>\n\n\n\n\n\n\n\n

\n

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.<\/p>\n<\/blockquote>\n\n\n\n

Substitution Cipher<\/h4>\n\n\n\n

The alphabet is changed through a substitution $s:\\Sigma\\rightarrow\\Gamma$,<\/p>\n\n\n\n

\n

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.<\/p>\n<\/blockquote>\n\n\n\n\n\n\n\n

Caesar Cipher and Affine Cipher are Monoalphabetic Substitution Ciphers.<\/p>\n\n\n\n

\n

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.<\/p>\n\n\n\n

Plain<\/td>$ABCDEFGIJKLMNOPQRSTUVWXYZ$<\/td><\/tr>
Cipher<\/td>$XYZABCDEFGIJKLMNOPQRSTUVW$<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n


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$.<\/p>\n<\/blockquote>\n\n\n\n

\n

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$.<\/p>\n<\/blockquote>\n\n\n\n

\n

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.<\/p>\n<\/blockquote>\n\n\n\n

Vigen\u00e8re Cipher and Hill Cipher are Polyalphabetic Substitution Ciphers.<\/p>\n\n\n\n

\n

Vigen\u00e8re Cipher
Vigen\u00e8re 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$.<\/p>\n<\/blockquote>\n\n\n\n

\n

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}$
<\/p>\n<\/blockquote>\n\n\n\n\n\n\n\n\n\n\n\n

Enigma Cipher<\/h4>\n\n\n\n


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$.<\/p>\n\n\n\n\n\n\n\n

Due to the algebra expression is complicated, the work process will be shown in examples.<\/p>\n\n\n\n\n\n\n\n

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.<\/p>\n\n\n\n\n\n\n\n

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$.<\/p>\n\n\n\n

Properties of some Traditional Cipher<\/h4>\n\n\n\n

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}$$<\/p>\n\n\n\n\n\n\n\n

\n

Vigen\u00e8re Cipher Cracking
Here is a part of the cipher text used Vigen\u00e8re 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…$$<\/p>\n<\/blockquote>\n\n\n\n



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.
<\/p>\n\n\n\n\n\n\n\n

Hill Cipher Cracking<\/p>\n\n\n\n

\n

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.<\/p>\n<\/blockquote>\n\n\n\n

Part II Cryptography Develops Here<\/h2>\n\n\n\n

We can not just protect the encrypting algorithms any more.<\/p>\n\n\n\n

Chapter 3 Block Cipher: DES<\/h3>\n\n\n\n

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.<\/p>\n\n\n\n

The Design of Block Cipher<\/span><\/h4>\n\n\n\n


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.<\/p>\n\n\n\n


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.<\/p>\n\n\n\n

The Design of Round Function<\/span><\/h4>\n\n\n\n


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:<\/p>\n\n\n\n

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

    The Design of Sub-key<\/span><\/h4>\n\n\n\n


    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:<\/p>\n\n\n\n

    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.<\/p>\n\n\n\n

    DES<\/h4>\n\n\n\n


    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.<\/p>\n\n\n\n

    The structure of DES<\/span><\/h4>\n\n\n\n

    \/\/TODO PICTURE<\/p>\n\n\n\n

      \n
    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.<\/li>\n\n\n\n
    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})$<\/li>\n<\/ol>\n\n\n\n

      Details in DES<\/span><\/h4>\n\n\n\n

      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)\u201424 bits from the left half, and 24 from the right.
      $PC1$ and $PC2$ is left out.
      Function $E$ is defined as:<\/p>\n\n\n\n

      [\n32 1  2  3  4  5\n4  5  6  7  8  9\n8  9  10 11 12 13\n12 13 14 15 16 17\n16 17 18 19 20 21\n20 21 22 23 24 25\n24 25 26 27 28 29\n28 29 30 31 32 1 \n] <\/code><\/pre>\n\n\n\n
      thus expand 32 bits into 48 bits.<\/p>\n\n\n\n
      $F(R_{i-1},k_i)=P(S(E(R_{i-1})\\oplus K_i))$
      Function $P$ is defined as:<\/p>\n\n\n\n
      [\n16 7  20 21 29 12 28 17\n1  15 23 26 5  18 31 10\n2  8  24 14 32 27 3  9\n19 13 30 6  22 11 4 25\n]<\/code><\/pre>\n\n\n\n
       which shuffles the positions.
      S boxes changes 6 bits into 4 bits. Box $S1$ is defined as:
      <\/p>\n\n\n\n
      14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7\n0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8\n4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0\n15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13<\/code><\/pre>\n\n\n\n

      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.
      <\/p>\n\n\n\n
      Decryption of DES<\/span><\/h4>\n\n\n\n

      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)$<\/p>\n\n\n\n
      Cryptanalysis of DES<\/span><\/h4>\n\n\n\n

      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.<\/p>\n\n\n\n
      Weak keys in DES<\/strong><\/p>\n\n\n\n
      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: <\/p>\n\n\n\n
      0101010101010101\n1F1F1F1FE0E0E0E0\nE0E0E0E01F1F1F1F\nFEFEFEFEFEFEFEFE<\/code><\/pre>\n\n\n\n

      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. <\/p>\n\n\n\n
      Multiple DES<\/span><\/h5>\n\n\n\n
      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.<\/p>\n\n\n\n
      Chapter 4 Block Cipher: AES<\/h3>\n\n\n\n
      Brief Abstract Algebra<\/h4>\n\n\n\n
      Group<\/strong>
      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 \\)<\/p>\n\n\n\n
      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|$.<\/p>\n\n\n\n
      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.<\/p>\n\n\n\n
      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$ .<\/p>\n\n\n\n
      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.<\/p>\n\n\n\n
      Ring<\/strong>
      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<\/strong>
      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) \\)<\/p>\n\n\n\n
      Galois Field<\/h4>\n\n\n\n

      \tGalois 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.
      \t
      \t$GF(p)$ is defined as the modulo calculations on the set $\\mathbb{Z}_p = \\{0,1,\\cdots,p-1\\}$

      Polynomial Operations On Galois Field<\/strong>
      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<\/strong>
      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<\/strong>
      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$.<\/p>\n\n\n\n
      AES<\/h4>\n\n\n\n

      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<\/strong>
      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\\]
      <\/p>\n\n\n\n
      Data Structure<\/h4>\n\n\n\n

      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:<\/p>\n\n\n\n
      $$\\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}$$<\/p>\n\n\n\n
      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}$$<\/p>\n\n\n\n
      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}$$<\/p>\n\n\n\n
      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}$$<\/p>\n\n\n\n
      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}$$<\/p>\n\n\n\n
      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}$$<\/p>\n\n\n\n
      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}$$<\/p>\n\n\n\n
      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.<\/p>\n\n\n\n
      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$$
      <\/p>\n\n\n\n
      Detailed AES Encryption Structure<\/h4>\n\n\n\n

      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$.<\/p>\n\n\n\n
      Encryption:<\/p>\n\n\n\n
      State = plaintext\nState = AK(State, Key_0)\nfor i in range(1,N): # 1,2,3,\u2026,N-1\n    State = NS(State, SBox)\n    State = SR(State)\n    State = MC(State)\n    State = AK(State, Key_i)\nState = NS(State, SBox)\nState = SR(State)\nState = AK(State, Key_N)\nciphertext = State<\/code><\/pre>\n\n\n\n

      This is S-Box:<\/p>\n\n\n\n
      63 7C 77 7B F2 6B 6F C5 30 01 67 2B FE D7 AB 76\nCA 82 C9 7D FA 59 47 F0 AD D4 A2 AF 9C A4 72 C0\nB7 FD 93 26 36 3F F7 CC 34 A5 E5 F1 71 D8 31 15\n04 C7 23 C3 18 96 05 9A 07 12 80 E2 EB 27 B2 75\n09 83 2C 1A 1B 6E 5A A0 52 3B D6 B3 29 E3 2F 84\n53 D1 00 ED 20 FC B1 5B 6A CB BE 39 4A 4C 58 CF\nD0 EF AA FB 43 4D 33 85 45 F9 02 7F 50 3C 9F A8\n51 A3 40 8F 92 9D 38 F5 BC B6 DA 21 10 FF F3 D2\nCD 0C 13 EC 5F 97 44 17 C4 A7 7E 3D 64 5D 19 73\n60 81 4F DC 22 2A 90 88 46 EE B8 14 DE 5E 0B DB\nE0 32 3A 0A 49 06 24 5C C2 D3 AC 62 91 95 E4 79\nE7 C8 37 6D 8D D5 4E A9 6C 56 F4 EA 65 7A AE 08\nBA 78 25 2E 1C A6 B4 C6 E8 DD 74 1F 4B BD 8B 8A\n70 3E B5 66 48 03 F6 0E 61 35 57 B9 86 C1 1D 9E\nE1 F8 98 11 69 D9 8E 94 9B 1E 87 E9 CE 55 28 DF\n8C A1 89 0D BF E6 42 68 41 99 2D 0F B0 54 BB 16<\/code><\/pre>\n\n\n\n
      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.<\/p>\n\n\n\n
      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).<\/p>\n\n\n\n
      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.<\/p>\n\n\n\n
      AES and DES share some similarities, but they also have notable differences.<\/p>\n\n\n\n
      Chapter 5 Modes On Block Cipher<\/h3>\n\n\n\n
      Electronic Codebook (ECB)<\/h4>\n\n\n\n
      The simplest mode of operation:
         Encryption: Encrypts one 64-bit plaintext block at a time, with the same key for each block.
      \u00a0\u00a0 Suitable for short message encryption.<\/p>\n\n\n\n
      Advantages:<\/strong>
      \u00a0\u00a0 Simple to implement.
      \u00a0\u00a0 Different plaintext blocks can be encrypted in parallel, especially in hardware, where the speed is very fast.<\/p>\n\n\n\n
      Disadvantages:<\/strong>
      \u00a0\u00a0 The same plaintext block corresponds to the same ciphertext block, which cannot hide statistical patterns in plaintext.
      \u00a0\u00a0 Cannot resist substitution attacks.
      \u00a0\u00a0 Under the same key, the same plaintext block will always produce the same ciphertext block, making it vulnerable to replay attacks.<\/p>\n\n\n\n
      Cipher Block Chaining (CBC)<\/h4>\n\n\n\n
         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.<\/p>\n\n\n\n
         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.<\/p>\n\n\n\n
      CBC Initialization Vector (IV)<\/strong><\/p>\n\n\n\n
      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.<\/p>\n\n\n\n
      Encryption and Decryption Process<\/strong><\/p>\n\n\n\n
      Encryption:
      $$C_i=E_k(P_i\\oplus C_{i-1})$$
      \/\/TODO PICTURE<\/p>\n\n\n\n
      Decryption:
      $$P_i=D_k(C_i)\\oplus C_{i-1}$$
      \/\/TODO PICTURE<\/p>\n\n\n\n
      CBC Padding<\/strong><\/p>\n\n\n\n
      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.<\/p>\n\n\n\n
      CBC Padding Standard – PKCS #7 Padding Scheme<\/strong><\/p>\n\n\n\n
      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.
      \u00a0\u00a0\u00a0 If the difference is zero, a new block is added, fully filled with the block length in bytes `10′.
      \u00a0\u00a0\u00a0 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.<\/p>\n\n\n\n
      CBC Mode: Advantages and Disadvantages<\/strong><\/p>\n\n\n\n
      Advantages:
      \u00a0\u00a0 Hides the pattern of plaintext data. The chaining mechanism prevents tampering with the data, such as replay, embedding, or deletion attacks.
      \u00a0\u00a0 Can be used to create a message authentication code (MAC) for data integrity verification.<\/p>\n\n\n\n
      Disadvantages:
      \u00a0\u00a0 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.
      \u00a0\u00a0 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.<\/p>\n\n\n\n
      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.<\/p>\n\n\n\n
      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.<\/p>\n\n\n\n
      Padding Attack<\/strong><\/p>\n\n\n\n
      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.<\/p>\n\n\n\n
      Padding Attack Process:<\/p>\n\n\n\n
      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})\\]<\/p>\n\n\n\n
      For decryption: \\[P_i = D_k(C_i) \\oplus C_{i-1}\\]<\/p>\n\n\n\n
      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.\u00a0 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$.<\/p>\n\n\n\n
      This method is highly efficient and allows the attacker to decrypt each plaintext byte with an average of 128 attempts per byte.<\/p>\n\n\n\n
      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.<\/p>\n\n\n\n
      Cipher Feedback (CFB) Mode<\/h4>\n\n\n\n
      In CFB mode:
      \u00a0\u00a0 Encryption: The input is a 64-bit shift register initialized with an IV (Initialization Vector).
      \u00a0\u00a0 Decryption: The received ciphertext is XORed with the output of the encryption function to retrieve the plaintext.
      \u00a0\u00a0 Unlike CBC, the ciphertext is not directly added to the plaintext; instead, it is fed back into the key generation process.<\/p>\n\n\n\n
      Advantages:<\/strong>
      \u00a0\u00a0 Suitable for converting block ciphers into stream ciphers.
      \u00a0\u00a0 Can obscure plaintext patterns and detect modifications to ciphertext.<\/p>\n\n\n\n
      Disadvantages:<\/strong>
      \u00a0\u00a0 Sensitive to transmission errors and may propagate errors.
      \u00a0\u00a0 Requires an IV, and both the key and IV must be frequently updated.
      \u00a0\u00a0 Cannot process multiple plaintext blocks in parallel.<\/p>\n\n\n\n
      Output Feedback (OFB) Mode<\/h4>\n\n\n\n
      In OFB mode:<\/p>\n\n\n\n
         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.<\/p>\n\n\n\n
         OFB mode does not propagate errors and can handle transmission errors better than CBC or CFB.<\/p>\n\n\n\n
      Advantages:<\/strong>
      \u00a0\u00a0 Solves the error propagation issue present in CBC and CFB modes.<\/p>\n\n\n\n
      Disadvantages:<\/strong>
      \u00a0\u00a0 Difficult to detect if the ciphertext has been tampered with.
      \u00a0 \u00a0Requires strict synchronization between the sender and receiver.<\/p>\n\n\n\n
      Counter (CTR) Mode<\/h4>\n\n\n\n
      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.<\/p>\n\n\n\n
      Hardware Efficiency:<\/strong>
      CTR mode supports parallel processing of multiple plaintext (or ciphertext) blocks during encryption (or decryption).<\/p>\n\n\n\n
      Software Efficiency:<\/strong>
      CTR mode can take advantage of parallel computing architectures such as pipelining, multi-instruction dispatch per clock cycle, and SIMD instructions to enhance performance.<\/p>\n\n\n\n
      Random Access:<\/strong>
      CTR mode allows for random access to any block of plaintext or ciphertext.<\/p>\n\n\n\n
      Simplicity:<\/strong>
      Unlike ECB and CBC modes, CTR mode only requires the implementation of an encryption algorithm without a corresponding decryption algorithm.<\/p>\n\n\n\n
      No Padding:<\/strong>
      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.<\/p>\n\n\n\n
      Comparison of Block Cipher Modes<\/h4>\n\n\n\n
      Mode<\/span><\/th>Advantages<\/th>Disadvantages<\/th><\/tr><\/thead>
      1.ECB<\/td>Simple, supports parallel processing,  
      Cannot hide plaintext patterns, no error propagation<\/td>      		Cannot hide plaintext patterns, 
      vulnerable to active attacks<\/td><\/tr>
      2.CBC<\/td>Resistant to active attacks, 
      suitable for long messages<\/td>      		Cannot process blocks in parallel, 
      error propagation<\/td><\/tr>
      3.CFB<\/td>Resistant to active attacks, can convert block ciphers to streamciphers,  
      can encrypt data smaller than block size<\/td>      		Cannot process blocks in parallel, 
      error propagation<\/td><\/tr>
      4.OFB<\/td>Can convert block ciphers to stream ciphers,
      supports data smaller than block size<\/td>      		Vulnerable to active attacks, 
      difficult to detect tampering<\/td><\/tr>
      5.CTR<\/td>Supports parallel processing, no padding needed, 
      fast hardware and software<\/td>      		Vulnerable to active attacks<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
      Chapter 6  Introduction to Cryptography<\/p>\n\n\n\n\n\n\n\n
      Chapter 7  Introduction to Cryptography<\/p>\n\n\n\n\n\n\n\n
      Chapter 8  Introduction to Cryptography<\/p>\n\n\n\n\n\n\n\n
      Chapter 9  Introduction to Cryptography<\/p>\n\n\n\n\n\n\n\n
      Chapter 10  Introduction to Cryptography<\/p>\n\n\n\n\n\n\n\n
      Chapter 11  Introduction to Cryptography<\/p>\n","protected":false},"excerpt":{"rendered":"
      Notes on Foundation of Cryptography given by HITSZ.<\/p>\n","protected":false},"author":1,"featured_media":1317,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"swell_btn_cv_data":"","_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[89],"tags":[],"class_list":["post-1195","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-89"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/yanagichiaki.jp\/wp-content\/uploads\/2024\/11\/Sitecover.png","_links":{"self":[{"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/posts\/1195","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/comments?post=1195"}],"version-history":[{"count":66,"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/posts\/1195\/revisions"}],"predecessor-version":[{"id":1415,"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/posts\/1195\/revisions\/1415"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/media\/1317"}],"wp:attachment":[{"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/media?parent=1195"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/categories?post=1195"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/yanagichiaki.jp\/index.php\/wp-json\/wp\/v2\/tags?post=1195"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}