moderncryptography.tex

a very popular packet of cryptography tools,it encloses the most common used algorithm and protocols

{\bf Merkle-Hellman Verfahren} (auf Knapsackproblemen basierend).
\vskip +20 pt



1982 gab \index{Shamir, Adi} Shamir \cite{Shamir1982} einen Algorithmus zum
Brechen des Systems in polynomialer \index{Polynom} Zeit an, ohne das allgemeine
Knapsackproblem zu l"osen. Len \index{Adleman, Leonard} Adleman
\cite{Adleman1982} und Jeff Lagarias \index{Lagarias, Jeff}
\cite{Lagarias1983} gaben einen Algorithmus zum Brechen des 2-fachen
iterierten Merkle-Hellman Knapsack-Verschl"usselungsverfahrens in
polynomialer Zeit an. Ernst Brickell \index{Brickell, Ernst}
\cite{Brickell1985} gab schlie"slich einen Algorithmus zum Brechen des
mehrfachen iterierten Merkle-Hellman Knapsack-Verschl"usselungsverfahren in
polynomialer Zeit an. Damit war dieses Verfahren als
Verschl"usselungsverfahren ungeeignet. Dieses Verfahren liefert also eine
Einwegfunktion, deren Fallt"ur-In"-for"-ma"-tion (Verfremden des
0-1-Knapsackproblems) durch einen Gegner entdeckt werden k"onnte.


%---------------------------------------------------------------------
\subsection{Primfaktorzerlegung als Basis f"ur Public Key-Verfahren}\index{Primfaktor!Zerlegung}
%--------------------------------------------------------------------


%--------------------------------------------------------------------
\subsubsection[Das RSA-Verfahren]
{Das RSA-Verfahren\footnotemark}
\footnotetext{%
Mit CrypTool\index{CrypTool} k"onnen Sie praktische Erfahrungen
mit dem RSA-Verfahren sammeln: per Men"u {\bf Einzelverfahren 
\textbackslash{} RSA-Kryptosystem \textbackslash{} RSA-Demo}.
}\index{RSA} \hypertarget{RSAVerfahren}{} \label{rsaverfahren}

Bereits 1978 stellten R. \index{Rivest, Ronald} Rivest,
\index{Shamir, Adi} A. Shamir,  \index{Adleman, Leonard} L. Adleman
 \cite{RSA1978} das bis heute wichtigste 
asymmetrische Kryptographie-Verfahren vor.  \par

