moderncryptography.tex

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

\>\> {\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) $ is the solution. \\
\>{\bf else} \\
\>\> No solution exists.
\end{tabbing}
}}
\end{center}
\vskip +10 pt
{\bf Algorithm 1.} Solving knapsack problems with super-increasing weights
\vskip +20 pt


%--------------------------------------------------------------------
\subsubsection{Merkle-Hellman knapsack encryption}
%--------------------------------------------------------------------
\index{Hellman, Martin} \index{Merkle, Ralph} 

In 1978, Merkle and Hellman 
\cite{Merkle1978} \index{Encryption!Merkle-Hellman} specified a public key 
encryption procedure that is based on ``defamiliarising'' the easy 0-1 
knapsack problem with a super-increasing sequence into a congruent one with a 
super-increasing sequence. It is a block ciphering that ciphers an $n$-bit 
plaintext each time it runs.
\index{Knapsack!Merkle-Hellman}
More precisely:

\begin{center}
\fbox{\parbox{12cm}{        
Let $ (a_1, \dots, a_n) $ be super-increasing. Let $ m $ and $ w $ be two co-prime 
numbers with $ m > \sum_{i=1}^{n} a_i $ and $ 1\leq w \leq m-1. $ Select 
$\bar{w} $ with $ w \bar{w} \equiv 1 \mod m $ the modular inverse of $ w $ and 
set $ b_i:= wa_i \mod m, $ $ 0\leq b_i < m $ for $ i=1, \dots ,n, $ and verify 
whether the sequence $ b_1, \dots b_n $ is not super-increasing. A permutation $ 
b_{\pi (1)}, \dots , b_{\pi(n)} $ of  $ b_1, \dots , b_n $ is then published and 
the inverse permutation $ \mu $ to $ \pi $ is defined secretly. A sender writes 
his/her message in blocks $ (x_1^{(j)}, \dots, x_n^{(j)}) $ of binary numbers $ 
n $ in length, calculates
\[ g^{(j)}:= \sum_{i=1}^n x_{i}^{(j)} b_{\pi(i)} \]
and sends $ g^{(j)}, (j=1,2, \dots). $\par
The owner of the key calculates
\[ G^{(j)}:=\bar{w} g^{(j)} \mod m ,\quad 0 \leq G^{(j)} < m \]
and obtains the $ x_{\mu(i)}^{(j)} \in \{ 0,1\} $ (and thus also the $ x_i^{(j)} 
$) from
\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*}
by solving the easier 0-1 knapsack problems $ K(a_1,\dots,a_n;G^{(j)}) $ with 
super-increasing sequence $ a_1, \dots,a_n $.
}}
\end{center}
\vskip +10 pt
{\bf Merkle-Hellman procedure} (based on knapsack problems).
\vskip +20 pt



In 1982, \index{Shamir, Adi} Shamir \cite{Shamir1982} specified an algorithm for 
breaking the system in polynomial \index{Polynomial} time without solving the general knapsack 
problem. Len \index{Adleman, Leonard} Adleman \cite{Adleman1982} and Jeff 
Lagarias \index{Lagarias, Jeff} \cite{Lagarias1983} specified an algorithm for 
breaking the twice iterated Merkle-Hellman knapsack encryption procedure in 
polynomial time. Ernst Brickell \index{Brickell, Ernst} \cite{Brickell1985} then 
specified an algorithm for breaking multiply iterated Merkle-Hellman knapsack 
encryption procedures in polynomial time. This made this procedure unsuitable as 
an encryption procedure. It therefore delivers a one way function whose trapdoor 
information (defamiliarisation of the 0-1 knapsack problem) could be discovered 
by an evesdropper.



\subsection{Decomposition into prime factors as a basis for public key 
procedures}\index{Prime factor!decomposition}


%--------------------------------------------------------------------
\subsubsection[The RSA procedure]
{The RSA procedure\footnotemark}
\footnotetext{
Using CrypTool\index{CrypTool} you can gain practical experience
with the RSA procedure via the menu {\bf Indiv.Procedures \textbackslash{} 
RSA Cryptosystem \textbackslash{} RSA Demonstration}.
}
\index{RSA} \hypertarget{RSAVerfahren}{} 
As early as 1978, R. \index{Rivest, Ronald} Rivest, \index{Shamir, Adi} A. Shamir,
\index{Adleman, Leonard} L. Adleman \cite{RSA1978} introduced 
the most important asymmetric cryptography procedure to date.  \par


\begin{center}
\fbox{\parbox{12cm}{        
\underline{Key generation:} \vskip + 5pt

Let $ p $ and $ q $ be two different prime numbers and $ N = pq$. Let 
$ e $ be any prime number relative to $ \phi (N) $ \index{Prime number!relative prime}, i.e. $ \ggt (e,\phi (N))=1. $\index{Gcd}
Using the Euclidean algorithm, 
we calculate the natural number  $ d < \phi (N), $ such that
\[ ed \equiv 1 \mod \phi (N). \]
whereby $ \phi $ is the {\bf Euler phi Function}. 

The output text is divided into blocks and encrypted, whereby each block has a 
binary value $ x^{(j)} \leq N $. \vskip + 5 pt

\underline{Public key:}
\[ N,e. \]
\underline{Private key:}
\[ d. \]
\underline{Encryption:}
\[ y= e_{T} (x) = x^{e} \mod N.\]
\underline{Decryption:}
\[ d_{T} (y) = y^d \mod N. \]
}} % \fbox

\end{center}

\vskip +10 pt
{\bf RSA procedure} (based on the factorisation problem).
\vskip +20 pt
\index{Factorisation!factorisation problem}
\index{Euler!(phi) function}
{\bf Comment:} 
The Euler phi function is defined as: $ \phi (N)$ is the number of natural 
numbers that do not have a common factor with $ N $ \index{Co-prime} {}
$ x \leq N. $ Two natural numbers $ a $ and $ b $ are co-prime if 
$ \ggt (a,b)=1. $ 

