Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place.

1
\documentclass[12pt,letterpaper,final]{report}
2
\usepackage{amsmath}
3
\usepackage{amsfonts}
4
\usepackage{amssymb}
5
\usepackage{amsthm}
6
\usepackage[linewidth=1pt]{mdframed}
7
\usepackage{fullpage}
8
\usepackage{graphicx}
9

10

11
\begin{document}
12

13
\begin{mdframed}
14

15
\center{\Large{\textbf{MATH 314 Fall 2024 - Class Notes}}}
16
\center{9/26/2024}  %Put the date of the class here!
17
\center{Mark Alexander} %Put Your Name Here!
18

19
\end{mdframed}
20

21
\bigskip
22
\textbf{\underline{Summary:}} This class covered simplified AES (SAES) and SAES encryption up to the key expansion step.
23

24
\bigskip\bigskip
25
\textbf{\underline{Advanced Encryption Standard (AES)}}
26

27
\begin{itemize}
28
\item All the encryption happens in $\mathbb{F}_{256} = \mathbb{F}_{2^8}$
29
\item Permutation/Substitution network with 10 rounds, every round uses a different key all generated from a master key by key expansion
30
\item Confusion is produced using a single substitution box (S-box)
31
\end{itemize}
32

33
\bigskip
34
\textbf{\underline{Simplified Advanced Encryption Standard (SAES)}}
35
\begin{itemize}
36
\item Uses $\mathbb{F}_{256} = \mathbb{F}_{2^4}$ instead
37
\item$\pmod{x^4+x+1}$
38
\item SAES S-box is a function $\mathbb{F}_{16} \rightarrow \mathbb{F}_{16}$, in other words, inputs 4 bits $\rightarrow$ outputs 4 bits
39
\item Formula: Treat input as a polynomial in $\mathbb{F}_{16}$, find its inverse. Takes this output and convert the bits to a vector $\vec{v}$:
40
$$
41
\begin{bmatrix}
42
1 & 0 & 1 & 1\\
43
1 & 1 & 0 & 1\\
44
1 & 1 & 1 & 0\\
45
0 & 1 & 1 & 1\\
46
\end{bmatrix}
47
\vec{v} +
48
\begin{bmatrix}
49
1 \\
50
0 \\
51
0 \\
52
1 \\
53
\end{bmatrix}
54
\rightarrow \text{output of S-box}
55
$$
56
\end{itemize}
57

58

59
\bigskip
60
\textbf{\underline{Example:}}  Compute the s-box value of \texttt{1010}
61

62
\texttt{1010} evaluates to $1x^3+0x^2+1x+0$ as a polynomial, simplified as $x^3+x$
63

64
\bigskip
65
The inverse of $x^3+x$ is then found using Euclid's algorithm for polynomials:
66

67
\includegraphics[width=0.6\textwidth]{./IMG_7819.jpeg}
68

69
\bigskip
70
\textbf{\underline{Note:}} AES (and SAES) are $\mathbb{F}_2[x]$, and are therefore mod 2, simply meaning all negatives become positive
71

72
\bigskip
73
Long division is performed for all found remainders, where the divisor is divided by the last found remainder. This is performed until a remainder of 0 is found or the degree of the divisor is larger than the dividend.
74

75
\bigskip
76
$(x^3+x) \div (x^2+x+1) = (x+1)\ R(x+1)$
77

78
$(x^2+x+1) \div (x+1) = (x)\ R(1)$
79

80
\bigskip
81
Thus, we have found:
82

83
$(x^4+x+1)=x(x^3+x)+(x^2+x+1)$
84

85
$(x^3+x)=(x+1)(x^2+x+1)+(x+1)$
86

87
$(x^2+x+1)=x(x+1)+1$
88

89
\bigskip
90
Using Extended Euclid's Algorithm:
91

92
$(x^2+x+1)=(x^4+x+1)+x(x^3+x)$
93

94
$(x+1)=(x^3+x)+(x+1)(x^2+x+1)$
95

96
$1=(x^2+x+1)+x(x+1)$
97

98
\bigskip
99
Finding the inverse of $x^3+x$:
100

101
$1=(x^2+x+1)+x(x+1)$
102

103
$1=(x^2+x+1)+x((x^3+x)+(x+1)(x^2+x+1))$
104

105
$1=(x^2+x+1)+x(x^3+x)+(x^2+x)(x^2+x+1)$
106

107
$1=(x^2+x+1)(x^2+x+1)+x(x^3+x)$
108

109
$1=(x^2+x+1)((x^4+x+1)+x(x^3+x))+x(x^3+x)$
110

111
$1=(x^2+x+1)(x^4+x+1)+(x^3+x^2+x)(x^3+x)+x(x^3+x)$
112

113
$1=(x^2+x+1)(x^4+x+1)+(x^3+x^2)(x^3+x) \pmod{x^4+x+1}$
114

115
$1=(x^3+x^2)(x^3+x) \pmod{x^4+x+1}$
116

117
$(x^3+x)^{-1}=x^3+x^2 \pmod{x^4+x+1}$
118

