Merge branch 'master' of github.com:AndreasFMueller/SeminarMatrizen

5 files changed, 387 insertions, 0 deletions

diff --git a/vorlesungen/slides/a/aes/blocks.tex b/vorlesungen/slides/a/aes/blocks.tex
new file mode 100644
index 0000000..9e95a86
--- /dev/null
+++ b/vorlesungen/slides/a/aes/blocks.tex
@@ -0,0 +1,193 @@
+%
+% blocks.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\def\s{0.4}
+\def\punkt#1#2{({#1*\s},{(3-#2)*\s})}
+\def\feld#1#2#3{
+        \fill[color=#3] \punkt{(#1-0.5)}{(#2+0.5)}
+		rectangle \punkt{(#1+0.5)}{(#2-0.5)};
+}
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Blocks}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Blocks}
+$4\times k$ Matrizen mit $k=4,\dots,8$
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\xdef\s{0.4}
+\foreach \i in {0,...,31}{
+	\pgfmathparse{mod(\i,4)}
+	\xdef\y{\pgfmathresult}
+	\pgfmathparse{int(\i/4)}
+	\xdef\x{\pgfmathresult}
+	\node at \punkt{\x}{\y} {\tiny $\i$};
+}
+\foreach \x in {-0.5,0.5,...,7.5}{
+	\draw \punkt{\x}{-0.5} -- \punkt{\x}{3.5};
+}
+\foreach \y in {-0.5,0.5,...,3.5}{
+	\draw \punkt{-0.5}{\y} -- \punkt{7.5}{\y};
+}
+\end{tikzpicture}
+\end{center}
+\uncover<2->{%
+Spalten sind $4$-dimensionale $\mathbb{F}_{2^8}$-Vektoren
+}
+\end{block}
+\uncover<3->{%
+\begin{block}{Zeilenshift}
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+
+\xdef\s{0.35}
+
+\begin{scope}
+	\feld{0}{3}{red!20}
+	\feld{0}{2}{red!20}
+	\feld{0}{1}{red!20}
+	\feld{0}{0}{red!20}
+
+	\feld{1}{3}{red!10}
+	\feld{1}{2}{red!10}
+	\feld{1}{1}{red!10}
+	\feld{1}{0}{red!10}
+
+	\feld{2}{3}{yellow!20}
+	\feld{2}{2}{yellow!20}
+	\feld{2}{1}{yellow!20}
+	\feld{2}{0}{yellow!20}
+
+	\feld{3}{3}{yellow!10}
+	\feld{3}{2}{yellow!10}
+	\feld{3}{1}{yellow!10}
+	\feld{3}{0}{yellow!10}
+
+	\feld{4}{3}{darkgreen!20}
+	\feld{4}{2}{darkgreen!20}
+	\feld{4}{1}{darkgreen!20}
+	\feld{4}{0}{darkgreen!20}
+
+	\feld{5}{3}{darkgreen!10}
+	\feld{5}{2}{darkgreen!10}
+	\feld{5}{1}{darkgreen!10}
+	\feld{5}{0}{darkgreen!10}
+
+	\feld{6}{3}{blue!20}
+	\feld{6}{2}{blue!20}
+	\feld{6}{1}{blue!20}
+	\feld{6}{0}{blue!20}
+
+	\feld{7}{3}{blue!10}
+	\feld{7}{2}{blue!10}
+	\feld{7}{1}{blue!10}
+	\feld{7}{0}{blue!10}
+
+	\foreach \x in {-0.5,0.5,...,7.5}{
+		\draw \punkt{\x}{-0.5} -- \punkt{\x}{3.5};
+	}
+	\foreach \y in {-0.5,0.5,...,3.5}{
+		\draw \punkt{-0.5}{\y} -- \punkt{7.5}{\y};
+	}
+\end{scope}
+
+\begin{scope}[xshift=3.5cm]
+        \feld{0}{0}{red!20}
+        \feld{1}{1}{red!20}
+        \feld{2}{2}{red!20}
+        \feld{3}{3}{red!20}
+
+        \feld{1}{0}{red!10}
+        \feld{2}{1}{red!10}
+        \feld{3}{2}{red!10}
+        \feld{4}{3}{red!10}
+
+        \feld{2}{0}{yellow!20}
+        \feld{3}{1}{yellow!20}
+        \feld{4}{2}{yellow!20} \feld{5}{3}{yellow!20}
+
+        \feld{3}{0}{yellow!10}
+        \feld{4}{1}{yellow!10}
+        \feld{5}{2}{yellow!10}
+        \feld{6}{3}{yellow!10}
+
+        \feld{4}{0}{darkgreen!20}
+        \feld{5}{1}{darkgreen!20}
+        \feld{6}{2}{darkgreen!20}
+        \feld{7}{3}{darkgreen!20}
+
+        \feld{5}{0}{darkgreen!10}
+        \feld{6}{1}{darkgreen!10}
+        \feld{7}{2}{darkgreen!10}
+        \feld{0}{3}{darkgreen!10}
+
+        \feld{6}{0}{blue!20}
+        \feld{7}{1}{blue!20}
+        \feld{0}{2}{blue!20}
+        \feld{1}{3}{blue!20}
+
+        \feld{7}{0}{blue!10}
+        \feld{0}{1}{blue!10}
+        \feld{1}{2}{blue!10}
+        \feld{2}{3}{blue!10}
+
+	\foreach \x in {-0.5,0.5,...,7.5}{
+		\draw \punkt{\x}{-0.5} -- \punkt{\x}{3.5};
+	}
+	\foreach \y in {-0.5,0.5,...,3.5}{
+		\draw \punkt{-0.5}{\y} -- \punkt{7.5}{\y};
+	}
+
+	\node at \punkt{-1.5}{1.5} {$\rightarrow$};
+\end{scope}
+
+\end{tikzpicture}
+\end{center}
+\end{block}}
+\end{column}
+\begin{column}{0.50\textwidth}
+\uncover<4->{%
+\begin{block}{Spalten mischen}
+Lineare Operation auf Spaltenvektoren mit Matrix
+\begin{align*}
+C&=\begin{pmatrix}
+\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}\\
+\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}&\texttt{01}_{16}\\
+\texttt{01}_{16}&\texttt{01}_{16}&\texttt{02}_{16}&\texttt{03}_{16}\\
+\texttt{03}_{16}&\texttt{01}_{16}&\texttt{01}_{16}&\texttt{02}_{16}
+\end{pmatrix}
+\\
+\uncover<5->{
+\det C
+&=
+\texttt{0a}_{16}
+}
+\uncover<6->{
+\ne 0}
+\uncover<7->{
+\quad\Rightarrow\quad \exists C^{-1}
+}
+\end{align*}
+\end{block}}
+\uncover<8->{%
+\begin{block}{Als Polynommultiplikation}
+Spalten = Polynome in $\mathbb{F}_{2^8}[Z]/(Z^4-1)$,
+\\
+\uncover<9->{%
+$C=\mathstrut$ Multiplikation mit
+\[
+c(Z) = \texttt{03}_{16}Z^3 + Z^2 + Z + \texttt{02}_{16}
+\]
+}
+\end{block}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/aes/bytes.tex b/vorlesungen/slides/a/aes/bytes.tex
new file mode 100644
index 0000000..e873e9a
--- /dev/null
+++ b/vorlesungen/slides/a/aes/bytes.tex
@@ -0,0 +1,96 @@
+%
+% bytes.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Bytes}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Endlicher Körper}
+1 Byte = 8 bits: $\mathbb{F}_{2^8}$
+mit Minimalpolynom:
+\[
+m(X) = X^8+X^4+X^3+X+1
+\]
+\end{block}
+\vspace{-10pt}
+\uncover<2->{%
+\begin{block}{Inverse $a^{-1}$}
+Mit dem euklidischen Algorithmus
+\[
+\begin{aligned}
+sa+tm&=1
+&&\Rightarrow&
+\uncover<3->{
+a^{-1} &= s}
+\\
+&
+&&&
+\uncover<4->{
+\overline{a}
+&=
+\begin{cases}
+a^{-1}&\; a\ne 0\\
+0     &\; a =  0
+\end{cases}}
+\end{aligned}
+\]
+\end{block}}
+\vspace{-10pt}
+\uncover<5->{%
+\begin{block}{Vektorraum}
+$\mathbb{R}_{2^8}$
+ist ein $8$-dimensionaler $\mathbb{F}_2$-Vektorraum
+\end{block}}
+\end{column}
+\begin{column}{0.48\textwidth}
+\uncover<6->{%
+\begin{block}{S-Box}
+$S\colon a\mapsto A\overline{a}+q$ mit
+\begin{align*}
+\only<1-7>{\phantom{\mathstrut^{-1}}A}
+\ifthenelse{\boolean{presentation}}{}{\only<8>{A^{-1}}}
+&=\only<1-7>{\begin{pmatrix}
+1&0&0&0&1&1&1&1\\
+1&1&0&0&0&1&1&1\\
+1&1&1&0&0&0&1&1\\
+1&1&1&1&0&0&0&1\\
+1&1&1&1&1&0&0&0\\
+0&1&1&1&1&1&0&0\\
+0&0&1&1&1&1&1&0\\
+0&0&0&1&1&1&1&1
+\end{pmatrix}}
+\ifthenelse{\boolean{presentation}}{}{
+\only<8->{
+\begin{pmatrix}
+0&0&1&0&0&1&0&1\\
+1&0&0&1&0&0&1&0\\
+0&1&0&0&1&0&0&1\\
+1&0&1&0&0&1&0&0\\
+0&1&0&1&0&0&1&0\\
+0&0&1&0&1&0&0&1\\
+1&0&0&1&0&1&0&0\\
+0&1&0&0&1&0&1&0
+\end{pmatrix}}
+}
+\\
+q&=X^7+X^6+X+1
+\end{align*}
+\end{block}}
+\vspace{-10pt}
+\uncover<7->{%
+\begin{block}{Inverse $S$-Box}
+\vspace{-10pt}
+\[
+S^{-1}(b) = \overline{A^{-1}(b-q)}
+\]
+\end{block}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/aes/keys.tex b/vorlesungen/slides/a/aes/keys.tex
new file mode 100644
index 0000000..d2ab712
--- /dev/null
+++ b/vorlesungen/slides/a/aes/keys.tex
@@ -0,0 +1,36 @@
+%
+% keys.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Schlüsselerzeugung}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{center}
+\includegraphics[width=\textwidth]{../../buch/chapters/90-crypto/images/keys.pdf}
+\end{center}
+\end{column}
+\begin{column}{0.48\textwidth}
+\begin{block}{Algorithmus}
+\begin{enumerate}
+\item<2->
+Startblock: begebener Schlüssel
+\item<3->
+Zeilenpermutation:
+$\pi=\mathstrut$ Multiplikation mit $Z^3=Z^{-1}$
+\item<4-> $S$-Box
+\item<5-> $r_i$: Addition einer Konstanten
+\[
+r_i = (\texttt{02}_{16})^{i-1}
+\]
+\end{enumerate}
+\end{block}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/aes/runden.tex b/vorlesungen/slides/a/aes/runden.tex
new file mode 100644
index 0000000..570b577
--- /dev/null
+++ b/vorlesungen/slides/a/aes/runden.tex
@@ -0,0 +1,47 @@
+%
+% runden.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{$n$ Runden}
+\vspace{-23pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Verschlüsselung}
+In Runde $i=0,\dots,n-1$
+\begin{enumerate}
+\item<2-> Wende die $S$-Box auf alle Bytes des Blocks an
+\item<3-> Führe den Zeilenschift durch
+\item<4-> Mische die Spalten
+\item<5-> Berechne den Schlüsselblock $i$  ($i=0$: ursprünglicher Schlüssel)
+\item<6-> Addiere (XOR) den Rundenschlüssel
+\end{enumerate}
+\end{block}
+\end{column}
+\begin{column}{0.48\textwidth}
+\uncover<7->{%
+\begin{block}{Entschlüsselung}
+In Runde $i=0,\dots,n-1$
+\begin{enumerate}
+\item<8-> Addiere den Rundenschlüssel $n-1-i$
+\item<9-> Invertiere Spaltenmischung (mit $C^{-1}$)
+\item<10-> Invertiere den Zeilenshift
+\item<11-> Wende $S^{-1}$ an auf jedes Byte
+\end{enumerate}
+\end{block}}
+\end{column}
+\end{columns}
+\uncover<12->{%
+\begin{block}{Charakteristika}
+\begin{itemize}
+\item<13-> Invertierbar
+\item<14-> Skalierbar: beliebig grosse Blöcke (Vielfache von 32\,bit)
+\item<15-> Keine ``magischen'' Schritte
+\end{itemize}
+\end{block}}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/aes/sinverse.tex b/vorlesungen/slides/a/aes/sinverse.tex
new file mode 100644
index 0000000..059100e
--- /dev/null
+++ b/vorlesungen/slides/a/aes/sinverse.tex
@@ -0,0 +1,15 @@
+%
+% sinverse.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Inverse $S$-Box}
+\begin{center}
+\includegraphics[width=\textwidth]{../../buch/chapters/90-crypto/images/sbox.pdf}
+\end{center}
+\end{frame}
+\egroup