diff options
Diffstat (limited to '')
| -rw-r--r-- | buch/chapters/90-crypto/arith.tex | 282 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/chapter.tex | 2 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/ff.tex | 2 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/images/Makefile | 8 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/images/multiplikation.pdf | bin | 0 -> 25263 bytes | |||
| -rw-r--r-- | buch/chapters/90-crypto/images/multiplikation.tex | 464 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/images/schieberegister.pdf | bin | 0 -> 28254 bytes | |||
| -rw-r--r-- | buch/chapters/90-crypto/images/schieberegister.tex | 120 | ||||
| -rw-r--r-- | buch/chapters/90-crypto/uebungsaufgaben/9001.tex | 2 |
9 files changed, 870 insertions, 10 deletions
diff --git a/buch/chapters/90-crypto/arith.tex b/buch/chapters/90-crypto/arith.tex index b6f2fd8..44eb6bb 100644 --- a/buch/chapters/90-crypto/arith.tex +++ b/buch/chapters/90-crypto/arith.tex @@ -6,20 +6,290 @@ \section{Arithmetik für die Kryptographie \label{buch:section:arithmetik-fuer-kryptographie}} \rhead{Arithmetik für die Kryptographie} +Die Algorithmen der mathematischen Kryptographie basieren +auf den Rechenoperationen in grossen, aber endlichen Körpern. +Für die Division liefert der euklidische Algorithmus eine +Methode, der in so vielen Schritten die Inverse findet, +wie Dividend und Divisor Binärstellen haben. +Dies ist weitgehend optimal. + +Die Division ist umkehrbar, in der Kryptographie strebt man aber an, +Funktionen zu konstruieren, die nur mit grossem Aufwand umkehrbar sind. +Eine solche Funktion ist das Potenzieren in einem endlichen Körper. +Die Berechnung von Potenzen durch wiederholte Multiplikation ist jedoch +prohibitiv aufwendig, daher ist ein schneller Potenzierungsalgorithmus +nötig, der in Abschnitt~\ref{buch:subsection:potenzieren} beschrieben +wird. +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 +\ref{buch:subsection:rechenoperationen-in-fp} +und +\ref{buch:subsection:rechenoperatione-in-f2l} +besprochen. \subsection{Potenzieren \label{buch:subsection:potenzieren}} -% XXX Divide-and-Conquer Algorithmus +Wir gehen davon aus, dass wir einen schnellen Algorithmus zur +Berechnung des Produktes zweier Elemente $a,b$ in einer +beliebigen Gruppe $G$ haben. +Die Gruppe $G$ kann die Multiplikation der ganzen oder reellen Zahlen +sein, dies wird zum Beispiel in Implementation der Potenzfunktion +verwendet. +Für kryptographische Anwendungen ist $G$ die multiplikative Gruppe +eines endlichen Körpers oder eine elliptische Kurve. + +Zur Berechnung von $a^k$ sind bei einer naiven Durchführung des +Algorithmus $k-1$ Multiplikationen nötig, immer sofort gefolgt +von einer Reduktion $\mod 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)$ Multiplikationen, die Laufzeit wächst +also exponentiell mit der Bitlänge von $k$ an. +Der nachfolgend beschriebene Algorithmus reduziert die Laufzeit auf +die $O(l)$. + +Zunächst schreiben wir den Exponenten $k$ in binärer Form als +\[ +k = k_l2^l + k_{l-1}2^{l-1} + \dots k_22^2+k_12^1 k_02^0. +\] +Die Potenz $a^k$ kann dann geschrieben werden als +\[ +a^k += +a^{k_l2^l} \cdot a^{k_{l-1}2^{l-1}} \cdot \dots \cdot +a^{k_22^2} \cdot a^{k_12^1} \cdot a^{k_02^0} +\] +Nur diejenigen Faktoren tragen etwas bei, für die $k_i\ne 0$ ist. +Die Potenz kann man daher auch schreiben als +\[ +a^k += +\prod_{k_i\ne 0} a^{2^i}. +\] +Es sind also nur so viele Faktoren zu berücksichtigen, wie $k$ +Binärstellen $1$ hat. + +Die einzelnen Faktoren $a^{2^i}$ können durch wiederholtes Quadrieren +erhalten werden: +\[ +a^{2^i} = a^{2\cdot 2^{i-1}} = (a^{2^{i-1}})^2, +\] +also durch maximal $l-1$ Multiplikationen. +Wenn $k$ keine Ganzzahl ist sondern binäre Nachkommastellen hat, also +\[ +k=k_l2^l + \dots + k_12^1 + k_02^0 + k_{-1}2^{-1} + k_{-2}2^{-2}+\dots, +\] +dann können die Potenzen $a^{2^{-i}}$ durch wiederholtes Wurzelziehen +\[ +a^{2^{-i}} = a^{\frac12\cdot 2^{-i+1}} = \sqrt{a^{2^{-i+1}}} +\] +gefunden werden. +Die Berechnung der Quadratwurzel lässt sich in Hardware effizient +implementieren. + +\begin{algorithmus} +Der folgende Algorithmsu berechnet $a^k$ in $O(\log_2(k))$ +Multiplikationen +\begin{enumerate} +\item Initialisiere $p=1$ und $q=a$ +\item Falls $k$ ungerade ist, setze $p:=p\cdot q$ +\item Setze $q:=q^2$ und $k := k/2$, wobei die ganzzahlige Division durch $2$ +am effizientesten als Rechtsshift implementiert werden kann. +\item Falls $k>0$, fahre weiter bei 2. +\end{enumerate} +\end{algorithmus} + +\begin{beispiel} +Die Berechnung von $1.1^{17}$ mit diesem Algorithmus ergibt +\begin{enumerate} +\item $p=1$, $q=1.1$ +\item $k$ ist ungerade: $p:=1.1$ +\item $q:=q^2=1.21$, $k := 8$ +\item $k$ ist gerade +\item $q:=q^2=1.4641$, $k := 4$ +\item $k$ ist gerade +\item $q:=q^2=2.14358881$, $k := 2$ +\item $k$ ist gerade +\item $q:=q^2=4.5949729863572161$, $k := 1$ +\item $k$ ist ungerade: $p:=1.1\cdot p = 5.05447028499293771$ +\item $k:=0$ +\end{enumerate} +Multiplikationen sind nur nötig in den Schritten 3, 5, 7, 9, 10, es +werden also genau $5$ Multiplikationen ausgeführt. +\end{beispiel} \subsection{Rechenoperationen in $\mathbb{F}_p$ \label{buch:subsection:rechenoperationen-in-fp}} -% XXX Multiplikation: modulare Reduktion mit jedem Digit -% XXX Divide-and-Conquer +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$ +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<{$}} +\text{Multiplikation mit $2$}&\text{Reduktion?}&\text{reduziert} + &\text{Summanden}&\text{Summe}&\text{reduziert} +\\ +\hline +\texttt{101111} & &\texttt{101111} + &\texttt{101111}&\texttt{101111}&\texttt{101111} +\\ +\texttt{101111\phantom{0}} &\texttt{{\color{red}1011110}}&\texttt{101001} + & & & +\\ +\texttt{101111\phantom{00}} &\texttt{0{\color{red}111010}}&\texttt{011101} + & & & +\\ +\texttt{101111\phantom{000}} &\texttt{0001010}&\texttt{000101} + &\texttt{000101}&\texttt{110100}&\texttt{110100} +\\ +\texttt{101111\phantom{0000}} &\texttt{0010100}&\texttt{001010} + & & & +\\ +\texttt{101111\phantom{00000}}&\texttt{0101000}&\texttt{010100} + &\texttt{010100}&\texttt{{\color{red}1001000}}&\texttt{10011}\rlap{$\mathstrut=19$} +\end{tabular} +\end{center} +\caption{Multiplikation von $41=\texttt{101001}_2$ mit $47=\texttt{101111}_2$, +Reduktion nach jeder Multiplikation mit $2$: falls das Resultat +$>p$ ist, wie in den rot markierten Zeilen $p=53=\texttt{110101}_2$ +durchgeführt. +Bei der Bildung der Summe wird ebenfalls in jedem Schritt falls nötig +reduziert, angezeigt durch die roten Zahlen in der zweitletzten +Spalte. +Die Anzahl der Subtraktionen, die für die Reduktionen nötig sind, ist +von der selben Grössenordnung wie bei der Durchführung des +Divisionsalgorithmus. +\label{buch:crypto:fig:reduktion}} +\end{figure} + +Es ist also möglich, mit gleichem Aufwand an Operationen +aber mit halbe 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. \subsection{Rechenoperationen in $\mathbb{F}_{2^l}$ \label{buch:subsection:rechenoperatione-in-f2l}} -% XXX Darstellung eines Körpers der Art F_{2^l} -% XXX Addition (XOR) und Multiplikation -% XXX Beispiel F_{2^8} +Von besonderem praktischem Interesse sind die endlichen Körper +$\mathbb{F}_{2^l}$. +Die arithmetischen Operationen in diesen Körpern lassen sich besonders +effizient in Hardware realisieren. + +\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$ +\[ +m(X) += +X^l + m_{l-1}X^{l-1} + m_{l-2}X^{l-2} + \dots + m_2X^2 + m_1X + m_0 +\] +gegeben. +Ein Element in $\mathbb{F}_2[X]/(m)$ kann dargestellt werden durch ein +Polynom vom Grad $l-1$, 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$ +dargestellt werden. + +\subsubsection{Addition} +Die Addition in $\mathbb{F}_2$ ist in Hardware besonders leicht zu +realisieren. +Die Addition ist die XOR-Operation, die Multiplikation ist die UND-Verknüfung. +Ausserdem stimmen in $\mathbb{F}_2$ Addition und Subtraktion überein. + +Die Addition zweier Polynome erfolgt komponentenweise. +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 +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 +gross wird, dass eine Reduktionsoperation modulo $m(X)$ nötig wird. +Die Reduktion wird immer dann nötig, wenn der Koeffizient von $X^l$ +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. +Das Minimalpolynom $m(X)=X^8+X^4+X^3+X+1$ bedeutet, dass in $\mathbb{F}_{2^l}$ +$X^8=X^4+X^3+X+1$ gilt, so dass man das Überlaufbit durch +$X^4+X^3+X+1$ ersetzen und addieren kann. + +Ein Produktes $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)$ +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} + + % XXX Beispiel F einer Oakley-Gruppe diff --git a/buch/chapters/90-crypto/chapter.tex b/buch/chapters/90-crypto/chapter.tex index 43ac8de..d2fcbbf 100644 --- a/buch/chapters/90-crypto/chapter.tex +++ b/buch/chapters/90-crypto/chapter.tex @@ -20,7 +20,7 @@ In diesem Abschnitt soll dies an einigen Beispielen gezeigt werden. \input{chapters/90-crypto/arith.tex} \input{chapters/90-crypto/ff.tex} \input{chapters/90-crypto/aes.tex} -\input{chapters/90-crypto/rs.tex} +%\input{chapters/90-crypto/rs.tex} \section*{Übungsaufgaben} \rhead{Übungsaufgaben} diff --git a/buch/chapters/90-crypto/ff.tex b/buch/chapters/90-crypto/ff.tex index 4ab9c34..535b359 100644 --- a/buch/chapters/90-crypto/ff.tex +++ b/buch/chapters/90-crypto/ff.tex @@ -26,7 +26,7 @@ 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$ +Der folgende Algorithmus berechnet die Potenz in $O(\log_2 a)$ Multiplikationen. \begin{algorithmus}[Divide-and-conquer] diff --git a/buch/chapters/90-crypto/images/Makefile b/buch/chapters/90-crypto/images/Makefile index 9480163..bbb960f 100644 --- a/buch/chapters/90-crypto/images/Makefile +++ b/buch/chapters/90-crypto/images/Makefile @@ -3,7 +3,7 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: dh.pdf elliptic.pdf +all: dh.pdf elliptic.pdf schieberegister.pdf multiplikation.pdf dh.pdf: dh.tex pdflatex dh.tex @@ -11,3 +11,9 @@ dh.pdf: dh.tex elliptic.pdf: elliptic.tex pdflatex elliptic.tex +schieberegister.pdf: schieberegister.tex + pdflatex schieberegister.tex + +multiplikation.pdf: multiplikation.tex + pdflatex multiplikation.tex + diff --git a/buch/chapters/90-crypto/images/multiplikation.pdf b/buch/chapters/90-crypto/images/multiplikation.pdf Binary files differnew file mode 100644 index 0000000..86345b8 --- /dev/null +++ b/buch/chapters/90-crypto/images/multiplikation.pdf diff --git a/buch/chapters/90-crypto/images/multiplikation.tex b/buch/chapters/90-crypto/images/multiplikation.tex new file mode 100644 index 0000000..27c4329 --- /dev/null +++ b/buch/chapters/90-crypto/images/multiplikation.tex @@ -0,0 +1,464 @@ +% +% multiplikation.tex -- +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\definecolor{darkgreen}{rgb}{0,0.6,0} + +\def\s{0.45} + +\def\punkt#1#2{({#1*\s},{#2*\s})} + +\def\pfeile{ + \foreach \x in {0.5,1.5,...,7.5}{ + \draw[->,color=blue] \punkt{\x}{-2.1} -- \punkt{(\x-1)}{-3.3}; + } +} + +\begin{scope}[yshift=0.1cm] + \node at \punkt{0}{0.5} [left] {$p(X)=\mathstrut$}; + \draw \punkt{0}{0} rectangle \punkt{8}{1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{0} -- \punkt{\x}{1}; + } + \node at \punkt{0.5}{0.5} {\texttt{1}}; + \node at \punkt{1.5}{0.5} {\texttt{0}}; + \node at \punkt{2.5}{0.5} {\texttt{0}}; + \node at \punkt{3.5}{0.5} {\texttt{1}}; + \node at \punkt{4.5}{0.5} {\texttt{0}}; + \node at \punkt{5.5}{0.5} {\texttt{1}}; + \node at \punkt{6.5}{0.5} {\texttt{0}}; + \node at \punkt{7.5}{0.5} {\texttt{1}}; + \foreach \x in {0.5,1.5,...,7.5}{ + \draw[->,color=blue] \punkt{\x}{-0.1} -- \punkt{(\x-1)}{-1.3}; + } +\end{scope} + +\begin{scope}[yshift=-1cm] + \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8); + \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$}; + \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1}; + \draw \punkt{0}{0} rectangle \punkt{8}{1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{0} -- \punkt{\x}{1}; + } + \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{1}}; + \node at \punkt{0.5}{0.5} {\texttt{0}}; + \node at \punkt{1.5}{0.5} {\texttt{0}}; + \node at \punkt{2.5}{0.5} {\texttt{1}}; + \node at \punkt{3.5}{0.5} {\texttt{0}}; + \node at \punkt{4.5}{0.5} {\texttt{1}}; + \node at \punkt{5.5}{0.5} {\texttt{0}}; + \node at \punkt{6.5}{0.5} {\texttt{1}}; + \node at \punkt{7.5}{0.5} {\texttt{0}}; + + \draw[->,color=darkgreen] + \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5}; + \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}}; + \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}}; + \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}}; + \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}}; + + \draw \punkt{0}{-2} rectangle \punkt{8}{-1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{-2} -- \punkt{\x}{-1}; + } + \node at \punkt{0.5}{-1.5} {\texttt{0}}; + \node at \punkt{1.5}{-1.5} {\texttt{0}}; + \node at \punkt{2.5}{-1.5} {\texttt{1}}; + \node at \punkt{3.5}{-1.5} {\texttt{1}}; + \node at \punkt{4.5}{-1.5} {\texttt{0}}; + \node at \punkt{5.5}{-1.5} {\texttt{0}}; + \node at \punkt{6.5}{-1.5} {\texttt{0}}; + \node at \punkt{7.5}{-1.5} {\texttt{1}}; + + \pfeile +\end{scope} + +\begin{scope}[yshift=-3cm] + \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8); + \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$}; + \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1}; + \draw \punkt{0}{0} rectangle \punkt{8}{1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{0} -- \punkt{\x}{1}; + } + \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{0}}; + \node at \punkt{0.5}{0.5} {\texttt{0}}; + \node at \punkt{1.5}{0.5} {\texttt{1}}; + \node at \punkt{2.5}{0.5} {\texttt{1}}; + \node at \punkt{3.5}{0.5} {\texttt{0}}; + \node at \punkt{4.5}{0.5} {\texttt{0}}; + \node at \punkt{5.5}{0.5} {\texttt{0}}; + \node at \punkt{6.5}{0.5} {\texttt{1}}; + \node at \punkt{7.5}{0.5} {\texttt{0}}; + +% \draw[->,color=darkgreen] +% \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5}; +% \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}}; + \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$}; + + \draw \punkt{0}{-2} rectangle \punkt{8}{-1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{-2} -- \punkt{\x}{-1}; + } + \node at \punkt{0.5}{-1.5} {\texttt{0}}; + \node at \punkt{1.5}{-1.5} {\texttt{1}}; + \node at \punkt{2.5}{-1.5} {\texttt{1}}; + \node at \punkt{3.5}{-1.5} {\texttt{0}}; + \node at \punkt{4.5}{-1.5} {\texttt{0}}; + \node at \punkt{5.5}{-1.5} {\texttt{0}}; + \node at \punkt{6.5}{-1.5} {\texttt{1}}; + \node at \punkt{7.5}{-1.5} {\texttt{0}}; + + \pfeile +\end{scope} + +\begin{scope}[yshift=-5cm] + \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8); + \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$}; + \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1}; + \draw \punkt{0}{0} rectangle \punkt{8}{1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{0} -- \punkt{\x}{1}; + } + \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{0}}; + \node at \punkt{0.5}{0.5} {\texttt{1}}; + \node at \punkt{1.5}{0.5} {\texttt{1}}; + \node at \punkt{2.5}{0.5} {\texttt{0}}; + \node at \punkt{3.5}{0.5} {\texttt{0}}; + \node at \punkt{4.5}{0.5} {\texttt{0}}; + \node at \punkt{5.5}{0.5} {\texttt{1}}; + \node at \punkt{6.5}{0.5} {\texttt{0}}; + \node at \punkt{7.5}{0.5} {\texttt{0}}; + +% \draw[->,color=darkgreen] +% \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5}; +% \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}}; + \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$}; + + \draw \punkt{0}{-2} rectangle \punkt{8}{-1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{-2} -- \punkt{\x}{-1}; + } + \node at \punkt{0.5}{-1.5} {\texttt{1}}; + \node at \punkt{1.5}{-1.5} {\texttt{1}}; + \node at \punkt{2.5}{-1.5} {\texttt{0}}; + \node at \punkt{3.5}{-1.5} {\texttt{0}}; + \node at \punkt{4.5}{-1.5} {\texttt{0}}; + \node at \punkt{5.5}{-1.5} {\texttt{1}}; + \node at \punkt{6.5}{-1.5} {\texttt{0}}; + \node at \punkt{7.5}{-1.5} {\texttt{0}}; + + \pfeile +\end{scope} + +\begin{scope}[yshift=-7cm] + \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8); + \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$}; + \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1}; + \draw \punkt{0}{0} rectangle \punkt{8}{1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{0} -- \punkt{\x}{1}; + } + \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{1}}; + \node at \punkt{0.5}{0.5} {\texttt{1}}; + \node at \punkt{1.5}{0.5} {\texttt{0}}; + \node at \punkt{2.5}{0.5} {\texttt{0}}; + \node at \punkt{3.5}{0.5} {\texttt{0}}; + \node at \punkt{4.5}{0.5} {\texttt{1}}; + \node at \punkt{5.5}{0.5} {\texttt{0}}; + \node at \punkt{6.5}{0.5} {\texttt{0}}; + \node at \punkt{7.5}{0.5} {\texttt{0}}; + + \draw[->,color=darkgreen] + \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5}; + \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}}; + \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}}; + \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}}; + \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$}; + + \draw \punkt{0}{-2} rectangle \punkt{8}{-1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{-2} -- \punkt{\x}{-1}; + } + \node at \punkt{0.5}{-1.5} {\texttt{1}}; + \node at \punkt{1.5}{-1.5} {\texttt{0}}; + \node at \punkt{2.5}{-1.5} {\texttt{0}}; + \node at \punkt{3.5}{-1.5} {\texttt{1}}; + \node at \punkt{4.5}{-1.5} {\texttt{0}}; + \node at \punkt{5.5}{-1.5} {\texttt{0}}; + \node at \punkt{6.5}{-1.5} {\texttt{1}}; + \node at \punkt{7.5}{-1.5} {\texttt{1}}; + + \pfeile +\end{scope} + +\begin{scope}[yshift=-9cm] + \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8); + \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$}; + \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1}; + \draw \punkt{0}{0} rectangle \punkt{8}{1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{0} -- \punkt{\x}{1}; + } + \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{1}}; + \node at \punkt{0.5}{0.5} {\texttt{0}}; + \node at \punkt{1.5}{0.5} {\texttt{0}}; + \node at \punkt{2.5}{0.5} {\texttt{1}}; + \node at \punkt{3.5}{0.5} {\texttt{0}}; + \node at \punkt{4.5}{0.5} {\texttt{0}}; + \node at \punkt{5.5}{0.5} {\texttt{1}}; + \node at \punkt{6.5}{0.5} {\texttt{1}}; + \node at \punkt{7.5}{0.5} {\texttt{0}}; + + \draw[->,color=darkgreen] + \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5}; + \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}}; + \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}}; + \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}}; + \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$}; + + \draw \punkt{0}{-2} rectangle \punkt{8}{-1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{-2} -- \punkt{\x}{-1}; + } + \node at \punkt{0.5}{-1.5} {\texttt{0}}; + \node at \punkt{1.5}{-1.5} {\texttt{0}}; + \node at \punkt{2.5}{-1.5} {\texttt{1}}; + \node at \punkt{3.5}{-1.5} {\texttt{1}}; + \node at \punkt{4.5}{-1.5} {\texttt{1}}; + \node at \punkt{5.5}{-1.5} {\texttt{1}}; + \node at \punkt{6.5}{-1.5} {\texttt{0}}; + \node at \punkt{7.5}{-1.5} {\texttt{1}}; + + \pfeile +\end{scope} + +\begin{scope}[yshift=-11cm] + \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8); + \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$}; + \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1}; + \draw \punkt{0}{0} rectangle \punkt{8}{1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{0} -- \punkt{\x}{1}; + } + \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{0}}; + \node at \punkt{0.5}{0.5} {\texttt{0}}; + \node at \punkt{1.5}{0.5} {\texttt{0}}; + \node at \punkt{2.5}{0.5} {\texttt{1}}; + \node at \punkt{3.5}{0.5} {\texttt{1}}; + \node at \punkt{4.5}{0.5} {\texttt{1}}; + \node at \punkt{5.5}{0.5} {\texttt{0}}; + \node at \punkt{6.5}{0.5} {\texttt{1}}; + \node at \punkt{7.5}{0.5} {\texttt{0}}; + +% \draw[->,color=darkgreen] +% \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5}; +% \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}}; + \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$}; + + \draw \punkt{0}{-2} rectangle \punkt{8}{-1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{-2} -- \punkt{\x}{-1}; + } + \node at \punkt{0.5}{-1.5} {\texttt{0}}; + \node at \punkt{1.5}{-1.5} {\texttt{0}}; + \node at \punkt{2.5}{-1.5} {\texttt{1}}; + \node at \punkt{3.5}{-1.5} {\texttt{1}}; + \node at \punkt{4.5}{-1.5} {\texttt{1}}; + \node at \punkt{5.5}{-1.5} {\texttt{0}}; + \node at \punkt{6.5}{-1.5} {\texttt{1}}; + \node at \punkt{7.5}{-1.5} {\texttt{0}}; + + \pfeile +\end{scope} + +\begin{scope}[yshift=-13cm] + \draw[<-] \punkt{8.2}{-1.3} arc (-30:30:1.8); + \node at \punkt{9.3}{0.6} {$\mathstrut\cdot X$}; + \fill[color=blue!20] \punkt{-1}{0} rectangle \punkt{0}{1}; + \draw \punkt{0}{0} rectangle \punkt{8}{1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{0} -- \punkt{\x}{1}; + } + \node[color=darkgreen] at \punkt{-0.5}{0.5} {\texttt{0}}; + \node at \punkt{0.5}{0.5} {\texttt{0}}; + \node at \punkt{1.5}{0.5} {\texttt{1}}; + \node at \punkt{2.5}{0.5} {\texttt{1}}; + \node at \punkt{3.5}{0.5} {\texttt{1}}; + \node at \punkt{4.5}{0.5} {\texttt{0}}; + \node at \punkt{5.5}{0.5} {\texttt{1}}; + \node at \punkt{6.5}{0.5} {\texttt{0}}; + \node at \punkt{7.5}{0.5} {\texttt{0}}; + +% \draw[->,color=darkgreen] +% \punkt{-0.5}{0.1} -- \punkt{-0.5}{-0.5} -- \punkt{3.1}{-0.5}; +% \node[color=darkgreen] at \punkt{3.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{4.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{6.5}{-0.5} {\texttt{1}}; +% \node[color=darkgreen] at \punkt{7.5}{-0.5} {\texttt{1}}; + \node[color=darkgreen] at \punkt{4}{-0.5} {$\|$}; + + \draw \punkt{0}{-2} rectangle \punkt{8}{-1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{-2} -- \punkt{\x}{-1}; + } + \node at \punkt{0.5}{-1.5} {\texttt{0}}; + \node at \punkt{1.5}{-1.5} {\texttt{1}}; + \node at \punkt{2.5}{-1.5} {\texttt{1}}; + \node at \punkt{3.5}{-1.5} {\texttt{0}}; + \node at \punkt{4.5}{-1.5} {\texttt{1}}; + \node at \punkt{5.5}{-1.5} {\texttt{1}}; + \node at \punkt{6.5}{-1.5} {\texttt{1}}; + \node at \punkt{7.5}{-1.5} {\texttt{1}}; + +% \pfeile +\end{scope} + +\begin{scope}[xshift=9cm] + +\begin{scope}[yshift=0.1cm] + \draw[->] \punkt{-11.8}{0.5} -- \punkt{-0.1}{0.5}; + \draw \punkt{0}{0} rectangle \punkt{8}{1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{0} -- \punkt{\x}{1}; + } + \draw \punkt{4}{-0.1} -- \punkt{4}{-3}; + \node at \punkt{0.5}{0.5} {\texttt{1}}; + \node at \punkt{1.5}{0.5} {\texttt{0}}; + \node at \punkt{2.5}{0.5} {\texttt{0}}; + \node at \punkt{3.5}{0.5} {\texttt{1}}; + \node at \punkt{4.5}{0.5} {\texttt{0}}; + \node at \punkt{5.5}{0.5} {\texttt{1}}; + \node at \punkt{6.5}{0.5} {\texttt{0}}; + \node at \punkt{7.5}{0.5} {\texttt{1}}; +\end{scope} + +\def\summation#1#2#3#4#5#6#7#8{ + \draw[->] \punkt{4}{2.3} -- \punkt{4}{1}; + + \draw[->] \punkt{-11.8}{0.5} -- \punkt{3.5}{0.5}; + + \draw \punkt{4}{0.5} circle[radius=0.2]; + \draw \punkt{4}{0.20} -- \punkt{4}{0.80}; + \draw \punkt{3.7}{0.5} -- \punkt{4.3}{0.5}; + + \draw[->] \punkt{4}{-0.05} -- \punkt{4}{-0.95}; + \draw \punkt{0}{-2} rectangle \punkt{8}{-1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{-2} -- \punkt{\x}{-1}; + } + + \node at \punkt{0.5}{-1.5} {\texttt{#1}}; + \node at \punkt{1.5}{-1.5} {\texttt{#2}}; + \node at \punkt{2.5}{-1.5} {\texttt{#3}}; + \node at \punkt{3.5}{-1.5} {\texttt{#4}}; + \node at \punkt{4.5}{-1.5} {\texttt{#5}}; + \node at \punkt{5.5}{-1.5} {\texttt{#6}}; + \node at \punkt{6.5}{-1.5} {\texttt{#7}}; + \node at \punkt{7.5}{-1.5} {\texttt{#8}}; +} + +\begin{scope}[yshift=-1.9cm] + \summation{1}{0}{0}{1}{0}{1}{0}{1} +\end{scope} + +\begin{scope}[yshift=-3.9cm] + \summation{1}{1}{1}{1}{0}{1}{1}{1} +\end{scope} + +\begin{scope}[yshift=-5.9cm] + \summation{1}{1}{1}{1}{0}{1}{1}{1} +\end{scope} + +\begin{scope}[yshift=-7.9cm] + \summation{0}{1}{1}{0}{0}{1}{0}{0} +\end{scope} + +\begin{scope}[yshift=-9.9cm] + \summation{0}{1}{0}{1}{1}{0}{0}{1} +\end{scope} + +\begin{scope}[yshift=-11.9cm] + \summation{0}{1}{0}{1}{1}{0}{0}{1} +\end{scope} + +\begin{scope}[yshift=-13.9cm] + \summation{0}{0}{1}{1}{0}{1}{1}{0} + \node at \punkt{0}{-1.5} [left] {$p(X)\cdot q(X)=\mathstrut$}; +\end{scope} + +\end{scope} + +\begin{scope}[xshift=5cm] + +\begin{scope}[yshift=2cm] + \node at \punkt{0}{0.5} [left] {$q(X)=\mathstrut$}; + \draw \punkt{0}{0} rectangle \punkt{8}{1}; + \foreach \x in {1,...,7}{ + \draw \punkt{\x}{0} -- \punkt{\x}{1}; + } + \node at \punkt{0.5}{0.5} {\texttt{1}}; + \node at \punkt{1.5}{0.5} {\texttt{0}}; + \node at \punkt{2.5}{0.5} {\texttt{1}}; + \node at \punkt{3.5}{0.5} {\texttt{1}}; + \node at \punkt{4.5}{0.5} {\texttt{0}}; + \node at \punkt{5.5}{0.5} {\texttt{1}}; + \node at \punkt{6.5}{0.5} {\texttt{0}}; + \node at \punkt{7.5}{0.5} {\texttt{1}}; + + \draw[->] \punkt{7.5}{-0.1} -- ({7.5*\s},{-1.3}); + \node at ({7.5*\s},{-1.2}) [below] {$\mathstrut\cdot\texttt{1}$}; + + \def\y{1.2} + + \draw[->] \punkt{6.5}{-0.1} -- ({6.5*\s},{-1*2-\y-0.1}); + \node at ({6.5*\s},{-1*2-\y}) [below] {$\mathstrut\cdot\texttt{0}$}; + + \draw[->] \punkt{5.5}{-0.1} -- ({5.5*\s},{-2*2-\y-0.1}); + \node at ({5.5*\s},{-2*2-\y}) [below] {$\mathstrut\cdot\texttt{1}$}; + + \draw[->] \punkt{4.5}{-0.1} -- ({4.5*\s},{-3*2-\y-0.1}); + \node at ({4.5*\s},{-3*2-\y}) [below] {$\mathstrut\cdot\texttt{0}$}; + + \draw[->] \punkt{3.5}{-0.1} -- ({3.5*\s},{-4*2-\y-0.1}); + \node at ({3.5*\s},{-4*2-\y}) [below] {$\mathstrut\cdot\texttt{1}$}; + + \draw[->] \punkt{2.5}{-0.1} -- ({2.5*\s},{-5*2-\y-0.1}); + \node at ({2.5*\s},{-5*2-\y}) [below] {$\mathstrut\cdot\texttt{1}$}; + + \draw[->] \punkt{1.5}{-0.1} -- ({1.5*\s},{-6*2-\y-0.1}); + \node at ({1.5*\s},{-6*2-\y}) [below] {$\mathstrut\cdot\texttt{0}$}; + + \draw[->] \punkt{0.5}{-0.1} -- ({0.5*\s},{-7*2-\y-0.1}); + \node at ({0.5*\s},{-7*2-\y}) [below] {$\mathstrut\cdot\texttt{1}$}; +\end{scope} + +\end{scope} + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/90-crypto/images/schieberegister.pdf b/buch/chapters/90-crypto/images/schieberegister.pdf Binary files differnew file mode 100644 index 0000000..30b675b --- /dev/null +++ b/buch/chapters/90-crypto/images/schieberegister.pdf diff --git a/buch/chapters/90-crypto/images/schieberegister.tex b/buch/chapters/90-crypto/images/schieberegister.tex new file mode 100644 index 0000000..7c24e52 --- /dev/null +++ b/buch/chapters/90-crypto/images/schieberegister.tex @@ -0,0 +1,120 @@ +% +% schieberegister.tex -- template for standalon tikz images +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\definecolor{darkgreen}{rgb}{0,0.6,0} + +\def\s{0.8} + +\def\punkt#1#2{({#1*\s},{#2*\s})} + +\fill[color=blue!20] \punkt{0}{0} rectangle \punkt{8}{1}; + +\node at \punkt{0.5}{1} [above] {$X^7\mathstrut$}; +\node at \punkt{3}{1} [above] {$+\mathstrut$}; +\node at \punkt{3.5}{1} [above] {$X^4\mathstrut$}; +\node at \punkt{5}{1} [above] {$+\mathstrut$}; +\node at \punkt{5.5}{1} [above] {$X^2\mathstrut$}; +\node at \punkt{7}{1} [above] {$+\mathstrut$}; +\node at \punkt{7.5}{1} [above] {$1\mathstrut$}; + +\node at \punkt{0}{1} [above left] {\llap{$p(X)=\mathstrut$}}; + +\node at \punkt{0.5}{0.5} {\texttt{1}}; +\node at \punkt{1.5}{0.5} {\texttt{0}}; +\node at \punkt{2.5}{0.5} {\texttt{0}}; +\node at \punkt{3.5}{0.5} {\texttt{1}}; +\node at \punkt{4.5}{0.5} {\texttt{0}}; +\node at \punkt{5.5}{0.5} {\texttt{1}}; +\node at \punkt{6.5}{0.5} {\texttt{0}}; +\node at \punkt{7.5}{0.5} {\texttt{1}}; + +\draw \punkt{0}{0} rectangle \punkt{8}{1}; +\foreach \x in {1,...,7}{ + \draw \punkt{\x}{0} -- \punkt{\x}{1}; +} + +\fill[color=blue!20] \punkt{-1}{-3} rectangle \punkt{7}{-2}; +\fill[color=darkgreen!20] \punkt{0}{-4} rectangle \punkt{8}{-3}; + +\node[color=darkgreen] at \punkt{-1}{-1.5} [left] + {$m(X) = X^8+X^4+X^3+X+1$}; + +\node[color=darkgreen] at \punkt{-1}{-2.7} [left] + {$\underbrace{X^4+X^3+X+1}_{}= X^8=\mathstrut$}; + +\coordinate (A) at ({-4.15*\s},{-3*\s}); +\coordinate (B) at ({0*\s},{-3.5*\s}); + +\draw[->,color=red,shorten >= 0.1cm] (A) to[out=-90,in=180] (B); +\node[color=red] at \punkt{-3.1}{-3.8} [below] {Feedback}; + +\node at \punkt{-0.5}{-2.5} {\texttt{1}}; +\node at \punkt{0.5}{-2.5} {\texttt{0}}; +\node at \punkt{1.5}{-2.5} {\texttt{0}}; +\node at \punkt{2.5}{-2.5} {\texttt{1}}; +\node at \punkt{3.5}{-2.5} {\texttt{0}}; +\node at \punkt{4.5}{-2.5} {\texttt{1}}; +\node at \punkt{5.5}{-2.5} {\texttt{0}}; +\node at \punkt{6.5}{-2.5} {\texttt{1}}; +\node at \punkt{7.5}{-2.5} {\texttt{0}}; + +\node[color=darkgreen] at \punkt{0.5}{-3.5} {\texttt{0}}; +\node[color=darkgreen] at \punkt{1.5}{-3.5} {\texttt{0}}; +\node[color=darkgreen] at \punkt{2.5}{-3.5} {\texttt{0}}; +\node[color=darkgreen] at \punkt{3.5}{-3.5} {\texttt{1}}; +\node[color=darkgreen] at \punkt{4.5}{-3.5} {\texttt{1}}; +\node[color=darkgreen] at \punkt{5.5}{-3.5} {\texttt{0}}; +\node[color=darkgreen] at \punkt{6.5}{-3.5} {\texttt{1}}; +\node[color=darkgreen] at \punkt{7.5}{-3.5} {\texttt{1}}; + +\draw \punkt{0}{-4} rectangle \punkt{8}{-2}; +\draw \punkt{0}{-3} -- \punkt{8}{-3}; +\foreach \x in {1,...,7}{ + \draw \punkt{\x}{-4} -- \punkt{\x}{-2}; +} + +\foreach \x in {0.5,1.5,...,7.5}{ + \draw[->,color=blue] \punkt{\x}{-0.1} -- \punkt{(\x-1)}{-1.9}; +} + +\draw \punkt{0}{-6} rectangle \punkt{8}{-5}; +\foreach \x in {1,...,7}{ + \draw \punkt{\x}{-6} -- \punkt{\x}{-5}; +} + +\node at \punkt{0.5}{-5.5} {\texttt{0}}; +\node at \punkt{1.5}{-5.5} {\texttt{0}}; +\node at \punkt{2.5}{-5.5} {\texttt{1}}; +\node at \punkt{3.5}{-5.5} {\texttt{1}}; +\node at \punkt{4.5}{-5.5} {\texttt{0}}; +\node at \punkt{5.5}{-5.5} {\texttt{0}}; +\node at \punkt{6.5}{-5.5} {\texttt{0}}; +\node at \punkt{7.5}{-5.5} {\texttt{1}}; + +\node at \punkt{4}{-4.5} {$\|$}; + +\node at \punkt{10.3}{-3} [left] + {$\left.\begin{matrix}\\ \\ \\ \end{matrix}\right\} + = \text{XOR}$}; + +\draw[<-,shorten >= 0.1cm, shorten <= 0.1cm] + \punkt{8.0}{-2.0} arc (-30:30:{2.0*\s}); +\node at \punkt{8.3}{-1} [right] {$\mathstrut \cdot X$}; + +\node at \punkt{8.1}{-5.5} [right] {$=X\cdot p(X)\mathstrut$}; + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/90-crypto/uebungsaufgaben/9001.tex b/buch/chapters/90-crypto/uebungsaufgaben/9001.tex index 5bf4558..7ed1e57 100644 --- a/buch/chapters/90-crypto/uebungsaufgaben/9001.tex +++ b/buch/chapters/90-crypto/uebungsaufgaben/9001.tex @@ -6,7 +6,7 @@ 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$. +$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 |