Merge remote-tracking branch 'upstream/master'

13 files changed, 457 insertions, 0 deletions

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