diff options
author | Andreas Müller <andreas.mueller@ost.ch> | 2021-09-25 20:41:52 +0200 |
---|---|---|
committer | Andreas Müller <andreas.mueller@ost.ch> | 2021-09-25 20:41:52 +0200 |
commit | 39f232312a86c70c271f8edef77b233e1dd40c1c (patch) | |
tree | d63150486a2f97a810b63a8f3cdd4c3cb7afb851 | |
parent | zweite Lesung (diff) | |
download | SeminarMatrizen-39f232312a86c70c271f8edef77b233e1dd40c1c.tar.gz SeminarMatrizen-39f232312a86c70c271f8edef77b233e1dd40c1c.zip |
2. Lesung
22 files changed, 178 insertions, 164 deletions
diff --git a/buch/chapters/05-zahlen/komplex.tex b/buch/chapters/05-zahlen/komplex.tex index 2f9378d..2053326 100644 --- a/buch/chapters/05-zahlen/komplex.tex +++ b/buch/chapters/05-zahlen/komplex.tex @@ -63,7 +63,7 @@ ist \[ \mathbb{C} = -\{a+bi\;|\;a,b\in\mathbb{R}\} +\{a+bi \mid a,b\in\mathbb{R}\} \] mit den Rechenoperationen~\eqref{buch:zahlen:cregeln}. Die Menge $\mathbb{C}$ verhält sich daher wie eine zweidimensionaler @@ -340,7 +340,7 @@ i^2 = j^2 = k^2 = i\!jk = -1. \end{equation} Er nannte die Menge aller Linearkombinationen \[ -\mathbb{H} = \{ a_0+a_1i+a_2j+a_3k\;|\; a_l\in \mathbb{R}\} +\mathbb{H} = \{ a_0+a_1i+a_2j+a_3k \mid a_l\in \mathbb{R}\} \] die {\em Quaternionen}, die Einheiten $i$, $j$ und $k$ heissen auch \index{Quaternionen}% diff --git a/buch/chapters/10-vektorenmatrizen/gruppen.tex b/buch/chapters/10-vektorenmatrizen/gruppen.tex index 9a9bef3..d7c9266 100644 --- a/buch/chapters/10-vektorenmatrizen/gruppen.tex +++ b/buch/chapters/10-vektorenmatrizen/gruppen.tex @@ -98,7 +98,7 @@ Die Menge der invertierbaren Matrizen \operatorname{GL}_n(\Bbbk) = \{ -A\in M_n(\Bbbk)\;|\; \text{$A$ invertierbar} +A\in M_n(\Bbbk) \mid \text{$A$ invertierbar} \} \] ist bezüglich der Multiplikation eine Gruppe. @@ -224,7 +224,7 @@ Ist $\varphi\colon G\to H$ ein Homomorphisus, dann ist \[ \ker\varphi = -\{g\in G\;|\; \varphi(g)=e\} +\{g\in G \mid \varphi(g)=e\} \] eine Untergruppe. \index{Kern}% @@ -290,7 +290,7 @@ also $H$ ein Normalteiler ist. Für eine Gruppe $G$ mit Normalteiler $H\triangleleft G$ ist die Menge \[ -G/H = \{ gH \;|\; g\in G\} +G/H = \{ gH \mid g\in G\} \] eine Gruppe mit der Verknüpfung $g_1H\cdot g_2H=(g_1g_2)H$. $G/H$ heisst {\em Faktorgruppe} oder {\em Quotientengruppe}. diff --git a/buch/chapters/10-vektorenmatrizen/linear.tex b/buch/chapters/10-vektorenmatrizen/linear.tex index 33169bd..dcb2e8a 100755 --- a/buch/chapters/10-vektorenmatrizen/linear.tex +++ b/buch/chapters/10-vektorenmatrizen/linear.tex @@ -268,7 +268,7 @@ Sind $a_1,\dots,a_n\in V$ Vektoren, dann heisst die Menge \[ \langle a_1,\dots,a_n\rangle = -\{x_1a_1+\dots+x_na_n\;|\; x_1,\dots,x_n\in\Bbbk\} +\{x_1a_1+\dots+x_na_n \mid x_1,\dots,x_n\in\Bbbk\} \] aller Vektoren, die sich durch Linearkombination aus den Vektoren $a_1,\dots,a_n$ gewinnen lassen, der von $a_1,\dots,a_n$ @@ -403,7 +403,7 @@ M_{m\times n}(\Bbbk) = M_{m,n}(\Bbbk) = -\{ A\;|\; \text{$A$ ist eine $m\times n$-Matrix}\}. +\{ A \mid \text{$A$ ist eine $m\times n$-Matrix}\}. \] Falls $m=n$ gilt, heisst die Matrix $A$ auch {\em quadratisch}. \index{quadratische Matrix}% @@ -1412,7 +1412,7 @@ Ist $f$ eine lineare Abbildung $U\to V$, dann heisst die Menge \[ \ker f = -\{x\in U\;|\; f(x)=0\} +\{x\in U \mid f(x)=0\} \] der {\em Kern} oder {\em Nullraum} der linearen Abbildung $f$. \index{Kern}% @@ -1423,7 +1423,7 @@ Der Kern oder Nullraum der Matrix $A$ ist die Menge \[ \ker A = -\{ x\in\Bbbk^n \;|\; Ax=0\}. +\{ x\in\Bbbk^n \mid Ax=0\}. \] \end{definition} @@ -1446,12 +1446,12 @@ wie folgt. Ist $f\colon V\to U$ eine lineare Abbildung dann ist das Bild von $f$ der Unterraum \[ -\operatorname{im}f = \{ f(v)\;|\;v\in V\} \subset U +\operatorname{im}f = \{ f(v) \mid v\in V\} \subset U \] von $U$. Das {\em Bild} einer $m\times n$-Matrix $A$ ist die Menge \[ -\operatorname{im}A = \{ Av \;|\; v\in\Bbbk^n\} \subset \Bbbk^m. +\operatorname{im}A = \{ Av \mid v\in\Bbbk^n\} \subset \Bbbk^m. \] \end{definition} \index{Bild}% diff --git a/buch/chapters/10-vektorenmatrizen/ringe.tex b/buch/chapters/10-vektorenmatrizen/ringe.tex index 6c7e091..33626bf 100644 --- a/buch/chapters/10-vektorenmatrizen/ringe.tex +++ b/buch/chapters/10-vektorenmatrizen/ringe.tex @@ -119,7 +119,7 @@ Die Menge \[ \mathbb{Z} + i\mathbb{Z} = -\{a+bi\;|\; a,b\in\mathbb{Z}\} +\{a+bi \mid a,b\in\mathbb{Z}\} = \mathbb{Z}[i] \subset @@ -181,7 +181,7 @@ Die Menge der invertierbaren Elemente verdient einen besonderen Namen. \begin{definition} Ist $R$ ein Ring mit Eins, dann heissen die Elemente von \[ -U(R) = \{ r\in R \;|\; \text{$r$ in $R$ invertierbar}\}. +U(R) = \{ r\in R \mid \text{$r$ in $R$ invertierbar}\}. \] die {\em Einheiten} von $R$. \index{Einheit}% @@ -267,7 +267,7 @@ ist und ausserdem gilt \] Der Kern ist die Menge \[ -\ker\varphi = \{ r\in R\;|\; \varphi(r)=0\} +\ker\varphi = \{ r\in R \mid \varphi(r)=0\} \] \index{Kern}% \end{definition} diff --git a/buch/chapters/20-polynome/definitionen.tex b/buch/chapters/20-polynome/definitionen.tex index 659a972..b4e7b26 100644 --- a/buch/chapters/20-polynome/definitionen.tex +++ b/buch/chapters/20-polynome/definitionen.tex @@ -41,7 +41,7 @@ Die Menge R[X] = \{ -p(X) = a_nX^n+a_{n-1}X^{n-1} + \dots a_1X+a_0\;|\; a_k\in R, n\in\mathbb{N} +p(X) = a_nX^n+a_{n-1}X^{n-1} + \dots a_1X+a_0 \mid a_k\in R, n\in\mathbb{N} \} \] heisst die Menge der {\em Polynome} mit Koeffizienten in $R$ @@ -266,7 +266,7 @@ bilden die Teilmenge \[ R^{(n)}[X] = -\{ p\in R[X]\;|\; \deg p \le n\}. +\{ p\in R[X] \mid \deg p \le n\}. \] Die Mengen $R^{(n)}[X]$ bilden eine {\em Filtrierung} des Polynomrings $R[X]$, d.~h.~sie sind ineinander geschachtelt @@ -288,7 +288,7 @@ R^{(-\infty)}[X] & \subset \\[3pt] \{0\} & \subset & R & \subset - & \{a_1X+a_0\;|a_k\in R\} & \subset & \dots & + & \{a_1X+a_0 \mid a_k\in R\} & \subset & \dots & \end{array} \] und ihre Vereinigung ist $R[X]$. diff --git a/buch/chapters/20-polynome/vektoren.tex b/buch/chapters/20-polynome/vektoren.tex index e494477..535b896 100644 --- a/buch/chapters/20-polynome/vektoren.tex +++ b/buch/chapters/20-polynome/vektoren.tex @@ -51,7 +51,7 @@ Die Abbildung $\varphi$ ist also ein Isomorphismus \[ \varphi \colon -\{p\in R[X]\;|\; \deg(p) \le n\} +\{p\in R[X] \mid \deg(p) \le n\} \overset{\cong}{\to} R^{n+1} \] diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex index 8052d4c..c968f1d 100644 --- a/buch/chapters/30-endlichekoerper/wurzeln.tex +++ b/buch/chapters/30-endlichekoerper/wurzeln.tex @@ -219,7 +219,7 @@ Als Menge ist daher \Bbbk(\alpha) = \{ -a_0+a_1\alpha+a_2\alpha^2+\dots+a_{n-1}\alpha^{n-1}\;|\; a_i\in\Bbbk\} +a_0+a_1\alpha+a_2\alpha^2+\dots+a_{n-1}\alpha^{n-1} \mid a_i\in\Bbbk\} \] ausreichend. Die Addition von solchen Ausdrücken und die Multiplikation mit Skalaren diff --git a/buch/chapters/40-eigenwerte/grundlagen.tex b/buch/chapters/40-eigenwerte/grundlagen.tex index 2ecba95..fa924c8 100644 --- a/buch/chapters/40-eigenwerte/grundlagen.tex +++ b/buch/chapters/40-eigenwerte/grundlagen.tex @@ -83,9 +83,9 @@ Wegen = \operatorname{im} A^{k-1} A = -\{ A^{k-1} Av\;|\; v \in \Bbbk^n\} +\{ A^{k-1} Av \mid v \in \Bbbk^n\} \subset -\{ A^{k-1} v\;|\; v \in \Bbbk^n\} +\{ A^{k-1} v \mid v \in \Bbbk^n\} = \mathcal{J}^{k-1}(A) \] @@ -275,7 +275,7 @@ selbst. Ein Unterraum $U\subset V$ heisst {\em invarianter Unterraum}, wenn \[ -f(U) = \{ f(x)\;|\; x\in U\} \subset U +f(U) = \{ f(x) \mid x\in U\} \subset U \] gilt. \index{invarianter Unterraum}% diff --git a/buch/chapters/40-eigenwerte/spektraltheorie.tex b/buch/chapters/40-eigenwerte/spektraltheorie.tex index 1023d20..0617fe5 100644 --- a/buch/chapters/40-eigenwerte/spektraltheorie.tex +++ b/buch/chapters/40-eigenwerte/spektraltheorie.tex @@ -252,7 +252,7 @@ Wir betrachten einen Kreis in der Ebene, also die Menge \[ S^1 = -\{(x_1,x_2)\;|\; x_1^2 + x_2^2=1\} +\{(x_1,x_2) \mid x_1^2 + x_2^2=1\} \] $S^1$ ist eine abgeschlossene und beschränkte Menge in $\mathbb{R}^2$. Die Funktion $x\mapsto x_1$ trennt die Punkte nicht, denn zu jedem @@ -390,7 +390,7 @@ Funktionen in $A$ beliebig genau durch eine monoton wachsende Folge von Funktionen approximieren. Da $A$ eine Algebra ist, ist $f^2\in A$. -Sei ausserdem $m^2=\sup \{f(x)^2\;|\;x\in K\}$, so dass $f^2/m^2$ eine Funktion +Sei ausserdem $m^2=\sup \{f(x)^2 \mid x\in K\}$, so dass $f^2/m^2$ eine Funktion mit Werten im Intervall $[0,1]$ ist. Die Funktionen $f_n(x)=mu_n(f(x)^2/m^2)$ sind ebenfalls in $A$, bilden eine monoton wachsende Folge von Funktionen und @@ -543,7 +543,7 @@ in $\mathbb{C}[z]$} Der Satz~\ref{buch:satz:stone-weierstrass} von Stone-Weierstrass für reelle Funktionen gilt nicht für komplexe Funktionen. In diesem Abschnitt zeigen wir, dass sich die Funktion $z\mapsto\overline{z}$ -auf der Einheitskreisscheibe $K=\{z\in\mathbb{C}\;|\; |z|\le 1\}$ nicht +auf der Einheitskreisscheibe $K=\{z\in\mathbb{C} \mid |z|\le 1\}$ nicht gleichmässig durch Polynome $p(z)$ mit komplexen Koeffizienten approximieren lässt. Sei also $p_n(z)$ eine Folge von Polynomen, die auf der Einheitskreisscheibe diff --git a/buch/chapters/50-permutationen/endlich.tex b/buch/chapters/50-permutationen/endlich.tex index 3fa6aa7..24ed053 100644 --- a/buch/chapters/50-permutationen/endlich.tex +++ b/buch/chapters/50-permutationen/endlich.tex @@ -120,7 +120,7 @@ Z_i = \{ s_i, \sigma(s_i), \sigma(\sigma(s_i)), \dots \} = -\{\sigma^k(s_i)\;|\; k\ge 0\}. +\{\sigma^k(s_i) \mid k\ge 0\}. \] \item Falls $\bigcup_{j\le i} Z_j\ne [n]$, erhöhe $i$ um $1$ und fahre diff --git a/buch/chapters/50-permutationen/transpositionen.tex b/buch/chapters/50-permutationen/transpositionen.tex index dcbf2e0..222a7cc 100644 --- a/buch/chapters/50-permutationen/transpositionen.tex +++ b/buch/chapters/50-permutationen/transpositionen.tex @@ -104,7 +104,7 @@ Die Teilmenge A_n = \{ -\sigma\in S_n\;|\; \operatorname{sgn}(\sigma)=1 +\sigma\in S_n \mid \operatorname{sgn}(\sigma)=1 \} = \ker \operatorname{sgn} diff --git a/buch/chapters/60-gruppen/lie-gruppen.tex b/buch/chapters/60-gruppen/lie-gruppen.tex index 9f0c26f..76fa0ee 100644 --- a/buch/chapters/60-gruppen/lie-gruppen.tex +++ b/buch/chapters/60-gruppen/lie-gruppen.tex @@ -12,7 +12,7 @@ Die Gruppe \[ \operatorname{GL}_n(\mathbb{R}) = -\{ A \in M_n(\mathbb{R})\;|\; \det A \ne 0\} +\{ A \in M_n(\mathbb{R}) \mid \det A \ne 0\} \] besteht aus den Matrizen, deren Determinante nicht $0$ ist. Da die Menge der Matrizen mit $\det A=0$ eine abgeschlossene Menge @@ -266,7 +266,7 @@ Jede komplexe Zahl $z$ vom Betrag $1$ kann geschrieben werden in der Form $z=e^{i\alpha}$. Die Abbildung $f$ ist also eine Parametrisierung des Einheitskreises in der Ebene. -Wir bezeichen $S^1=\{z\in\mathbb{C}\;|\; |z|=1\}$ die komplexen Zahlen vom +Wir bezeichen $S^1=\{z\in\mathbb{C} \mid |z|=1\}$ die komplexen Zahlen vom Betrag $1$. $S^1$ ist eine Gruppe bezüglich der Multiplikation, da für alle Zahlen $z,w\in S^1$ gilt @@ -479,7 +479,7 @@ daher aus den Matrizen \[ \operatorname{O}(n) = -\{ A\in M_n(\mathbb{R})\;|\; AA^t=I\}. +\{ A\in M_n(\mathbb{R}) \mid AA^t=I\}. \] Die Matrixgleichung $AA^t=I$ liefert $n(n+1)/2$ unabhängige Bedingungen, die die orthogonalen Matrizen innerhalb der $n^2$-dimensionalen diff --git a/buch/chapters/60-gruppen/symmetrien.tex b/buch/chapters/60-gruppen/symmetrien.tex index ece02b5..3db4873 100644 --- a/buch/chapters/60-gruppen/symmetrien.tex +++ b/buch/chapters/60-gruppen/symmetrien.tex @@ -499,22 +499,22 @@ Die Projektionen auf die einzelnen Koordinaten liefern die folgenden vier Karten: \begin{align*} \color{red} -\varphi_1&{\color{red}\colon U_{x>0}=\{(x,y)\;|\;x^2+y^2=1\wedge x>0\}}\to\mathbb{R} +\varphi_1&{\color{red}\colon U_{x>0}=\{(x,y) \mid x^2+y^2=1\wedge x>0\}}\to\mathbb{R} : (x,y) \mapsto y \\ \color{blue} -\varphi_2&{\color{blue}\colon U_{x<0}=\{(x,y)\;|\;x^2+y^2=1\wedge x<0\}}\to\mathbb{R} +\varphi_2&{\color{blue}\colon U_{x<0}=\{(x,y) \mid x^2+y^2=1\wedge x<0\}}\to\mathbb{R} : (x,y) \mapsto y \\ \color{darkgreen} -\varphi_3&{\color{darkgreen}\colon U_{y>0}=\{(x,y)\;|\;x^2+y^2=1\wedge y>0\}}\to\mathbb{R} +\varphi_3&{\color{darkgreen}\colon U_{y>0}=\{(x,y) \mid x^2+y^2=1\wedge y>0\}}\to\mathbb{R} : (x,y) \mapsto x \\ \color{orange} -\varphi_4&{\color{orange}\colon U_{y<0}=\{(x,y)\;|\;x^2+y^2=1\wedge y<0\}}\to\mathbb{R} +\varphi_4&{\color{orange}\colon U_{y<0}=\{(x,y) \mid x^2+y^2=1\wedge y<0\}}\to\mathbb{R} : (x,y) \mapsto x \end{align*} @@ -588,7 +588,7 @@ die Kreislinie (Abbildung~\ref{buch:gruppen:fig:kartenkreis}). Ganz analog zum vorangegangenen Beispiel über die Kreisline lässt sich für eine $n$-di\-men\-sio\-nale Sphäre \[ -S^n = \{ (x_1,\dots,x_{n+1})\;|\; x_0^2+\dots+x_n^2=1\} +S^n = \{ (x_1,\dots,x_{n+1}) \mid x_0^2+\dots+x_n^2=1\} \] immer ein Atlas aus $2^{n+1}$ Karten mit den Koordinatenabbildungen \[ @@ -596,7 +596,7 @@ immer ein Atlas aus $2^{n+1}$ Karten mit den Koordinatenabbildungen \colon U_{i,\pm} = -\{p\in S^n\;|\; \pm x_i >0\} +\{p\in S^n \mid \pm x_i >0\} \to \mathbb{R}^n : diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index 5bae074..932a003 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -387,7 +387,7 @@ noch den Wert der Beschriftung enthalten. Ein gerichteter Graph mit beschrifteten Kanten ist eine Menge $V$ von Knoten und eine Menge von beschrifteten Kanten der Form \[ -E \{ (u,v,l)\in V^2\times L\;|\; \text{Eine Kante mit Beschriftung $l$ führt von $u$ nach $v$}\}. +E \{ (u,v,l)\in V^2\times L \mid \text{Eine Kante mit Beschriftung $l$ führt von $u$ nach $v$}\}. \] Die Menge $L$ enthält die möglichen Beschriftungen der Kanten. \end{definition} diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex index c453eb9..e259512 100644 --- a/buch/chapters/70-graphen/wavelets.tex +++ b/buch/chapters/70-graphen/wavelets.tex @@ -303,7 +303,7 @@ Frequenzskala identifizieren können. \begin{definition} \label{buch:graphen:def:frame} Ein Frame des Vektorraumes $\mathbb{R}^n$ ist eine Menge -$F=\{e_k\;|\; k=1,\dots,N\}$ von Vektoren mit der Eigenschaft +$F=\{e_k \mid k=1,\dots,N\}$ von Vektoren mit der Eigenschaft \begin{equation} A\|v\|^2 \le diff --git a/buch/chapters/80-wahrscheinlichkeit/positiv.tex b/buch/chapters/80-wahrscheinlichkeit/positiv.tex index 4e57fe0..4b86e00 100644 --- a/buch/chapters/80-wahrscheinlichkeit/positiv.tex +++ b/buch/chapters/80-wahrscheinlichkeit/positiv.tex @@ -688,7 +688,7 @@ dann ist = \langle u\rangle \oplus -\{ x\in\mathbb{R}^n\;|\; px=0\} +\{ x\in\mathbb{R}^n \mid px=0\} = \langle u\rangle \oplus diff --git a/buch/chapters/90-crypto/aes.tex b/buch/chapters/90-crypto/aes.tex index f726e24..0ece6b1 100644 --- a/buch/chapters/90-crypto/aes.tex +++ b/buch/chapters/90-crypto/aes.tex @@ -9,7 +9,7 @@ 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 +entstehen könnte, dass sich dahinter nicht 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. @@ -51,12 +51,13 @@ Elemente eines endlichen Körpers $\mathbb{F}_{2^8}$ interpretiert werden. \subsubsection{Bytes als Elemente von $\mathbb{F}_{2^8}$} Das Polynom $m(X)=X^8+X^4+X^3+X+1\in \mathbb{F}_2[X]$ ist irreduzibel, somit ist $\mathbb{F}_{2^8} = \mathbb{F}_2[X]/(m)$ ein Körper. -Die Elemente können dargestellt werden als Polynome, das Byte -$\texttt{63}_{16}$ bekommt die Form +Die Elemente können dargestellt werden als Polynome \[ p(X) = p_7X^7 + p_6X^6 + \dots + p_2X^2+p_1X + p_0, \] sie bestehen daher aus den $8$ Bits $p_7,\dots,p_0$. +Das Byte $\texttt{63}_{16}$ entspricht also dem Polynom +$X^6+X^5+X+1$ in $\mathbb{F}_2[X]/(m)$. Die Interpretation der Bytes als Elemente eines Körpers bedeutet, dass jede Multiplikation mit einem nicht verschwindenden Byte @@ -66,7 +67,7 @@ undurchsichtige, aber umkehrbare Art durcheinander, wie dies für ein Verschlüsselungsverfahren wünschenswert ist. \subsubsection{$S$-Box} -Für die Operation der $S$-Box wird wie folgt zusammengesetzt. +Für die Operation der sogenannten $S$-Box wird wie folgt zusammengesetzt. Zunächst wird ein Byte $x$ durch das zugehörige multiplikative inverse Element \[ @@ -135,7 +136,7 @@ Die $S$-Box-Operation kann also vektoriell geschrieben werden als Die Implementation ist möglicherweise mit einer Tabelle am schnellsten, es sind ja nur 256 Bytes im Definitionsbereich der $S$-Box-Abbildung -und ebenso nur 256 möglich Werte. +und ebenso nur 256 mögliche Werte. \subsection{Block-Operationen \label{buch:subsection:block-operationen}} @@ -171,8 +172,8 @@ untereinander gut gemischt werden. Die bisher beschriebenen Operationen operieren immer nur auf einzelnen Bytes während die im nächsten Abschnitt beschriebene Spalten-Mischoperation -nur auf Spalten wird. -Die Zeilenmischoperation permutiert die Zeilen in den vier Zeilen +nur auf Spalten wirkt. +Die Zeilen\-misch\-ope\-ra\-tion permutiert die Zeilen in den vier Zeilen eines Blocks zyklisch, die erste Zeile bleibt an Ort, die zweite Zeile wird um ein Byte rotiert, die dritte um zwei und die letzte um 3 Bytes, wie in Abbildung~\ref{buch:crypto:fig:shift} @@ -342,7 +343,7 @@ macht. \subsubsection{Schlüsseladdition} Nach jeder Spaltenmischoperation wird ein Rundenschlüssel -zum Blockhinzuaddiert. +zum Block hinzuaddiert. Beim ersten Mal wird dazu einfach das vom Benutzer vorgegebene Schlüsselmaterial verwendet. Für die folgenden Runden muss aus diesem Schlüssel neues @@ -366,10 +367,10 @@ Die Erzeugung der Rundenschlüssel ist in Abbildung schematisch dargestellt. Die Blöcke beschreiben wieder Spaltenvektoren im vierdimensionalen Raum $\mathbb{F}_{2^8}^4$. -Die Blöcke $K_0$ bis $K_7$ stellen den ursprünglichen Schlüssel dar. +Die Blöcke $K_0$ bis $K_7$ enthalten den ursprünglichen Schlüssel. Die Erzeugung eines neuen Blocks Schlüsselmatrial beginnt damit, -dass der letzte Vektor des vorangegangenblocks drei Operationen -unterworfen werden. +dass der letzte Vektor des vorangegangen Blocks drei Operationen +unterworfen wird. \begin{itemize} \item Die Operation $\pi$ vertauscht die Bytes des Vektors zyklisch: @@ -401,9 +402,10 @@ Die Operation $\pi$ vertauscht die Bytes des Vektors zyklisch: \end{tikzpicture} \end{center} \item -Die $S$-Operation wendet die $S$-Box auf alle Bytes eines Vektors an. +Die $S$-Operation wendet die $S$-Box auf jedes Byte eines Vektors an. \item -Die $r_i$ Operation addiert in Runde $i$ eine Konstante $r_i$ zur $0$-Komponente. +Die $r_i$ Operation addiert in Runde $i$ eine Konstante $r_i$ zur +$0$-Komponente. \end{itemize} Die Konstante $r_i$ ist wieder ein einzelnes Byte und es ist daher naheliegend, diese Bytes mit Hilfe der Arithmetik in $\mathbb{F}_{2^8}$ diff --git a/buch/chapters/90-crypto/arith.tex b/buch/chapters/90-crypto/arith.tex index d140489..4b0828b 100644 --- a/buch/chapters/90-crypto/arith.tex +++ b/buch/chapters/90-crypto/arith.tex @@ -24,7 +24,7 @@ Bei der Verschlüsselung grosser Datenmengen wie zum Beispiel bei der Verschlüsselung ganzer Harddisks mit Hilfe des AES-Algorithmus kommt es auf die Geschwindigkeit auch der elementarsten Operationen in den endlichen Körpern an. -Solche Methoden werden in den Abschnitten +Dafür geeignete Methoden werden in den Abschnitten \ref{buch:subsection:rechenoperationen-in-fp} und \ref{buch:subsection:rechenoperatione-in-f2l} @@ -40,11 +40,11 @@ sein, dies wird zum Beispiel in Implementationen der Potenzfunktion in Programmierbibliotheken verwendet. Für kryptographische Anwendungen ist $G$ die multiplikative Gruppe eines endlichen Körpers oder eine elliptische Kurve -(siehe Abschnitt~\ref{buch:subsection:elliptische-kurven}). +(siehe Abschnitt~\ref{buch:section:elliptische-kurven}). Zur Berechnung von $a^k$ in $\mathbb{F}_p$ sind bei einer naiven Vorgehen $k-1$ Multiplikationen nötig, immer sofort gefolgt -von einer Reduktion $\mod p$ um sicherzustellen, dass die Resultate +von einer Reduktion modulo $p$ um sicherzustellen, dass die Resultate nicht zu gross werden. Ist $l$ die Anzahl der Binärstellen von $k$, dann benötigt dieser naive Algorithmus $O(2^l)$ Operationen, die Laufzeit wächst @@ -127,44 +127,19 @@ werden also genau $5$ Multiplikationen ausgeführt statt die 16 Multiplikationen, die bei der naiven Vorgehensweise nötig wären. \end{beispiel} + \subsection{Rechenoperationen in $\mathbb{F}_p$ \label{buch:subsection:rechenoperationen-in-fp}} Die Multiplikation macht aus zwei Faktoren $a$ und $b$ ein Resultat mit Bitlänge $\log_2 a+\log_2 b$, die Bitlänge wird -also typischerweise verdoppelt. -In $\mathbb{F}_p$ muss anschliessend das Resultat $\mod p$ +also typischerweise ungefähr verdoppelt. +In $\mathbb{F}_p$ muss anschliessend das Resultat modulo $p$ reduziert werden, so dass die Bitlänge wieder höchstens $\log_2p$ ist. In folgenden soll gezeigt werden, dass dieser Speicheraufwand für eine Binärimplementation deutlich reduziert werden kann, wenn die Reihenfolge der Operationen modifiziert wird. -Für die Multiplikation von $41\cdot 47$ rechnet man im Binärsystem -\begin{center} -\begin{tabular}{>{$}r<{$}} -\texttt{{\color{darkgreen}1}0{\color{red}1}001}\cdot\texttt{101111}\\ -\hline -\texttt{101111}\\ -\texttt{{\color{red}101111}\phantom{000}}\\ -\texttt{{\color{darkgreen}101111}\phantom{00000}}\\ -\hline -\texttt{11110000111}\\ -\hline -\end{tabular} -\end{center} -In $\mathbb{F}_{53}$ muss im Anschluss Modulo $p=53$ reduziert werden. - -Der Speicheraufwand entsteht zunächst dadurch, dass durch die Multiplikation -mit $2$ die Summanden immer länger werden. -Man kann den die Sumanden kurz halten, indem man jedesmal, wenn -der Summand nach der Multiplikation mit $2$ grösser als $p$ geworden ist, -$p$ subtrahiert (Abbildung~\ref{buch:crypto:fig:reduktion}). -Ebenso kann bei nach jeder Addition das bereits reduzierten zweiten -Faktors wieder reduziert werden. -Die Anzahl der nötigen Reduktionsoperationen wird durch diese -frühzeitig durchgeführten Reduktionen nicht teurer als bei der Durchführung -des Divisionsalgorithmus. - \begin{figure} \begin{center} \begin{tabular}{>{$}r<{$}>{$}r<{$}>{$}r<{$}|>{$}r<{$}>{$}r<{$}>{$}r<{$}} @@ -201,12 +176,48 @@ Divisionsalgorithmus. \label{buch:crypto:fig:reduktion}} \end{figure} +Für die Multiplikation von $41\cdot 47$ rechnet man im Binärsystem +\begin{center} +\begin{tabular}{>{$}r<{$}} +\texttt{{\color{darkgreen}1}0{\color{red}1}001}\cdot\texttt{101111}\\ +\hline +\texttt{101111}\\ +\texttt{{\color{red}101111}\phantom{000}}\\ +\texttt{{\color{darkgreen}101111}\phantom{00000}}\\ +\hline +\texttt{11110000111}\\ +\hline +\end{tabular} +\end{center} +In $\mathbb{F}_{53}$ muss im Anschluss Modulo $p=53$ reduziert werden. + +Der Speicheraufwand entsteht zunächst dadurch, dass durch die Multiplikation +mit $2$ die Summanden immer länger werden. +Man kann den die Sumanden kurz halten, indem man jedesmal, wenn +der Summand nach der Multiplikation mit $2$ grösser als $p$ geworden ist, +$p$ subtrahiert (Abbildung~\ref{buch:crypto:fig:reduktion}). +Ebenso kann nach jeder Addition des bereits reduzierten zweiten +Faktors wieder reduziert werden. +Die Anzahl der nötigen Reduktionsoperationen wird durch diese +frühzeitig durchgeführten Reduktionen nicht teurer als bei der Durchführung +des Divisionsalgorithmus. + + Es ist also möglich, mit gleichem Aufwand an Operationen -aber mit halbe Speicherplatzbedarf die Multiplikationen in $\mathbb{F}_p$ +aber mit halbem Speicherplatzbedarf die Multiplikationen in $\mathbb{F}_p$ durchzuführen. Die Platzeinsparung ist besonders bei Implementationen in Hardware hilfreich, wo on-die Speicherplatz teuer sein kann. +\begin{figure} +\centering +\includegraphics{chapters/90-crypto/images/schieberegister.pdf} +\caption{Implementation der Multiplikation mit $X$ in einem +endlichen Körper $\mathbb{F}_{2^l}$ mit dem Minimalpolynom +$m(X) = X^8+X^4+X^3+X^+1$ als Feedback-Schieberegister. +\label{buch:crypto:fig:schieberegister}} +\end{figure} + \subsection{Rechenoperationen in $\mathbb{F}_{2^l}$ \label{buch:subsection:rechenoperatione-in-f2l}} Von besonderem praktischem Interesse sind die endlichen Körper @@ -214,6 +225,19 @@ $\mathbb{F}_{2^l}$. Die arithmetischen Operationen in diesen Körpern lassen sich besonders effizient in Hardware realisieren. +\begin{figure} +\centering +\includegraphics[width=\textwidth]{chapters/90-crypto/images/multiplikation.pdf} +\caption{Multiplikation zweier Elemente von $\mathbb{F}_{2^l}$. +Mit Hilfe des Schieberegisters am linken Rand werden die Produkte +$X\cdot p(X)$, $X^2\cdot p(X),\dots,X^7\cdot p(X)$ nach der in +Abbildung~\ref{buch:crypto:fig:schieberegister} dargestellten +Methode berechnet. +Am rechten Rand werden diejenigen $X^k\cdot p(X)$ aufaddiert, +für die der $X^k$-Koeffizient von $q(X)$ von $0$ verschieden ist. +\label{buch:crypto:fig:multiplikation}} +\end{figure} + \subsubsection{Zahldarstellung} Ein endlicher Körper $\mathbb{F}_{2^l}$ ist definiert durch ein irreduzibles Polynom in $\mathbb{F}_2[X]$ vom Grad $2^l$ @@ -229,9 +253,11 @@ dargestellt werden, also durch \[ a = a_{l-1}X^{l-1} + a_{l-2}X^{l-2} +\dots + a_2X^2 + a_1X + a_0. \] -In einer Maschine kann eine Zahl also als eine Bitfolge der Länge $l$ +In einer Maschine kann ein Elemente von $\mathbb{F}_2[X]/(m)$ +also als eine Bitfolge der Länge $l$ dargestellt werden. + \subsubsection{Addition} Die Addition in $\mathbb{F}_2$ ist in Hardware besonders leicht zu realisieren. @@ -243,9 +269,10 @@ Die Addition von zwei Elemente von $\mathbb{F}_{2^l}$ kann also durch die bitweise XOR-Verknüpfung der Darstellungen der Summanden erfolgen. Diese Operation ist in einem einzigen Maschinenzyklus realisierbar. -Die Subtraktion, die für die Reduktionsoperation module $m(X)$ nötig +Die Subtraktion, die für die Reduktionsoperation modulo $m(X)$ nötig ist, ist mit der Addition identisch. + \subsubsection{Multiplikation} Die Multiplikation zweier Polynome benötigt zunächst die Multiplikation mit $X$, wodurch der Grad des Polynoms ansteigt und möglicherweise so @@ -255,15 +282,6 @@ nicht $0$ ist. Der Koeffizient kann dann zum Verschwinden gebracht werden, indem $m(X)$ addiert wird. -\begin{figure} -\centering -\includegraphics{chapters/90-crypto/images/schieberegister.pdf} -\caption{Implementation der Multiplikation mit $X$ in einem -endlichen Körper $\mathbb{F}_{2^l}$ mit dem Minimalpolynom -$m(X) = X^8+X^4+X^3+X^+1$ als Feedback-Schieberegister. -\label{buch:crypto:fig:schieberegister}} -\end{figure} - In Abbildung~\ref{buch:crypto:fig:schieberegister} wird gezeigt, wie die Reduktion erfolgt, wenn die Multiplikation mit $X$, also der Shift nach links, einen Überlauf ergibt. @@ -274,25 +292,13 @@ $X^4+X^3+X+1$ ersetzen und addieren kann. Ein Produkt $p(X)\cdot q(X)$, wobei $p(X)$ und $q(X)$ Repräsentaten von Elementen $\mathbb{F}_{2^l}$ sind, kann jetzt wie folgt berechnet werden. -Mit dem Schieberegister werden die Vielfachen $X^k\cdot p(X)$ +Mit einem Schieberegister werden die Vielfachen $X^k\cdot p(X)$ für $k=0,\dots,l-1$ berechnet. Diejenigen Vielfachen, für die der Koeffizient von $X^k$ in $q(X)$ von $0$ verschieden ist werden aufsummiert und ergeben das Produkt. Der Prozess in Abbildung~\ref{buch:crypto:fig:multiplikation} dargestellt. -\begin{figure} -\centering -\includegraphics[width=\textwidth]{chapters/90-crypto/images/multiplikation.pdf} -\caption{Multiplikation zweier Elemente von $\mathbb{F}_{2^l}$. -Mit Hilfe des Schieberegisters am linken Rand werden die Produkte -$X\cdot p(X)$, $X^2\cdot p(X),\dots,X^7\cdot p(X)$ nach der in -Abbildung~\ref{buch:crypto:fig:schieberegister} dargestellten -Methode berechnet. -Am rechten Rand werden diejenigen $X^k\cdot p(X)$ aufaddiert, -für die der $X^k$-Koeffizient von $q(X)$ von $0$ verschieden ist. -\label{buch:crypto:fig:multiplikation}} -\end{figure} diff --git a/buch/chapters/90-crypto/chapter.tex b/buch/chapters/90-crypto/chapter.tex index 829a718..d7e248a 100644 --- a/buch/chapters/90-crypto/chapter.tex +++ b/buch/chapters/90-crypto/chapter.tex @@ -15,7 +15,7 @@ Die Eigenschaften dieser Körper sind reichhaltig genug, um kryptographisch 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. +In diesem Abschnitt soll dies an einigen Beispielen illustriert werden. \input{chapters/90-crypto/arith.tex} \input{chapters/90-crypto/ff.tex} diff --git a/buch/chapters/90-crypto/elliptisch.tex b/buch/chapters/90-crypto/elliptisch.tex index 99ed4cd..f5bf579 100644 --- a/buch/chapters/90-crypto/elliptisch.tex +++ b/buch/chapters/90-crypto/elliptisch.tex @@ -11,11 +11,11 @@ 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, fir die -die Gleichung $a^x=b$ schwierig zu lösen ist. +die Gleichung $a^x=b$ schwierig nach $x$ aufzulösen ist. Ein Halbgruppe 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. +$S^1=\{z\in\mathbb{C} \mid |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. @@ -42,7 +42,7 @@ 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. +über endlichen Körpern genau die verlangten Eigenschaften haben. \subsection{Definition} Elliptische Kurven sind Lösungen einer Gleichung der Form @@ -70,7 +70,7 @@ die Menge \[ E_{a,b}(\Bbbk) = -\{(X,Y)\in\Bbbk^2\;|\;Y^2+XY=X^3+aX+b\}, +\{(X,Y)\in\Bbbk^2 \mid Y^2+XY=X^3+aX+b\}, \] für $a,b\in\Bbbk$. \end{definition} @@ -150,7 +150,7 @@ Abbildung~\ref{buch:crypto:fig:elliptischekurve} zeigt eine elliptische Kurve in der Ebene $\mathbb{R}^2$. \subsection{Geometrische Definition der Gruppenoperation} -In der speziellen Form \ref{buch:crypto:ellvereinfacht} ist die +In der speziellen Form \eqref{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. @@ -165,7 +165,7 @@ 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 +auf der elliptischen Kurve indem man 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. @@ -186,10 +186,10 @@ Punkte die gleiche $u$-Koordinaten haben. \subsection{Gruppenoperation, algebraische Konstruktion} Nach den geometrischen Vorarbeiten zur Definition der Gruppenoperation -kann können wir die Konstruktion jetzt algebraisch über einem +können wir jetzt die Konstruktion algebraisch über einem beliebigen Körper umsetzen. -Wir gehen jetzt wieder von der elliptischen Kurve in der Form +Wir gehen wieder von der elliptischen Kurve in der Form \begin{equation} Y^2+XY=X^3+aX+b \label{buch:crypto:eqn:grupopgl} @@ -377,7 +377,7 @@ 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 +Die Werte $u$ und $v$ 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 @@ -490,7 +490,7 @@ Diffie-Hellmann-ähnlichen Verfahrens, wird das neutrale Element nicht wirklich benötigt. Um den Potenz-Algorithmus~\ref{buch:crypto:teile-und-hersche} durchzuführen, brauchen wir nur die beiden Operationen -Multiplizieren und quadrieren, für die wir bereits +Multiplizieren und Quadrieren, für die wir bereits geeignete Formeln gefunden haben. \subsubsection{Gruppenstruktur auf einer elliptischen Kurve} @@ -502,7 +502,7 @@ E_{a,b}(\mathbb{F}_{p^l}) = \{ (X,Y)\in\mathbb{F}_{p^l} -\;|\; +\mid Y^2+XY = X^3-aX-b \} \] @@ -510,7 +510,7 @@ trägt eine Gruppenstruktur, die wie folgt definiert ist: \begin{enumerate} \item Es gibt ein neutrales Element, welches man manchmal als $(0,0)$ schreibt, obwohl dieser Punkt nicht auf der Kuve liegt. -\item Das inverse Element von $(x,y)$ ist $(-x,-y-x)$. +\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} @@ -556,7 +556,7 @@ 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. +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 diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex index 066b9d2..3cdc748 100644 --- a/buch/chapters/90-crypto/ff.tex +++ b/buch/chapters/90-crypto/ff.tex @@ -12,11 +12,34 @@ 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} +$\mathbb{F}_p$ wird in Abschnitt~\ref{buch:section:elliptische-kurven} verallgemeinert auf eine sogenannte elliptische Kurve. Diese Version des Algorithmus ist sehr effizient was die Bitlänge der Schlüssel betrifft. +\begin{table} +\centering +\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|} +\hline + i& q& k_i& f\\ +\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} +\caption{Potenzen von 7 im Körper $\mathbb{F}_{1291}$. +\label{buch:crypto:fig:f1291}} +\end{table} + \subsection{Potenzen in $\mathbb{F}_p$ und diskreter Logarithmus \label{buch:subsection:potenzen-diskreter-logarithmus}} Für kryptographische Anwendungen wird eine einfach zu berechnende @@ -28,6 +51,7 @@ 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. Dank dem Algorithmus~\ref{buch:crypto:teile-und-hersche} ist auch sie effizient durchführbar. @@ -87,38 +111,20 @@ sie effizient durchführbar. %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:teile-und-hersche} in der folgenden -Tabelle -\begin{center} -\begin{tabular}{|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|>{$}r<{$}|} -\hline - i& q& k_i& f\\ -\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} +Algorithmus~\ref{buch:crypto:teile-und-hersche} in der +Tabelle~\ref{buch:crypto:fig:f1291} In der Spalte $q$ stehen die Potenzen $a^{i+1}=7^{i+1}$, in Spalte $f$ die ausgerechneten Produkte. 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. +Die Tabelle~\ref{buch:crypto:fig:f1291} 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 @@ -164,6 +170,21 @@ Funktion. %berechnet werden. %\end{algorithmus} +\begin{figure} +\centering +\includegraphics{chapters/90-crypto/images/dh.pdf} +\caption{Schlüsselaustausch nach Diffie-Hellman. +\index{Diffie-Hellmann}% +\index{Schlüsseltausch}% +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} % % Diffie-Hellman Schlüsseltausch @@ -179,7 +200,7 @@ ausgehandelten Schlüssel zu ermitteln. 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 +Weiter erzeugen sie je 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$ @@ -199,21 +220,6 @@ 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. -\index{Diffie-Hellmann}% -\index{Schlüsseltausch}% -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$. diff --git a/buch/chapters/95-homologie/homologieketten.tex b/buch/chapters/95-homologie/homologieketten.tex index ed91726..b684c79 100644 --- a/buch/chapters/95-homologie/homologieketten.tex +++ b/buch/chapters/95-homologie/homologieketten.tex @@ -33,7 +33,7 @@ Z_k = Z_k^C = -\{z\in C_k\;|\; \partial_k z = 0\} +\{z\in C_k \mid \partial_k z = 0\} = \ker \partial_k \] @@ -57,7 +57,7 @@ B_k = B_k^C = -\{\partial_{k+1}z\;|\; C_{k+1}\} +\{\partial_{k+1}z \mid C_{k+1}\} = \operatorname{im} \partial_{k+1} \] |