aboutsummaryrefslogtreecommitdiffstats
path: root/vorlesungen
diff options
context:
space:
mode:
authorRoy Seitz <roy.seitz@ost.ch>2021-04-15 17:46:16 +0200
committerRoy Seitz <roy.seitz@ost.ch>2021-04-15 17:46:16 +0200
commita0efb46dd0415f3131021cc825ae4f6bf7172b12 (patch)
tree68e0bdbc652f89d765498495b4615c926b45ec85 /vorlesungen
parentSkalar-zu-Matrix DGL Folie. (diff)
parentadd oakley groups (diff)
downloadSeminarMatrizen-a0efb46dd0415f3131021cc825ae4f6bf7172b12.tar.gz
SeminarMatrizen-a0efb46dd0415f3131021cc825ae4f6bf7172b12.zip
Merge branch 'master' of github.com:AndreasFMueller/SeminarMatrizen
Diffstat (limited to '')
-rw-r--r--vorlesungen/07_msecrypto/Makefile33
-rw-r--r--vorlesungen/07_msecrypto/MathSemMSE-07-crypto.tex14
-rw-r--r--vorlesungen/07_msecrypto/common.tex16
-rw-r--r--vorlesungen/07_msecrypto/crypto-handout.tex11
-rw-r--r--vorlesungen/07_msecrypto/slides.tex40
-rw-r--r--vorlesungen/slides/Makefile.inc3
-rw-r--r--vorlesungen/slides/a/Makefile.inc19
-rw-r--r--vorlesungen/slides/a/chapter.tex17
-rw-r--r--vorlesungen/slides/a/dc/beispiel.tex54
-rw-r--r--vorlesungen/slides/a/dc/effizient.tex65
-rw-r--r--vorlesungen/slides/a/dc/naiv.txt2
-rw-r--r--vorlesungen/slides/a/dc/prinzip.tex86
-rw-r--r--vorlesungen/slides/a/ecc/gruppendh.tex51
-rw-r--r--vorlesungen/slides/a/ecc/inverse.tex48
-rw-r--r--vorlesungen/slides/a/ecc/kurve.tex56
-rw-r--r--vorlesungen/slides/a/ecc/oakley.tex85
-rw-r--r--vorlesungen/slides/a/ecc/oakley1.txt14
-rw-r--r--vorlesungen/slides/a/ecc/oakley2.txt16
-rw-r--r--vorlesungen/slides/a/ecc/oakley3.txt17
-rw-r--r--vorlesungen/slides/a/ecc/oakley4.txt17
-rw-r--r--vorlesungen/slides/a/ecc/operation.tex68
-rw-r--r--vorlesungen/slides/a/ecc/prime1.txt5
-rw-r--r--vorlesungen/slides/a/ecc/prime2.txt8
-rw-r--r--vorlesungen/slides/a/ecc/primes13
-rw-r--r--vorlesungen/slides/a/ecc/quadrieren.tex59
-rw-r--r--vorlesungen/slides/test.tex43
26 files changed, 829 insertions, 31 deletions
diff --git a/vorlesungen/07_msecrypto/Makefile b/vorlesungen/07_msecrypto/Makefile
new file mode 100644
index 0000000..5d4ecd0
--- /dev/null
+++ b/vorlesungen/07_msecrypto/Makefile
@@ -0,0 +1,33 @@
+#
+# Makefile -- crypto
+#
+# (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil
+#
+all: crypto-handout.pdf MathSemMSE-07-crypto.pdf
+
+include ../slides/Makefile.inc
+
+SOURCES = common.tex slides.tex $(slides)
+
+MathSemMSE-07-crypto.pdf: MathSemMSE-07-crypto.tex $(SOURCES)
+ pdflatex MathSemMSE-07-crypto.tex
+
+crypto-handout.pdf: crypto-handout.tex $(SOURCES)
+ pdflatex crypto-handout.tex
+
+thumbnail: thumbnail.jpg # fix1.jpg
+
+thumbnail.pdf: MathSemMSE-07-crypto.pdf
+ pdfjam --outfile thumbnail.pdf --papersize '{16cm,9cm}' \
+ MathSemMSE-07-crypto.pdf 1
+thumbnail.jpg: thumbnail.pdf
+ convert -density 300 thumbnail.pdf \
+ -resize 1920x1080 -units PixelsPerInch thumbnail.jpg
+
+fix1.pdf: MathSemMSE-07-crypto.pdf
+ pdfjam --outfile fix1.pdf --papersize '{16cm,9cm}' \
+ MathSemMSE-07-crypto.pdf 1
+fix1.jpg: fix1.pdf
+ convert -density 300 fix1.pdf \
+ -resize 1920x1080 -units PixelsPerInch fix1.jpg
+
diff --git a/vorlesungen/07_msecrypto/MathSemMSE-07-crypto.tex b/vorlesungen/07_msecrypto/MathSemMSE-07-crypto.tex
new file mode 100644
index 0000000..179837b
--- /dev/null
+++ b/vorlesungen/07_msecrypto/MathSemMSE-07-crypto.tex
@@ -0,0 +1,14 @@
+%
+% MathSem-07-msecrypto.tex -- Präsentation
+%
+% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\documentclass[aspectratio=169]{beamer}
+\input{common.tex}
+\setboolean{presentation}{true}
+\begin{document}
+\begin{frame}
+\titlepage
+\end{frame}
+\input{slides.tex}
+\end{document}
diff --git a/vorlesungen/07_msecrypto/common.tex b/vorlesungen/07_msecrypto/common.tex
new file mode 100644
index 0000000..0700acf
--- /dev/null
+++ b/vorlesungen/07_msecrypto/common.tex
@@ -0,0 +1,16 @@
+%
+% common.tex -- gemeinsame definition
+%
+% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\input{../common/packages.tex}
+\input{../common/common.tex}
+\mode<beamer>{%
+\usetheme[hideothersubsections,hidetitle]{Hannover}
+}
+\beamertemplatenavigationsymbolsempty
+\title[Titel]{Titel}
+\author[A.~Müller]{Prof. Dr. Andreas Müller}
+\date[]{}
+\newboolean{presentation}
+
diff --git a/vorlesungen/07_msecrypto/crypto-handout.tex b/vorlesungen/07_msecrypto/crypto-handout.tex
new file mode 100644
index 0000000..d42a260
--- /dev/null
+++ b/vorlesungen/07_msecrypto/crypto-handout.tex
@@ -0,0 +1,11 @@
+%
+% msecrypto-handout.tex -- Handout XXX
+%
+% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\documentclass[handout,aspectratio=169]{beamer}
+\input{common.tex}
+\setboolean{presentation}{false}
+\begin{document}
+\input{slides.tex}
+\end{document}
diff --git a/vorlesungen/07_msecrypto/slides.tex b/vorlesungen/07_msecrypto/slides.tex
new file mode 100644
index 0000000..0f62d18
--- /dev/null
+++ b/vorlesungen/07_msecrypto/slides.tex
@@ -0,0 +1,40 @@
+%
+% slides.tex -- Präsentation zur Kryptographie
+%
+% (c) 2017 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Diffie-Hellmann}
+\folie{4/dh.tex}
+
+\section{Divide and Conquer}
+% Potenzieren
+\folie{a/dc/prinzip.tex}
+% effiziente Durchführung
+\folie{a/dc/effizient.tex}
+% Beispieldurchführung
+\folie{a/dc/beispiel.tex}
+
+\section{Elliptische Kurven}
+% Idee
+\folie{a/ecc/gruppendh.tex}
+% Was ist eine elliptische Kurve (char 0 Bild)
+\folie{a/ecc/kurve.tex}
+% Involution/Inverse
+\folie{a/ecc/inverse.tex}
+% Verknüpfung
+\folie{a/ecc/operation.tex}
+% Quadrieren
+\folie{a/ecc/quadrieren.tex}
+% XXX Oakley Gruppe
+%\folie{a/ecc/oakley.tex}
+
+\section{AES}
+% XXX Byte-Operationen
+%\folie{a/aes/bytes.tex}
+% XXX Block-Operationen
+%\folie{a/aes/blocks.tex}
+% XXX Key-Schedule
+%\folie{a/aes/keys.tex}
+% XXX Zusammensetzung
+%\folie{a/aes/runden.tex}
+
diff --git a/vorlesungen/slides/Makefile.inc b/vorlesungen/slides/Makefile.inc
index e2271b8..0f5fa8c 100644
--- a/vorlesungen/slides/Makefile.inc
+++ b/vorlesungen/slides/Makefile.inc
@@ -12,7 +12,8 @@ include ../slides/5/Makefile.inc
include ../slides/7/Makefile.inc
include ../slides/8/Makefile.inc
include ../slides/9/Makefile.inc
+include ../slides/a/Makefile.inc
slides = \
$(chapter0) $(chapter1) $(chapter2) $(chapter3) $(chapter4) \
- $(chapter5) $(chapter7) $(chapter8) $(chapter9)
+ $(chapter5) $(chapter7) $(chapter8) $(chapter9) $(chaptera)
diff --git a/vorlesungen/slides/a/Makefile.inc b/vorlesungen/slides/a/Makefile.inc
new file mode 100644
index 0000000..9dba93f
--- /dev/null
+++ b/vorlesungen/slides/a/Makefile.inc
@@ -0,0 +1,19 @@
+#
+# 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/chapter.tex
+
diff --git a/vorlesungen/slides/a/chapter.tex b/vorlesungen/slides/a/chapter.tex
new file mode 100644
index 0000000..84ee609
--- /dev/null
+++ b/vorlesungen/slides/a/chapter.tex
@@ -0,0 +1,17 @@
+%
+% 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}
+
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..9cf1aa2
--- /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{Kubische 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
diff --git a/vorlesungen/slides/test.tex b/vorlesungen/slides/test.tex
index 4673f76..bc1744b 100644
--- a/vorlesungen/slides/test.tex
+++ b/vorlesungen/slides/test.tex
@@ -4,36 +4,19 @@
% (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswil
%
-\section{Matrizen-Gruppen}
-% Was sind Symmetrien
-%\folie{7/symmetrien.tex}
-% Algebraische Bedingungen für Matrixgruppen
-%\folie{7/algebraisch.tex}
-% Parametrisierung, Beispiel SO(3)
-%\folie{7/parameter.tex}
-% Mannigfaltigkeiten
-%\folie{7/mannigfaltigkeit.tex}
-% Weitere Beispiele
-% SL_2(R)
-%\folie{7/sl2.tex}
-\folie{7/drehung.tex}
-%\folie{7/drehanim.tex}
-% Semidirekte Produkte SO(2) x R^2, R^+ x R
-%\folie{7/semi.tex}
+%\folie{a/dc/prinzip.tex}
+%\folie{a/dc/effizient.tex}
+%\folie{a/dc/beispiel.tex}
-\section{Ableitungen}
-% Kurven in einer Gruppe
-%\folie{7/kurven.tex}
-% Einparameter-Gruppen
-%\folie{7/einparameter.tex}
-% Ableitung einer Einparameter-Gruppe
-%\folie{7/ableitung.tex}
-% Lie-Algebra
-%\folie{7/liealgebra.tex}
-% Kommutator
-%\folie{7/kommutator.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}
-\section{Exponentialabbildung}
-% Differentialgleichung für die Exponentialabbildung
-%\folie{7/dg.tex}
+%\folie{a/aes/bytes.tex}
+%\folie{a/aes/blockes.tex}
+%\folie{a/aes/kays.tex}
+%\folie{a/aes/runden.tex}