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{theorem}{0}
\setcounter{definition}{0}

\newcommand{\NT}{\vspace*{0.2\baselineskip}\\}
%\newcommand{\VT2}{\vspace*{0.1\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}{{\rm gcd}}
\newcommand{\kgv}{\text{kgV}}
\newcommand{\Id}{\text{Id}}
\newcommand{\nqcarre}{{\ncarre}_{q^2}}
%\newcommand{\mod}{{\rm mod~}}
%\normalsize
%\parindent = 0pt
%\setlength{\textwidth}{140mm}
%\setlength{\textheight}{216mm}


% \theorembodyfont{\} 
% \newtheorem{Bsp}{Beispiel}[section]

% {\theorembodyfont{\em}
%                  \newtheorem{Def}[Bsp]{Definition} }

% \theorembodyfont{\em} 
% \newtheorem{Hilf}[Bsp]{Hilfssatz}

%\theorembodyfont{\em} 
% \newtheorem{Lem}[Bsp]{Lemma}

%\theorembodyfont{\em} 
% \newtheorem{Kor}[Bsp]{Korollar}

%\theorembodyfont{\em}
% \newtheorem{Folg}[Bsp]{Folgerung}

%\theorembodyfont{\em}
%  \newtheorem{Satz}[Bsp]{Satz}

% \theoremstyle{break} 
% {\theorembodyfont{\em} 
% \newtheorem{Theo}[Bsp]{Theorem}}                 
% In diesem Stil wird nach dem Theoremkopf ein Zeilenumbruch vorgenommen.

% \theoremstyle{break} 
% {\theorembodyfont{\em} 
% \newtheorem{Haupt}[Bsp]{Hauptsatz}}                 
% In diesem Stil wird nach dem Theoremkopf ein Zeilenumbruch vorgenommen.
% \newenvironment{Beweis}[1]
%   {\textbf{Beweis #1} \\}
%   {\hfill$\Box$ \\}

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

\newpage
%**************************************************************************************************************************
\section{The Mathematical Ideas behind Modern Cryptography}
\label{Chapter_ModernCryptography}
\hypertarget{Chapter_ModernCryptography}{}
%**************************************************************************************************************************
(Oyono R. / Esslinger B., Sep. 2000, Updates Nov. 2000, Feb. 2003)

%--------------------------------------------------------------------------------------------------------------------------
\subsection{One way functions with trapdoor and complexity classes}
%--------------------------------------------------------------------------------------------------------------------------
\index{Cryptography!modern} \index{One way function} \hypertarget{OneWayFunktion1}{}
A {\bf one way function} is a function that can be calculated 
efficiently, but whose inverse is extremely complicated and practically 
impossible to calculate.\par

To put it more precisely:  A one way function is a mapping $ f $ from a set $ X 
$ to a set $ Y, $ such that $ f(x) $ can be calculated easily for each element $ 
x $ of $ X $, whereas for (almost) every $ y $ from $ Y $  it is practically 
impossible to find an inverse image $ x $ (i.e. an $ x $ where $ f(x)=y $).\par

An everyday example of a one way function is a telephone book: the function to 
be performed is to assign a name to the corresponding telephone number. This can 
be done easily due to the fact that the names are sorted alphabetically. 
However, the inverse function - assigning a name to a given number - is 
obviously difficult if you only have a telephone book available. \par

One way functions play a decisive role in cryptography. Almost all cryptographic 
terms can be rephrased using the term one way function. Let's take for example 
public key encryption \index{Encryption!public key}\index{Encryption!asymmetric} 
(asymmetric cryptography):\par

Each subscriber $ T $ to the system is assigned a private \index{Key!private} 
\index{Key!public} key $ d_T $   and what is known as a public key $ e_T $. 
These keys must have the following property (public key property):\\
For an opponent who knows the public key $ e_T $, it is practically impossible 
to determine the private key  $ d_T $.\par

In order to construct useful public key procedures, therefore, we look for a 
one way function that is ``easy'' to calculate in one direction {}, but 
is ``difficult'' (practically impossible) to calculate in the other 
direction, provided that a particular piece of additional information 
\index{One way function!with trapdoor } (trapdoor) is not available. This 
additional piece of information allows the inverse to be found efficiently. Such 
functions are called {\bf trapdoor one way functions}. In the above case, $ d_T 
$ is the trapdoor information. \par

In this process, we describe a problem as ``easy'' if it can be solved in 
\index{Runtime!polynomial} \index{Polynomial}polynomial time as a function of the length of the 
input. If the length of the input is $ n $ bits, then the time for calculating 
the function is proportional to $ n^{a}, $ where $ a $  is a constant. We say 
that the \index{Complexity} complexity of such problems is $ O(n^{a}) $
[Landau- or Big-O notation]. 

If you compare two functions  $ 2^n $  and   $ n^{a} $,  where $ a $  is a
constant, then there always exists a value for  $ n $,  from which for all
further  $ n $  applies: $ n^{a}  <  2^n $. 
The function  $ n^{a} $  has a lower complexity.    
Sample: for $ a=5 $ the following applies: from the length $ n=23 $, $ 2^n$
is greater than $n^5 $; for further $ n $  $ 2^n $ clearly increases more
quickly \
[($ 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 

The term ``practically impossible'' is slightly less precise. In 
general, we can say that a problem cannot be solved \index{Runtime!efficient} 
efficiently, if the time required to solve it increases more quickly than the 
polynomial\index{Polynomial} time as a function of the size of the input. If, for example, the 
length of the input is $ n $  bits and the time required for calculating the 
function is proportional to $ 2^n $, then the following currently applies: the 
function practically cannot be calculated for $n > 80$.

In order to develop a public key procedure that can be implemented in practice, 
it is therefore necessary to discover a suitable trapdoor one way function.\par

In order to tidy things up among this confusing multitude of possible problems 
and their complexities, we group problems with similar complexities into 
classes.

The most important complexity classes are the classes \textbf{P} and 
\textbf{NP}: 

\begin{itemize}

    \item The class \textbf{P}: This class contains those problems that can be 
solved in a polynomial \index{Polynomial} amount of time.
    
		\item The class \textbf{NP}: The definition of this class doesn't look at
		the time required to solve a problem, but rather at the time required to
		verify a given solution. The class \textbf{NP} consists of those problems
		for which a given solution can be verified in a polynomial \index{Polynomial} amount of time.
		Hereby, the term \textbf{NP} ``non-deterministic'' means polynomial and is
		based on a calculation model, i.e. on a computer that only exists in theory
		and can ``guess'' correct solutions non-deterministically then verify them
		in polynomial time.

\end{itemize}

The class \textbf{P} is contained in the class \textbf{NP}. A well-known 
unsolved problem is the question whether or not $ \textbf{P} \neq \textbf{NP} $ 
is true, i.e. whether or not \textbf{P} is a true subset. An important property 
of the class \textbf{NP} is that it also contains what are known as ``\textbf{NP}-complete''
problems. These are problems that represent the 
class \textbf{NP} as follows: If a ``good'' algorithm for such a 
problem exists, then ``good'' algorithms exist for all problems from 
\textbf{NP}. In particular: if \textbf{P} only contained one complete problem, 
i.e. if a polynomial \index{Polynomial} solution algorithm existed for this problem, then 
\textbf{P}would be equal to \textbf{NP}. In this sense, the \textbf{NP}-complete 
problems are the most difficult problems in \textbf{NP}.

Many cryptographic protocols are formed in such a way that the ``good''
subscribers only have to solve problems from \textbf{P}, whereas a 
perpetrator is faced with problems from \textbf{NP}.

Unfortunately, we do not yet know whether one way functions actually exist. 
However, we can prove that one way functions exist if and only if $ \textbf{P} 
\neq \textbf{NP} $ \cite[S.63]{Balcazar1988}.\\

\vskip +3pt
Mathematicians have again and again claimed to have proven the equivalence, e.g.

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

but so far the claims have always turned out to be false.

A number of algorithms have been suggested for public key procedures\index{Cryptography!public key}. In many 
cases - although they at first appeared promising - it was discovered that they 
could be solved polynomially\index{Polynomial}. The most famous failed applicant is the knapsack 
with trapdoor, suggested by Ralph Merkle \cite{Merkle1978}.

\newpage
%--------------------------------------------------------------------
\subsection{Knapsack problem as a basis for public key procedures}%
\index{Cryptography!public key}
%--------------------------------------------------------------------
%--------------------------------------------------------------------
\subsubsection{Knapsack problem} \index{Knapsack}
%--------------------------------------------------------------------

You are given $ n $ objects $ G_1, \dots, G_n $ with the weights $ g_1, \dots 
g_n $ and the values $w_1, \cdots, w_n. $ The aim is to carry away as much as 
possible in terms of value while restricted to an upper weight limit $ g $. You 
therefore need to find a subset of $ \{ G_1, \cdots,G_n\}, $ i.e. $ \{G_{i_1}, 
\dots ,G_{i_k} \}, $ so that $ w_{i_1}+ \cdots +w_{i_k} $ is maximised under the 
condition $  g_{i_1}+ \cdots +g_{i_k} \leq g. $ \par
Such questions are called {\bf NP}-complete problems (not \index{Runtime!not polynomial NP} deterministically polynomial\index{Polynomial}) that are difficult to 
calculate.\index{Knapsack}

A special case of the knapsack problem is:\\
Given the natural numbers $ a_1, \dots, a_n $   and $ g .$,
find $ x_1, \dots, x_n \in \{ 0,1\} $  where $ g = \sum_{i=1}^{n}x_i a_i $  
(i.e. where $ g_i = a_i = w_i $ is selected). This problem is also called a  
{\bf 0-1 knapsack problem} and is identified with $ K(a_1, \dots, a_n;g) $.\\

Two 0-1 knapsack problems  $ K(a_1, \dots, a_n;g) $   and  $ K(a'_1, \dots, 
a'_n;g') $  are called congruent if two \index{Co-prime} co-prime numbers $ w $ 
and $ m $ exist in such a way that
\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 $ for all $ i=1, \dots, n.$

\end{enumerate}
 
{\bf Comment:}
Congruent 0-1 knapsack problems have the same solutions.
No quick algorithm is known for clarifying the question as to whether two 0-1
knapsack problems are congruent.

A 0-1 knapsack problem can be solved by testing the $ 2^n $   possibilities for 
$ x_1, \dots, x_n $. The best method requires $ O(2^{n/2}) $  operations, which 
for $ n=100 $  with $ 2^{100} \approx 1.27 \cdot 10^{30} $  and  $ 2^{n/2} 
\approx 1.13 \cdot 10^{15} $ represents an insurmountable hurdle for computers.
However, for special $ a_1, \dots, a_n $   the solution is quite easy to find, 
e.g. for $ a_i = 2^{i-1}. $  The binary representation of $ g $ immediately 
delivers $ x_1, \dots, x_n$. In general, the a 0-1 knapsack problem can be 
solved easily if a \index{Permutation} permutation\footnote{A permutation\index{Permutation} $\pi$ 
of the numbers $1, \dots, n$ is a change in the order in which these numbers are 
listed. For example, a permutation $\pi$ of $(1,2,3)$ is $(3,1,2),$ i.e. 
$\pi(1) = 3$, $\pi(2) =1$ 
and $\pi(3) = 2$.} 
$ \pi $  of $ 1, \dots, n $  exists with $ a_{\pi (j)} > \sum_{i=1}^{j-1} 
a_{\pi(i)} $. If, in addition, $ \pi $ is the identity, i.e. $ \pi(i)=i $ for $ 
i=1,2,\dots,n, $ then the sequence $ a_1, \dots , a_n $ is said to be 
super-increasing.
The following algorithm solves the knapsack problem with a super-increasing 
sequence in the timeframe of $ O(n). $
\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} \\