From e0b1a2148f6eb58eb96804275f5795e3e8b6c863 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 26 Jul 2021 18:43:36 +0200 Subject: complete the crypto chapter --- buch/chapters/10-vektorenmatrizen/linear.tex | 9 +++ buch/chapters/50-permutationen/determinante.tex | 102 ++++++++++++++++++++++++ buch/chapters/50-permutationen/matrizen.tex | 5 +- buch/chapters/60-gruppen/symmetrien.tex | 4 +- buch/chapters/70-graphen/wavelets.tex | 2 +- buch/chapters/90-crypto/arith.tex | 1 + buch/chapters/90-crypto/ff.tex | 53 ++++++++++-- buch/chapters/references.bib | 7 ++ 8 files changed, 172 insertions(+), 11 deletions(-) (limited to 'buch') 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/}, -- cgit v1.2.1