new stuff

5 files changed, 314 insertions, 0 deletions

diff --git a/buch/chapters/90-crypto/aes.tex b/buch/chapters/90-crypto/aes.tex
index d392761..6004dde 100644
--- a/buch/chapters/90-crypto/aes.tex
+++ b/buch/chapters/90-crypto/aes.tex
@@ -6,4 +6,30 @@
 \section{Advanced Encryption Standard -- AES
 \label{buch:section:aes}}
 \rhead{Advanced Encryption Standard}
+Eine wichtige Forderung bei der Konzeption des damals neuen
+Advanced Encryption Standard war, dass darin keine ``willkürlich''
+erscheinenden Operationen geben darf, bei denen der Verdacht
+entstehen könnte, dass sich dahinter noch offengelegtes Wissen
+über einen möglichen Angriff auf den Verschlüsselungsalgorithmus
+verbergen könnte.
+Dies war eine Schwäche des vor AES üblichen DES Verschlüsselungsalgorithmus.
+In seiner Definition kommt eine Reihe von Konstanten vor, über deren
+Herkunft nichts bekannt war.
+Die Gerüchteküche wollte wissen, dass die NSA die Konstanten aus dem
+ursprünglichen Vorschlag abgeändert habe, und dass dies geschehen sei,
+um den Algorithmus durch die NSA angreifbar zu machen.
+
+Eine weiter Forderung war, dass die Sicherheit des neuen
+Verschlüsselungsstandards ``skalierbar'' sein soll, dass man also
+die Schlüssellänge mit der Zeit von 128~Bit auf 196 oder sogar 256~Bit
+steigern kann.
+Der Standard wird dadurch langlebiger und gleichzeitig entsteht die
+Möglichkeit, Sicherheit gegen Rechenleistung einzutauschen.
+Weniger leistungsfähige Systeme können den Algorithmus immer noch
+nutzen, entweder mit geringerer Verschlüsselungsrate oder geringerer
+Sicherheit.
+
+In diesem Abschnitt soll gezeigt werde, wie sich die AES
+spezifizierten Operationen als mit der Arithmetik der
+endlichen Körper beschreiben lassen.
 
diff --git a/buch/chapters/90-crypto/chapter.tex b/buch/chapters/90-crypto/chapter.tex
index 92bb09b..829169f 100644
--- a/buch/chapters/90-crypto/chapter.tex
+++ b/buch/chapters/90-crypto/chapter.tex
@@ -8,7 +8,22 @@
 \label{buch:chapter:kryptographie}}
 \lhead{Kryptographie und Codierungstheorie}
 \rhead{}
+Die algebraische Theorie der endlichen Körper hat sich als besonders
+nützliche herausgestellt in der Krypographie.
+Die Eigenschaften dieser Körper sind reichhaltig genug, um 
+kryptographsch widerstandsfähige Algorithmen zu liefern, die
+auch in ihrer Stärke beliebig skaliert werden können.
+Gleichzeitig liefert die Algebra auch eine effiziente Implementierung.
+In diesem Abschnitt soll dies an einigen Beispielen gezeigt werden.
 
 \input{chapters/90-crypto/ff.tex}
 \input{chapters/90-crypto/aes.tex}
 \input{chapters/90-crypto/rs.tex}
+
+\section*{Übungsaufgaben}
+\rhead{Übungsaufgaben}
+\aufgabetoplevel{chapters/90-crypto/uebungsaufgaben}
+\begin{uebungsaufgaben}
+\uebungsaufgabe{9001}
+\end{uebungsaufgaben}
+
diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex
index ccaef63..f05dd20 100644
--- a/buch/chapters/90-crypto/ff.tex
+++ b/buch/chapters/90-crypto/ff.tex
@@ -7,3 +7,212 @@
 \section{Kryptographie und endliche Körper
 \label{buch:section:kryptographie-und-endliche-koerper}}
 \rhead{Kryptographie und endliche Körper}
