diff options
Diffstat (limited to 'vorlesungen/slides/a')
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 |