For the Euler phi function: $ \phi (1)=1, \phi(2)=1,
\phi(3)=2, \phi (4)=2, \phi(6)=2, \phi (10)= 4, \phi (15)=8. $  For example, $ 
\phi (24)=8, $ because
$|\{ x <24 : \ggt (x,24) =1 \}| =|\{1,5,7,11,13,17,19,23\}|. $

If  $ p $ is a prime number, then $ \phi (p)= p-1. $

If we know the various prime factors $ p_1, \dots , p_k $ of $ N, $ then $ \phi 
(N) = N \cdot (1-\frac{1}{p_1}) \,
\cdots \, (1-\frac{1}{p_k}) $\footnote{Further formulas for the Euler phi
function are in the article ``Introduction to Elementary Number Theory with
Examples'', chapter~\ref{patternsandstructures}.}.

In the case of $ N=pq $, $ \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) $ & The natural numbers that are co-prime to $ n $ and less than 
$ 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
The function $ e_T $  is a one way function whose trapdoor information is the 
decomposition into primes of $ N $.

At the moment, no algorithm is known that can factorise two prime numbers 
sufficiently quickly for extremely large values (e.g. for several hundred 
decimal places). The quickest algorithms known today
\cite{4Stinson1995}\index{Stinson 1995} 
factorise a compound whole number $ N $ in a time period proportional to $ 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
As long as no better algorithm is found, this means that values of the order of 
magnitude $ 100 $ to $ 200 $ decimal places are currently safe. Estimates of the 
current computer technology indicate that a number with $100$ decimal places 
could be factorised in approximately two weeks at justifiable cost. Using an 
expensive configuration (e.g. of around 10 million US dollars), a number with 
$150$ decimal places could be factorised in about a year. A $200-$digit number 
should remain impossible to factorise for a long time to come, unless there is a 
mathematical breakthrough. For example, it would take about 1000 years to 
decompose a 200-digit number into prime factors using the existing algorithms; 
this applies even if $ 10^{12} $  operations can be performed per second, which 
is beyond the performance\index{Performance} of current technology and would cost billions of 
dollars in development costs. However, you can never be sure that there won't be 
a mathematical breakthrough tomorrow.

To this date, it has not been proved that the problem of breaking RSA is 
equivalent to the factorisation problem. Nevertheless, it is clear that the RSA 
procedure will no longer be safe if the factorisation problem is ``solved''.


\subsubsection{Rabin public key procedure (1979)}

In this case it has been shown that the procedure \index{Rabin, Michael O.} 
\index{Rabin!public key procedure} is equivalent to breaking the factorisation problem. 
Unfortunately, this procedure is susceptible to chosen-cipher text attacks.
\index{Attack!chosen-cipher text}
\begin{center}
\fbox{\parbox{12cm}{        
Let $ p $ and $ q $ be two different prime numbers with $ p,q\equiv 3 \mod 4 $ 
and $ n = pq.$ Let $ 0\leq B \leq n-1.$ \\
\underline{Public key:}
\[ e=(n,B). \]
\underline{Private key:}
\[ d=(p,q). \]
\underline{Encryption:}
\[ y= e_{T} (x) = x(x+B) \mod n.\]
\underline{Decryption:}
\[ d_{T} (y) = \sqrt{y + B^2/4} -B/2 \mod n. \]
}}
\end{center}

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

Caution:
Because $ p,q \equiv 3 \mod 4 $  the encryption is easy to calculate (if the key 
is known). This is not the case for $ p \equiv 1 \mod 4. $ In addition, the 
encryption function is not injective: There are precisely four different source 
codes that have $ e_T(x) $  as inverse image: $ x,-x-B,\omega (x+B/2)-B/2, -
\omega(x+B/2)-B/2, $ where $ \omega $  is one of the four roots of unity. The 
source codes therefore must be redundant for the encryption to remain unique!

Backdoor information is the decomposition into prime numbers of $ n = pq. $ 






       \subsection{The discrete logarithm as a basis for public key procedures}
Discrete logarithms \index{Discrete logarithm} form the basis for a large number of algorithms for public-
key procedures.
\index{Logarithm problem!discrete}





    \subsubsection{The discrete logarithm in $ \Z_p $}
Let $ p $ be a prime number and let $ g \in \Z_p^\ast=\{0,1,\ldots,p-1\} $. Then 
the discrete exponential function base $ g $  is defined as
\[ e_g : k \longrightarrow y:=g^k \mod p, \quad 1\leq k \leq p-1. \]
The inverse function is called a discrete logarithm function $ \log_g $; the 
following holds:
\[ \log_g (g^k) =k. \]
\index{Exponential function!discrete} The problem of the discrete logarithm (in 
$ \Z_p^\ast$) is understood to be as follows:
\[ {\rm Given~ } p,g {\rm ~and~ } y, {\rm~determine~} k {\rm ~such~that~ } 
y=g^k \mod p {\rm .}\]
It is much more difficult to calculate the discrete logarithm than to evaluate 
the discrete exponential function (see chapter \ref{MultOrdPrimitveRoot}).
There are several procedures for calculating the discrete logarithm 
\cite{4Stinson1995}\index{Stinson 1995}:
\vskip + 5pt
\begin{center}
\begin{tabular}{|l|l|}\hline
Name                 &        Complexity \\ \hline \hline
Baby-Step-Giant-Step &         $ O(\sqrt{p}) $ \\ \hline
Silver-Pohlig-Hellman    &    polynomial in $ q, $ the greatest \\
&  prime factor of $ 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}