digitalsignatures.tex

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

connected with a corresponding encryption scheme.

Both, RSA and DSA signature are discussed in more detail in the following
two sections. After that we go one step further and show how digital
signatures can be used to create the digital equivalent of ID cards. This
is called Public Key Certification.


% --------------------------------------------------------------------------
\vskip + 15pt
\subsection{RSA signatures}
\index{Signature!digital}
\index{RSA!signature}

\def\Mod#1{\ (\mbox{mod }#1)}
As mentioned in the comment at the end of \hyperlink{RSAproof}{section
  \ref{RSAproof}} it is possible to perform the RSA private and public key
operation in reverse order, i.~e.\ raising $M$ to the power of $d$ and then
to the power of $e \Mod{N}$ yields $M$ again. Based on this simple fact, RSA
can be used as a signature scheme.

The RSA signature $S$ for a message $M$ is created by performing the private
key operation:
$$ S \equiv M^d \Mod{N} $$
In order to verify, the corresponding public key operation is performed on
the signature $S$ and the result is compared with message $M$:
$$ S^e \equiv (M^d)^e \equiv (M^e)^d \equiv M \Mod{N}$$
If the result matches the message $M$, then the signature is accepted by the
verifier, otherwise the message has been tampered with, or was never signed
by the holder of $d$.

As explained above, signatures are not performed on the message itself, but
on a cryptographic hash value of the message. To prevent certain attacks
on the signature procedure (alone or in combination with encryption) it is
necessary to format the hash value before doing the exponentiation, as
described in the PKCS\#1 (Public Key Cryptography Standard \#1
\cite{PKCS1})\index{PKCS\#1}. 
The fact that this standard had to be revised recently, after
being in use for several years, can serve as an example of how difficult it is
to get the details of cryptography right.


% --------------------------------------------------------------------------
\vskip + 15pt
\subsection{DSA signatures}
\index{Signature!digital}
\index{DSA!signature}

In August of 1991, the U.S. National Institute of Standards and Technology
(NIST\index{NIST}) proposed a digital signature algorithm (DSA), which was
subsequently adopted as a U.S. Federal Information Processing Standard (FIPS 186
\cite{FIPS186}). 

The algorithm is a variant of the ElGamal scheme. Its security is based on
the Discrete Logarithm Problem\index{Logarithm problem!discrete}. The DSA public and private key and its
procedures for signature and verification are summarised below.

\paragraph{Public Key}\strut\\
\begin{tabular}{l@{ }l}
$p$ & prime \\
$q$ & 160-bit prime factor of $p - 1$ \\
$g$ & $ = h^{(p-1)/q}  \mbox{ mod } p$, where $h < p - 1$ and
$h^{(p-1)/q} > 1  \Mod{p}$ \\
$y$ & $\strut \equiv  g^x  \mbox{ mod } p$ 
\end{tabular}

\emph{Remark:} Parameters $p,q$ and $g$ can be shared among a group of users.

\paragraph{Private Key}\strut\\
\begin{tabular}{l@{ }l}
$x < q$ (a 160-bit number) 
\end{tabular}

\paragraph{Signing}\strut\\
\begin{tabular}{l@{ }l}
$m$ & the message to be signed\\
$k$ & choose at random\index{Random}, less than $q$\\
$r$ & $= (g^k \; \mbox{ mod } p) \mbox{ mod } q$\\
$s$ & $= (k^{-1}(\mbox{SHA-1}(m) + xr)) \mbox{ mod } q$
\end{tabular}

\emph{Remark:}
\begin{itemize}
\item $(s,r)$ is the signature.
\item The security of the signature depends not only on the mathematical
  properties, but also on using a good random source\index{Random}  for $k$.
\item SHA-1 \index{SHA-1} is a 160-bit hash function.
\end{itemize}
\paragraph{Verifying}\strut\\
\begin{tabular}{l@{ }l}
$w$ & $= s^{-1} \;  \mbox{ mod } q$\\
$u_1$ & $= (\mbox{SHA-1}(m)w) \mbox{ mod } q$\\
$u_2$ & $= (rw)  \mbox{ mod } q$\\
$v$ & $= (g^{u_1}y^{u_2}) \mbox{ mod } p)  \mbox{ mod } q$\\

\end{tabular}

\emph{Remark:} If $v = r$, then the signature is verified.

While DSA was specifically designed, so that it can be exported from
countries regulating export of encryption soft and hardware (like the U.S.\ 
at the time when it was specified), it has been noted
\cite[p.~490]{Schneier1996ds}, that the operations involved in DSA can be
used to emulate RSA and ElGamal encryption.


% --------------------------------------------------------------------------
\vskip + 15pt
\subsection{Public key certification}
\index{Certification!public key}
\index{PKI}
The aim of public key certification is to guarantee the connection between a
public key and a user and to make it traceable for external parties. In cases in
which it is impossible to ensure that a public key really belongs to a
particular person, many protocols are no longer secure, even if the individual
cryptographic modules cannot be broken.


