diff options
Diffstat (limited to 'buch/chapters/90-crypto')
| -rw-r--r-- | buch/chapters/90-crypto/aes.tex | 28 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/arith.tex | 118 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/chapter.tex | 2 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/elliptisch.tex | 26 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/ff.tex | 86 |
5 files changed, 137 insertions, 123 deletions
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$. |