moderncryptography.tex

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

Das Revolution"are der modernen Kryptographie ist unter anderem, dass man keine geheimen Kan"ale mehr braucht: Man kann geheime Schl"ussel "uber nicht-geheime, also "offentliche Kan"ale vereinbaren. \\
Ein Protokoll, das dieses Problem l"ost, ist das von Diffie und Hellman.\\ %\enlargethispage{+20pt}

\newpage
\begin{center}
\fbox{\parbox{12cm}{   
Zwei Teilnehmer $ A $ und $ B $ wollen einen gemeinsamen geheimen Schl"ussel vereinbaren. \par    
Sei $ p $ eine Primzahl und $ g $ eine nat"urliche Zahl. Diese beide Zahlen m"ussen nicht geheim sein. \\
Zun"achst w"ahlen sich die beiden Teilnehmer je eine geheime Zahl $ a $ bzw. $ b. $ Daraus bilden sie die Werte $ \alpha = g^{a}\mod p $ und $ \beta = g^b \mod p. $ Dann werden die Zahlen $ \alpha $ und $ \beta $ ausgetauscht. Schlie"slich potenziert jeder den erhaltenen Wert mit seiner geheimen Zahl und erh"alt $ \beta^{a} \mod p $ bzw. $ \alpha^b \mod p. $\\
Damit gilt
\[ \beta^{a} \equiv (g^b)^{a} \equiv g^{ba} \equiv g^{ab} \equiv (g^{a})^b \equiv \alpha^b \mod p \]
}}
\end{center}

