% Autor: Heinrich Moser, mail@heinzi.at
%
% Folien:
% \documentclass[slidesonly,a4,12pt]{seminar}
% tex -> dvi: latex dh
% dvi -> ps:  dvips -t landscape dh
% dvi -> pdf: dvipdfm -l -p a4 dh
%
% Notizen & Folien:
% \documentclass[article,a4,12pt]{seminar}
% tex -> dvi: latex dh
% dvi -> ps:  dvips dh
% dvi -> pdf: dvipdfm -p a4 dh
\documentclass[slidesonly,a4,12pt]{seminar}

\usepackage{sem-a4}
\usepackage{semcolor}
\usepackage{fancybox}
\usepackage{slidesec}
\usepackage{pifont}
\usepackage{amstext}
\usepackage{epsfig}
\usepackage{pstcol}

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{url}
\usepackage[austrian]{babel}
\usepackage[latin1]{inputenc}
\usepackage{colortbl}
\usepackage{semlayer}
\usepackage{fancyhdr}

\input{seminar.bug}             % Official bugs corrections
\input{seminar.bg2}             % Unofficial bugs corrections

% Blauer und roter Text
\newcommand{\textblue}[1]{\textcolor{blue}{#1}}
\newcommand{\textred}[1]{\textcolor{red}{#1}}

% Format der Titelfolie
\renewcommand\slidemaketitle{%
  \par
  \begin{center}\bf
    {\Large \textblue \thetitle}\par\vskip 1ex
    \begin{tabular}[t]{c} \theauthor \end{tabular}\par\vskip 1ex
    \thedate
  \end{center}%
  \thethanks\par}

% Abschnittsanzeiger
\newcommand{\progress}[1] {%
  \fontfamily{cmss}\scriptsize\selectfont{}
  \begin{tabular}{#1}
    \hline
    ~&Verfahren&Mathematik&Attacken&~\\
    \hline
  \end{tabular}
  \vspace{-0.5mm}
}

% Blaue Überschrift
\newcommand{\blueheading}[1]{\slideheading{\textblue{#1}}}

% Kommandos zum Abrufen und Setzen des Abschnittsanzeigers
\def\theprogress{}
\def\setprogress#1{\gdef\theprogress{\progress{#1}}}

% Headers and footers personalization using the `fancyhdr' package
\newcommand{\headfootfont}{\fontsize{8}{9}\selectfont} % Schriftgröße
\fancyhf{} % Clear all fields
\renewcommand{\headrulewidth}{0.2mm}
\renewcommand{\footrulewidth}{0.2mm}
\fancyhead[L]{\headfootfont \textit{\thetitle}}
\fancyhead[R]{\theprogress}
\fancyfoot[L]{\headfootfont \textit{\theauthor}}
\fancyfoot[R]{\headfootfont \theslide}

% To avoid that the headers be too close of the top of the page
\renewcommand{\slidetopmargin}{2cm}

% To center horizontally the headers and footers
\renewcommand{\headwidth}{\textwidth}

% Breite von Kopf- und Fusszeile an Seitenbreite anpassen
\autoslidemarginstrue

% Formatvorlage für Folien und Overlays
\slideframe{none}
\overlayframe{none}
\slidepagestyle{fancy}
\overlaypagestyle{empty}

%%%
\title{Diffie-Hellmann Key Exchange}
\author{Heinrich Moser}
\date{}

\begin{document}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \maketitle
  \begin{center}
    \begin{small}\url{http://www.heinzi.at}\end{small}
  \end{center}
  \addtocounter{slide}{-1}
  \slidepagestyle{empty}
\end{slide}

% NOTES
\begin{itemize}
\item Anfang: Wie wir aus der Vorlesung wissen, sind
  \textbf{symmetrische} Verschlüsselungalgorithmen
  \textbf{effizienter} als asymmetrische. D.h. wenn wir irgendeine
  Form von \textbf{Echtzeit-Kommunikation} über das Internet
  \textbf{verschlüsseln} wollen, z.B.  eine \textbf{ssh-Session}, so
  möchten wir symmetrische Verschlüsselung verwenden. Bei
  symmetrischer Verschlüsselung haben wir allerdings \textbf{ein
    Problem}: den \textbf{sicheren Austausch} des symmetrischen
  Schlüssles.  [Wechsel auf nächste Folie]
\end{itemize}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \setprogress{|>{\columncolor{cyan}}l|l|l|l|l|} % Einführung
  \blueheading{Schlüsselübermittlung (key exchange)}
  \bigskip\bigskip

  Problem:

  \begin{itemize}
  \item Symmetrischer Schlüssel muss ausgetauscht werden
  \end{itemize}

  \medskip

  Lösungen:

  \begin{itemize}
  \item verschiedene Kanäle
  \item asymmetrische Verschlüsselung
  \item Schlüsselaustauschprotokoll
  \end{itemize}

\end{slide}

% NOTES

\begin{itemize}
\item Verschiedene Kanäle
\begin{itemize}
\item Post, Telefon, Persönlich
\item nicht praktisch automatisierbar (Beispiel ssh)
\end{itemize}
\item asymmetrische Verschlüsselung
\begin{itemize}
\item nur Sitzungsschlüssel wird symmetrisch verschlüsselt
\item Risiko (Methode zur Primzahlfaktorisierung wird gefunden)
\end{itemize}
\end{itemize}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \setprogress{|l|>{\columncolor{cyan}}l|l|l|l|} % Verfahren
  \blueheading{Diffie-Hellmann}
  \bigskip
  
  \begin{itemize}
  \item Sitzungsschlüssel wird von A und B gemeinsam erzeugt
  \item erster Public-Key Algorithmus (1976)
  \item nur für Schlüsselaustausch (keine Verschlüsselung)
  \item ein paar Jahre zuvor vom GCHQ entwickelt
  \end{itemize}

\end{slide}

% NOTES
\begin{itemize}
\item Historisch interessant
\item "`Erfinder"' der Public-Key Kryptographie
\item Sitzungsschlüssel nicht von A generiert und an B geschickt
  sondern aus den aus Daten von A und B erzeugt.
\item GCHQ = Government Communications Headquarters, britischer
  Geheimdienst
\end{itemize}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \blueheading{Diffie-Hellmann}
  \bigskip

  \begin{center}
    gemeinsam: $g$\overlay{1}\textblue{, $p$}\overlay{0} \\
    \bigskip
    \begin{tabular}{rcccl}
      & A & & B \\
      \hline
      wählt     & $\textred{x}$ & & $\textred{y}$ & \\
      berechnet & $g\textred{^x}$ & & $g\textred{^y}$ & \overlay{1}\textblue{${}\bmod p$}\overlay{0}\\
      & & \begin{picture}(10,10)(-5,-5)
            \put(-20,10){\vector(2,-1){44.72}}
            \put(20,10){\vector(-2,-1){44.72}}
          \end{picture} & & \\
      berechnet & $(g^y)\textred{^x}$ & $=$ & $(g^x)\textred{^y}$  
                & $= g^{xy} \overlay{1}\textblue{{}\bmod p}\overlay{0}$ \\
    \end{tabular} \\
    \bigskip
    \begin{tabular}{|c|}
      \hline
      symmetrischer Schlüssel: $g^{xy}$ \overlay{1}\textblue{${}\bmod p$}\overlay{0} \\
      \hline
    \end{tabular}
  \end{center}
\end{slide}

Beispiel:
\begin{enumerate}
\item $g = 5$, $p = 97$, $x = 36$, $y = 58$
\item $5^{36} \bmod 97 = 50 \bmod 97$, $5^{58} \bmod 97 = 44 \bmod 97$
\item Transfer 50, 44
\item $44^{36} \bmod 97 = 75 \bmod 97$, $50^{58} \bmod 97 = 75 \bmod 97$
\end{enumerate}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \blueheading{Algorithmus}
  \medskip

  \begin{enumerate}
  \item A und B wählen gemeinsam öffentliche Zahlen
    \begin{itemize}
    \item $p$ (große Primzahl)
    \item $g$ (primitiv bzgl. $p$)
    \end{itemize}
  \item A wählt $x$ ($< p$, geheim), schickt $X = \textblue{g^x \bmod p}$ an B
  \item B wählt $y$ ($< p$, geheim), schickt $Y = \textblue{g^y \bmod p}$ an A
  \item A berechnet \textred{$Y^x \bmod p$} (= $g^{xy} \bmod p$)
  \item B berechnet \textred{$X^y \bmod p$} (= $g^{xy} \bmod p$)
  \end{enumerate}

  \medskip

  \begin{center}
    \textred{$g^{xy} \bmod p$} ist der gemeinsame symmetrische
    Schlüssel.
  \end{center}
\end{slide}

% NOTES
\begin{itemize}
\item "`$a$ ist primitiv bzgl. $p$"' bedeutet: $a^1 \bmod p$ \ldots
  $a^{p-1} \bmod p$ sind alle verschieden und erzeugen die Zahlen $1$
  bis $p-1$.  $a$ ist dann ein "`Erzeuger"' von $Z_p$.
\item gemeinsamer symmetrischer Schlüssel = Sitzungsschlüssel
\end{itemize}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \blueheading{Public-Key Infrastruktur}

  \bigskip

  \begin{itemize}
  \item $\textblue{g^{x} \bmod p}$ ist der öffentliche Schlüssel.
  \item $\textred{x}$ ist der private Schlüssel.
  \end{itemize}

  \medskip

  \begin{center}
    \begin{tabular}{p{2.5cm}|p{2.5cm}p{0.3cm}p{3.5cm}}
      \centering A & \centering B & ~ & ~ \\
      \multicolumn{2}{c}{
        \begin{tabular}{|c|}
          \hline
          öffentliches Verzeichnis \\
          \hline
        \end{tabular}
      } & ~ & enthält Pub.Keys \\
      \centering $\textblue{g^{y} \bmod p}$ \hfill $\downarrow$ \hfill ~
      &  \centering ~ \hfill $\downarrow$ \hfill $\textblue{g^{x} \bmod p}$
      & ~ & \\
      \medskip \centering $(g^{y})^{\textred{x}} \bmod p$ 
      & \medskip \centering $(g^{x})^{\textred{y}} \bmod p$ 
      & ~ & \medskip = Sitzungsschlüssel
    \end{tabular}
  \end{center}

\end{slide}

% NOTES
\begin{itemize}
\item Keine Übertragung von A nach B notwendig
\item $p$ und $g$ sind öffentlich und für alle gleich
\end{itemize}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \setprogress{|l|l|>{\columncolor{cyan}}l|l|l|} % Mathematik
  \blueheading{Warum sicher?}

  \bigskip\bigskip

  \begin{itemize}
  \item \textblue{$X = g^{x}$ \hspace{1cm} $\rightarrow$ \hspace{1cm} $x = log_g X$} \\
  \item Im Körper $\textred{{\mathbb{Z}}_p = (\{0, 1, \ldots, p-1\}, *, +)}$, $p$ Primzahl: \\
    \textblue{$X = g^{x}$ \hspace{1cm} $\rightarrow$ \hspace{1cm} Bestimmung von $x$ "`schwer"'} \\
    (Bedingung: auch $\frac{p-1}{2}$ ist eine Primzahl).
  \item mindestens so schwer wie Primzahlfaktorisierung (RSA)
  \end{itemize}

\end{slide}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \blueheading{Exponentialfunktion}

  \bigskip\bigskip

  \begin{itemize}
  \item $\mbox{exp}_g: \mathbb{N} \rightarrow \Bbb{Z}_p$
  \item $g$ "`primitiv bzgl. $p$"', "`Primitivwurzel"', "`Erzeuger"' $\Leftrightarrow$ \\
    $\{g^x | x \in \{1, \ldots, p-1\}\} = \{1, \ldots, p-1\}$
  \item \textblue{square-and-multiply}: $g^{13}$ (13 = binär 1101)
    
    $g^{13} = g^{2^3+2^2+2^0} = g^{2^3}*g^{2^2}*g^{2^0} = ((g^2)^2)^2*(g^2)^2*g$
    
    \begin{itemize}
    \item höchstens $2*log_2(x)$ Multiplikationen
    \end{itemize}
  \end{itemize}

\end{slide}

% NOTES
\begin{itemize}
\item Primitivwurzel notwendig, um Größe des Schlüsselraums zu
  erhalten
\end{itemize}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \blueheading{Primitivwurzel}

  \bigskip\bigskip

  \begin{center}
    $\mathbb{Z}_5$ ($p$ = 5) \medskip

    \begin{tabular}{|l||r|r|r|r|r|}
      \hline
      & x =& 1 & 2 & 3 & 4 \\
      \hline \hline
      $g = 1$ & $1^x =$ & 1 & 1 & 1 & 1 \\
      $\textred{g = 2}$ & $\textred{2^x =}$ & \textred{2} & \textred{4} & \textred{3} & \textred{1} \\
      $\textred{g = 3}$ & $\textred{3^x =}$ & \textred{3} & \textred{4} & \textred{2} & \textred{1} \\
      $g = 4$ & $4^x =$ & 4 & 1 & 4 & 1 \\
      \hline
    \end{tabular}
  \end{center}

\end{slide}

% NOTES
\begin{itemize}
\item $x$ Raum für geheimen Schlüssel
\item $g^x$ Raum für öffentlichen und gemeinsamen Schlüssel
\end{itemize}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \blueheading{Diskreter Logarithmus}

  \bigskip\bigskip

  \begin{itemize}
  \item $\mbox{log}_g: \Bbb{Z}_p \rightarrow \Bbb{N}$
  \item Keine Annäherung \hspace{0.5cm} ($x < y \not\Rightarrow \log_g(x) < \log_g(y)$)
  \item Lösungen: {\small (sub-)exponentialer Aufwand bzgl. Bitlänge}
    \begin{itemize}
    \item durchprobieren
    \item baby-step giant-step {\small (hoher Speicherbedarf)}
    \item Pohlig-Hellmann {\small (kleine Primteiler von $p-1$)}
    \item Pollard-Rho
    \item Index-Calculus
    \end{itemize}
  \end{itemize}
  
\end{slide}

% NOTES
\begin{itemize}
\item $x < y \Rightarrow \log_g(x) < \log_g(y)$ in $\mathbb{R}^+$
\item baby-step giant-step = Shank's Algorithmus
\item Shank's und Pohlig-Hellmann auch exponential, aber mit kleinerem Exponenten.
\item Pollard-Rho bester Algorithmus aus der Gruppe der collision search-Methoden.
\item Index-Calculus ist Gruppe von Algorithmen, die gewisse
  mathematische Eigenschaften brauchen. Beste bekannte Algorithmen für
  disketen Log.
\end{itemize}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \setprogress{|l|l|l|>{\columncolor{cyan}}l|l|} % Attacken
  \blueheading{Attacken}

  \bigskip\bigskip

  \begin{itemize}
  \item \textbf{Man-in-the-middle Attack} \\
    Abhilfe: Station-to-Station Protokoll (Diffie, van Oorschot,
    Wiener: 1992) oder Interlock Protokoll (Rivest, Shamir: 1984)
  \item \textbf{Bekannte Verfahren} \\
    Abhilfe: $p$ gut wählen
  \item \textbf{Quantencomputer}
  \item \textbf{Knacken des symmetrischen Verfahrens}
  \end{itemize}

\end{slide}

% NOTES
\begin{itemize}
\item STS übermittelt $g^x$, sig($g^x$), PubKey, Zertifikat
\item Interlock: Allgemeines Verfahren zum Aufspüren von
  man-in-the-middle-Attacken
\end{itemize}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \blueheading{Attacken (Zukunft)}

  \bigskip\bigskip

  \begin{itemize}
  \item \textbf{allgemeine Lösung \textblue{diskreter Logarithmus}}
    \begin{tabbing}
      Gegeben: \= $g^x$ \\
      Gesucht: \> $x$
    \end{tabbing}
  \item \textbf{allgemeine Lösung \textblue{Diffie-Hellmann-Problem}}
    \begin{tabbing}
      Gegeben: \= $g^x$, $g^y$ \\
      Gesucht: \> $g^{xy}$
    \end{tabbing}
  \end{itemize}

\end{slide}

\begin{itemize}
\item nicht bewiesen, dass diskLog und DHProb äquivalent sind
\end{itemize}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \setprogress{|l|l|l|l|>{\columncolor{cyan}}l|} % Ende
  \blueheading{Unterlagen}

  \bigskip\bigskip

  \begin{itemize}
    \item W. Diffie and M.E. Hellman. New directions in cryptography.
      \textit{IEEE Transactions on Information Theory}, IT-22: 644-654, 1976.
    \item Patent 1997 abgelaufen
    \item ElGamal-Algorithmus (gleiches Prinzip)
    \item RFC 2631 (Juni 1999), basierend auf ANSI X9.42
    \item Vortragsfolien: \url{http://www.heinzi.at}
  \end{itemize}

\end{slide}

% NOTES
\begin{itemize}
\item im RFC auch genaue Kriterien und Algorithmen gegeben (z.B. zur
  Generierung von g) gegeben
\end{itemize}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \blueheading{\huge{FRAGEN?}}
\end{slide}

\end{document}

% --------------------------------- SLIDE ---------------------------------
\begin{slide}
  \blueheading{}

  \bigskip\bigskip

\end{slide}