\index{Faktorisierung!Faktorisierungsproblem}
\index{Eulersche Phi-Funktion}
\begin{center}
\fbox{\parbox{12cm}{        
\underline{Schl"usselgenerierung:} \vskip + 5pt
Seien $p$ und $q$ zwei verschiedene Primzahlen und $N=pq.$ Sei $e$ eine frei w"ahlbare, zu $ \phi (N) $ \index{Primzahl!relative} relative Primzahl, d.h. $ \ggt (e,\phi (N))=1. $ Mit dem Euklidschen Algorithmus berechnet man die nat"urliche Zahl  $ d < \phi (N), $ so dass gilt

\[ ed \equiv 1 \mod \phi (N). \]
Dabei ist $ \phi $ die {\bf Eulersche Phi-Funktion}. 

Der Ausgangstext wird in Bl"ocke zerlegt und verschl"usselt, wobei jeder Block einen bin"aren Wert $ x^{(j)} \leq N $ hat. \vskip + 5 pt

\underline{"Offentlicher Schl"ussel:}
\[ N,e. \]
\underline{Privater Schl"ussel:}
\[ d. \]
\underline{Verschl"usselung:}
\[ y= e_{T} (x) = x^{e} \mod N.\]
\underline{Entschl"usselung:}
\[ d_{T} (y) = y^d \mod N \]
}}
\end{center}

\vskip +10 pt
{\bf RSA-Verfahren} (auf dem Faktorisierungsproblem basierend).
\vskip +20 pt

{\bf Bemerkung:} 
Die Eulersche Phi-Funktion ist definiert duch: $ \phi (N)$ ist die  Anzahl der zu $ N $ \index{teilerfremd} {} teilerfremden nat"urlichen Zahlen 
$ x \leq N. $ Zwei nat"urliche Zahlen $ a $ und $ b $ \index{teilerfremd} sind teilerfremd, falls $ \ggt (a,b)=1. $ 

F"ur die Eulersche Phi-Funktion gilt: $ \phi (1)=1,~\phi(2)=1,
~\phi(3)=2, ~\phi (4)=2, ~\phi(6)=2, ~\phi (10)= 4, ~\phi (15)=8. $

Zum Beispiel ist $ \phi (24)=8, $ weil 
$|\{ x <24 : \ggt (x,24) =1 \}| =|\{1,5,7,11,13,17,19,23\}|. $

Ist  $ p $ eine Primzahl, so gilt $ \phi (p)= p-1. $

Kennt man die verschiedenen Primfaktoren  $ p_1, \dots , p_k $ von $ N, $ so ist $ \phi (N) = N \cdot (1-\frac{1}{p_1}) \,
\cdots \, (1-\frac{1}{p_k}) $\footnote{Weitere Formeln finden sich in den
Artikel \hyperlink{Kapitel_3_8}{\glqq Einf"uhrung in die elementare Zahlentheorie
mit Beispielen\grqq, Kap. 3.8}.}.

Im Spezialfall $ N=pq $ ist $ \phi (N)= pq(1-1/p)(1-1/q) = p(1-1/p)q(1-1/q)=(p-1)(q-1).$
\\ \vskip +5 pt
\begin{center}
\begin{tabular}{|l|l|l|}\hline
$n$ & $\phi (n) $ & Die zu $ n $ teilerfremden nat"urlichen Zahlen kleiner $ n. $ \\ \hline
1 & 1 & 1  \\
2 & 1 & 1 \\
3 &  2 & 1, 2 \\ 
4 &  2 & 1, 3 \\ 
5 &  4 & 1, 2, 3, 4 \\ 
6 &  2 & 1, 5 \\ 
7 &  6 & 1, 2, 3, 4, 5, 6 \\ 
8 &  4 & 1, 3, 5, 7 \\ 
9 &  6 & 1, 2, 4, 5, 7, 8 \\ 
10 &  4 & 1, 3, 7, 9 \\ 
15 &  8 & 1, 2, 4, 7, 8, 11, 13, 14 \\ \hline
\end{tabular}
\end{center}
\vskip +5 pt 
Die Funktion $ e_T $  ist eine Einwegfunktion, deren Fallt"ur-Information die Primfaktorzerlegung von $ N $ ist.

Zur Zeit ist kein Algorithmus bekannt, der das Produkt zweier Primzahlen bei sehr gro"sen Werten geeignet schnell
zerlegen kann (z.B. bei mehreren hundert Dezimalstellen). Die heute schnellsten bekannten Algorithmen \cite{Stinson1995} zerlegen eine 
zusammengesetzte ganze Zahl $ N $ in einem Zeitraum proportional zu  
$ L(N)= e^{\sqrt{\ln (N) \ln (\ln (N))}}. $ 
\vskip +5 pt
\begin{center}
\begin{tabular}{|l||l|l|l|l|l|l|}\hline
$N$ & $ 10^{50} $ & $ 10^{100} $ & $ 10^{150} $ & $ 10^{200} $ & $ 10^{250} $ & $ 10^{300} $ \\ \hline
$L(N)$ & $ 1,42 \cdot 10^{10} $ &  $ 2,34  \cdot 10^{15} $ &  $ 3,26 \cdot 10^{19} $ &  $ 1,20 \cdot 10^{23} $ &  $ 1,86 \cdot 10^{26} $ &  $ 1,53 \cdot 10^{29} $ \\ \hline
\end{tabular}
\end{center}
\vskip +5 pt 
Solange kein besserer Algorithmus gefunden wird, hei"st dies, dass Werte der
Gr"o"senordnung $ 100 $ bis $ 200 $ Dezimalstellen zur Zeit sicher sind.
Einsch"atzungen der aktuellen Computertechnik besagen, dass eine Zahl mit $100$
Dezimalstellen bei vertretbaren Kosten in etwa zwei Wochen zerlegt werden
k"onnte. Mit einer teuren Konfiguration (z.B. im Bereich von 10 Millionen
US-Dollar) k"onnte eine Zahl mit $150$ Dezimalstellen in etwa einem Jahr zerlegt
werden.  Eine $200-$stellige Zahl d"urfte noch f"ur eine sehr lange Zeit
unzerlegbar bleiben, falls es zu keinem mathematischen Durchbruch kommt. Zum
Beispiel w"urde es etwa 1000 Jahre dauern, um eine 200-stellige Zahl mit den
bestehenden Algorithmen in Primfaktoren zu zerlegen; dies gilt selbst dann, wenn
$ 10^{12} $  Operationen pro Sekunde ausgef"uhrt werden k"onnten, was jenseits
der Leistung der heutigen Technik liegt und in der Entwicklung Milliarden von
Dollar kosten w"urde. Dass es aber nicht doch schon morgen zu einem
mathematischen Durchbruch kommt, kann man nie ausschlie"sen.

Bewiesen ist bis heute nicht, dass das Problem, RSA zu brechen "aquivalent zum
Faktorisierungsproblem \index{Faktorisierung!Faktorisierungsproblem} ist. Es ist
aber klar, dass wenn das Faktorisierungsproblem \glqq gel"ost\grqq {} ist, dass
dann das RSA-Verfahren nicht mehr sicher ist.


%--------------------------------------------------------------------
    \subsubsection{Rabin-Public Key-Verfahren (1979)}
%--------------------------------------------------------------------

F"ur \index{Rabin, Michael O.} \index{Rabin!Public-Key Verfahren} 
dieses Verfahren konnte gezeigt werden, dass es "aquivalent zum Brechen
des Faktorisierungsproblems ist. Leider ist dieses Verfahren anf"allig
gegen chosen-ciphertext-Angriffe.
\index{Angriff!Chosen-ciphertext}
\begin{center}
\fbox{\parbox{12cm}{        
Seien $ p $ und $ q $ zwei verschiedene Primzahlen mit $ p,q\equiv 3 \mod 4 $ und $ n = pq.$ Sei $ 0\leq B \leq n-1.$ \\
\underline{"Offentlicher Schl"ussel:}
\[ e=(n,B). \]
\underline{Privater Schl"ussel:}
\[ d=(p,q). \]
\underline{Verschl"usselung:}
\[ y= e_{T} (x) = x(x+B) \mod n.\]
\underline{Entschl"usselung:}
\[ d_{T} (y) = \sqrt{y + B^2/4} -B/2 \mod n. \]
}}
\end{center}

\vskip +10 pt
{\bf Rabin-Verfahren} (auf dem Faktorisierungsproblem basierend).
\vskip +20 pt

Vorsicht:
Wegen $ p,q \equiv 3 \mod 4 $  ist die Verschl"usselung (mit Kenntnis des Schl"ussels) leicht  zu berechnen. Dies ist nicht der Fall f"ur $ p \equiv 1 \mod 4. $ Au"serdem ist die Verschl"usselungsfunktion nicht injektiv: Es gibt genau vier verschiedene Quellcodes, die $ e_T(x) $  als Urbild besitzen $ x,-x-B,\omega (x+B/2)-B/2, -\omega(x+B/2)-B/2, $ dabei ist  $ \omega $  eine der vier Einheitswurzeln. Es muss also eine  Redundanz der Quellcodes geben, damit die Entschl"usselung trotzdem eindeutig bleibt!

Hintert"ur-Information ist die Primfaktorzerlegung von $ n = pq. $ 



%--------------------------------------------------------------------
       \subsection{Der diskrete Logarithmus als Basis f"ur Public Key-Verfahren}
%--------------------------------------------------------------------
Diskrete Logarithmen\index{Logarithmusproblem!diskret} sind die Grundlage f"ur eine gro"se Anzahl von Algorithmen von Public Key-Verfahren.

%--------------------------------------------------------------------
    \subsubsection{Der diskrete Logarithmus in $ \Z_p^* $}
%--------------------------------------------------------------------
Sei $ p $ eine Primzahl, und sei $g$ ein Erzeuger der zyklischen multiplikativen Gruppe $ \Z_p^\ast=\{1,\ldots,p-1\} $. Dann ist die diskrete Exponentialfunktion zur Basis $ g $  definiert durch
\[ e_g : k \longrightarrow y:=g^k \mod p, \quad 1\leq k \leq p-1. \]
Die Umkehrfunktion wird diskrete Logarithmusfunktion $ \log_g $ genannt; es gilt
\[ \log_g (g^k) =k. \]
\index{Exponentialfunktion!diskrete} Unter dem Problem des diskreten Logarithmus (in $ \Z_p^\ast$) versteht man das folgende:
\[ \text{Gegeben } p,g \text{~(ein Erzeuger der Gruppe } \Z_p^* \text{) und } y, \text{ bestimme } k \text{ so, dass } y=g^k \mod p \text{ gilt.}\]
Die Berechnung des diskreten Logarithmus ist viel schwieriger als die Auswertung der diskreten Exponentialfunktion (siehe Kapitel \ref{MultOrdPrimitveRoot}).
Es gibt viele Verfahren zur Berechung des diskreten Logarithmus \cite{Stinson1995}:
\vskip + 5pt
\begin{center}
\begin{tabular}{|l|l|}\hline
Name                 &        Komplexit"at \\ \hline \hline
Baby-Step-Giant-Step &         $ O(\sqrt{p}) $ \\ \hline
Silver-Pohlig-Hellman &    polynomial in $ q, $ dem gr"o"sten \\
&  Primteiler von $ p-1. $ \\ \hline
Index-Calculus &             $ O(e^{(1+o(1)) \sqrt{\ln (p) \ln (\ln (p))}}) $ \\ \hline
\end{tabular}
\end{center}
\vskip +5 pt
\index{Silver} \index{Pohlig, S. C.} \index{Hellman, Martin}
\index{Baby-Step-Giant-Step}


%--------------------------------------------------------------------
\subsubsection[Diffie-Hellman-Schl"usselvereinbarung]
{Diffie-Hellman-Schl"usselvereinbarung\footnotemark}
\footnotetext{%
In CrypTool\index{CrypTool} ist dieses Austauschprotokoll visualisiert:
Sie k"onnen die einzelnen Schritte mit konkreten Zahlen nachvollziehen 
per Men"u {\bf Einzelverfahren \textbackslash{} Protokolle \textbackslash{} Diffie-Hellman-Demo}.
}

\index{Schl""usselaustausch!Diffie-Hellman} 
\index{Diffie, Whitfield} 
\index{Hellman, Martin} 
\index{Diffie-Hellman}
\hypertarget{DH-KeyExch}{} \label{DH-KeyExch}

Die Mechanismen und Algorithmen der klassischen Kryptographie greifen erst dann, wenn die Teilnehmer bereits den geheimen Schl"ussel ausgetauscht haben. Im Rahmen der klassischen Kryptographie  f"uhrt kein Weg daran vorbei, dass Geheimnisse kryptographisch ungesichert ausgetauscht werden m"ussen. Die Sicherheit der "Ubertragung muss hier durch nicht-kryptographische Methoden erreicht werden. Man sagt dazu, dass man zum Austausch der Geheimnisse einen geheimen Kanal braucht; dieser kann physikalisch oder organisatorisch realisiert sein. \\