119
\bigskip
120
The inverse of $x^3+x$ is $x^3+x^2$ expressed in bits as \texttt{1100}
121

122
\bigskip
123
To find the S-box value:
124

125
\bigskip
126
$
127
\begin{bmatrix}
128
1 & 0 & 1 & 1\\
129
1 & 1 & 0 & 1\\
130
1 & 1 & 1 & 0\\
131
0 & 1 & 1 & 1\\
132
\end{bmatrix}
133
\begin{bmatrix}
134
1 \\
135
1 \\
136
0 \\
137
0 \\
138
\end{bmatrix} +
139
\begin{bmatrix}
140
1 \\
141
0 \\
142
0 \\
143
1 \\
144
\end{bmatrix} =
145
\begin{bmatrix}
146
0 \\
147
0 \\
148
0 \\
149
0 \\
150
\end{bmatrix}
151
$
152

153

154
\bigskip
155
The S-box value of \texttt{1010} is \texttt{0000}
156

157
\bigskip\bigskip
158
\textbf{\underline{Using SAES:}}
159
\begin{itemize}
160
\item SAES performs 2 rounds
161
\item Utilizes a masterkey, plaintext, and ciphertext (all 16 bits)
162
\item The masterkey consists of two 8 bit words $(W_0, W_1)$
163
\item 2 "round keys" are needed, these are used for each round
164
\item The keys $k_1$ and $k_2$ are found using key expansion
165
\end{itemize}
166

167
\bigskip
168
Key Expansion:
169

170
$W_2 = W_0 \oplus g(W_1, 1)$
171

172
$W_3 = W_1 \oplus W_2$
173

174
$W_4 = W_2 \oplus g(W_3, 2)$
175

176
$W_5 = W_3 \oplus W_4$
177

178
\bigskip
179
The function $g(W, i)$ is found using:
180
\begin{figure}[h]
181
\includegraphics[width=0.6\textwidth]{./IMG_7825.jpg}
182
\end{figure}
183

184
\bigskip\bigskip\bigskip
185
\textbf{\underline{SAES Encryption:}}
186
\begin{itemize}
187
\item Plaintext is 16 bits
188
\item Add master key
189
\end{itemize}
190
Round 1:
191
\begin{enumerate}
192
\item Substitute
193
\item Shift rows
194
\item Mix columns
195
\item Add round key 1
196
\end{enumerate}
197
Round 2:
198
\begin{enumerate}
199
\item Substitute
200
\item Shift rows
201
\item Add round key 2
202
\end{enumerate}
203
After round 2 the ciphertext is found.
204

205
\bigskip\bigskip
206

207

208
\textbf{\underline{Breaking down the steps:}}
209

210
\bigskip
211
Substitute Step
212
\begin{enumerate}
213
\item Break into 4 nibbles
214
\item Substitute into S-box
215
\item Write entries out in a matrix (fill out columns first)
216
\end{enumerate}
217

218
\bigskip
219
Shift Rows
220
\begin{enumerate}
221
\item Leave top row unchanged
222
\item Swap entries in bottom row
223
\end{enumerate}
224

225
\bigskip
226
Mix Columns
227
\begin{enumerate}
228
\item Take the matrix and multiply by encryption matrix
229
\item Add round key either by reading back to string of 1s and 0s or by converting the key into a matrix of nibbles.
230
\end{enumerate}
231

232
\bigskip
233
\textbf{\underline{Example:}} Encrypt $P = 1011\ 1001\ 1110\ 0000$ with key, $k_0 = 1001\ 1111\ 0101\ 1000$
234

235
\bigskip
236
Key expansion:
237

238
$W_0 = 1001\ 1111$
239

240
$W_1 = 0101\ 1000$
241

242
\bigskip
243
$W_2 = W_0 \oplus g(W_1, 1)$
244

245
\includegraphics[width=0.6\textwidth]{./IMG_7824.jpg}
246

247
$W_2 = 1001\ 1111 \oplus 1110\ 0001 = 0111\ 1110$
248

249
\bigskip
250
$W_3 = W_1 \oplus W_2$
251

252
$W_3 = 0101\ 1000 \oplus 0111\ 1110 = 0010\ 0110$
253

254
\bigskip
255
$W_4 = W_2 \oplus g(W_3, 2)$
256

257
\includegraphics[width=0.6\textwidth]{./IMG_7823.jpg}
258

259
$W_4 = 0111\ 1110 \oplus 1011\ 1010 = 1100\ 0100$
260

261
\bigskip
262
$W_5 = W_3 \oplus W_4$
263

264
$W_5 = 0010\ 0110 \oplus 1100\ 0100 = 1110\ 0010$
265

266
\bigskip
267
$k_1 = 0111\ 1110\  0010\ 0110$
268

269
$k_2 = 1100\ 0100\  1110\ 0010$
270

271
\bigskip
272
Computing P + $k_0$ beings round 0:
273

274
$P \oplus k_0 = 0010\ 0110\ 1011\ 1000$
275

276
\bigskip
277
From here, round 1 and 2 occur using the computed P + $k_0$ following the steps for each round.
278

279
\end{document}
280