moderncryptography.tex

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

%--------------------------------------------------------------------
\subsubsection[Diffie-Hellman key agreement]
{Diffie-Hellman key agreement\footnotemark}
\footnotetext{%
With CrypTool\index{CrypTool} this exchange protocol has been
visualized: you can execute the single steps with concrete numbers using 
menu {\bf Indiv. Procedures \textbackslash{} Protocols \textbackslash{} Diffie-Hellman Demonstration}.
}

\index{Key agreement (key exchange)!Diffie-Hellman} 
\index{Diffie, Whitfield}
\index{Hellman, Martin}
\index{Diffie-Hellman}
\hypertarget{DH-KeyExch}{} \label{DH-KeyExch}

The mechanisms and 
algorithms of classical cryptography only take effect when the subscribers have 
already exchanged the secret key. In classical cryptography you cannot avoid 
exchanging secrets without encrypting them. Transmission safety here must be 
achieved using non-cryptographic methods. We say that we need a secret channel 
for exchanging secrets. This channel can be realised either physically or 
organisationally. \\
What is revolutionary about modern cryptography is, amongst other things, that 
you no longer need secret channels: You can agree secret keys using non-secret, 
i.e. public channels. \\
One protocol that solves this problem is that of Diffie and Hellman. \\

\begin{center}
\fbox{\parbox{12cm}{        
Two subscribers $ A $ and $ B $ want to agree on a joint secret key. \par
Let $ p $ be a prime number and $ g $ a natural number. These two numbers do not 
need to be secret. \\
The two subscribers then select a secret number $ a $ and $ b$ from which they 
calculate the values $ \alpha = g^{a}\mod p $ and $ \beta = g^b \mod p. $ They 
then exchange the numbers $ \alpha $ and $ \beta $. To end with, the two 
subscribers calculate the received value to the power of their secret value to 
get $ \beta^{a} \mod p $ and $ \alpha^b \mod p. $\\
Thus
\[ \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 key agreement.}
\vskip +20 pt


The safety of the {\bf Diffie-Hellman protocol} is closely connected to 
calculating the discrete logarithm mod $p$\index{Logarithm}. It is even thought that these 
problems are equivalent.

%--------------------------------------------------------------------
\subsubsection{ElGamal public key encryption procedure in $ \Z_p^\ast$}
%--------------------------------------------------------------------
\index{ElGamal!public key}
By varying the Diffie-Hellman key agreement protocol \index{Diffie-Hellman} 
\index{Encryption!ElGamal public key} slightly, you can obtain an 
asymmetric encryption algorithm. This observation was made by Taher ElGamal.
\begin{center}
\fbox{\parbox{12cm}{        
Let $ p $ be a prime number such that the discrete logarithm in $ \Z_p $ is 
difficult to compute. Let $ \alpha \in \Z_p^\ast $ be a primitive element. Let $a \in \N$ and $ 
\beta = \alpha^{a}  \mod p. $\\
\underline{Public key:}
\[ p,\alpha,\beta. \]
\underline{Private key:}
\[a. \]
Let $ k \in \Z_{p-1} $ be a random number and $ x \in \Z_p^{\ast} $ the 
plaintext. \\
\underline{Encryption:}
\[ e_T(x,k)=(y_1,y_2), \]
where
\[ y_1=\alpha^k \mod p\]
and
\[ y_2 = x\beta^k \mod p.\]
\underline{Decryption:}
\[ d_T(y_1,y_2)= y_2 (y_1^{a})^{-1} \mod p \]
}}
\end{center}


\vskip +10 pt
{\bf ElGamal procedure} (based on the factorisation problem).
\vskip +20 pt



%--------------------------------------------------------------------
\subsubsection{Generalised ElGamal public key encryption procedure}
%--------------------------------------------------------------------

The discrete logarithm can be generalised in any number of finite \index{Group} 
groups $ (G, \circ) $. The following provides several properties of $ G, $ that 
make the discrete logarithm problem difficult. \\
\index{Exponential function!calculation}
\paragraph{Calculating the discrete exponential function}
Let $ G $ be a group with the operation $ \circ $ and $ g \in G. $ The 
(discrete) exponential function  base $ g $ is defined as
\[ e_g : k \longmapsto g^k, \quad {\rm for~all~} k \in {\rm N}. \]
where
 \[ \ g^{k}:=\underbrace{g \circ \ldots \circ g}_{k {\rm ~times}}.\]
The exponential function is easy to calculate:
\vskip +20 pt \noindent
{\bf Lemma.}

{\em
  The power $ g^k $ can be calculated in at most $ 2 \log_2 k $ group 
operations.
}
\vskip +10 pt

\begin{Proof}{}
Let $ k=2^n + k_{n-1} 2^{n-1} + \cdots + k_1 2 + k_0 $ be the binary 
representation of $k. $ Then $ n \leq \log_2 (k), $  because $ 2^n \leq k < 
2^{n+1}. $ $ k $ can be written in the form $ k=2k' + k_0 $ with $ k'= 2^{n-1} + 
k_{n-1} 2^{n-2} + \cdots + k_1 $. Thus 
\[ g^k = g^{2k'+k_0}= (g^{k'})^2 g^{k_0} .\]
We therefore obtain $ g^k $ from $ g^{k'} $ by squaring and then multiplying by 
$ g $. The claim is thus proved by induction to $ n. $
\end{Proof}

\vskip +10 pt
{\bf Problem of the discrete logarithm}\index{Logarithm problem!discrete}
\vskip +10 pt
\begin{center}
\fbox{\parbox{12cm}{        
Let $ G $ by a finite group with the operation $ \circ. $ Let $ \alpha \in G $ 
and $ \beta \in H=\{ \alpha^{i}: i\geq 0\}. $ \\
We need to find a unique $ a \in {\rm N} $ with $ 0 \leq a \leq |H| -1 $ and $ \beta 
= \alpha^{a}. $ \\       
We define $ a $ as $ \log_\alpha (\beta). $
}}
\end{center}

\paragraph{Calculating the discrete logarithm }
A simple procedure for calculating the discrete logarithm of a group element, 
that is considerably more efficient than simply trying all possible values for $ 
k, $ is the \index{Baby-Step-Giant-Step} Baby-Step-Giant-Step algorithm.
\begin{theorem}\label{thm-cry-bsgs}[Baby-Step-Giant-Step algorithm]
Let $ G $ be a group and $ g \in G. $ Let $ n $ be the smallest natural number 
with $ |G|\leq n^2. $ Then the discrete logarithm of an element $ h 
\in G $ can be calculated base $ g $ by generating two lists each containing $ n 
$ elements and comparing these lists.\\
In order to calculate these lists, we need $ 2n $ group operations.
\end{theorem}

\begin{Proof}{}
  First create the two lists \\
Giant-Step list: $ \{1,g^n,g^{2n}, \ldots, g^{n \cdot n}\}, $\\
Baby-Step list: $ \{ hg^{-1} , hg^{-2} , \ldots , hg^{-n} \}. $ \par
If $ g^{jn} = hg^{-i}, $ i.e. $ h = g^{i+jn}, $ then the problem is solved. If 
the lists are disjoint, then $ h $ cannot be represented as $ g^{i + jn}, i, 
j\leq n,$. As all powers of $ g $ are thus recorded, the logarithm problem does 
not have a solution.
\end{Proof}

You can use the Baby-Step-Giant-Step algorithm to demonstrate that it is much 
more difficult to calculate the discrete logarithm than to calculate the 
discrete exponential function. If the numbers that occur have approximately 1000 
bits in length, then you only need around 2000 multiplications to calculate $ 
g^k $ but around $ 2^{500} \approx 10^{150} $ operations to calculate the 
discrete logarithm using the Baby-Step-Giant-Step algorithm. \\
In addition to the Baby-Step-Giant-Step algorithm, there are also numerous other 
procedures for calculating the discrete logarithm \cite{4Stinson1995}\index{Stinson 1995}.

\paragraph{The theorem from Silver-Pohlig-Hellman}
In finite Abelian groups, the discrete logarithm problem can be reduced to 
groups of a lower order.
\begin{theorem}\label{thm-cry-pohe}[Silver-Pohlig-Hellman]
Let $ G $ be a finite Abelian group with $ |G|= p_1^{a_1} p_2^{a_2} \cdot \ldots 
\cdot p_s^{a_s}. $ The discrete logarithm in $ G $ can then be reduced to 
solving logarithm problems in groups of the order $ p_1, \ldots , p_s $.
\end{theorem}

If $ |G| $ contains a ``dominant'' prime factor $ p ,$ then the 
complexity \index{Complexity} of the logarithm problem is approximately
\[ O(\sqrt{p}). \]
Therefore, if the logarithm problem is to be made difficult, the order of the 
group used $ G $ should have a large prime factor. In particular, if the 
discrete exponential function in the group $ \Z_p^{\ast} $ is to be a one way 
function, then $ p -1 $ must be a large prime factor.




\begin{center}
\fbox{\parbox{12cm}{        
Let $ G $ be a finite group with operation $  \circ, $ and let $ \alpha \in G, $ 
so that the discrete logarithm in $ H =\{ \alpha^{i}: i \geq 0 \} $ is 
difficult, Let $ a $ with $   0 \leq a \leq |H| -1 $ and let $ \beta = 
\alpha^{a}. $\\
\underline{Public key:}
\[ \alpha,\beta. \]
\underline{Private key:}
\[a. \]
Let $ k \in \Z_{|H|} $ be a random number and $ x \in G $ be a plaintext. \\
\underline{Encryption:}
\[ e_T(x,k)=(y_1,y_2), \]
where
\[ y_1=\alpha^k \]
and
\[ y_2 = x\circ \beta^k .\]
\underline{Decryption:}
\[ d_T(y_1,y_2)= y_2\circ (y_1^{a})^{-1}  \]
}}
\end{center}


\vskip +10 pt
{\bf Generalised ElGamal procedure} (based on the factorisation problem).
\vskip +20 pt

\hyperlink{ellcurve}{Elliptic curves} {} provide useful groups for public key 
encryption procedures.


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

   \bibitem[Adleman1982]{Adleman1982} \index{Adleman 1982}
       Adleman L.: \\ 
       \emph{On breaking the iterated Merkle-Hellman public key 
             Cryptosystem.} \\ 
       Advances in Cryptology, 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.
           
%already defined in elementaryNumberTheory.tex
    \bibitem[Stinson1995]{4Stinson1995} \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-en.tex"
% End: