complete the crypto chapter

8 files changed, 172 insertions, 11 deletions

diff --git a/buch/chapters/10-vektorenmatrizen/linear.tex b/buch/chapters/10-vektorenmatrizen/linear.tex
index 10b5a7e..e368364 100644
--- a/buch/chapters/10-vektorenmatrizen/linear.tex
+++ b/buch/chapters/10-vektorenmatrizen/linear.tex
@@ -1088,6 +1088,15 @@ für die Inverse einer Matrix der Form
 \eqref{buch:vektoren-und-matrizen:abeispiel:eqn1}.
 \end{beispiel}
 
+\subsubsection{Produktregel für die Determinante}
+Aus der Charakterisierung der Determinanten kann man auch ableiten,
+dass  die Produktregel 
+\[
+\det (AB) = \det(A) \cdot \det(B)
+\]
+gilt.
+Daraus folgt auch, dass $\det(A^{-1})=\det(A)^{-1}$.
+
 %
 % Lineare Abbildungen
 %
diff --git a/buch/chapters/50-permutationen/determinante.tex b/buch/chapters/50-permutationen/determinante.tex
index c440caf..805235d 100644
--- a/buch/chapters/50-permutationen/determinante.tex
+++ b/buch/chapters/50-permutationen/determinante.tex
@@ -7,3 +7,105 @@
 \section{Determinante
 \label{buch:section:determinante}}
 \rhead{Determinante}
+Das Signum einer Permutationsmatrizen lässt sich
+gemäss~\eqref{buch:permutationen:determinante}
+mit der Determinanten berechnen.
+Umgekehrt sollte es auch möglich sein, eine Formel
+für die Determinante zu finden.
+Die Basis dafür ist der
+Entwicklungssatz 
+\begin{equation}
+\det(A)
+=
+\sum_{i=1}^n (-1)^{i+j} a_{ij} \cdot \det(A_{ij})
+\label{buch:permutationen:entwicklungssatz}
+\end{equation}
+von Laplace für die Determinante.
+In den Produkten $a_{ij}\cdot\det(A_{ij})$ enthält 
+die Untermatrix $A_{ij}$ weder Elemente der Zeile $i$ noch der 
+Zeile $j$.
+Die Summanden auf der rechten Seite von
+\eqref{buch:permutationen:entwicklungssatz}
+sind daher Produkte der Form
+\[
+a_{1i_1}
+a_{2i_2}
+a_{3i_3}
+\dots
+a_{ni_n},
+\]
+in denen nur Faktoren aus verschiedenen Spalten der Matrix $A$
+vorkommen.
+Das ist gleichbedeutend damit, dass unter den Spaltenindizes
+$i_1,i_2,i_3,\dots,i_n$ keine zwei gleich sind, dass also
+\[
+\sigma
+=
+\begin{pmatrix}
+1&2&3&\dots&n\\
+i_1&i_2&i_3&\dots&i_n
+\end{pmatrix}
+\]
+eine Permutation ist.
+
+Die Determinante muss sich daher als Summe über alle Permutationen
+in der Form
+\begin{equation}
+\det(A)
+=
+\sum_{\sigma\in S_n} 
+c(\sigma)
+a_{1\sigma(1)}
+a_{2\sigma(2)}
+\dots
+a_{n\sigma(n)}
+\label{buch:permutationen:cformel}
+\end{equation}
+schreiben lassen, wobei die Koeffizienten $c(\sigma)$ noch zu bestimmen
+sind.
+Setzt man in
+\eqref{buch:permutationen:cformel}
+eine Permutationsmatrix $P_\tau$ ein, dann verschwinden alle
+Terme auf der rechten Seite ausser dem zur Permutation $\tau$,
+also
+\[
+\det(P_\tau)
+=
+\sum_{\sigma \in S_n}
+c(\sigma)
+(P_\tau)_{1\sigma(1)}
+(P_\tau)_{2\sigma(2)}
+\dots
+(P_\tau)_{n\sigma(n)}
+=
+c(\tau)
+1\cdot 1\cdot\dots\cdot 1
+=
+c(\tau).
+\]
+Der Koeffizientn $c(\tau)$ ist also genau das Vorzeichen
+der Permutation $\tau$.
+Damit erhalten wir den folgenden Satz:
+
+\begin{satz}
+Die Determinante einer $n\times n$-Matrix $A$ kann berechnet werden als
+\[
+\det(A)
+=
+\sum_{\sigma\in S_n}
+\operatorname{sgn}(\sigma)
+a_{1\sigma(1)}
+a_{2\sigma(2)}
+\dots
+a_{n\sigma(n)}
+=
+\sum_{\tau\in S_n}
+\operatorname{sgn}(\tau)
+a_{\tau(1)1}
+a_{\tau(2)2}
+\dots
+a_{\tau(n)n}.
+\]
+Insbesondere folgt auch $\det(A)=\det(A^t)$.
+\end{satz}
+
diff --git a/buch/chapters/50-permutationen/matrizen.tex b/buch/chapters/50-permutationen/matrizen.tex
index 7e55364..f7e9e31 100644
--- a/buch/chapters/50-permutationen/matrizen.tex
+++ b/buch/chapters/50-permutationen/matrizen.tex
@@ -181,7 +181,7 @@ Die Determinante einer solchen Permutationsmatrix ist
 Nach der Produktregel für die Determinante folgt für eine Darstellung
 der Permutation $\sigma=\tau_1\dots\tau_l$ als Produkt von Transpositionen,
 dass