\vskip +10 pt
{\bf Diffie-Hellman-Schl"usselvereinbarung}.
\vskip +20 pt


Die Sicherheit des {\bf Diffie-Hellman-Protokolls} h"angt eng mit der Berechnung der diskreten Logarithmus modulo $p$ zusammen. Es wird sogar vermutet, dass diese Probleme "aquivalent sind.


%--------------------------------------------------------------------
\subsubsection{ElGamal-Public Key-Verschl"usselungsverfahren in $ \Z_p^\ast$}
%--------------------------------------------------------------------
\index{ElGamal!Public Key}
Indem man das Diffie-Hellman Schl"usselvereinbarungsprotokoll 
\index{Diffie-Hellman} \index{Verschl""usselung!ElGamal-Public Key} 
leicht variiert, kann man einen asymmetrischen Verschl"usselungsalgorithmus
erhalten. Diese Beobachtung geht auf Taher ElGamal zur"uck.
\begin{center}
\fbox{\parbox{12cm}{        
Sei $p$ eine Primzahl, so dass der diskrete Logarithmus in $\Z_p$ schwierig zu berechnen ist. 
Sei $ \alpha \in \Z_p^\ast $ ein primitives Element. Sei $a \in \N$ eine nat"urliche Zahl und $ \beta = \alpha^{a}  \mod p. $\\
\underline{"Offentlicher Schl"ussel:}
\[ p,\alpha,\beta. \]
\underline{Privater Schl"ussel:}
\[a. \]
Sei $ k \in \Z_{p-1} $ eine zuf"allige Zahl und $ x \in \Z_p^{\ast} $ der Klartext. \\
\underline{Verschl"usselung:}
\[ e_T(x,k)=(y_1,y_2), \]
wobei
\[ y_1=\alpha^k \mod p,\]
und
\[ y_2 = x\beta^k \mod p.\]
\underline{Entschl"usselung:}
\[ d_T(y_1,y_2)= y_2 (y_1^{a})^{-1} \mod p. \]
}}
\end{center}

\vskip +10 pt
{\bf ElGamal Verfahren} (auf dem diskreten Logarithmusproblem basierend).
\vskip +20 pt


%-----------------------------------------------------------------------------------------------------------------------
\subsubsection{Verallgemeinertes ElGamal-Public Key-Verschl"usselungsverfahren }
%-----------------------------------------------------------------------------------------------------------------------

Den diskreten Logarithmus kann man in beliebigen endlichen \index{Gruppen} Gruppen $ (G, \circ) $ verallgemeinern. Im folgenden geben wir einige Eigenschaften "uber die Gruppe $G$ an, damit das diskrete Logarithmusproblem schwierig wird. \\
\index{Exponentialfunktion!Berechnung}
\paragraph{Berechnung der diskreten Exponentialfunktion}
Sei $ G $ eine Gruppe mit der Operation $ \circ $ und $ g \in G. $ Die (diskrete) Exponentialfunktion  zur Basis $ g $ ist definiert durch
\[e_g: k \longmapsto g^k, \quad \text{ f"ur alle } k \in \N. \]
Dabei definiert man
 \[ \ g^{k}:=\underbrace{g \circ \ldots \circ g}_{k \text{ mal}}.\]
Die Exponentialfunktion ist leicht zu berechnen:
% \begin{lemma}
\vskip +20 pt \noindent
{\bf Lemma.}\par
\nopagebreak[4]
{\em
  Die Potenz $ g^k $ kann in h"ochstens $ 2 \log_2 k $ Gruppenoperationen berechnet werden.
}
% \end{lemma}
\vskip +10 pt

\begin{Beweis}{}
Sei $ k=2^n + k_{n-1} 2^{n-1} + \cdots + k_1 2 + k_0 $ die Bin"ardarstellung von $k. $ Dann ist $ n \leq \log_2 (k), $  denn $ 2^n \leq k < 2^{n+1}. $ $ k $ kann in der Form $ k=2k' + k_0 $ mit $ k'= 2^{n-1} + k_{n-1} 2^{n-2} + \cdots + k_1 $ geschrieben werden. Es folgt 
\[ g^k = g^{2k'+k_0}= (g^{k'})^2 g^{k_0} .\]
Man erh"alt also $ g^k $ aus $ g^{k'} $ indem man einmal quadriert und eventuell mit $ g $ multipliziert. Damit folgt die Behauptung durch Induktion nach $ n. $
\end{Beweis}

\vskip +10 pt
{\bf Problem \index{Logarithmusproblem!diskret} des diskreten Logarithmus'}
\vskip +10 pt
\begin{center}
\fbox{\parbox{12cm}{ 
Sei $ G $ eine endliche Gruppe mit der Operation $ \circ. $ Sei $ \alpha \in G $ und $ \beta \in H=\{ \alpha^{i}: i\geq 0\}. $ \\
Gesucht ist der eindeutige $ a \in \N $ mit $ 0 \leq a \leq |H| -1 $ und $ \beta = \alpha^{a}. $ \\       
Wir bezeichnen $ a $ mit $ \log_\alpha (\beta). $
}}
\end{center}

\paragraph{Berechung des diskreten Logarithmus'}
Ein einfaches Verfahren zur Berechnung des diskreten Logarithmus' eines Gruppenelements, das wesentlich effizienter ist als das blo"se Durchprobieren aller m"oglichen Werte f"ur $ k, $ ist der \index{Baby-Step-Giant-Step} Baby-Step-Giant-Step-Algorithmus.
\begin{satz}[Baby-Step-Giant-Step-Algorithmus]\label{thm-cry-bsgs}
Sei $ G $ eine Gruppe  und $ g \in G. $ Sei $ n $ die kleinste nat"urliche Zahl mit $ |G|\leq n^2. $ Dann kann der diskrete Logarithmus eines Elements $ h 
\in G $ zur Basis $ g $ berechnet werden, indem man zwei Listen mit jeweils $ n $ Elementen erzeugt und diese Listen vergleicht.\\
Zur Berechnung dieser Listen braucht man $ 2n $ Gruppenoperationen.
\end{satz}

\begin{Beweis}{}
  Zuerst bilde man die zwei Listen \\
Giant-Step-Liste: $ \{1,g^n,g^{2n}, \ldots, g^{n \cdot n}\}, $\\
Baby-Step-Liste: $ \{ hg^{-1} , hg^{-2} , \ldots , hg^{-n} \}. $ \par
Falls $ g^{jn} = hg^{-i}, $ also $ h = g^{i+jn}, $ so ist das Problem gel"ost. Falls die Listen disjunkt sind, so ist $ h $ nicht als $ g^{i + jn}, i, j\leq n,$ darstellbar. Da dadurch alle Potenzen von $ g $ erfasst werden, hat das Logarithmusproblem keine L"osung.
\end{Beweis}

Man kann sich mit Hilfe des Baby-Step-Giant-Step-Algorithmus klar machen, dass die Berechnung des diskreten Logarithmus' sehr viel schwieriger ist als die Berechnung der diskreten Exponentialfunktion. Wenn die auftretenden Zahlen etwa 1000 Bit L"ange haben, so ben"otigt man zur Berechnung von $ g^k $ nur etwa 2000 Multiplikationen, zur Berechnung des diskreten Logarithmus' mit dem Baby-Step-Giant-Step-Algorithmus aber etwa $ 2^{500} \approx 10^{150} $ Operationen. \\
Neben dem Baby-Step-Giant-Step-Algorithmus gibt es noch zahlreiche andere Verfahren zur Berechnung des diskreten Logarithmus' \cite{Stinson1995}.

\paragraph{Der Satz von Silver-Pohlig-Hellman}
In endlichen abelschen Gruppen l"asst sich das  diskrete Logarithmusproblem in Gruppen kleinerer Ordnung reduzieren.
\begin{satz}[Silver-Pohlig-Hellman]\label{thm-cry-pohe}
Sei $ G $ eine endliche abelsche Gruppe mit $ |G|= p_1^{a_1} p_2^{a_2} \cdot \ldots \cdot p_s^{a_s}. $ Dann l"asst sich das diskrete Logarithmusproblem in $ G $ auf das L"osen von Logarithmenproblemen in Gruppen der Ordnung $ p_1, \ldots , p_s $ zur"uckf"uhren.
\end{satz}

Enth"alt $ |G| $ eine \glqq dominanten\grqq {} Primteiler $ p ,$ so ist die Komplexit"at \index{Komplexit""at} des Logarithmenproblem ungef"ahr
\[ O(\sqrt{p}). \]
Wenn also das Logarithmusproblem schwer sein soll, so muss die Ordnung der verwendeten Gruppe $ G $ einen gro"sen Primteiler haben. Insbesondere gilt, wenn die diskrete Exponentialfunktion in der Gruppe $ \Z_p^{\ast} $ eine Einwegfunktion sein soll, so muss $ p -1 $ einen gro"sen Primteiler haben.


\begin{center}
\fbox{\parbox{12cm}{    
Sei $ G $ eine endliche Gruppe  mit Operation $  \circ, $ und sei $ \alpha \in G, $ so dass der diskrete Logarithmus in $ H =\{ \alpha^{i}: i \geq 0 \} $ schwer ist. Sei $ a $ mit $   0 \leq a \leq |H| -1 $ und sei $ \beta = \alpha^{a}. $\\
\underline{"Offentlicher Schl"ussel:}
\[ \alpha,\beta. \]
\underline{Privater Schl"ussel:}
\[a. \]
Sei $ k \in \Z_{|H|} $ eine zuf"allige Zahl und $ x \in G $ ein Klartext. \\
\underline{Verschl"usselung:}
\[ e_T(x,k)=(y_1,y_2), \]
wobei
\[ y_1=\alpha^k, \]
und
\[ y_2 = x\circ \beta^k .\]
\underline{Entschl"usselung:}
\[ d_T(y_1,y_2)= y_2\circ (y_1^{a})^{-1}.  \]
}}
\end{center}


\vskip +10 pt
{\bf Verallgemeinertes ElGamal Verfahren} (auf das diskrete Logarithmusproblem basierend).
\vskip +20 pt

\hyperlink{ellcurve}{Elliptische Kurven}{} liefern n"utzliche Gruppen f"ur Public Key-Verschl"usselungsverfahren.



%--------------------------------------------------------------------
\newpage
\addcontentsline{toc}{subsection}{Literaturverzeichnis}
\begin{thebibliography}{99}

   \bibitem[Adleman1982]{Adleman1982} \index{Adleman 1982}
       Adleman L.: \\ 
       \emph{On breaking the iterated Merkle-Hellman public key 
             Cryptosystem.} \\ 
       Advances in Cryptologie, Proceedings of Crypto 82, 
       Plenum Press 1983, 303-308.

   \bibitem[Balcazar1988]{Balcazar1988} \index{Balcazar 1988} 
       Balcazar J.L., Daaz J., Gabarr\'{} J.: \\ 
       \emph{Structural Complexity I.} \\ 
       Springer Verlag, pp 63.
           
    \bibitem[Brickell1985]{Brickell1985} \index{Brickell 1985}
       Brickell E.F.: \\
       \emph{Breaking Iterated Knapsacks.}  \\
       Advances in Cryptology: Proc. CRYPTO\'84, 
       Lecture Notes in Computer Science, vol. 196, 
       Springer Verlag, New York, 1985, pp. 342-358.

    \bibitem[Lagarias1983]{Lagarias1983} \index{Lagarias 1983} 
       Lagarias J.C.: \\
       \emph{Knapsack public key Cryptosystems and diophantine
             Approximation.} \\
       Advances in Cryptology, Proseedings of Crypto 83, Plenum Press.

    \bibitem[Merkle1978]{Merkle1978} \index{Merkle 1978} 
       Merkle R. and Hellman M.: \\
       \emph{Hiding information and signatures in trapdoor knapsacks.} \\
       IEEE Trans. Information Theory, IT-24, 1978.

    \bibitem[RSA1978]{RSA1978} \index{RSA 1978}
       Rivest R.L., Shamir A. and Adleman L.: \\
       \emph{A Method for Obtaining Digital Signatures and 
             Public Key Cryptosystems.} \\
       Commun. ACM, vol 21, April 1978, pp. 120-126.

    \bibitem[Shamir1982]{Shamir1982} \index{Shamir 1982}
       Shamir A.: \\
       \emph{A polynomial time algorithm for breaking the basic 
             Merkle-Hellman Cryptosystem.} \\
       Symposium on Foundations of Computer Science (1982), 145-152.
           
    \bibitem[Stinson1995]{Stinson1995} \index{Stinson 1995}
       Stinson D.R.: \\
       \emph{Cryptography.} \\
       CRC Press, Boca Raton, London, Tokyo, 1995.

\end{thebibliography}


%--------------------------------------------------------------------
\section*{Web-Links}
\addcontentsline{toc}{subsection}{Web-Links}
\begin{enumerate}
   \item \href{http://www.geocities.com/st\_busygin/clipat.html}
              {http://www.geocities.com/st\_busygin/clipat.html }
\end{enumerate}

% Local Variables:
% TeX-master: "../script-de.tex"
% End: