Merge remote-tracking branch 'upstream/master'

24 files changed, 1099 insertions, 0 deletions

diff --git a/vorlesungen/slides/a/Makefile.inc b/vorlesungen/slides/a/Makefile.inc
new file mode 100644
index 0000000..0c7ab0b
--- /dev/null
+++ b/vorlesungen/slides/a/Makefile.inc
@@ -0,0 +1,25 @@
+#
+# Makefile.inc -- additional depencencies
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+chaptera =								\
+	../slides/a/dc/prinzip.tex					\
+	../slides/a/dc/effizient.tex					\
+	../slides/a/dc/beispiel.tex					\
+									\
+	../slides/a/ecc/gruppendh.tex					\
+	../slides/a/ecc/kurve.tex					\
+	../slides/a/ecc/inverse.tex					\
+	../slides/a/ecc/operation.tex					\
+	../slides/a/ecc/quadrieren.tex					\
+	../slides/a/ecc/oakley.tex					\
+									\
+	../slides/a/aes/bytes.tex					\
+	../slides/a/aes/sinverse.tex					\
+	../slides/a/aes/blocks.tex					\
+	../slides/a/aes/keys.tex					\
+	../slides/a/aes/runden.tex					\
+									\
+	../slides/a/chapter.tex
+
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
diff --git a/vorlesungen/slides/a/chapter.tex b/vorlesungen/slides/a/chapter.tex
new file mode 100644
index 0000000..78eec84
--- /dev/null
+++ b/vorlesungen/slides/a/chapter.tex
@@ -0,0 +1,23 @@
+%
+% chapter.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswi
+%
+
+\folie{a/dc/prinzip.tex}
+\folie{a/dc/effizient.tex}
+\folie{a/dc/beispiel.tex}
+
+\folie{a/ecc/gruppendh.tex}
+\folie{a/ecc/kurve.tex}
+\folie{a/ecc/inverse.tex}
+\folie{a/ecc/operation.tex}
+\folie{a/ecc/quadrieren.tex}
+\folie{a/ecc/oakley.tex}
+
+\folie{a/aes/bytes.tex}
+\folie{a/aes/sinverse.tex}
+\folie{a/aes/blocks.tex}
+\folie{a/aes/keys.tex}
+\folie{a/aes/runden.tex}
+
diff --git a/vorlesungen/slides/a/dc/beispiel.tex b/vorlesungen/slides/a/dc/beispiel.tex
new file mode 100644
index 0000000..4c99e9e
--- /dev/null
+++ b/vorlesungen/slides/a/dc/beispiel.tex
@@ -0,0 +1,54 @@
+%
+% beispiel.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\def\u#1#2{\uncover<#1->{#2}}
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Beispiel}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Aufgabe}
+Berechne $1291^{17}\in\mathbb{F}_{2027}$
+\end{block}
+\uncover<2->{%
+\begin{block}{Exponent}
+\vspace{-10pt}
+\[
+17 = 2^4 + 1
+=
+\texttt{10001}_2
+=
+\texttt{0x11}
+\]
+\end{block}}
+\end{column}
+\begin{column}{0.48\textwidth}
+\uncover<3->{%
+\begin{block}{Divide-and-Conquor}
+\begin{center}
+\begin{tabular}{|>{$}r<{$}>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
+\hline
+i&2^i&    a^{2^i} &       n &     n_i &                      m \\
+\hline
+0&  1&       1291 &      17 & \u{4}{1}&\u{5}{             1291}\\
+1&  2& \u{6}{ 487}& \u{7}{8}& \u{8}{0}& \u{9}{\color{gray}1291}\\
+2&  4&\u{10}{  10}&\u{11}{4}&\u{12}{0}&\u{13}{\color{gray}1291}\\
+3&  8&\u{14}{ 100}&\u{15}{2}&\u{16}{0}&\u{17}{\color{gray}1291}\\
+4& 16&\u{18}{1892}&\u{19}{1}&\u{20}{1}&\u{21}{              37}\\
+\hline
+\end{tabular}
+\end{center}
+\end{block}}
+\uncover<22->{%
+\begin{block}{Resultat}
+\(1291^{17} \equiv 37\mod 2027\)
+\end{block}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/dc/effizient.tex b/vorlesungen/slides/a/dc/effizient.tex
new file mode 100644
index 0000000..327ee7e
--- /dev/null
+++ b/vorlesungen/slides/a/dc/effizient.tex
@@ -0,0 +1,65 @@
+%
+% effizient.tex -- Effiziente Berechnung der Potenz
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Effiziente Berechnung}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Prinzip}
+\begin{enumerate}
+\item<3-> {\color{red}Bits mit Shift isolieren}
+\item<4-> {\color{blue}Laufend reduzieren}
+\item<5-> {\color{darkgreen}effizient quadrieren}
+\end{enumerate}
+\end{block}
+\end{column}
+\begin{column}{0.48\textwidth}
+\begin{block}{Algorithmus}
+\begin{center}
+\begin{tikzpicture}[>=latex,thick]
+\uncover<3->{
+\fill[color=red!20] (2.3,-2.44) rectangle (3.8,-1.98);
+\fill[color=red!20] (1.45,-3.88) rectangle (3.2,-3.42);
+}
+\uncover<4->{
+\fill[color=blue!20] (2.15,-2.94) rectangle (3.7,-2.48);
+}
+\uncover<5->{
+\fill[color=darkgreen!20] (1.45,-4.37) rectangle (3.8,-3.91);
+}
+\node at (0,0) [below right] {\begin{minipage}{6cm}\obeylines
+{\tt int potenz(int $a$, int $n$) \{}\\
+\hspace*{0.7cm}{\tt int m = 1;}\\
+\hspace*{0.7cm}{\tt int q = $a$;}\\
+\uncover<2->{%
+\hspace*{0.7cm}{\tt while ($n$ > 0) \{}\\
+\uncover<3->{%
+\hspace*{1.4cm}{\tt if (0x1 \& $n$) \{}\\
+\uncover<4->{%
+\hspace*{2.1cm}{\tt m *= q;}\\
+}%
+\hspace*{1.4cm}{\tt \}}\\
+\hspace*{1.4cm}{\tt $n$ >{}>= 1;}\\
+}%
+\uncover<5->{%
+\hspace*{1.4cm}{\tt q = sqr(q);}\\
+}%
+\hspace*{0.7cm}{\tt \}}\\
+}%
+\hspace*{0.7cm}{\tt return m;}\\
+{\tt \}}
+\end{minipage}};
+\end{tikzpicture}
+\end{center}
+\end{block}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/dc/naiv.txt b/vorlesungen/slides/a/dc/naiv.txt
new file mode 100644
index 0000000..bf5569d
--- /dev/null
+++ b/vorlesungen/slides/a/dc/naiv.txt
@@ -0,0 +1,2 @@
+int m = 1, i = 0;
+while (i++ < n) { m *= a; }
diff --git a/vorlesungen/slides/a/dc/prinzip.tex b/vorlesungen/slides/a/dc/prinzip.tex
new file mode 100644
index 0000000..c75af61
--- /dev/null
+++ b/vorlesungen/slides/a/dc/prinzip.tex
@@ -0,0 +1,86 @@
+%
+% prinzip.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Potenzieren $\mod p$}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Aufgabe}
+Berechne $a^n\in\mathbb{F}_p$ für grosses $n$
+\end{block}
+\uncover<2->{%
+\begin{block}{Mengengerüst}
+\(
+\log_2 n > 2000
+\)
+\\
+\uncover<3->{%
+RSA mit $N=pq$: Exponenten sind $e,d$, $e$ klein, aber 
+\(
+ed\equiv 1 \mod \varphi(N)
+\)}
+\end{block}}
+\uncover<4->{%
+\begin{block}{Naive Idee}
+\verbatiminput{../slides/a/dc/naiv.txt}
+Laufzeit: $O(n) \uncover<5->{= O(2^{\log_2n})}$%
+\uncover<5->{, d.~h.~exponentiell in der Bitlänge von $n$}
+\end{block}}
+\end{column}
+\begin{column}{0.48\textwidth}
+\uncover<6->{%
+\begin{block}{Idee 1: Exponent binär schreiben}
+\vspace{-12pt}
+\[
+n = n_k2^k + n_{k-1}2^{k-1} + \dots  +n_12^1 + n_02^0
+\]
+\end{block}}
+\vspace{-5pt}
+\uncover<7->{%
+\begin{block}{Idee 2: Potenzgesetze}
+\vspace{-12pt}
+\[
+a^n
+=
+a^{n_k2^k}
+a^{n_{k-1}2^k}
+\dots
+a^{n_12^1}
+a^{n_02^0}
+\uncover<8->{=
+\prod_{n_i = 1}
+a^{2^i}}
+\]
+\end{block}}
+\vspace{-15pt}
+\uncover<9->{%
+\begin{block}{Idee 3: Quadrieren}
+\vspace{-10pt}
+\begin{align*}
+a^{2^i}
+&=
+a^{2\cdot 2^{i-1}}
+\uncover<10->{=
+(a^{2^{i-1}})^2}
+\\
+&\uncover<11->{=
+(\dots(a\underbrace{\mathstrut^2)^2\dots)^2}_{\displaystyle i}}
+\end{align*}
+\end{block}}
+\vspace{-18pt}
+\uncover<12->{%
+\begin{block}{Laufzeit}
+Multiplikationen: $\le 2 \cdot(\log_2(n) - 1)$
+\\
+\uncover<13->{Worst case Laufzeit: $O(\log_2 n)$}
+\end{block}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/ecc/gruppendh.tex b/vorlesungen/slides/a/ecc/gruppendh.tex
new file mode 100644
index 0000000..13d85c8
--- /dev/null
+++ b/vorlesungen/slides/a/ecc/gruppendh.tex
@@ -0,0 +1,51 @@
+%
+% template.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Diffie-Hellmann verallgemeinern}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{block}{Diffie-Hellman in $\mathbb{F}_p$\strut}
+\begin{enumerate}
+\item<2-> Parteien einigen sich auf $g\in \mathbb{F}_p$, $g\ne 0$, $g\ne 1$
+\item<3-> $A$ und $B$ wählen Exponenten $a,b\in \mathbb{N}$
+\item<4-> Parteien tauschen $u=g^a$ und $v=g^b$ aus
+\item<5-> Parteien berechnen $v^a$ und $u^b$
+\[
+v^a = (g^b)^a = g^{ab} =(g^a)^b = u^b
+\]
+gemeinsamer privater Schlüssel
+\end{enumerate}
+\end{block}
+\uncover<11->{%
+{\usebeamercolor[fg]{title}Spezialfall:} $G=\mathbb{F}_p^*$
+}
+\end{column}
+\begin{column}{0.48\textwidth}
+\uncover<6->{%
+\begin{block}{Diffie-Hellmann in $G$\strut}
+\begin{enumerate}
+\item<7-> Parteien einigen sich auf $g\in G$, $g\ne e$
+\item<8-> $A$ und $B$ wählen Exponenten $a,b\in \mathbb{N}$
+\item<9-> Parteien tauschen $u=g^a$ und $v=g^b$ aus
+\item<10-> Parteien berechnen $v^a$ und $u^b$
+\[
+v^a = (g^b)^a = g^{ab} =(g^a)^b = u^b
+\]
+gemeinsamer privater Schlüssel
+\end{enumerate}
+\end{block}}
+\uncover<12->{%
+{\usebeamercolor[fg]{title}Idee:} Wähle effizient zu berechnende, ``grosse''
+Gruppen, mit ``komplizierter'' Multiplikation
+}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/ecc/inverse.tex b/vorlesungen/slides/a/ecc/inverse.tex
new file mode 100644
index 0000000..c50f698
--- /dev/null
+++ b/vorlesungen/slides/a/ecc/inverse.tex
@@ -0,0 +1,48 @@
+%
+% inverse.tex -- slide template
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Involution/Inverse}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{center}
+\includegraphics[width=\textwidth]{../../buch/chapters/90-crypto/images/elliptic.pdf}
+\end{center}
+\end{column}
+\begin{column}{0.48\textwidth}
+\begin{block}{In speziellen Koordinaten}
+\vspace{-12pt}
+\[
+v^2 = u^3+Au+B
+\]
+\uncover<2->{invariant unter $v\mapsto -v$}%
+\\
+\uncover<3->{{\color{red}geht nicht in $\mathbb{F}_2$}}
+\end{block}
+\uncover<4->{%
+\begin{block}{Allgemein}
+\vspace{-12pt}
+\begin{align*}
+Y^2+XY &= X^3 + aX+b
+\\
+\uncover<5->{%
+Y(Y+X) &= X^3 + aX + b}
+\end{align*}
+\uncover<6->{invariant unter}
+\begin{align*}
+\uncover<7->{X&\mapsto X,& Y&\mapsto -X-Y}
+\\
+\uncover<8->{&&\Rightarrow X+Y&\mapsto -Y}
+\end{align*}
+\uncover<9->{Spezialfall $\mathbb{F}_2$: $Y\leftrightarrow X+Y$}
+\end{block}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/ecc/kurve.tex b/vorlesungen/slides/a/ecc/kurve.tex
new file mode 100644
index 0000000..04d15f8
--- /dev/null
+++ b/vorlesungen/slides/a/ecc/kurve.tex
@@ -0,0 +1,56 @@
+%
+% kurve.tex -- elliptische Kurven
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Elliptische Kurven}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.48\textwidth}
+\begin{center}
+\uncover<5->{%
+\includegraphics[width=\textwidth]{../../buch/chapters/90-crypto/images/elliptic.pdf}
+}
+\end{center}
+\end{column}
+\begin{column}{0.48\textwidth}
+\begin{block}{Allgemein}
+mit $a,b\in\Bbbk$
+\[
+Y^2 + XY = X^3 + aX + b
+\]
+\end{block}
+\vspace{-10pt}
+\uncover<2->{%
+\begin{block}{Spezielle Parametrisierung}
+\vspace{-10pt}
+\begin{align*}
+Y^2 + XY + \frac14X^2
+&=
+X^3 + \frac14X^2 + aX + b
+\\
+\uncover<3->{
+(Y+\frac12X)^2
+&=
+X^3 + \frac14X^2 + aX + b
+}\\
+\uncover<4->{
+v^2
+&=
+u^3+Au+B}
+\end{align*}
+\uncover<4->{mit
+\[
+v=Y+{\textstyle\frac12}X,
+\qquad
+u=X-\frac1{12}
+\]}
+\end{block}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/ecc/oakley.tex b/vorlesungen/slides/a/ecc/oakley.tex
new file mode 100644
index 0000000..6980c10
--- /dev/null
+++ b/vorlesungen/slides/a/ecc/oakley.tex
@@ -0,0 +1,85 @@
+%
+% oakley.tex -- Oakley Gruppen
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Oakley-Gruppen}
+\only<1>{%
+\small
+\verbatiminput{../slides/a/ecc/oakley1.txt}
+$\approx 1.55252\cdot 10^{231}$
+}
+\only<2>{%
+\begin{block}{$\mathbb{F}_p$}
+Endlicher Körper mit $p = $
+\verbatiminput{../slides/a/ecc/prime1.txt}
+\end{block}
+}
+\only<3>{%
+\small
+\verbatiminput{../slides/a/ecc/oakley2.txt}
+}
+\only<4>{%
+\begin{block}{$\mathbb{F}_p$}
+Endlicher Körper mit $p = $
+\verbatiminput{../slides/a/ecc/prime2.txt}
+$\approx 1.7977\cdot 10^{308}$
+\end{block}
+}
+\only<5>{%
+\small
+\verbatiminput{../slides/a/ecc/oakley3.txt}
+}
+\only<6>{%
+\begin{block}{Oakley Gruppe 3}
+\begin{align*}
+m(x) &= x^{155} + x^{62} + 1
+\\
+a    &= 0
+\\
+b    &= \texttt{0x07338f}
+\\
+g_x  &= 0x7b = x^6 + x^5 + x^4 + x^3 + x + 1
+\\
+&=
+x^{18}+x^{17}+x^{16}
++
+x^{13}+x^{12}
++
+x^{9}+x^{8}+x^{7}
++
+x^{3}+x^{1}+x^{1}+1
+\\
+|G|&=45671926166590716193865565914344635196769237316 = 4.5672\cdot 10^{46}
+\\
+\log_2|G|&=155\,\text{bit}
+\end{align*}
+\end{block}}
+\only<7>{%
+\small
+\verbatiminput{../slides/a/ecc/oakley4.txt}
+}
+\only<8>{%
+\begin{block}{Oakley Gruppe 4}
+\begin{align*}
+m(x) &= x^{185} + x^{69} + 1
+\\
+a    &= 0
+\\
+b    &= \texttt{0x1ee9} = x^{12} + x^{11}+x^{10}+x^9 + x^7+x^6+x^5 + x^3+1
+\\
+g_x  &= \texttt{0x18} = x^4+x^3
+\\
+|G| &= 49039857307708443467467104857652682248052385001045053116
+\\
+&= 4.9040\cdot 10^{55}
+\\
+\log_2|G| &= 185
+\end{align*}
+\end{block}}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/ecc/oakley1.txt b/vorlesungen/slides/a/ecc/oakley1.txt
new file mode 100644
index 0000000..4cc31ae
--- /dev/null
+++ b/vorlesungen/slides/a/ecc/oakley1.txt
@@ -0,0 +1,14 @@
+6.1 First Oakley Default Group
+
+   Oakley implementations MUST support a MODP group with the following
+   prime and generator. This group is assigned id 1 (one).
+
+      The prime is: 2^768 - 2 ^704 - 1 + 2^64 * { [2^638 pi] + 149686 }
+      Its hexadecimal value is
+
+         FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
+         29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
+         EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
+         E485B576 625E7EC6 F44C42E9 A63A3620 FFFFFFFF FFFFFFFF
+
+      The generator is: 2.
diff --git a/vorlesungen/slides/a/ecc/oakley2.txt b/vorlesungen/slides/a/ecc/oakley2.txt
new file mode 100644
index 0000000..ddb2d2a
--- /dev/null
+++ b/vorlesungen/slides/a/ecc/oakley2.txt
@@ -0,0 +1,16 @@
+6.2 Second Oakley Group
+
+   IKE implementations SHOULD support a MODP group with the following
+   prime and generator. This group is assigned id 2 (two).
+
+   The prime is 2^1024 - 2^960 - 1 + 2^64 * { [2^894 pi] + 129093 }.
+   Its hexadecimal value is
+
+         FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1
+         29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD
+         EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245
+         E485B576 625E7EC6 F44C42E9 A637ED6B 0BFF5CB6 F406B7ED
+         EE386BFB 5A899FA5 AE9F2411 7C4B1FE6 49286651 ECE65381
+         FFFFFFFF FFFFFFFF
+
+   The generator is 2 (decimal)
diff --git a/vorlesungen/slides/a/ecc/oakley3.txt b/vorlesungen/slides/a/ecc/oakley3.txt
new file mode 100644
index 0000000..ab2c78f
--- /dev/null
+++ b/vorlesungen/slides/a/ecc/oakley3.txt
@@ -0,0 +1,17 @@
+6.3 Third Oakley Group
+
+   IKE implementations SHOULD support a EC2N group with the following
+   characteristics. This group is assigned id 3 (three). The curve is
+   based on the Galois Field GF[2^155]. The field size is 155. The
+   irreducible polynomial for the field is:
+          u^155 + u^62 + 1.
+   The equation for the elliptic curve is:
+           y^2 + xy = x^3 + ax^2 + b.
+
+   Field Size:                         155
+   Group Prime/Irreducible Polynomial:
+                    0x0800000000000000000000004000000000000001
+   Group Generator One:                0x7b
+   Group Curve A:                      0x0
+   Group Curve B:                      0x07338f
+   Group Order: 0X0800000000000000000057db5698537193aef944
diff --git a/vorlesungen/slides/a/ecc/oakley4.txt b/vorlesungen/slides/a/ecc/oakley4.txt
new file mode 100644
index 0000000..3ec20cc
--- /dev/null
+++ b/vorlesungen/slides/a/ecc/oakley4.txt
@@ -0,0 +1,17 @@
+6.4 Fourth Oakley Group
+
+   IKE implementations SHOULD support a EC2N group with the following
+   characteristics. This group is assigned id 4 (four). The curve is
+   based on the Galois Field GF[2^185]. The field size is 185. The
+   irreducible polynomial for the field is:
+           u^185 + u^69 + 1. The
+   equation for the elliptic curve is:
+           y^2 + xy = x^3 + ax^2 + b.
+
+   Field Size:                         185
+   Group Prime/Irreducible Polynomial:
+                    0x020000000000000000000000000000200000000000000001
+   Group Generator One:                0x18
+   Group Curve A:                      0x0
+   Group Curve B:                      0x1ee9
+   Group Order: 0X01ffffffffffffffffffffffdbf2f889b73e484175f94ebc
diff --git a/vorlesungen/slides/a/ecc/operation.tex b/vorlesungen/slides/a/ecc/operation.tex
new file mode 100644
index 0000000..61ef95d
--- /dev/null
+++ b/vorlesungen/slides/a/ecc/operation.tex
@@ -0,0 +1,68 @@
+%
+% operation.tex -- Gruppen-Operation auf einer elliptischen Kurve
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Gruppenoperation}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.40\textwidth}
+\begin{center}
+\includegraphics[width=\textwidth]{../../buch/chapters/90-crypto/images/elliptic.pdf}
+\end{center}
+\vspace{-23pt}
+\uncover<8->{%
+\begin{block}{Verifizieren}
+\begin{enumerate}
+\item<9-> Assoziativ?
+\item<10-> Neutrales Element $\mathstrut=\infty$
+\item<11-> Involution = Inverse?
+\end{enumerate}
+\end{block}}
+\end{column}
+\begin{column}{0.56\textwidth}
+\begin{block}{Gerade}
+$g_1,g_2\in G$, $t\in \Bbbk$
+\begin{align*}
+g(t)
+&=
+tg_1+(1-t)g_2
+\\
+\uncover<2->{
+\begin{pmatrix}X(t)\\Y(t)\end{pmatrix}
+&=
+t\begin{pmatrix}x_1\\y_1\end{pmatrix}
++
+(1-t)\begin{pmatrix}x_2\\y_2\end{pmatrix}
+\in\Bbbk^2
+}
+\end{align*}
+\end{block}
+\vspace{-13pt}
+\uncover<3->{%
+\begin{block}{3. Schnittpunkt}
+$g(t)$ einsetzen in die elliptische Kurve
+\[
+p(t)
+=
+Y(t)^2+X(t)Y(t)-X(t)^3-aX(t)-b=0
+\]
+\vspace{-12pt}
+\begin{enumerate}
+\item<4->
+kubisches Polynom mit Nullstellen $t=0,1$
+\item<5->
+$p(t) $ ist durch $t(t-1)$ teilbar
+\item<6->
+$p(t) = t(t-1)(Jt+K)=0
+\uncover<7->{\Rightarrow t=-K/J$}
+\end{enumerate}
+\end{block}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup
diff --git a/vorlesungen/slides/a/ecc/prime1.txt b/vorlesungen/slides/a/ecc/prime1.txt
new file mode 100644
index 0000000..eb4515d
--- /dev/null
+++ b/vorlesungen/slides/a/ecc/prime1.txt
@@ -0,0 +1,5 @@
+                     15 52518 09230 07089 35130 91813 12584
+81755 63133 40494 34514 31320 23511 94902 96623 99491 02107
+25866 94538 76591 64244 29100 07680 28886 42291 50803 71891
+80463 42632 72761 30312 82983 74438 08208 90196 28850 91706
+91316 59317 53674 69551 76311 98433 71637 22100 72105 77919
diff --git a/vorlesungen/slides/a/ecc/prime2.txt b/vorlesungen/slides/a/ecc/prime2.txt
new file mode 100644
index 0000000..13458fb
--- /dev/null
+++ b/vorlesungen/slides/a/ecc/prime2.txt
@@ -0,0 +1,8 @@
+                                                 1797 69313
+48623 15907 70839 15679 37874 53197 86029 60487 56011 70644
+44236 84197 18021 61585 19368 94783 37958 64925 54150 21805
+65485 98050 36464 40548 19923 91000 50792 87700 33558 16639
+22955 31362 39076 50873 57599 14822 57486 25750 07425 30207
+74477 12589 55095 79377 78424 44242 66173 34727 62929 93876
+68709 20560 60502 70810 84290 76929 32019 12819 44676 27007
+
diff --git a/vorlesungen/slides/a/ecc/primes b/vorlesungen/slides/a/ecc/primes
new file mode 100644
index 0000000..3feea29
--- /dev/null
+++ b/vorlesungen/slides/a/ecc/primes
@@ -0,0 +1,13 @@
+#! /bin/bash
+#
+# primes
+# 
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+bc <<EOF
+ibase=16
+FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A63A3620FFFFFFFFFFFFFFFF
+
+FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFFFFFFFFFF
+
+EOF
diff --git a/vorlesungen/slides/a/ecc/quadrieren.tex b/vorlesungen/slides/a/ecc/quadrieren.tex
new file mode 100644
index 0000000..942c73b
--- /dev/null
+++ b/vorlesungen/slides/a/ecc/quadrieren.tex
@@ -0,0 +1,59 @@
+%
+% quadrieren.tex -- Quadrieren 
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\bgroup
+\begin{frame}[t]
+\setlength{\abovedisplayskip}{5pt}
+\setlength{\belowdisplayskip}{5pt}
+\frametitle{Quadrieren}
+\vspace{-20pt}
+\begin{columns}[t,onlytextwidth]
+\begin{column}{0.40\textwidth}
+\begin{block}{Problem}
+\( g = g_1 = g_2 \)
+$\Rightarrow$
+Tangente
+\\
+\uncover<2->{{\color{red}ohne Analysis!}}
+\end{block}
+\begin{center}
+\includegraphics[width=\textwidth]{../../buch/chapters/90-crypto/images/elliptic.pdf}
+\end{center}
+\end{column}
+\begin{column}{0.56\textwidth}
+\uncover<3->{%
+\begin{block}{Lösung}
+Finde $h\in G$ derart, dass 
+\begin{align*}
+g(t)
+&=
+tg + (1-t)h
+\\
+\uncover<4->{%
+\begin{pmatrix}X(t)\\Y(t)\end{pmatrix}
+&=
+t\begin{pmatrix}x_g\\y_g\end{pmatrix}
++(1-t) \begin{pmatrix}x_h\\y_h\end{pmatrix}
+}
+\end{align*}
+\uncover<5->{eingesetzt
+\[
+p(t)
+=
+Y(t)^2+X(t)Y(t)-X(t)^3-aX(t)-b
+=
+0
+\]}%
+\uncover<6->{%
+Nullstellen $0$ (doppelt) und $1$ hat:}
+\[
+\uncover<7->{p(t) = c(t^3-t)}
+\]
+\uncover<8->{Koeffizientenvergleich: einfachere Gleichungen für $x_h$ und $y_h$}
+\end{block}}
+\end{column}
+\end{columns}
+\end{frame}
+\egroup