-\[
+\begin{equation}
 \det P_{\sigma}
 =
 \det P_{\tau_1} \dots \det P_{\tau_l}
@@ -189,7 +189,8 @@ dass
 (-1)^l
 =
 \operatorname{sgn}(\sigma).
-\]
+\label{buch:permutationen:determinante}
+\end{equation}
 Das Vorzeichen einer Permutation ist also identisch mit der Determinante
 der zugehörigen Permutationsmatrix.
 
diff --git a/buch/chapters/60-gruppen/symmetrien.tex b/buch/chapters/60-gruppen/symmetrien.tex
index 7364c85..aee3b41 100644
--- a/buch/chapters/60-gruppen/symmetrien.tex
+++ b/buch/chapters/60-gruppen/symmetrien.tex
@@ -714,8 +714,8 @@ Kurve so zu definieren, dass dabei Längen und Winkel erhalten bleiben.
 Dieser Ansatz ist die Basis der Theorie der Krümmung sogenannter
 Riemannscher Mannigfaltigkeiten.
 
-\subsection{Der Satz von Noether
-\label{buch:subsection:noether}}
+%\subsection{Der Satz von Noether
+%\label{buch:subsection:noether}}
 
 
 
diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex
index ef1520e..8baa88c 100644
--- a/buch/chapters/70-graphen/wavelets.tex
+++ b/buch/chapters/70-graphen/wavelets.tex
@@ -10,7 +10,7 @@ In Abschnitt~\ref{buch:subsection:standardbasis-und-eigenbasis} wurde
 gezeigt dass die Standardbasis den Zusammenhang zwischen den einzelnen
 Teilen des Graphen völlig ignoriert, während die Eigenbasis Wellen
 beschreibt, die mit vergleichbarer Amplitude sich über den ganzen
-Graphen entsprechen.
+Graphen erstrecken.
 Die Eigenbasis unterdrückt also die ``Individualität'' der einzelnen
 Knoten fast vollständig.
 
diff --git a/buch/chapters/90-crypto/arith.tex b/buch/chapters/90-crypto/arith.tex
index dcc31b8..b05110f 100644
--- a/buch/chapters/90-crypto/arith.tex
+++ b/buch/chapters/90-crypto/arith.tex
@@ -91,6 +91,7 @@ Die Berechnung der Quadratwurzel lässt sich in Hardware effizient
 implementieren.
 
 \begin{algorithmus}
+\label{buch:crypto:teile-und-hersche}
 Der folgende Algorithmus berechnet $a^k$ in $O(\log_2(k))$
 Multiplikationen
 \begin{enumerate}
diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex
index 535b359..a1cb747 100644
--- a/buch/chapters/90-crypto/ff.tex
+++ b/buch/chapters/90-crypto/ff.tex
@@ -7,6 +7,15 @@
 \section{Kryptographie und endliche Körper
 \label{buch:section:kryptographie-und-endliche-koerper}}
 \rhead{Kryptographie und endliche Körper}
+In diesem Abschnitt soll illustriert werden, wie die Arithmetik in
+endlichen Körpern Algorithmen zu konstruieren erlaubt, mit denen sich
+zum Beispiel sehr effizient kryptographische Schlüssel aushandeln 
+lassen.
+Der klassische Diffie-Hellmann-Algorithmus in einem Galois-Körper
+$\mathbb{F}_p$ wird in Abschnitt~\ref{buch:subsection:elliptische-kurven}
+verallgemeinert auf eine sogenannte elliptische Kurve.
+Diese Version des Algorithmus ist sehr effizient was die Bitlänge der
+Schlüssel betrifft.
 
 \subsection{Potenzen in $\mathbb{F}_p$ und diskreter Logarithmus
 \label{buch:subsection:potenzen-diskreter-logarithmus}}
@@ -439,6 +448,7 @@ Das Polynom ist
 \[
 p(t)
 =
+XXX
 \]
 Nach Division durch $t(t-1)$ erhält man als den Quotienten
 \begin{align*}
@@ -652,13 +662,44 @@ 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
+Der klassische Diffie-Hellmann-Schlüsselalgorithmus in einem Körper
+$\mathbb{F}_p$ basiert darauf, dass man beliebige Potenzen eines 
+Elementes berechnen kann, und dass es schwierig ist, diese Operation
+umzukehren.
+Die Addition in $\mathbb{F}_p$ wird für diesen Algorithmus überhaupt
+nicht benötigt.
+
+In einer elliptischen Kurve gibt es ebenfalls eine Multiplikation,
+aus der sich mit dem 
+Algorithmus~\ref{buch:crypto:teile-und-hersche} eine effizienter
+Potenzieralgorithmus konstruieren lässt.
+
+Die im Internet Key Exchange Protokol
+in RFC 2409
+\cite{buch:rfc2409}
+definierte Oakley-Gruppe 4
+zum Beispiel verwendet einen Galois-Körper $\mathbb{F}_{2^{185}}$ 
+mit dem Minimalpolynom $m(x)=x^{185}+x^{69}+1\in \mathbb{F}_2[x]$
+und den Koeffizienten
+\begin{align*}
+a&=0\\
+b&=x^{12}+x^{11} + x^{10} + x^9 + x^7 + x^6 + x^5 + x^3 +1,
+\end{align*} 
+die die elliptische Kurve definieren.
+
+Als Elemente $g$ für den Diffie-Hellmann-Algorithmus wird ein Punkt
+der elliptischen Kurve verwendet, dessen $X$-Koordinaten durch das
+Polynom $g_x = x^4+x^3$ gegeben ist.
+Der Standard spezifiziert die $Y$-Koordinate nicht, diese kann aus
+den gegebenen Daten abgeleitet werden.
+Die entstehende Gruppe hat etwa $4.9040\cdot10^{55}$ Elemente, die
+für einen brute-force-Angriff durchprobiert werden müssten.
+
+
+
+
+
 
 
 
diff --git a/buch/chapters/references.bib b/buch/chapters/references.bib
index 59a8376..977bf81 100644
--- a/buch/chapters/references.bib
+++ b/buch/chapters/references.bib
@@ -39,6 +39,13 @@ abstract = "In this paper, we present Google, a prototype of a large-scale searc
 	year = {2016},
 }
 
+@online{buch:rfc2409,
+	title = {The Internet Key Exchange (IKE)},
+	author = { D. Harkins and D. Carrel},
+	url = {https://datatracker.ietf.org/doc/html/rfc2409},
+	year = {1998}
+}
+
 @online{buch:fftw,
 	title = {Fastest Fourier Transform in the West},
 	url = {http://www.fftw.org/},