+
+\subsection{Potenzen in $\mathbb{F}_p$ und diskreter Logarithmus
+\label{buch:subsection:potenzen-diskreter-logarithmus}}
+Für kryptographische Anwendungen wird eine einfach zu berechnende
+Funktion benötigt,
+die ohne zusätzliches Wissen, üblicherweise der Schlüssel genannt,
+nicht ohne weiteres umkehrbar ist.
+Die arithmetischen Operationen in einem endlichen Körper sind
+mit geringem Aufwand durchführbar.
+Für die ``schwierigste'' Operation, die Division, steht der
+euklidische Algorithmus zur Verfügung.
+
+Die nächstschwierigere Operation ist die Potenzfunktion.
+Für $g\in \Bbbk$ und $a\in\mathbb{N}$ ist die Potenz $g^a\in\Bbbk$
+natürlich durch die wiederholte Multiplikation definiert.
+In der Praxis werden aber $g$ und $a$ Zahlen mit vielen Binärstellen
+sein, die die wiederholte Multiplikation ist daher sicher nicht
+effizient, das Kriterium der einfachen Berechenbarkeit scheint
+also nicht erfüllt.
+Der folgende Algorithmus berechnet die Potenz in $O(\log_2 a$
+Multiplikationen.
+
+\begin{algorithmus}[Divide-and-conquer]
+\label{buch:crypto:algo:divide-and-conquer}
+Sei $a=a_0 + a_12^1 + a_22^2 + \dots + a_k2^k$ die Binärdarstellung
+der Zahl $a$.
+\begin{enumerate}
+\item setze $f=g$, $x=1$, $i=0$
+\label{divide-and-conquer-1}
+\item solange $i\ge k$ ist, führe aus
+\label{divide-and-conquer-2}
+\begin{enumerate}
+\item
+\label{divide-and-conquer-3}
+falls $a_i=1$ setze $x \coloneqq x \cdot f$
+\item
+\label{divide-and-conquer-4}
+$i \coloneqq i+1$ und $f\coloneqq f\cdot f$
+\end{enumerate}
+\end{enumerate}
+Die Potenz $x=g^a$ kann so in $O(\log_2a)$ Multiplikationen
+berechnet werden.
+\end{algorithmus}
+
+\begin{proof}[Beweis]
+Die Initalisierung in Schritt~\ref{divide-and-conquer-1} stellt sicher,
+dass $x$ den Wert $g^0$ hat. 
+Schritt~\ref{divide-and-conquer-4} stellt sicher,
+dass die Variable $f$ immer den Wert $g^{2^i}$ hat.
+Im Schritt~\ref{divide-and-conquer-3} wird zu $x$ die Potenz
+$g^{a_i2^i}$ hinzumultipliziert.
+Am Ende des Algorithmus hat daher $x$ den Wert
+\[
+x = g^{a_02^0} \cdot g^{a_12^1} \cdot g^{a_22^2} \cdot\ldots\cdot 2^{a_k2^k}
+=
+g^{a_0+a_12+a_22^2+\dots+a_k2^k}
+=
+g^a.
+\]
+Die Schleife wird $\lfloor1+\log_2ab\rfloor$ mal durchlaufen.
+In jedem Fall wird auf jeden Fall die Multiplikation in 
+Schritt~\ref{divide-and-conquer-4} durchgeführt
+und im schlimmsten Fall auch noch die Multiplikation in
+Schritt~\ref{divide-and-conquer-3}.
+Es werden also nicht mehr als $2\lfloor 1+\log_2a\rfloor=O(\log_2a)$
+Multiplikationen durchgeführt.
+\end{proof}
+
+\begin{beispiel}
+Man berechne die Potenz $7^{2021}$ in $\mathbb{F}_p$.
+Die Binärdarstellung von 2021 ist $2021_{10}=\texttt{11111100101}_2$.
+Wir stellen die nötigen Operationen des
+Algorithmus~\ref{buch:crypto:algo:divide-and-conquer} in der folgenden
+Tabelle
+\begin{center}
+\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
+\hline
+ i&   f& a_i&    x\\
+\hline
+ 0&   7&   1&    7\\
+ 1&  49&   0&    7\\
+ 2&1110&   1&   24\\
+ 3& 486&   0&   24\\
+ 4&1234&   0&   24\\
+ 5& 667&   1&  516\\
+ 6& 785&   1&  977\\
+ 7& 418&   1&  430\\
+ 8& 439&   1&  284\\
+ 9& 362&   1&  819\\
+10& 653&   1&  333\\
+\hline
+\end{tabular}
+\end{center}
+Daraus liest man ab, dass $7^{2021}=333\in\mathbb{F}_{1291}$.
+\end{beispiel}
+
+Die Tabelle suggeriert, dass die Potenzen von $g$ ``wild'', also
+scheinbar ohne System in $\mathbb{F}_p$ herumspringen.
+Dies deutet an, dass die Umkehrung der Exponentialfunktion in $\mathbb{F}_p$
+schwierig ist.
+Die Umkehrfunktion der Exponentialfunktion, die Umkehrfunktion von 
+$x\mapsto g^x$ in $\mathbb{F}_p$ heisst der {\em diskrete Logarithmus}.
+\index{diskreter Logarithmus}%
+Tatsächlich ist der diskrete Logarithmus ähnlich schwierig zu bestimmen
+wie das Faktorisieren von Zahlen, die das Produkt grosser
+Primafaktoren ähnlicher Grössenordnung wie $p$ sind.
+Die Funktion $x\mapsto g^x$ ist die gesuchte, schwierig zu invertierende
+Funktion.
+
+\subsection{Diffie-Hellman-Schlüsseltausch
+\label{buch:subsection:diffie-hellman}}
+Eine Grundaufgabe der Verschlüsselung im Internet ist, dass zwei
+Kommunikationspartner einen gemeinsamen Schlüssel für die Verschlüsselung
+der Daten aushandeln können müssen.
+Es muss davon ausgegangen werden, dass die Kommunikation abgehört wird.
+Trotzdem soll es für einen Lauscher nicht möglich sein, den 
+ausgehandelten Schlüssel zu ermitteln.
+
+% XXX Historisches zu Diffie und Hellman
+
+Die beiden Partner $A$ und $B$ einigen sich zunächst auf eine Zahl $g$,
+die öffentlich bekannt sein darf.
+Weiter erzeugen sie eine zufällige Zahl $a$ und $b$, die sie geheim
+halten.
+Das Verfahren soll aus diesen beiden Zahlen einen Schlüssel erzeugen,
+den beide Partner berechnen können, ohne dass sie $a$ oder $b$ 
+übermitteln müssen.
+Die beiden Zahlen werden daher auch die privaten Schlüssel genannt.
+
+Die Idee von Diffie und Hellman ist jetzt, die Werte $x=g^a$ und $y=g^b$
+zu übertragen.
+In $\mathbb{R}$ würden dadurch natürlich dem Lauscher auch $a$ offenbart,
+er könnte einfach $a=\log_g x$ berechnen.
+Ebenso kann auch $b$ als $b=\log_g y$ erhalten werden, die beiden
+privaten Schlüssel wären also nicht mehr privat.
+Statt der Potenzfunktion in $\mathbb{R}$ muss also eine Funktion
+verwendet werden, die nicht so leicht umgekehrt werden kann.
+Die Potenzfunktion in $\mathbb{F}_p$ erfüllt genau diese Eigenschaft.
+Die Kommunikationspartner einigen sich also auch noch auf die (grosse)
+Primzahl $p$ und übermitteln $x=g^a\in\mathbb{F}_p$ und
+$y=g^b\in\mathbb{F}_p$.
+
+\begin{figure}
+\centering
+\begin{tikzpicture}[>=latex,thick]
+\def\l{2.5}
+\fill[color=blue!20] (-7,-6.5) rectangle (7,0.5);
+\fill[color=red!20] (-\l,-6.5) rectangle (\l,0.501);
+\node[color=red] at (0,-1.5) {öffentliches Netzwerk};
+\node[color=blue] at (-7,0.2) [right] {privat};
+\node[color=blue] at (7,0.2) [left] {privat};
+\coordinate (A) at (-\l,-2.5);
+\coordinate (C) at (\l,-5.5);
+\coordinate (B) at (\l,-2.5);
+\coordinate (D) at (-\l,-5.5);
+\node at (0,0) {$p\in\mathbb{N},g\in\mathbb{F}_p$ aushandeln};
+\fill[color=white] (-\l,-0.7) circle[radius=0.3];
+\draw (-\l,-0.7) circle[radius=0.3];
+\fill[color=white] (\l,-0.7) circle[radius=0.3];
+\draw (\l,-0.7) circle[radius=0.3];
+\node at (-\l,-0.7) {$A$};
+\node at (\l,-0.7) {$B$};
+\node at (-\l,-1.5) [left] {$a$ auswählen};
+\node at (-\l,-2.0) [left] {$x=g^a\in\mathbb{F}_p$ auswählen};
+\node at (\l,-1.5) [right] {$b$ auswählen};
+\node at (\l,-2.0) [right] {$y=g^b\in\mathbb{F}_p$ auswählen};
+\draw[->] (-\l,-1) -- (-\l,-6);
+\draw[->] (\l,-1) -- (\l,-6);
+\draw[->] (A) -- (C);
+\draw[->] (B) -- (D);
+\fill (A) circle[radius=0.08];
+\fill (B) circle[radius=0.08];
+\node at ($0.8*(A)+0.2*(C)$) [above right] {$x=g^a$};
+\node at ($0.8*(B)+0.2*(D)$) [above left] {$y=g^b$};
+\node at (-\l,-5.5) [left] {$s=g^{ab}=y^a\in\mathbb{F}_p$ ausrechnen};
+\node at (\l,-5.5) [right] {$s=g^{ab}=x^b\in\mathbb{F}_p$ ausrechnen};
+\fill[rounded corners=0.3cm,color=darkgreen!20] ({-\l-1},-7) rectangle ({\l+1},-6);
+\draw[rounded corners=0.3cm] ({-\l-1},-7) rectangle ({\l+1},-6);
+\node at (0,-6.5) {$A$ und $B$ haben den gemeinsamen Schlüssel $s$};
+\end{tikzpicture}
+\caption{Schlüsselaustausch nach Diffie-Hellman.
+Die Kommunikationspartner $A$ und $B$ einigen sich öffentlich auf
+$p\in\mathbb{N}$ und $g\in\mathbb{F}_p$.
+$A$ wählt dann einen privaten Schlüssel $a\in\mathbb{N}$ und
+$B$ wählt $b\in\mathbb{N}$, sie tauschen dann $x=g^a$ und $y=g^b$
+aus.
+$A$ erhält den gemeinsamen Schlüssel aus $y^a$, $B$ erhält ihn
+aus $x^b$.
+\label{buch:crypto:fig:dh}}
+\end{figure}
+
+Aus $x$ und $y$ muss jetzt der gemeinsame Schlüssel abgeleitet werden.
+$A$ kennt $y=g^b$ und $a$, $B$ kennt $x=g^a$ und $b$.
+Beide können die Zahl $s=g^{ab}\in\mathbb{F}_p$ berechnen.
+$A$ macht das, indem er $y^a=(g^b)^a = g^{ab}$ rechnet,
+$B$ rechnet $x^b = (g^a)^b = g^{ab}$, beide natürlich in $\mathbb{F}_p$.
+Der Lauscher kann aber $g^{ab}$ nicht ermitteln, dazu müsste er
+$a$ oder $b$ ermitteln können.
+Die Zahl $s=g^{ab}$ kann also als gemeinsamer Schlüssel verwendet
+werden.
+
+
+
+\subsection{Elliptische Kurven
+\label{buch:subsection:elliptische-kurven}}
+Das Diffie-Hellman-Verfahren basiert auf der Schwierigkeit, in einem 
+Körper $\mathbb{F}_p$ die Gleichung $a^x=b$ nach $x$ aufzulösen.
+
+
diff --git a/buch/chapters/90-crypto/rs.tex b/buch/chapters/90-crypto/rs.tex
index e8ea3b4..ec8ec8c 100644
--- a/buch/chapters/90-crypto/rs.tex
+++ b/buch/chapters/90-crypto/rs.tex
@@ -6,3 +6,36 @@
 \section{Fehlerkorrigierende Codes nach Reed-Solomon
 \label{buch:section:reed-solomon}}
 \rhead{Fehlerkorrigierende Codes}
+Jede Art von Datenübertragung muss sich mit dem Problem der Fehler befassen,
+die auf dem Übertragungskanal entstehen können.
+Die einfachste Lösung dieses Problem versucht, Fehler zu erkennen und 
+dann eine erneute Übermittelung zu veranlassen.
+Dies ist zum Beispiel bei der Datenübertragung von einer Raumsonde
+wie Voyager~1 nicht möglich, die Signallaufzeit von der Sonde und wieder
+zurück ist über 40 Stunden.
+Es ist auch nicht sinnvoll beim Lesen eines optischen Mediums wie einer
+CD oder DVD, wenn ein Fehler durch eine Beschädigung der Oberfläche
+des Mediums verursacht wird.
+Erneutes Lesen würde das Resultat auch nicht ändern.
+Es wird also eine Möglichkeit gesucht, die Daten so zu codieren, dass
+ein Fehler nicht nur erkannt sondern auch korrigiert werden kann.
+
+In diesem Abschnitt werden die algebraisch besonders interessanten
+Reed-Solmon-Codes beschrieben.
+Ihren ersten Einsatz hatten Sie bei den Voyager-Raumsonden, die 1977
+gestartet wurden.
+Sie befinden sich im Moment in einer Entfernung von 
+Zum ersten mal kommerziell verwendet wurden sie für die optischen
+Medien CD und DVD.
+
+% https://www.youtube.com/watch?v=uOLW43OIZJ0
+% https://www.youtube.com/watch?v=4BfCmZgOKP8
+
+\subsection{Was ist ein Code?
+\label{buch:subsection:was-ist-ein-code}}
+
+\subsection{Reed-Solomon-Code
+\label{buch:subsection:reed-solomon-code}}
+
+\subsection{Decodierung
+\label{buch:subsection:decodierung}}
diff --git a/buch/chapters/90-crypto/uebungsaufgaben/9001.tex b/buch/chapters/90-crypto/uebungsaufgaben/9001.tex
new file mode 100644
index 0000000..5bf4558
--- /dev/null
+++ b/buch/chapters/90-crypto/uebungsaufgaben/9001.tex
@@ -0,0 +1,31 @@
+$A$ und $B$ einigen sich darauf, das Diffie-Hellman-Verfahren für
+$p=2027$ durchzuführen und mit $g=3$ zu arbeiten.
+$A$ verwenden $a=49$ als privaten Schlüssel und erhält von $B$
+den öffentlichen Schlüssel $y=1772$.
+Welchen gemeinsamen Schlüssel verwenden $A$ und $B$?
+
+\begin{loesung}
+Der zu verwendende gemeinsame Schlüssel ist
+$g^{ab}=(g^b)^a = y^a\in\mathbb{F}_2027$.
+Diese Potenz kann man mit dem Divide-and-Conquer-Algorithmus effizient
+berechnen.
+Die Binärdarstellung des privaten Schlüssels von $A$ ist
+$a=49_{10}=\texttt{110001}_2$.
+Der Algorithmus verläuft wie folgt:
+\begin{center}
+\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|}
+\hline
+i&g^{2^i}&a_i&     x\\
+\hline
+0&      3&  1&     3\\
+1&      9&  0&     3\\
+2&     81&  0&     3\\
+3&    480&  0&     3\\
+4&   1349&  1&  2020\\
+5&   1582&  1&  1088\\
+\hline
+\end{tabular}
+\end{center}
+Der gemeinsame Schlüssel ist daher $s=1088$.
+\end{loesung}
+