% % arith.tex % % (c) 2021 Prof Dr Andreas Müller, Hochschule Rapperswil % \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}} 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} \label{buch:crypto:teile-und-hersche} Der folgende Algorithmus 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}} 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}} 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