\documentclass{beamer}
%\documentclass[handout,gray]{beamer}
\usepackage{german}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{mathptmx,graphicx,textcomp}
\usepackage[scaled=.90]{helvet}
\usepackage{courier}



\mode<presentation>
{
  \usetheme{Frankfurt}
  \useoutertheme{infolines}
  %\usecolortheme{dove}
}



\hypersetup{pdfkeywords={ElGamal, Kryptographie, Verschlüsselung}}

\title{Chiffrierung nach \textsc{ElGamal}}
\author{CryptoCon13}
\date{14. April 2013}
\logo{\href{http://www.sublab.org/}{\includegraphics[width=5mm]{sublab_logo_text}}}




\begin{document}
\begin{frame}
\titlepage
\end{frame}

\begin{frame}
\frametitle{Agenda}
\tableofcontents
\end{frame}

\section{Grundlagen}
\begin{frame}
\frametitle{Allgemeines}

\begin{itemize}
\item \textsc{ElGamal}-Verfahren ist ein asymmetrisches Chiffrierverfahren, d.h., Chiffrierschlüssel $\neq$ Dechiffrierschlüssel
\item asymmetrische Chiffrierverfahren mit großer Rechenintensität verbunden \textrightarrow\ oft nur in Kombination mit symmetrischen Verfahren eingesetzt
\item Beschreibung des \textsc{ElGamal}-Verfahren u.\,a. im "`Handbook of Applied Cryptography"' (online verfügbar)
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Erzeugung des Schlüsselpaares}

\begin{enumerate}
\item Bestimme große, sichere Primzahl $p=2q+1$, so daß auch $q$ eine Primzahl ist
\item Bestimme primitives Element $\alpha$\footnote{$\mathbf{Z}^\ast_p = \left\{\alpha ^i \bmod p\ |\ 0 \leq i \leq p-2\right\}$} bzgl. $\mathbf{Z}^\ast_p$
\item Wähle ein beliebiges $a$ mit $1 \leq a \leq p-2$.
\item Berechne $\beta := \alpha ^a \bmod p$.
\end{enumerate}
\begin{itemize}
\item Öffentlicher Schlüssel $\mathcal{K}_\mathrm{pub} := (p, \alpha, \beta)$
\item Privater Schlüssel $\mathcal{K}_\mathrm{prv} := (p, a)$
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Verschlüsselung mit öffentlichem Schlüssel}
\begin{itemize}
\item Sei $x \in \mathcal{P}$ mit $0 \leq x \leq p-1$ beliebiger Klartextblock
\item Wähle für jeden Klartextblock ein zufälliges $\lambda$ mit $1 \leq \lambda \leq p-2$
\item $y_1:= \alpha^\lambda \bmod p$
\item $y_2:= x \cdot \beta^\lambda \bmod p$
\item $\mathcal{E_{K_\mathrm{pub}}}(x):=(y_1, y_2)$
\end{itemize}
\begin{itemize}
\item Geheimtext doppelt so lang wie der Klartext
\item Menge möglicher Geheimtexte größer als Menge der Klartexte \textrightarrow\ probabilistische Verschlüsselung
\end{itemize}
\end{frame}

\begin{frame}
\frametitle{Entschlüsselung mit privatem Schlüssel}

\begin{eqnarray*}
\mathcal{D_{K_\mathrm{prv}}}(y_1, y_2) &:=& y_2 \cdot y_1^{-a} \bmod p\\
&:=& x \cdot \beta^\lambda \cdot \alpha^{-a\lambda} \bmod p\\
&:=& x \cdot \alpha^{a\lambda} \cdot \alpha^{-a\lambda} \bmod p\\
&=& x
\end{eqnarray*}
Verringerung des Rechenaufwandes durch Anwendung des Kleinen Satzes von Fermat:
\begin{eqnarray*}
\mathcal{D_{K_\mathrm{prv}}}(y_1, y_2) &:=& (y_2 \bmod p) \cdot (y_1^{p-1-a} \bmod p)
\end{eqnarray*}
\end{frame}

\begin{frame}
\frametitle{Sicherheit}
\begin{itemize}
\item Brechen der ElGamal-Chiffrierung bei bekanntem öffentlichen Schlüssel und Geheimtext \textrightarrow\ Diffie-Hellman-Problem
\item Bis zum heutigen Zeitpunkt: Lösen des Diffie-Hellman-Problems nur über Berechnung diskreter Logarithmen
\item Angriff: privaten Schlüsselteil $a$ aus dem öffentlichen Schlüssel $(p, \alpha, \beta)$ berechnen: $\beta\equiv \alpha ^a \bmod p$
\item Berechnen von $a$ (sog. diskreter Logarithums) schwer im Vergleich zur Berechnung von $\beta$ \textrightarrow\ Einwegfunktion
\end{itemize}

Weiterhin ist es wichtig, $\lambda$ immer zufällig zu wählen und dafür einen gute Zufallsquelle zu verwenden.
\end{frame}

\section{Lizenz}
\begin{frame}
\frametitle{Lizenz}
\begin{center}
\includegraphics{cc0}
\end{center}
To the extent possible under law, the person who associated CC0 with this work has waived all copyright and related or neighboring rights to this work.
\url{http://creativecommons.org/publicdomain/zero/1.0/deed.de}
\end{frame}
\end{document}
