Merge pull request #1 from AndreasFMueller/master

update

14 files changed, 1111 insertions, 0 deletions

diff --git a/buch/chapters/90-crypto/Makefile.inc b/buch/chapters/90-crypto/Makefile.inc
new file mode 100644
index 0000000..9543ce1
--- /dev/null
+++ b/buch/chapters/90-crypto/Makefile.inc
@@ -0,0 +1,12 @@
+#
+# Makefile.inc -- Makefile dependencies for chapter 9
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+
+CHAPTERFILES = $(CHAPTERFILES)						\
+	chapters/90-crypto/arith.tex					\
+	chapters/90-crypto/ff.tex					\
+	chapters/90-crypto/aes.tex					\
+	chapters/90-crypto/rs.tex					\
+	chapters/90-crypto/chapter.tex
diff --git a/buch/chapters/90-crypto/aes.tex b/buch/chapters/90-crypto/aes.tex
new file mode 100644
index 0000000..6004dde
--- /dev/null
+++ b/buch/chapters/90-crypto/aes.tex
@@ -0,0 +1,35 @@
+%
+% aes.tex -- Beschreibung des AES Algorithmus
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\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/arith.tex b/buch/chapters/90-crypto/arith.tex
new file mode 100644
index 0000000..b6f2fd8
--- /dev/null
+++ b/buch/chapters/90-crypto/arith.tex
@@ -0,0 +1,25 @@
+%
+% arith.tex
+%
+% (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\section{Arithmetik für die Kryptographie
+\label{buch:section:arithmetik-fuer-kryptographie}}
+\rhead{Arithmetik für die Kryptographie}
+
+\subsection{Potenzieren
+\label{buch:subsection:potenzieren}}
+% XXX Divide-and-Conquer Algorithmus
+
+\subsection{Rechenoperationen in $\mathbb{F}_p$
+\label{buch:subsection:rechenoperationen-in-fp}}
+% XXX Multiplikation: modulare Reduktion mit jedem Digit
+% XXX Divide-and-Conquer
+
+\subsection{Rechenoperationen in $\mathbb{F}_{2^l}$
+\label{buch:subsection:rechenoperatione-in-f2l}}
+% XXX Darstellung eines Körpers der Art F_{2^l}
+% XXX Addition (XOR) und Multiplikation
+% XXX Beispiel F_{2^8}
+% XXX Beispiel F einer Oakley-Gruppe
+
diff --git a/buch/chapters/90-crypto/chapter.tex b/buch/chapters/90-crypto/chapter.tex
new file mode 100644
index 0000000..43ac8de
--- /dev/null
+++ b/buch/chapters/90-crypto/chapter.tex
@@ -0,0 +1,31 @@
+%
+% chapter.tex -- Anwendungen von Matrizen in der Codierungstheorie und
+%                Kryptographie
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+% !TeX spellcheck = de_CH
+\chapter{Anwendungen in Kryptographie und Codierungstheorie
+\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/arith.tex}
+\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
new file mode 100644
index 0000000..4ab9c34
--- /dev/null
+++ b/buch/chapters/90-crypto/ff.tex
@@ -0,0 +1,664 @@
+%
+% ff.tex -- Kryptographie und endliche Körper
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+
+\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.
+
+Auf dern ersten Blick scheint der
+Algorithmus~\ref{buch:crypto:algo:divide-and-conquer}
+den Nachteil zu haben, dass erst die Binärdarstellung der Zahl $a$ 
+ermittelt werden muss.
+In einem Computer ist dies aber normalerweise kein Problem, da $a$
+im Computer ohnehin binär dargestellt ist.
+Die Binärziffern werden in der Reihenfolge vom niederwertigsten zum
+höchstwertigen Bit benötigt.
+Die folgende Modifikation des Algorithmus ermittelt laufend
+auch die Binärstellen von $a$.
+Die dazu notwendigen Operationen sind im Binärsystem besonders
+effizient implementierbar, die Division durch 2 ist ein Bitshift, der
+Rest ist einfach das niederwertigste Bit der Zahl.
+
+\begin{algorithmus}
+\label{buch:crypto:algo:divide-and-conquer2}
+\begin{enumerate}
+\item
+Setze $f=g$, $x=1$, $i=0$
+\item
+Solange $a>0$ ist, führe aus
+\begin{enumerate}
+\item
+Verwende den euklidischen Algorithmus um $r$ und $b$ zu bestimmen mit $a=2b+r$
+\item
+Falls $r=1$ setze $x \coloneqq x \cdot f$
+\item
+$i \coloneqq i+1$, $a = b$ 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}
+
+
+%
+% Diffie-Hellman Schlüsseltausch
+%
+\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
+\includegraphics{chapters/90-crypto/images/dh.pdf}
+\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.
+Die Addition in $\mathbb{F}_p$ wird dazu nicht benötigt.
+Es reicht, eine Menge mit einer Multiplikation zu haben, in der das
+die Gleichung $a^x=b$ schwierig zu lösen ist.
+Ein Gruppe wäre also durchaus ausreichend.
+
+Ein Kandidat für eine solche Gruppe könnte der Einheitskreis
+$S^1=\{z\in\mathbb{C}\;|\; |z|=1\}$ in der komplexen Ebene sein.
+Wählt man eine Zahl $g=e^{i\alpha}$, wobei $\alpha$ ein irrationales
+Vielfaches von $\pi$ ist, dann sind alle Potenzen $g^n$ für natürliche
+Exponenten voneinander verschieden.
+Wäre nämlich $g^{n_1}=g^{n_2}$, dann wäre $e^{i\alpha(n_1-n_2)}=1$ und
+somit müsste $\alpha=2k\pi/(n_1-n_2)$ sein.
+Damit wäre aber $\alpha$ ein rationales Vielfaches von $\pi$, im Widerspruch
+zur Voraussetzung.
+Die Abbildung $n\mapsto g^n\in S^1$ ist auf den ersten Blick etwa ähnlich
+undurchschaubar wie die Abbildung $n\mapsto g^n\in\mathbb{F}_p$.
+Es gibt zwar die komplexe Logarithmusfunktion, mit der man $n$ bestimmen
+kann, dazu muss man aber den Wert von $g^n$ mit beliebiger Genauigkeit
+kennen, denn die Werte von $g^n$ können beliebig nahe beieinander liegen.
+
+Der Einheitskreis ist die Lösungsmenge der Gleichung $x^2+y^2=1$ für
+reelle Koordinaten $x$ und $y$,
+doch Rundungsunsicherheiten verunmöglichen den Einsatz in einem 
+Verfahren ähnlich dem Diffie-Hellman-Verfahren.
+Dieses Problem kann gelöst werden, indem für die Variablen Werte
+aus einem endlichen Körper verwendet werden.
+Gesucht ist also eine Gleichung in zwei Variablen, deren Lösungsmenge
+in einem endlichen Körper eine Gruppenstruktur trägt.
+Die Lösungsmenge ist eine ``Kurve'' von Punkten mit
+Koordinaten in einem endlichen Körper.
+
+In diesem Abschnitt wird gezeigt, dass sogenannte elliptische Kurven
+über endlichen Körpern genau die verlangen Eigenschaften haben.
+
+\subsubsection{Elliptische Kurven}
+Elliptische Kurven sind Lösungen einer Gleichung der Form
+\begin{equation}
+Y^2+XY=X^3+aX+b
+\label{buch:crypto:eqn:ellipticcurve}
+\end{equation}
+mit Werten von $X$ und $Y$ in einem geeigneten Körper.
+Die Koeffizienten $a$ und $b$ müssen so gewählt werden, dass die
+Gleichung~\eqref{buch:crypto:eqn:ellipticcurve} genügend viele
+Lösungen hat.
+Über den komplexen Zahlen hat die Gleichung natürlich für jede Wahl von
+$X$ drei Lösungen.
+Für einen endlichen Körper können wir dies im allgemeinen nicht erwarten,
+aber wenn wir genügend viele Wurzeln zu $\mathbb{F}$ hinzufügen können wir
+mindestens erreichen, dass die Lösungsmenge so viele Elemente hat, 
+dass ein Versuch, die Gleichung $g^x=b$ mittels Durchprobierens zu
+lösen, zum Scheitern verurteil ist.
+
+\begin{definition}
+\label{buch:crypto:def:ellipticcurve}
+Die {\em elliptische Kurve} $E_{a,b}(\Bbbk)$ über dem Körper $\Bbbk$ ist 
+die Menge
+\[
+E_{a,b}(\Bbbk)
+=
+\{(X,Y)\in\Bbbk^2\;|\;Y^2+XY=X^3+aX+b\},
+\]
+für $a,b\in\Bbbk$.
+\end{definition}
+
+Um die Anschauung zu vereinfachen, werden wir elliptische Kurven über
+dem Körper $\mathbb{R}$ visualisieren.
+Die daraus gewonnenen geometrischen Einsichten werden wir anschliessend
+algebraisch umsetzen.
+In den reellen Zahlen kann man die
+Gleichung~\eqref{buch:crypto:eqn:ellipticcurve}
+noch etwas vereinfachen.
+Indem man in \eqref{buch:crypto:eqn:ellipticcurve} 
+quadratisch ergänzt, bekommt man
+\begin{align}
+Y^2 + XY + \frac14X^2 &= X^3+\frac14 X^2 +aX+b
+\notag
+\\
+\Rightarrow\qquad
+v^2&=X^3+\frac14X^2+aX+b,
+\label{buch:crypto:eqn:ell2}
+\end{align}
+indem man $v=Y+\frac12X$ setzt.
+Man beachte, dass man diese Substition nur machen kann, wenn $\frac12$
+definiert ist.
+In $\mathbb{R}$ ist dies kein Problem, aber genau über den Körpern
+mit Charakteristik $2$, die wir für die Computer-Implementation
+bevorzugen, ist dies nicht möglich.
+Es geht hier aber nur um die Visualisierung.
+
+Auch die Form \eqref{buch:crypto:eqn:ell2} lässt sich noch etwas 
+vereinfachen.
+Setzt man $X=u-\frac1{12}$, dann verschwindet nach einiger Rechnung,
+die wir hier nicht durchführen wollen, der quadratische Term
+auf der rechten Seite.
+Die interessierenden Punkte sind Lösungen der einfacheren Gleichung
+\begin{equation}
+v^2
+=
+u^3+\biggl(a-\frac{1}{48}\biggr)u + b-\frac{a}{12}+\frac{1}{864}
+=
+u^3+Au+B.
+\label{buch:crypto:ellvereinfacht}
+\end{equation}
+In dieser Form ist mit $(u,v)$ immer auch $(u,-v)$ eine Lösung,
+die Kurve ist symmetrisch bezüglich der $u$-Achse.
+Ebenso kann man ablesen, dass nur diejenigen $u$-Werte möglich sind,
+für die das kubische Polynom $u^3+Au+B$ auf der rechten Seite von
+\eqref{buch:crypto:ellvereinfacht}
+nicht negativ ist.
+
+Sind $u_1$, $u_2$ und $u_3$ die Nullstellen des kubischen Polynoms
+auf der rechten Seite von~\eqref{buch:crypto:ellvereinfacht}, folgt
+\[
+v^2
+=
+(u-u_1)(u-u_2)(u-u_3)
+=
+u^3
+-(u_1+u_2+u_3)u^2
++(u_1u_2+u_1u_3+u_2u_3)u
+-
+u_1u_2u_3.
+\]
+Durch Koeffizientenvergleich sieht man, dass $u_1+u_2+u_3=0$ sein muss.
+\begin{figure}
+\centering
+\includegraphics{chapters/90-crypto/images/elliptic.pdf}
+\caption{Elliptische Kurve in $\mathbb{R}$ in der Form
+$v^2=u^3+Au+B$ mit Nullstellen $u_1$, $u_2$ und $u_3$ des
+kubischen Polynoms auf der rechten Seite.
+Die blauen Punkte und Geraden illustrieren die Definition der
+Gruppenoperation in der elliptischen Kurve.
+\label{buch:crypto:fig:elliptischekurve}}
+\end{figure}
+Abbildung~\ref{buch:crypto:fig:elliptischekurve}
+zeigt eine elliptische Kurve in der Ebene.
+
+\subsubsection{Geometrische Definition der Gruppenoperation}
+In der speziellen Form \ref{buch:crypto:ellvereinfacht} ist die
+elliptische Kurve symmetrisch unter Spiegelung an der $u$-Achse.
+Die Spiegelung ist eine Involution, zweimalige Ausführung führt auf
+den ursprünglichen Punkt zurück.
+Die Inverse in einer Gruppe hat diese Eigenschaft auch, es ist
+daher naheliegend, den gespiegelten Punkt als die Inverse eines
+Elementes zu nehmen.
+
+Eine Gerade durch zwei Punkte der
+in Abbildung~\ref{buch:crypto:fig:elliptischekurve}
+dargestellten Kurve schneidet die Kurve ein drittes Mal.
+Die Gruppenoperation wird so definiert, dass drei Punkte der Kurve
+auf einer Geraden das Gruppenprodukt $e$ haben.
+Da aus $g_1g_2g_3=e$ folgt $g_3=(g_1g_2)^{-1}$ oder
+$g_1g_2=g_3^{-1}$, erhält man das Gruppenprodukt zweier Elemente
+auf der elliptischen Kurve indem erst den dritten Schnittpunkt
+ermittelt und diesen dann an der $u$-Achse spiegelt.
+
+Die geometrische Konstruktion schlägt fehl, wenn $g_1=g_2$ ist.
+In diesem Fall kann man die Tangente im Punkt $g_1$ an die Kurve 
+verwenden.
+Dieser Fall tritt zum Beispiel auch in den drei Punkten 
+$(u_1,0)$, $(u_2,0)$ und $(u_3,0)$ ein.
+
+Um das neutrale Element der Gruppe zu finden, können wir 
+zwei Punkte $g$ und $g^{-1}$ miteinander verknüpfen.
+Die Gerade durch $g$ und $g^{-1}$ schneidet aber die Kurve
+kein drittes Mal.
+Ausserdem sind alle Geraden durch $g$ und $g^{-1}$ für verschiedene
+$g$ parallel.
+Das neutrale Element entspricht also einem unendlich weit entfernten Punkt.
+Das neutrale Element entsteht immer dann als Produkt, wenn zwei
+Punkte die gleiche $u$-Koordinaten haben.
+
+\subsubsection{Gruppenoperation, algebraische Konstruktion}
+Nach den geometrischen Vorarbeiten zur Definition der Gruppenoperation
+kann können wir die Konstruktion jetzt algebraisch umsetzen.
+
+Zunächst überlegen wir uns wieder eine Involution, welche als Inverse
+dienen kann.
+Dazu beachten wir, dass die linke Seite der definierenden Gleichung
+\begin{equation}
+Y^2+XY=X^3-aX+b.
+\label{buch:crypto:eqn:grupopgl}
+\end{equation}
+auch als $Y(Y+X)$ geschrieben werden kann.
+Die Abbildung $Y\mapsto -X-Y$ macht daraus
+\[
+(-X-Y)(-X-Y+X)=(X+Y)Y,
+\]
+dies ist also die gesuchte Involution.
+
+Seien also $g_1=(x_1,y_1)$ und $g_2=(x_2,y_2)$ zwei verschiedene Lösungen
+der Gleichung \eqref{buch:crypto:eqn:grupopgl}
+Als erstes brauchen wir eine Gleichung für die Gerade durch die beiden
+Punkte.
+Sei also $l(X,Y)$ eine Linearform derart, dass $l(g_1)=d$ und $l(g_2)=d$
+für ein geeignetes $d\in\Bbbk$.
+Dann gilt auch für die Punkte
+\[
+g(t) = tg_1 + (1-t)g_2
+\qquad\Rightarrow\qquad
+l(g(t))
+=
+tl(g_1) + (1-t)l(g_2)
+=
+tc+(1-t)c
+=
+(t+1-t)c
+=c,
+\]
+jeder Punkt der Geraden durch $g_1$ und $g_2$ lässt sich in dieser Form
+schreiben.
+
+Setzt man jetzt $g(t)$ in die Gleichung ein, erhält man eine kubische
+Gleichung in $t$, von der wir bereits zwei Nullstellen kennen, nämlich 
+$0$ und $1$.
+Die kubische Gleichung muss also durch $t$ und $(t-1)$ teilbar sein.
+Diese Berechnung kann man einfach in einem Computeralgebrasystem
+durchführen.
+Das Polynom ist
+\[
+p(t)
+=
+\]
+Nach Division durch $t(t-1)$ erhält man als den Quotienten
+\begin{align*}
+q(t)
+&=
+(y_2-y_1)^2 
++
+(y_2-y_1) (x_2-x_1)
++
+t(x_2-x_1)^3
+-
+2x_2^3+3x_1x_2^2-x_1^3
+\end{align*}
+und den Rest
+\[
+r(t)
+=
+t(y_1^2+x_1y_1-x_1^3-ax_1-b)
++
+(1-t)(y_2^2+x_2y_2-x_2^3-ax_2-b).
+\]
+Die Klammerausdrücke verschwinden, da die sie gleichbedeutend damit sind,
+dass die Punkte Lösungen von \eqref{buch:crypto:eqn:grupopgl} sind.
+
+Für den dritten Punkt auf der Geraden muss $t$ so gewählt werden, dass
+$q(t)=0$ ist.
+Dies ist aber eine lineare Gleichung mit der Lösung
+\begin{align*}
+t
+&=
+-\frac{
+(y_1-y_2)^2
++
+(y_2-y_1)(x_2-x_1)
+-2x_2^3+3x_1x_2^2-x_1^3
+}{(x_2-x_1)^3}
+.
+\end{align*}
+Setzt man dies $g(t)$ ein, erhält man für die Koordinaten des dritten
+Punktes $g_3$ die Werte
+\begin{align}
+x_3
+&=
+\frac{
+(y_2-y_1)^2(x_2-x_1) + (y_2-y_1)(x_2-x_1)^2
+-(x_2^4+x_1^4)
+}{
+(x_2-x_1)^3
+}
+\label{buch:crypto:eqn:x3}
+\\
+y_3
+&=
+\frac{
+(y_2-y_1)^3
++(x_2-x_1)(y_2-y_1)^2
+-(x_{2}-x_{1})^3 ( y_{2} - y_{1})
+-(x_{2}-x_{1})^2 ( x_{1} y_{2}- x_{2} y_{1})
+}{
+(x_2-x_1)^3
+}
+\label{buch:crypto:eqn:y3}
+\end{align}
+Die Gleichungen 
+\eqref{buch:crypto:eqn:x3}
+und
+\eqref{buch:crypto:eqn:y3}
+ermöglichen also, das Element $g_1g_2^{-1}$ zu berechnen.
+Interessant daran ist, dass in den Formeln die Konstanten $a$ und $b$ 
+gar nicht vorkommen.
+
+Es bleibt noch der wichtige Fall des Quadrierens in der Gruppe zu
+behandeln, also den Fall $g_1=g_2$.
+In diese Fall sind die Formeln
+\eqref{buch:crypto:eqn:x3}
+und
+\eqref{buch:crypto:eqn:y3}
+ganz offensichtlich nicht anwendbar.
+Die geometrische Anschauung hat nahegelegt, die Tangent an die Kurve
+im Punkt $g_1$ zu nehmen.
+In $\mathbb{R}$ würde man dafür einen Grenzübergang $g_2\to g_1$ machen,
+aber in einem endlichen Körper ist dies natürlich nicht möglich.
+
+Wir schreiben die Gerade als Parameterdarstellung in der Form
+\(
+t\mapsto g(t)= (x_1+ut, y_1+vt)
+\)
+für beliebige Parameter in $\Bbbk$.
+Die Werte $u_1$ und $u_2$ müssen so gewählt werden, dass $g(t)$ eine
+Tangente wird.
+Setzt man $g(t)$ in die Gleichung~\eqref{buch:crypto:eqn:grupopgl} ein,
+entsteht ein kubische Gleichung, die genau dann eine doppelte Nullstelle
+bei $0$ hat, wenn $u,v$ die Tangentenrichtung beschreiben.
+Einsetzen von $g(t)$ in \eqref{buch:crypto:eqn:grupopgl}
+ergibt die Gleichung
+\begin{align}
+0
+&=
+-u^3t^3
++
+(-3u^2x_{1}+v^2+uv)t^2
++
+(2vy_1+uy_1-3ux_1^2+vx_1-au)t
++
+(y_1^2+x_1y_1-x_1^3-ax_1-b)
+\label{buch:crypto:eqn:tangente1}
+\end{align}
+Damit bei $t=0$ eine doppelte Nullstelle mussen die letzten beiden
+Koeffizienten verschwinden, dies führt auf die Gleichungen
+\begin{align}
+y_1^2+x_1y_1&=x_1^3+ax_1+b
+\label{buch:crypto:eqn:rest1}
+\\
+(2y_1
++x_1)v
++(y_1
+-3x_1^2
+-a)u
+&=0
+\label{buch:crypto:eqn:rest2}
+\end{align}
+Die erste Gleichung \eqref{buch:crypto:eqn:rest1} drückt aus,
+dass $g_1$ ein Punkt der Kurve ist, sie ist automatisch erfüllt.
+
+Die zweite Gleichung
+\eqref{buch:crypto:eqn:rest2}
+legt das Verhältnis von $u$ und $v$, also die
+\label{buch:crypto:eqn:rest2}
+Tangentenrichtung fest.
+Eine mögliche Lösung ist
+\begin{equation}
+\begin{aligned}
+u &= x_1+2y_1
+\\
+v &= -y_1+3x_1^2+a.
+\end{aligned}
+\label{buch:crypto:eqn:uv}
+\end{equation}
+
+Der Quotient ist ein lineares Polynom in $t$, die Nullstelle parametrisiert
+den Punkt, der $(g_1)^{-2}$ entspricht.
+Der zugehörige Wert von $t$ ist
+\begin{equation}
+t=-\frac{3u^2x_1-v^2-uv}{u^3}.
+\label{buch:crypto:eqn:t}
+\end{equation}
+
+
+Setzt man
+\label{buch:crypto:eqn:t}
+und
+\eqref{buch:crypto:eqn:uv}
+in $g(t)$ ein, erhält man sehr komplizierte Ausdrücke für den dritten Punkt.
+Wir verzichten darauf, diese Ausdrücke hier aufzuschreiben.
+In der Praxis wird man in einem Körper der Charakteristik 2 arbeiten.
+In diesem Körper werden alle geraden Koeffizienten zu $0$, alle ungeraden
+Koeffizienten werden unabhängig vom Vorzeichen zu $1$.
+Damit bekommt man die folgenden, sehr viel übersichtlicheren Ausdrücke
+für den dritten Punkt:
+\begin{equation}
+\begin{aligned}
+x
+&=
+-\frac{
+y_1^2+x_1y_1+x_1^4+x_1^3+ax_1-a^2
+ }{
+x_1^2
+}
+\\
+y
+&=
+\frac{
+y_1^3+(x_1^2+x_1+a)y_1^2+(x_1^4 +a^2)y_1+x_1^6+ax_1^4+ax_1^3+a^2x_1^2+a^2x_1+a^3
+}{
+ x_1^3
+}
+\end{aligned}
+\label{buch:crypto:eqn:tangentechar2}
+\end{equation}
+Damit haben wir einen vollständigen Formelsatz für die Berechnung der
+Gruppenoperation in der elliptischen Kurve mindestens für den praktisch
+relevanten Fall einer Kurve über einem Körper der Charakteristik $2$.
+
+\begin{satz}
+Die elliptische Kurve
+\[
+E_{a,b}(\mathbb{F}_{p^l})
+=
+\{
+(X,Y)\in\mathbb{F}_{p^l}
+\;|\;
+Y^2+XY = X^3-aX-b
+\}
+\]
+trägt eine Gruppenstruktur, die wie folgt definiert ist:
+\begin{enumerate}
+\item Der Punkt $(0,0)$ entspricht dem neutralen Element.
+\item Das inverse Element von $(x,y)$ ist $(-x,-y-x)$.
+\item Für zwei verschiedene Punkte $g_1$ und $g_2$ kann $g_3=(g_1g_2)^{-1}$
+mit Hilfe der Formeln
+\eqref{buch:crypto:eqn:x3}
+und
+\eqref{buch:crypto:eqn:y3}
+gefunden werden.
+\item Für einen Punkt $g_1$ kann $g_3=g_1^{-2}$ in Charakteristik $2$ mit
+Hilfe der Formeln
+\eqref{buch:crypto:eqn:tangentechar2}
+gefunden werden.
+\end{enumerate}
+Diese Operationen machen $E_{a,b}(\mathbb{F}_{p^l})$ zu einer endlichen
+abelschen Gruppe.
+\end{satz}
+
+\subsubsection{Beispiele}
+% XXX
+TODO: elliptische Kurven in IPsec: Oakley Gruppen
+
+\subsubsection{Diffie-Hellman in einer elliptischen Kurve}
+% XXX
+TODO: $g^x$ in einer elliptischen Kurve
+
+
+
diff --git a/buch/chapters/90-crypto/images/Makefile b/buch/chapters/90-crypto/images/Makefile
new file mode 100644
index 0000000..9480163
--- /dev/null
+++ b/buch/chapters/90-crypto/images/Makefile
@@ -0,0 +1,13 @@
+#
+# Makefile -- build images for crypto chapter
+#
+# (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+#
+all:	dh.pdf elliptic.pdf
+
+dh.pdf:	dh.tex
+	pdflatex dh.tex
+
+elliptic.pdf:	elliptic.tex
+	pdflatex elliptic.tex
+
diff --git a/buch/chapters/90-crypto/images/dh.pdf b/buch/chapters/90-crypto/images/dh.pdf
new file mode 100644
index 0000000..67b95a5
--- /dev/null
+++ b/buch/chapters/90-crypto/images/dh.pdf
diff --git a/buch/chapters/90-crypto/images/dh.tex b/buch/chapters/90-crypto/images/dh.tex
new file mode 100644
index 0000000..1faa830
--- /dev/null
+++ b/buch/chapters/90-crypto/images/dh.tex
@@ -0,0 +1,53 @@
+%
+% dh.tex -- diffie hellmann key exchange
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math,calc,hobby}
+\begin{document}
+\definecolor{darkgreen}{rgb}{0,0.6,0}
+\def\skala{1}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+\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}
+\end{document}
+
diff --git a/buch/chapters/90-crypto/images/elliptic.pdf b/buch/chapters/90-crypto/images/elliptic.pdf
new file mode 100644
index 0000000..d408f1e
--- /dev/null
+++ b/buch/chapters/90-crypto/images/elliptic.pdf
diff --git a/buch/chapters/90-crypto/images/elliptic.tex b/buch/chapters/90-crypto/images/elliptic.tex
new file mode 100644
index 0000000..f0843cd
--- /dev/null
+++ b/buch/chapters/90-crypto/images/elliptic.tex
@@ -0,0 +1,97 @@
+%
+% elliptic.tex -- elliptic curve
+%
+% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+%
+\documentclass[tikz]{standalone}
+\usepackage{amsmath}
+\usepackage{times}
+\usepackage{txfonts}
+\usepackage{pgfplots}
+\usepackage{csvsimple}
+\usetikzlibrary{arrows,intersections,math}
+\begin{document}
+\def\skala{4}
+\begin{tikzpicture}[>=latex,thick,scale=\skala]
+
+\def\uone{-1.1}
+\def\utwo{0.3}
+\pgfmathparse{-(\uone+\utwo)}
+\xdef\uthree{\pgfmathresult}
+\xdef\r{0.017}
+
+\def\gone{-1.05}
+\def\gtwo{0.2}
+\def\gthree{1.105}
+
+\pgfmathparse{-sqrt((\gone-\uone)*(\gone-\utwo)*(\gone-\uthree))}
+\xdef\yone{\pgfmathresult}
+\pgfmathparse{sqrt((\gtwo-\uone)*(\gtwo-\utwo)*(\gtwo-\uthree))}
+\xdef\ytwo{\pgfmathresult}
+\pgfmathparse{sqrt((\gthree-\uone)*(\gthree-\utwo)*(\gthree-\uthree))}
+\xdef\ythree{\pgfmathresult}
+
+\begin{scope}
+\clip (-1.5,-1.5) rectangle (1.5,1.5);
+\draw[color=blue]
+	({\gone-(\gtwo-\gone)},{\yone-(\ytwo-\yone)})
+	--
+	({\gone+2*(\gtwo-\gone)},{\yone+2*(\ytwo-\yone)});
+\draw[color=blue] (\gthree,-2) -- (\gthree,2);
+\end{scope}
+
+\draw[line width=1.4pt,color=red]
+	(\uone,0) --
+	plot[domain={\uone+0.001}:{\utwo-0.001},samples=100]
+		(\x,{sqrt((\x-\uone)*(\x-\utwo)*(\x-\uthree))})
+	-- (\utwo,0);
+\draw[line width=1.4pt,color=red]
+	(\uone,0) --
+	plot[domain={\uone+0.001}:{\utwo-0.001},samples=100]
+		(\x,{-sqrt((\x-\uone)*(\x-\utwo)*(\x-\uthree))})
+	-- (\utwo,0);
+
+\draw[line width=1.4pt,color=red]
+	(\uthree,0) --
+	plot[domain={\uthree}:1.5,samples=100]
+		(\x,{sqrt((\x-\uone)*(\x-\utwo)*(\x-\uthree))}) ;
+\draw[line width=1.4pt,color=red]
+	(\uthree,0) --
+	plot[domain={\uthree}:1.5,samples=100]
+		(\x,{-sqrt((\x-\uone)*(\x-\utwo)*(\x-\uthree))}) ;
+
+\draw[->] (-1.5,0) -- (1.5,0) coordinate[label={$u$}];
+\draw[->] (0,-1.5) -- (0,1.5) coordinate[label={right:$v$}];
+\node at (0,0) [below left] {$O$};
+
+\fill[color=white] (\uone,0) circle[radius=\r];
+\draw (\uone,0) circle[radius=\r];
+\node at ({\uone+0.01},-0.01) [above left] {$u_1$};
+
+\fill[color=white] (\utwo,0) circle[radius=\r];
+\draw (\utwo,0) circle[radius=\r];
+\node at ({\utwo-0.01},-0.01) [above right] {$u_2$};
+
+\fill[color=white] (\uthree,0) circle[radius=\r];
+\draw (\uthree,0) circle[radius=\r];
+\node at ({\uthree+0.01},-0.01) [above left] {$u_3$};
+
+\fill[color=white] (\gone,\yone) circle[radius=\r];
+\draw[color=blue] (\gone,\yone) circle[radius=\r];
+
+\fill[color=white] (\gtwo,\ytwo) circle[radius=\r];
+\draw[color=blue] (\gtwo,\ytwo) circle[radius=\r];
+
+\fill[color=white] (\gthree,\ythree) circle[radius=\r];
+\draw[color=blue] (\gthree,\ythree) circle[radius=\r];
+\fill[color=white] (\gthree,-\ythree) circle[radius=\r];
+\draw[color=blue] (\gthree,-\ythree) circle[radius=\r];
+
+\node[color=blue] at (\gone,{\yone-0.03}) [above left] {$g_1$};
+\node[color=blue] at ({\gtwo+0.03},{\ytwo+0.01}) [above] {$g_2$};
+\node[color=blue] at (\gthree,{\ythree+0.02}) [below right] {$g_3$};
+\node[color=blue] at (\gthree,{-\ythree+0.03}) [below left] {$g_1g_2=g_3^{-1}$};
+
+\end{tikzpicture}
+\end{document}
+
diff --git a/buch/chapters/90-crypto/rechnungen/elliptic.maxima b/buch/chapters/90-crypto/rechnungen/elliptic.maxima
new file mode 100644
index 0000000..8c43e6c
--- /dev/null
+++ b/buch/chapters/90-crypto/rechnungen/elliptic.maxima
@@ -0,0 +1,42 @@
+/*
+ * elliptic.maxima
+ *
+ * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule
+ */
+
+p: Y^2+X*Y - X^3 - a*X -b;
+
+x: x1*t+(1-t)*x2;
+y: y1*t+(1-t)*y2;
+
+q: subst(x,X,p);
+q: subst(y,Y,q);
+q: ratsimp(expand(q));
+tex(q);
+
+qr: divide(q,t*(t-1),t);
+r: qr[2];
+q: qr[1];
+tex(q);
+
+subst(0,t,r);
+subst(1,t,r);
+
+tex(r);
+
+polydecomp(qr[2], t);
+
+s: solve(q = 0, t);
+tex(s);
+
+x3: ratsimp(expand(subst(s, x)));
+y3: ratsimp(expand(subst(s, y)));
+
+tex(x3);
+tex(y3);
+
+Y3: expand(y3 * (x2-x1)^3 - (y2-y1)^3 - (x2-x1)*(y2-y1)^2 );
+Y3: factor(expand(Y3));
+tex(Y3);
+
+
diff --git a/buch/chapters/90-crypto/rechnungen/tangent.maxima b/buch/chapters/90-crypto/rechnungen/tangent.maxima
new file mode 100644
index 0000000..aa7d236
--- /dev/null
+++ b/buch/chapters/90-crypto/rechnungen/tangent.maxima
@@ -0,0 +1,67 @@
+/*
+ * tangent.maxima
+ *
+ * (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule 
+ */
+
+p: Y^2+X*Y - X^3 - a*X -b;
+
+x: x1 + u * t;
+y: y1 + v * t;
+
+q: subst(x,X,p);
+q: subst(y,Y,q);
+q: ratsimp(expand(q));
+tex(q);
+tex(coeff(expand(q), t, 3));
+tex(coeff(expand(q), t, 2));
+tex(coeff(expand(q), t, 1));
+tex(coeff(expand(q), t, 0));
+qr: divide(q,t^2,t);
+r: qr[2];
+s: solve(qr[1] = 0, t);
+tex(s);
+
+T: subst(s, t);
+
+U: x1+2*y1;
+V: y1-3*x1^2-a;
+X: subst(U, u, x);
+Y: subst(V, v, y);
+T: subst(U, u, T);
+T: subst(V, v, T);
+ratsimp(expand(T));
+
+q: subst(U, u, q);
+q: subst(V, v, q);
+
+qr: divide(q,t^2,t);
+r: qr[2];
+q: qr[1];
+tex(q);
+
+tex(coeff(r, t, 3));
+tex(coeff(r, t, 2));
+tex(coeff(r, t, 1));
+tex(coeff(r, t, 0));
+
+subst(0,t,r);
+subst(0,t,diff(r,t));
+
+tex(r);
+
+polydecomp(qr[2], t);
+
+s: solve(q = 0, t);
+tex(s);
+
+/*
+x3: ratsimp(expand(subst(s, -X)));
+y3: ratsimp(expand(subst(s, -Y-X)));
+*/
+
+x3: ratsimp(expand(subst(s, X)));
+y3: ratsimp(expand(subst(s, Y)));
+
+tex(x3);
+tex(y3);
diff --git a/buch/chapters/90-crypto/rs.tex b/buch/chapters/90-crypto/rs.tex
new file mode 100644
index 0000000..ec8ec8c
--- /dev/null
+++ b/buch/chapters/90-crypto/rs.tex
@@ -0,0 +1,41 @@
+%
+% rs.tex -- Reed-Solomon-Code
+%
+% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil
+%
+\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}
+