moderncryptography.tex

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

% $Id: moderncryptography.tex 1205 2005-07-04 13:58:13Z koy $
\setcounter{satz}{0}
\setcounter{definition}{0}

\newcommand{\NT}{\vspace*{0.2\baselineskip}\\}
\newcommand{\HZ}{\vspace*{0.5\baselineskip}}
\newcommand{\R}{\text{I}\!\text{R}}
\newcommand{\N}{\text{I}\!\text{N}}
\newcommand{\Q}{\text{Q}\!\!\!\text{l}\,\,}
\newcommand{\C}{\text{C}\!\!\!\text{l}\,\,}
\newcommand{\K}{\text{I}\!\text{K}}
\newcommand{\Z}{\mathbf{\mathbb{Z}}}
%--------------------------------------- matheScript-Zeichen definieren
\newcommand{\fs}{\mathscr{F}}  
\newcommand{\es}{\mathscr{E}}  
\newcommand{\cs}{\mathscr{C}}  
\newcommand{\gs}{\mathscr{G}}
\newcommand{\is}{\mathscr{I}}
\newcommand{\os}{\mathscr{O}}
\newcommand{\ks}{\mathscr{K}}
\newcommand{\qs}{\mathscr{Q}}
\newcommand{\us}{\mathscr{U}}
\newcommand{\hs}{\mathscr{H}}
\newcommand{\ps}{\mathscr{P}}
\newcommand{\as}{\mathscr{A}}
\newcommand{\rs}{\mathscr{R}}
\newcommand{\bs}{\mathscr{B}}
%-------------------------------------
\newcommand{\PG}{\text{I}\!\text{P}}
\newcommand{\carre}{\square}
\newcommand{\ncarre}{/\negthickspace\negthickspace\square}
\newcommand{\ncarreq}{{\ncarre}_q}
\newcommand{\ncarree}{/\negthickspace\negthickspace\negthickspace\square}
\newcommand{\ncarrepi}{{\ncarre}_{p^i}}
\newcommand{\mc}[1]{{\cal #1}}
\newcommand{\Char}{\text{char}}
\newcommand{\Aut}{\text{Aut}}
\newcommand{\Fix}{\text{Fix}}
\newcommand{\Syl}{\text{Syl}}
\newcommand{\Bild}{\text{Bild}}
\newcommand{\ggt}{\text{ggT}}
\newcommand{\kgv}{\text{kgV}}
\newcommand{\Id}{\text{Id}}
\newcommand{\nqcarre}{{\ncarre}_{q^2}}

\setlength{\fboxrule}{.4pt}
\setlength{\fboxsep}{4pt}

\newpage
%**************************************************************************************************************************
\section{Die mathematischen Ideen hinter der modernen Kryptographie}
\label{Chapter_ModernCryptography}
\hypertarget{Chapter_ModernCryptography}{}
%**************************************************************************************************************************
(Oyono R./ Esslinger B., Sep. 2000, Updates Nov. 2000, Feb. 2003)

%--------------------------------------------------------------------------------------------------------------------------
\subsection{Einwegfunktionen mit Fallt"ur und Komplexit"atsklassen}
%--------------------------------------------------------------------------------------------------------------------------
\index{Kryptographie!moderne} \index{Einwegfunktion}
Eine {\bf Einwegfunktion} \hypertarget{OneWayFunktion1}{} ist eine effizient zu 
berechnende Funktion, deren Umkehrung jedoch nur mit 
extrem hohem Rechenaufwand -- jedoch praktisch unm"oglich -- zu berechnen ist.\par

Etwas genauer formuliert:  Eine Einwegfunktion ist eine Abbildung $ f $ einer Menge $ X $ in eine Menge $ Y, $ so dass $ f(x) $ f"ur jedes Element $ x $ von $ X $ leicht zu berechnen ist, w"ahrend es f"ur (fast) jedes $ y $ aus $ Y $  praktisch unm"oglich ist, ein Urbild $ x $ (d.h. ein $ x $ mit $ f(x)=y $) zu finden.\par

Ein allt"agliches Beispiel f"ur eine Einwegfunktion ist ein Telefonbuch: die auszuf"uhrende Funktion ist die, einem Namen die entsprechende Telefonnummer zuzuordnen. Da die Namen alphabetisch geordnet sind, ist diese Zuordnung einfach auszuf"uhren. Aber ihre Invertierung, also die Zuordnung eines Namens zu einer gegebenen Nummer, ist offensichtlich schwierig, wenn man nur ein Telefonbuch zur Verf"ugung hat. \par

Einwegfunktionen spielen in der Kryptographie eine entscheidende Rolle. Fast alle kryptographischen Begriffe kann man durch Verwendung des Begriffs Einwegfunktion umformulieren. Als Beispiel betrachten wir die Public Key-Verschl"usselung \index{Verschl""usselung!Public Key} (asymmetrische Kryptographie):\par

Jedem Teilnehmer $ T $ des Systems wird ein privater \index{Schl""ussel!privat}
\index{Schl""ussel!""offentlich} Schl"ussel $d_T$~\mbox{und} ein sogenannter "offentlicher Schl"ussel $ e_T $   zugeordnet. Dabei muss die folgende Eigenschaft (Public Key-Eigenschaft) gelten:\\
F"ur einen Gegner, der den "offentlichen Schl"ussel $ e_T $  kennt, ist es praktisch unm"oglich, den privaten Schl"ussel  $ d_T $ zu bestimmen.\par

Zur Konstruktion n"utzlicher Public Key-Verfahren sucht man also eine Einwegfunktion, die in einer Richtung \glqq einfach\grqq {} zu berechnen, die in der anderen Richtung jedoch \glqq schwer\grqq {} (praktisch unm"oglich) zu berechnen ist, solange eine bestimmte zus"atzliche Information \index{Einwegfunktion!mit Fallt""ur} (Fallt"ur) nicht zur Verf"ugung steht. Mit der zus"atzlichen Information kann die Umkehrung effizient gel"ost werden. Solche Funktionen nennt man {\bf Einwegfunktionen mit Fallt"ur} (trapdoor one-way function). Im obigen Fall ist $ d_T $ die Fallt"ur-In"-for"-ma"-tion. \par

