From 39f232312a86c70c271f8edef77b233e1dd40c1c Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sat, 25 Sep 2021 20:41:52 +0200 Subject: 2. Lesung --- buch/chapters/90-crypto/arith.tex | 118 ++++++++++++++++++++------------------ 1 file changed, 62 insertions(+), 56 deletions(-) (limited to 'buch/chapters/90-crypto/arith.tex') 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} -- cgit v1.2.1