% --------------------------------------------------------------------------
\vskip + 15pt
\subsubsection{Impersonation attacks}\label{Impersonalisierungsattacke}
\index{Impersonation attack}
Assume Charlie has two pairs of keys (PK1, SK1) and (PK2, SK2), where SK denotes
the secret key and PK the public key. Further assume that he manages to palm off
PK1 on Alice as Bob's public key and PK2 on Bob as Alice's public key (by
falsifying a public key directory).

Then he can attack as follows:
\begin{itemize}
    \item Alice wants to send a message to Bob. She encrypts it using PK1
because she thinks that this is Bob's public key. She then signs the message
using her secret key and sends it.
    \item Charlie intercepts the message, removes the signature and decrypts the
message using SK1. If he wants to, he can then change the message in any way he
likes. He then encrypts the message again, but this time using Bob's genuine
public key, which he has taken from a public key directory, signs the message
using SK2 and forwards it to Bob.
    \item Bob verifies the signature using PK2 and will reach the conclusion
that the signature is correct. He then decrypts the message using his secret
key.
\end{itemize}

In this way Charlie can listen in on communication between Alice and Bob and
change the exchanged messages without them noticing. The attack will also work
if Charlie only has one pair of keys.

Another name for this type of attack is \index{Attack!man-in-the-middle}
% \index{Man-in-the-middle attack}
``man-in-the-middle attack''. Users are promised
protection against this type of attack by publickey
certification, which is intended to guarantee the
\index{Authenticity} authenticity of public keys. The most common
certification method is the X.509 standard.


% --------------------------------------------------------------------------
\vskip + 15pt
\subsubsection{X.509 certificate}
\index{X.509} 
Each participant who wants to have an X.509 certificate (\cite{X.509})
verifying that his public key belongs to a real person consults what is
known as a \index{Certification authority (CA)} certification authority
(CA)\footnote{%
Often called trust center, if the certificates are not only offered
to a closed user group.
}. 
He proves his identity to this CA (for example by showing his ID). 
The CA then issues him an electronic document (certificate) which 
essentially contains the name of the certificate-holder and the name
of the CA, the certificate-holder's public key and the validity period
of the certificate. The CA then signs the certificate using its secret key.

Anyone can now use the CA's public key to verify whether a certificate is
falsified. The CA therefore guarantees that a public key belongs to a particular
user.

This procedure is only secure as long as it can be guaranteed that the CA's
public key is correct. For this reason, each CA has its public key certified by
another CA that is superior in the hierarchy. In the upper hierarchy level there
is usually only one CA, which can of course then have its key certified by
another CA. It must therefore transfer its key securely in another way. In the
case of many software products that work with certificates (such as the
Microsoft and Netscape Web browsers), the certificates of these root CAs are
permanently embedded in the program right from the start and cannot be changed
by users at a later stage. However, (public) CA keys, in particularly those of
the root entity, can also be secured by means of making them available publicly.


\begin{thebibliography}{99999}
\addcontentsline{toc}{subsection}{Bibliography}

\bibitem[Schneier1996]{Schneier1996ds} \index{Schneier 1996} 
    Bruce Schneier, \\
    {\em Applied Cryptography, Protocols, Algorithms, and Source Code in C}, \\
    Wiley, 2nd edition, 1996.

\bibitem[PKCS1]{PKCS1} RSA Laboratories,\\ 
    \index{PKCS\#1} \index{RSA Laboratories}
    {\em PKCS \#1 v2.1 Draft 3: RSA Cryptography Standard}, \\
    April 19, 2002.

\bibitem[X.509]{X.509} ITU-T, \\
    \index{X.509}
    {\em ITU-T Recommendation X.509 (1997 E): Information Technology -- 
    Open Systems Interconnection -- The Directory: Authentication Framework},\\
    June 1997.
    
\bibitem[X.509v3]{X.509v3} ITU-T, \\
    \index{X.509} \index{ITU-T} \index{ISO/IEC 9594-8}
    {\em X.509 (1993) Amendment 1: Certificate Extensions, The Directory
    Authentication Framework},\\ 
    International Telecommunication Union, Geneva, Switzerland, July 1995\\
    (equivalent to amendment 1 to ISO/IEC 9594-8).

\bibitem[FIPS180-2]{FIPS180-2} U.S. Department of Commerce/N.I.S.T. ,
    \index{FIPS180-2} \\
    {\em Secure Hash Standard (SHS)}, \\
    August 1, 2002.\\
    (FIPS 180-2 will supersede FIPS 180-1 beginning February 1, 2003.)

\bibitem[FIPS186]{FIPS186} U.S. Department of Commerce/N.I.S.T. ,
    \index{FIPS186} \\
    {\em Entity authentication using public key cryptography}, \\
    February 18, 1997.\\
    No more valid.
    
\bibitem[FIPS186-2]{FIPS186-2} U.S. Department of Commerce/N.I.S.T. ,
    \index{FIPS186-2} \\
    {\em Digital Signature Standard (DSS)}, \\
    January 27, 2000. Change Note: October 5, 2001.\\
    http://csrc.nist.gov/publications/fips/fips186-2/fips186-2-change1.pdf

\end{thebibliography}

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