Dabei bezeichnet man ein Problem als \glqq einfach\grqq, wenn es in \index{Laufzeit!polynomial} \index{Polynom} polynomialer Zeit als Funktion der L"ange der Eingabe l"osbar ist, d.h. wenn es so gel"ost werden kann, dass der Zeitaufwand sich als polynomiale Funktion in Abh"angigkeit der L"ange der Eingabe darstellen l"asst. 
Wenn die L"ange der Eingabe $ n $ Bits betr"agt, so ist die Zeit der Berechnung der Funktion proportional zu $ n^{a}, $ wobei $ a $  eine Konstante ist. Man sagt, dass die \index{Komplexit""at} Komplexit"at solcher Probleme $ O(n^{a}) $ betr"agt (Landau- oder Big-O-Notation). 

Vergleicht man 2 Funktionen  $ 2^n $  und   $ n^{a} $, wobei $ a $  
eine Konstante ist, dann gibt es immer einen Wert f"ur  $ n $, ab dem
f"ur alle weiteren $ n $ gilt: $ n^{a}  <  2^n $. 
Die Funktion  $ n^{a} $  hat eine geringere Komplexit"at.
Z.B. f"ur $ a=5 $ gilt: ab der L"ange $ n=23 $ ist 
$ 2^n > n^5 $ ~\mbox{und} danach w"achst $ 2^n $ auch deutlich 
schneller \
[($ 2^{22}= 4.194.304 $, $ 22^5= 5.153.632 $), \
 ($ 2^{23}= 8.388.608 $, $ 23^5= 6.436.343 $), \
 ($ 2^{24}=16.777.216 $, $ 24^5= 7.962.624 $)].\par 
% "\mbox" nur, weil bei Ausdruck bei be die Blanks stets falsch sa遝n:
%  "n^5un d"

Der Begriff \glqq praktisch unm"oglich\grqq {} ist etwas schwammiger. 
Allgemein kann man sagen, ein Problem ist \index{Laufzeit!effizient}
nicht effizient l"osbar, wenn der zu seiner L"osung ben"otigte Aufwand
schneller w"achst als die polynomiale \index{Polynom} Zeit als Funktion der Gr"o"se der
Eingabe. Wenn beispielsweise die L"ange der Eingabe $ n $  Bits betr"agt
und die Zeit zur Berechnung der Funktion proportional zu $ 2^n $ ist, 
so gilt gegenw"artig: die Funktion ist f"ur $n > 80$ praktisch nicht zu 
berechnen.

