diff options
Diffstat (limited to '')
| -rw-r--r-- | buch/chapters/90-crypto/aes.tex | 26 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/chapter.tex | 15 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/ff.tex | 209 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/rs.tex | 33 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/uebungsaufgaben/9001.tex | 31 |
5 files changed, 314 insertions, 0 deletions
diff --git a/buch/chapters/90-crypto/aes.tex b/buch/chapters/90-crypto/aes.tex index d392761..6004dde 100644 --- a/buch/chapters/90-crypto/aes.tex +++ b/buch/chapters/90-crypto/aes.tex @@ -6,4 +6,30 @@ \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/chapter.tex b/buch/chapters/90-crypto/chapter.tex index 92bb09b..829169f 100644 --- a/buch/chapters/90-crypto/chapter.tex +++ b/buch/chapters/90-crypto/chapter.tex @@ -8,7 +8,22 @@ \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/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 index ccaef63..f05dd20 100644 --- a/buch/chapters/90-crypto/ff.tex +++ b/buch/chapters/90-crypto/ff.tex @@ -7,3 +7,212 @@ \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. + +\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 +\begin{tikzpicture}[>=latex,thick] +\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} +\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. + + diff --git a/buch/chapters/90-crypto/rs.tex b/buch/chapters/90-crypto/rs.tex index e8ea3b4..ec8ec8c 100644 --- a/buch/chapters/90-crypto/rs.tex +++ b/buch/chapters/90-crypto/rs.tex @@ -6,3 +6,36 @@ \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} + |