\documentclass[a4paper]{article} \usepackage[ngerman]{babel} \usepackage[utf8]{inputenc} \usepackage{multicol} \usepackage{calc} \usepackage{ifthen} \usepackage[landscape]{geometry} \usepackage{amsmath,amsthm,amsfonts,amssymb} \usepackage{color,graphicx,overpic} \usepackage{xcolor, listings} \usepackage[compact]{titlesec} %less space for headers \usepackage{mdwlist} %less space for lists \usepackage{pdflscape} \usepackage{verbatim} \usepackage[most]{tcolorbox} \usepackage[hidelinks,pdfencoding=auto]{hyperref} \usepackage{bussproofs} \usepackage{fancyhdr} \usepackage{lastpage} \pagestyle{fancy} \fancyhf{} \fancyhead[L]{Kryptographie} \fancyfoot[L]{\thepage/\pageref{LastPage}} \renewcommand{\headrulewidth}{0pt} %obere Trennlinie \renewcommand{\footrulewidth}{0pt} %untere Trennlinie \pdfinfo{ /Title (Kryptographie - Cheatsheet) /Creator (TeX) /Producer (pdfTeX 1.40.0) /Author (Robert Jeutter) /Subject () } %%% Code Listings \definecolor{codegreen}{rgb}{0,0.6,0} \definecolor{codegray}{rgb}{0.5,0.5,0.5} \definecolor{codepurple}{rgb}{0.58,0,0.82} \definecolor{backcolour}{rgb}{0.95,0.95,0.92} \lstdefinestyle{mystyle}{ backgroundcolor=\color{backcolour}, commentstyle=\color{codegreen}, keywordstyle=\color{magenta}, numberstyle=\tiny\color{codegray}, stringstyle=\color{codepurple}, basicstyle=\ttfamily, breakatwhitespace=false, } \lstset{style=mystyle, upquote=true} %textmarker style from colorbox doc \tcbset{textmarker/.style={% enhanced, parbox=false,boxrule=0mm,boxsep=0mm,arc=0mm, outer arc=0mm,left=2mm,right=2mm,top=3pt,bottom=3pt, toptitle=1mm,bottomtitle=1mm,oversize}} % define new colorboxes \newtcolorbox{hintBox}{textmarker, borderline west={6pt}{0pt}{yellow}, colback=yellow!10!white} \newtcolorbox{importantBox}{textmarker, borderline west={6pt}{0pt}{red}, colback=red!10!white} \newtcolorbox{noteBox}{textmarker, borderline west={3pt}{0pt}{green}, colback=green!10!white} % define commands for easy access \renewcommand{\note}[2]{\begin{noteBox} \textbf{#1} #2 \end{noteBox}} \newcommand{\warning}[1]{\begin{hintBox} \textbf{Warning:} #1 \end{hintBox}} \newcommand{\important}[1]{\begin{importantBox} \textbf{Important:} #1 \end{importantBox}} % This sets page margins to .5 inch if using letter paper, and to 1cm % if using A4 paper. (This probably isn't strictly necessary.) % If using another size paper, use default 1cm margins. \ifthenelse{\lengthtest { \paperwidth = 11in}} { \geometry{top=.5in,left=.5in,right=.5in,bottom=.5in} } {\ifthenelse{ \lengthtest{ \paperwidth = 297mm}} {\geometry{top=1.3cm,left=1cm,right=1cm,bottom=1.2cm} } {\geometry{top=1.3cm,left=1cm,right=1cm,bottom=1.2cm} } } % Redefine section commands to use less space \makeatletter \renewcommand{\section}{\@startsection{section}{1}{0mm}% {-1ex plus -.5ex minus -.2ex}% {0.5ex plus .2ex}%x {\normalfont\large\bfseries}} \renewcommand{\subsection}{\@startsection{subsection}{2}{0mm}% {-1explus -.5ex minus -.2ex}% {0.5ex plus .2ex}% {\normalfont\normalsize\bfseries}} \renewcommand{\subsubsection}{\@startsection{subsubsection}{3}{0mm}% {-1ex plus -.5ex minus -.2ex}% {1ex plus .2ex}% {\normalfont\small\bfseries}} \makeatother % Don't print section numbers \setcounter{secnumdepth}{0} \setlength{\parindent}{0pt} \setlength{\parskip}{0pt plus 0.5ex} % compress space \setlength\abovedisplayskip{0pt} \setlength{\parskip}{0pt} \setlength{\parsep}{0pt} \setlength{\topskip}{0pt} \setlength{\topsep}{0pt} \setlength{\partopsep}{0pt} \linespread{0.5} \titlespacing{\section}{0pt}{*0}{*0} \titlespacing{\subsection}{0pt}{*0}{*0} \titlespacing{\subsubsection}{0pt}{*0}{*0} \begin{document} \raggedright \begin{multicols}{3}\scriptsize % multicol parameters % These lengths are set only within the two main columns %\setlength{\columnseprule}{0.25pt} \setlength{\premulticols}{1pt} \setlength{\postmulticols}{1pt} \setlength{\multicolsep}{1pt} \setlength{\columnsep}{2pt} \section{Einführung} Kryptologie = Kryptographie (Entwicklung kryptographischer Verfahren) + Kryptoanalyse (Versuch kryptographische Verfahren zu brechen) Die Kryptographie im engeren und ,,klassischen'' Sinn beschäftigt sich mit Verfahren, um in verschiedenen Kommunikationsszenarien eine gegen Angriffe von Gegnern (Mitlesen, Verändern, Unterschieben, Abstreiten) abgesicherte Kommunikation zu ermöglichen. Die ,,moderne'' Kryptologie beschäftigt sich mit kryptographischen Verfahren, mit kryptoanalytischen Verfahren, mit Sicherheitskonzepten und mit mathematischen Methoden zur Untersuchung dieser Dinge, abstrakt und an konkreten Verfahren. Aufgaben von Kryptosystemen \begin{description*} \item[Konzelation] Geheimhaltung/Vertraulichkeit/Zugriffsschutz(kein Unberechtigter kann Nachrichteninhalt mithören oder mitlesen \item[Integrität/Fälschungsschutz] stelle sicher, dass Nachrichten auf dem Übertragungsweg nicht manipuliert worden sind \item[Authentizität/Signaturen] Garantiere Absenderidentität; Bob kann kontrollieren, dass Nachricht vom behaupteten Absender Alice kommt \item[Nichtabstreitbarkeit] Bob kann gegenüber Dritten beweisen,dass die Nachricht in der empfangenen Form vom behaupteten Absender Alice kam \end{description*} \note{Message Authentication Code (MAC)}{ Funktion, die aus einer Nachricht x einen Code $mac=MAC(x)$ berechnet. Diese Funktion ist ein Geheimnis von legitimen Sendern von Nachrichten an Bob. Insbesondere kann Eva bei gegebener Nachricht x' keinen korrekten MAC für x' berechnen. Bob verfügt über ein Prüfverfahren, das es ihm erlaubt, ein empfangenes Paar $(x,mac)$ darauf zu testen, ob der zweite Teil der zu x gehörende MAC-Wert ist. Wenn Alice die einzige Instanz ist, die die geheime Funktion MAC kennt, dann kann Bob sogar überprüfen, ob Alice tatsächlich die Absenderin ist. } \note{Cäsar-Chiffre}{ Cäsar ließ Texte verschlüsseln, indem man nimmt immer den Buchstaben, der im Alphabet drei Positionen ,,weiter rechts'' steht, mit ,,wrap around'' am Ende. Nachteil ist offensichtlich: Wer den Trick kannte, konnte jede Nachricht mitlesen. Es gibt einen Schlüssel } \note{Verschiebechiffre}{ Eine einfache ,,Verbesserung'' der Cäsar-Chiffre: Verschiebe zyklisch um eine andere Anzahl k von Buchstaben als nur 3. Um hier die Verschlüsselung und die Entschlüsselung durchzuführen, musste man als ,,Schlüssel'' nur das Bild von A kennen, alternativ die Verschiebeweite k als Zahl. Es gibt dann 21 Schlüssel. } \note{Substitutionschiffre}{ Sie sagt, dass das Bild eines Buchstabens ein ganz beliebiger anderer Buchstabe sein soll. Dabei müssen natürlich verschiedene Buchstaben auf verschiedene Buchstaben abgebildet werden. Es er gibt sich eine Chiffre, die durch eine Tabelle mit ganz beliebiger Buchstabenanordnung gegeben ist. Wenn man hier ver- und entschlüsseln möchte, muss man die gesamte zweite Tabellenzeile kennen. Diese kann hier also als ,,Schlüssel'' dienen. Es gibt $21!\approx 5,11* 10^{19}$ viele verschiedene Schlüssel. } \note{Vigenère-Verschlüsselung (16.Jhd)}{ Man benutzt ein Schlüsselwort $a_0,...,a_{s-1}$ größerer Länge $s > 1$ über dem Alphabet $\{A,...,X\}$. $x=x_0...x_{n-1}$ ist der Klartext, $k=a_0 ...a_{s-1}$ der Schlüssel. Verschlüssle x mit den durch k gegebenen Verschiebungen wie folgt: $x_0$ mit $A \rightarrow a_0$ ,$x_2$ mit $A \rightarrow a_2,... ,x_{s-1}$ mit $A\rightarrow a_{s-1}$. Wenn der Schlüssel k aufgebraucht ist, benutze ihn wieder von vorne: Verschlüssle $x_i,i\geq s$, mit Verschiebung $A \rightarrow a_{i\ mod\ s}$. } kryptographische Verfahren mit Schlüsseln \begin{description*} \item[Symmetrisch (Private-Key)] Es gibt einen geheimen Schlüssel $k$, den beide der kommunizierenden Parteien kennen müssen. Bei Konzelationssystemen bedeutet dies etwa, dass das Verschlüsselungsverfahren und das Entschlüsselungsverfahren beide diesen Schlüssel $k=k'$ benutzen. Bsp. AES (Advanced Encryption Standard). \item[Asymmetrisch (Public-Key)] Nur eine Seite hat einen geheimen Schlüssel $k'$, die andere Seite benutzt einen ,,öffentlichen'' Schlüssel $k\not =k'$. Bsp. RSA \end{description*} \note{Das Kerckhoffs-Prinzip (1883)}{ besagt,dass man davon ausgehen muss, dass Eva die Struktur des Verschlüsselungsverfahrens kennt und die Sicherheit nur von der Geheimhaltung des Schlüssels abhängen darf. \begin{enumerate*} \item Geheimhaltung eines Verfahrens ist schwer sicherzustellen \item Verfahren sind aufwendig zu entwickeln. Ist das geheime Verfahren einmal bekannt, soist es nutzlos. (Mehrfach passiert: Enigma, GSM-Verfahren ,Stromchiffre RC4) \item Allgemein bekannte Verfahren können von mehr Experten auf ,,Sicherheit'' geprüft werden. Findet niemand einen erfolgreichen Angriff, so kann man eher auf Sicherheit des Verfahrens vertrauen \item Nur offen gelegte Verfahren können standardisiert werden und weite Verbreitung finden (DES, AES) \end{enumerate*} } \section{Symmetrische Sicherheitsmodelle} Angriffsszenarien/Bedrohungsszenarien \begin{enumerate*} \item ciphertext-only attack (COA): nur mithören \item known-plaintext attack (KPA): Paare von Klartext und Chiffretext bekannt \item chosen-plaintext attack (CPA): einige von Eva gewählte Klartexte verschlüsseln \item chosen-cyphertext attack (CCA): einige von Eva gewählte Chiffretexte entschlüsseln \item Eva hat hier Möglichkeiten 3. + 4. \end{enumerate*} Fähigkeiten von Eva (unter anderem) \begin{enumerate*} \item informationstheoretische Sicherheit: unbegrenzte Rechenkapazitäten \item Konkrete Sicherheit: maximale Anzahl an Rechenoperationen (z.B. $2^{60}$) und begrenzter Speicher (z.B. 1000 TB) \item Im Design des Verschlüsselungsverfahrens gibt es einen Stellhebel, einen ,,Sicherheitsparameter''. Je nach Leistungsfähigkeit von Eva kann man durch entsprechende Wahl dieses Parameters die Sicherheit des Systems an eine gegebene (geschätzte) Rechenzeitschranke anpassen. \item Asymptotische Sicherheit: wenn asymptotisch der Rechenzeitaufwand für Eva zum Brechen des Systems schneller als polynomiell wächst, kann man sagen, dass sie für genügend lange Texte keine Chance mehr hat, das System erfolgreich zu brechen \end{enumerate*} symmetrische Konzelationssysteme, mit steigender Komplexität. Alice und Bob haben sich auf einen Schlüssel geeinigt. \begin{enumerate*} \item Einmalige Verschlüsselung: Ein einzelner Klartext $x$ vorher bekannter Länge wird übertragen, Eva hört mit (COA) \begin{itemize*} \item Unvermeidlich: Triviale Information, z.B. dass eine Nachricht übertragen wurde \item Vermeiden Eva erhält nicht-triviale Information, z.B. Klartext$=x$ oder Klartext weder $x_1$ noch $x_2$ \item Gegenstand der Steganographie sind Verfahren, Nachrichten so zu übertragen, dass noch nicht einmal die Existenz der Nachricht entdeckt werden kann. \end{itemize*} \item Frische Verschlüsselung: Mehrere Klartexte vorher bekannter Länge werden übertragen, Eva hört mit, kann sich einige Klartexte verschlüsseln lassen (CPA). \begin{itemize*} \item Triviale Information: z.B. Anzahl der Nachrichten oder Klartext, falls Eva sich zufälligerweise vorher den ,,richtigen'' Klartext hat verschlüsseln lassen. \end{itemize*} \item Uneingeschränkte symmetrische Verschlüsselung: Mehrere Klartexte verschiedener Länge, Eva hört mit, kann sich einige Klartexte verschlüsseln lassen (CPA). \begin{itemize*} \item Triviale Information: Analog zur frischen Verschlüsselung \end{itemize*} \end{enumerate*} \subsection{Kryptosysteme und possibilistische Sicherheit} \textbf{Definition 1.1} Ein Kryptosystem ist ein Tupel $S=(X,K,Y,e,d)$, wobei \begin{itemize*} \item X und K nicht leere endliche Mengen sind [Klartexte bzw. Schlüssel], \item Y eine Menge ist [Chiffretexte], und \item $e:X\times K\rightarrow Y$ und $d:Y\times K\rightarrow X$ Funktionen sind [Verschlüsselungsfunktion bzw. Entschlüsselungsfunktion], \end{itemize*} so dass Folgendes gilt: \begin{enumerate*} \item $\forall x\in X\forall k\in K:d(e(x,k),k) =x$ (Dechiffrierbedingung) \item $\forall y\in Y\exists x\in X,k\in K:y=e(x,k)$ (Surjektivität) \end{enumerate*} Bemerkung: Surjektivität kann immer hergestellt werden, indem man $Y$ auf das Bild $Bi(e) =e(X\times K)$ einschränkt. Die Forderung ist für unsere Analysen aber bequem. Für festes $k\in K$ wird die Funktion $e(.,k):X\rightarrow Y,x \rightarrow e(x,k)$ als Chiffre bezeichnet. \textbf{Beispiel} $X=\{a,b\},K=\{k_0,k_1,k_2\},Y=\{A,B,C\}$. Die Funktion $e$ ist gegeben durch die erste, die Funktion $d$ durch die zweite der folgenden Tabellen. Dann ist $(X,K,Y,e,d)$ Kryptosystem, denn die Dechiffrierbedingung und die Surjektivität sind erfüllt. \begin{tabular}{c|c|c} e & a & b \\\hline $k_0$ & A & B \\ $k_1$ & B & A \\ $k_2$ & A & C \end{tabular} \begin{tabular}{c|c|c|c} d & A & B & C \\\hline $k_0$ & a & b & a \\ $k_1$ & b & a & a \\ $k_2$ & a & a & b \end{tabular} Jede Chiffre $e(.,k)$ eines Kryptosystems muss injektiv sein. (Die Einträge in jeder Zeile der Tabelle für $e$ müssen verschieden sein.) Das Vernam-Kryptosystem oder one-time pad der Länge $l$ ist das Kryptosystem $(\{0,1\}^l,\{0,1\}^l,\{0,1\}^l,\oplus_l,\oplus_l)$. Benannt nach Gilbert S. Vernam (1890, 1960), der im Jahr 1918 dieses System für fünf Bits in der Sprache einer Relais-Schaltung beschrieben und zum US-Patent angemeldet hat. In diesem Fall ist es für nicht ganz kleine l offensichtlich unbequem, wenn nicht ganz unmöglich, die Ver-und Entschlüsselungsfunktion durch Tabellen anzugeben. Man benutzt hier und auch üblicherweise mathematische Beschreibungen.\\ Beispiel: $x=1011001,k=1101010$. Dann ist $y=e(x,k)=1011001\oplus_7 1101010 = 0110011$. Zur Kontrolle: $d(y,k) = 0110011\oplus_7 1101010 = 1011001 =x$. Wir kontrollieren dass das Vernam-System tatsächlich ein Kryptosystem ist. \begin{enumerate*} \item Für $x\in X$ und $k\in K$ gelten $d(e(x,k),k)=(x\oplus_l k)\oplus_l k=x\oplus_l(k\oplus_l k) =x\oplus_l 0^l=x$, d.h. die Dechiffrierbedingung ist erfüllt. \item Für $y\in Y$ gilt $e(y,0^l) =y$ und $y\in X,0^l\in K$. Also gilt Surjektivität. \end{enumerate*} \textbf{Definition} Ein Kryptosystem $S=(X,K,Y,e,d)$ heißt possibilistisch sicher, wenn $\forall y\in Y\forall x\in X\exists k\in K:e(x,k)=y$. \begin{enumerate*} \item Sei $S=(X,K,Y,e,d)$ Kryptosystem. Dann sind äquivalent: \begin{itemize*} \item $S$ ist possibilistisch sicher. \item $\forall x\in X:e(x,K)=\{e(x,k)|k\in K\}=Y$. \end{itemize*} \item Das Vernam-Kryptosystem der Länge $l$ ist possibilistisch sicher: Seien $x\in X$ und $y\in Y$. Setze $k=x\oplus_l y$.Dann gilt $e(x,k)=x\oplus_l(x\oplus_l y)=(x\oplus_l x)\oplus_l y= 0^l\oplus_l y=y$. \end{enumerate*} \textbf{Definition} Für eine endliche, nichtleere Menge $X$ sei $K=P_X$ die Menge der Permutationen (bijektive Funktion $\pi:X\rightarrow X$) auf $X$. Das Substitutionskryptosystem auf $X$ ist das Tupel $(X,PX,X,e,d)$ mit $e(x,\pi)=\pi(x)$ und $d(y,\pi)=\pi^{-1} (y)$. Wenn $\pi:X\rightarrow X$ eine Permutation ist, dann ist $\pi^{-1}:X\rightarrow X$ die Permutation mit $\pi^{-1}(\pi(x))=\pi(\pi^{-1}(x)) =x$ für alle $x\in X$. Bei possibilistischer Sicherheit von Klartexten und Schlüsseln, die Zeichenreihen über einem Alphabet sind, müssen Schlüssel mindestens so lang sein wie der zu übermittelnde Text. unrealistisch $\rightarrow$ Possibilistisch sichere Systeme kommen daher nur als Bausteine in größeren Systemen vor. \subsection{Elementare Wahrscheinlichkeitsrechnung} \textbf{Definition}: Ein (diskreter) Wahrscheinlichkeitsraum ist ein Paar $(\Omega,Pr)$, wobei \begin{itemize*} \item $\Omega$ eine nichtleere endliche oder abzählbar unendliche Menge und \item $Pr:P(\Omega)\rightarrow[0,1]$ eine Abbildung ($P(\Omega)=\{A|A\subseteq\Omega\}$ ist die Potenzmenge) \end{itemize*} \textbf{Definition} Sei $(\Omega,Pr)$ ein Wahrscheinlichkeitsraum und seien $A,B$ Ereignisse. Dann heißen A und B unabhängig, wenn $Pr(A\cap B)=Pr(A)*Pr(B)$ gilt. \textbf{Definition} Sei $(\Omega,Pr)$ ein Wahrscheinlichkeitsraum und R eine endliche oder abzählbare Menge. Eine Zufallsvariable ist eine Abbildung $X:\Omega\rightarrow R$. Zufallsvariablen mit $R\subseteq R$ heißen reelle Zufallsvariable. \subsection{Informationstheoretische Sicherheit} Wenn sich durch das Beobachten einer Chiffre die Meinung von Eva über die Wahrscheinlichkeiten der verschiedenen Klartexte von der ursprünglichen Verteilung unterscheidet, hat Eva aus der Beobachtung von y eine gewisse Information erhalten. In das math. Modell $\Omega=X\times K$ bauen wir die Vorstellung ein, dass $x\in X$ und $k\in K$ nach den Verteilungen $Pr_X$ (Teil der Anwendung) und $Pr_K$ (Teil des Kryptosystems) zufällig und unabhängig gewählt werden. Die Verteilung $Pr_X$ braucht beim Entwurf des Kryptosystems nicht einmal bekannt zu sein. \textbf{Definition} Ein Kryptosystem mit Schlüsselverteilung (KSV) ist ein 6-Tupel $V=(X,K,Y,e,d,Pr_K)$, wobei \begin{itemize*} \item $S=(X,K,Y,e,d)$ das zugrundeliegende Kryptosystem ist \item $Pr_K:K\rightarrow (0,1]$ die Schlüsselverteilung \item Für $V=(X,K,Y,e,d,Pr_K)$ schreiben wir auch $S[Pr_K]$ \item $Pr_K(k)\in (0,1]$ also $Pr_K(k)> 0$ für alle $k\in K$ \item weiter $Pr_X:X\rightarrow [0,1]$ Klartextverteilung \item $Pr:X\times K\rightarrow [0,1]$ durch $Pr((x,k)):=Pr_X(x)*Pr_K(k)$ \item Annahme modelliert, dass der Schlüssel k unabhängig vom Klartext durch ein von $Pr_K$ gesteuertes Zufallsexperiment gewählt \end{itemize*} \textbf{Beispiel} Sei $X=\{a,b,c\},K=\{0,1,2,3\},Y=\{A,B,C\}$ und die Verschlüsselungsfunktion sei durch die folgende Tabelle gegeben: \begin{tabular}{c|c|c|c} e & a(0,4) & b(0) & c(0,6) \\\hline 0 ($\frac{1}{4}$) & A & B & C \\ 1 ($\frac{1}{8}$) & B & C & A \\ 2 ($\frac{1}{2}$) & C & A & B \\ 3 ($\frac{1}{8}$) & C & B & A \end{tabular} Die Wahrscheinlichkeiten $Pr_X(x)$ sind bei den Klartexten, die Wahrscheinlichkeiten $Pr_K(k)$ bei den Schlüsseln in Klammern notiert. Klartexte a und c sind aktiv, Klartext b ist passiv. Einige einfache Zusammenhänge, für $x_0\in X,k_0\in K,y_0\in Y$ \begin{itemize*} \item $X: X\times K \rightarrow X, (x,k)\rightarrow x$ \item $X: X\times K \rightarrow K, (x,k)\rightarrow k$ \item $Pr(x_0):=Pr(\{x_0\}\times K) = Pr_X(x_0)*Pr_K(K) = Pr_X(x_0)$. \item $Pr(k_0):=Pr(X\times\{k_0\})=Pr_X(X)*Pr_K(k_0)=Pr_K(k_0)$ \item Man erhält die ursprünglichen Wahrscheinlichkeiten für Klartexte und Schlüssel zurück \item Im Bsp $Pr(A)=\frac{1}{4}*0,4+ \frac{1}{8}*0,6 +\frac{1}{2}*0 +\frac{1}{8}* 0,6=0,25$ \item Im Bsp $Pr(c,A)=0,6*(\frac{1}{8}+\frac{1}{8})=0,15$ \item Im Bsp $Pr(c|A)=\frac{P(c,A)}{P(A)}=\frac{0,15}{0,25}=0,6$ \end{itemize*} \textbf{Definition} $V=(X,K,Y,e,d,Pr_K)$ ein Kryptosystem mit Schlüsselverteilung \begin{enumerate*} \item Sei $Pr_X$ eine Wahrscheinlichkeitsfunktion auf den Klartexten. Dann heißt $V$ informationstheoretisch sicher bezüglich $Pr_X$, wenn für alle $x\in X,y\in Y$ mit $Pr(y)>0$ gilt: $Pr(x) = Pr(x|y)$. \item Das KSV $V$ heißt informationstheoretisch sicher, wenn es bezüglich jeder beliebigen Klartextverteilung $Pr_X$ informationstheoretisch sicher ist. \end{enumerate*} \textbf{Satz: Informationstheoretische Sicherheit des Vernam-Systems} Sei $l>0$ und $S=(X,K,Y,e,d)$ mit $X=K=Y=\{0,1\}^l$ und $e=d=\oplus_l$ das Vernam-System der Länge $l$. Sei weiter $Pr_K:K\rightarrow [0,1]$ die Gleichverteilung. Dann ist $V=S[Pr_K]$ informationstheoretisch sicher. Es wird sich herausstellen, dass informationstheoretische Sicherheit in bestimmten Fällen Gleichverteilung auf den Schlüsseln erzwingt und dass die informationstheoretische Sicherheit eines KSV nichts mit den konkreten Wahrscheinlichkeiten der Klartextverteilung $Pr_X$ zu tun hat, sondern nur die Menge $\{x\in X|Pr_X(x)> 0\}$ der ''aktiven'' Klartexte relevant ist. $Pr(x|y) =\frac{Pr(x,y)}{Pr(y)}=\frac{Pr(y|x)*Pr(x)}{Pr(y)}=\frac{Pr_K(k_{x,y})*Pr(x)}{Pr(y)}=^* \frac{\frac{1}{|K|}*Pr(x)}{\frac{1}{|K|}}=Pr(x)$ \textbf{Satz} Sei $V= (X,K,Y,e,d,Pr_K)$ ein KSV mit $|X|=|Y|=|K|$. Dann sind äquivalent: \begin{enumerate*} \item $V$ ist informationstheoretisch sicher. \item $(X,K,Y,e,d)$ ist possibilistisch sicher und $Pr_K(k)=\frac{1}{|K|}$ für alle $k\in K$. \end{enumerate*} Der Satz besagt, dass man informationstheoretisch sichere Systeme mit $|X|=|Y|=|K|$ daran erkennt, dass in der Verschlüsselungstabelle in jeder Spalte alle Chiffretexte vorkommen (possibilistische Sicherheit) und dass die Schlüsselverteilung $Pr_K$ uniform ist. Auch in jeder Zeile kommen natürlich alle Chiffretexte vor: das liegt aber einfach an der Dechiffrierbedingung. Die Klartextverteilung ist irrelevant. Technisch hilfreich sind die folgenden Größen, die nur von der Verschlüsselungsfunktion und der Schlüsselverteilung abhängen \begin{itemize*} \item $P^x(y):=\sum_{k\in K, e(x,k)=y} Pr(k)$ für $x\in X,y\in Y$ (1.1) \item Für alle $x\in X:Pr(x,y) = Pr(x)*P^x(y)$ (1.2) \item wenn $Pr(x)> 0:Pr(y|x) = \frac{Pr(x,y)}{Pr(x)}=P^x(y)$ (1.3) \end{itemize*} \textbf{Lemma} Sei $V=(X,K,Y,e,d,Pr_K)$ KSV und seien $Pr_X$ und $Pr'_X$ Klartextverteilungen mit $Pr'_X(x)>0\Rightarrow Pr_X(x)>0$. Dann gilt: Ist $V$ informationstheoretisch sicher bzgl. $Pr_X$, so ist V informationstheoretisch sicher bzgl. $Pr'_X$. Besagt, dass man die Wahrscheinlichkeiten aktiver Klartexte beliebig ändern kann, ohne dass eine bestehende informationstheoretische Sicherheit zerstört wird. Beweis: Sei $V$ informationstheoretisch sicher bzgl. $Pr_X$. Wir zeigen nacheinander vier Aussagen. \begin{enumerate*} \item $Pr_X(x)> 0 \Rightarrow Pr^x(y) = Pr(y|x) = Pr(y)$ für alle $y\in Y$ \item $Pr'_X(x)> 0 \Rightarrow Pr'(y|x) = Pr(y)$ für alle $y\in Y$ \item $Pr'(y)=Pr(y)$ für alle $y\in Y$ \item $Pr'(x)=Pr'(x|y)$ für alle $x\in X,y\in Y$ mit $Pr'(y)>0$ \end{enumerate*} \textbf{Satz} Sei $V=(X,K,Y,e,d,Pr_K)$ KSV und sei $Pr_X$ eine Klartextverteilung. Dann sind äquivalent: \begin{enumerate*} \item V ist informationstheoretisch sicher für $Pr_X$. \item Für jedes $x\in X$ und jedes $y\in Y$ gilt: $Pr(x,y)=Pr(x)Pr(y)$ (das Eintreten von x und das Eintreten von y sind unabhängig). \item Für alle $x\in X$ mit $Pr(x)>0$ und alle $y\in Y$ gilt $Pr(y)=Pr(y|x)$ (andere Formulierung der Unabhängigkeit). \item Für alle $x,x'\in X$ mit $Pr(x),Pr(x')>0$ und alle $y\in Y$ gilt $P^x(y)=P^{x'}(y)$. \end{enumerate*} Die informationstechnische Sicherheit drückt sich dadurch aus, dass diese Chiffretextwahrscheinlichkeiten auch für jeden Klartext (also jede Spalte) separat auftreten. \subsection{Cyphertext-only-Angriffe: Vigenère-Chiffre} Eine Folge $x=x_0 ...x_{l-1}$ von Buchstaben im Klartextalphabet $\{a,...,z\}$ der Größe 26. Ein informationstheoretisch sicheres Verfahren ist, für jede Buchstabenposition $0\geq i < L$ rein zufällig einen Schlüssel $k_i\in\{A,...,Z\}$ zu wählen und an Position $i$ die Verschiebechiffre mit Schlüssel $k_i$ anzuwenden. Der Schlüssel $k_0,...,k_{L-1}$ ist dann aber mindestens so lang wie die Klartextfolge. Allerdings ist das nach unseren bisherigen Ergebnissen auch unvermeidlich: Wenn $V=(X,K,Y,e,d,Pr_K)$ informationstheoretisch sicher ist, ist $(X,K,Y,e,d)$ possibilistisch sicher, also $|X|\geq |K|$. \subsubsection{Viginère Angriffe bei bekannter Schlüssellänge} \textbf{Definition} Eine Verschiebechiffre ist ein Kryptosystem $S=(Z_n,Z_n,Z_n,e,d)$ mit $e(x,k)=(x+k) mod\ n$. (Offensichtlich ist dann $d(y,k)=(y-k)mod\ n$.) Unser Beispiel ist der Fall $n=26$, also $X=Y=K=\{0,1,2,...,25\}$. Wir identifizieren die Elemente dieser Menge mit den Buchstaben $a,...,z$ (bei X) bzw. $A,...,Z$ (bei K und Y). Die einfachste Methode ist folgende Version der Cäsar-Chiffre: Wähle einen Schlüssel k aus $K=\{0,1,...,25\}=\{A,...,Z\}$ zufällig. Um ,,Texte'' (d.h. Wörter über $\mathbb{Z}_n$) zu verschlüsseln, wird S buchstabenweise angewandt: Aus $x_0 x_1...x_{l-1}$ wird $e(x_0,k)e(x_1,k)...e(x_{l-1},k)$. Diese Methode ist allerdings sehr leicht zu brechen, sogar ,,von Hand''. Es gibt mindestens die folgenden naheliegenden Möglichkeiten \begin{enumerate*} \item probiere die 26 möglichen Schlüssel aus, oder \item zähle, welche Buchstaben am häufigsten im Chiffretext vorkommen und teste die Hypothese, dass einer von diesen für ,,e'' steht (Häufigkeitstabellen) \end{enumerate*} \textbf{Definition} Das Vigenère-Kryptosystem (mit Parametern $(n,S,L)\in\mathbb{N}^3$) ist das Kryptosystem ($(\mathbb{Z}_n)\geq L,(\mathbb{Z}_n)\geq S,(\mathbb{Z}_n)\geq L,e,d$), so dass für alle $s\geq S,l\geq L,x_i,k_j\in\mathbb{Z}_n$ gilt: $e(x_0...x_{l-1},k_0 ...k_{s-1})=y_0 ...y_{l-1}$ mit $y_i=(x_i+k_{i\ mod\ s}) mod\ n$, für alle $0\geq i < l$. Die zentrale Idee ist, dass für die Verschlüsselung des ,,Teiltextes'' $y_i=y_iy_{i+s}y_{i+2s}...$, für $0\geq iN(log_2 N-log_2 e)> N(log_2 N- 1.45)$) $log(2^{128}!)> 2^{128}*(128- 1.45)> 2^{134}>(10^3 )^{13.4} > 10^{40}$ viele Bits, eine unpraktikable Zahl. Also können wir in realen Situationen im Szenarium 2 keine possibilistische Sicherheit, geschweige denn informationstheoretische Sicherheit erhalten. \textbf{Definition} Sei $l>0$. Ein l-Block-Kryptosystem ist ein Kryptosystem $S=(\{0,1\}^l,K,\{0,1\}^l,e,d)$ mit $K\subseteq \{0,1\}^s$ für ein $s>0$. \subsection{Substitutions-Permutations-Kryptosysteme (SPKS)} Grundsätzlich handelt es sich um $mn$-Block-Kryptosysteme. Dabei werden die Klartexte $x=(x_0,...,x_{mn-1})\in\{ 0,1\}^{mn}$ als m-Tupel $(x^{(0)},x^{(1)},...,x^{(m-1)})$ von Bitvektoren der Länge n betrachtet. Dabei gilt $x(i)=(x_{in},x_{in+1},...,x_{(i+1)n-1})$, für $0\leq i10^{38}$ beträgt. Um diesen Trick auszuschließen, werden wir den Ressourcenverbrauch eines Algorithmus als Summe von Laufzeit und Länge des Programmcodes (=Größe der Transitionstabelle der Turingmaschine) messen. Die Programmgröße ist eine untere Schranke für die Zeit, die Eva zur Erstellung ihres Programms benötigt. Unser Ressourcenmaß erfasst also die Zeit für die Erstellung und die Zeit für die Ausführung des Algorithmus.ünsere Algorithmen werden oft mit Kryptosystemen einer festen Blocklänge $l$ und einer fixen Anzahl von Klartext-/Chiffretext-Paaren arbeiten. Damit sind nur endlich viele Eingaben möglich, der Ressourcenverbrauch kann also nicht asymptotisch (,,bei großen Eingaben'') angegeben werden. Daher betrachten wir zunächst Algorithmen mit konstanter Laufzeit. Das führt dazu, dass alle eventuell vorhandenen Schleifen nur konstant oft durchlaufen werden. Damit können wir aber auf Schleifenanweisungen vollständig verzichten. Die resultierenden Programme heißen ,,Straight-Line-Programme''. Man kann sie sich in Pseudocode geschrieben vorstellen (ohne ,,while'' und ,,for'' und ohne Rückwärtssprünge), oder als Turingmaschinenprogramme mit der Eigenschaft, dass nie eine Programmzeile zweimal ausgeführt wird. \paragraph{Randomisierung bei Straight-Line-Programmen} In unseren Algorithmen wollen wir zusätzlich die Anweisung ,,$y\leftarrow flip(M)$'' erlauben, wobei $M$ eine endliche Menge ist. Die Idee dabei ist, dass der Variable $y$ ein zufälliges Element von $M$ (bzgl. der Gleichverteilung auf $M$) zugewiesen wird. Damit berechnen unsere Algorithmen keine Funktionen, sondern zufällige Werte, die durch eine Wahrscheinlichkeitsverteilung gesteuert werden.üm den Wahrscheinlichkeitsraum definieren zu können, machen wir die folgenden Annahmen (die keine Einschränkung darstellen): \begin{enumerate*} \item Bei nacheinander ausgeführten Kommandos der Form $y\leftarrow flip(M)$, mit identischem oder unterschiedlichem $M$, werden immer neue, unabhängige Zufallsexperimente ausgeführt. \item Wie eben diskutiert, enthalten unsere Algorithmen keine Schleifen. Wir können daher jedes Ergebnis eines Zufallsexperiments in einer eigenen Variable speichern. Zusätzlich können wir die flip-Kommandos aus dem gesamten Programm, auch den bedingten Anweisungen, herausziehen und sie alle (vorab, auf Vorrat) ausführen. Damit können wir annehmen: Wenn die Anweisung $y\leftarrow flip(M)$ im Programmtext vorkommt, dann wird sie in jedem Durchlauf des Algorithmus (unabhängig von der Eingabe und den Ergebnissen der flip-Anweisungen) genau einmal ausgeführt. \end{enumerate*} Abkürzung: $flip(l)$ für $flip(\{0,1\}^l)$ (l-facher Münzwurf) und $flip()$ für $flip(1)$, also $flip(\{0,1\})$ (einfacher Münzwurf). Sei nun A ein randomisierter Algorithmus (also ein Straight-Line-Programm), indem die $flip$-Anweisungen $y_i\leftarrow flip(M_i)$ für $1\geq i\geq r$ vorkommen. Dann verwenden wir als zugrundeliegenden Wahrscheinlichkeitsraum die Menge $M=M_1\times M_2\times...\times M_r$ mit der Gleichverteilung. Dies modelliert die Idee, dass die $r$ Zufallsexperimente jeweils mit der uniformen Verteilung und insgesamt unabhängig voneinander ausgeführt werden. $I$ sei die Menge der Eingaben, $Z$ sei die Menge der Ausgaben. Ist $x\in I$ eine Eingabe, so erhalten wir für jedes $m=(m_1,...,m_r)\in M$ genau eine Ausgabe $A^m(x)\in\mathbb{Z}$, indem wir in $A$ die Anweisung $y_i\leftarrow flip(M_i)$ durch $y_i\leftarrow m_i$ ersetzen. Auf diese Weise erhalten wir \begin{itemize*} \item Für jedes $m\in M$ eine Funktion $A^m:I\rightarrow Z,x \rightarrow A^m(x)$, und \item für jedes $x\in I$ eine Zufallsgröße $A(x):M\rightarrow Z,m\rightarrow A^m(x)$. \end{itemize*} \textbf{Beispiel}2.8 Betrachte den folgenden Algorithmus: \begin{itemize*} \item $A(x:\{0,1\}^4):\{0,1\}$ // nach dem Doppelpunkt: Typ der Eingabe bzw. Ausgabe \item $b_0 \leftarrow flip()$ \item $b_1 \leftarrow flip()$ \item $b_2 \leftarrow flip()$ \item $b_3 \leftarrow flip()$ \item $if b_0 = 1 \text{ then return } x(0)$ \item $if b_1 = 1 \text{ then return } x(1)$ \item $if b_2 = 1 \text{ then return } x(2)$ \item $if b_3 = 1 \text{ then return } x(3)$ \item return 1 \end{itemize*} Dann ist $M=\{0,1\}^4$, und es gilt: $A^{0110}(1101)=1$ und $A^{0010}(1101)=0$. Kompakt: Wenn $b_0 b_1 b_2 b_3$ mit $i$ Nullen und einer $1$ (an Position $i$) beginnt, dann ist die Ausgabe $x(i)$, für $i=0,1,2,3$. Ist $b_0 b_1 b_2 b_3=0000$, so ist die Ausgabe 1. Also gilt: $Pr(A(1101)=0) = Pr(\{w\in\{0,1\}^4 |w_0=w_1=0, w_2=1\}) =(\frac{1}{2})^3 =\frac{1}{8}$ und $Pr(b_1=1) =Pr(\{w\in\{0,1\}^4 |w(1)=1\})=\frac{1}{2}$ Damit erhalten wir auch sinnvolle kombinierte und bedingte Wahrscheinlichkeiten: $Pr(A(1101)=0, b_0=0)= Pr(\{w\in\{0,1\}^4 |w_0=w_1=0, w_2=1\}) =\frac{1}{8}$ und $Pr(A(1101)=0| b_0=0) =\frac{Pr(A(1101)=0, b_0=0)}{Pr(b_0=0)}=\frac{1}{4}$ Wir können auch den Algorithmus $A$ so ändern, dass eine Anweisung $y_i\leftarrow flip(M_i)$ durch $y_i\leftarrow m^{(0)}_i$ ersetzt wird. (Diesen Algorithmus bezeichnen wir dann mit $A(y_i=m^{(0)}_i)$.) Es gilt dann für alle Eingaben $x$ und Ausgaben $z$: $Pr(A(x)=z| y_i=m^{(0)}_i) =Pr(A(y_i=m^{(0)}_i)(x) =z)$. Die verallgemeinerte Notation $A(y_1=m^{(0)}_1,...,y_s=m^{(0)}_s)$ erklärt sich von selbst. \paragraph{Prozeduren als Parameter} Wir werden Algorithmen $A$ betrachten, die als Eingabe eine Prozedur $B$ (z.B. die Verschlüsselungsfunktion einer Blockchiffre mit fest eingesetzem Schlüssel) erhalten. Diese Prozedur darf nur aufgerufen werden, sie wird nicht als Text in den Rumpf von $A$ eingefügt. Sie könnte aber wiederum zufallsgesteuert sein. Um den Wahrscheinlichkeitsraum von $A$ mit einem solchen Funktionsparameter zu bestimmen, müssen folgende Informationen gegeben sein: \begin{itemize*} \item $B$, \item die Anzahl der Aufrufe von $B$ in $A$, \item welche Aufrufe $y\leftarrow flip(M)$ in $B$ vorkommen. \end{itemize*} Wir behandeln dann die Variablen $y$ in verschiedenen Aufrufen von $B$ genau wie die aus einem gewöhnlichen randomisierten Programm (Umbenennen der Variablen, Herausziehen der Zufallsexperimente an den Anfang). In dem resultierenden Wahrscheinlichkeitsraum sind dann die Zufallsexperimente in den verschiedenen Aufrufen von $B$ und die in Teilen von $A$ außerhalb von $B$ unabhängig. \subsubsection{Sicherheit von Block-Kryptosystemen} Wir betrachten hier l-Block-Kryptosysteme $B=(X,K,Y,e,d)$ mit $X=Y=\{0,1\}^l$ und $K\subseteq\{0,1\}^s$ für ein $s$. $e$ ist die Verschlüsselungsfunktion und $d$ die Entschlüsselungsfunktion. Wir erinnern uns: \begin{enumerate*} \item Im Szenario 2 (chosen-plaintext attack,CPA) kann die Angreiferin Eva sich eine ,,geringe Zahl'' von Klartexten verschlüsseln lassen, also hat sie eine Liste von Klartext-Chiffretext-Paaren: $(x_1,y_1),...,(x_r,y_r)$. Nun kann jedenfalls nur ein ,,neuer'' Klartext $x$, also ein $x\in X\{x_1,...,x_r\}$, geheim übertragen werden. Die possibilistische Sicherheit verlangt genau, dass dies möglich ist: Wenn $y\in Y\{y_1,...,y_r\}$ ein neuer gegebener Chiffretext ist, dann gibt es für jeden Klartext $x\in X\{x_1,...,x_r\}$ einen Schlüssel $k$, der $x_i$ zu $y_i$ chiffriert, $1 \geq i\geq r$, und $x$ zu $y$ chiffriert. \item Wenn dabei $r$ beliebig groß sein darf, können nach Prop.2.3 nur Substitutionskryptosysteme in diesem Sinne sicher sein. Da sie $|X|!$ Schlüssel haben müssen und daher immense Schlüssellänge (mindestens $|X|log|X|-O(|X|)$ Bits) erfordern, kommen sie in der Praxis nicht in Frage. \end{enumerate*} Idee eines neuen Sicherheitsbegriffs (für Block-Kryptosysteme): Gegeben sei eine Angreiferin Eva mit beschränkten Berechnungsressourcen. Wir fragen, wie sehr aus Evas Sicht das $l$-Block-Kryptosystem $B=(\{0,1\}^l,K,\{0,1\}^l,e,d)$ dem Substitutionskryptosystem $S'=(\{0,1\}^l,P\{0,1\}^l,\{0,1\}^l,e',d')$ (siehe Def.1.9) ähnelt. Ist es ihr mit ,,signifikanter Erfolgswahrscheinlichkeit'' möglich, aufgrund der ihr vorliegenden Information und im Rahmen ihrer Ressourcen, zu unterscheiden, welches der beiden Systeme verwendet wird? Wenn dies nicht der Fall ist, kann das Kryptosystem $B$ als sicher gelten, wie die folgende Überlegung zeigt. Wenn Eva aufgrund der ihr vorliegenden Information (2.4) nicht mit nennenswerter Erfolgswahrscheinlichkeit unterscheiden kann, ob sie es mit der Chiffre $e(.,k)$ (für ein zufälliges $k\in K$) oder mit $e'(.,\pi)$ (für ein zufälliges $\pi\in P_{\{0,1\}^l}$) zu tun hat, dann hat sie aus der ihr vorliegenden Information keine nennenswerte Information über die konkrete Chiffree $(.,k)$ gelernt. Insbesondere kann sich ihre Information über die Klartextverteilung nicht (wesentlich) ändern, wenn ihr ein neuer Chiffretext $y$ vorgelegt wird, da bei $S'=(\{0,1\}^l,P\{0,1\}^l,\{0,1\}^l,e',d')$ keine solche Änderung eintritt. Wir modellieren Verfahren, die eine Chiffre benutzen dürfen und dann ,,raten'' sollen, ob es eine Chiffre zu einem BKS $B$ oder eine Zufallspermutation ist, als randomisierte Algorithmen. \textbf{Definition} 2.9 Ein l-Unterscheider ist ein randomisierter Algorithmus $U(F:\{0,1\}^l\rightarrow\{0,1\}^l):\{0,1\}$, dessen Laufzeit bzw. Ressourcenaufwand durch eine Konstante beschränkt ist. Das Argument des l-Unterscheiders ist also eine Chiffre $F$. Diese ist als ,,Orakel'' gegeben, das heißt als Prozedur, die nur ausgewertet werden kann, deren Programmtext $U$ aber nicht kennt. Das Programm $U$ kann $F$ endlich oft aufrufen, um sich Paare wie in (2.4) zu besorgen. Danach kann $U$ noch weiter rechnen, um zu einer Entscheidung zu kommen. Das von $U$ gelieferte Ergebnis ist ein Bit. Am liebsten hätte man folgendes Verhalten, für ein gegebenes Block-Kryptosystem $B$: Programm $U$ sollte 1 liefern, wenn $F$ eine Chiffre $e(.,k)$ zu $B$ ist, und $0$, wenn $F=\pi$ für eine Permutation $\pi\in P\{0,1\}^l$ ist, die keine $B$-Chiffre ist. Das gewünschte Verhalten wird sich bei $U$ natürlich niemals mit absoluter Sicherheit, sondern nur mit mehr oder weniger großer Wahrscheinlichkeit einstellen, je nach Situation. \textbf{Beispiel}2.10 Als Beispiel betrachten wir das Vernam-Kryptosystem $B=B_{Vernam}$, siehe Beispiel 1.6. Wir definieren einen l-Unterscheider $U=U_{Vernam}$, der als Parameter eine Funktion $F:\{0,1\}^l\rightarrow\{0,1\}^l$ erhält und Folgendes tut: \begin{enumerate*} \item $k\leftarrow F(0^l)$ \item $y\leftarrow F(1^l)$ \item falls $1^l\oplus_l k=y$, dann gib $1$ aus, sonst $0$. \end{enumerate*} Dieser Unterscheider benutzt keine Zufallsexperimente, obwohl es ihm erlaubt wäre. Man sieht leicht Folgendes: Wenn $F(.) =e(.,k)$ für die Vernam-Chiffre mit beliebigem Schlüssel $k$, liefert $U_{Vernam}$ immer das Ergebnis 1. Wenn hingegen $F$ eine zufällige Permutation $\pi$ von $\{0,1\}^l$ ist, dann ist die Wahrscheinlichkeit, dass $F(1^l)=1^l\oplus_l F(0^l)$ gilt, genau $\frac{1}{2^{l-1}}$, also wird die Ausgabe $1$ nur mit sehr kleiner Wahrscheinlichkeit ausgegeben (wenn $l$ nicht ganz klein ist). Wir definieren nun ein Spiel (,,game''), mit dem ein beliebiges Block-Kryptosystem $B$ und ein beliebiger Unterscheider $U$ darauf getestet werden, ob $B$ gegenüber $U$ ,,anfällig'' ist oder nicht. (Das Spiel ist ein Gedankenexperiment, es ist nicht algorithmisch.) Die Idee ist folgende: Man entscheidet mit einem Münzwurf (Zufallsbit b), ob $U$ für seine Untersuchungen als $F(.)$ eine zufällige Chiffre $e(.,k)$ von $B$ (,,Realwelt'') oder eine zufällige Permutation $\pi$ von $\{0,1\}^l$ (,,Idealwelt'') erhalten soll. Dann rechnet $U$ mit $F$ als Orakel und gibt dann seine Meinung ab, ob er sich in der Realwelt oder in der Idealwelt befindet. U ,,gewinnt'', wenn diese Meinung zutrifft. \textbf{Definition} 2.11 Sei $B=(\{0,1\}^l,K,\{0,1\}^l,e,d)$ ein l-Block-Kryptosystem, und sei $U$ ein Unterscheider. Das zugehörige Experiment (oder Spiel) ist der folgende Algorithmus: \begin{itemize*} \item $GBU():\{0,1\}$ // kein Argument, Ausgabe ist ein Bit \begin{enumerate*} \item $b\leftarrow flip(\{0,1\})$ \begin{itemize*} \item if $b=1$ (,,Realwelt'') then $k\leftarrow flip(K);F\leftarrow e(.,k)$ // Zufallschiffre von B \item if $b=0$ (,,Idealwelt'') then $F\leftarrow flip(P\{0,1\}^l)$ // Zufallspermutation \end{itemize*} \item $b'\leftarrow U(F)$ // Der l-Unterscheider versucht herauszubekommen, ob $b=0$ oder $b=1$ gilt. \item if $b=b'$ then return 1 else return 0. // 1 heißt, dass $U$ das richtige Ergebnis hat. \end{enumerate*} \end{itemize*} Das verkürzte Experiment/Spiel $S^B_U$ (,,short'') gibt im 3.Schritt einfach $b'$ aus. Der Wahrscheinlichkeitsraum für die Analyse des Spiels wird über die Zufallsexperimente zur Wahl von b, von k, der Zufallspermutation $\pi$ aus $P_{\{0,1\}^l}$ und die Zufallsexperimente in $U$ gebildet. Die Wahrscheinlichkeit dafür, dass der Unterscheider richtig liegt, ist $Pr(G^B_U=1)$, gemessen in diesem etwas verschachtelten Wahrscheinlichkeitsraum. Wir erläutern intuitiv, wieso diese Definition eine sehr allgemeine Situation erfasst. Angenommen, Angreiferin Eva kann auf irgendeine algorithmische Weise mit einer gewissen positiven Wahrscheinlichkeit eine ,,nicht triviale Information'' über die Klartexte gewinnen, wenn diese mittels einer zufälligen Chiffre des l-Block-Kryptosystems $B$ verschlüsselt worden sind. Damit kann sie einen Unterscheider mit nichttrivialer Erfolgswahrscheinlichkeit bauen! Sie ruft die Verschlüsselungsfunktion $F$ auf, um einige selbstgewählte Klartexte $x_1,...,x_q$ zu $F(x_1)=y_1,...,F(x_q)=y_q$ zu verschlüsseln. Dann berechnet sie aus $y_1,...,y_q$ ihre ,,nichttriviale Information'' $I_1,...,I_q$ zu den entsprechenden Klartexten und prüft, ob $I_r$ auf $x_r$ zutrifft, für $r=1,...,q$. Gibt es eine gute Übereinstimmung, so geht sie davon aus, dass $F$ aus der ,,Realwelt'' stammt, also eine Chiffre von $B$ ist. Ansonsten vermutet sie, dass $F$ aus der ,,Idealwelt'' stammt, also eine zufällige Permutation ist. \textbf{Beispiel}2.12 Für einen l-Bit-String $z$ sei $p(z)=\oplus_{1 \geq i\geq l} z_i$ seine Parität. Nehmen wir an, das Chiffrierverfahren von $N$ ist unvorsichtig geplant und zwar so, dass $p(e(x,k)) =p(x)$ ist für beliebige $x\in X$ und $k\in K$. Bei der Chiffrierung ändert sich also die Parität nicht. (Die Parität ist sicher ,,nichttriviale Information'', auch wenn sie vielleicht nicht unmittelbar nützlich ist.) $U_{Paritaet}(F)$: \begin{enumerate*} \item Wähle Klartexte $x_1,...,x_q$ mit $p(x_1)=...=p(x_q) = 0$. \item $y_r\leftarrow F(x_r)$, für $r=1,...,q$. \item falls $p(y_1)=...=p(y_q)=0$, dann gib 1 aus, sonst 0. \end{enumerate*} Wenn wir in der ,,Realwelt'' sind $(b=1)$, also $F$ eine Chiffre $e(.,k)$ ist, dann ist die Antwort von $U$ immer ,,1'', also korrekt. Wenn wir in der ,,Idealwelt'' sind $(b=0)$, also $F$ eine zufällige Permutation ist, dann ist die Antwort nur mit Wahrscheinlichkeit $\frac{2^{l-1} (2^{l-1} -1)(2^{l-1}-2)...(2^{l-1} -q+ 1)}{2^l (2^l-1)(2^l-2)...(2^l-q+ 1)} \geq \frac{1}{2^q}$ falsch. (Alle Werte $F(x_1),...,F(x_q)$ müssen zufällig zu Chiffretexten geführt haben, die Parität 0 haben, von denen es $2^{l-1}$ viele gibt.) Es ergibt sich $Pr(G^B_U= 1)\geq\frac{1}{2} (1+1-2^{-q}) =1-2^{-(q+1)}$. Mit der effizienten Berechenbarkeit der ,,nichttrivialen Information'' hat man also einen Unterscheider gefunden, der $Pr(G^B_U=1)$ ,, groß'' macht. Beispiel: Der folgende triviale l-Unterscheider $U_{trivial}$ erreicht $Pr(G^B_{U_{trivial}}= 1)=\frac{1}{2}$: $b\leftarrow flip(\{0,1\}); return\ b$. Daher interessieren wir uns nicht für die Wahrscheinlichkeit $Pr(G^B_U= 1)$ ansich, sondern für den Abstand von $Pr(G^B_U=1)$ zu $Pr(G^B_{U_{trivial}}= 1) =\frac{1}{2}$: \textbf{Definition} 2.13 Sei $U$ ein l-Unterscheider und $B$ ein l-Block-KS. Der Vorteil von $U$ bzgl. B ist $adv(U,B):= 2(Pr(G^B_U=1)-\frac{1}{2})$ Klar ist: \begin{itemize*} \item Für jeden l-Unterscheider $U$ und jedes l-Block-KS $B$ gilt $-1\geq adv(U,B)\geq 1$. \item Werte $adv(U,B)<0$ sind uninteressant. (Wenn man einen Unterscheider $U$ mit $adv(U,B)<0$ hat, sollte man in $U$ die Ausgaben $0$ und $1$ vertauschen und erhält einen Unterscheider mit positivem Vorteil.) \item Für den trivialen l-Unterscheider $U_{trivial}$ gilt $adv(U,B) = 0$.üm den Vorteil eines Unterscheiders auszurechnen, sind seine ,,Erfolgswahrscheinlichkeit'' und seine ,,Misserfolgswahrscheinlichkeit'' hilfreiche Werte: Der Erfolg von U bzgl. B ist (für das verkürzte Spiel $S=S_U^B$) $suc(U,B) := Pr(S\langle b= 1\rangle = 1)$, d.h. die Wahrscheinlichkeit, dass U die Verwendung des l-Block-KS B richtig erkennt. Der Misserfolg ist $fail(U,B) := fail(U) := Pr(S\langle b= 0\rangle = 1)$, d.h. die Wahrscheinlichkeit, dass U die Verwendung des idealen Substitutionskryptosystems nicht erkennt. Man kann in der Notation für ,,fail'' das ,,B'' auch weglassen, da im Fall $b=0$ das Kryptosystem B überhaupt keine Rolle spielt. \end{itemize*} \textbf{Lemma} 2.14 $adv(U,B) = suc(U,B)-fail(U)$. Beweis: $Pr(G^B_U= 1) = Pr(S_U^B=b)$ \begin{itemize*} \item $= Pr(S_U^B= 1,b= 1) + Pr(S_U^B= 0,b= 0)$ \item $= Pr(S_U^B= 1|b= 1)* Pr(b= 1) + Pr(S^B_U= 0|b= 0)*Pr(b= 0)$ \item $=\frac{1}{2}( Pr(S_U^B\langle b= 1\rangle = 1) + Pr(S_U^B\langle b= 0\rangle = 0))$ \item $=\frac{1}{2}( Pr(S_U^B\langle b= 1\rangle = 1) + (1-Pr(S_U^B\langle b= 0\rangle = 1)))$ \item $=\frac{1}{2}( (suc(U,B) + (1-fail(U)))$ \item $=\frac{1}{2}(suc(U,B)-fail(U)) + \frac{1}{2}$ \end{itemize*} Durch Umstellen ergibt sich die Behauptung. Unterscheider mit Werten $adv(U,B)$ substanziell über 0 können als interessant (oder möglicherweise gefährlich) für B gelten. Wir müssen noch die beschränkten Ressourcen des Unterscheiders ins Spiel bringen. \textbf{Definition} 2.15 Sei $l\in\mathbb{N}$, U ein l-Unterscheider, B ein l-Block-KS. Für $q,t\in\mathbb{N}$ heißt U $(q,t)$-beschränkt, wenn die Laufzeit des Aufrufs von U innerhalb von $G^B_U$ durch t beschränkt ist und dieser Aufruf die Funktion F mit höchstens $q$ verschiedenen Argumenten ausführt. \textbf{Beispiel}2.10 (Fortsetzung) Der l-Unterscheider $U_{Vernam}$ wertet die Funktion $F$ an zwei Stellen $0^l$ und $1^l$ aus. Die Laufzeit des Aufrufs von $U$ ist beschränkt durch $c*l$ für eine Konstante $c\geq 1$. Also ist $U_{Vernam}$ $(2,c*l)$-beschränkt. \textbf{Definition} 2.16 Sei $\epsilon>0$. Dann heißt $B(q,t,\epsilon)$-sicher, wenn für jeden $(q,t)$-beschränkten l-Unterscheider $U$ gilt $adv(U,B)< \epsilon$. Man kann diese Bedingung auch umgedreht lesen, nämlich so: ,,Um mit Wahrscheinlichkeit größer als $\frac{1}{2}(1 +\epsilon)$ im Experiment $G^B_U$ die richtige Antwort 1 zu erzeugen, braucht ein l-Unterscheider mehr als q Auswertungen oder mehr Laufzeit/Platz als $t$.'' Mit beliebig hohen Rechenzeiten lassen sich praktisch alle Block-Kryptosysteme brechen, selbst mit sehr kleinem $q$. \textbf{Beispiel}2.10 (Fortsetzung) Sei $B$ das Vernam-System der Länge $l$. Um den Vorteil von $U_{Vernam}$ bzgl. $B$ zu bestimmen, berechnen wir Erfolg und Misserfolg von $U$: Es gilt offensichtlich $1=Pr(S^B_U\langle b= 1\rangle = 1) = suc(U,B)$. Es gilt $fail(U) = Pr(S^B_U\langle b= 0\rangle = 1) = Pr(S_U^B= 1|b= 0)$. Das verkürzte Experiment $S_U^B$ gibt 1 aus, wenn der Unterscheider $U$ dies tut. Dieser tut es aber genau dann, wenn $1^l\oplus_l F(0^l) =F(1^l)$ gilt, d.h. $fail(U) = Pr(S_U^B\langle b= 0\rangle = 1) = Pr(1^l\oplus_l F(0^l) =F(1^l)) = \frac{1}{2^l- 1}$. Damit haben wir aber $adv(U,B) = suc(U,B)-fail(U) = 1-\frac{1}{2^l- 1}=\frac{2^l-2}{2^l-1}\approx 1$. Das Vernam-System der Länge $l$ ist also nicht $(2,c*l,\frac{2^l- 2}{2^l- 1})$-sicher. Dafür realistische Werte von $l$ (z.B. 128) der Wert $\frac{2^l-2}{2^l-1}$ praktisch 1 ist, muss das Vernam-System im Szenario 2 als unsicher angesehen werden. Natürlich sieht man auch mit bloßem Auge, dass die Vernam-Chiffre bei mehrfacher Verwendung nicht ,,sicher'' ist, da sie leicht entschlüsselt werden kann. Hier geht es aber um die Formulierung eines Sicherheitskonzepts, das allgemein anwendbar ist. Es ist beruhigend, dass im Fall der Vernam-Chiffre herauskommt, dass sie auch im Sinn dieser Definition unsicher ist. Am obigen Beispiel eines Block-Kryptosystems, das die Parität von $x$ auf den Chiffretext $e(x,k)$ überträgt, sieht man aber auch, dass das Unterscheiderkonzept sehr empfindlich ist: Obwohl die Information über die Parity klein und harmlos scheint, erklärt es das System für nicht $(q,O(ql), 1-2^{-q})$-sicher, weil die Auswertung der Parität nur Zeit $O(l)$ kostet. \textbf{Beispiel}2.17 Es sei $B$ ein l-Block-Kryptosystem. (Man denke an AES.) Wir nehmen (realistisch) an, dass $t$ (etwa $t=6$) Klartext-Chiffretext-Paare $(x_1,y_1),...,(x_t,y_t)$ in $B$ den Schlüssel $k$ der Länge $s=l$ eindeutig bestimmen, für mindestens die Hälfte der Schlüssel (*). Der l-Unterscheider $U_{brute-force}$ wertet die Funktion F an $t+1$ Stellen $x_1,...,x_t,x$ aus, mit Ergebnissen $y_1,...,y_t,y$. Er probiert alle $2^l$ Schlüssel $k$, um einen zu finden, der $e(x_1,k)=y_1 ,...,e(x_t,k) =y_t$ erfüllt. Wenn kein solches $k$ gefunden wird, gibt $U$ den Wert $0$ aus. Sonst wird getestet, ob $e(x,k)=y$ ist. Falls ja, wird $1$ ausgegeben, sonst $0$. Das Verhalten lässt sich so beschreiben: In der ,,Realwelt'', wenn $F=e(.,k)$ ist für einen zufälligen Schlüssel $k$, dann findet $U$ dieses $k$ mit Wahrscheinlichkeit größer als $\frac{1}{2}$ (wegen (*)). Dann ist $e(x,k) =F(x)$ nach Wahl von $F$ und $y=F(x)$, weil $y$ so bestimmt wurde. Also ist $e(x,k) =y$, also gibt $U$ den Wert 1 aus. In der ,,Idealwelt'' wird entweder kein passendes $k$ gefunden, oder wenn doch, dann ist die Wahrscheinlichkeit, dass $e(x,k) =y$ ist, wo $y$ einzufälliger Wert in $\{0,1\}^l-\{y_1,...,y_t\}$ ist, durch $1/(2^l-t)$ beschränkt. Damit ist $adv(U,B) = suc(U,B)-fail(U)\geq \frac{1}{2}-\frac{1}{2^l-t}\approx\frac{1}{2}$. Die Laufzeit des Aufrufs von $U$ ist beschränkt durch $O(|K|) =O(2^l)$. Daher ist $B$ nicht $(7, O(2^l),\frac{1}{2})$-sicher. Das ist natürlich nicht sehr schlimm, weil die Rechenzeit von $U$ unrealistisch hoch ist. Schlussbemerkung: Gesucht wäre nun natürlich ein l-Block-Kryptosystem, das $(q,t,\epsilon)$-sicher ist, wobei $q$ und $t$ einigermaßen groß sind und $\epsilon$ möglichst klein ist. Es gibt unter bestimmten Annahmen (,,Existenz von Einwegfunktionen'') theoretisch konstruierbare Systeme, die für große $l$ einigermaßen effiziente (,,polynomiell in l'') Verschlüsselung und Entschlüsselung erlauben und im definierten Sinn für Angreifer mit (im Bezug zu $l$) nicht zu großen Ressourcen (,,polynomiell in l'') $\epsilon$-sicher sind, für recht kleine $\epsilon$ (der Wert $1/\epsilon$ darf polynomiell groß sein). Diese Systeme sind aber praktisch nicht verwendbar. Von praktisch relevanten Systemen wie AES weiß man nicht, für welche Werte sie sicher sind. \section{Uneingeschränkte symmetrische Verschlüsselung} Szenarium 3: Alice möchte Bob mehrere Klartexte beliebiger Länge schicken. Sie verwendet dafür immer denselben Schlüssel. Eva hört die Chiffretexte mit und kann sich einige wenige Klartexte mit dem verwendeten Schlüssel verschlüsseln lassen. Erweiterungen im Vergleich zu vorher: \begin{enumerate*} \item Beliebig lange Texte sind erlaubt. \item Mehrfaches Senden desselben Textes ist möglich; Eva sollte dies aber nicht erkennen. \end{enumerate*} Wir müssen die bisher benutzten Konzepte anpassen, um auch das mehrfache Senden derselben Nachricht zu erfassen. Ein grundlegender Ansatz, um mit identischen Botschaften umzugehen, ist Folgendes: Alices Verschlüsselungsalgorithmus ist randomisiert, liefert also zufallsabhängig unterschiedliche Chiffretexte für ein und denselben Klartext. Allerdings ist normalerweise die Anzahl der Zufallsexperimente fest und nicht von der Klartextlänge abhängig, sodass wir wie vorher davon ausgehen können, dass nur ein Experiment am Anfang ausgeführt wird. Auch der Sicherheitsbegriff und die Rechenzeitbeschränkungen müssen verändert werden. Klartexte und Chiffretexte sind nun endliche Folgen von Bitvektoren (,,Blöcken'') der festen Länge $l$. Die Menge aller dieser Folgen bezeichnen wir mit $(\{0,1\}^l)^*$ oder kürzer mit $\{0,1\}^{l*}$. Es gibt also unendlich viele Klartexte und Chiffretexte. Die Menge der Schlüssel heißt $K$. Der Verschlüsselungsalgorithmus $E$ ist randomisiert und transformiert einen Klartext $x$ und einen Schlüssel $k$ in einen Chiffretext. Der Entschlüsselungsalgorithmus $D$ ist deterministisch und transformiert einen Chiffretext $y$ und einen Schlüssel $k$ in einen Klartext. Sicher muss man den Algorithmen eine Rechenzeit zugestehen, die von der Länge der zu verarbeitenden Texte abhängt. Als effizient werden Algorithmen angesehen, die eine polynomielle Rechenzeit haben. Es muss eine verallgemeinerte Dechiffrierbedingung gelten, die die Randomisierung der Verschlüsselung berücksichtigt. \textbf{Definition} 3.1 Ein symmetrisches $l$-Kryptoschema ist ein Tupel $S= (K,E,D)$, wobei \begin{itemize*} \item $K\subseteq\{0,1\}^s$ eine endliche Menge ist (für ein $s\in\mathbb{N}$), \item $E(x:\{0,1\}^{l*},k:K) :\{0,1\}^{l*}$ ein randomisierter Algorithmus und \item $D(y:\{0,1\}^{l*},k:K) :\{0,1\}^{l*}$ ein deterministischer Algorithmus sind, so dass gilt: \item Die Laufzeiten von $E$ und $D$ sind polynomiell beschränkt in der Länge von $x$ bzw. $y$. \item Für jedes $x\in\{0,1\}^{l*},k\in K$ und jedes $m\in M_1\times...\times M_r$ (die Ausgänge der flip-Anweisungen in $E$) gilt: $D(E^m(x,k),k)=x$ (Dechiffrierbedingung). \end{itemize*} Die Elemente von \begin{itemize*} \item $K$ heißen ,,Schlüssel'' \item $\{0,1\}^{l*}$ heißen ,,Klartexte'' bzw. ,,Chiffretexte'', je nachdem, welche Rolle sie gerade spielen. \end{itemize*} $E$ ist der Chiffrieralgorithmus, $D$ der Dechiffrieralgorithmus. Bemerkungen: \begin{itemize*} \item Zentral: Die Nachrichtenlänge ist unbestimmt. \item Wir werden immer davon ausgehen, dass der Schlüssel $k$ uniform zufällig aus $K$ gewählt wurde und beiden Parteien bekannt ist. Die Angreiferin Eva kennt $k$ natürlich nicht. \item Etwas allgemeiner ist es, wenn man den Schlüssel nicht uniform zufällig aus einer Menge wählt, sondern von einem randomisierten Schlüsselerzeugungsalgorithmus $G(s:integer):\{0,1\}^*$ generieren lässt. Konzeptuell besteht zwischen den beiden Situationen aber kein großer Unterschied. \item Jeder Klar-und jeder Chiffretext ist ein Bitvektor der Länge $l*h$ für ein $h\in\mathbb{N}$. (Um auf ein Vielfaches der Blocklänge zu kommen, muss man die Texte notfalls mit Nullen auffüllen.) \item Um einen Klartext $x$ zu verschicken, wird der Algorithmus $E$ mit einem neuen, uniform zufällig gewählten Element $m$ abgearbeitet und es wird $E^m(x,k)$ als Chiffretext verschickt. Insbesondere entsteht bei wiederholter Verschlüsselung eines Textes $x$ (mit sehr großer Wahrscheinlichkeit) jedes mal ein anderer Chiffretext. \item In der Literatur finden sich auch Kryptoschemen, bei denen auch die Dechiffrierung randomisiert ist. Wir betrachten dies hier nicht. \end{itemize*} Der Standardansatz zur Konstruktion eines Kryptoschemas besteht darin, von einer Block-chiffre wie in Kapitel 2 auszugehen und sie zu einem Kryptoschema auszubauen. Dies wird im Folgenden beschrieben. \subsection{Betriebsarten} Symmetrische Kryptoschemen erhält man z.B. aus Blockchiffren. Durch einfache Regeln wird erklärt, wie ein Klartext, der aus einer Folge von Blöcken besteht, zu chiffrieren ist. Für alle folgenden Konstruktionen sei $B=(\{0,1\}^l,K_B,\{0,1\}^l,e_B,d_B)$ ein l-Block-Kryptosystem für Blöcke einer Länge $l$. (Man darf sich hier zum Beispiel AES mit $l=128$ vorstellen, oder eine Variante von DES.) \subsubsection{ECB-Betriebsart ( ,,Electronic Code Book mode'' )} Dies ist die nächstliegende Methode. Ein Schlüssel ist ein Schlüssel $k$ von $B$. Man verschlüsselt einfach die einzelnen Blöcke von $x$ mit $B$, jedes mal mit demselben Schlüssel $k$. \textbf{Definition}: Das zu $B$ gehörende $l$-ECB-Kryptoschema $S=ECB(B)=(KB,E,D)$ ist gegeben durch die folgenden Algorithmen: \begin{itemize*} \item $E(x:\{0,1\}^{l*},k:K_B) :\{0,1\}^{l*}$ \item zerlege $x$ in Blöcke der Länge $l:x=x_0 x_1 ...x_{m-1}$; \item für $0\geq i < m$ setze $y_i\leftarrow e_B(x_i,k)$; \item gib $y=y_0 ...y_{m-1}$ zurück. \item $D(y:\{0,1\}^{l*},k:K_B) :\{0,1\}^{l*}$ \item zerlege $y$ in Blöcke der Länge $l:y=y_0 y_1 ...y_{m-1}$; \item für $0\geq i < m$ setze $x_i\leftarrow d_B(y_i,k)$; \item gib $x=x_0 ...x_{m-1}$ zurück. \end{itemize*} Die Verschlüsselung verzichtet auf die Option, Randomisierung zu verwenden. (Sie hat den großen Vorteil, parallel ausführbar zu sein.) Es ist klar, dass die Dechiffrierbedingung erfüllt ist. Jedoch hat dieses Kryptoschema ein ziemlich offensichtliches Problem, nämlich, dass ein Block $x\in\{0,1\}^l$ immer gleich verschlüsselt wird, Eva also ganz leicht nicht-triviale Informationen aus dem Chiffretext erhalten kann. Zum Beispiel kann sie sofort sehen, ob der Klartext die Form $x=x_1 x_1$, mit $x_1\in\{0,1\}^l$, hat oder nicht. Das Problem wird augenfällig zum Beispiel bei der Verschlüsselung von Bildern. Ein Bild ist dabei einrechteckiges Schema (eine Matrix) von ,,Pixeln'', denen jeweils ein Farbcode (z.B. 1 Byte) zugeordnet ist. Man könnte dabei die Pixel in Gruppen (quadratische Blöcke oder Zeilensegmente) unterteilen. Das Farbmuster jeder solchen Gruppe liefert einen Klartextblock. Wenn viele Bildteile identisch aussehen, etwa gleich konstant gefärbt sind, ergibt sich jeweils derselbe Klartext für den entsprechenden Block, und damit auch derselbe Chiffretext. Wenn man den Chiffretext bildlich darstellt, ergibt sich leicht ein grober Eindruck des Originalbildes. Als Beispiel betrachte diese Bilder aus \href{https://de.wikipedia.org/wiki/Electronic_Code_Book_Mode}{Wikipedia}. Fazit: Obwohl er so naheliegend ist, sollte der ECB-Modus niemals benutzt werden! \subsubsection{CBC-Betriebsart( ,,Cipher Block Chaining mode'' )} Diese Betriebsart weicht dem zentralen Problem von ECB aus, indem man die Blöcke in Runden $i=0, 1 ,...,m-1$ nacheinander verschlüsselt und das Ergebnis einer Runde zur Modifikation des Klartextblocks der nächsten Runde benutzt. Konkret: Es wird nicht $x_i$ mit $B$ verschlüsselt, sondern $x_i\oplus_l y_{i-1}$ (bitweises XOR). Man benötigt dann einen Anfangsvektor $y_{-1}$ für die erste Runde. Dieser ist Teil des Schlüssels des Kryptoschemas (nicht von B), ein Schlüssel des Schemas ist also ein Paar $(k,v)$ mit $k\in K_B$ und $v\in\{0,1\}^l$. \textbf{Definition}: Das zu $B$ gehörende $l$-CBC-Kryptoschema $S=CBC(B)=(KB\times\{0,1\}^l,E,D)$ ist durch die folgenden Algorithmen gegeben: \begin{itemize*} \item $E(x:\{0,1\}^{l*},(k,v) :KB\times\{0,1\}^l) :\{0,1\}^{l*}$ \item zerlege $x$ in Blöcke der Länge $l:x=x_0 x_1 ...x_{m-1}$; \item $y_{-1} \leftarrow v$; \item für $i= 0,...,m-1$ nacheinander: $y_i\leftarrow e_B(x_i\oplus_l y_{i-1},k)$; \item gib $y=y_0 ...y_{m-1}$ zurück. \item $E(x:\{0,1\}^{l*},(k,v) :K_B\times\{0,1\}^l) :\{0,1\}^{l*}$ \item zerlege $y$ in Blöcke der Länge $l:y=y_0 y_1 ...y_{m-1}$ \item $y_{-1} \leftarrow v$; \item für $i=0,...,m-1$ nacheinander: $x_i\leftarrow d_B(y_i,k)\oplus_l y_{i-1}$; \item gib $x=x_0 ...x_{m-1}$ zurück. \end{itemize*} Der Vektor $v$ wird Initialisierungsvektor genannt. Man versteht recht gut, was beim Chiffrieren passiert, wenn man sich das Bild auf Seite 104 im Buch von Küsters/Wilke ansieht. Beim Dechiffrieren geht man den umgekehrten Weg: Entschlüssele einen Block $y_i$ mittels B, dann addiere $y_{i-1}$, um den Klartextblock $x_i$ zu erhalten. Es ist klar, dass die Dechiffrierbedingung erfüllt ist. Interessant ist die folgende Eigenschaft der Entschlüsselung im CBC-Modus: Wenn bei der Übertragung des Chiffretextes ein einzelner Block $y_i$ durch einen Fehler zu $y_i'$ verfälscht wird, dann ist die Entschlüsselung ab Block $y_{i+2}$ trotzdem wieder korrekt. In diesem Kryptoschema ist der zentrale Nachteil der ECB-Betriebsart verschwunden: Identische Klartextblöcke führen nun praktisch immer zu verschiedenen Chiffretextblöcken. Die Verschlüsselung von $x=x_1 x_1$ mit $x_1\in\{0,1\}^l$ liefert i.a. keinen Chiffretext der Form $y=y_1 y_1$. Die oben erwähnte Wikipedia-Seite zeigt auch, dass bei der Verschlüsselung des Bildes mit CBC keine offensichtlichen Probleme mehr auftauchen. Ein Problem bleibt aber bestehen: Wird zweimal der Klartext $x$ verschlüsselt, so geschieht dies immer durch denselben Chiffretext $y=E(x,(k,v))$. Dies ist eine Folge der Eigenschaft von CBC, deterministisch zu sein. Auch CBC wird man in der Praxis daher nicht benutzen. \subsubsection{R-CBC-Betriebsart( ,,Randomized CBC mode'' )} Um das Problem der identischen Verschlüsselung identischer Klartexte zu beseitigen, muss in die Verschlüsselung eine Zufalls komponente eingebaut werden. Beispielsweise kann man dazu CBC leicht modifizieren. Der Initialisierungsvektor $y_{-1}=v\in\{0,1\}^l$ ist nicht mehr Teil des Schlüssels, sondern wird vom Verschlüsselungsalgorithmus einfach zufällig gewählt, und zwar für jeden Klartext immer aufs Neue. Damit der Empfänger entschlüsseln kann, benötigt er $v$. Daher wird $y_{-1}$ als Zusatzkomponente dem Chiffretext vorangestellt. Damit ist der Chiffretext um einen Block länger als der Klartext, und Eva kennt auch $v=y_{-1}$. \textbf{Definition}: Das zu $B$ gehörende l-R-CBC-Kryptoschema $S=R-CBC(B) = (K_B,E,D)$ ist gegeben durch die folgenden Algorithmen: \begin{itemize*} \item $E(x:\{0,1\}^{l*},k:K_B) :\{0,1\}^{l*}$; \item zerlege $x$ in $m$ Blöcke der Länge $l:x=x_0 x_1 ...x_{m-1}$ \item setze $y_{-1}= flip(\{0,1\}^l)$; \item für $i=0,...,m-1$ nacheinander: $y_i\leftarrow e_B(x_i\oplus_l y_{i-1} ,k)$; \item gib $y=y_{-1} y_0 ...y_{m-1}$ zurück. //Länge: $m+1$ Blöcke \item $D(y:\{0,1\}^{l*},k:K_B) :\{0,1\}^{l*}$; \item zerlege $y$ in $m+1$ Blöcke der Länge $l:y=y_{-1} y_0 y_1 ...y_{m-1}$ \item für $i=0,...,m-1$ nacheinander: $x_i\leftarrow d_B(y_i,k)\oplus_l y_{i-1}$; \item gib $x=x_0 ...x_{m-1}$ zurück. //Länge: m Blöcke \end{itemize*} Es gibt zwei Unterschiede zu CBC: \begin{enumerate*} \item Für jede Verschlüsselung eines Klartextes wird ein neuer zufälliger Initialisierungsvektor verwendet. Dadurch wird ein Klartext $x$ bei mehrfachem Auftreten mit hoher Wahrscheinlichkeit immer verschieden verschlüsselt. \item Der Initialisierungsvektor ist nicht Teil des geheimen Schlüssels, sondern ist dem Angreifer bekannt, da er Teil des Chiffretextes ist. (Intuitiv würde man vielleicht sagen, dass dies ,,die Sicherheit verringert'') \end{enumerate*} Tatsächlich und etwas unerwartet kann man nach einer sorgfältigen Formulierung eines Sicherheitsbegriffs für Kryptoschemen beweisen, dass die Betriebsart R-CBC zu ,,sicheren'' Verfahren führt, wenn die zugrundeliegende Blockchiffre ,,sicher'' ist. (Der Beweis ist aufwendig.) Warnung, als Beispiel für harmlos erscheinende Modifikationen, die Kryptoschemen unsicher machen: \begin{enumerate*} \item Man könnte meinen, dass es genügt, bei jeder Verschlüsselung einen neuen Initialisierungsvektor zu benutzen, also zum Beispiel nacheinander $v,v+1,v+2,...$. Dies führt jedoch zu einem unsicheren Kryptoschema. \item Um Kommunikation zu sparen, könnte man auf die Idee kommen, dass Alice und Bob sich von einer Kommunikationsrunde zur nächsten den letzten Chiffretextblock merken und ihn bei der nächsten Runde als Initialisierungsvektor benutzen. Dieses Verfahren heißt ,,chained CBC'' und wurde in SSL3.0 und TLS1.0 verwendet. Es stellte sich heraus, dass dieses Verfahren mit einem Angriff mit gewähltem Klartext erfolgreich attackiert werden kann! \end{enumerate*} \subsubsection{OFB-Betriebsart( ,,Output Feed Back mode'' )} Wir kommen nun zu zwei Betriebsarten, die einen ganz anderen Ansatz für die Verschlüsselung der einzelnen Blöcke von $x$ verfolgen. Es wird dazu nämlich nicht $B$ mit Schlüssel $k$ benutzt, sondern der Mechanismus des Vernam-Systems (One-Time-Pads, siehe Beispiel 1.6) :$y_i=x_i\oplus_l k_i$, wobei $k_i\in\{0,1\}^l$ ein ,,Rundenschlüssel'' für Block $x_i$ ist. Das Kryptosystem $B$ wird nur dafür benutzt, diese Rundenschlüssel herzustellen, die bei Verschlüsselung und bei Entschlüsselung identisch sind. Die Dechiffrierbedingung folgt dann daraus, dass das Vernam-System korrekt dechiffriert. Der Ansatz führt dazu, dass die Entschlüsselungsfunktiond $B$ des Block-Kryptosystems gar nicht benötigt wird. Zuerst betrachten wir die Betriebsart ,,Output Feedback''. Dabei wird ein zufälliger Startvektor $v$ aus $\{0,1\}^l$ gewählt. Man setzt $k_{-1}=v$, und konstruiert die Rundenschlüssel $k_0,...,k_{m-1}$ dadurch, dass man iteriert den letzten Rundenschlüssel durch die Verschlüsselungsfunktion von $B$ schickt: $k_i=e_B(k_{i-1}, k)$, für $i=0,1,...,m-1$. (Der Name ''Output Feedback''rührt daher, dass das Ergebnis einer Verschlüsselung durch $e_B$ wieder als Input des nächsten Aufrufs von $e_B$ benutzt wird.) Der Empfänger benötigt $v$, um seinerseits die Rundenschlüssel zu berechnen; daher wird $v$ als $y_{-1}$ dem Chiffretext vorangestellt, wie beim R-CBC-Modus. \textbf{Definition}: Das zu $B$ gehörende l-OFB-Kryptoschema $S=(K_B,E,D) =OFB(B) =(K_B,E,D)$ ist gegeben durch die folgenden Algorithmen: \begin{itemize*} \item $E(x:\{0,1\}^{l*},k:K_B) :\{0,1\}^{l*}$; \item zerlege $x$ in $m$ Blöcke der Länge $l:x=x_0 x_1 ...x_{m-1}$; \item $k_{-1} \leftarrow y_{-1} \leftarrow flip(\{0,1\}^l)$; \item für $i=0,...,m-1$ nacheinander: $k_i\leftarrow e_B(k_{i-1},k)$ und $y_i\leftarrow x_i\oplus_l k_i$; \item gib $y=y_{-1} y_0 ...y_{m-1}$ zurück. \item $D(y:\{0,1\}^{l*},k:K_B) :\{0,1\}^{l*}$; \item zerlege $y$ in $m+1$ Blöcke der Länge $l:y=y_{-1} y_0 y_1 ...y_{m-1}$; \item $k_{-1} \leftarrow y_{-1}$; \item für $i=0,...,m-1$ nacheinander: $k_i\leftarrow e_B(k_{i-1} ,k)$ und $x_i\leftarrow y_i\oplus k_i$; \item gib $x=x_0 ...x_{m-1}$ zurück. \end{itemize*} Dieses Verfahren hat einen interessanten Vorteil. Oft werden die Blöcke des Chiffretextes beim Empfänger nacheinander eintreffen. Die Hauptarbeit, nämlich die iterierte Verschlüsselung mit $e_B$ zur Ermittlung der Rundenschlüssel $k_i$, kann unabhängig von der Verfügbarkeit der Klartextblöcke erfolgen, sobald $y_{-1}$ eingetroffen ist. Man kann beweisen, dass die Betriebsarten R-CBC und OFB ,,sicher'' sind, wenn die zugrundeliegende Blockchiffre ,,sicher'' ist. Dazu weiter unten mehr. \subsubsection{R-CTR-Betriebsart (,,Randomized CounTeR mode'' )} Dies ist die zweite Betriebsart, bei der das Kryptosystem $B$ nur zur Herstellung von m ,,Rundenschlüsseln'' benutzt wird, mit denen dann die Blöcke per $\oplus_l$ verschlüsselt werden. Anstatt iteriert zu verschlüsseln, was bei OFB eine sequentielle Verarbeitung erzwingt, werden hier die mit $B$ zu verschlüsselnden Strings anders bestimmt. Man fasst $\{0,1\}^l$ als äquivalent zur Zahlenmenge $\{0,1,...,2^{l-1}\}$ auf, interpretiert einen $l$-Bit-String also als Block oder als Zahl, wie es passt. In dieser Menge wählt man eine Zufallszahl $r$. Man ,,zählt'' von $r$ ausgehend nach oben und berechnet die Rundenschlüssel $k_0,...,k_{m-1}$ durch Verschlüsseln von $r,r+1,...,r+m-1$ (modulo $2^l$ gerechnet) mittelse $B(.,k)$. Rundenschlüssel $k_i$ ist also $e_B((r+i) mod\ 2^l,k)$, und Chiffretextblock $y_i$ ist $k_i\oplus_l x_i$. Interessant ist, dass hier die Berechnung der Rundenschlüssel und die Ver- bzw. Entschlüsselung der Blöcke parallel erfolgen kann, also sehr schnell, falls mehrere Prozessoren zur Verfügung stehen. \textbf{Definition}: Das zu $B$ gehörende l-R-CTR-Kryptoschema $S=R-CTR(B) = (K_B,E,D)$ ist gegeben durch die folgenden Algorithmen: \begin{itemize*} \item $E(x:\{0,1\}^{l*},k:K_B) :\{0,1\}^{l*}$; \item zerlege $x$ in $m$ Blöcke der Länge $l:x=x_0 x_1 ...x_{m-1}$; \item $r\leftarrow flip(\{0,..., 2^l-1\})$; \item für $0\geq i < m:y_i\leftarrow e_B((r+i) mod\ 2^l,k)\oplus_l x_i$; \item gib $y=r y_0 ...y_{m-1}$ zurück. \item $D(y: (\{0,1\}^l)+,k:K_B) :\{0,1\}^{l*}$; \item zerlege $y$ in $m+1$ Blöcke der Länge $l:y=y_{-1} y_0 y_1 ...y_{m-1}$; \item $r\leftarrow y_{-1}$; \item für $0\geq i < m:x_i\leftarrow e_B((r+i) mod\ 2^l,k)\oplus_l y_i$; \item gib $x=x_0 ...x_{m-1}$ zurück. \end{itemize*} Es ist offensichtlich, dass die Dechiffrierbedingung erfüllt ist. Bemerkungen: \begin{itemize*} \item Wie bei R-CBC und OFB wird hier ein zufälliger Initialisierungswert $r$ verwendet, der als Teil des Chiffretextes dem Angreifer bekannt ist. \item Wie bei OFB wird die Entschlüsselungsfunktion $d_B$ gar nicht verwendet, man kann also anstelle der Verschlüsselungsfunktion $e_B$ eine beliebige Funktion $e_B:\{0,1\}^l\times\{0,1\}^l\rightarrow\{0,1\}^l$ benutzen, bei der die ,,Chiffren'' $e_B(.,k)$ nicht einmal injektiv sein müssen. \item Man kann dieses Kryptoschema auch wie folgt verstehen: Zu einem gegebenen Klartext $x\in\{0,1\}^{lm}$ wird aus einem zufälligen Initialwert $r$ ein langer Bitstring $k'=E_B(r,k) E_B((r+1) mod\ 2^l,k)... E_B((r+m-1) mod\ 2^l,k)$ berechnet und der Klartext $x$ dann mittels Vernamsystem und diesem Schlüssel verschlüsselt. Der Empfänger erhält $r$ und den Chiffretext, kann also ebenfalls $k'$ b erechnen und damit entschlüsseln. Ist $B$ ein sicheres Block-Kryptosystem, so kann ein Angreifer aus $r$ den Vernam-Schlüssel $k'$ nicht so einfach berechnen, da er $k$ nicht kennt. Die R-CTR-Betriebsart liefert also intuitiv einen hohen Grad an Sicherheit. \end{itemize*} \subsection{Sicherheit von symmetrischen Kryptoschemen} Wir werden hier ein Sicherheitsmodell definieren, das es gestattet, Aussagen wie die folgende zu formulieren (und zu beweisen): Wenn B ein ,,sicheres'' l-Block-Kryptosystem ist (bzgl. einer Reihe von Parametern), und das Kryptoschema $S$ wird aus $B$ konstruiert, indem man einen geeigneten Betriebsmodus verwendet, dann ist $S$ ebenfalls ,,sicher'' (bzgl. einer variierten Reihe von Parametern). Ziel ist dabei, Betriebsmodi zu identifizieren, die keine unnötigen neuen Unsicherheitskomponenten ins Spiel bringen, die nicht im Block-KS $B$ schon vorhanden waren. Wir beschränken uns hier auf den Fall, wo Eva begrenzte Ressourcen (Zeit, Orakelaufrufe) hat. Damit müssen wir uns bei Überlegungen zu Kryptoschemen auf das Verhalten auf Klartexten begrenzter Länge und auf feste Rechenzeiten beschränken. Nach dem Kerckhoffs-Prinzip nehmen wir an, dass Eva das Kryptoschema kennt, also zum Beispiel das verwendete Block-Kryptosystem und den Betriebsmodus. Sie kann sich einige Klartexte verschlüsseln lassen (,,known-plaintext attack'') und sieht einen Chiffretext $y$. Ihr Ziel ist, aus $y$ Information über den zugrundeliegenden Klartext $x$ zu gewinnen. Wir können nicht verhindern, dass Eva aus der Länge des Chiffretextes $y$ auf die Länge von $x$ schließt. (Bei allen Betriebsmodi, die wir gesehen haben, ergibt sich die Länge von $x$ direkt aus der Länge von $y$). Abgesehen hiervon soll sie mit hoher Wahrscheinlichkeit ,,keine signifikante Information'' über den Klartext erhalten können. Wir skizzieren zunächst eine Idee für ein Sicherheitsmodell, das die Fähigkeit, in so einer Situation ,,Information zu ermitteln'', formalisiert. Eva behauptet, sie könne ,,aus $y$ Information über $x$ ermitteln, die über die Länge von $x$ hinausgeht''. Um das zu überprüfen, stellt ihr ein ,,Herausforderer'' Charlie folgende Aufgabe: Eva darf sich zunächst eine Reihe von Klartexten ihrer Wahl verschlüsseln lassen. Dann wählt sie selbst zwei verschiedene, gleichlange Klartexte $z_0$ und $z_1$. Charlie verschlüsselt einen von diesen; der Chiffretext ist $y$. Eva bekommt $y$. Sie soll herausfinden, ob $y$ von $z_0$ oder von $z_1$ kommt. Für diese Entscheidung darf sie sich weitere Klartexte verschlüsseln lassen und weiter rechnen. Wir betrachten ein Kryptoschema als unsicher, wenn Eva eine signifikant von ,,purem Raten'' abweichende Erfolgswahrscheinlichkeit hat, sie also mit guten Chancen unterscheiden kann, ob $z_0$ oder $z_1$ zu $y$ verschlüsselt wurde. Wie in Abschnitt 2.4 formulieren wir den Vorgang wieder als Spiel. Gegeben ist also $S=(K,E,D)$. Akteure sind Eva, hier ,,Angreifer'' (engl.: adversary) genannt, und Charlie (,,Herausforderer'' ,engl.: challenger). Die Parameter, mit denen wir die Erfolgschancen von Eva unter Ressourcenbeschränkungen messen, sind der ,,Vorteil'' in Analogie zu Definition 2.13, die Rechenzeit (inklusive Speicherplatz, wie vorher), Anzahl der Orakelaufrufe und Anzahl der bei der Verschlüsselung bearbeiteten Blöcke. \begin{itemize*} \item Charlie wählt zufällig einen Schlüssel $k$ aus $K$ und legt damit die Chiffre $H=E(.,k)$ fest, die Klartexte aus $\{0,1\}^{l*}$ in Chiffretexte aus $\{0,1\}^{l*}$ transformiert. \item Eva wählt einige Klartexte und lässt sie sich von Charlie mit $H$ verschlüsseln. \item Eva wählt zwei Klartexte $z_0$ und $z_1$ gleicher Länge und gibt sie an Charlie. \item Verdeckt vor Eva: Charlie wirft eine Münze, um zufällig einen der beiden Klartexte zu wählen. Er verschlüsselt ihn mit $H$, das Ergebnis ist $y$. Charlie gibt $y$ an Eva. \item Eva kann sich weitere Klartexte verschlüsseln lassen und (mit beschränkten Ressourcen) rechnen und muss schließlich sagen (raten?), ob Charlie $z_0$ oder $z_1$ zu $y$ verschlüsselt hat. \end{itemize*} Wenn die Wahrscheinlichkeit, dass Eva richtig antwortet, weit von zufälligem Raten abweicht, wollen wir das Kryptoschema als unsicher ansehen. Man beachte: Unter den vorher oder nachher verschlüsselten Klartexten können auch $z_0$ und $z_1$ sein. Ein deterministisches Kryptoschema, also eines, das zu gegebenem Schlüssel $k$ einen Klartext stets gleich verschlüsselt, ist damit sofort disqualifiziert. Wenn aber bei der Verschlüsselung Randomisierung im Spiel ist, liefern wiederholte Verschlüsselungsanforderungen mit Klartexten $z_0$ und $z_1$ (wahrscheinlich) lauter unterschiedliche Antworten, so dass dieser direkte Weg zur Ermittlung des verschlüsselten Klartextes nicht funktioniert. Wir beschreiben den Part von Eva in diesem Spiel als Algorithmenpaar. Der erste Algorithmus $AF$ (der ,,Finder'', ,,find'' ) ist für das Erzeugen von $z_0$ und $z_1$ zuständig. Als Argument erhält dieser Teil eine Chiffre $H$, die er im Sinne eines Orakels benutzen kann. Außerdem werden Aufzeichnungen über die angeforderten Verschlüsselungen und ihre Ergebnisse gemacht. Diese Aufzeichnungen sind als Element $v$ einer endlichen Menge $V$ kodiert. Der zweite Algorithmus $AG$ (der ,,Rater'' , ,,guess'' ) ist dafür zuständig, herauszufinden, ob $z_0$ oder $z_1$ verschlüsselt wurde. Dieser Algorithmus bekommt $H$ als Orakel, die Aufzeichnungen $v$ von $AF$ und den Chiffretext $y$ als Input. \textbf{Definition} 3.2 Ein l-Angreifer $A$ ist ein Paar von randomisierten Algorithmen \begin{itemize*} \item $AF(H(\{0,1\}^{l*}) :\{0,1\}^{l*}) : (\{0,1\}^l\times\{0,1\}^l)^+\times V$ \item $AG(v:V,H(\{0,1\}^{l*}) :\{0,1\}^{l*},y:\{0,1\}^{l*}) :\{0,1\}$ \end{itemize*} Hierbei ist $H$ ein randomisierter Algorithmus (und nicht als Funktion zu verstehen). Der ,,Finder'' AF bekommt also eine Chiffre $H=E(.,k)$ für einen zufälligen Schlüssel $k$ gegeben. (Er darf diese Chiffre nur zum Verschlüsseln benutzen; $k$ kennt er nicht.) Daraus berechnet er zwei verschiedene Klartexte $(z_0,z_1)$ gleicher Länge und ,,Notizen'' $v\in V$. Das Ausgabeformat $(\{0,1\}^l\times\{0,1\}^l)^+$ sagt, dass eine Folge $((z_0^{(0)},z^{(0)}_1),(z_0^{(1)},z_1^{(1)}),...,(z_0^{(m-1)},z_1^{(m-1)}))$ von Blockpaaren ausgegeben werden soll, die wir dann als Paar $(z_0 ,z_1) = ((z^{(0)}_0 ,z_0^{(1)},...,z_0^{(m-1)}),(z_1^{(0)},z^{(1)}_1 ,...,z_1^{(m-1)}))$ von zwei Folgen gleicher Länge lesen. Danach wird zufällig $z_0$ oder $z_1$ zu $y$ verschlüsselt. Im zweiten Schritt verwendet der ,,Rater'' $AG$ die Notizen $v$, die Chiffre $H=E(.,k)$ und die ,,Probe'' $y$, um zu bestimmen, ob $z_0$ oder $z_1$ verschlüsselt wurde. \textbf{Definition} 3.3 Sei $S=(K,E,D)$ ein symmetrisches Kryptoschema, und sei $A=(AF,AG)$ ein l-Angreifer. Das zugehörige Experiment (oder Spiel) ist der folgende Algorithmus $G^S_A:\{0,1\}:$ \begin{enumerate*} \item $k\leftarrow flip(K)$, $H\leftarrow E(.,k)$ (In diesem Schritt wählt Charlie zufällig eine Chiffre des Kryptoschemas $S$.) \item $(z_0, z_1 ,v)\leftarrow AF(H)$ (In dieser Phase berechnet der Finder ein Paar von Klartexten gleicher Länge, von denen er annimmt,ihre Chiffretexte unterscheiden zu können.) \item $b\leftarrow flip(\{0,1\})$ und $y\leftarrow E(z_b,k)$ (In dieser Phase wählt Charlie zufällig einen der beiden Klartexte und verschlüsselt ihn zu $y$.) \item $b'\leftarrow AG(v,H,y)$ (In dieser Phase versucht der Rater herauszubekommen, ob $z_0$ oder $z_1$ verschlüsselt wurde.) \item falls $b=b'$, so gib $1$ zurück, sonst $0$. (Charlies Auswertung: Hat $AG$ recht oder nicht?) \end{enumerate*} Das verkürzte Experiment oder Spiel $S^S_A$ gibt im 5.Schritt einfach $b'$ aus. Dann ist $Pr(G^S_A = 1)$ die Wahrscheinlichkeit dafür, dass der Angreifer $A$ sich für den korrekten Klartext entscheidet. Der Wahrscheinlichkeitsraum entsteht durch die expliziten Zufallsexperimente in Schritt 1. und 3. in Kombination mit den Zufallsexperimenten, die bei der Verwendung von $H$ ausgeführt werden. Man kann jetzt wie in Abschnitt 2.4 (Sicherheit von l-Block-Kryptosystemen) den Vorteil $adv(A,S) = 2(Pr(G^S_A= 1)-\frac{1}{2})$ und die Größen $suc(A,S) = Pr(S^S_A\langle b= 1\rangle = 1)$ (,,Erfolg'') und $fail(A,S) = Pr(S_A^S\langle b= 0\rangle = 1)$ ( ,,Misserfolg'' ) definieren. Allerdings haben die beiden letzten Werte eine etwas andere Semantik. Der Wert $suc(A,S)$ ist die bedingte Wahrscheinlichkeit, dass richtig erkannt wird, dass $z_1$ verschlüsselt wurde, $fail(A,S)$ ist die bedingte Wahrscheinlichkeit, dass nicht erkannt wird, dass $z_0$ verschlüsselt wurde. Lemma 2.14 gilt wörtlich. Das heißt: $$adv(A,S) = suc(A,S)-fail(A,S)$$. Wenn ein Angreifer $A$ mit ,,nicht zu großem Rechenaufwand'' einen Vorteil erzielen kann, der deutlich über $0$ liegt, wird man das Kryptoschema als unsicher einstufen. \textbf{Beispiel} 3.4 Ziel ist es, die ECB-Betriebsart anzugreifen, d.h. sei $S=ECB(B)$ für ein l-Block-Kryptosystem $B$. Wir wollen zeigen, dass es einen l-Angreifer $A$ mit $Pr(G^S_A= 1) = 1$, also $adv(A,S) = 1$, gibt. Dieser ist wie folgt aufgebaut. \begin{itemize*} \item l-Angreifer $A$ mit $V=\{1\}$ ($V=\{1\}$ bedeutet, dass stets $v=1$ gilt, dass die Aufzeichnung $v$ also keinerlei Information übermittelt.) \item $AF(H)$ arbeitet wie folgt: $z_0\leftarrow 0^{2l}; z_1\leftarrow 0^l 1^l;$ Ausgabe: $(z_0,z_1 ,1)$ \item $AG(v,H,y)$ tut Folgendes: falls $y=y_1y_1$ für ein $y_1\in\{0,1\}^l$, gib $0$ aus, sonst $1$. \end{itemize*} Im Ablauf des Spiels $G^S_A$ wird der Rater $AG$ mit $y=E(0^{2l},k)=e_B(0^l,k)e_B(0^l,k)$ oder mit $y=E(0^l 1^l,k)=e_B(0^l,k)e_B(1^l,k)$ gestartet. Im ersten Fall ist $y=y_1y_1$ für ein $y_1\in\{0,1\}^l$, im zweiten Fall ist dies nicht so, wegen der Dechiffrierbedingung. Daher gilt $Pr(G^S_A= 1) = 1$, d.h. $adv(A,S) = 1$. Die Ressourcen, die $A$ benötigt, sind sehr klein: Zwei Aufrufe des Verschlüsselungsverfahrens $e_B$ des Block-Kryptosystems. Wir können schließen, dass es einen effizienten Angreifer $A$ gibt, dem das Sicherheitsmodell Vorteil 1 gibt. Damit gilt das Kryptoschema $ECB(B)$ als komplett unsicher. \textbf{Beispiel} 3.5 Ziel ist es, die CBC-Betriebsart anzugreifen, d.h. es sei $S=CBC(B)$ für ein Block-Kryptosystem $B$. Das Problem mit dieser Betriebsart ist, dass ein Klartext bei Wiederholung identisch verschlüsselt wird. Um dies auszunutzen, verwenden wir den folgenden l-Angreifer $A$ mit $V=\{0,1\}^l$, der zwei verschiedene Klartexte benutzt, die nur einen Block enthalten: \begin{itemize*} \item $AF(H)$ arbeitet wie folgt: $z_0\leftarrow 0^l;v\leftarrow H(z_0);z_1\leftarrow 1^l;$ Ausgabe: $(z_0,z_1,v)$ \item ($A$ merkt sich den Chiffretext zu $x=0^l$.) \item $AG(v,H,y)$ tut Folgendes: falls $v=y$, so gib $0$ aus, sonst $1$. \end{itemize*} Im Ablauf des Spiels $G^S_A$ wird der Rater $AG$ mit $E(0^l,k)$ oder mit $E(1^l,k)$ gestartet. Wegen $e_B(0^l,k)\not=e_B(1^l,k)$ (wegen der Dechiffrierbedingung) gilt also $Pr(G^S_A=1)=1$, d.h. $adv(A,S)=1$. Dieses Beispiel lässt sich verallgemeinern: \textbf{Lemma} 3.6 Es gibt einen l-Angreifer $A$, so dass für jedes l-Kryptoschema $S$ mit deterministischer Verschlüsselungsfunktion gilt: $adv(A,S) = 1$. Wir benutzen einfach den in Beispiel 3.5 beschriebenen Angreifer. Damit zeigt sich, dass das beschriebene Spiel in der Lage ist, alle deterministischen Kryptoschemen als unsicher einzustufen (und damit die intuitive Einschätzung zu bestätigen). Nun bringen wir die Ressourcen ins Spiel, die der Angreifer benutzen darf. Komponenten dabei sind die Laufzeit des gesamten Experiments, die Anzahl der durchgeführten H-Verschlüsselungen von Chiffretexten und die Anzahl der dabei bearbeiteten Blöcke. ($S$ kann eine beliebige Struktur haben, muss also nicht notwendigerweise auf einem l-Block-Kryptosystem beruhen. Dennoch sind die Klartexte in Blöcke eingeteilt, und die Gesamtlänge aller betrachteten Blöcke ist eine sinnvolle Maßzahl.) \textbf{Definition} 3.7 Sei $n,q,t,l\in\mathbb{N}$, $A$ ein l-Angreifer, $S$ ein symmetrisches l-Kryptoschema. Dann heißt $A(n,q,t)$-beschränkt, wenn die Laufzeit des Experiments $G^S_A$ durch $t$ beschränkt ist, der Algorithmus $H$ (als Orakel) höchstens $q$ mal aufgerufen wird und bei diesen Aufrufen höchstens $n$ Blöcke verwendet werden. Sei $\epsilon> 0$. Dann heißt $S(n,q,t,\epsilon)$-sicher, wenn für jeden $(n,q,t)$-beschränkten l-Angreifer $A$ gilt $adv(A,S)\geq\epsilon$. Nach obigem Lemma gibt es (kleine) Konstanten $c_1,c_2$ und $c_3$, so dass kein deterministisches l-Kryptoschema $(c_1,c_2,c_3,1-\delta)$-sicher ist, für jedes noch so kleine $\delta > 0$. Wir stellen nun fest, dass man aus sicheren Block-Kryptosystemen mit der R-CTR-Betriebsart sichere Kryptoschemen erhält, wenn man die Parameter richtig wählt, das heißt im Wesentlichen, wenn die Blocklänge genügend groß ist. Diese ,,relative Sicherheit'' kann man folgendermaßen ,,rückwärts'' ausdrücken: Wenn das Kryptoschema $S=R-CTR(B)$ unsicher ist, es also einen Angreifer mit großem Vorteil $adv(A,S)$ gibt, bei beschränkten Ressourcen, dann ist schon $B$ unsicher, das heißt, es gibt einen Unterscheider $U$ für $B$ mit großem Vorteil $adv(U,B)$, bei beschränkten Ressourcen. Technisch wird dies folgendermaßen formuliert, unter Einbeziehung gewisser Fehlerterme und genauer Benennung der Ressourcenschranken. \textbf{Satz} 3.8 Es gibt eine kleine Konstante $c$, so dass für alle $t,n,q,l > 0$, alle l-Block-Kryptosysteme $B$ und alle $(n,q,t)$-beschränkten l-Angreifer $A$ ein $(n,t+c(q\ log(q) +n)*l)$-beschränkter l-Unterscheider $U$ existiert, so dass $adv(A,S)\geq 2 *adv(U,B) + \frac{2 qn+n^2}{2^l}$, wobei $S$ das symmetrische l-Kryptoschema ist, das $B$ in der R-CTR-Betriebsart verwendet. Den Fehlerterm $(2qn+n^2)/2^l$ kann man vernachlässigen, wenn $l$ genügend groß gewählt wird. Die Zahlen $q$ und $n$ entsprechen der Verarbeitung von Blöcken, Werte für $q$ und $n$ von mehr als $1012$ sind also eher unrealistisch. Mit $l=128$ ist $2^l> 3 * 10^{38}$. Damit kann man ohne Weiteres $\frac{2qn+n^2}{2^l} <10^{-14}$ annehmen. Im Wesentlichen besagt der Satz also, dass aus der Existenz eines effizienten l-Angreifers mit einem gewissen Vorteil $a>0$ gegen R-CTR($B$) folgt, dass es einen effizienten l-Unterscheider $U$ mit Vorteil $a/2$ gegen $B$ gibt. Wenn also R-CTR($B$) unsicher ist (nicht $\epsilon$-sicher für relativ großes $\epsilon$), dann muss schon $B$ unsicher gewesen sein (nicht $\epsilon/2$-sicher). Oder noch kürzer: Wenn $B$ ,,sicher'' ist, dann auch R-CTR($B$). Durch die R-CTR-Betriebsart wird keine neue Unsicherheitskomponente ins Spiel gebracht. Mit den folgenden Definitionen lässt sich diese Aussage vielleicht noch griffiger formulieren. \textbf{Definition} 3.9 Die Unsicherheit eines Block-Kryptosystems $B=(X,K,Y,e,d)$ zu Parametern $q,t$ ist $insec(q,t,B) := max\{adv(U,B)|\text{ U ist } (q,t) \text{-beschränkter Unterscheider}\}$. Man beachte: Weil mit $t$ auch die Programmtextlänge beschränkt ist, gibt es nur endlich viele solche Unterscheider. Damit ist das Maximum wohl definiert. Offensichtlich gilt, nach den Definitionen aus Abschnitt 2.4: $B$ ist $(q,t,\epsilon)$-sicher $\Leftrightarrow insec(q,t,B)\geq\epsilon$. Analog definiert man: \textbf{Definition} 3.10 Die Unsicherheit eines Kryptoschemas $S=(K,E,D)$ zu Parametern $n,q,t$ ist $insec(n,q,t,S):=max\{adv(A,S)|A \text{ ist }(n,q,t)\text{-beschränkter Angreifer}\}$. \textbf{Satz} 3.8 liest sich dann wie folgt: Wenn $S$ das symmetrische l-Kryptoschema ist, das $B$ in der R-CTR-Betriebsart verwendet, dann gilt für beliebige $n,t,q: insec(n,q,t,S)\geq 2 * insec(n,t+c(q\ log(q) +n)*l,B) +\frac{2qn+n^2}{2^l}$. $S$ ,,erbt'' also die obere Schranke für die Unsicherheit von $B$, bezüglich $n$ Orakelanfragen und einer vergrößerten Rechenzeit von $t+c(q\ log(q) +n)*l$, verschlechtert nur um einen Faktor $2$ und einen additiven Term $\frac{2qn+n^2}{2^l}$. Die Unsicherheit kommt also nicht durch die Verwendung der Betriebsart R-CTR ins Spiel, sondern steckt gegebenenfalls schon in $B$. Bemerkung: Für die Betriebsarten R-CBC und OFB gelten Aussagen, die zu Satz 3.8 analog sind. Die Beweise sind allerdings noch aufwendiger. Einen vollständigen Beweis von Satz 3.8 findet man in ,,Küsters und Wilke, Moderne Kryptographie'' (S.114, 121), und im Anhang. Im Buch werden auch die folgenden konkreten Parameter diskutiert: $l=128$. Nehmen wir an, die zugelassene Laufzeit $t$ für den Angreifer ist $2^{60} > 10^{18}$ Rechenschritte (das ist so groß, dass es nicht wirklich realisierbar ist), und wir gestatten $q=2^{30} \approx 10^{9}$ Orakelanfragen, wobei die gesamte betroffene Textlänge $n=2^{36}\approx 64*10^9$ Blöcke ist (etwa $2^{40}$ Byte,also ein Terabyte). Wenn die Konstante aus dem Satz etwa $c=10$ ist, erhalten wir: $$insec(2^{36}, 2^{30}, 2^{60},S)\geq 2*insec(2^{36}, 2^{60}+ 10(30*2^{30}+ 2^{36})* 128 ,B) +\frac{2^{66} + 2^{72}}{2^{128}}$$. Man sieht, dass der additive Term $\frac{2^{66} +2^{72}}{2^{128}}$ kleiner als $2^{-55}$ ist, und die für den Unterscheider zugelassene Zeitschranke mit $2^{60} + 10(30* 2^{30}+2^{36})*128 < 2^{61}$ kaum größer ist als die für den Angreifer. Wenn man für $insec(2^{36}, 2^{61} ,B)$ eine Schranke $\geq 2^{-55}$ hätte, wäre $insec(2^{36}, 2^{30}, 2^{60},S)$ auch kleiner als $2^{-54}$. (Solche konkreten Schranken sind allerdings für kein konkretes Block-Kryptosystem bewiesen.) \section{Zahlentheorie und Algorithmen} Zu Aussagen, die mit (*) markiert sind, gibt es Beweise oder Anmerkungen im Anhang A. Beweise von rein zahlentheoretischen Aussagen sind nicht prufungsrelevant. Beweise für Wahrscheinlichkeitsaussagen und Begründungen für Rechenzeiten von Algorithmen dagegen sind prüfungsrelevant. \subsection{Fakten aus der Zahlentheorie und grundlegende Algorithmen} Unsere Zahlenbereiche: \begin{itemize*} \item $\mathbb{N}=\{ 0 , 1 , 2 , 3 ,...\}$, \item $\mathbb{Z}=\{...,- 2 ,- 1 , 0 , 1 , 2 , 3 ,...\}$ \end{itemize*} Wir stellen uns die Zahlen immer als zu einer passenden Basis $b$ dargestellt vor: Binärdarstellung, (Oktaldarstellung,) Dezimaldarstellung, Hexadezimaldarstellung, Darstellung zur Basis 256 (eine Ziffer ist ein Byte) oder $2^{32}$ oder $2^{64}$ (eine Ziffer ist ein 32- bzw. 64-Bit-Wort, passend für die Darstellung in einem Rechner). Die Anzahl der Ziffern in der Darstellung von $a\in\mathbb{N}$ zur Basis $b$ ist $\lceil log_b(a+1)\rceil$. Das ist etwa $\frac{ln\ a}{ln\ b}=\frac{log\ a}{log\ b}$. Verwendete Operationen: Addition, Subtraktion, Multiplikation, Division mit Rest. Wir nehmen an, dass zwei einziffrige Zahlen in Zeit $O(1)$ addiert und subtrahiert werden können (,,von der Hardware''). Addition zweier n-ziffriger Zahlen kostet dann Zeit $O(n)$, Multiplikation einer n-ziffrigen und einer l-ziffrigen Zahl mit der Schulmethode kostet Zeit $O(nl)$. Es gibt schnellere Verfahren: Karatsuba mit $O(n^{1,59})$ für zwei n-ziffrige Zahlen, Schönhage-Strassen (1977) sogar mit $O(n\ log\ n\ log\ log\ n)$. Nach längerer Pause erschienen 2007 und 2008 Verbesserungen. Im März 2019 erschien eine Arbeit, die zeigt, wie man zwei n-Bit-Zahlen in Zeit $O(n\ log\ n)$ multiplizieren kann. Man vermutet, dass das optimal ist. (Nach aktuellem Stand ergeben sich Vorteile gegenüber Karatsuba aber erst für unrealistisch lange Zahlen.) Fakt 4.1 Division mit Rest: Zu $x\in\mathbb{Z}$ und $m\geq 1$ gibt es ein $r$ mit $0\leq r < m$ und ein $q$ mit $x=qm+r$. Die Zahlen $q$ und $r$ sind eindeutig bestimmt. Die Zahl $r$ (,,Rest'') bezeichnen wir mit $x\ mod\ m$. Sie hat die Darstellung $x-qm$, unterscheidet sich also von $x$ um ein Vielfaches von $m$. Der Quotient $q$ wird mit $x\ div\ m$ bezeichnet. Beispiel: $30 = 3*9 + 3, 30\ mod\ 9 = 3, -30 = (-4) *9 + 6, (-30)\ mod\ 9 = 6$. Aufwand für Division mit Rest: Die Division einer n-ziffrigen Zahl durch eine l-ziffrige Zahl mit der Schulmethode kostet Zeit $O(nl)$. Wir sagen, dass eine ganze Zahl $y$ die ganze Zahl $x$ teilt (oder dass $y$ ein Teiler von $x$ ist), wenn $x=qy$ für eine ganze Zahl $q$ gilt. Oft schreibt man dafür kurz $y|x$. Wenn $y$ kein Teiler von $x$ ist, schreiben wir $y\not|x$. Beispiel: $3|12,-3|12,-3|-12,-3|12,3|0,0|0$. Beobachtungen: Die Teilbarkeitsrelation $|$ ist reflexiv und transitiv. Es handelt sich damit um eine ,,Präordnung'' (oft auch ,,Quasiordnung'' genannt). Zahlen $x$ und $-x$ können von ihr nicht unterschieden werden: Es gilt $x|y\Leftrightarrow -x|y$ und $y|x\Leftrightarrow y|-x$, und weiter $x|-x$ und $-x|x$. Die Präordnung ist also nicht antisymmetrisch. Sie ist auch nicht total, weil manche Elemente nicht verglichen werden können: $4\not|9$ und $9\not|4$. Aus $0|x$ folgt $x=0$; für jede ganze Zahl $y$ gilt $y|0$; also ist in dieser Präordnung $0$ das eindeutig bestimmte größte Element. Für jede ganze Zahl $x$ gilt: $1|x$ und $-1|x$, also sind $1$ und $-1$ kleinste Elemente. Wenn $m\geq 1$ ist, ist $m|x$ gleichbedeutend mit $x\ mod\ m= 0$. Fakt 4.2 Teilbarkeit: Für beliebige $x,y,z\in\mathbb{Z}$ gilt: \begin{enumerate*} \item Aus $x|y$ und $x|z$ folgt $x|uy+vz$ für alle $u,v\in\mathbb{Z}$. \item Aus $x|y$ folgt $ux|uy$ für alle $u\in\mathbb{Z}$. \item Aus $x|y$ und $y|z$ folgt $x|z$ (Transitivität). \item Aus $x|y$ und $y\not= 0$ folgt $0<|x|\leq |y|$. \item Aus $x|y$ und $y|x$ folgt $|x|=|y|$. Wenn zudem $x,y\geq 0$ gilt, folgt $x=y$. \end{enumerate*} ![Abbildung 1](Assets/Kryptographie-teilbarkeitsbeziehung.png) Einige Zahlen und ihre Teilbarkeitsbeziehungen. Beziehungen, die aus der Transitivität folgen, sind nicht eingetragen. Man erkennt $1$ und $-1$ als kleinste Elemente und $0$ als größtes Element der Teilbarkeitsbeziehung als Präordnung. Die Elemente in der Ebene unmittelbar über $\{1,-1\}$ sind die Primzahlen, positiv und negativ, also Zahlen $x\not=\pm 1$, die durch keine Zahl außer $\pm x$ und $\pm 1$ teilbar sind. Der Beweis ist eine einfache Übung. \textbf{Definition} 4.3 Größter gemeinsamer Teiler: \begin{enumerate*} \item Für $x,y\in\mathbb{Z}$ heißt $t\in\mathbb{Z}$ ein gemeinsamer Teiler von $x$ und $y$, wenn $t|x$ und $t|y$ gilt. (Bemerkung: 1 ist stets gemeinsamer Teiler von $x$ und $y$.) \item Für $x,y\in\mathbb{Z}$ sei $ggT(x, y)$, der größte gemeinsame Teiler von $x$ und $y$, die (eindeutig bestimmte) nichtnegative Zahl $d$ mit: \begin{itemize*} \item $d$ ist gemeinsamer Teiler von $x$ und $y$; \item jeder gemeinsame Teiler von $x$ und $y$ ist Teiler von $d$. \end{itemize*} \item $x,y\in\mathbb{Z}$ heißen teilerfremd, wenn $ggT(x,y)=1$ gilt, d.h. wenn sie nicht beide $0$ sind und keine Zahl $>1$ beide teilt. \end{enumerate*} Bei Definition 4.3.2 stellt sich die Frage nach Existenz und Eindeutigkeit von $ggT(x,y)$. Wir beweisen diese Eigenschaften im Anhang. Wir bemerken, dass $ggT(0,0) = 0$ gilt. (Sei $d = ggT(0,0)$. Weil $0|0$, folgt mit Def. 4.3.2 $0|d$ und damit $d=0$.) Wenn $x\not= 0$ oder $y\not= 0$ gilt, kann es keinen gemeinsamen Teiler geben, der größer als $max\{|x|,|y|\}$ ist, und der größte gemeinsame Teiler ist auch größtmöglich im Sinn der gewöhnlichen Ordnung auf $\mathbb{Z}$. Weil das Vorzeichen für die Teilbarkeit irrelevant ist, gilt stets $ggT(x,y) = ggT(|x|,|y|)$, und man kann sich immer auf den Fall nichtnegativer Argumente beschränken. Weiter gilt $$ggT(x,y) = ggT(x+uy,y) \quad\quad(4.1)$$, für beliebige $x,y,u\in\mathbb{Z}$. (Wenn $d$ gemeinsamer Teiler von $x$ und $y$ ist, dann teilt $d$ auch $x+uy$. Wenn $d$ gemeinsamer Teiler von $z=x+uy$ und $y$ ist, dann teilt $d$ auch $z-uy =x$. Also haben die Paare $(x,y)$ und $(x+uy,y)$ dieselbe Menge gemeinsamer Teiler, und es folgt $ggT(x,y) = ggT(x+uy,y)$.) Es gibt einen effizienten Algorithmus zur Ermittlung des größten gemeinsamen Teilers. Er beruht auf den Gleichungen \begin{enumerate*} \item $ggT(x,y) = ggT(|x|,|y|)$ für alle $x,y\in\mathbb{Z}$, \item $ggT(x,y) = ggT(y,x)$ für alle $x,y\in\mathbb{Z}$, \item $ggT(a,0) =a$ für $a\geq 0$, \item $ggT(a,b) = ggT(b,a\ mod\ b)$ für $a\geq b >0$. \end{enumerate*} (1. gilt, weil Teilbarkeit das Vorzeichen ignoriert. 2. ist trivial. 3. folgt daraus, dass jede Zahl Teiler von $0$ ist. 4. folgt aus 4.1 und 2., weil $a\ mod\ b=a-qb$ mit $q=ba/bc$ gilt.) Wir setzen die Beobachtung in ein iteratives Verfahren um. Algorithmus 4.1 Euklidischer Algorithmus: \begin{itemize*} \item Input: Zwei ganze Zahlen $x$ und $y$. \item Methode: \begin{enumerate*} \item $a,b:integer;a\leftarrow |x|;b\leftarrow |y|;$ \item $while\ b> 0\ repeat$ \item $(a,b)\leftarrow (b,amodb);$ // simultane Zuweisung \item return $a$. \end{enumerate*} \end{itemize*} Die eigentliche Rechnung findet in der while-Schleife statt. In dieser Schleife wird immer ein Zahlenpaar durch ein anderes ersetzt, das dieselben gemeinsamen Teiler hat wie $x$ und $y$. Wenn der Algorithmus terminiert, weil der Inhalt $b$ von $b$ Null geworden ist, kann man den Inhalt von $a$ ausgeben. Beispiel: Auf Eingabe $x=10534, y=12742$ ergibt sich der nachstehenden Tabelle angegebene Ablauf. Die Zahlen $a_i$ und $b_i$ bezeichnen den Inhalt der Variablen $a$ und $b$, nachdem die Schleife in Zeilen $2-3$ i-mal ausgeführt worden ist. Die Ausgabe ist $46 = ggT(10534,12742)$. \begin{tabular}{c} | i | $a_i$ | $b_i$ \\\hline | 0 | 10534 | 12742 \\ | 1 | 12742 | 10534 \\ | 2 | 10534 | 2208 \\ | 3 | 2208 | 1702 \\ | 4 | 1702 | 506 \\ | 5 | 506 | 184 \\ | 6 | 184 | 138 \\ | 7 | 138 | 46 \\ | 8 | 46 | 0 \end{tabular} Fakt 4.4 Algorithmus 4.1 gibt $ggT(x,y)$ aus. Wenn $|x|<|y|$, hat der erste Schleifendurchlauf nur den Effekt, die beiden Zahlen zu vertauschen. Wir ignorieren diesen trivialen Schleifendurchlauf. Wir betrachten die Zahlen $a$ in $a$ und $b$ in $b$. Es gilt stets $a>b$, und $b$ nimmt in jeder Runde strikt ab, also terminiert der Algorithmus. Um einzusehen, dass er sogar sehr schnell terminiert, bemerken wir Folgendes. Betrachte den Beginn eines Schleifendurchlaufs. Der Inhalt von $a$ sei $a$, der Inhalt von $b$ sei $b$, mit $a\geq b >0$. Nach einem Schleifendurchlauf enthält $a$ den Wert $a'=b$ und $b$ den Wert $b'=a\ mod\ b$. Falls $b'=0$, endet der Algorithmus. Sonst wird noch ein Durchlauf ausgeführt, an dessen Ende $a$ den Wert $b'=a\ mod\ b$ enthält. Wir behaupten: $b'<\frac{1}{2} a$. Um dies zu beweisen, betrachten wir zwei Fälle: Wenn $b>\frac{1}{2} a$ ist, gilt $b'=a\ mod\ b=a-b<\frac{1}{2} a$. Wenn $b\leq\frac{1}{2} a$ ist, gilt $b'=a\ mod\ b < b\leq\frac{1}{2} a$. - Also wird der Wert in $a$ in jeweils zwei Durchläufen mindestens halbiert. Nach dem ersten Schleifendurchlauf enthält $a$ den Wert $min\{x,y\}$. Daraus ergibt sich Teil 1. der folgenden Aussage. Fakt 4.5 \begin{enumerate*} \item Die Schleife in Zeilen $2-3$ wird höchstens $O(log(min\{x,y\}))$-mal ausgeführt. \item Die gesamte Anzahl von Ziffernoperationen für den Euklidischen Algorithmus ist $O((log\ x)(log\ y))$. \end{enumerate*} Man beachte, dass $\lceil log(x+1)\rceil\approx log\ x$ die Anzahl der Bits in der Binärdarstellung von $x$ ist. Damit hat der Euklidische Algorithmus bis auf einen konstanten Faktor denselben Aufwand wie die Multiplikation von $x$ und $y$, wenn man die Schulmethode benutzt. (Der Beweis der Schranke in 2. benötigt eine Rechnung, die die Längen der beteiligten Zahlen genauer verfolgt.) Beispiel: \begin{enumerate*} \item $21$ und $25$ sind teilerfremd. Es gilt $31*21 + (-26)*25 = 651-650 = 1$. \item Auch $-21$ und $25$ sind teilerfremd. Aus 1. folgt sofort $(-31)*(-21) + (-26)*25 =651 -650 = 1$. \item Es gilt $ggT(21,35) = 7$, und $2* 35 - 3 *21 = 7$. \end{enumerate*} Die folgende sehr nützliche Aussage verallgemeinert diese Beobachtung: \textbf{Lemma} 4.6... von Bezout \begin{enumerate*} \item Wenn $x,y\in\mathbb{Z}$ teilerfremd sind, gibt es $s,t\in\mathbb{Z}$ mit $sx+ty= 1$. \item Für $x,y\in\mathbb{Z}$ gibt es $s,t\in\mathbb{Z}$ mit $sx+ty= ggT(x,y)$. \end{enumerate*} Wir geben einen Algorithmus an, der zu $x$ und $y$ die Werte $s$ und $t$ (sehr effizient) berechnet. Damit ist die Frage der Existenz natürlich gleich mit erledigt. Vorab bemerken wir noch, dass es eine Art Umkehrung von 1. gibt: Wenn $sx+ty= 1$ für ganze Zahlen $s$ und $t$ gilt, dann sind $x$ und $y$ teilerfremd. (Beweis: Alle gemeinsamen Teiler von $x$ und $y$ teilen auch $1$, sind also $1$ oder $-1$. Daraus folgt $ggT(x,y) = 1$.) Für den Algorithmus können wir o.B.d.A. annehmen, dass $x,y\geq 0$ gilt. Die Umrechnung für negative Inputs ist offensichtlich. Algorithmus 4.2 Erweiterter Euklidischer Algorithmus: \begin{itemize*} \item Eingabe: Natürliche Zahlen $x$ und $y$. \item Methode: \begin{enumerate*} \item $a,b,sa,ta,sb,tb,q:integer;$ \item $a\leftarrow x; b\leftarrow y;$ \item $sa\leftarrow 1; ta\leftarrow 0; sb\leftarrow 0; tb\leftarrow 1;$ \item while $b> 0$ repeat \begin{enumerate*} \item $q\leftarrow a\ div\ b$; \item $(a,b)\leftarrow (b,a-q*b)$; \item $(sa,ta,sb,tb)\leftarrow (sb,tb,sa-q*sb,ta-q*tb)$; \end{enumerate*} \item return$(a,sa,ta)$; \end{enumerate*} \end{itemize*} Genau wie im ursprünglichen Euklidischen Algorithmus findet die eigentliche Arbeit in der while-Schleife (Zeilen 4 - 7 ) statt. Die Idee hinter dem Algorithmus ist folgende. Wie im (einfachen) Euklidischen Algorithmus werden in den Variablen $a$ und $b$ Zahlen $a$ und $b$ mit geführt, die stets $ggT(a,b) =d= ggT(x,y)$ erfüllen. Nach dem ersten Durchlauf gilt $b\leq a$. Die Variablen $sa,ta,sb$ und $t_b$ enthalten immer Zahlenpaare $(s_a,t_a)$ und $(s_b,t_b)$, die folgende Gleichungen erfüllen: $$a=s_a*x+t_a*y$$ $$b=s_b*x+t_b*y \quad\quad(4.2)$$ Diese Gleichung wird durch die Initialisierung hergestellt. In einem Schleifendurchlauf wird $a$ durch $b$ ersetzt und $(s_a,t_a)$ durch $(s_b,t_b)$, und es wird $b$ durch $a-q*b$ ersetzt sowie $(s_b,t_b)$ durch $(s_a-q*s_b, t_a-q*t_b)$. Dadurch bleiben die Gleichungen (4.2) gültig. Wenn schließlich $b=0$ geworden ist, gilt $d=ggT(x,y) =a=s_a*x+t_a*y$. Das bedeutet, dass die Ausgabe das gewünschte Ergebnis darstellt. Als Beispiel betrachten wir den Ablauf des Algorithmus auf der Eingabe $(x,y) =(10534,12742)$. Die Zahlen $a_i,b_i,s_{a,i},t_{a,i},s_{b,i},t_{b,i}$ bezeichnen den Inhalt von $a,b,sa,ta,sb,tb$ nach dem i-ten Schleifendurchlauf. \begin{tabular}{c|c|c|c|c|c|c|c|c|c} $i$ & $a_i$ & $b_i$ & $s_{a,i}$ & $t_{a,i}$ & $s_{b,i}$ & $t_{b,i}$ & $q_i$ & & \\\hline 0 & 10534 & 12742 & & 1 & 0 & 0 & 1 & - \\ 1 & 12742 & 10534 & & 0 & 1 & 1 & 0 & - \\ 2 & 10534 & 2208 & 1 & 0 & - & 1 & 1 & 1 \\ 3 & 2208 & 1702 & - & 1 & 1 & 5 - & 4 & 4 \\ 4 & 1702 & 506 & 5 & - & 4 & - 6 & 5 & 1 \\ 5 & 506 & 184 & - & 6 & 5 & 23 & - & 19 & 3 \\ 6 & 184 & 138 & 23 & - & 19 & - & 52 & 43 & 2 \\ 7 & 138 & 46 & - & 52 & 43 & 75 & - & 62 & 1 \\ 8 & 46 & 0 & 75 & - & 62 & - & 277 & 229 & 3 \end{tabular} Die Ausgabe ist $(46, 75 ,-62)$. Man überprüft leicht, dass $46 = ggT(10534,12742) = 75* 10534 - 62 * 12742$ gilt. - Allgemein gilt: Fakt 4.7: Wenn Algorithmus 4.2 auf Eingabe $(x,y)$ mit $x,y\geq 0$ gestartet wird, dann gilt: \begin{enumerate*} \item Für die Ausgabe $(d,s,t)$ gilt $d= ggT(x,y) =sx+ty$. \item Die Anzahl der Schleifendurchläufe ist dieselbe wie beim gewöhnlichen Euklidischen Algorithmus. \item Die Anzahl von Ziffernoperationen für Algorithmus 4.2 ist $O((log\ x)(log\ y))$. \end{enumerate*} Wir notieren noch eine wichtige Folgerung aus dem Lemma von Bezout. Die Aussage ist aus der Schule bekannt: Wenn eine Zahl z.B. durch $3$ und durch $5$ teilbar ist, dann ist sie auch durch 15 teilbar. Dort benutzt man die Primzahlzerlegung zur Begründung. Diese ist aber gar nicht nötig. Fakt 4.8: Wenn $x$ und $y$ teilerfremd sind und $a$ sowohl durch $x$ als auch durch $y$ teilbar ist, dann ist $a$ auch durch $xy$ teilbar. Beweis: Weil $x$ und $y$ Teiler von $a$ sind, kann man $a=ux$ und $a=vy$ schreiben, für ganze Zahlen $u,v$. Weil $x$ und $y$ teilerfremd sind, liefert Lemma 4.6.1 zwei ganze Zahlen $s$ und $t$ mit $1=sx+ty$. Dann ist $a=asx+aty=vysx+uxty= (vs+ut)xy$, also ist $xy$ Teiler von $a$. \subsection{Modulare Arithmetik} \textbf{Definition} 4.9: Für $m\geq 2$ definieren wir eine zweistellige Relation auf $\mathbb{Z}: x\equiv y (mod\ m)$ heißt $m|(x-y)$. Man sagt: ,,$x$ ist kongruent zu $y$ modulo $m$.'' In der Mathematik sieht man auch oft die kompaktere Notation $x\equiv y(m)$ oder $x\equiv_m y$. Es besteht eine enge Beziehung zwischen dieser Relation und der Division mit Rest. Fakt 4.10: \begin{enumerate*} \item $x\equiv y(mod\ m)$ gilt genau dann wenn $x\ mod\ m=y\ mod\ m$ gilt. \item Die zweistellige Relation $*\equiv *(mod\ m)$ ist eine Äquivalenzrelation, sie ist also reflexiv, transitiv und symmetrisch. \end{enumerate*} \textbf{Beispiel}für 1.: $29\ mod\ 12 = 53\ mod\ 12 = 5$ und $53-29 = 24$ ist durch $12$ teilbar. Der Beweis von 1. ist eine leichte Übung; 2. folgt sofort aus 1. Die Kongruenzrelation $* \equiv *(mod\ m)$ führt (wie jede Äquivalenzrelation) zu einer Zerlegung der Grundmenge $\mathbb{Z}$ in Äquivalenzklassen (die hier ,,Restklassen'' heißen): $[x]_m= [x] =\{y\in\mathbb{Z}|x\equiv y(mod\ m)\}=\{y\in\mathbb{Z}|x\ mod\ m=y\ mod\ m\}$. Wir definieren: $m\mathbb{Z}:=\{...,-3m,-2m,-m,0,m,2m,3m,...\}$ und $x+A:=\{x+y|y\in A\}$, für $A\supseteq Z$. Beispiel: Für $m=3$ gibt es die drei Restklassen \begin{itemize*} \item $[0] = [0]_3 =\{...,-6,-3,0,3,6,...\}= 0 + 3\mathbb{Z}$, \item $[1] = [1]_3 =\{...,-5,-2,1,4,7,...\}= 1 + 3\mathbb{Z}$, \item $[2] = [2]_3 =\{...,-4,-1,2,5,8,...\}= 2 + 3\mathbb{Z}$. \end{itemize*} Mit den Restklassen kann man dann wieder rechnen: Addition und Multiplikation lassen sich wie folgt definieren. \begin{itemize*} \item $[x]_m+ [y]_m := [x+y]_m$, \item $[x]_m*[y]_m := [x*y]_m$ \end{itemize*} Beispielsweise gelten für $m=3$ die Gleichheiten $[4] + [5] = [9] = [0]$ und $[4]*[5] =[20] = [2]$. Fakt 4.11: Diese Operationen sind wohldefiniert, d.h., aus $x\equiv x'(mod\ m)$ und $y\equiv y'(mod\ m)$ folgt $[x+y]_m= [x'+y']_m$ und $[x*y]_m= [x'*y']_m$. Der Beweis ist einfach. Weil $x\equiv x' (mod\ m)$ und $y\equiv y' (mod\ m)$ gilt, sind $x-x'$ und $y-y'$ durch $m$ teilbar. Also ist auch $xy-x'y'=x(y-y') + (x-x')y'$ durch $m$ teilbar, und es gilt $x*y\equiv x'*y' (mod\ m)$. Der Fall der Addition ist noch einfacher. Aus der Definition und der Wohldefiniertheit ergibt sich, dass man anstatt mit Restklassen auch mit Repräsentanten rechnen kann. Statt $([5]_3 *[5]_3)*[2]_3 = [25]_3 *[2]_3 = [1]_3 *[2]_3 = [2]_3$ schreibt man dann einfach $(5*5)* 2 \equiv 25 * 2 \equiv 1 * 2 \equiv 2 (mod\ 3)$. Fakt 4.11 besagt auch, dass an jeder Stelle einer solchen Rechnung jede Zahl durch eine dazu kongruente Zahl ersetzt werden darf, je nachdem, wie es bequem ist. Beispiel: $(5*5)* 2 \equiv((-1)*(-1))*(-1) = (-1)^3 =- 1 \equiv 2 (mod\ 3)$. Da $(x\ mod\ m)\equiv x(mod\ m)$ für alle $x$ und $m\geq 1$ gilt, kann man in ,,modulo-m-Rechnungen'' eine Zahl $x$ insbesondere immer durch ihren Rest modulo m ersetzen. Beispiel: Um $13^7\ mod\ 11$ zu berechnen, rechnet man $13^7\equiv 27\equiv 2^5*4 =32* 4\equiv (-1)*4 = -4\equiv 7(mod\ 11)$. Um $3^{1006}\ mod\ 7$ zu berechnen, bemerkt man, dass $3^2\ mod\ 7=2$ ist, also $3^{1006}\equiv 2^{503}(mod\ 7)$. Weil nun $2^3\ mod\ 7=1$ gilt, folgt $2^{503}=(2^3)^{167} * 2^2 \equiv 1^{167}*4=4(mod\ 7)$. Zu $m\geq 1$ betrachtet die Menge aller Restklassen: $\mathbb{Z}_m:=\mathbb{Z}/m\mathbb{Z}:=\{[x]_m|x\in\mathbb{Z}\}=\{[x]| 0 \leq x1$ ist, gibt es kein Inverses zu $x$ in $\mathbb{Z}_m$. Wenn $d=1$ ist, folgt $sx\ mod\ m=1$, also ist $s\ mod\ m$ das gewünschte inverse Element. Die Rechenzeit für das Berechnen des ,,modularen Inversen'' beträgt also $O((log\ x)(log\ m))$. Die Menge der invertierbaren Elemente von $\mathbb{Z}_m$ erhält eine eigene Bezeichnung. \textbf{Definition} 4.17: Für $m\geq 2$ sei $\mathbb{Z}^*_m:=\{x\in\mathbb{Z}_m| ggT(x,m)=1\}$. (Wieder sind eigentlich die Restklassen $[x]_m, 0\leq x < m, ggT(x,m) = 1$, gemeint.) Fakt 4.18: Für jedes $m\geq 2$ gilt: $\mathbb{Z}^*_m$ mit der Multiplikation modulo m als Operation ist eine (kommutative) Gruppe. Beispiel: $\mathbb{Z}^*_{21}=\{1,2,4,5,8,10,11,13,16,17,19,20\}$ und $\mathbb{Z}^*_7=\{1,2,3,4,5,6\}$. Wir haben $8*16 \equiv 128 \equiv 2 (mod\ 21)$, mit $2\in\mathbb{Z}^*_{21}$. Für $17\in\mathbb{Z}^*_{21}$ gibt es das Inverse $5$, denn $17*5 = 85\equiv 1 (mod\ 21)$. Aus den Gruppeneigenschaften weiß man, dass Inverse eindeutig bestimmt sind. Für das Inverse von $x$ (wenn es existiert) schreiben wir $x^{-1} mod\ m$ (gemeint ist die Restklasse oder der eindeutig bestimmte Repräsentant in $\{0,1 ,...,m-1\}$). Am schönsten ist die Situation, wenn alle Zahlen $1,...,m-1$ in $\mathbb{Z}^*_m$ liegen. Das heißt insbesondere, dass keine der Zahlen $2, 3 ,...,m-1$ die Zahl $m$ teilt. Um diese Situation zu beschreiben, definieren wir vorläufig den Begriff der Primzahl. Man erinnere sich, dass jede ganze Zahl $x$ durch $x$ und $-x$ sowie durch $1$ und $-1$ teilbar ist. Eine ganze Zahl $p\geq 1$ heißt Primzahl, wenn $p$ genau zwei positive Teiler hat, nämlich $1$ und $p$. Die Folge der Primzahlen beginnt mit $2, 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 ,....$ Fakt 4.19 (*): Für jedes $m\geq 2$ sind folgende Aussagen äquivalent: \begin{enumerate*} \item $m$ ist eine Primzahl. \item $\mathbb{Z}^*_m=\{ 1 ,...,m-1\}$. \item $\mathbb{Z}_m$ ist ein Körper. \end{enumerate*} Der Beweis erfolgt durch einen Ringschluss. \begin{itemize*} \item ,,1. $\Rightarrow$ 2.'': Sei $m$ Primzahl. Dann kann für kein Element $x\in\{1 ,...,m-1\}$ die Beziehung $ggT(x,m)>1$ gelten, weil sonst die Zahl $ggT(x,m)$ ein Teiler von $m$ strikt zwischen $1$ und $m$ wäre. \item ,,2. $\Rightarrow$ 3.'': Wenn $\mathbb{Z}^*_m=\{1 ,...,m-1\}$ gilt, hat nach Fakt 4.16 jedes Element von $\mathbb{Z}_m -\{0\}$ ein multiplikatives Inverses. Das ist genau die Eigenschaft, die dem Ring $\mathbb{Z}_m$ zum Körper fehlt. \item ,,3. $\Rightarrow$ 1.'': Das beweisen wir durch Kontraposition. Sei also 1. falsch, d.h. sei $m$ keine Primzahl. Dann gibt es ein $x\in\{2,...,m-1\}$, das Teiler von $m$ ist. Insbesondere ist $ggT(x,m) =x >1$. \item Mit Fakt 4.16 folgt, dass $x$ kein multiplikatives Inverses modulo $m$ hat, also ist $\mathbb{Z}_m$ kein Körper, d.h. 3. ist falsch. \end{itemize*} Beispiel: $m=13$. Wir geben für jedes $x\in\mathbb{Z}^*_{13}$ das Inverse $y$ sowie das Produkt $x*y$ an (das natürlich bei der Division durch $13$ Rest $1$ lassen muss). \begin{tabular}{c} | x | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 \\\hline | y | 1 | 7 | 9 | 10 | 8 | 11 | 2 | 5 | 3 | 4 | 6 | 12 \\ | $x*y$ | 1 | 14 | 27 | 40 | 40 | 66 | 14 | 40 | 27 | 40 | 66 | 144 \end{tabular} $14$ ist keine Primzahl, und es gibt keine Zahl $y$ mit $2*y\ mod\ 14 = 1$; das heißt, dass $2\not\in\mathbb{Z}^*_{14}$ und daher, dass $\mathbb{Z}_{14}$ kein Körper ist. Wir notieren noch einen altehrwürdigen Satz aus der Zahlentheorie. Der Satz wurde von Pierre de Fermat, 1607-1665, einem französischen Mathematiker und Juristen, gefunden. Fakt 4.20 (Kleiner Satz von Fermat): Wenn $p$ eine Primzahl ist, dann gilt: $a^{p-1}\ mod\ p= 1$, für jedes $a\in\mathbb{Z}^*_p$. Beweis: Sei $a\in\mathbb{Z}^*_p$ gegeben. Betrachte die Abbildung $g_a: \mathbb{Z}^*_p \owns s\rightarrow as\ mod\ p\in\mathbb{Z}^*_p$. Diese Abbildung ist injektiv, da für das zu $a$ inverse Element $b=a^{-1}\ mod\ p$ gilt: $b*g_a(s)\ mod\ p=b(as)\ mod\ p=((ba)\ mod\ p)s\ mod\ p=s$. Also gilt: $\{1,...,p-1\}=\{g_a(1),...,g_a(p-1)\}$. Wir multiplizieren die Zahlen $1,...,p-1$ in zwei Anordnungen: $1*...*(p-1)\ mod\ p =g_a(1) *...*g_a(p-1)\ mod\ p=a^{p-1} *(1*...*(p-1)\ mod\ p)$. Wenn wir beide Seiten mit dem multiplikativen Inversen von $X:= 1*...*(p-1)\ mod\ p$ multiplizieren, erhalten wir $1=a^{p-1}\ mod\ p$. Wir bemerken, dass auch eine gewisse Umkehrung gilt, sogar für beliebige $m$: Wenn $a^{m-1}\ mod\ m=1$ ist, d.h. $a^{m-1}-qm=1$ für ein $q$, dann folgt $ggT(a,m)=1$. Wenn also $a\in\mathbb{Z}_m -\mathbb{Z}^*_m$, dann gilt auf jeden Fall $a^{m-1}\ mod\ m\not= 1$. \subsection{Der Chinesische Restsatz} Der ,,Chinesische Restsatz'' besagt im Wesentlichen, dass für teilerfremde Zahlen $m$ und $n$ die Strukturen $\mathbb{Z}_m \times\mathbb{Z}_n$ (mit komponentenweisen Operationen) und $\mathbb{Z}_{mn}$ isomorph sind. Wir beginnen mit einem Beispiel, nämlich $m=3,n=8$, also $mn=24$. Die folgende Tabelle gibt die Reste der Zahlen $x\in\{0,1,...,23\}\ modulo\ 3$ und $modulo\ 8$ an. Die Restepaare wiederholen sich zyklisch für andere $x\in\mathbb{Z}$. \begin{tabular}{c} | x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 \\\hline | x mod 3 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 \\ | x mod 8 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | 8 | 4 | 5 | 6 | 7 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 \end{tabular} Wenn wir die Einträge in Zeilen 2 und 3 als 24 Paare in $\mathbb{Z}_3 \times\mathbb{Z}_8$ ansehen, erkennen wir, dass sie alle verschieden sind, also auch alle Möglichkeiten in $\{0,1,2\}\times\{0,1,...,7\}$ abdecken. D.h.: Die Abbildung $x\rightarrow (x\ mod\ 3,x\ mod\ 8)$ ist eine Bijektion zwischen $\mathbb{Z}_{24}$ und $\mathbb{Z}_3\times\mathbb{Z}_8$. Zudem spiegeln sich arithmetische Operationen auf den Elementen von $\mathbb{Z}_{24}$ in den Resten modulo $3$ und $8$ wider. Beispielsweise liefert die Addition von $(2,7)$ und $(2,1)$ das Resultat $(1,0)$, das der Addition von $23$ und $17$ mit dem Resultat $40\ mod\ 24 = 16$ entspricht. Genauso ist $(2^5\ mod\ 3, 3^5\ mod\ 8)=(2,3)$, was der Beobachtung $11^5\ mod\ 24 = 11$ entspricht. Der Chinesische Restsatz sagt im wesentlichen, dass eine solche strukturelle Entsprechung zwischen den Resten modulo $mn$ und Paaren von Resten modulo $m$ bzw. $n$ immer gilt, wenn $m$ und $n$ teilerfremd sind. Fakt 4.21 Chinesischer Restsatz (*): $m$ und $n$ seien teilerfremd. Dann ist die Abbildung $\Phi:\mathbb{Z}_{mn} \owns x \rightarrow (x\ mod\ m, x\ mod\ n)\in\mathbb{Z}_m\times\mathbb{Z}_n$ bijektiv. Weiterhin: Wenn $\Phi(x)=(x_1,x_2)$ und $\Phi(y)=(y_1,y_2)$, dann gilt: \begin{enumerate*} \item $\Phi(x+_{mn} y) = (x_1 +_m y_1 , x_2 +_n y_2)$ \item $\Phi(x*_{mn} y) = (x_1 *_m y_1 , x_2 *_n y_2)$ \item $\Phi(1) = (1,1)$ \end{enumerate*} (Dabei bezeichnen $+_j$ und $*_j$ die Addition und die Multiplikation modulo $j$.) Für mathematisch-strukturell orientierte Leser/innen: Die Gleichungen 1. bis 3. kann man etwas abstrakter auch so fassen, dass die Abbildung $\Phi$ ein Ring-mit-1-Isomorphismus zwischen $\mathbb{Z}_{mn}$ und $\mathbb{Z}_m \times\mathbb{Z}_n$ ist. Man kann sich noch fragen, wie man nötigenfalls zu gegebenen Zahlen $s\in\mathbb{Z}_m$ und $t\in\mathbb{Z}_n$ die Zahl $x\in\mathbb{Z}_{mn}$ berechnen kann, die $\Phi(x)=(s,t)$ erfullt. Dazu betrachtet man zunächst den Fall $s=1$ und $t=0$. Weil $m$ und $n$ teilerfremd sind, kann man mit dem erweiterten Euklidischen Algorithmus ein $u\in\mathbb{Z}_{m}$ mit $un\ mod\ m=1$ finden. Wir setzen $y=un\in\mathbb{Z}_{mn}$. Dann gilt $y\ mod\ m=1$ und $y\ mod\ n=0$. Analog findet man ein $z\in\mathbb{Z}_{mn}$ mit $z\ mod\ m=0$ und $z\ mod\ n=1$. Nun setzen wir $x:=(sy+tz)\ mod\ mn\in\mathbb{Z}_{mn}$. Wir haben, modulo $m$ gerechnet: $x\equiv sy+tz\equiv s*1+t* 0 \equiv s\ (mod\ m)$. Analog ergibt sich $x\equiv sy+tz\equiv s*0+t*1 \equiv t(mod\ n)$, wie gewünscht. Der Berechnungsaufwand für das Finden von $x$ ist $O((log\ m)(log\ n))$ Ziffernoperationen, das geht also sehr schnell. Beispiel: $m=5,n=8,s=3,t=7$. Wir finden $u=2$ mit $u*8\ mod\ 5 = 1$ und $y= 2*8=16$ sowie $v=5$ mit $v*5\ mod\ 8=1$ und $z=5*5=25$. Nun setzen wir $x=(3*16+7*25) \ mod\ 40=(48+175)\ mod\ 40 = (8 + 15)\ mod\ 40 = 23$. Und tatsächlich: $23\ mod\ 5 = 3$ und $23\ mod\ 8 = 7$. Wir wollen noch untersuchen, wie sich Zahlen, die zu $m$ und $n$ teilerfremd sind, in der Sichtweise des Chinesischen Restsatzes verhalten. \textbf{Proposition} 4.22 (*): Wenn man die Abbildung $\Phi$ aus dem Chinesischen Restsatz auf $\mathbb{Z}^*_{mn}$ einschränkt, ergibt sich eine Bijektion zwischen $\mathbb{Z}^*_{mn}$ und $\mathbb{Z}^*_m\times\mathbb{Z}^*_n$. Bemerkung: Der Chinesische Restsatz und die nachfolgenden Bemerkungen und Behauptungen lassen sich leicht auf $r>2$ paarweise teilerfremde Faktoren $n_1,...,n_r$ verallgemeinern. Die Aussagen lassen sich durch vollständige Induktion über $r$ beweisen. Mit Prop. 4.22 können wir eine übersichtliche Formel für die Kardinalitäten der Mengen $\mathbb{Z}^*_m, m\geq 2$, entwickeln. \textbf{Definition} 4.23 (Eulersche $\varphi$-Funktion): für $m\geq 2$ sei $\varphi(m):=|\mathbb{Z}^*_m| =|\{x| 01$ hätten, dann wäre $p_1$ Teiler von $p^{t_2}_2...p^{t_s}_s$, was sofort einen Widerspruch zur Eindeutigkeit der Primfaktorzerlegung ergibt. Mit Lemma 4.24, $(s-1)$-mal angewendet, erhalten wir $\varphi(m) =\prod^s_{i=1} \varphi(p^{t_i}_i) = \prod^s_{i=1} (p^{t_i}_i (1-1/p_i)) =m* \prod^s_{i=1} (1-\frac{1}{p_i})$. Mit dieser Formel lassen sich die Werte in Tabelle 2 schnell verifizieren. (Beispiel: $\varphi(12) = 12(1-1/2)(1-1/3) = 12*(1/2)*(2/3) = 4$) Man beachte als Spezialfall: Wenn $m=pq$ für verschiedene Primzahlen $p$ und $q$, dann ist $\varphi(m)=pq(1-1/p)(1-1/q) =(p-1)(q-1)$. (Beispiel: $\varphi(15) =2*4=8$) Bemerkung: Die einfache Formel in Lemma 4.29 könnte zu dem Schluss verleiten, dass sich $\varphi(m)$ zu gegebenem $m$ immer leicht berechnen lässt. Aber Achtung: Man muss dazu die Menge der Primfaktoren von $m$ kennen. Dies läuft darauf hinaus, dass Faktorisierungsproblem für $m$ zu lösen, also einen beliebigen Primfaktor für $m$ zu finden, und hierfür kennt man keine effizienten Algorithmen. Tatsächlich ist auch kein effizienter Algorithmus bekannt, der es erlaubt, $\varphi(m)$ aus $m$ zu berechnen. Fakt 4.30: Jede zusammengesetzte Zahl $x$ besitzt einen Primfaktor $p$ mit $p\leq\sqrt{x}$. Beweis: Man schreibt $x=yz$ für Zahlen $y$ und $z$, die weder 1 noch $x$ sind. Es ist nicht möglich, dass beide größer als $\sqrt{x}$ sind. Der kleinere Faktor enthält also einen Primfaktor, der nicht größer als $\sqrt{x}$ ist. Bemerkung: Wir betrachten das resultierende naive Faktorisierungsverfahren: Teste die Zahlen in $\{2,...,\lfloor\sqrt{x}\rfloor\}$ nacheinander darauf, ob sie $x$ teilen; wenn ein Faktor $p$ gefunden wurde, wende dasselbe Verfahren auf $x'=x/p$ an. Dieses Verfahren hat im schlechtesten Fall Rechenzeit mindestens $\Theta (\sqrt{x}) = \Theta (2^{(log\ x)/ 2})$, also exponentiell in der Bitlänge von $x$. Wie wir später genauer diskutieren werden, sind für das Auffinden der Primzahlzerlegung einer gegebenen Zahl $x$ überhaupt keine effizienten Algorithmen bekannt (also Algorithmen mit Laufzeiten $O((log\ x)^c)$ für konstantes $c$). Aber es gibt effiziente Algorithmen, mit denen man feststellen kann, ob eine Zahl $x$ eine Primzahl ist oder nicht. Dieser Unterschied in der Schwierigkeit des Faktorisierungsproblems und des Primzahlproblems liegt einer ganzen Reihe von kryptographischen Verfahren zugrunde. Satz 4.31 (Euklid): Es gibt unendlich viele Primzahlen. Beweis: Wenn $\{p_1,...,p_k\}$, für $k\geq 1$, eine endliche Menge von (verschiedenen) Primzahlen ist, betrachten wir die Zahl $x=1+p_1...p_k$. Die Zahl $x$ kann durch keine der Zahlen $p_1,...,p_k$ teilbar sein, sonst wäre $1$ durch diese Primzahl teilbar, was nicht möglich ist. Also sind alle Primfaktoren in der Primzahlzerlegung von $x$ von $p_1,...,p_k$ verschieden, es muss also außer $p_1,...,p_k$ noch weitere Primzahlen geben. Über die Verteilung der Primzahlen (ihre ,,Dichte'') in $N$ gibt der berühmte Primzahlsatz Auskunft. Mit $\pi(x)$ bezeichnen wir die Anzahl der Primzahlen, die nicht größer als $x$ sind. Satz 4.32 Primzahlsatz: $lim_{x\rightarrow \infty} \frac{\pi(x)}{x\backslash ln\ x}= 1$ Das heißt, dass für große $x$ in $(x,2x]$ etwa $\frac{2x}{ln(2x)}-\frac{x}{ln\ x}\approx \frac{x}{ln\ x}$ Primzahlen zu erwarten sind. Die $n$-Bit-Zahlen bilden das Intervall $[2^{n-1} , 2n)$. Der Anteil der Primzahlen in diesem Intervall ist näherungsweise $\frac{2^{n-1}\ ln(2^{n-1})}{2^{n-1}}\approx \frac{1}{(ln\ 2)(n-1)}\approx 1,44/n$. Für $n\approx 2000$ ist der relative Anteil von Primzahlen im interessanten Zahlenbereich also $\approx 1,44/2000\approx 1/1400$. Er sinkt umgekehrt proportional zur Ziffernzahl. Eine schärfere Form des Primzahlsatzes ist folgende Aussage (wobei der Beweis Nichtspezialisten nicht zugänglich ist): $\frac{x}{ln\ x}(1+\frac{1}{ln\ x})\leq \pi(x)\leq \frac{x}{ln\ x}(1+\frac{1,2762}{ln\ x})$. Für $x\geq 500 000$ folgt daraus: $\frac{x}{ln\ x}< \pi(x)< 1, frac{x}{ln\ x}$. Daraus folgt, dass für $n\geq 20$ der Anteil der Primzahlen unter den n-Bit-Zahlen folgende Ungleichung erfüllt: $\frac{|\{p\in [2^{n-1}, 2^n)| \text{p is prime}\}|}{2^{n-1}} = \frac{\pi(2^n)-\pi(2^{n-1})}{2^{n-1}} \geq \frac{2^n\backslash (n\ ln\ 2)- 1,1*2^{n-1}\backslash ((n-1)ln\ 2)}{2^{n-1}}\geq \frac{2}{n\ ln\ 2}-\frac{1,1}{n\ ln\ 2}*\frac{n}{n-1}\geq \frac{6}{5n}$. Mit Hilfe eines Computeralgebraprogramms findet man heraus, dass die Ungleichung $|\{p\in [2^{n-1}, 2^n)|\text{ p is prime}\}|/2^{n-1} \geq 6 /(5n)$ auch für $9\leq n\leq 20$ gilt. (Für $n=8$ ist sie falsch.) Man kann sich also merken: für $n\geq 9$ ist der Anteil der Primzahlen an den n-Bit-Zahlen mindestens $\frac{6}{5n}$. \begin{tabular}{c} | Ziffernzahl $n$ | Dusart-Schranke $(\pi(2^n)-\pi(2^{n-1}))\backslash 2^{n-1}$ | für numerische untere Schranke \\\hline | $256$ | $\frac{6}{5*256}$ | $\geq \frac{1}{214}$ \\ | $512$ | $\frac{6}{5*512}$ | $\geq \frac{1}{427}$ \\ | $1024$ | $\frac{6}{5*1024}$ | $\geq\frac{1}{854}$ \\ | $2048$ | $\frac{6}{5*2048}$ | $\geq\frac{1}{1707}$ \end{tabular} Eine leichter zu beweisende Aussage der Art $\pi(2m)-\pi(m) = O(m/log\ m)$ ist die folgende: Satz 4.33 Ungleichung von Finsler: Für jede ganze Zahl $m\geq 2$ liegen im Intervall $(m, 2m]$ mindestens $m/(3\ ln(2m))$ Primzahlen: $\pi (2m)-\pi(m)\geq \frac{m}{3\ ln(2m)}$. Ein vollständiger, vergleichsweise einfacher Beweis für Satz 4.33 findet sich zum Beispiel in dem Lehrbuch ,,Elemente der Diskreten Mathematik: Zahlen und Zählen, Graphen und Verbände'' von Diekert, Kufleitner, Rosenberger (De Gruyter 2013). \subsection{Der Primzahltest von Miller und Rabin} In diesem Abschnitt lernen wir einen randomisierten Algorithmus kennen, der es erlaubt, zu einer gegebenen Zahl $N$ zu entscheiden, ob $N$ eine Primzahl ist oder nicht. Ein idealer Primzahltest sieht so aus: \begin{itemize*} \item Eingabe: Eine natürliche Zahl $N\geq 3$. \item Ausgabe: $0$, falls $N$ eine Primzahl ist; $1$, falls $N$ zusammengesetzt ist. \end{itemize*} Wozu braucht man Primzahltests? Zunächst ist die Frage ,,Ist $N$ eine Primzahl?'' eine grundlegende mathematisch interessante Fragestellung. Spätestens mit dem Siegeszug des RSA-Kryptosystems hat sich die Situation jedoch dahin entwickelt, dass man Algorithmen benötigt, die immer wieder neue vielziffrige Primzahlen (etwa mit 1000 oder 1500 Bits bzw. 301 oder 452 Dezimalziffern) bereitstellen können. Den Kern dieser Primzahlerzeugungs-Verfahren bildet ein Verfahren, das eine gegebene Zahl $N$ darauf testet, ob sie prim ist. Ein naiver Primzahltest (,,versuchsweise Division''), der dem brute-force-Paradigma folgt, findet durch direkte Division der Zahl $N$ durch $2,3,4,...,\lfloor\sqrt{N}\rfloor$ heraus, ob $N$ einen nichttrivialen Teiler hat. Man kann dieses Verfahren durch einige Tricks beschleunigen, aber die Rechenzeit wächst dennoch mit $O(\sqrt{N})$. Dies macht es für Zahlen mit mehr als $40$ Dezimalstellen praktisch undurchführbar, von Zahlen mit mehr als $100$ Dezimalstellen ganz zu schweigen. (Achtung: Damit wird nichts über den Zeitaufwand bei anderen Faktorisierungsalgorithmen gesagt. Es gibt andere, sehr fortgeschrittene Faktorisierungsalgorithmen, die bei entsprechendem Zeitaufwand und mit sehr leistungsstarken Rechnern auch noch mit $200$-stelligen Zahlen zurechtkommen. Für Information zu früheren und aktuelleren Faktorisierungserfolgen siehe z.B. \href{http://en.wikipedia.org/wiki/RSA_numbers}{Wikipedia RSA Numbers}. In diesem Abschnitt beschreiben wir den randomisierten Primzahltest von Miller-Rabin. Dabei handelt es sich um einen ,,Monte-Carlo-Algorithmus mit einseitigem Fehler''. Das heißt: Auf Eingaben $N$, die Primzahlen sind, wird immer $0$ ausgegeben; auf Eingaben $N$, die zusammengesetzt sind, gibt es eine gewisse (von $N$ abhängige) Wahrscheinlichkeit, dass die Ausgabe $0$, also falsch ist. Für kein zusammengesetztes $N$ ist diese Wahrscheinlichkeit größer als die ,,Fehlerschranke'' $\frac{1}{4}$. Wir beweisen nur die Fehlerschranke $\frac{1}{2}$. Im Beweis benutzen wir einfache zahlentheoretische Überlegungen. Eine herausragende Eigenschaft des Miller-Rabin-Tests ist seine Effizienz. Wir werden sehen, dass selbst bei Verwendung der Schulmethoden für Multiplikation und Division die Anzahl der Ziffernoperationen des Primzahltests nur $O((log\ N)^3)$ ist. Bemerkung: Der Miller-Rabin-Algorithmus stammt aus dem Jahr 1977; er folgte einem kurz vorher vorgestellten anderen randomisierten Primzahltest (Solovay-Strassen-Test). Für diesen und andere randomisierte Primzahltests (z.B. der ,,Strong Lucas Probable Prime Test'' oder der ,,Quadratic Frobenius Test'' von Grantham) sei auf die Literatur verwiesen. Im Jahr 2002 stellten Agarwal, Kayal und Saxena einen deterministischen Primzahltest mit polynomieller Rechenzeit vor. (Die Rechenzeit ist z.B. durch $O((log\ N)^{7,5})$ beschränkt.) Dieser Algorithmus stellte insofern einen gewaltigen Durchbruch dar, als er ein Jahrhunderte altes offenes Problem löste, nämlich die Frage nach einem effizienten deterministischen Verfahren für das Entscheidungsproblem ,,ist $N$ Primzahl oder zusammengesetzt''? Andererseits ist seine Laufzeit im Vergleich etwa zu dem hier diskutierten randomisierten Verfahren so hoch, dass nach wie vor die randomisierten Algorithmen benutzt werden, um für kryptographische Anwendungen Primzahlen zu erzeugen. Da gerade Zahlen leicht zu erkennen sind, beschränken wir im Folgenden unsere Überlegungen auf ungerade Zahlen $N\geq 3$. \subsubsection{Der Fermat-Test} Wir erinnern uns an Fakt 4.20, den Kleinen Satz von Fermat: Wenn $p$ eine Primzahl ist und $1\leq a < p$, dann gilt $a^{p-1} mod\ p=1$. Wir können diese Aussage dazu benutzen, um ,,Belege'' oder ,,Zertifikate'' oder ,,Zeugen'' dafür anzugeben, dass eine Zahl $N$ zusammengesetzt ist: Wenn wir eine Zahl $a$ mit $1\leq a < N$ finden, für die $a^{N-1} mod\ N\not=1$ gilt, dann ist $N$ definitiv keine Primzahl. Beispiel: Mit $N=15$ und $a=2$ rechnen wir: $2^{14}\equiv (2^4)^3 * 2^2 \equiv 16^3*4 \equiv 1*4\equiv 4 (mod\ 15)$. Also ist $2^{14} mod\ 15 = 4\not= 1$, also ist $15$ definitiv keine Primzahl. (Man beachte, dass wir keinen Faktor angeben müssen, um zu diesem Schluss zu kommen.) Definition 4.34: Sei $N\geq 3$ ungerade und zusammengesetzt. Eine Zahl $a\in\{1,...,N-1\}$ heißt F-Zeuge für $N$, wenn $a^{N-1} mod\ N\not= 1$ gilt. Eine Zahl $a\in\{1,...,N-1\}$ heißt F-Lügner für $N$, wenn $a^{N-1} mod\ N=1$ gilt. Die Menge der F-Lügner nennen wir $L^F_N$. Wir bemerken, dass ein F-Zeuge belegt, dass es Faktoren $k,l >1$ mit $N=k*l$ gibt, dass aber ein F-Zeuge nicht auf solche Faktoren hinweist oder sie beinhaltet. Das Finden von Faktoren wird von Primzahltests auch nicht verlangt und normalerweise auch nicht geleistet. Man sieht sofort, dass $1$ und $N-1$ immer F-Lügner sind: Es gilt $1^{N-1} mod\ N=1$ und $(N-1)^{N-1} \equiv (-1)^{N-1}=1 (mod\ N)$, weil $N-1$ gerade ist. Für jede zusammengesetzte Zahl $N$ gibt es mindestens einen F-Zeugen. Nach Fakt 4.19 gilt $\{1,...,N-1\}-\mathbb{Z}^*_N\not=\varnothing$, wenn $N$ zusammengesetzt ist. Lemma 4.35: Wenn $N$ zusammengesetzt ist, ist jedes $a\in\{1,...,N-1\}-\mathbb{Z}^*_N$ ein F-Zeuge. Beweis: Sei $d=ggT(a,N)>1$. Dann ist auch $a^{N-1}$ durch $d$ teilbar, also auch $a^{N-1}\ mod\ N=a^{N-1}- \lfloor a^{N-1}\backslash N\rfloor *N$. Daher ist $a^{N-1} mod\ N\not= 1$. Beispiel: Für $N=15$ und $a=6$ gilt $6^{14}\equiv 36^7\equiv 6^7 \equiv 36^3 * 6 \equiv 6^4 \equiv 6^2 \equiv 6\ (mod\ 15)$. Der Rest $6$ ist durch $ggT(6,15) = 3$ teilbar. Leider ist für manche zusammengesetzten Zahlen $N$ die Menge $\{1 ,...,N-1\}-\mathbb{Z}^*_N$ äußerst dünn. Wenn zum Beispiel $N=pq$ für zwei Primzahlen $p$ und $q$ ist, dann gilt $ggT(a,N)> 1$ genau dann wenn $p$ oder $q$ ein Teiler von $a$ ist. Es gibt genau $p+q-2$ solche Zahlen $a$ in $\{ 1 ,...,N-1\}$, was gegenüber $N$ sehr klein ist, wenn $p$ und $q$ annähernd gleich groß sind. Um eine gute Chance zu haben, F-Zeugen zu finden, sollte es also mehr als nur die in $\{1 ,...,N-1\}-\mathbb{Z}^*_N$ geben. Beispiel: $N=91 = 7*13$. Es gibt 18 Vielfache von 7 und 13 (für größere $p$ und $q$ wird der Anteil dieser offensichtlichen F-Zeugen noch kleiner sein), und daneben weitere $36$ F-Zeugen und $36$ F-Lügner in $\{1 , 2 ,..., 90\}$. In diesem Beispiel gibt es um einiges mehr F-Zeugen als F-Lügner. Wenn dies für alle zusammengesetzten Zahlen $N$ der Fall wäre, wäre es eine elegante randomisierte Strategie, einfach zufällig nach F-Zeugen zu suchen. Dies führt zu unserem ersten Versuch für einen randomisierten Primzahltest. Tabelle 3: F-Zeugen und F-Lügner für $N=91= 7*13$. Es gibt $36$ F-Lügner und $36$ F-Zeugen in $\mathbb{Z}^*_{91}$. Wir wissen nach Lemma 4.35, dass alle 18 Vielfachen von $7$ und $13$ F-Zeugen sind. \begin{tabular}{c} | F-Zeugen in $\{ 1 ,..., 90\}-\mathbb{Z}^*_{91}$: | 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84; 13, 26, 39, 52, 65, 78 \\ | F-Lügner: | 1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88, 90 \\ | F-Zeugen in $\mathbb{Z}^*_{91}$ : | 2, 5, 6, 8, 11, 15, 18, 19, 20, 24, 31, 32, 33, 34, 37, 41, 44, 45, 46, 47, 50, 54, 57, 58, 59, 60, 67, 71, 72, 73, 76, 80, 83, 85, 86, 89 \end{tabular} Algorithmus 4.4: Fermat-Test \begin{itemize*} \item Eingabe: Ungerade Zahl $N\geq 3$ \item Methode: \begin{enumerate*} \item Wähle $a$ zufällig aus $\{1,...,N-1\}$ \item if $a^{N-1}\ mod\ N\not= 1$ then return $1$ else return $0$ \end{enumerate*} \end{itemize*} Die Laufzeitanalyse liegt auf der Hand: Der teuerste Teil ist die Berechnung der Potenz $a^{N-1}\ mod\ N$ durch schnelle Exponentiation, die nach den Ergebnissen von Lemma 4.14 $O(log\ N)$ arithmetische Operationen und $O((log\ N)^3)$ Ziffernoperationen benötigt. Weiter ist es klar, dass der Algorithmus einen F-Zeugen gefunden hat, wenn er ,,1'' ausgibt, dass in diesem Fall also $N$ zusammengesetzt sein muss. Umgekehrt ausgedrückt: Wenn $N$ eine Primzahl ist, gibt der Fermat-Test garantiert ,,0'' aus. Für $N=91$ wird das falsche Ergebnis $0$ ausgegeben, wenn als $a$ einer der 36 F-Lügner gewählt wird. Die Wahrscheinlichkeit hierfür ist $\frac{36}{90} =\frac{2}{5} = 0,4$. Für viele zusammengesetzte Zahlen $N$ gibt es reichlich F-Zeugen, so dass der Fermat-Test für diese $N$ mit konstanter Wahrscheinlichkeit das korrekte Ergebnis liefert. Wir analysieren das Verhalten des Fermat-Tests für solche ,,gutmütigen'' Eingabezahlen $N$ (für die $N=91$ ein typisches Beispiel ist). Satz 4.36: Sei $N\geq 9$ eine ungerade zusammengesetzte Zahl. Wenn es mindestens einen F-Zeugen $b\in\mathbb{Z}^*_N$ gibt, dann liefert der Fermat-Test auf Eingabe $N$ mit Wahrscheinlichkeit größer als $\frac{1}{2}$ die korrekte Antwort ,,1''. Beweis: Sei $b\in\mathbb{Z}^*_N$ ein F-Zeuge. Betrachte die Funktiong $b:L^F_N\rightarrow\mathbb{Z}^*_N$, die den F-Lügner $a$ auf $g_b(a) =ba\ mod\ N$ abbildet. Wie im Beweis von Fakt 4.20 sieht man, dass $g_b$ injektiv ist. Weiter ist $g_b(a)$ für jedes $a\in L^F_N$ ein F-Zeuge: $(ba\ mod\ N)^{N-1}\ mod\ N= (b^{N-1}\ mod\ N)(a^{N-1}\ mod\ N) =b^{N-1}\ mod\ N\not= 1$. Wir können also jedem F-Lügner $a$ einen eigenen F-Zeugen $g_b(a)$ in $\mathbb{Z}^*_N$ zuordnen. Daraus folgt, dass es in $\mathbb{Z}^*_N$ mindestens so viele F-Zeugen wie F-Lügner gibt. Mit Lemma 4.35 ergibt sich, dass $\{1,...,N-1\}$ mehr F-Zeugen als F-Lügner enthält. Daher ist die Wahrscheinlichkeit, dass die im Fermat-Test zufällig gewählte Zahl $a$ ein F-Lügner ist, kleiner als $\frac{1}{2}$. Eine Fehlerwahrscheinlichkeit in der Nähe von $\frac{1}{2}$ ist natürlich viel zu groß. Wir verringern die Fehlerschranke durch wiederholte Ausführung des Fermat-Tests. Algorithmus 4.5: Iterierter Fermat-Test \begin{itemize*} \item Eingabe: Ungerade Zahl $N\geq 3$, eine Zahl $l\geq 1$ \item Methode: \begin{enumerate*} \item repeat $l$ times \begin{itemize*} \item $a\leftarrow$ ein zufälliges Element von $\{1 ,...,N-1\}$ \item if $a^{N-1}\ mod\ N\not= 1$ then return $1$ \end{itemize*} \item return 0 \end{enumerate*} \end{itemize*} Wenn die Ausgabe $1$ ist, hat der Algorithmus einen F-Zeugen für $N$ gefunden, also ist $N$ zusammengesetzt. D.h.: Wenn $N$ eine Primzahl ist, ist die Ausgabe $0$. Andererseits: Wenn $N$ zusammengesetzt ist, und es mindestens einen F-Zeugen $b\in\mathbb{Z}^*_N$ gibt, dann ist nach Satz 4.36 die Wahrscheinlichkeit für die falsche Ausgabe ,,0'' höchstens $(\frac{1}{2})^l= 2^{-l}$. Indem wir $l$ genügend groß wählen, können wir die Fehlerwahrscheinlichkeit so klein wie gewünscht einstellen. Wenn es darum geht, aus einem genügend großen Bereich zufällig gewählte Zahlen darauf zu testen, ob es sich um eine Primzahl handelt, dann ist der Fermat-Test (in Kombination mit dem Testen auf kleine Teiler, etwa alle Primzahlen unter 1000) allem Anschein nach eine sehr effiziente und zuverlässige Methode. Dies wird durch empirische Resultate nahegelegt. Wenn man allerdingsüber die Herkunft der zu testenden Zahl $N$ keine Information hat und eventuell damit rechnen muss, dass jemand (ein ,,Gegenspieler'') absichtlich eine besonders schwierige Eingabe vorlegt, dann stößt der Fermat-Test an eine Grenze. Es gibt nämlich ,,widerspenstige'' zusammengesetzte Zahlen, denen man mit diesem Test nicht beikommen kann, weil alle Elemente von $\mathbb{Z}^*_N$ F-Lügner sind. Mit diesen befasst sich der folgende Abschnitt. \subsubsection{Carmichael-Zahlen} Definition 4.37: Eine ungerade zusammengesetzte Zahl $N$ heißt eine Carmichael-Zahl, wenn für alle $a\in\mathbb{Z}^*_N$ die Gleichung $a^{N-1}\ mod\ N= 1$ gilt. Die kleinste Carmichael-Zahl ist $561 = 3* 11 *17$. Weitere kleine Carmichael-Zahlen sind $1105 = 5* 13 *17$ und $1729 = 7* 13 *19$. Erst im Jahr 1994 wurde bewiesen, dass es unendlich viele Carmichael-Zahlen gibt, genauer: Wenn $x$ genügend groß ist, dann gibt es in $\{N\in\mathbb{N}| N\leq x\}$ mehr als $x^{2/7}$ Carmichael-Zahlen. Die aktuell beste bekannte untere Schranke ist $x^{1/3}$. Von Erdös (1956) stammt die obere Schranke $x*exp(\frac{-c\ ln\ x\ ln\ ln\ ln\ x}{ln\ ln\ x})$, für eine Konstante $c>0$, die zeigt, dass Carmichael-Zahlen viel seltener als Primzahlen sind. Wenn wir dem Fermat-Test eine Carmichael-Zahl $N$ als Eingabe geben, ist die Wahrscheinlichkeit für die falsche Antwort $0$ nach Lemma 4.29 genau $\frac{\varphi(N)}{N-1} > \frac{\varphi(N)}{N} = \prod_{p\ prim, p\ teilt\ N} (1 -\frac{1}{p})> 1 -\sum_{p\ prim, p\ teilt\ N} \frac{1}{p}$. Diese Wahrscheinlichkeit liegt nahe an $1$, wenn $N$ nur wenige und relativ große Primfaktoren hat. An solchen Carmichael-Zahlen besteht etwa im Bereich der Zahlen im Bereich $[10^{17} , 10^{18} ]$ kein Mangel, wie ein Blick in entsprechende Tabellen zeigt. Zum Beispiel ist $N=925619721362375041 = 425681* 1277041 *1702721$ eine 18-ziffrige Carmichael-Zahl mit $\varphi(N)/N > 0.999996$. Der Wiederholungstrick zur Wahrscheinlichkeitsverbesserung hilft hier leider auch nicht, denn wenn etwa $p_0$ der kleinste Primfaktor von $N$ ist, und $N$ nur $3$ oder $4$ Faktoren hat, dann sind $\Omega(p_0)$ Wiederholungen nötig, um die Fehlerwahrscheinlichkeit auf $\frac{1}{2}$ zu drücken. Sobald $p_0$ mehr als 30 Dezimalstellen hat, ist dies undurchführbar. Für einen zuverlässigen, effizienten Primzahltest, der für alle Eingabezahlen funktioniert, müssen wir über den Fermat-Test hinausgehen. Interessanterweise ist dies praktisch ohne Effizienzverlust möglich. Für spätere Benutzung stellen wir noch eine Hilfsaussage über Carmichael-Zahlen bereit. Lemma 4.38: Wenn $N$ eine Carmichael-Zahl ist, dann ist $N$ keine Primzahlpotenz. Beweis: Wir beweisen die Kontraposition: Wenn $N=p^l$ für eine ungerade Primzahl $p$ und einen Exponenten $l\geq 2$ ist, dann ist $N$ keine Carmichael-Zahl. Dazu genügt es, eine Zahl $a\in\mathbb{Z}^*_N$ anzugeben, so dass $a^{N-1}\ mod\ N\not= 1$ ist. Wir definieren: $a:=p^{l-1} + 1$. (Wenn z.B. $p=7$ und $l=3$ ist, ist $N=343$ und $a=49+1=50$.) Man sieht sofort, dass $a0$. Wir wählen $d=a$. Dann gilt (i), weil $a$ Teiler von $a$ und von 0 ist, und es gilt (ii), weil jeder gemeinsame Teiler von $a$ und 0 auf jeden Fall Teiler von $a$ ist. \item *Induktionsschritt*: $b>0$. Setze $q:=a\ div\ b$ und $r:=a-qb=a\ mod\ b$ und $(a',b'):=(b,r)$. Dann ist $b'=r < b=a'$. Nun haben $a$ und $b$ genau dieselben gemeinsamen Teiler wie $a'$ und $b'$. (Aus $t|a$ und $t|b$ folgt $t|(a-qb)$, also $t|a'$, und aus $t|a'$ und $t|b'$ folgt $t|r+qb$, also $t|a$.) Nach I.V. existiert $d= ggT(a',b')$, und dieses $d$ ist dann auch größter gemeinsamer Teiler von $a$ und $b$. \end{itemize*} \section{Asymmetrische Verschlüsselung: RSA \& Co.} \subsection{Das RSA-Kryptosystem (,,Vorlesungs-Version'')} RSA: Erfunden von Ronald L. Rivest, Adi Shamir und Leonard Adleman, 1977. Ein ähnliches Verfahren wurde (von J. H. Ellis, C. C. Cocks und M. J. Williamson) bereits Anfang der 1970er Jahre in den Government Communications Headquarters, der Kryptologie-Abteilung des britischen Geheimdienstes, entwickelt, aber nicht veröffentlicht. Vorsicht: In der hier zunächst vorgestellten einfachen/naiven Version ist RSA unsicher. Es müssen Modifikationen und Einschränkungen vorgenommen werden, um ein sicheres Verfahren zu erhalten. Gute Referenz hierfür: Baumann, Franz, Pfitzmann, Kryptographische Systeme, Springer Vieweg 2014, S. 231ff. Wir betrachten ein einfaches Kommunikationsszenario. Die Teilnehmer sind Alice und Bob. Alice möchte an Bob eine Nachricht schicken. Dies soll über einen offen zugänglichen Kanal (E-Mail, ein Webportal) geschehen. Dieser Kanal wird von Eva mitgelesen. Alice und Bob wollen vermeiden, dass Eva den Inhalt der Nachricht erfährt. Wenn auch Bob an Alice Nachrichten schicken möchte, müssen die Aktionen auch mit vertauschten Rollen ausgeführt werden. Die Menge $X$ der möglichen Nachrichten kann als Teilmenge von $\{0,1\}^*$ aufgefasst werden. Wir möchten vermeiden, dass sich Alice und Bob vor der Kommunikation auf einen gemeinsamen Schlüssel einigen müssen. Stattdessen wird ein Schlüsselpaar $(k,\hat{k})$ verwendet. Die erste Komponente $k$ heißt der öffentliche Schlüssel von Bob und wird von Bob allen zugänglich gemacht, etwa über seine Webseite oder als Anhang von E-Mails. Die zweite Komponente $\hat{k}$ heißt der private Schlüssel von Bob und ist nur ihm bekannt. Die Menge der Schlüsselpaare $(k,\hat{k})$, die zusammengehören, nennen wir die Schlüsselmenge $K$. Definition 5.1: Ein Public-Key-Kryptosystem $(X,Y,K,E,D)$ hat 5 Komponenten: \begin{itemize*} \item Klartextmenge $X$ (endlich), \item Chiffretextmenge $Y$ (endlich), \item Schlüsselmenge $K$, wobei $K\supseteq K_{pub} \times K_{priv}$ für Mengen $K_{pub}$ und $K_{priv}$, \item Verschlüsselungsfunktion $E:X\times K_{pub} \rightarrow Y$, \item Entschlüsselungsfunktion $D:Y\times K_{priv} \rightarrow X$, \item wobei die folgende Dechiffrierbedingung gilt: $D(E(x,k), \hat{k}) =x$, für alle $x\in X,(k,\hat{k})\in K$. \end{itemize*} Um ein solches System benutzen zu können, benötigt man noch ein Verfahren, um Schlüsselpaare $(k,\hat{k})$ zu erzeugen. Dieses Verfahren heißt $G$, ist randomisiert und wird von Bob angestoßen, dem auch das Ergebnis mitgeteilt wird. Dies ist notwendig, da die Ausgabe von $G$ den geheimen Schlüsselteil $\hat{k}$ enthält. Nach Erzeugung des Paars $(k,\hat{k})$ gibt Bob $k$ bekannt und speichert $\hat{k}$ geheim ab. Wenn Alice Bob eine Nachricht $x\in X$ schicken will, berechnet sie $y=E(x,k)$ und schickt $y$. Wenn Bob einen Chiffretext $y$ empfängt, berechnet er $z=D(y,\hat{k})$. Nach der Dechiffrierbedingung ist dies wieder $x$. Das RSA-System in seiner puren Form benutzt Klartext- und Chiffretextmenge $X=Y=[N]$, für eine feste Zahl $N$. Ab hier nehmen wir stets an, dass der Klartext $x$ selbst eine Zahl in $X = X_N= [N]$ ist. Dann ist $Y = Y_N= [N]$ die Menge der möglichen Chiffretexte. Das (randomisierte) Verfahren $G$ zur Erzeugung von Schlüsselpaaren $(k,\hat{k})$ aus $K_{pub} \times K_{priv}$ hat üblicherweise einen Parameter $l$, die Schlüssellänge. Den Wertebereich von $G$, also die Menge aller möglichen Schlüsselpaare $(k,\hat{k})$, wollen wir $K$ nennen. Dabei ist $k$ Bobs ,,öffentlicher Schlüssel'', der öffentlich zugänglich ist (zum Beispiel in einem allgemein zugänglichen ,,Schlüsselbuch'' oder auf Bobs Webseite) und $\hat{k}$ ist sein ,,privater Schlüssel'', den nur er kennt. Alice (und andere Teilnehmer, die Bob eine Nachricht schicken wollen) verwendet $k$ zur Verschlüsselung, Bob verwendet $\hat{k}$ zur Entschlüsselung. Es gibt einen (eventuell randomisierten) Verschlüsselungsalgorithmus $E$, der aus $x\in X$ und dem öffentlichen Schlüssel $k$ den Chiffretext $y\in Y$ berechnet, sowie einen (deterministischen) Entschlüsselungsalgorithmus $D$, der aus $y\in Y$ und dem privaten Schlüssel $\hat{k}$ den entschlüsselten Text $z\in X$ berechnet. Abstrakt haben wir zwei Funktionen $E: (x,k)\rightarrow y\in Y$, wobei $x\in X$ und $k$ erste Komponente eines Schlüsselpaars $(k,\hat{k})\in K$ mit zugeordneter Zahl $N$ ist, und $D:(y,\hat{k})\rightarrow z\in X$, wobei $y\in Y$ und $\hat{k}$ zweite Komponente eines Schlüsselpaars $(k,\hat{k})\in K$ mit zugeordneter Zahl $N$ ist. Typischerweise sind die Funktionen $E$ und $D$ allgemein bekannt; das einzige Geheimnis im Verfahren steckt im privaten Schlüssel $\hat{k}$. Korrektheit/Dechiffrierbedingung: Es gilt: $D(E(x,k), \hat{k}) =x$, für $x\in X$ und $(k,\hat{k})\in K$. Sicherheit: Es soll verhindert werden, dass Eva aus dem Chiffretext $y$ und dem öffentlichen Schlüssel $k$ ,,relevante Informationen''über den Klartext $x$ gewinnen kann. Hierbei wird üblicherweise angenommen, dass sie nur ,,begrenzten Rechenaufwand'' betreiben kann. \subsubsection{Schlüsselerzeugung} Wir beschreiben den Erzeugungsprozess $G$. Dieser Vorgang wird von Bob selbst oder einer Sicherheitsagentur (,,trust center'') durchgefuhrt. Die Schlüssellänge ist festzulegen (etwa $l= 1024, 2048$ oder $4096$ Bits). Danach werden zwei (zufällige, verschiedene) Primzahlen $p$ und $q$ bestimmt, deren Bitlänge die Hälfte der Schlüssellänge ist. Hierzu kann man im Prinzip wie in Abschnitt 4.7 beschrieben vorgehen. Nun wird das Produkt $N=pq$ berechnet. Die Zahl $N$ hat $l$ oder $l-1$ Bits. Weiter wird $\varphi(N) = (p-1)(q-1)$ berechnet. Es wird eine Zahl $e\in\{3,...,\varphi(N)-1\}$ mit $ggT(e,\varphi(N)) = 1$ gewählt. (Überprüfung mittels des erweiterten Euklidischen Algorithmus (Algorithmus 4.2), Rechenzeit $O(l^3)$.) Dann wird das multiplikative Inverse $d<\varphi(N) modulo\ \varphi(N)$ von $e$ bestimmt, so dass also $ed\ mod\ \varphi(N) = 1$ gilt. (Man beachte, dass nur ungerade $e$ in Frage kommen, weil $\varphi(N)$ gerade ist. Man weiß, dass die Anzahl der geeigneten Werte $e$ mindestens $\frac{\varphi(N)}{log(\varphi(N))}$ ist, so dass die erwartete Anzahl von Versuchen $O(log(\varphi(N)))=O(logN)$ ist.) Bob erhält aus seiner Rechnung $N$, $e$ und $d$. Aus diesen wird das Schlüsselpaar $(k,\hat{k})$ gebildet: \begin{itemize*} \item Der öffentliche Schlüssel $k$ ist das Paar $(N,e)$. Dieser wird bekanntgegeben. \item Der geheime Schlüssel $\hat{k}$ ist $(N,d)$. (Natürlich ist nur der Teil $d$ wirklich geheim.) \end{itemize*} Der erwartete Berechnungsaufwand für die Schlüsselerzeugung ist $O((log\ N)^4) =O(l^4)$, weil dies die Kosten der Primzahlerzeugung sind (siehe Abschnitt 4.7); die Kosten für das Finden von $e$ sind geringer. \subsubsection{Verschlüsselung} \begin{itemize*} \item Gegeben: Klartext $x$. \item Benötigt: Öffentlicher Schlüssel $k= (N,e)$. \end{itemize*} Verschlüsselung von $x\in X= [N]: y=E(x,(N,e)) :=x^e\ mod\ N$. (Zu berechnen mit schneller Exponentiation, Rechenzeit $O((log\ N)^3) =O(l^3)$.) \subsubsection{Entschlüsselung} \begin{itemize*} \item Gegeben: Chiffretext $y$. \item Benötigt: Privater Schlüssel $\hat{k}= (N,d)$. \end{itemize*} $z=D(y,(N,d)) :=y^d\ mod\ N$. (Zu berechnen mit schneller Exponentiation, Rechenzeit $O((log\ N)^3) =O(l^3)$.) Nach den Potenzrechenregeln, die auch für die modulare Arithmetik gelten, ist $z=(x^e\ mod\ N)^d\ mod\ N=x^{ed}\ mod\ N$. Die Korrektheit der Entschlüsselung beruht auf folgendem Satz. Satz 5.2: Korrektheit/Dechiffrierbedingung von RSA: Wenn $ed\ mod\ \varphi(N) = 1$ gilt, dann haben wir $x^{ed}\ mod\ N=x$, für alle $x\in [N]$. Beweis: Weil $x$ und $x^{ed}\ mod\ N$ beide in $[N]$ liegen, also der Betrag ihrer Differenz kleiner als $N$ ist, genügt es zu zeigen, dass $x^{ed} \equiv x(mod\ N)$ gilt, d.h. dass $N$ Teiler von $x^{ed}-x$ ist. Dies weisen wir im Folgenden nach. Betrachte die Primfaktoren $p$ und $q$ von $N$. Da $ed\equiv 1 (mod\ \varphi(N))$ und $\varphi(N) = (p-1)(q-1)$ gilt, haben wir $ed=k(p-1)(q-1) + 1$ für eine Zahl $k\in\mathbb{N}$, also $x^{ed}-x= (x^{k(p-1)(q-1)} -1)*x$. Behauptung: $p$ teilt $x^{ed}-x$. - Wenn $x$ durch $p$ teilbar ist, ist dies klar. Wir können also annehmen, dass $p$ kein Teiler von $x$ ist, dass also $x$ und $p$ teilerfremd sind. Nach dem kleinen Satz von Fermat (Fakt 4.27) gilt $x^{p-1}\ mod\ p= 1$, also auch $x^{k(p-1)(q-1)}\ mod\ p= (x^{(p-1)})^{k(q-1)}\ mod\ p= 1$. Dies bedeutet, dass $p$ ein Teiler von $x^{k(p-1)(q-1)}-1$ ist, also auch ein Teiler von $x^{ed}-x$. Die Behauptung gilt naturlich genauso für $q$: Auch $q$ ist ein Teiler von $x^{ed}-x$. Da $p$ und $q$ teilerfremd sind, folgt aus Fakt 4.8, dass $N=pq$ Teiler von $x^{ed}-x$ ist, wie gewünscht. Beispiel: \begin{itemize*} \item Schlüsselerzeugung: $N= 55 = 5*11$. \item $\varphi(N) = 4*10 = 40$. \item $e= 3, ggT(3,40) = 1, d=e^{-1}\ mod\ 40 = 27$, weil $3*27 = 81\equiv 1 (mod\ 40)$ gilt. \item Also: $k= (55,3)$, $\hat{k}= (55,27)$. \item Sei der Klartext $x=9$ gegeben. \item Verschlüsselung: $y= 9^3\ mod\ 55 = 729\ mod\ 55 = 14$. \item Entschlüsselung: Wir rechnen modulo 55: $y^{27}\equiv (14^2 * 14)^9 \equiv (31*14)^9 \equiv 434^9 \equiv ((-6)^3)^3 \equiv 4^3 \equiv 64 \equiv 9\ (mod\ 55)$. \end{itemize*} RSA, unsichere Version, insgesamt \begin{itemize*} \item Bob erzeugt einen Schlüsselsatz $(k, \hat{k}) = ((N,e),(N,d))$. \item Er veröffentlicht $(N,e)$ und hält $d$ geheim. \item Wenn Alice $(x_1,...,x_r)\in [N]^r$ an Bob schicken will, verschlüsselt sie $y_i:=x^e_i\ mod\ N$, für $i=1,...,r$, und sendet $(y_1,...,y_r)$ an Bob. \item Dieser entschlüsselt $z_i:=y^d_i\ mod\ N$, für $i=1,...,r$, und erhält $(z_1,...,z_r) = (x_1,...,x_r)$. \end{itemize*} \subsection{Asymmetrische Kryptoschemen, Sicherheitsbegriff} Wir betrachten die Situation asymmetrisch verschlüsselter Kommunikation allgemein, also für beliebig lange Klartexte, und formulieren ein Sicherheitskonzept. Der Einfachheit halber nehmen wir als Menge $Y$ der Chiffretexte die Menge aller Binärstrings an. Szenarium 4: Alice möchte Bob vertrauliche Nachrichten beliebiger Länge über einen abhörbaren Übertragungsweg zukommen lassen. Alice und Bob besitzen keinen gemeinsamen Schlüssel. \subsubsection{Asymmetrische Kryptoschemen} Definition 5.3: Ein asymmetrisches Kryptoschema ist ein Tupel $S= (X,K,G,E,D)$, wobei \begin{itemize*} \item $X,K\supseteq K_{pub} \times K_{priv}$ Mengen, \item $G():K_{pub} \times K_{priv}$ ein randomisierter Algorithmus, \item $E(x:X,k:K_{pub}):\{0,1\}^*$ ein randomisierter Algorithmus und \item $D(y:\{0,1\}^*,k:K_{priv}):\{0,1\}^*$ ein deterministischer Algorithmus sind, \item so dass gelten \item die (erwartete) Laufzeit von $?$ ist beschränkt durch eine Konstante, \item die Laufzeiten von $?$ und $D$ sind polynomiell beschränkt in der Länge von $x$ bzw. $y$, \item für jedes $x\in X,k\in K_{pub}$, jede Ausgabe $(k,\hat{k})$ von $?$ und jedes $m\in\{0,1\}^{p(|x|)}$ (die Ausgänge der flip-Anweisungen in $E$, für ein Polynom $p(n)$) gilt: $D(E^m (x,k), \hat{k}) =x$. \end{itemize*} Begriffe \begin{itemize*} \item Die Elemente von X heißen ,,Klartexte'', die Menge der ,,Chiffretexte'' ist $\{0,1\}^*$. \item Die Elemente von $K_{pub}$ heißen ,,Öffentliche Schlüssel'', die von $K_{priv}$ ,,private Schlüssel'', mit $K\supseteq K_{pub} \times K_{priv}$ bezeichnen wir die Menge der Schlüsselpaare, die $G$ möglicherweise ausgibt. \item $G$ ist der ,,Schlüsselgenerierungsalgorithmus''. Er hat im Prinzip kein Argument, eventuell gibt es verschiedene Varianten, die von einem ,,Sicherheitsparameter'' $l$ abhängen. \item $E$ ist der ,,Verschlüsselungs-'' und $D$ der ,,Entschlüsselungsalgorithmus''. \end{itemize*} Beispiel: Die Erweiterung des RSA-Schemas auf Strings beliebiger Länge durch Anwendung auf Blöcke der Länge $w\leq log\ N$, wie oben beschrieben, liefert ein Kryptoschema. Die Frage ist, wie gut dieses Kryptoschema ist. \subsubsection{Sicherheit von asymmetrischen Kryptoschemen} Definition 5.4: Ein Angreifer $A$ auf ein asymmetrisches Kryptoschema $S= (X,K,G,E,D)$ ist ein Paar zufallsgesteuerter Algorithmen $AF(k:K_{pub}):(\{0,1\}\times\{0,1\})+\times V$, $AG(v:V,k:K_{pub}, y:\{0,1\}^*) :\{0,1\}$ Die Idee ist wie folgt: Der Finder $AF$ bekommt einen öffentlichen Schlüssel $k$. Daraus berechnet er zwei verschiedene Klartexte $(z_0,z_1)$ gleicher Länge und ,,Notizen'' $v\in V$. Danach wird zufällig $z_0$ oder $z_1$ zu $y$ verschlüsselt. Im zweiten Schritt verwendet der Rater $AG$ die Zwischeninformation $v$, den öffentlichen Schlüssel $k$ und die ,,Probe'' $y$, um zu bestimmen, ob $z_0$ oder $z_1$ verschlüsselt wurde. Definition 5.5: Sei $S=(X,K,G,E,D)$ ein asymmetrisches Kryptoschema und $A=(AF,AG)$ ein Angreifer. Das zugehörige Experiment oder Spiel ist der folgende Algorithmus $G^S_A:\{0,1\}$: \begin{enumerate*} \item $(k,\hat{k})\leftarrow G()$ (ein Schlüsselpaar des Kryptoschemas $S$ wird gewählt) \item $(z_0,z_1,v)\leftarrow AF(k)$ (der Finder berechnet ein Paar von Klartexten gleicher Länge, von denen er annimmt, ihre Chiffretexte unterscheiden zu können) \item $b\leftarrow flip()$ und $y\leftarrow E(z_b,k)$ (einer der Klartexte wird zuyverschlüsselt) \item $b'\leftarrow AG(v,k,y)$ (der Rater versucht herauszubekommen, ob $z_0$ oder $z_1$ verschlüsselt wurde) \item falls $b=b'$, so gib $1$ zurück, sonst $0$. \begin{itemize*} \item Das verkürzte Experiment oder Spiel $S^S_A$ gibt im 5. Schritt einfach $b'$ aus. \end{itemize*} \end{enumerate*} Dann ist $Pr(G^S_A= 1)$ die Wahrscheinlichkeit dafür, dass der Angreifer $A$ den korrekten Klartext erkennt. Man kann jetzt wie in Abschnitt 2.4 (Sicherheit von $l$-Blockkryptosystemen) den Vorteil $adv(A,S) = 2 Pr(G^S_A = 1)- 1$, den ,,Erfolg'' $suc(A,S) = Pr(G^S_A\langle b = 1\rangle = 1)$ und den ,,Misserfolg'' $fail(A,S) =Pr(G^S_A\langle b= 0\rangle = 1)$ definieren. Lemma 2.16 gilt dann wörtlich. Beispiel 5.6: Sei $S=(X,K,G,E,D)$ ein asymmetrisches Kryptoschema, in dem der Verschlüsselungsalgorithmus $E$ deterministisch ist. Wir betrachten den folgenden Angreifer $A$ mit $V=\{0,1\}^*$. Seien $z_0$ und $z_1$ verschiedene Elemente von $X$: \begin{itemize*} \item $AF(k:K_{pub}) : (\{0,1\}\times\{0,1\})^+\times V$ \item $v\leftarrow E(z_0,k);return(z_0,z_1,v)$ \item $AG(v:V,k:K_{pub},y:\{0,1\}^*):\{0,1\}$ \item if $v=y$ then return 0 else return 1. \item Im Ablauf des Spiels $G^S_A$ wird der Rater $AG$ also mit $E(z_0,k)$ oder mit $E(z_1,k)$ gestartet. Wegen $E(z_0,k)\not=E(z_1,k)$ gilt $Pr(G^S_A=1)=1$, d.h. $adv(A,S)=1$. \end{itemize*} Dieses Beispiel lässt sich verallgemeinern: Lemma 5.7: Für jedes deterministische asymmetrische Kryptoschema $S$ gibt es einen Angreifer $A$ mit $adv(A,S) = 1$. Definition 5.8: Sei $t\in\mathbb{N}$, $A$ ein Angreifer auf ein asymmetrisches Kryptoschema $S$. Dann heißt $A$ $t$-beschränkt, wenn die Laufzeit des Experiments $G^S_A$ durch $t$ beschränkt ist. Sei $\epsilon >0$. Dann heißt $S(t,\epsilon)$-sicher, wenn für jeden $t$-beschränkten Angreifer $A$ gilt $adv(A,S)\leq \epsilon$. Nach obigem Lemma gibt es für jedes deterministische asymmetrische Kryptoschema $S$ eine kleine Konstante $t$, so dass $S$ für kein $\epsilon >0 (t,\epsilon)$-sicher ist. Da die Verschlüsselung von RSA deterministisch ist, ist dieses Verfahren nach Lemma 5.7 nicht sicher. Zur Übung entwerfe man einen Angreifer $A$ gegen das RSA-System für die Situation, wo die Klartexte $(x_1,x_2)$ nur aus zwei Blöcken in $[N]$ bestehen. Dabei soll $A$ das Spiel mit Wahrscheinlichkeit $1$ gewinnen und die Notizenmenge $V$ soll trivial sein, also $V=\{0\}$, so dass $A$ sich gar keine Notizen machen kann. Betrachten wir nun konkret das RSA-System mit nur einem Block, also $X=[N]$. Kann Eva aus Kenntnis von $y=x^e\ mod\ N$, $e$ und $N$ irgendeine konkrete Information über $x$ ermitteln? Definition 5.9: \begin{enumerate*} \item Das ,,Legendre-Symbol'' gibt an, ob $a\in\mathbb{Z}$ modulo einer Primzahl $p$ ein Quadrat ist. Für $p>2$ prim und $a\in\mathbb{Z}$ setze $L_p(a) =\begin{cases} 0 \quad\text{ falls } p|a \\ 1 \quad\text{ falls } p\not|a, \exists b:b^2 \equiv a (mod\ p) \\ -1 \quad\text{ falls } p\not|a, \lnot\exists b:b^2 \equiv a (mod\ p)\end{cases}$. \item Das ,,Jacobi-Symbol'' verallgemeinert dies auf Moduli $N$, die nicht notwendig Primzahlen sind. Für $N>2$ ungerade mit Primzahlzerlegung $N=\prod_{1\leq i\leq r} p^{alpha_i}_i$ und $a\in\mathbb{Z}$ setze $J_N(a) =\prod_{1 \leq i\leq r} L_{p_i}(a)^{\alpha_i}$ \end{enumerate*} Beobachtungen und Beispiele: \begin{itemize*} \item Weil $4^2\ mod\ 7 = 2$, gilt $L_7(2) = 1$. Weiter gilt $L_7(21) = 0$ und $L_7(5) =-1$, weil $1,2,4$ die einzigen Quadrate modulo $7$ sind. \item $J_N(a) = 0$ genau dann, wenn $ggT(a,N)>1$. \item Wenn $p\not|a$ und $p$ ist ein Primfaktor, der in $N$ mit geradem Exponenten vorkommt, dann ist der Beitrag von $p$ zu $J_N(a)$ der Faktor 1, spielt also keine Rolle. \item Wenn $ggT(a,N) = 1$, dann ist $J_N(a) = (-1)^{\#}\{i\leq r|\text{a ist Nichtquadrat modulo } p_i\}$. \end{itemize*} Das Legendre-Symbol ist leicht mit schneller modularer Exponentiation zu berechnen. Fakt 5.10 Euler-Kriterium: $L_p(a) =a^{(p-1)/ 2}mod\ p$ für alle $a\in\mathbb{Z}$ und Primzahlen $p>2$. Überraschenderweise lässt sich auch das Jacobi-Symbol $J_N(a)$ effizient berechnen, selbst wenn man die Primzahlzerlegung von $N$ nicht kennt. Fakt 5.11: Für $a\geq 1$ und ungerade $N\geq 3$ lässt sich $J_N(a)$ in Zeit $O((log\ N+log\ a)^3)$ berechnen (ohne $N$ zu faktorisieren!). (Man benutzt einen klassischen Satz aus der Zahlentheorie, nämlich das quadratische Reziprozitätsgesetz, das auf Gauß zurückgeht. Damit erhält man eine Berechnung, deren Rekursionsschema dem des Euklidischen Algorithmus ähnelt. Details: Buch von Küsters/Wilke.) Lemma 5.12: Seien $p,q >2 prim,N=pq,e\in\mathbb{Z}^*_{\varphi(N)}$. Dann gilt $J_N(x^e\ mod\ N) =J_N(x)$ für alle $x\in\mathbb{Z}$. Beweis: $L_p(x^e\ mod\ N)\equiv_p (x^e\ mod\ N)^{\frac{p-1}{2}} \equiv_p x^{e\frac{p-1}{2}} \equiv_p (x^{\frac{p-1}{2}}\ mod\ p)^e \equiv_p (L_p(x)^e =L_p(x)$ denn $e$ ist ungerade und damit $L_p(x^e\ mod\ N) =L_p(x)$. Analog gilt $L_q(x^e\ mod\ N) =L_q(x)$. Also: $J_N(x^e\ mod\ N) =L_p(x^e\ mod\ N)*L_q(x^e\ mod\ N) =L_p(x)*L_q(x) =J_N(x)$. Das heißt: $J_N(E(x,(N,e))) =J_N(x)$. Der Chiffretext zu $x$ erbt eine nichttriviale Eigenschaft von $x$, nämlich den Wert des Jacobi-Symbols. Da sich das Jacobi-Symbol effizient berechnen lässt, erhält man sofort einen effizienten Angreifer. Wie? Der Finder berechnet zwei Klartexte $z_0$ und $z_1$ mit $J_N(z_0) = 1$ und $J_N(z_1) = -1$. Aus dem Jacobisymbol $J_N(y)$ der Probe kann er schließen, welcher der beiden Klartexte verschlüsselt wurde. Es folgt erneut: RSA ist nicht sicher im Sinn des Tests in Abschnitt 5.2.2. Man könnte versuchen, diesem ,,kleinen'' Problem zu entkommen, indem man nur Klartexte $x\in [N]$ mit $J_N(x) = 1$ zulässt. Allerdings wird dadurch die Menge der Bitstrings, die Klartexte sein dürfen, auf etwas unübersichtliche Weise eingeschränkt. \subsection{Weitere Bemerkungen zur Sicherheit und effizienten Verwendung von RSA} Der Einwand, dass man das Jacobisymbol des Klartextes ermitteln kann, ist vielleicht eine Schwäche von RSA, die man als praktisch geringfügig einschätzen kann. Viel schlimmer ist es, wenn man aus $y$ und $(e,N)$ den kompletten Klartext $x$ ermitteln kann. Es ist kein Verfahren bekannt, das dies in der allgemeinen Situation effizient bewerkstelligt. Wir beschreiben hier (informal) Begründungen dafür, dass die naheliegendsten Angriffe vermutlich nicht effizient durchführbar sind, und Maßnahmen, die RSA zu einem (praktisch, vermutet) sicheren System machen. \subsubsection{Äquivalenz ,,d bekannt'' zu ,,N faktorisieren''} Wenn Eva die Zahl $N$ effizient in ihre Faktoren $p$ und $q$ zerlegen kann, kann sie natürlich sofort $\varphi(N)$ und $d$ berechnen und damit sämtliche mit $k=(e,N)$ verschlüsselten Nachrichten lesen. Nach aktuellem Stand sind Faktorisierungsverfahren nicht effizient genug, um Zahlen mit einigen hundert Dezimalstellen zuverlässig effizient zu faktorisieren. Eine scheinbar schwächere Anforderung ist, dass Eva den Wert $\varphi(N)$ berechnen kann, denn dann kann sie auch $d$ berechnen (mit dem erweiterten Euklidischen Algorithmus) und direkt entschlüsseln. Ganz allgemein ist der RSA-Schlüssel $(k,\hat{k}) = ((e,N),(d,N))$ vollständig gebrochen, wenn Eva $d$ ermitteln kann, nur aus der Kenntnis von $(e,N)$. Ist dies vielleicht ,,leichter'' als die Faktorisierung von $N$? Man kann Folgendes zeigen: Aus $N$, $e$ und $d$ lassen sich mit einem randomisierten Verfahren effizient die Faktoren $p$ und $q$ berechnen. Das heißt: Das vollständige Brechen eines RSA-Schlüssels durch Ermittlung von $d$ ist in etwa genauso schwierig wie die Faktorisierung von $N$. Wir skizzieren die entsprechenden überlegungen. Satz: Es gibt einen randomisierten Polynomialzeitalgorithmus, der aus $e$, $d$ und $N$ die Primfaktoren $p$ und $q$ von $N$ berechnet. Skizze des Vorgehens in diesem Algorithmus: Wir schreiben $ed-1 = 2^k u$ für eine ungerade Zahl $u$ und $k\geq 1$. (Beachte, dass $e$ und $d$ ungerade sein müssen, weil sie teilerfremd zu $\varphi(N) = (p-1)(q-1)$ sind, einer geraden Zahl.) Definiere: $ord_p(b) = min\{w|b^w\ mod\ p= 1\}$, für $b\ mod\ p\not= 0$, analog $ord_q(b)$, für $b\ mod\ q\not= 0$. Dies ist die ,,Ordnung'' von $b\ mod\ p$ in der multiplikativen Gruppe $\mathbb{Z}^*_p$ bzw. $b\ mod\ q$ in $\mathbb{Z}^*_q$. Lemma 1: $p\not| a\Rightarrow ord_p(a^u)\in\{2^0, 2^1,...,2^k\}$. Beweis des Lemmas: Wenn $p|a$, ist nichts zu zeigen. Sonst benutze, dass es ein $s$ mit $s\varphi(N) =ed-1$ gibt. Dann gilt $(a^u)^{2^k}\equiv a^{s(p-1)(q-1)}\equiv (a^{p-1})^{s(q-1)}\equiv 1 (mod\ p)$ nach dem kleinen Satz von Fermat. Also ist (das gilt immer in Gruppen) die Ordnung von $a^u$ ein Teiler von $2^k$. Dies beweist das Lemma. Lemma 2: Wenn $p\not| a$ und $q\not| a$ und $ord_p(a^u)\not= ord_q(a^u)$, dann gibt es ein $i\leq k$ mit $ggT(N,(a^{u2^i}-1) mod\ N)\in\{p,q\}$. Beweis des Lemmas: O.B.d.A.: $ord_p(a^u)>ord_q(a^u) = 2^i$, mit $i1$. Falls ja, ist $ggT(a, N)$ ein Primfaktor von $N$. Sonst berechne $ggT(N, a^{u 2^i}-1\ mod\ N)$, für $i=0,1,... , k$. Falls einer dieser Werte $>1$ ist, ist er ein Primfaktor von $N$. Was noch fehlt: Satz $|\{a\in\{1,...,N-1\}|ord_p(a^u)\not= ord_q(a^u)\}|\geq\frac{1}{2}\varphi(N)$. Der Satz, für dessen Beweis wir auf das Buch von Baumann, Franz, Pfitzmann verweisen, besagt, dass der Algorithmus mit Wahrscheinlichkeit mindestens $\frac{1}{2}$ erfolgreich einen Primfaktor von $N$ findet. Konsequenz aus diesen Überlegungen: Wenn $d$ bekannt wird, darf man den Modulus $N$ keinesfalls weiter verwenden. Im Wesentlichen ist also das vollständige Brechen des Systemsäquivalent dazu, $N$ in seine Faktoren zu zerlegen. Das Faktorisierungsproblem gilt bislang als im Allgemeinen schwierig und für das Produkt $N$ von zwei zufälligen Primzahlen mit 512 Bits (oder 1024 Bits) als praktisch nicht lösbar. Man beachte aber: Den geheimen Schlüssel $d$ zu finden muss nicht die einzige Möglichkeit sein, aus $N,e$ und $y$ partielle Information über $x$ zu gewinnen, wie man am Jacobi-Symbol sieht. \subsubsection{Bemerkungen zum Faktorisierungsproblem, allgemein} Nach wie vor gibt es keinen Polynomialzeitalgorithmus, der beliebige zusammengesetzte Zahlen $N$ in ihre Primfaktoren zerlegen kann (äquivalent: in polynomieller Zeit einen nichttrivialen Faktor von $N$ bestimmen kann). Allerdings gab es in den letzten Jahrzehnten auch gewaltige Fortschritte bei der Entwicklung immer besserer Verfahren. \begin{itemize*} \item Pollards $(p-1)$-Methode (klassisch): Führt zu schneller Ermittlung eines Faktors von $N$, wenn für einen Primfaktor $p$ von $N$ gilt, dass $p-1$ nur kleine Primfaktoren hat. \item Pollards ${\rho}$-Methode (klassisch): Führt zur Ermittlung eines Faktors von $N$ in Zeit $O(\sqrt{p})$, wo $p$ ein Primfaktor von $N$ ist. Da $N$ immer einen Primfaktor in $O(\sqrt{n})$ hat, ist die Rechenzeit im schlechtesten Fall in $O(\sqrt[4]{n}) =O(2^{(log\ N)/ 4)})$. Schnell zum Ziel kommt man also, wenn $N$ einen kleinen Primfaktor $p$ hat. (Die oben angegebenen Vorschriften zur Wahl von $p$ und $q$ vermeiden diese Situation.) \item Quadratisches Sieb (Pomerance, 1981): Rechenzeit $O(e^{sqrt{(ln\ N)(ln\ ln\ N)}})$. \item Faktorisierung mit Elliptischen Kurven (Hendrik W. Lenstra, 1987): Rechenzeit $O(e^{(1+o(1)) \sqrt{(ln\ p)(ln\ ln\ p)}})$, wo $p$ der kleinste Primteiler von $N$ ist. \item Zahlkörpersieb (um 1990, zwei Varianten): Die schnellsten heute bekannten Faktorisierungsverfahren. Die anfallenden Rechnungen können auf vielen Rechnern parallel durchgeführt werden. Die Gesamtrechenzeit ist beschränkt durch $O(e^{C(ln\ N)^{\frac{1}{3}} (ln\ ln\ N)^{\frac{2}{3}}})$, für eine Konstante $C$. An der Verbesserung der Verfahren wird laufend gearbeitet. \end{itemize*} Der Rechenaufwand für die Faktorisierung auch nur 260-stelliger Zahlen in Dezimaldarstellung ist heute noch so immens, dass diese Art von Angriff auf das RSA-System noch nicht als ernsthafte Bedrohung angesehen wird. Das BSI (Bundesamt für Sicherheit in der Informationstechnik) empfiehlt für RSA-Anwendungen Schlüssellängen von 2000 Bits oder etwa 600 Dezimalziffern (bzw. 3000 Bits oder 900 Dezimalziffern, wenn auch Entwicklungen der nächsten Jahre mit einkalkuliert werden sollen.) Wenn sich $p$ und $q$ nur geringfügig unterscheiden, lässt sich $N$ effizient faktorisieren. Man sollte also darauf achten, dass $p$ und $q$ in nicht mehr als etwa den ersten 20 Binärstellen übereinstimmen. Bei zufälliger Wahl wird dies mit sehr hoher Wahrscheinlichkeit eintreten. Es gibt ein RSA-spezifisches Angriffsverfahren (,,Iteration''), das effizient funktioniert, wenn $p-1$ und $q-1$ kleine Primfaktoren haben. Bei der Wahl von $p$ und $q$ ist also auch darauf zu achten, dass dies nicht der Fall ist (s. Buch von Buchmann). \subsubsection{Zufallskomponente} In der Praxis wird der Klartext $x\in\{0,1\}^w$ mit $w<\lfloor log\ N\rfloor$ durch Anhängen eines zufälligen Bitstrings $r$ auf Länge $\lfloor log\ N\rfloor$ gebracht und das Wort $x\circ r$ (Konkatenation von $x$ und $r$) wie beschrieben verschlüsselt. Die Zufallskomponentermacht den Verschlüsselungsalgorithmus $E$ zu einem randomisierten Verfahren. Der Empfänger muss natürlich ebenfalls die Länge $w$ kennen, um nach der Entschlüsselung aus $x\circ r$ die eigentliche Botschaft $x$ zu ermitteln. Dieses Vorgehen hat auch den Vorteil, dass selbst bei mehrmaligem Versenden derselben Botschaft (oder Wiederholung von Blöcken) unterschiedliche Chiffretexte entstehen und zum Beispiel die Parität der Anzahl der 1-Bits in $x\circ r$ sowie das letzte Bit von $x\circ r$ rein zufällig sind und keine Information über $x$ liefern. Auch das Problem mit dem Jacobisymbol wird damit entschärft, da $J_N(x\circ r)$ vermutlich einigermaßen zufällig sein wird. Zudem wird in realen Anwendungen noch eine ,,kryptographische Hashfunktion'' $h$ auf $x\circ r$ angewendet und der neue Klartext $x'=x\circ r\circ h(x\circ r)$ mit dem RSA-System verschlüsselt. Bob entschlüsselt zu $z\circ t\circ w$ und akzeptiert die Nachricht $z$ nur, wenn $h(z\circ t)=w$ ist. Vorteil hiervon: Manipulationen an der Nachricht werden erkannt, die Nachrichten-Integrität ist gesichert. (Es bleibt das Problem sicherzustellen, dass die Nachricht tatsächlich von Alice gesendet worden ist.) \subsubsection{Effizienzverbesserungen} 1. Wahl des Verschlüsselungsschlüssels $e$: Mitunter wird vorgeschlagen, $e=3$ zu wählen, weil dann die Verschlüsselung besonders effizient vor sich geht. (Man benötigt nur zwei Multiplikationen modulo N.) Es gibt aber einen Angriff, der den Klartextxeffizient ermitteln kann, wenn drei Chiffretexte für $x$ mit verschiedenenöffentlichen Schlüsseln $(N_1,3),(N_2,3),(N_3,3)$ vorliegen. (Dies kann passieren, wenn Alice dieselbe Nachricht ohne Zufallskomponente an drei verschiedene Empfänger mit verschiedenen RSA-Schlüsseln schickt.) Diesem Problem entgeht man, indem man etwa $e=2^{16}+1$ wählt. Auch in diesem Fall ist die Verschlüsselung billiger als im allgemeinen Fall, da man mit 17 Multiplikationen modulo N auskommt. 2. Empfänger rechnet modulo $p$ und $q$, um Rechenzeit zu sparen: Da Bob $d$ kennt, können wir auch annehmen, dass er sogar die Faktoren $p$ und $q$ kennt. Dies kann zu einer Beschleunigung der Berechnung von $z=y^d\ mod\ N$ benutzt werden, wie folgt: Bob berechnet $z_p=y^d\ mod\ p$ und $z_q=y^d\ mod\ q$. Aus diesen beiden Zahlen bestimmt er mit dem Chinesischen Restsatz $z\in [N]$ mit $z\equiv z_p (mod\ p)$ und $z\equiv z_q(mod\ q)$. Dieses Vorgehen spart Rechenaufwand, da die Exponentiationen nur mit Zahlen der halben Länge durchgeführt werden müssen und die Anwendung des Chinesischen Restsatzes auf den erweiterten Euklidischen Algorithmus hinauslaufen, der eine deutlich kleinere Rechenzeit als eine Exponentiation hat. Eine Überschlagsrechnung ergibt, dass sich durch dieses Vorgehen der Rechenaufwand für die Entschlüsselung etwa um den Faktor 4 verringert. (Man beachte, dass dies die im vorherigen Abschnitt diskutierte Erweiterung des Klartextes um einen Zufallsstring und einen Hashwert kompensiert.) \subsubsection{Das Rabin-Kryptosystem} Es ist nicht bekannt, ob das Problem, RSA-verSchlüsselte Botschaften unberechtigterweise zu entschlüsseln, äquivalent zum Faktorisierungsproblem ist. Wir betrachten hier noch das Rabin-Verschlüsselungsverfahren, bei dem dies der Fall ist. Auch beim Rabin-Verfahren handelt es sich um ein Public-Key-Kryptosystem. *Schlüsselerzeugung* (Bob oder Trust Center): Wähle zwei verschiedene zufällige große Primzahlen $p$ und $q$ mit $p\equiv q\equiv 3 (mod\ 4)$, also Primzahlen, die um 1 kleiner als ein Vielfaches von 4 sind. Berechne $N=pq$. Der öffentliche Schlüssel ist $k=N$; der geheime Schlüssel ist $\hat{k}= (p,q)$. *Verschlüsselung* eines Blocks, der eine Zahl $x1$, ist sie fertig, denn dieser größte gemeinsame Teiler ist entweder $p$ oder $q$. Andernfalls berechnet sie $y=x^2\ mod\ N$. Dann wendet sie ihr Entschlüsselungsverfahren an und berechnet ein $z=B(y)$ mit $z^2 \equiv y\ mod\ N$. Dieses $z$ hängt wohlgemerkt nicht von $x$, sondern nur von $y$ ab. Es gilt $x^2\equiv z^2 (mod\ N)$. Wie oben gesehen gibt es vier Möglichkeiten: \begin{enumerate*} \item $x\equiv z (mod\ p)$ und $x\equiv z (mod\ q)$ \item $x\equiv z (mod\ p)$ und $x\equiv -z (mod\ q)$ \item $x\equiv -z (mod\ p)$ und $x\equiv z (mod\ q)$ \item $x\equiv -z (mod\ p)$ und $x\equiv -z (mod\ q)$ \end{enumerate*} Welche dieser Möglichkeiten die richtige ist, hängt vom Zufall ab, der die Auswahl von $x$ steuert. Jede der 4 Quadratwurzeln von $y$ hat dieselbe Wahrscheinlichkeit $1/4$, als $x$ gewählt worden zu sein. \begin{enumerate*} \item Fall: $x=z$, Misserfolg. \item Fall: $0<|x-z|< N$ und $x-z$ durch $p$ teilbar, woraus $ggT(x-z,N) =p$ folgt: Erfolg! \item Fall: $0<|x-z|< N$ und durch $q$ teilbar, woraus $ggT(x-z,N) =q$ folgt: Erfolg! \item Fall: $x+z=N$, also $x-z\equiv 2x(mod\ N)$. Weil $2x$ teilerfremd zu $N$ ist, ergibt sich $ggT(x-z,N)=1$, Misserfolg. \end{enumerate*} Eva muss also nur $ggT(x-z,N)$ berechnen! Damit gelingt es ihr mit Wahrscheinlichkeit $1/2$, die Faktoren von $N$ zu ermitteln. Durch l-fache Wiederholung desselben Experiments lässt sich die Erfolgswahrscheinlichkeit auf $1-\frac{1}{2^l}$ erhöhen. \subsection{Diskrete Logarithmen und Anwendungen} \subsubsection{Diskrete Logarithmen} Wir betrachten eine endliche zyklische Gruppe $(G,\circ,e)$ (multiplikativ geschrieben) mit einem erzeugenden Element $g$. Das bedeutet : $G=\{g^0=e,g^1=g,g^2,...,g^{|G|- 1}\}$. Sei $N=|G|$ die Größe (,,Ordnung'') dieser Gruppe. Dann haben wir: \begin{itemize*} \item Die Exponentiationsabbildung $exp_g:\{0,1,...,N-1\}\rightarrow G, a\rightarrow g^a$, ist eine Bijektion (sogar ein Gruppenisomorphismus zwischen $(\mathbb{Z}_N,+,0)$ und $(G,\circ,e)$). \item Die Umkehrfunktion $log_g:G\rightarrow\{0,1,...,N-1\},g^a\rightarrow a$, heißt der diskrete Logarithmus zur Basis $g$. \item Das DL-Problem für $G$ und $g$ bezeichnet die Aufgabe, zu gegebenem $h\in G$ den Exponenten $a=log_g (h) \in\{0,1,...,N-1\}$ zu berechnen, also den Exponenten $a$ mit $g^a=h$. \end{itemize*} Für alle kryptographischen Verfahren, die mit zyklischen Gruppen arbeiten, müssen die Gruppenelemente eine explizite Darstellung haben, auf denen die Gruppenoperationen $\circ$ und $^{-1}$ effizient ausführbar sind. Dann ist auch die Exponentiation $a\rightarrow h^a$ effizient ausführbar (mit $\leq 2 log\ a$ Gruppenoperationen), mittels einer Variante der schnellen modularen Exponentiation. Das DL-Problem darf jedoch keinen (bekannten) effizienten Algorithmus haben. Als Gruppen $G$ kommen u.a. in Frage: \begin{itemize*} \item Für Primzahlen $p$: Die multiplikative Gruppe $\mathbb{Z}^*_p$ mit Grundmenge $\{1,...,p-1\}$ und Multiplikation modulo $p$ als Operation. Die Ordnung (d.h. die Größe) dieser Gruppe ist bekanntermaßen $N=p-1$. Siehe die folgende Tabelle. Es ist ein recht einfacher Fakt aus der Zahlentheorie, dass diese Gruppe für jede Primzahlpzyklisch ist, also ein erzeugendes Element $g$ hat. Die Gruppenoperationen sind effizient ausführbar: Die Gruppenoperation $\circ$ ist die Multiplikation modulo $p$; das neutrale Element ist die 1; zu gegebenem $h\in G$ kann man $h^{-1}$ mit dem erweiterten Euklidischen Algorithmus berechnen. Für $p$ mit 2048 Bits oder mehr, wobei $p-1$ einen ,,großen'' Primteiler enthält, gilt das DL-Problem als praktisch nicht lösbar (für ,,allgemeine'' $a$). \item Die multiplikative Gruppe eines beliebigen endlichen Körpers, z. B. $GF(2^k)$. Es muss nur sichergestellt sein, dass die Multiplikation im Körper effizient ausführbar ist. Hierfür benötigt man ein irreduzibles Polynom von Grad $k$ und man muss Implementierungen von Polynommultiplikation und -Division haben. Für das Bilden von Inversen kann man den Potenzierungstrick benutzen oder den erweiterten Euklidischen Algorithmus für Polynome. Schließlich muss ein erzeugendes Element der multiplikativen Gruppe $GF(2^k)^*$ bekannt sein. (Die Kardinalität der Gruppe sollte mindestens $2^{2000}$ sein.) \item Zyklische Untergruppen von ,,elliptischen Kurven'' über endlichen Körpern. (Hier genügen Körperelemente mit einer Bitlänge von 256 Bits.) \end{itemize*} Tabelle: Die multiplikative Gruppe $\mathbb{Z}^*_{11}$ für $p=11$ mit erzeugendem Element $g=2$. Die erzeugenden Elemente sind mit $*$ markiert. Sie entsprechen den Potenzen $g^a$ mit $ggT(a,10) = 1$. \begin{tabular}{c} | a | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 \\\hline | $2^a$ | 1 | 2 | 4 | 8 | 5 | 10 | 9 | 7 | 3 | 6 \\ | | | * | | * | | | | * | | * \end{tabular} Für kryptographische Anwendungen ungeeignetist dagegen die bekannteste zyklische Gruppe $(\mathbb{Z}_N,+,0)$. Hier ist die Gruppenoperation die Addition modulo $N$; die Potenz $g^a$ für $a\in\mathbb{Z}$ entspricht dem Element $a*g\ mod\ N$. Die erzeugenden Elemente sind gerade die Elemente von $\mathbb{Z}^*_N$. Wenn $g\in\mathbb{Z}^*_N$ ist, dann besteht das DL-Problem für $g$ in folgendem: Gegeben $h=g^a$ (in der Gruppe gerechnet, das ist also $h=a*g\ mod\ N)$, finde $a$. Dies ist mit dem erweiterten Euklidischen Algorithmus leicht möglich: finde $g-1\ mod\ N$, berechne $h*g^{-1}\ mod\ N$. Das DL-Problem in dieser Gruppe ist also effizient lösbar. Wenn eine zyklische Gruppe $G$ mit effizienten Operationen gefunden worden ist, muss man immer noch ein erzeugendes Element finden. Das ist unter Umständen nicht ganz einfach. Wir wissen: \begin{itemize*} \item Eine zyklische Gruppe $G=\langle g\rangle $ mit $|G|=N$ hat genau $\varphi(N) = |\mathbb{Z}^*_N|$ viele erzeugende Elemente, nämlich die Elemente $g^a$ mit $a\in\mathbb{Z}^*_N$. \end{itemize*} Das bedeutet, dass ein Anteil von $\varphi(N)/N$ der Elemente von $G$ erzeugende Elemente sind. Aus Kapitel 4 wissen wir, dass $\varphi(N)/N=\prod_{p\ ist\ prim, p|N}(1-\frac{1}{p})$ gilt. Man kann zeigen, dass dies $\Omega(1/log\ log\ N)$ ist. Wir können also analog zum Vorgehen bei der Primzahlerzeugung ein erzeugendes Element finden, wenn wir folgende Operationen zur Verfügung haben: \begin{itemize*} \item zufälliges Wählen eines Elements von $G$ \item Test, ob $h\in G$ ein erzeugendes Element ist oder nicht \end{itemize*} Jedoch setzen alle bekannten effizienten Verfahren für den Test ,,Ist $h$ erzeugendes Element?'' voraus, dass man die Primfaktoren von $N=|G|$ kennt. Für den Fall $G=\mathbb{Z}^*_p$ ist die Situation so: Für große zufällige Primzahlen $p$ (512, 1024 oder 2048 Bits) ist die Primfaktorzerlegung von $N=p-1$ normalerweise nicht leicht zu ermitteln. Ein Ausweg ist, gezielt nach Primzahlen $p$ zu suchen, für die $p-1$ eine übersichtliche Primfaktorzerlegung hat. Besonders angenehm ist die Situation, wenn $p=2q+1$ für eine Primzahl $q$ ist. In dieser Situation gibt es genau $q-1=(p-3)/2$ erzeugende Elemente und man kann ein $x\in G$ durch schnelle Exponentiation darauf testen, ob es ein erzeugendes Element ist. Man erhält direkt ein randomisiertes Verfahren, das nach durchschnittlich zwei Tests ein erzeugendes Element gefunden hat. Alle im Folgenden beschriebenen kryptographischen Verfahren werden unsicher, wenn man in der verwendeten Gruppe das DL-Problem effizient lösen kann. Bei der Verwendung solcher Verfahren muss man also unbedingt darauf achten, keine Gruppen zu benutzen, bei denen praktikable Verfahren für das DL-Problem bekannt sind. Für das Folgende nehmen wir an, dass die verwendete Gruppe diesen Mindestanforderungen genügt. \subsubsection{Diffie-Hellman-Schlüsselaustausch} Sei $G$ eine zyklische Gruppe mit Erzeuger $g$ und sei $(X,G,Y,e,d)$ ein symmetrisches Kryptosystem wie in Kapiteln 1 und 2 oder $(G,E,D)$ ein symmetrisches Kryptoschema wie in Kapitel 3. (Das heißt, dass die Elemente von $G$ die Schlüssel sind.) Nehmen wir an, Alice und Bob möchten per Kommunikationüber einen öffentlich (insbesondere von Eva) einsehbaren Kanal einen gemeinsamen, geheimen, zufälligen Schlüssel $k\in G$ festlegen. Das Diffie-Hellman-Schlüsselaustausch-Protokoll macht dies möglich! Die Idee dabei ist, dass $k=g^{ab}$ ist, wo nur Alice $a$ kennt und nur Bob $b$. Über den öffentlichen Kanal laufen die Gruppenelemente $g^a$ und $g^b$. Eva hat also das Problem, aus $g^a$ und $g^b$ den Wert $g^{ab}$ zu berechnen. (Das ist das sogenannte DH-Problem, benannt nach W. Diffie und M. E. Hellman, die das Schlüsselaustauschverfahren 1976 vorgeschlagen haben.) Wenn Eva das DL-Problem lösen könnte, wäre dies leicht. Andere Möglichkeiten, das DH-Problem effizient zu lösen, ohne einen effizienten Algorithmus für das DL-Problem, sind prinzipiell denkbar, aber nicht bekannt. *Protokoll ,,Diffie-Hellman-Schlüsselaustausch''* \begin{itemize*} \item Voraussetzung: Alice and Bob kennen $G,|G|$ und $g$. \end{itemize*} \begin{enumerate*} \item Alice wählt $a\in\{2 ,...,|G|- 2\}$ zufällig, und sendet $A=g^a$ an Bob. \item Bob wählt $b\in\{2 ,...,|G|-2\}$ zufällig, und sendet $B=g^b$ an Alice. \item Alice berechnet $B^a= (g^b)^a=g^{ab}=k$. \item Bob berechnet $A^b= (g^a)^b=g^{ab}=k$. \end{enumerate*} Dabei wird benutzt, dass die Multiplikation der Exponenten $a$ und $b$ kommutativ ist. Alice und Bob kennen nun $k$; Eva kennt nur $A$ und $B$, sowie (nach dem Kerckhoffs-Prinzip) $G$ und $|G|$. Achtung! Das DH-Protokoll in der hier vorgestellten Form wird völlig unsicher, wenn Eva den Kommunikationskanal nicht nur abhört, sondern aktiv eingreifen kann. ,,Man-in-the-middle-attack'': Eva fängt alle Nachrichten von Alice an Bob und umgekehrt ab und modifiziert sie. Schlüsselvereinbarung: Alice sendet $A=g^a$. Eva fängt $A$ ab, wählt selbst eine Zufallszahl $a'$ und schickt $A'=g^{a'}$ an Bob. Dieser nimmt an, $A'$ käme von Alice. Sein $B=g^b$ wird ebenfalls von Eva abgefangen und durch $B'=g^{b'}$ ersetzt, für ein von Eva gewähltes $b'$. Alice nimmt an, $B'$ käme von Bob. Senden eines Chiffretextes: Wenn Alice Nachricht $x$ an Bob schicken möchte, verwendet sie Schlüssel $k'= (B')^a=g^{ab'}$ und sendet $y'=E(x,k')$. Eva fängt dies ab und entschlüsselt mittels $k'=A^{b'}$. Sie kennt nun $x$, berechnet $k''=B^{a'}$ und schickt $E(x,k'')$ an Bob. Dieser entschlüsselt mittels $k''= (A')^b$, und erhält wieder $x$. Um das DH-Protokoll gegen solche Angriffe abzusichern, muss man andere Protokolle (sog. Authentifizierungsprotokolle) benutzen, die es ermöglichen herauszufinden, ob der Absender einer Nachricht tatsächlich der gewünschte Partner (Alice bzw. Bob) ist. \subsubsection{Das ElGamal-Kryptosystem} Das ElGamal-Kryptosystem steht in engem Zusammenhang mit dem DH-Schlüsselaustausch. Wie RSA ist auch dieses System ein Public-Key-Kryptosystem. Seine Sicherheit beruht nicht auf der (vermuteten) Schwierigkeit des Faktorisierungsproblems wie RSA, sondern auf der (vermuteten) Schwierigkeit des DL-Problems bzw. des DH-Problems. *Erzeugung* des Schlüssels (Bob oder Trust-Center im Auftrag von Bob): Es wird eine zyklische Gruppe $(G,\circ,e)$ mit einem erzeugenden Element $g$ benötigt, sowie $N=|G|$, so dass das zugehörige DH-Problem schwer zu lösen ist. Ein Element $b$ wird zufällig aus $\{2 ,...,|G|-2\}$ gewählt, und es wird mittels schneller Exponentiation $B=g^b$ berechnet. Der öffentliche Schlüssel ist $k_{pub}= (G,g,B)$, der geheime Schlüssel ist $b$ bzw. $k_{priv}=(G,g,b)$. *Verschlüsselung*: Wir nehmen an, dass die Menge der möglichen Botschaften (Binärstrings) eine Teilmenge von $G$ ist. Um eine Botschaft $x\in G$ zu verschlüsseln, wählt Alice eine Zufallszahl $a$ aus $\{2,...,|G|-2\}$ und berechnet $A=g^a$. Weiter berechnet sie $y:=B^a \circ x$. Der Chiffretext ist $(A,y)$. Kommentar: Der Rechenaufwand liegt im Wesentlichen in den zwei schnellen Exponentiationen. RSA benötigt eine schnelle Exponentiation. Man erkennt die Komponenten $A$ und $B$ aus dem Diffie-Hellman-Schlüsselaustausch wieder. Der Wert $B^a$ ist $k=g^{ab}$, der Wert $y$ ist $k\circ x$. *Entschlüsselung*: Bob kennt die Gruppe $G$ und $g$, sowie $A$ und $y$ (von Alice) sowie seinen geheimen Schlüssel $b$. Er berechnet $A^b= (g^a)^b=k$. Dann berechnet er das Gruppenelement $z=k^{-1}\circ y$, mit Hilfe der effizienten Invertierung und Gruppenoperation in $G$. *Beobachtung*: $z=x$. (Das ist klar: $z=k^{-1}\circ y=k^{-1}\circ(k\circ x) =x$) Kommentar: Der Rechenaufwand der Entschlüsselung liegt im Wesentlichen in der schnellen Exponentiation und der Invertierung von $k$. *Sicherheit*: Man kann sich überlegen, dass für eine Angreiferin Eva und eine Gruppe G mit erzeugendem Element $g$ folgende Situationen äquivalent sind: \begin{enumerate*} \item Eva kann alle mit dem ElGamal-Verfahren bzgl. $G$ und $g$ verschlüsselten Nachrichten effizient entschlüsseln, also aus $B$, $A$ und $y$ die Nachricht $x$ berechnen, die zum Chiffretext $(A,y)$ geführt hat. \item Eva kann das DH-Problem für $G$ lösen. \end{enumerate*} Wenn Eva diskrete Logarithmen bezüglich $G$ und $g$ berechnen kann, gelten natürlich 1. und 2. Wir beweisen die Äquivalenz. \begin{itemize*} \item ,,1.$\Rightarrow$2.'': Eva hat $B=g^b$ und $A=g^a$ vorliegen und möchte $k=g^{ab}$ bestimmen. Sie wendet ihr Entschlüsselungsverfahren auf $B$, $A$ und $y=1$ an. Es ergibt sich ein Wert $x$ mit $g^{ab}\circ x=k\circ x=y=1$. Es gilt also $x=k^{-1}$, und Eva kann $k$ durch Invertierung von $x$ in $G$ berechnen. \item ,,2.$\Rightarrow$1.'': Eva hat $B=g^b$,$A=g^a$,$y=g^{ab}\circ x$ vorliegen. Weil sie das DH-Problem lösen kann, kann sie $k=g^{ab}$ berechnen und damit natürlich $x=k^{-1}\circ y$ bestimmen. \end{itemize*} Unterschiede zwischen RSA und ElGamal: \begin{itemize*} \item RSA in der puren Form benötigt einen Chiffretext $y=x^e\ mod\ N$, der die gleiche Bitlänge hat wie der Klartext $x$. ElGamal hat einen doppelt so langen Chiffretext $(B,y)$. \item ElGamal ist erzwungenermaßen randomisiert. Daher führt die wiederholte Verschlüsselung desselben Klartextes $x$ stets zu unterschiedlichen Chiffretexten, weil der Schlüssel $k$ zufällig ist. \end{itemize*} Allerdings gibt es die Empfehlung, beim Arbeiten mit RSA den Klartext $x$ durch das Anhängen eines nicht ganz kurzen Zufallsstrings zu randomisieren. Wenn dieser angehängte Zufallsstring die gleiche Länge wie $x$ hat, ist der Chiffretext genauso lang wie bei ElGamal. \subsubsection{Berechnung diskreter Logarithmen} Wie schwierig ist das ,,DL-Problem''? Geg.: Zyklische Gruppe $(G,\circ,e),|G|=N,$ mit erzeugendem Element $g$. Input: $h\in G$ Gesucht: $a$ mit $0\leq a 10^{36}$, und an eine Ausführung von ,,Enumeration'' ist nicht zu denken. Babystep-Giantstep-Algorithmus von Shanks: Wähle $m=\lceil \sqrt{N}\rceil$. Der gesuchte Exponent $a$ hat eine Zerlegung $a=bm+c$, für $0\leq c < m$ und passendes $b\leq a/m < N/m\leq \sqrt{N}$. \begin{itemize*} \item Es gilt: $h=g^a=g^{bm+c}=g^{bm} \circ g^c$, also $g^{-c}=h^{-1}\circ g^{bm}$. \item Gesucht: $b$ und $c$. \item Algorithmus: Berechne alle Potenzen $g^{bm}$, $0\leq b < N/m$, und speichere $h^{-1}\circ g^{bm}$ (als Schlüssel) mit Wert $b$ in einer Hashtabelle $T$, Umfang $2N/m\leq 2\sqrt{N}$. Berechne $g^{-c}$, für $c=0,1,...,m-1$ und suche $g^{-c}$ in $T$. Wenn gefunden, gilt $h^{-1} \circ g^{bm}=g^{-c}$, also $h=g^{bm+c}$. \item Rechenzeit: $O(\sqrt{N})$ (erwartet) für Tabellenaufbau und $O(\sqrt{N})$ (erwartet) für die Suche, zusammen $O(\sqrt{N})$. \item Platzbedarf: $O(\sqrt{N})$ \item Wenn $N=2^{200}$, ist $\sqrt{N}= 2^{100}> 10^{30}$. Selbst wenn man nur in dem unwahrscheinlichen Fall $a\leq 2^{160}$ erfolgreich sein möchte, muss man Tabellengröße $2^{80}> 10^{24}$ veranschlagen. Auch dies ist nicht durchführbar. \end{itemize*} Pollards ${\rho}$-Algorithmus für DL Idee: Definiere eine Folge $(x_i,a_i,b_i),i= 0,1,2,...,$ in $G\times\mathbb{Z}_N\times\mathbb{Z}_N$, so dass $x_i=F(x_{i-1})$ gilt, für eine als zufällig geltende Funktion $F:G\rightarrow G$. Dann verhalten sich die ersten Komponenten $x_i$ wie zufällige Elemente in $G$, solange noch keine Wiederholung in der Folge $(Z_i)_{i=0, 1 , 2 ,...}$ aufgetreten ist. Nach dem Geburtstagsparadoxon weiß man, dass für eine genügend große Konstante $K$ die Wahrscheinlichkeit, dass $K\sqrt{N}$ zufällig gewählte Elemente von $G$ alle verschieden sind, sehr klein ist. Wir erwarten also nach $O(\sqrt{N})$ Schritten die Wiederholung eines Elements, also $i_0< j_0=O(\sqrt{N})$ mit $x_{i_0}= x_{j_0}$. Danach wiederholt sich die Folge: $x_{i_0 +1}= F(x_{i_0}) =F(x_{j_0}) = x_{j_0 +1}$, usw., also gilt $x_i=x_{i+kl}$ für alle $i\geq i_0$ und alle $k\geq 1$, wenn man $l=j_0 -i_0$ definiert. Man kann das Verhalten der Folge wie folgt zeichnen: $x_0,...,x_{i0}$ als gerade Linie ohne Wiederholung, daran angehängt $x_{i0},...,x_{j0}=x_{i0}$ als Kreis. Dies gibt die Form ,,${\rho}$'', wie beim griechischen Buchstaben ,,rho''. Wenn man es nun noch schafft, aus zwei Indizes $i < j$ mit $x_i=x_j$ den gesuchten Exponenten $a$ mit $h=g^a$ auszurechnen, ist man fertig. Um den Algorithmus auszuführen, muss man scheinbar $x_0,x_1,...,x_{j0-1}$ speichern, was wieder zu Speicherplatzbedarf $\Theta (\sqrt{N})$ führen würde. Es gibt nun einen Trick, mit dessen Hilfe man nur Platz $O(1)$ benötigt. Man beobachtet die Doppelfolge $((x_i,x_{2i}))_{i=0, 1 , 2 ,...}$ und wartet, bis $x_i= x_{2i}$ gilt. Gibt es solche $i$? Ja, denn für jedes $i\geq i_0$, für das $2i-i=i$ durch $l=j_0-i_0$ teilbar ist, ist $x_{2i}=x_{i+kl}$ für ein $k>0$, also $x_{2i}=x_i$. Zwischen $i_0$ und $j_0$ liegt auf jeden Fall ein solches $i$. Nun müssen wir noch $F$ definieren. Dazu betrachten wir erweiterte Elemente $(x,b,c)\in G\times\mathbb{Z}_N \times\mathbb{Z}_N$, die die Gleichung $x=g^b \circ h^c$ erfüllen. Das Starttripel ist $(g^{b0},b_0,0)$ für ein zufällig gewähltes $b_0$. Die Gruppe $G$ muss in etwa drei gleich große disjunkte Teilmengen $S_1,S_2,S_3$ aufgeteilt sein, etwa über die letzten 10 Bits der Darstellung der Elemente. Dann definieren wir die Schrittfunktion wie folgt: $$f(x,b,c) =\begin{cases} (h\circ x,b,c+1)\,\quad\text{ falls }x\in S_1\\ (x^2, 2b, 2c),\quad\text{ falls }x\in S_2\\ (g\circ x,b+1,c),\quad\text{ falls } x\in S_3 \end{cases}$$ Beachte, dass mit $(x,b,c)$ auch $f(x,b,c)$ die geforderte Gleichung erfüllt. Die Funktion $F$ ist einfach die Einschränkung von $f$ auf die erste Komponente. Nun berechnen wir in Runden $Y_i= (x_i,b_i,c_i)$ und $Z_i= (x_{2i},b_{2i},c_{2i})$, für $i=0,1,2,....$ (Es ist $Y_0=Z_0=(g^{b0},b_0,0)$ für $b_0$ zufällig und $Y_i=f(Y_{i-1})$ und $Z_{2i}=f(f(Z_{i-1}))$.) Dies wird so lange durchgeführt, bis zum ersten Mal $x_i=x_{2i}$ gilt. Dann haben wir: $g^{b_{2i}} h^{c_{2i}}=g^{b_i} h^{c_i}$, also $g^{b_{2i}+ac_{2i}}=g^{b_i+ac_i}$. Weil $g$ Ordnung $N$ hat, folgt $b_{2i} +ac_{2i}\equiv b_i+ac_i (mod\ N)$, das heißt $a(c_{2i}-c_i)\equiv b_i-b_{2i} (mod\ N)$. Falls nun $ggT(c_{2i}-c_i,N) = 1$ ist, können wir mit $a= (b_i-b_{2i})(c_{2i}-c_i)^{-1}\ mod\ N$ den gesuchten Exponenten berechnen. Die Rechenzeit ist $O(\sqrt{N})$, wenn man unterstellt, dass die Abbildung $F:x_{i-1}\rightarrow x_i$ rein zufällig ist. (In der Praxis bestätigt sich diese Vorstellung.) Weitere Algorithmen für das DL-Problem: \begin{itemize*} \item Pohlig-Hellman-Algorithmus. Dieser Algorithmus benötigt die Primfaktorzerlegung von $N=|G|$. Seine Rechenzeit ist $O(\sum_{1 \leq i\leq k} e_i(log|G|+\sqrt{p_i}) + (log\ |G|)^2)$, wenn $|G|$ die Primfaktorzerlegung $p^{e_1}_1... p^{e_k}_k$ hat. Dieser Algorithmus ist also effizient, wenn $|G|$ nur eher kleine Primfaktoren hat. Wenn man also mit $G$ arbeiten will, muss $N=|G|$ mindestens einen ,,großen'' Primfaktor enthalten, damit nicht der Pohlig-Hellman-Algorithmus das DL-Problem effizient löst. \item Indexkalkül. Dieser Algorithmus ist nur für die multiplikative Gruppe $GF(q)^*$ in endlichem Körper $GF(q)$ anwendbar. \item Zahlkörpersieb. Ebenso nur für $GF(q)^*$ (mit ähnlichen subexponentiellen Rechenzeiten wie bei dem gleichnamigen Algorithmus bei der Faktorisierung). \end{itemize*} Letzteres ist eine allgemeine Beobachtung: DL in $GF(q)^*$ scheint nicht viel schwieriger zu sein als das Faktorisierungsproblem für Zahlen in der Größenordnung von $q$. \subsubsection{Elliptische Kurven über endlichen Körpern} Elliptische Kurven (,,elliptic curves'', ,,EC'') sind mathematische Strukturen, die eine moderne, attraktive Methode zur Erzeugung endlicher zyklischer Gruppen zur Verwendung in der Kryptographie liefern. Der Ansatz wurde 1985 unabhängig von den amerikanischen Mathematikern Neal Koblitz (\*1948) und Victor S. Miller (\*1947) vorgeschlagen. Der große Vorteil des Verfahrens ist, dass die unter gewissen Umständen schnellen DL-Verfahren für $GF(q)^*$, nämlich Indexkalkül und Zahlkörpersieb, nicht anwendbar sind. Die benötigte Gruppengröße, um ,,Sicherheit'' im praktischen Sinn zu garantieren, ist deutlich kleiner als die bei der zyklischen Gruppe $GF(q)^*$. Dies führt zu Gruppenelementen mit kleinerer Darstellungsgröße und daher effizienterer Verfahren für Verschlüsselung und Entschlüsselung. (Übliche Längen im Jahr 2016: Bestehende Verfahren benutzen 160 Bits, Planung bis 2030: 224 oder 256 Bits. Ein System, das $\mathbb{Z}^*_p$ für eine 256-Bit-Primzahl $p$ benutzt, gilt als äußerst sicher. Andere endliche Körper kommen ebenfalls in Frage. Vorsicht bei $GF(2^k)^*$! Man benötigt andere Formeln als die unten diskutierten!) Wir geben nur eine Beschreibung der Verfahren. Für mathematischen Hintergrund sei auf die Literatur verwiesen, z.B. A. Werner, Elliptische Kurven in der Kryptographie, Springer 2002, oder Diekert, Kufleitner, Rosenberger, Diskrete algebraische Methoden, de Gruyter 2013. Als anschaulichen Hintergrund, nicht zur Anwendung in der Kryptographie, betrachten wir zunächst Elliptische Kurven in $\mathbb{R}^2$. Gegeben seien Koeffizienten $A, B$ in $\mathbb{R}$, die die Ungleichung $4A^3+ 27B^3 \not= 0$ erfüllen. (Diese Bedingung hat zur Folge, dass die Funktion $x\rightarrow x^3+Ax+B$ keine Mehrfachnullstellen hat, weder im Reellen noch im Komplexen. Dabei heißt $a\in C$ eine Mehrfachnullstelle, wenn man $x^3+Ax+B= (x-b)(x-a)^2$ schreiben kann, für ein $b\in C$.) Betrachte die Menge $\{(x,y)\in\mathbb{R}^2| y^2=x^3+Ax+B\}$. Diese bildet eine ,,Kurve'' in $\mathbb{R}^2$. Verschiedene Formen sind möglich. Die ,,Kurve'' kann auch mehrere Komponenten haben. Man beobachtet allgemein: Die Punktmenge ist symmetrisch bezüglich der x-Achse; die ,,Gestalt'' hängt von der Lage der Nullstellen von $x\rightarrow x^3+Ax+B$ ab. Veranschaulichung für $(A,B)\in\{(- 1 ,-1),(- 1 ,0),(- 1 ,1)\}$ später. Da Doppelnullstellen ausgeschlossen sind, gibt es eine oder drei Nullstellen. Solche Kurven, eventuell ergänzt um einen Punkt $O$, nennt man Elliptische Kurven in $\mathbb{R}^2$. Unsere eigentliche Konstruktion benutzt nicht $\mathbb{R}$, sondern endliche Körper $\mathbb{Z}_p$ für eine Primzahl $p>3$. Wir rechnen ab hier in einem solchen Körper, für festes $p$; die Operationen $+$ und $*$ sind immer als Addition und Multiplikation modulo $p$ zu interpretieren. \textbf{Definition} 5.13: Sei $p >3$ eine Primzahl, seien $A,B\in\mathbb{Z}_p$ mit $4A^3+ 27B^3 \not= 0$. Die elliptische Kurve $E_{A,B}$ besteht aus der Menge aller Lösungen $(x,y)\in\mathbb{Z}^2_p$ der Gleichung $y^2=x^3+Ax+B$ sowie einem zusätzlichen Punkt $O$ (genannt ,,der unendliche Punkt''). Wenn man für $\mathbb{Z}_p$ die Repräsentanten $-\frac{p-1}{2},..., 0 , ...,\frac{p-1}{2}$ benutzt, beobachtet man wiederum die Symmetrie entlang der x-Achse, sonst gibt es kein erkennbares Muster. Beispiel: $\mathbb{Z}_7$. Setze $f(x)=x^3+ 3x+ 3$ (in $\mathbb{Z}_7$) und betrachte $E_{3,3}=\{(x,y)\in\mathbb{Z}^2_7 | f(x)=y^2\}\cup \{O\}$. Damit $(x,y)$ zu $E_{3,3}$ gehört, muss $f(x)$ ein Quadrat sein. Allgemein weiß man, dass es in $\mathbb{Z}_p$ genau $\frac{p-1}{2}$ Quadrate gibt. Jedes $f(x)$, das von $0$ verschieden und ein Quadrat ist, führt zu zwei Punkten auf der elliptischen Kurve. Weiter gibt es für jedes $x$ mit $f(x) = 0$ einen Punkt auf der Kurve. Man rechnet aus: \begin{tabular}{c|c|c|c|c|c|c|c} x & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline f(x) & 3 & 0 & 3 & 4 & 2 & 3 & 6 \\ Quadrat? & - & X & - & X & X & - & - \\ Wurzeln & & 0 & & 2, 5 & 3, 4 & \\ Punkte & & (1,0) & & (3,2) & (4,3) \\ & & & & (3,5) & (4,4) \end{tabular} Um auf dieser Menge eine Gruppenstruktur festzulegen, benötigen wir ,,Geraden'' in $\mathbb{Z}^2_p$. Dies sind Punktmengen $\{(x,y)|y=ax+b\}$ für $a,b\in\mathbb{Z}_p$ oder $\{(x,y)|x=b\}\cup\{O\}$ (,,senkrechte Geraden''). Man stellt nun (durch Unterscheiden verschiedener Fälle) Folgendes fest: Wenn eine Gerade eine elliptische Kurve $E=E_{A,B}$ in mindestens einem Punkt schneidet, dann sogar in drei Punkten, die aber nicht notwendigerweise verschieden sein müssen. (Das liegt an der Anzahl der Nullstellen von $x^3+Ax+B$. Veranschaulichung im Reellen!) Wenn zwei der betrachteten Schnittpunkte zusammenfallen, ist die Gerade eine Tangente in diesem Punkt; bei senkrechten Geraden gilt der unendliche Punkt als einer der Schnittpunkte oder gar als drei zusammenfallende Schnittpunkte. Die Operation $\circ$ kann dann anschaulich wie folgt beschrieben werden (man verwendet wieder für einen Moment die Bilder im $\mathbb{R}^2$): Gegeben seien Punkte $P$ und $Q$ auf der elliptischen Kurve, beide von $O$ verschieden. Man legt eine Gerade durch $P$ und $Q$ (wenn sie identisch sind, eine Parallele zur Kurve in $P$) und bestimmt den dritten Punkt $R$ im Schnitt von Kurve und Gerade. Wenn $R=O$ ist, ist $P\circ Q=O$, wenn $R= (x,y)\not=O$, dann ist $P\circ Q=\overline{R}= (x,-y)$ (Spiegelung an der x-Achse). Weiter definiert man: $P\circ O=O\circ P=P$ für alle Punkte $P$. Es ergeben sich (mit einigem Rechnen) die folgenden Formeln. Diese werden dann wörtlich auch als Definition für eine Operation $\circ$ in einer elliptischen Kurve über $\mathbb{Z}_p$ benutzt. \begin{itemize*} \item $O+O=O,$ \item $O+ (x,y) = (x,y) +O$ für alle $(x,y)\in\mathbb{Z}^2_p$, \item $(x_1,y_1) + (x_2,y_2) =\begin{cases} O,\quad\text{ falls } x_1=x_2 \text{ und } y_1=-y_2 \\ (x_3,y_3),\quad\text{ sonst,}\end{cases}$ \end{itemize*} wobei $(x_3,y_3)$ folgendermaßen berechnet wird: $x_3=\lambda^2-x_1-x_2$, $y_3=\lambda(x_1-x_3)-y_1$ mit $\lambda=\begin{cases} (y_2-y_1)/(x_2-x_1),\quad\text{ falls } (x_1,y_1)\not= (x_2,y_2)\\ (3x^2_1+A)/(2y_1),\quad\text{ falls } (x_1,y_1) = (x_2,y_2)\end{cases}$. Der erste Fall bezieht sich auf den dritten Schnittpunkt einer Geraden durch zwei Punkte; der zweite auf den Tangentenfall. \textbf{Satz} 5.14: Mit dieser Operation $\circ$ bildet $E_{A,B}$ eine kommutative Gruppe. Man beweist dies durch Nachrechnen. Der Nachweis der Assoziativität ist etwas mühselig. Das zu $(x,y)$ inverse Element ist $(x,-y)$, das zu $O$ inverse Element ist $O$. Notation: Die Gruppenoperation in Gruppen zu elliptischen Kurven wird additiv geschrieben, also mit $+$ bezeichnet. Das Inverse von $P$ heißt $-P$. Die wiederholte Verknüpfung eines Elementes mit sich selbst ist dann eine Multiplikation mit $a\in\mathbb{Z}$, etwa $2P, 3P,...$. Beispiel: Wenn $P=(x,0)$, dann gilt $P=-P$ und $2P=O$. Wir benötigen zyklische Untergruppen von $E_{A,B}$. Damit eine solche Gruppe ein schwieriges DL-Problem hat, muss sie natürlich groß sein, also muss auch $E_{A,B}$ groß sein. Wenn die Funktion $f(x) =x^3+Ax+B$ wie eine zufällige Funktion wirkt, wird sie für etwa die Hälfte der $x$ einen Wert haben, der ein Quadrat ist, und alle diese Werte (außer der $0$) führen zu zwei Punkten auf der Kurve. Nullstellen ergeben einen Punkt. Wir erwarten daher, dass $E_{A,B}$ etwa $p$ Elemente hat, und Folgendes sollte nicht zu sehr überraschen. Fakt 5.15 Hasse-Schranke: Sei $E$ elliptische Kurve über $\mathbb{Z}_p$. Dann gilt $p+ 1- 2\sqrt{p}\leq |E|\leq p+1 + 2\sqrt{p}$. Es gibt einen ,,effizienten'' Algorithmen zur Ermittlung der Gruppenordnung $N=|E|$ der höchstens $O((log\ p)^6)$ Gruppenoperationen benötigt. Wenn wir Glück haben, ist $N$ eine Primzahl; dann ist jedes Element von $E-\{O\}$ ein erzeugendes Element. Ein Standardverfahren ist, die Wahl von $A$ und $B$ so lange wiederholen, bis $N=|E_{A,B}|$ eine Primzahl $q$ ist. Dann wird ein Element $P$ aus $E-\{O\}$ zufällig gewählt und $(p,A,B,N,P)$ an den Kunden abgeliefert. Mit $p$ und $A$ kann man die Gruppenoperationen implementieren, mit $P$ und $N$ zusätzlich kann man den Diffie-Hellman-Schlüsselaustausch und das ElGamal-Kryptoschema umsetzen. Standardverfahren für das DL-Problem (Pollards ${\rho}$-Algorithmus, Pohlig-Hellman) funktionieren auch für Gruppen, die zu elliptischen Kurven gehören, nicht aber die viel schnelleren Verfahren wie Indexkalkül oder Zahlkörpersieb. Dies führt dazu, dass man annimmt, dass in EC-basierten Gruppen das DL-Problem (noch) schwieriger zu lösen ist als in $\mathbb{Z}^*_p$, so dass man mit kleineren Zahlbereichen arbeiten kann, was Verschlüsselung und Entschlüsselung wieder effizienter macht. *Effizienter Einsatz*: Wenn man versucht, das ElGamal-Kryptosystem auf der Basis einer elliptischen Kurve umzusetzen, gibt es das Problem, dass die Elemente von $E$ in $\mathbb{Z}^2_p$ eher dünn sind, so dass die Menge $E$ oder auch die Menge der x- Koordinaten von Punkten in $E$ als Klartextmenge schlecht geeignet ist. Wie soll man also gewöhnliche Nachrichten auf Punkte auf der Kurve abbilden? Es gibt ein reales kryptographisches Verfahren, das zeigt, wie man diese Schwierigkeit umgeht: ,,Elliptic Curve Integrated Encryption Scheme (ECIES)''. Es beruht darauf, nur für die Manipulationen auf der Schlüsselseite die Gruppe $E$ zu benutzen, und die eigentliche Verschlüsselung in $\mathbb{Z}^*_p$ auszuführen. Das reale ECIES-Verfahren integriert noch ein symmetrisches Verschlüsselungsverfahren und ,,message authentication'' (ein ganz anderes kryptographisches Elementarwerkzeug). Wir geben hier nur den Kern an, der ein asymmetrisches Kryptosystem darstellt. Es gibt Anklänge an das ElGamal-Kryptosystem, aber Unterschiede im Detail. Mit eingebaut ist ein Verfahren, das Elemente von $E-\{O\}$ kompakt darstellt: Anstelle von $(x,y)\in\mathbb{Z}^2_p$ speichern wir $x$ und ein Bit $b$. Im Allgemeinen gibt es keinen oder zwei Punkte auf $E_{A,B}$ mit erster Koordinate $x$ (außer bei den Nullstellen von $f$). Wenn $f(x)=x^3+Ax+B\not= 0$ ein Quadrat in $\mathbb{Z}_p$ ist, gibt es zwei passende Werte $y_1$ und $y_2$ mit $y_1+y_2=p$, von denen einer gerade und einer ungerade ist. Diese beiden Situationen werden durch $b$ unterschieden. $$Point-Compress: E-\{O\}\rightarrow\mathbb{Z}_p \times\{0,1\},(x,y)\rightarrow (x,y\ mod\ 2)$$ Dies ist eine injektive Funktion. Die Umkehrfunktion Point-Decompress benötigt die Funktion ,,Quadratwurzel modulo $p$'', die effizient berechnet werden kann, wenn $p+1$ durch $4$ teilbar ist, siehe ,,Entschlüsselung beim Rabin-Kryptosystem''. Daher verwendet man in der EC-Kryptographie vorzugsweise solche Primzahlen. Wenn man eine (und damit beide) Quadratwurzeln von $f(x)$ berechnet hat, wählt man als $y$ die gerade/ungerade davon, je nachdem ob $b=0$ oder $b=1$ ist, und gibt $(x,y)$ aus. *Simplified ECIES* Gegeben (und allen Beteiligten bekannt): Elliptische Kurve $E=E_{A,B}$ über $\mathbb{Z}_p$ (also $p,A,B$), zyklische Untergruppe $G=\langle P\rangle $ mit erzeugendem Element $P$, Kardinalität $N=|G|$, wobei $N$ eine Primzahl ist. Wir unterdrücken diese Angaben im Folgenden. (Sie sind aber Teil des öffentlichen Schlüssels und natürlich auch dem Empfänger Bob bekannt.) *Klartextmenge*: $X=\mathbb{Z}^*_p$. *Chiffretextmenge*: $Y=(\mathbb{Z}_p \times\{0,1\})\times\mathbb{Z}^*_p$. \begin{itemize*} \item (Paare aus: (komprimiertes) Element von $G$ und Element von $\mathbb{Z}^*_p$). \item Öffentliche Schlüssel: $K_{pub}=G$. Private Schlüssel: $K_{priv}=\mathbb{Z}_N$. \item Schlüsselmenge: $K=\{(Q,b)|Q\in K_{pub} = G,b\in K_{priv} =\mathbb{Z}_N,Q=bP\}$. \end{itemize*} *Schlüsselerzeugung*: (Gegeben sind $E$ [also $p,A,B$], $P$, $N$.) \begin{itemize*} \item Wähle $b\in\mathbb{Z}_N$ zufällig und berechne $Q=bP$ (schnelle Exponentiation). \item Schlüssel:$(Q,b)$. \item Der öffentliche Schlüssel ist $k_{pub}=Q$. \item Der private Schlüssel ist $k_{priv}=b$. \end{itemize*} *Verschlüsselungsfunktion* $E:X\times G\rightarrow Y$, als randomisierter Algorithmus. \begin{itemize*} \item Gegeben: Klartext $x\in\mathbb{Z}^*_p$. \item Öffentlicher Schlüssel $Q\in G$. \item Wähle zufällig $a\in\mathbb{Z}_N$ und berechne $(k,y) =aQ$ mit $k\in\mathbb{Z}^*_p$. //(Falls $k=0$, wähle neues $a$.) \item Berechne $E^a (x,Q)\leftarrow (Point-Compress(aP),x*k\ mod\ p) =: (y',y'');$ das Paar $(y',y'')\in(\mathbb{Z}_p\times\{0,1\})\times\mathbb{Z}^*_p$ ist der Chiffretext. \end{itemize*} Bemerkung: $k\in\mathbb{Z}^*_p$, die erste Komponente eines Punktes in $G$, wird durch eine Operation in $G$ erstellt, und dann wie beim One-Time-Pad (oder beim Vernam-System) benutzt, wobei diese Verschlüsselung durch Multiplikation in $\mathbb{Z}^*_p$ ausgeführt wird. *Entschlüsselungsfunktion* $D:Y\times\mathbb{Z}_N \rightarrow X$, als (deterministischer) Algorithmus. \begin{itemize*} \item Gegeben: Chiffretext $y=(y',y'')$ mit $y'\in\mathbb{Z}_p\times\{0,1\}$ und $y''\in\mathbb{Z}^*_p$. Privater Schlüssel $b$. \item Berechne $(x_1,y_1)\leftarrow Point-Decompress (y')$ //nun gilt $(x_1,y_1) =aP$ \item $(x_0,y_0)\leftarrow b(x_1,y_1)$ (in $G$, nun gilt $(x_0,y_0) = (ba)P=a(bP) =aQ= (k,y))$, und schließlich in $\mathbb{Z}^*_p$ \item $D((y',y''),b)\leftarrow y''*(x_0)^{-1}\ mod\ p$. \end{itemize*} Behauptung: Wenn $Q=bP$, dann gilt $D(E^a (x,Q),b) =x$, für jedes $x\in X$ und jedes $a$, für das $(k,y) =aQ\in\mathbb{Z}^*_p \times\mathbb{Z}_N$. (Dies gilt nach den Anmerkungen in der Beschreibung von $E$ und $D$.) \end{multicols} \end{document}