Die Entwicklung eines praktisch einsetzbaren Public Key-Verfahrens h"angt daher von der Entdeckung einer geeigneten Einwegfunktion mit Fallt"ur ab.\par

Um Ordnung in die verwirrende Vielfalt von m"oglichen Problemen und ihre Komplexit"aten zu bringen, fasst man Probleme mit "ahnlicher Komplexit"at zu Klassen zusammen.

Die wichtigsten Komplexit"atsklassen  sind die Klassen \textbf{P} und \textbf{NP}: 

\begin{itemize}

    \item Die Klasse \textbf{P}: Zu dieser Klasse geh"oren diejenigen Probleme, die mit polynomialem \index{Polynom} Zeitaufwand l"osbar sind.
    
    \item Die Klasse \textbf{NP}: Bei der Definition dieser Klasse betrachten wir nicht den Aufwand zur L"osung eines Problems, sondern den Aufwand zur Verifizierung einer gegebenen L"osung. Die Klasse \textbf{NP} besteht aus denjenigen Problemen, bei denen die Verifizierung einer gegebenen L"osung mit polynomialem Zeitaufwand m"oglich ist. Dabei bedeutet der Begriff \textbf{NP} \glqq nichtdeterministisch\grqq {} polynomial \index{Polynom} und bezieht sich auf ein Berechnungsmodell, d.h. auf einen nur in der Theorie existierenden Computer, der richtige L"osungen nichtdeterministisch \glqq raten\grqq {} und dies dann in polynomialer Zeit verifizieren kann.

\end{itemize}

Die Klasse \textbf{P} ist in der Klasse \textbf{NP} enthalten. Ein ber"uhmtes offenes Problem ist die Frage, ob $ \textbf{P} \neq \textbf{NP} $ gilt oder nicht, d.h. ob \textbf{P} eine echte Teilmenge ist oder nicht. Eine wichtige Eigenschaft der Klasse \textbf{NP} ist, dass sie auch sogenannte \glqq \textbf{NP}-vollst"andige\grqq {} Probleme enth"alt. Dies sind Probleme, welche die Klasse \textbf{NP} im folgenden Sinne vollst"andig repr"asentieren: Wenn es einen \glqq guten\grqq {} Algorithmus f"ur ein solches Problem gibt, dann existieren f"ur alle Probleme aus \textbf{NP} \glqq gute\grqq {} Algorithmen. Insbesondere gilt: wenn auch nur ein vollst"andiges Problem in \textbf{P} l"age, d.h. wenn es einen polynomialen \index{Polynom} L"osungsalgorithmus f"ur dieses Problem g"abe, so w"are \textbf{P}=\textbf{NP}. In diesem Sinn sind die \textbf{NP}-vollst"andigen Probleme die schwierigsten Probleme in \textbf{NP}.

Viele kryptographische Protokolle sind so gemacht, dass die \glqq guten\grqq {} Teilnehmer nur Probleme aus \textbf{P} l"osen m"ussen, w"ahrend sich ein Angreifer vor Probleme aus \textbf{NP} gestellt sieht.

Man wei"s leider bis heute nicht, ob es Einwegfunktionen "uberhaupt gibt. Man kann aber zeigen, dass Einwegfunktionen genau dann existieren, wenn $ \textbf{P} \neq \textbf{NP} $ gilt \cite[S.63]{Balcazar1988}.
\vskip +5pt

Es gab immer wieder die Aussage, jemand habe die "Aquivalenz bewiesen, z.B.

\href{http://www.geocities.com/st\_busygin/clipat.html}{\texttt{http://www.geocities.com/st\_busygin/clipat.html}}, 

aber bisher erwiesen sich diese Aussagen stets als falsch.

Es wurden eine Reihe von Algorithmen f"ur Public Key-Verfahren vorgeschlagen. Einige davon erwiesen sich, obwohl sie zun"achst vielversprechend erschienen, als polynomial \index{Polynom} l"osbar. Der ber"uhmteste durchgefallene Bewerber ist der Knapsack mit Fallt"ur, der von Ralph Merkle \cite{Merkle1978} vorgeschlagen wurde.


\newpage
%--------------------------------------------------------------------
       \subsection{Knapsackproblem als Basis f"ur Public Key-Verfahren} \index{Kryptographie!Public Key}
%--------------------------------------------------------------------
%--------------------------------------------------------------------
    \subsubsection{Knapsackproblem} \index{Knapsack}

%--------------------------------------------------------------------

Gegeben $ n $ Gegenst"ande $ G_1, \dots, G_n $ mit den Gewichten $ g_1, \dots g_n $ und den Werten $w_1, \cdots, w_n. $ Man soll wertm"a"sig so viel wie m"oglich unter Beachtung einer oberen Gewichtsschranke $ g $ davontragen. Gesucht ist also eine Teilmenge von $ \{ G_1, \cdots,G_n\}, $ etwa $ \{G_{i_1}, \dots ,G_{i_k} \}, $ so dass  $ w_{i_1}+ \cdots +w_{i_k} $ maximal wird unter der Bedingung $  g_{i_1}+ \cdots +g_{i_k} \leq g. $ \par
Derartige Fragen sind sogenannte {\bf NP}-vollst"andige Probleme (nicht \index{Laufzeit!nicht polynomial NP} deterministisch polynomial\index{Polynom}), die aufwendig zu berechnen sind.\index{Knapsack}

Ein Spezialfall des Knapsackproblems ist:\\
Gegeben sind die nat"urlichen Zahlen $ a_1, \dots, a_n $   und $ g .$
Gesucht sind  $ x_1, \dots, x_n \in \{ 0,1\} $  mit $ g = \sum_{i=1}^{n}x_i a_i $  (wo also $ g_i = a_i = w_i $ gew"ahlt ist).
Dieses Problem hei"st auch  {\bf 0-1-Knapsackproblem} und wird mit $ K(a_1, \dots, a_n;g) $  bezeichnet.\\

Zwei 0-1-Knapsackprobleme  $ K(a_1, \dots, a_n;g) $   und  $ K(a'_1, \dots, a'_n;g') $  hei"sen kongruent, falls es zwei \index{teilerfremd} teilerfremde Zahlen $ w $ und $ m $ gibt, so dass
\begin{enumerate}
    \item $ m > \max \{ \sum_{i=1}^n a_i , \sum_{i=1}^n a'_i \}, $

    \item $ g \equiv wg' \mod m, $

    \item $ a_i \equiv w a'_i \mod m $ f"ur alle $ i=1, \dots, n.$

\end{enumerate}
 
{\bf Bemerkung:}
Kongruente 0-1-Knapsackprobleme haben dieselben L"osungen.
Ein schneller Algorithmus zur Kl"arung der Frage, ob zwei 0-1-Knapsackprobleme kongruent sind, ist nicht bekannt.

Das L"osen eines 0-1-Knapsackproblems kann durch Probieren der $ 2^n $   M"oglichkeiten f"ur $ x_1, \dots, x_n $   erfolgen. Die beste Methode erfordert $ O(2^{n/2}) $  Operationen, was f"ur $ n=100 $  mit $ 2^{100} \approx 1,27 \cdot 10^{30} $  und  $ 2^{n/2} \approx 1,13 \cdot 10^{15} $ f"ur Computer eine un"uberwindbare H"urde darstellt.
Allerdings ist die L"osung f"ur spezielle $ a_1, \dots, a_n $   recht einfach zu finden, etwa f"ur $ a_i = 2^{i-1}. $  Die bin"are Darstellung von $ g $ liefert unmittelbar $ x_1, \dots, x_n$. Allgemein ist die L"osung des 0-1-Knapsackproblems leicht zu finden, falls eine \index{Permutation} Permutation\footnote{Eine Permutation\index{Permutation} $\pi$ der Zahlen $1, \dots, n$ ist die Vertauschung der Reihenfolge, in der
diese Zahlen aufgez"ahlt werden. Beispielsweise ist eine Permutation $\pi$ von $(1,2,3)$ gleich $(3,1,2),$ also $\pi(1) = 3$, $\pi(2) =1$ 
und $\pi(3) = 2$.} 
$ \pi $  von $ 1, \dots, n $  mit $ a_{\pi (j)} > \sum_{i=1}^{j-1} a_{\pi(i)} $  existiert. Ist zus"atzlich $ \pi $ die Identit"at, d.h. $ \pi(i)=i $ f"ur $ i=1,2,\dots,n, $ so hei"st die Folge $ a_1, \dots , a_n $ superwachsend.
Der folgende Algorithmus l"ost das Knapsackproblem mit superwachsender Folge im Zeitraum von $ O(n). $
\newpage
\begin{center}

\fbox{\parbox{12cm}{        
\begin{tabbing}
\hspace*{0.5cm} \= \hspace*{0.5cm} \= \hspace*{0.5cm} \= \kill
\>{\bf for} $ i=n $ {\bf to} 1 {\bf do} \\
\>\> {\bf if} $ T\geq a_i $ {\bf then}\\
\>\> \> $ T:=T-s_i $ \\
\>\>\> $ x_i:=1 $ \\
\>\> {\bf else} \\
\>\>\> $ x_i:=0 $\\
\>{\bf if} $ T=0 $ {\bf then} \\
\>\> $ X:=(x_1, \dots, x_n) $ ist die L"osung. \\
\>{\bf else} \\
\>\> Es gibt keine L"osung.
\end{tabbing}
}}
\end{center}
\vskip +10 pt
{\bf Algorithmus 1.} L"osen von Knapsackproblemen mit superwachsenden Gewichten
\vskip +20 pt


%--------------------------------------------------------------------
\subsubsection{Merkle-Hellman Knapsack-Verschl"usselung}
%--------------------------------------------------------------------
\index{Hellman, Martin} \index{Merkle, Ralph} 

1978 gaben Merkle und Hellman \cite{Merkle1978} \index{Verschl""usselung!Merkle-Hellman} ein Public Key-Verschl"usselungs-Verfahren an, das darauf beruht, das leichte 0-1-Knapsackproblem mit einer superwachsenden Folge in ein kongruentes mit einer nicht superwachsenden Folge zu \glqq verfremden\grqq. Es ist eine Blockchiffrierung, die bei jedem Durchgang einen $n$ Bit langen Klartext chiffriert.
\index{Knapsack!Merkle-Hellman}
Genauer:
\newpage

\begin{center}
\fbox{\parbox{12cm}{        
Es sei $ (a_1, \dots, a_n) $ superwachsend. Seien $ m $ und $ w $ zwei teilerfremde Zahlen mit $ m > \sum_{i=1}^{n} a_i $ und $ 1\leq w \leq m-1. $ W"ahle $\bar{w} $ mit $ w \bar{w} \equiv 1 \mod m $ die modulare Inverse von $ w $ und setze $ b_i:= wa_i \mod m, $ $ 0\leq b_i < m $ f"ur $ i=1, \dots ,n, $ und pr"ufe, ob die Folge $ b_1, \dots b_n $ nicht superwachsend ist. Danach wird eine Permutation $ b_{\pi (1)}, \dots , b_{\pi(n)} $ von $ b_1, \dots , b_n $ publiziert und insgeheim die zu $ \pi $ inverse Permutation $ \mu $ festgehalten. Ein Sender schreibt seine Nachricht in Bl"ocke $ (x_1^{(j)}, \dots, x_n^{(j)}) $ von Bin"arzahlen der L"ange $ n $ und bildet
\[ g^{(j)}:= \sum_{i=1}^n x_{i}^{(j)} b_{\pi(i)} \]
und sendet $ g^{(j)}, (j=1,2, \dots). $\par
Der Schl"usselinhaber bildet
\[ G^{(j)}:=\bar{w} g^{(j)} \mod m ,\quad 0 \leq G^{(j)} < m \]
und verschafft sich die $ x_{\mu(i)}^{(j)} \in \{ 0,1\} $ (und somit auch die $ x_i^{(j)} $) aus
\begin{eqnarray*}
G^{(j)} & \equiv & \bar{w} g^{(j)} = \sum_{i=1}^n x_i^{(j)} b_{\pi (i)} \bar{w} \equiv \sum_{i=1}^n x_i^{(j)} a_{\pi (i)} \mod m \\
& = & \sum_{i=1}^n x_{\mu (i)}^{(j)} a_{\pi (\mu (i))} = \sum _{i=1}^n x_{\mu (i)}^{(j)} a_i \mod m, 
\end{eqnarray*}
indem er die leichten 0-1-Knapsackprobleme $ K(a_1,\dots,a_n;G^{(j)}) $ mit superwachsender Folge $ a_1, \dots,a_n $ l"ost.
}}
\end{center}
\vskip +10 pt