\makeatletter\let\ifGm@compatii\relax\makeatother
%\documentclass{beamer}
\documentclass[notes,page number]{beamer}
%\documentclass[trans]{beamer} % PAS OVERLAYS
%\documentclass[handout]{beamer} % PAS OVERLAYS

%\documentclass[red]{beamer}  % TOUT ROUGE
%\documentclass[compress]{beamer}  % ??? taile sortie???

%\documentclass[draft]{beamer}  % Enleve les section

%\documentclass{article} % fait des slides ``LATEX''
%\usepackage[envcountsect]{beamerarticle}

% Do NOT take this file as a template for your own talks. Use a file
% in the directory solutions instead. They are much better suited.

% Try the class options [notes], [notes=only], [trans], [handout],
% [red], [compress], [draft] and see what happens!

% Copyright 2003 by Till Tantau <tantau@users.sourceforge.net>.
%
% This program can be redistributed and/or modified under the terms
% of the LaTeX Project Public License Distributed from CTAN
% archives in directory macros/latex/base/lppl.txt.
 
% For a green structure color use:
%\colorlet{structure}{green!50!black}

\mode<article> % only for the article version
{
  \usepackage{fullpage}
  \usepackage{hyperref}
}

\mode<presentation>
{
%\usetheme{Antibes} %++ Bleu noir up +
% \usetheme{Berkeley} %+ Bleu Gauche
%\usetheme{Berlin} % Bleu Gauche up -
% \usetheme{default} % Soft
% \usetheme{Dresden} % bleu Rond
% \usetheme{Goettingen} %soft degrade droit
% \usetheme{Hannover} % soft bleute  gauche
% \usetheme{Luebeck} %++ black bleu milieu
% \usetheme{Malmoe} % ++ black bleu milieu
% \usetheme{Marburg} % ++ black degrade bleu droite
%%%% 


%\usetheme{Pittsburgh} %soft classique droite + item rond
% \usetheme{Rochester} % + bleu up titre
%\usetheme{Copenhagen} % ++ black noir NO GASTEX
% \usetheme{Darmstadt} % black bleu pb NO GASTEX
%\usetheme{Frankfurt} % black bleu NO GASTEX
% \usetheme{Ilmenau} % bleu pb up NO GASTEX
% \usetheme{JuanLesPins} % ++ up black bleu Titre  NO GASTEX
% \usetheme{Malmoe} % ++ black bleu milieu
% \usetheme{Madrid} % +soft bleu titre...  NO GASTEX
% \usetheme{PaloAlto} % bleu bleu gauche.. NO GASTEX
%\usetheme{Singapore} % bleute up Rond  NO GASTEX
% \usetheme{Szeged} % Soft bleute up Rond
% \usetheme{Warsaw} %++ black bleu milie  NO GASTEX

%\usetheme{Montpellier} % ++ soft up plan .. blanc OK 


\usetheme{These} %



\beamertemplatenavigationsymbolsempty

%numero de page enbas gauche
\setbeamertemplate{footline}
{ \begin{flushright}
\textcolor{Violet}{\insertframenumber{} / \inserttotalframenumber
\hspace*{2ex}  }
\end{flushright}
}
%  \useinnertheme[shadow=true]{rounded} %PB
% \setbeamertemplate{background canvas}[vertical shading]%[bottom=red!10,top=blue!10]

}

\usepackage{tikz,pgflibraryarrows,pgffor,pgflibrarysnakes}


\usetikzlibrary{snakes}

\usepackage[english]{babel}
 %\usepackage{pstricks}
%\usepackage{graphicx,epsfig}
\usepackage{amsmath,amssymb}
\usepackage{mathpartir}
\usepackage{eurosym}
\usepackage{url} 

\usepackage{epsfig}
%\usepackage{pstricks,pst-grad,pst-node}

%\usepackage{pstricks,pst-grad,pst-node,pst-tree,pspicture,pifont}
\usepackage{graphicx}

%\usepackage{gastex}

\usepackage{xcolor}


\graphicspath{{IMAGES/}}


\include{macro}

\input{macros}% Yassine

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\xdefinecolor{LemonChiffon}{rgb}{1,.98,.8}
\xdefinecolor{Vert}{rgb}{0.01,.5,0.13}
%\xdefinecolor{Vert}{rgb}{0.07,0.5,0.4}
%\xdefinecolor{Bleu}{rgb}{0,.2,.54}
\xdefinecolor{Bleu}{rgb}{0, .4, .6} % en fait le bleu du LSV
\xdefinecolor{Ver}{rgb}{0.0525,0.375,0.3}
\xdefinecolor{Rouge}{rgb}{1,0,0}
\xdefinecolor{Violet}{rgb}{.5,0,.7}
\xdefinecolor{Bordeaux}{rgb}{.7,.2,0}
\xdefinecolor{Ivory}{rgb}{1,1,0.9}
\xdefinecolor{Marron}{rgb}{0.6,0.4,0.4}
\xdefinecolor{GrisClair}{rgb}{0.75,0.75,0.75}
\xdefinecolor{GrisFonce}{rgb}{0.55,0.55,0.55}
\xdefinecolor{BleuMarine}{rgb}{0,0,0.5}
%\xdefinecolor{BleuMarine}{rgb}{0.2,.1,.9}
%\xdefinecolor{BleuMarine}{rgb}{0,0,0.5}
\xdefinecolor{Turquoise}{rgb}{0.4,1.,1.}
\xdefinecolor{Rose}{rgb}{1.0,0.8,0.8}
\xdefinecolor{RoseFonce}{rgb}{0.8,0.,0.6}
\xdefinecolor{Blanc}{rgb}{0,0,0}
\xdefinecolor{Jaune}{rgb}{1,1,0}
%\xdefinecolor{Jaune}{rgb}{.95,.63,.21}

\xdefinecolor{Mycolor}{rgb}{.95,.81,.81} % 
%\xdefinecolor{Jaune}{rgb}{1,.9,0}
%\xdefinecolor{Jaune}{rgb}{.9,.6,.2}

% \newrgbcolor{orange}{.7 .2 0}

% \definecolor{bleu}{rgb}{0,.2,.54}
% \newrgbcolor{Rouge}{1 0 0}
% \newrgbcolor{ivory}{1 1 0.9}
% \newrgbcolor{Marron}{0.6 0.4 0.4}
% \newrgbcolor{GrisClair}{0.75 0.75 0.75}
% \newrgbcolor{GrisFonce}{0.55 0.55 0.55}
% \newrgbcolor{BleuMarine}{0 0 0.5}
% \newrgbcolor{Turquoise}{0.4 1. 1.}
% \newrgbcolor{ver}{0.0525 0.375 0.3}
% \newrgbcolor{Rose}{1.0 0.8 0.8}
% \newrgbcolor{RoseFonce}{0.8 0. 0.6}
% \newrgbcolor{Violet}{0.5 0. 0.7}
% \newrgbcolor{BleuMarine}{0 0 0.5}
% \newrgbcolor{vert}{0.07 0.5 0.4}
% \newrgbcolor{violet}{0.5 0. 0.7}
% %\definecolor{violet}{rgb}{.5,0,.7}
% \definecolor{bleu}{rgb}{0,.2,.54}
% \definecolor{LemonChiffon}{rgb}{1.,0.98,0.8}
% \newrgbcolor{toto}{0.6 1 0.6}
% \newrgbcolor{LemonChiffon}{1 0.98 0.8}
% \newrgbcolor{RoseFonce}{0.8 0. 0.6}
% \newcmykcolor{WildStrawberry}{0 0.96 0.39 0}

% \newrgbcolor{blanc}{0 0 0}


\def\pair#1#2{\langle #1, #2 \rangle}    \def\crypt#1#2{\{#1\}_{#2}}           
\def\dect{\vdash}                    


\title{\bf{Introduction to Cryptography}}
 \author{\bf{Pascal Lafourcade}  }

\institute{  \includegraphics[width=2cm]{logo_limos_coul_def} \hfill 
\includegraphics[width=1.5cm]{UCA.png}} 

 \date[]{ESC January 2021}


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


 \AtBeginSection[]
 {
   \begin{frame}<beamer>
     \frametitle{Outline}
     \tableofcontents[currentsection]
   \end{frame}
 }


\pgfdeclareimage[interpolate=true,height=1cm]{lettre}{IMAGES/lettre1}
\pgfdeclareimage[interpolate=true,height=2cm]{alice}{IMAGES/ALICE01}
\pgfdeclareimage[interpolate=true,height=2cm]{bob}{IMAGES/whiterabbit01.jpg}
\pgfdeclareimage[interpolate=true,height=1.5cm]{intrus}{IMAGES/cheshire01.jpg}
\pgfdeclareimage[interpolate=true,height=1.5cm]{chiffre}{IMAGES/chest121.jpg}
%\pgfdeclareimage[interpolate=true,height=.8cm]{k3}{key3.jpeg}
%\pgfdeclareimage[interpolate=true,height=.8cm]{k1}{key2.png}

\pgfdeclareimage[interpolate=true,height=.8cm]{kpub}{clef_publique.pdf}
\pgfdeclareimage[interpolate=true,height=.8cm]{kpriv}{clef_privee.pdf}

\pgfdeclareimage[interpolate=true,height=.8cm]{k2}{IMAGES/key-300}
\pgfdeclareimage[interpolate=true,height=.8cm]{ksym}{pure_clef_sym.pdf}


\section{Historic of  Cryptography}



\begin{frame}
\frametitle{Art to hide written secret} 


%\includegraphics[width=2cm]{crypto2}

  \begin{tikzpicture}
    \node (1) at (-0.5,0) {\includegraphics[width=1.5cm]{ecrire.jpg}};
\pause

\node (2bis) at (2,-2) {Steganography};
    \node (2) at (2,-1) {\includegraphics[width=1.5cm]{HeadMessage2}};
\draw [-latex] (1) -- (2);

\pause
\node (3) at (2,2) {Cryptography};
 \draw [-latex] (1) -- (3);

\pause

    \node (4) at (6,1) {Transposition};
        \node (4bis) at (6,0) {\includegraphics[width=2cm]{260px-Skytale.png}};
           \draw [-latex] (3) -- (4);
\pause
\node (5) at (6,3) {Substitution};
  \draw [-latex] (3) -- (5);

\pause
    

\node (7bis) at (9,3.25) {\includegraphics[width=1.5cm]{carottes.jpg} };
\node (7) at (9,4) {Code};

       \draw [-latex] (5) -- (7);
\pause

    \node (6) at (9,2) {Encryption};
    \node (6bis) at (9,1.25) {\includegraphics[width=2cm]{lhd1.jpg}};
     \draw [-latex] (5) -- (6);
     
  \end{tikzpicture}

%% \begin{center}
%% \includegraphics[scale=.7]{secret-writing}
%% \end{center}


%% \begin{itemize} \itemsep=4pt
%% \item \textcolor{red}{ Cryptology}: the study of secret writing.

%% \item \textcolor{red}{ Steganography}: the science of hiding messages in
%% other messages.

%% \item \textcolor{red}{ Cryptography}: the science of secret writing. 

%% Note: terms like \textcolor{red}{ encrypt}, \textcolor{red}{ encode}, and \textcolor{red}{ encipher}
%% are often (loosely and wrongly) used interchangeably

%\item \textcolor{red}{ Cryptanalysis:} science of recovering the plaintext from
%  ciphertext without the key.
%\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Applications}

\vspace{-1cm}

\includegraphics[width=2cm]{https-background}\hfill %web-security1}\hfill
\includegraphics[width=1.5cm]{vitale}\hfill
\includegraphics[width=2cm]{new-york-liberty-credit-card}\hfill
%carte_bancaire}
\includegraphics[width=2cm]{parabole}\hfill
\includegraphics[width=2cm]{samsung}
%mpx220_2}
%hypercom_0930}
%\includegraphics[width=1.5cm]{50-20-20}



\ \\

\includegraphics[width=2cm]{wifi-hotspot-router}\hfill
\includegraphics[width=2cm]{tomtom-go-700}\hfill
\includegraphics[width=2cm]{banque}\hfill
\includegraphics[width=2cm]{declaration}\hfill
\includegraphics[width=1.5cm]{urne}


%\includegraphics[width=1.5cm]{story.digital.sig}
%\includegraphics[width=1.5cm]{gps}


\end{frame}


\begin{frame}
\frametitle{Long time ago}

 \begin{center}
\includegraphics[scale=0.5]{classical-cipher}
\end{center}
\end{frame}


%% \begin{itemize}
%% %\item Used 4000 years ago by Egyptians to encipher hieroglyphics.

%% \item  2000 years ago Julius Caesar used a simple substitution cipher.

%% \item  Leon Alberti devised a cipher wheel, and described the
%%   principles of frequency analysis in the 1460s.
%% \end{itemize}
%% \end{frame}

 
%% \begin{frame}
%% \frametitle{Mono-alphabetic substitution ciphers}
%% \begin{itemize}
%% \item Simplest kind of cipher.  Idea over 2,000 years old.

%% \item   Let $\cK$ be the set of all permutations
%% on the alphabet $\calA$.  
%% Define for each $e \in \calK$ an encryption
%% transformation $E_e$ on strings $m = m_1 m_2 \cdots m_n \in \calM$
%% as
%% \[ E_e(m) = e(m_1)e(m_2) \cdots e(m_n) = c_1c_2 \cdots c_n = c \,.\]

%% \item To decrypt $c$, compute the inverse permutation $d = e^{-1}$
%% and
%% \[ D_d(c) = d(c_1)d(c_2) \cdots d(c_n) = m \,.\]

%% \item $E_e$ is a \textcolor{red}{ simple substitution cipher} or a
%% \textcolor{red}{ mono-alphabetic substitution cipher}.
%% \end{itemize}


%% Security ? \pause very weak, try the 26 possibilities ;-)
%% \end{frame}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{frame}
\frametitle{Grecks and Scythale}

\includegraphics[width=4cm]{260px-Skytale.png}

\pause

\begin{center}
\includegraphics[scale=.5]{scytale}

Transposition
\end{center}
\end{frame}


\begin{frame}
\frametitle{Romans} 


 \begin{center}
\includegraphics[width=4cm]{Cesar--Asterix-.jpg}

Caesar Encryption

Substitution +3
\vfill

\vspace{.5cm}

\pause Dyh Fhvdu

% Ave L oryh brx

\vfill

\pause   Ave Cesar
%I love you

\end{center}
\end{frame}


\begin{frame}
\frametitle{Is it secure ?}
\pause
\begin{center}
\includegraphics[width=9cm]{frequence-apparition-lettres-francais.jpg}

Frequence Analysis
\end{center}

\end{frame}



%% \begin{frame}
%% \frametitle{ Improvement: Homophonic substitution ciphers}

%%   $$\calA = \{a,b\}$$

%%  $H(a) = \{00,10\}$, and $H(b) = \{01,11\}$.


%% \begin{example}
%% The plaintext $ab$ encrypts to one of 0001, 0011, 1001, 1011.
%% \end{example}

%% \pause

%% \begin{itemize}
%% \item Rational: makes frequency analysis more difficult.
%% \item Cost: data expansion and more work for decryption.
%% \end{itemize}

%% \end{frame}


\begin{frame}
\frametitle{Substitution  polyalphabetic (Alberti, Vigen\`ere 1553)} 

\begin{center}
\includegraphics[scale=.26]{cipher_disk}
\end{center}

Example with the key  k = 3,7,10

\begin{center}
 ~~~~m = CON NAI TRE 
\end{center}
\pause
\begin{center}
$E_k(m)$ = FVX QHS WYO
\end{center}

\end{frame}




\begin{frame}
\frametitle{Kerchoff’s Principle}


 In 1883, a Dutch linguist Auguste Kerchoff von Nieuwenhof stated in
 his book ``La Cryptographie Militaire'' that: 

\begin{center}
 ``the security of a crypto-system must be totally dependent on the
 secrecy of the key, not the secrecy of the algorithm.''
\end{center}


%% The strength of an encryption algorithm does not reside in the secrecy of the algorithm

%% Corollary:
%% The strength of an encryption algorithm is not measurable unless the algorithm is known


%Published in 1883.
  Author’s name sometimes spelled Kerckhoff


%% Kerchoff’s Principle (1883): System should be secure even if
%% algorithms are known, as long as key is secret

\end{frame}

\begin{frame}
\frametitle{Encryption : Enigma (Second World War) }

\quad \includegraphics[width=2cm]{Cesar--Asterix-.jpg}\quad + \quad \includegraphics[width=2cm]{Cesar--Asterix-.jpg} \quad =  \quad \pause \includegraphics[width=2cm]{Cesar--Asterix-.jpg}

\pause
\ \\

\quad \includegraphics[width=2cm]{260px-Skytale.png} \quad + \quad \includegraphics[width=2cm]{260px-Skytale.png} \quad = \pause  \quad \includegraphics[width=2cm]{260px-Skytale.png}

\ \\

\pause

\includegraphics[width=.75cm]{260px-Skytale.png}  +  \includegraphics[width=.75cm]{Cesar--Asterix-.jpg} +  \includegraphics[width=.75cm]{260px-Skytale.png}  +  \includegraphics[width=.75cm]{Cesar--Asterix-.jpg} +  \includegraphics[width=.75cm]{260px-Skytale.png} +   \includegraphics[width=.75cm]{Cesar--Asterix-.jpg}+ \includegraphics[width=.75cm]{260px-Skytale.png}  +  \includegraphics[width=.75cm]{Cesar--Asterix-.jpg}   =  \includegraphics[width=1cm]{enigma}



\end{frame}




\begin{frame}
\frametitle{One-Time Pad (Vernam 1917)} 

\vspace{-1cm} ~\hfill \includegraphics[scale=.5]{telrouge}



Example:

\begin{center}
$\begin{array}{rll}
m &=& 010111\\
k &=& 110010\\ \hline
c & =& 100101
\end{array}$
\end{center}
\end{frame}



\begin{frame}
\frametitle{Shannon's Principle 1949}

\begin{block}{Confusion}
The purpose of confusion is to make the relation between the key and the ciphertext as complex as possible. 
\end{block}

Ciphers that do not offer much confusion (such as Vigenere cipher) are susceptible to frequency analysis. 
\pause
\begin{block}{Diffusion}
Diffusion spreads the influence of a single plaintext bit over many
ciphertext bits. 
\end{block}
The best diffusing component is substitution (homophonic)

\pause
\begin{block}{Principle}
A good cipher design   uses Confusion and Diffusion together
\end{block}
\end{frame}



%% \begin{frame}
%% \frametitle{ENIGMA}
%% \vspace{-.75cm}
%% \hfill \includegraphics[scale=.17]{enigma}

%% \vspace{-2cm}
%% Three-rotor German military Enigma machine

%% Dayly keys are used and stored in a book.

%% There are $10^114$ possibilities for one cipher.

%% \vspace{.75cm}
%% %%  Let $P$ denote the plugboard transformation, U denote the reflector,
%% %%  and $L,M,R$ denote the actions of the left, middle and right
%% %%  rotors. Then the encryption E can be expressed as:

%% %%  $    E = PRMLUL^{− 1}M^{− 1}R^{− 1}P^{− 1} $


%% \begin{block}{Other German Tricks}

%% A space was omitted or replaced by an X. The X was generally used as
%% point or full stop. They replaced the comma by Y and the question sign
%% by UD. The combination CH, as in "Acht" (eight) or "Richtung"
%% (direction) were replaced by Q (AQT, RIQTUNG).
%% \end{block}
%% \begin{center}
%% \includegraphics[scale=.5]{180px-Enigma-rotor-stack}
%% \end{center}

%% \end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%% \begin{frame}
%%   \frametitle{Churchyard cipher}

%% This ciphertext appeared engraved on a tombstone in Trinity 
%%       Churchyard (New York) in 1794.

%% \begin{center}
%%   \includegraphics[scale=1.2]{churchyard_cipher_text}
%%   \end{center}

%% First publisherd solution in 1896
%% \pause




      
%%       \begin{center}
%% 	\includegraphics[scale=2]{churchyard-key}
%% 	\end{center}

%%  REMEMBER DEATH

%% \end{frame}



\pgfdeclareimage[interpolate=true,height=1cm]{lettre}{IMAGES/lettre1}
\pgfdeclareimage[interpolate=true,height=2cm]{alice}{IMAGES/ALICE01}
\pgfdeclareimage[interpolate=true,height=2cm]{bob}{IMAGES/whiterabbit01.jpg}
\pgfdeclareimage[interpolate=true,height=1.5cm]{intrus}{IMAGES/cheshire01.jpg}
\pgfdeclareimage[interpolate=true,height=1.5cm]{chiffre}{IMAGES/chest121.jpg}
%\pgfdeclareimage[interpolate=true,height=.8cm]{k3}{key3.jpeg}
%\pgfdeclareimage[interpolate=true,height=.8cm]{k1}{key2.png}

\pgfdeclareimage[interpolate=true,height=.8cm]{kpub}{IMAGES/clef_publique.pdf}
\pgfdeclareimage[interpolate=true,height=.8cm]{kpriv}{IMAGES/clef_privee.pdf}

\pgfdeclareimage[interpolate=true,height=.8cm]{k2}{IMAGES/key-300}
\pgfdeclareimage[interpolate=true,height=.8cm]{ksym}{IMAGES/pure_clef_sym.pdf}


\section{Introduction to  Cryptography}


%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% \begin{frame}
%% \frametitle{Substitution cipher examples} 
%% \begin{itemize}
%% \item KHOOR ZRUOG \pause= HELLO WORLD

%% \textcolor{red}{Caesar cipher:} each plaintext character
%%     is replaced by the character three to the right modulo 26. \pause

%% \item    Zl anzr vf Nqnz \pause = My name is Adam

%% \textcolor{red}{ROT13}: shift each letter by 13 places.\\
%% Under Unix:  \textcolor{green}{ tr a-zA-Z n-za-mN-ZA-M}.

%% \item 2-25-5 2-25-5 \pause = BYE BYE

%% \textcolor{red}{Alphanumeric:} substitute numbers for letters.
%% \end{itemize}
%% How hard are these to cryptanalyze?   Caesar?  General?
%% \end{frame}


%% \begin{frame}
%% \frametitle{(In)security of substitution ciphers} 
%% \begin{itemize} %\itemsep=1pt

%% \item Key spaces are typically huge.  26 letters $\leadsto$ 26! possible keys.

%% \item Trivial to crack using frequency analysis (letters, digraphs...)

%% \item Frequencies for English based on data-mining books/articles.
%% %\vspace*{-10pt}
%%   \begin{center}
%% \includegraphics[scale=.6]{char-freq}
%% \end{center}

%% \end{itemize}

%% %% %\vspace*{-20pt}
%% %% $\Rightarrow$ Serdhrapvrf sbe Ratyvfu onfrq ba qngn-zvavat obbxf/negvpyrf.

%% %% \item Easy to apply, except for short, atypical texts
%% %% \pause
%% %% \emph{From Zanzibar to Zambia and Zaire, ozone zones make zebras run zany zigzags.}
%% %% \end{itemize}
%% %% \textcolor{red}{$\Rightarrow$} More sophistication required to
%% %% mask statistical regularities.
%% \end{frame}






%% \begin{frame}
%% \frametitle{Homophonic substitution ciphers}
%% \begin{itemize}
%% \item To each $a \in {\mathcal A}$, associate a set $H(a)$ of strings of $t$
%% symbols, where $H(a), a \in {\mathcal A}$ are pairwise disjoint.
%% A \textcolor{red}{homophonic substitution cipher} replaces each $a$ with a randomly
%% chosen string from $H(a)$.  To decrypt a string $c$ of $t$ symbols,
%% one must determine an $a \in {\mathcal A}$ such that $c \in H(a)$.  The key for
%% the cipher is the sets $H(a)$.
%% \end{itemize}

%% \pause

%% \begin{block}{Example:}  ${\mathcal A} = \{a,b\}$, $H(a) = \{00,10\}$,
%% and $H(b) = \{01,11\}$.  The plaintext $ab$ encrypts to one of 0001,
%% 0011, 1001, 1011.
%% \end{block}

%%  Rational: makes frequency analysis more difficult.

%% Cost: data expansion and more work for decryption.

%% \end{frame}


%% \begin{frame}
%% \frametitle{Example: Vigen{\`e}re ciphers} 
%% \begin{itemize}
%% \item Key given by sequence of numbers $e = e_1, \ldots, e_t$, where
%% \[p_i(a) = (a + e_i) \mbox{ mod } n \, \]
%% defining a permutation on an alphabet of size $n$.

%% \item Example: English ($n = 26$), with k = 3,7,10
%% \end{itemize}
%% \begin{center}
%%  m = THI SCI PHE RIS CER TAI NLY NOT SEC URE
%% \end{center}
%% then
%% \begin{center}
c%% $E_e(m)$ = WOS VJS SOO UPC FLB WHS QSI QVD VLM XYO
%% \end{center}
%% \end{frame}


%% \begin{frame}
%% \frametitle{One-time pads (Vernam cipher)} 
%% \begin{itemize}\itemsep=3pt
%% \item A \textcolor{red}{one-time pad} is a cipher defined over $\{0,1\}$. 
%% Message $m_1 \cdots m_n$ is encrypted by a binary key string $k_1 \cdots k_n$.
o%% \begin{eqnarray*}
%%   E_{k_1 \cdots k_n}(m_1 \cdots m_n) &=& (m_1 \oplus k_1) \cdots (m_n \oplus k_n) \\
%%   D_{k_1 \cdots k_n}(c_1 \cdots c_n) &=& (c_1 \oplus k_1) \cdots (c_n \oplus k_n)
%% \end{eqnarray*}


%% \item Example:
%% $\begin{array}{rll}
%% m &=& 010111\\
%% k &=& 110010\\ \hline
%% c & =& 100101
%% \end{array}$


%% \item Since every key sequence is equally likely, so is 
n%% every plaintext!   

%% Unconditional (information theoretic) security, if key isn't reused!

%% \item Moscow--Washington communication previously secured this way.

%% \item Problem?  \pause
%% Securely exchanging and synchronizing long keys.
%% \end{itemize}
%% \end{frame}
c


%% \begin{frame}
%% \frametitle{Example: transposition ciphers}
l%% \enlargethispage{20pt}
%% \begin{itemize}

%%   \item     $C=$  \textcolor{red}{A}duae\textcolor{red}{n}ttly\textcolor{red}{d}hato\textcolor{red}{i}ekou\textcolor{red}{n}letm\textcolor{red}{t}oiha\textcolor{red}{h}vsek\textcolor{red}{e}eele\textcolor{red}{e}yqo\textcolor{red}{n}ouv 
%% \pause

%%       \begin{center} \normalsize
%%       \begin{tabular}{|l|l|l|l|l|l|l|l|l|l|}        \hline
%%         A&n&d&i&n&t&h&e&e&n \\        \hline
%%         d&t&h&e&l&o&v&e&y&o \\        \hline
%%         u&t&a&k&e&i&s&e&q&u \\        \hline
%%         a&l&t&o&t&h&e&l&o &v \\ \hline
%%         e&y&o&u&m&a&k&e& & \\        \hline 
%%       \end{tabular} \\
%%     \end{center}
%% Table defines a permutation on {1, ..., 50}.
%%     \pause

%% \item Idea goes back to Greek \textcolor{red}{Scytale}: 
%% wrap belt spirally around baton and write plaintext lengthwise on it.

%% \medskip
%% \begin{center}
%%   \includegraphics[scale=.5]{scytale}
%% \end{center}





%% \end{itemize}

%% \end{frame}


%% \begin{frame}
%% \frametitle{Composite ciphers}
%% \begin{itemize}
%% \item Ciphers based on just substitutions or transpositions are
%% not secure 

%% \item Ciphers can be combined.  However \ldots
%% \begin{itemize}
%% \item  two substitutions are really only one more complex substitution,
%% \item two transpositions are really  only one transposition,
%% \item  but a substitution followed by a transposition makes a new 
%%   harder cipher.
%% \end{itemize}
%% \item Product ciphers chain \\
%% substitution-transposition combinations.
%% \item Difficult to do by hand \\
%% $\leadsto$ invention of cipher machines.

%% \begin{picture}(0,0)(0,0)
%% \put(200,-30){\includegraphics[scale=.18]{enigma}}
%% \end{picture}
%% \end{itemize}

%% \end{frame}



%% \begin{frame}
%% \frametitle{ENIGMA}
%% \vspace{-.75cm}
%% \hfill \includegraphics[scale=.17]{enigma}

%% \vspace{-2cm}
%% Three-rotor German military Enigma machine

%% Dayly keys are used and stored in a book.

%% There are $10^{114}$ possibilities for one cipher.

%% \vspace{.75cm}
%% %%  Let $P$ denote the plugboard transformation, U denote the reflector,
%% %%  and $L,M,R$ denote the actions of the left, middle and right
%% %%  rotors. Then the encryption E can be expressed as:

%% %%  $    E = PRMLUL^{− 1}M^{− 1}R^{− 1}P^{− 1} $


%% \begin{block}{Other German Tricks}

%% A space was omitted or replaced by an X. The X was generally used as
%% point or full stop. They replaced the comma by Y and the question sign
%% by UD. The combination CH, as in "Acht" (eight) or "Richtung"
%% (direction) were replaced by Q (AQT, RIQTUNG).
%% \end{block}
%% \begin{center}
%% %\includegraphics[scale=.5]{180px-Enigma-rotor-stack}
%% \end{center}

%% \end{frame}

%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%% \begin{frame}
%% \frametitle{Kerchoff’s Principle}



%%  In 1883, a Dutch linguist Auguste Kerchoff von Nieuwenhof stated in
%%  his book ``La Cryptographie Militaire'' that: 

%% \begin{center}
%%  ``the security of a crypto-system must be totally dependent on the
%%  secrecy of the key, not the secrecy of the algorithm.''
%% \end{center}


%% %% The strength of an encryption algorithm does not reside in the secrecy of the algorithm

%% %% Corollary:
%% %% The strength of an encryption algorithm is not measurable unless the algorithm is known


%% Published in 1883.  Author’s name sometimes spelled Kerckhoff


%% %% Kerchoff’s Principle (1883): System should be secure even if
%% %% algorithms are known, as long as key is secret


%% \end{frame}

%% %\section{Actual Encryption Schemes}








%% \section{Elliptic Curves}

%% \begin{frame}
%%   \frametitle{Introduction}
%% \vspace{-.5cm}
%% $$y^2= x^3+ax+b$$ 
%% \begin{center}
%% \begin{tikzpicture}[thick,>=latex, scale=.8]
%%     % Curve over R

%%     % Requires GNUplot installation (part of TeXLive)
%%     \begin{scope}[scale=.75]
%%       \draw[<->,gray] (-3,0) -- (3,0) node[right] {$x \in \mathbb{R}$};
%%       \draw[<->,gray] (0,-3) -- (0,3) node[above] {$y \in \mathbb{R}$};
%%       \draw[thick, name path=curve, every plot/.style={smooth}] plot[id=curve-21, raw gnuplot] function {
%%         f(x,y) = y**2 - x**3 + 2*x - 1;
%%         set xrange [-3:3];
%%         set yrange [-3:3];
%%         set view 0,0;
%%         set isosample 50,50;
%%         set cont base;
%%         set cntrparam levels incre 0,0.1,0;
%%         unset surface;
%%         splot f(x,y);
%%       };
%%     \end{scope}

%%     \node at (0,-3) {$y^2 = x^3 - 2 x + 1$ over $\mathbb{R}$};
    
%%     % Curve over Z_p

%%     % Generate list of points with Sage:
%%     % E = EllipticCurve(GF(89), [-2,1])
%%     % E.order()
%%     % print [(P[0],P[1]) for P in E]
%%     \begin{scope}[xshift=5cm, scale=.045]
%%       \draw[|<->|,gray] (0,-44) -- (0,44) node[above] {$y \in \mathbb{Z}_{89}$};
%%       \draw[->|,gray] (0,0) -- (89,0) node[right] {$x \in \mathbb{Z}_{89}$};
%%       \foreach \point in {
%%         (0, 1), (0, 1), (0, -1), (1, 0), (2, 19), (2, -19), (3, 17), (3, -17), (4, 18), (4, -18), (9, 0),
%%         (10, 25), (10, -25), (11, 8), (11, -8), (13, 6), (13, -6), (14, 15), (14, -15), (15, 26), (15, -26),
%%         (20, 29), (20, -29), (21, 26), (21, -26), (23, 14), (23, -14), (24, 31), (24, -31), (25, 1), (25, -1), (26, 9), (26, -9), (27, 36), (27, -36),
%%         (31, 2), (31, -2), (32, 24), (32, -24), (33, 19), (33, -19), (39, 18), (39, -18),
%%         (43, 37), (43, -37), (45, 16), (45, -16), (46, 18), (46, -18), (47, 32), (47, -32), (49, 28), (49, -28),
%%         (50, 37), (50, -37), (53, 26), (53, -26), (54, 19), (54, -19), (57, 7), (57, -7), (58, 40), (58, -40),
%%         (61, 34), (61, -34), (63, 30), (63, -30), (64, 1), (64, -1), (65, 38), (65, -38), (66, 42), (66, -42),
%%         (71, 41), (71, -41), (72, 27), (72, -27), (75, 20), (75, -20), (76, 12), (76, -12), (79, 0),
%%         (80, 25), (80, -25), (81, 22), (81, -22), (83, 8), (83, -8), (84, 8), (84, -8), (85, 37), (85, -37), (86, 43), (86, -43), (88, 25), (88, -25)
%%       } {\node at \point {$\bullet$};}
%%     \end{scope}

%%     \node[right] at (5,-3) {$y^2 = x^3 - 2 x + 1$ over $\mathbb{Z}_{89}$}; % order: 96

%%   \end{tikzpicture}  
%% %\includegraphics[scale=.7]{ECexamples01}
%% \end{center}


%% $E(K)= \{(x,y)$ such that  $ y^2= x^3+ax+b \}$ plus an extra point
%%   ``at infinite''

%% Weierstrass form if $\Delta = -16 (4a^3+27b^2) \neq 0$ (if K is not of
%% characteristic $2$ or $3$).
%% \end{frame}


%% \begin{frame}
%%   \frametitle{Laws}


%% \begin{block}{Theorem}
%% \begin{itemize}
%% \item Addition law on $E(K)$ 
%% \begin{itemize}
%% \item Associativity: $(P_1+P_2)+P_3= P_1+ (P_2+P_3)$
%% \item Commutativity: $P_1+P_2= P_2+P_1$
%% \item Neutral element  is $\infty$:  $P+ \infty= P$ 
%% \item Inverse: Given $P$ on $E$, there exists $P'$ on $E$ with $P+P'=
%%   \infty$ (usually denoted $-P$)
%% \end{itemize}

%% \item Three aligned points sum to neutral element often denoted zero 
%% \end{itemize}
%% \end{block}

%% \end{frame}




%% \begin{frame}
%%   \frametitle{Laws}


%%   \begin{tikzpicture}[scale=.5]

   

%%     \begin{scope}[xshift=7.5cm]
%%       \plotcurve{-2}{2}
%%       \draw[dashed, semithick, name path=vertical] (-1.25,2.5) -- ++(0,-5);
%%       \draw[name intersections={of=curve and vertical}] (intersection-1) node {$\bullet$} node[above left] {$P$}
%%                                                         (intersection-2) node {$\bullet$} node[below left] {$-P$};
%%       \node[below] at (0,-4) {Inverse element $-P$};
%%     \end{scope}


%%     \begin{scope}[xshift=15cm]
%%       \plotcurve{-2}{2}
%%       \draw[thick, name path=chord] (-2.5,.5) -- (2.5,2.0);
%%       \draw[name intersections={of=curve and chord}] (intersection-1) node {$\bullet$} node[above left] {$P$}
%%                                                      (intersection-2) node {$\bullet$} node[above right=-1pt] {$Q$}
%%                                                      (intersection-3) node {$\bullet$} coordinate[name=mPQ];
%%       \draw[dashed, semithick, name path=vertical] (mPQ) ++(0,1) -- +(0,-5.5);
%%       \draw[name intersections={of=curve and vertical}] (intersection-2) node {$\bullet$} node[below left] {$P+Q$};
%%       \node[below, align=center] at (0,-4) {Addition $P+Q$ \\ ``Chord rule''};
%%     \end{scope}


%%     \begin{scope}[xshift=22.5cm]
%%       \plotcurve[thick, tangent=0.265, every plot/.style={sharp plot}]{-2}{2}
%%       \draw[thick, use tangent, name path=chord] (-.6,0) -- (1.5,0);
%%       \draw[name intersections={of=curve and chord}] (intersection-1) node {$\bullet$} node[above] {$P$}
%%                                                      (intersection-2) node {$\bullet$} coordinate[name=mPQ];
%%       \draw[dashed, semithick, name path=vertical] (mPQ) ++(0,1) -- +(0,-5.0);
%%       \draw[name intersections={of=curve and vertical}] (intersection-2) node {$\bullet$} node[below left] {$2P$};
%%       \node[below, align=center] at (0,-4) {Doubling $P+P$ \\ ``Tangent rule''};
%%     \end{scope}

%%  %% \begin{scope}[xshift=0cm]
%%  %%      \plotcurve{-2}{2}
%%  %%      \draw[->, >=latex, thick] (-2.5,-1) -- ++(0,3.5) node[right] {$\mathcal{O}$};
%%  %%      \node[below] at (0,-4) {Neutral element $\mathcal{O}$};
%%  %%    \end{scope}

    
%%   \end{tikzpicture}

%% %\begin{center}
%% %\includegraphics[width=11cm]{680px-ECClinessvg}
%% %\end{center}

%% %% \end{frame}



%% %% \begin{frame}
%% %%   \frametitle{Addition}

%% %% \begin{center}
%% %% \includegraphics[width=7cm]{chp_elliptic}
%% %% \end{center}

%% $$P+R+Q=0 \Rightarrow R= -(P+Q)$$ 
%% $$ R+ S + 0 = 0 \Rightarrow R =-S $$
%% \end{frame}


%% \begin{frame}
%%   \frametitle{``Elliptic Discrete Logarithm''}

%% \begin{block}{Hard Problem}
%% Finding $k$, given $P$ and $Q = kP$.  is computationally intractable
%% for large values of $k$.
%% \end{block}

%% \end{frame}

%% \begin{frame}
%%   \frametitle{Cryptosystem: ECDH}
%% Exercice:  Give an Elliptic curve of ElGamal.
%% \end{frame}
  

%% \begin{frame}
%%   \frametitle{Cryptosystem: ECDH}

%% Alice's key is $(d_A,Q_A)$ where $Q_A= d_AG$.

%% \begin{block}{DH like Protocol}
%% \begin{enumerate}
%% \item Alice sends  $Q_A, G$ to  Bob.
%% \item Bob computes $k = d_BQ_A$.
%% \item Bob sends to Alice $Q_B$
%% \item Alice computes $k = d_AQ_B$.
%% \end{enumerate}
%%  The shared key is $x_k$ (the $x$ coordinate of the point).
%% \end{block}

%% The number calculated by both parties is equal, because $k= d_AQ_B =
%% d_Ad_BG = d_Bd_AG = d_BQ_A=k$.



%% \end{frame}




%% \begin{frame}
%%   \frametitle{ECDSA (Digital Signature Algorithm) I}

%% Alice private key $d_A$ and a public key $Q_A$ (where $Q_A = d_AG$).
%% \begin{block}{Signature generation algorithm}
%% \begin{enumerate}
%% \item Calculate $e = HASH(m)$, where HASH is a cryptographic hash function, such as SHA-1.
%% \item Select a random integer $k$ from $[1,n - 1]$.
%% \item Calculate $r = x_1(\mbox{ mod } n)$, where $(x_1,y_1) = kG$.\\ If $r = 0$, go back to step 2.
%% \item Calculate $s = k^{-1}(e + rd_A)(\mbox{ mod } n)$.\\ If $ s = 0$, go back to step 2.
%% \item The signature is the pair $(r,s)$.
%% \end{enumerate}
%% \end{block}

%% \end{frame}

%% \begin{frame}
%%   \frametitle{ECDSA (Digital Signature Algorithm) II}

%% \begin{block}{Signature verification algorithm}
%% \begin{enumerate}
%% \item Verify that $r$ and $s$ are integers in $[1,n - 1]$. \\If not, the signature is invalid.
%%  \item Calculate $e = HASH(m)$, where HASH is the same function used in the signature generation.
%%  \item Calculate $w = s^{-1}(\mbox{ mod } n)$.
%%  \item Calculate $u_1 = ew(\mbox{ mod } n)$ and $u_2 = rw(\mbox{ mod } n)$.
%%  \item Calculate $(x_1,y_1) = u_1G + u_2Q_A$.
%%  \item  The signature is valid if $r = x_1(\mbox{ mod } n)$, invalid otherwise.
%% \end{enumerate}
%% \end{block}
%% \end{frame}

%% \begin{frame}
%%   \frametitle{ECDSA (Digital Signature Algorithm)}

%% $$s = k^{-1}(e + rd_A)(\mbox{ mod } n)$$ 

%% Hence $k = s^{-1}(e + rd_A)(\mbox{ mod } n) = w(e+rd_A)= we + wrd_A= u_1 +
%% u_2d_A$

%% since $w= s^{-1}$, $u_1= we$ and $u_2= wr$
 

%% $$(x_1,y_1) = u_1G + u_2Q_A$$
%% Hence  $(x_1,y_1) = u_1G + u_2d_AG = k G$

%% because $Q_A = d_AG$ and $k=u_1 + u_2d_A$

%% We conclude that $r = x_1(\mbox{ mod } n)$ by construction.

%% \end{frame}



\begin{frame}{Symmetric Encryption}
   \begin{center}
\begin{tikzpicture}
\path (-1,2) node (A){\hbox to 2pt{\hss encryption \hss}};


%\path (-1,0) node (A){\hbox to 2pt{\hss clef secr\'ete \hss}};
%\path (3.5,0) node (A){\hbox to 2pt{\hss clef secr\'ete \hss}};


\path (3.5,2) node (A){\hbox to 2pt{\hss decryption \hss}};


\pgftext[at=\pgfpoint{4.5cm}{1cm},left,base]{\pgfuseimage{lettre}}

\pgftext[at=\pgfpoint{-4cm}{1cm},left,base]{\pgfuseimage{lettre}}


\pgftext[at=\pgfpoint{0cm}{1cm},left,base]{\pgfuseimage{chiffre}}


\pgftext[at=\pgfpoint{-1.75cm}{0.5cm},left,base]{\pgfuseimage{ksym}}
\pgftext[at=\pgfpoint{3cm}{0.5cm},left,base]{\pgfuseimage{ksym}}


 \draw[-latex',line width=2pt] (-2,1.5) -- (0,1.5);

  \draw[-latex',line width=2pt] (2.5,1.5) -- (4.5,1.5);
 

\end{tikzpicture}
\end{center}

\begin{block}{Examples}
\begin{itemize}
\item Caesar, Vigen\`ere
\item One Time Pad (OTP) $c=m\oplus k$
\item Data Encryption Standard (DES) 1976
\item Advanced Encryption Strandard (AES) 2001 
\end{itemize}
\end{block}
\end{frame}



\begin{frame}
  \frametitle{Phone Communications}

\begin{center}
\begin{tikzpicture}
    \node (S) at (0,0) {\includegraphics[width=1cm]{Server0}};
    \node (k1) at (-2,0) {\includegraphics[width=.75cm]{Key2G}};
    \node (k2) at (2,0) {\includegraphics[width=.5cm]{key3}};

    \node (k2bis) at (5,3.5) {\includegraphics[width=.5cm]{key3}};
    \node (k1bis) at (-5,3.5) {\includegraphics[width=.75cm]{Key2G}};

    \node (b1) at (2,3) {\includegraphics[width=1.5cm]{building-icone}};
    \node (b2) at (-2,3) {\includegraphics[width=1.5cm]{building-icone}};
    \node (a1) at (2,4) {\includegraphics[width=1cm]{NVTech_busi0715}};
    \node (a2) at (-2,4) {\includegraphics[width=1cm]{NVTech_busi0715}};

    \node (alice) at (-4,0) {\includegraphics[width=2cm]{ALICE01}};
     \node (alice) at (4,0) {\includegraphics[width=2cm]{whiterabbit01.jpg}};

   \node (t1) at (-4,2) {\includegraphics[width=1.5cm]{samsung}};
    \node (t2) at (4,2) {\includegraphics[width=1cm]{mpx220_2}};

\draw [-latex] (S) -- (k2);
\draw [-latex] (S) -- (k1);

\draw [red] (-2,1.25) -- (2,1.25);

\draw [red] (-2,1.25) -- (-2,3.25);
\draw [red] (2,1.25) -- (2,3.25);

   \node (c1) at (-3.5,3.5) {\includegraphics[width=1.5cm]{t_mobile_sim_card_chip}};

   \node (c2) at (4,3.5) {\includegraphics[width=1.5cm]{nomi_sim_card_chip}};
\end{tikzpicture}

\end{center}

\end{frame}



\begin{frame}
  \frametitle{Public Key Encryption}

   \begin{center}
\begin{tikzpicture}
\path (-1,2) node (A){\hbox to 2pt{\hss encryption \hss}};


%\path (-1,0) node (A){\hbox to 2pt{\hss clef publique \hss}};
%\path (3.5,0) node (A){\hbox to 2pt{\hss clef secr\'ete  \hss}};


\path (3.5,2) node (A){\hbox to 2pt{\hss decryption \hss}};


\pgftext[at=\pgfpoint{4.5cm}{1cm},left,base]{\pgfuseimage{lettre}}

\pgftext[at=\pgfpoint{-4cm}{1cm},left,base]{\pgfuseimage{lettre}}


\pgftext[at=\pgfpoint{0cm}{1cm},left,base]{\pgfuseimage{chiffre}}


\pgftext[at=\pgfpoint{-1.75cm}{0.5cm},left,base]{\pgfuseimage{kpub}}
\pgftext[at=\pgfpoint{2.5cm}{0.5cm},left,base]{\pgfuseimage{kpriv}}


 \draw[-latex',line width=2pt] (-2,1.5) -- (0,1.5);

  \draw[-latex',line width=2pt] (2.5,1.5) -- (4.5,1.5);
 

\end{tikzpicture}
\end{center}


\begin{block}{Examples}
\begin{itemize}
\item RSA (Rivest Shamir Adelmman 1977): $c= m^e \mod n$
\item ElGamal (1981) : $c \equiv (g^r,h^r \cdot m) $
\end{itemize}
\end{block}

\end{frame}

\begin{frame}
  \frametitle{Comparaison}

\begin{itemize}
\item Size of the key
\item Complexity of computation (time, hardware, cost ...)
\item Number of different keys ? 
\item Key distribution
\item Signature only possible with asymmetric scheme
\end{itemize}

\end{frame}



\begin{frame}
  \frametitle{Computational cost of encryption}

\begin{block}{2 hours of video (assumes 3Ghz CPU)}

$$
\begin{tabular}{|c|c|c|c|c|}
\cline{2-5}
%\hline
\multicolumn{1}{c|}{} 
& \multicolumn{2}{c|}{DVD 4,7 G.B} & \multicolumn{2}{c|}{Blu-Ray 25 GB} \\\hline
 Schemes  & encrypt & decrypt & encrypt & decrypt \\ \hline
RSA 2048(1)& 22 min & 24 h & 115 min & 130 h\\
RSA 1024(1)& 21 min & 10 h & 111 min & 53 h\\\hline
AES CTR(2) & 20 sec & 20 sec & 105 sec &105 sec\\\hline
\end{tabular}
$$
\end{block}

\end{frame}








\begin{frame}
  \frametitle{ElGamal Encryption Scheme}
  \begin{list}{}{}
  \item[\textcolor{blue}{Key generation:}] Alice chooses a prime number $p$ and a
group generator $g$ of $(\Z/p\Z)^*$ and $a\in (\Z/(p-1)\Z)^*$.
\item[\textcolor{blue}{Public key:}] $(p,g,h)$, where $h=g^a\mod p$.
\item[\textcolor{blue}{Private key:}] $a$
\item[\textcolor{blue}{Encryption:}] Bob chooses $r\in_R (\Z/(p-1)\Z)^*$ and computes
$(u,v)=(g^r,Mh^r)$
\item[\textcolor{blue}{Decryption:}] Given $(u,v)$, Alice computes
  $M\equiv_p \frac{v}{u^a}$
\item[\textcolor{blue}{Justification:}] $ \frac{v}{u^a} =\frac{Mh^r}{g^{ra}}\equiv_p M$
\item[\textcolor{blue}{Remarque:}] re-usage of the same random $r$ leads to a
  security flaw:
\[\frac{M_1h^r}{M_2h^r} \equiv_p \frac{M_1}{M_2}\]
\item[\textcolor{blue}{Practical Inconvenience:}] Cipher is twice as long as
  plain text.
  \end{list}
\end{frame}


\begin{frame}{Hash Function  (SHA-256, SHA-3)}
\vspace{-.25cm}
\begin{center}
  \includegraphics[width=.5cm]{homme}
    \includegraphics[width=1cm]{fleched} 
%\includegraphics[width=1cm]{adn} 
  \includegraphics[width=1cm]{empreinte-digitale}
\end{center}

\pause

\begin{block}{Security properties}
\begin{itemize}
\item Pr\'e-image Resistance


\vspace{-.5cm}


\hfill \includegraphics[width=1cm]{empreinte-digitale}     \includegraphics[width=1cm]{fleched}  \includegraphics[width=.5cm]{homme} \includegraphics[width=.75cm]{Point-d-interrogation.png}

\pause
\item Second Pr\'e-image Resistance

\vspace{-.5cm}

\hfill \includegraphics[width=.5cm]{homme2} \includegraphics[width=1cm]{empreinte-digitale}     \includegraphics[width=1cm]{fleched}  \includegraphics[width=.5cm]{homme3} \includegraphics[width=1cm]{empreinte-digitale} \includegraphics[width=.75cm]{Point-d-interrogation.png}

\pause
\item Collision Resistance

\vspace{-.5cm}


\hfill \includegraphics[width=1cm]{fleched}  \includegraphics[width=.5cm]{homme3} \includegraphics[width=.5cm]{homme2} \includegraphics[width=1cm]{empreinte-digitale} \includegraphics[width=.75cm]{Point-d-interrogation.png}


\end{itemize}
\end{block}
%% \end{frame}


%% \begin{frame}
%%   \frametitle{Hash Functions}  

%% \[ h:\{0,1\}^* \rightarrow \{0, 1\}^n \]

%% \begin{block}{Properties}

%% \begin{itemize}
%% \item Pre-image resistance: 
%%  $y \rightarrow ? ~ x$ such that $h(x) = y$

%% \item 2nd Pre-image resistance:
%% $x \rightarrow ?~ x'$ such that $ h(x') = h(x) $
%% \item  Collision resistance 
%% $ \rightarrow ?~ x$ and $x'$ such that $ h(x) = h(x')$
%% \end{itemize}

%% \end{block}

\vspace{-.25cm}
\begin{itemize}
\item Unkeyed Hash function: Integrity
\item Keyed Hash function (Message Authentication Code): Authentification
\end{itemize}

\end{frame}



\begin{frame}
  \frametitle{Software Installation}


\begin{center}
\begin{tikzpicture}
    \node (S1) at (4,3) {\includegraphics[width=2cm]{Server0}};
    \node (S2) at (4,-1.5) {\includegraphics[width=2cm]{1604}};

  \node (alice) at (-5,2) {\includegraphics[width=2cm]{ALICE01}};

  \node (laptop) at (-3,3) {\includegraphics[width=2cm]{laptop_02}};

 \node (file) at (0,2) {\includegraphics[width=2cm]{icon_securetransport}};

\draw [red, line width = 2pt, -latex] (file) -- (laptop);
\draw [red, line width = 2pt, -latex] (S1) -- (file);
\draw [red, line width = 2pt, -latex] (laptop) -- (S1);

\draw [-latex] (S2) -- (laptop);

 \node (hash) at (0,-1) {\Huge{H(}\includegraphics[width=1cm]{icon_securetransport})};

\end{tikzpicture}

\end{center}


\begin{center}
%%  \begin{pspicture}(0,0)(10,2.5)       
%% %   \psgrid[subgriddiv=0,griddots=10](10,3.25)      
%% 	  {     	
%% 	    \rput(10,2.5){\epsfig{file=Server0,width=15mm}}
%%             \rput(10,0.5){\epsfig{file=1604,width=15mm}}
%% 	    \rput(1,2.5){\epsfig{file=laptop_02,width=20mm}}
%% 	    \rput(5,2){\epsfig{file=icon_securetransport,width=15mm}}
%%             \rput(5,0.5){\epsfig{file=codebarre,width=20mm}}

%% %	    \rput(0,2){\epsfig{file=db_computeruserca412,width=10mm}}
%% %	    \rput(7,0){\epsfig{file=server,width=15mm}}
	

%% 	    \pscurve[linewidth=1.5pt,linecolor=black,border=0.5pt,arrowsize=7pt]{<-}(1,1.5)(2,0.5)(3.75,0.5)

%% 	    \pscurve[linewidth=1.5pt,linecolor=black,border=0.5pt,arrowsize=7pt]{->}(9,0.5)(7,0.5)(6,0.5)

%% 	    \pscurve[linewidth=1.5pt,linecolor=red,border=0.5pt]{->}(2,3)(3,3)(9,3)

%% 	    \pscurve[linewidth=1.5pt,linecolor=red,border=0.5pt]{<-}(2,2)(3,2)(4,2)
%% 	    \pscurve[linewidth=1.5pt,linecolor=red,border=0.5pt]{<-}(6,2)(7,2)(9,2)

%% 	  }
%%  \end{pspicture}
\end{center}

Integrity of the downloaded file.

  \begin{enumerate} \itemsep=5pt
  \item Download on server 1 the software.
  \item Download on server 2 the hash of the software.
  \item Check the integrity of the software.
  \end{enumerate}

\end{frame}


\begin{frame}{MD5, MD4 and RIPEMD  Broken }

 \hfill \includegraphics[width = 4cm]{james} \hfill \includegraphics[width = 4cm]{barry} \hfill ~

MD5(james.jpg)= e06723d4961a0a3f950e7786f3766338
\pause
MD5(barry.jpg) = e06723d4961a0a3f950e7786f3766338

\ \\
 How to Break MD5 and Other Hash Functions, by Xiaoyun Wang, et al.

\ \\

MD5 : Average run time on P4 1.6ghz PC: 45 minutes

MD4 and RIPEMD : Average runtime on P4 1.6ghz: 5 seconds

\end{frame}

\begin{frame}{SHA-1 broken in 2017 \hfill  \url{shattered.io}}
M. Stevens, P. Karpman, E. Bursztein, A. Albertini, Y. Markov
\begin{center}
\includegraphics[width = 10cm]{Collision-SHA.png}
\end{center}

\end{frame}

\begin{frame}{SHA-1 broken in 2017 \hfill  \url{shattered.io}}
\begin{center}
\includegraphics[width = 9cm]{SHA-attack.png}
\end{center}
\end{frame}


\begin{frame}{SHA-1 broken in 2017 \hfill  \url{shattered.io}}
\begin{center}
\includegraphics[width = 10cm]{SHA-impact.png}
\end{center}

\end{frame}

\begin{frame}{SHA-1 broken in 2017 \hfill  \url{shattered.io}}
\begin{center}
\includegraphics[width = 10cm]{SHA-Defense.png}
\end{center}

\end{frame}


\pgfdeclareimage[interpolate=true,height=2cm]{lettresceau}{IMAGES/courrier-scelle_318-47739.jpg}

\begin{frame}{Signature}

\begin{center}
\includegraphics[width = 2cm]{courrier-scelle_318-47739.jpg} \qquad      \includegraphics[width = 2cm]{cachet-de-cire-law.jpg} 
     \end{center}

\bigskip

\pause


   \begin{center}
\begin{tikzpicture}
\path (-1,2) node (A){\hbox to 2pt{\hss signature \hss}};


\path (-1,0) node (A){\hbox to 2pt{\hss secret key \hss}};
\path (3.5,0) node (A){\hbox to 2pt{\hss public key \hss}};


\path (3.5,2) node (A){\hbox to 2pt{\hss verification \hss}};

%\pgftext[at=\pgfpoint{4.5cm}{1cm},left,base]{\pgfuseimage{sceau}}
%\pgftext[at=\pgfpoint{6.5cm}{1cm},left,base]{\pgfuseimage{sceau2}}

\pgftext[at=\pgfpoint{4.5cm}{1cm},left,base]{\pgfuseimage{lettre}}

\pgftext[at=\pgfpoint{-4cm}{1cm},left,base]{\pgfuseimage{lettre}}


\pgftext[at=\pgfpoint{.25cm}{0.5cm},left,base]{\pgfuseimage{lettresceau}}


\pgftext[at=\pgfpoint{-1.75cm}{0.5cm},left,base]{\pgfuseimage{kpriv}}
\pgftext[at=\pgfpoint{3cm}{0.5cm},left,base]{\pgfuseimage{kpub}}


 \draw[-latex',line width=2pt] (-2,1.5) -- (0,1.5);

  \draw[-latex',line width=2pt] (2.5,1.5) -- (4.5,1.5);
 

\end{tikzpicture}
\end{center}

RSA: $m^d \mod n$
\end{frame}


\begin{frame}{Application : avoid to  ``\emph{fraude au pr\'esident}''}

\begin{itemize}
%\item FOVI : faux ordres de virement
\item In 2010 $> 485$ billions of euros
\item In 5 years 2.300 court cases
\end{itemize}

\pause

\begin{center}
\includegraphics[width = 10cm]{FOVI.jpg}


\pause
\vspace{-.75cm}
Solution : \includegraphics[width = 1.5cm]{courrier-scelle_318-47739.jpg} 

     \end{center}
\end{frame}


  \begin{frame}
\frametitle{Broadcast encryption (Fiat-Noar 1994)}


\includegraphics[width=11cm]{Broadcast.png}

The sender can select the target group of receivers to control who
access to the data like in PAYTV  %[Fiat-Naor - Crypto ‘94]

\end{frame}

  \begin{frame}
\frametitle{Functional encryption [Boneh-Sahai-Waters 2011]}

\includegraphics[width=11cm]{Functional.png}

The user generates sub-keys $K_y$ according to the input $y$ to control the amount of shared data.

From $C = Encrypt(x)$, then $Decrypt(K_y,C)$, outputs $f(x,y)$

\end{frame}

\section{Partial and Full Homomorphic Encryption}

 \begin{frame}
\frametitle{Fully Homomorphic Encryption [Gentry 2009]}

\includegraphics[width=10cm]{FHEsimple.png}
\end{frame}

\begin{frame}
\frametitle{Fully Homomorphic Encryption [Gentry 2009]}

FHE:  encrypt data, allow manipulation over data.

Symmetric Encryption (secret key) is enough

\begin{center}
\includegraphics[width=2.5cm]{glove.png}
\end{center}

$$f(\{x_1\}_K,\{x_2\}_K,\ldots,\{x_n\}_K) = \{f(x_1,x_2,\ldots,x_n)\}_K$$

\begin{itemize}
\item Allows private storage 
\item Allows private computations 
\item Private queries in an encrypted database 
\item Private search: without leaking   the content,  queries and  answers.
\end{itemize}
\end{frame}



\begin{frame}{Rivest Adleman Dertouzos 1978}

  \emph{``Going beyond the storage/retrieval of encrypted data by permitting
  encrypted data to be operated on for interesting operations, in a
  public fashion?''}

\end{frame}


\begin{frame}{Partial Homomorphic Encryption}
\begin{block}{Definition (additively homomorphic)}
\[ E(m_1) \otimes E(m_2) \equiv E(m_1 \oplus m_2). \]
\end{block}
\begin{block}{Applications}
\begin{itemize} \itemsep0em
\item  Electronic voting
\item   Secure Fonction Evaluation
\item   Private Multi-Party Trust Computation
\item   Private Information Retrieval
\item   Private Searching
\item  Outsourcing of Computations (e.g., Secure Cloud Computing)
\item   Private Smart Metering and Smart Billing
\item 
Privacy-Preserving Face Recognition
\item \ldots
\end{itemize}
\end{block}
\end{frame}

\begin{frame}{Brief history of partially homomorphic cryptosystems}
$$Enc(a,k)  *  Enc(b,k) = Enc(a*b,k) $$

\begin{tabular}{|c|c|c|c|}
\hline
\textbf{Year} & \textbf{Name} & \textbf{Security hypothesis} & \textbf{Expansion} \\
\hline
1977 & RSA & factorization & \\ 
\hline
1982 & Goldwasser - Micali & quadratic residuosity & $\log_2(n)$ \\
\hline
1994 & Benaloh & higher residuosity & $ > 2 $ \\
\hline
1998 & Naccache - Stern & higher residuosity & $> 2$ \\
\hline
1998 & Okamoto - Uchiyama & $p$-subgroup & $3$ \\
\hline
1999 & Paillier & composite residuosity & $2$ \\
\hline
2001 & Damgaard - Jurik & composite residuosity & $\frac{d+1}{d}$\\
\hline
2005  &  Boneh - Goh - Nissim  & ECC Log&\\
\hline
2010 & Aguilar-Gaborit-Herranz& SIVP  integer lattices&\\
\hline
\end{tabular}

\ \\

Expansion factor is the ration ciphertext over plaintext.
\end{frame}

\begin{frame}
  \frametitle{Scheme Unpadded RSA}

If the RSA public key is modulus $m$ and exponent $e$, then the
encryption of a message $x$ is given by

$$\mathcal{E}(x) = x^e \mod  m $$

\begin{eqnarray*}
  \mathcal{E}(x_1) \cdot \mathcal{E}(x_2) &=& x_1^e x_2^e \;\bmod\; m \\
  &=& (x_1x_2)^e \;\bmod\; m\\
  &=& \mathcal{E}(x_1 \cdot x_2)
  \end{eqnarray*}


  

\end{frame}

\begin{frame}
  \frametitle{Scheme ElGamal}

In the ElGamal cryptosystem, in a cyclic group $G$ of order $q$ with
generator $g$, if the public key is $( G , q , g , h )$, where $
h=g^{x}$ and $x$ is the secret key, then the encryption of a message
$m$ is $\mathcal{E}(m) = (g^r,m\cdot h^r)$, for some random  $r \in \{0, \ldots,
q-1\}$.



\begin{eqnarray*}
{\mathcal {E}}(m_{1})\cdot {\mathcal{E}}(m_{2})&=&(g^{{r_{1}}},m_{1}\cdot
h^{{r_{1}}})(g^{{r_{2}}},m_{2}\cdot h^{{r_{2}}})\\
&=& (g^{{r_{1}+r_{2}}},(m_{1}\cdot m_{2})h^{{r_{1}+r_{2}}})\\
&=&{\mathcal {E}}(m_{1}\cdot m_{2})
\end{eqnarray*}

\end{frame}



\begin{frame}
\frametitle{Fully Homomorphic Encryption}

$$Enc(a,k)  *  Enc(b,k) = Enc(a*b,k) $$
$$Enc(a,k)  +  Enc(b,k) = Enc(a+b,k) $$
$$f( Enc(a,k)  ,  Enc(b,k)) = Enc(f(a,b),k) $$
\begin{block}{Fully Homomorphic encryption}
\begin{itemize}
\item Craig Gentry (STOC 2009) using lattices
\item Marten van Dijk; Craig Gentry, Shai Halevi, and Vinod
  Vaikuntanathan  using integer
\item Craig Gentry; Shai Halevi. "A Working Implementation of Fully
  Homomorphic Encryption"
\item $\cdots$ \end{itemize}
\end{block}
\end{frame}


\begin{frame}
  \frametitle{Simple SHE: SGHV Scheme [vDGHV10]}

Public error-free element  : $x_0 = q_0 \cdot p$

Secret key $sk =p$

\begin{block}{Encryption of $m \in \{0,1\}$}
$$c = q \cdot p + 2 \cdot r + m $$

where $q$ is a large random and $r$ a small random.
\end{block}

\pause

\begin{block}{Decryption of $c$}
$$m = (c \mod p ) \mod 2$$
\end{block}
\end{frame}


%% \begin{frame}
%%   \frametitle{Limitations}

%%   \begin{itemize}
%%   \item Efficiency: HEtest: A Homomorphic Encryption Testing Framework (2015)
%% \end{itemize}

%% \begin{center}
%% \includegraphics[width=11cm]{Homo.png}
%% \end{center}

%% \end{frame}




\newcommand\ras[1]{\randd{#1}{\mathcal{U}}}
\newcommand\randd[2]{{#1}\stackrel{r}{\leftarrow}{#2}}





\section{Security Properties}



%% \begin{frame}
%% \frametitle{Typical security-critical problems}
%% \begin{itemize} \itemsep=0pt
%% \item  \textcolor{red}{Secure communication}, e.g., via telephone, email, fax.

%%   \textcolor{red}{Objective:} confidentiality and integrity of
%%   transmitted information.

%% \item \textcolor{blue}{Internet banking}.
%%   \textcolor{red}{Objectives:} confidentiality of transactions and
%%   account information, prevention of false transactions, impossibility
%%   of repudiating (denying) a transaction by a user, ...

%% \item \textcolor{blue}{Digital payment systems}.  

%% \item \textcolor{blue}{ E-voting systems}, ...

%% %\item \textcolor{blue}{ Digital rights management}.
%% \end{itemize}

%% N.B.: specifying objectives (security properties) is not always easy. \\
%% Neither is building systems that satisfy these objectives!
%% \end{frame}



\begin{frame}
\frametitle{Traditional security properties}
\begin{itemize} %\itemsep=0pt
%% \item Policies are often formulated to achieve certain standard
%%   \textcolor{blue}{ security properties} (also called
%%   \textcolor{blue}{ security goals})

\item  Common security properties are:
\begin{itemize} \itemsep=5pt
\item [-] \textcolor{red}{Confidentiality or Secrecy}: No improper
  disclosure of information
\item [-] \textcolor{red}{Authentification}: To be sure to talk with
  the right person.
  disclosure of information
\item [-] \textcolor{red}{Integrity}: No improper modification of
  information
\item [-] \textcolor{red}{Availability}: No improper impairment of
  functionality/service
\end{itemize}

%% \item Note that: \textcolor{red}{(Im)proper} must be specified
%%   individually, for each system.
\end{itemize}
\end{frame}




\begin{frame}
\frametitle{Authentication}
\begin{center}
\includegraphics[scale=.35]{idog}
\end{center}
\end{frame}



\begin{frame}
\frametitle{Mechanisms for  Authentication}

\begin{center}
\includegraphics[width=8cm]{Homer-Authentication.jpg}
\end{center}

%% \begin{picture}(0,0)(0,0)
%% %\put(570,50){\includegraphics[scale=1.4]{fig5_4}}
%% \put(180,-45){\includegraphics[scale=1.7]{eye-scan}}
%% \end{picture}  \vspace*{-40pt}

%% \begin{enumerate}\itemsep=7pt
%% \item Something that you know

%% E.g. a PIN or a password

%% \item Something that you have

%% E.g. a smart-card

%% \item Something that you are 

%% Biometric characteristics like voice, fingerprints, eyes, ...

%% \item Where you are located

%% E.g. in a secure building
%% \end{enumerate}

 \textcolor{blue}{ Strong authentication} combines multiple factors: 

E.g., Smart-Card + PIN
\end{frame}


\begin{frame}
\frametitle{Other security properties}
\begin{itemize} %\itemsep=0pt
%% \item \textcolor{blue}{ Authenticity} (e.g., ``channel input only accessible
%% to sender'')  is often the same as integrity, with
%% just a difference of emphasis.

\item \textcolor{red}{ Non-repudiation} (also called
  \textcolor{blue}{ accountability}) is where one can establish
  responsibility for actions.

\item \textcolor{red}{ Fairness} is the fact there is no advantage to
  play one role in a protocol comparing with the other ones.
%% \item \textcolor{blue}{ Plausible deniability} is contrary to non-repudiation
%% and can be seen as weak form of secrecy.

\item \textcolor{red}{ Privacy} 
\begin{description} %\itemsep=7pt
\item [\textcolor{blue}{ Anonymity}:] secrecy of principal identities or
communication relationships.
\item [\textcolor{blue}{ Pseudonymity}:]  anonymity plus link-ability.
\item [\textcolor{blue}{ Data protection}:] personal data is only used in certain ways.
\end{description}
\end{itemize}
\end{frame}

%% \begin{frame}
%% \frametitle{Example: banking}

%% \begin{itemize}
%% \item A bank may require
%% \begin{itemize} \itemsep=7pt
%% \item authenticity of clients (at teller, ATMs, or on the Internet),
%% \item non-repudiation of transactions,
%% \item integrity of accounts and other customer data,
%% \item secrecy of customer data, and
%% \item availability of logging.
%% \end{itemize}
%% \item The conjunction of these properties might constitute
%% the bank's (high-level) security policy.     
%% \end{itemize}
%% \end{frame}


\begin{frame}
\frametitle{Example: e-voting}
%\transit{0}{(450,-17)}{\includegraphics[scale=.64]{fig/dad-votes.jpg}} 
%\vspace*{-10pt}
\begin{itemize}  
\item An e-voting system should ensure that
\begin{itemize} %\itemsep=4pt
\item only registered voters vote,
\item each voter can only vote once,
\item integrity of votes,
\item privacy of voting information (only used for tallying), and
\item availability of system during voting period
\end{itemize}
%\item In practice, many policy aspects are difficult to formulate precisely.
\end{itemize}

%% \textcolor{Violet}{Exercise (Due to next course):} Give the security
%% properties that an mobile phone should guarantee.\\

%\textcolor{Violet}{Exercise:} Give the security properties that an
%international airport should guarantee.\\
%More details with Florent Autreau later.

\end{frame}


\section{ZKP}

\begin{frame}
  \frametitle{Idea of Zero Knowledge Proof}

 \begin{columns}[c] % the "c" option specifies center vertical alignment
 \column{2cm}

\begin{center}
\includegraphics[width=2cm]{pascal.jpg}

Prover (P)
\end{center}

\column{6.9cm} 

\begin{center}
(P) convinces (V) that it knows
something without revealing any information
\end{center}

 \column{2cm}
\begin{center}
\includegraphics[width=2cm]{vercingetrorix.jpg}

Verifier (V)
\end{center}

\end{columns}
%vincent-cassel.jpg 

\pause

\begin{block}{Applications:}
  \begin{itemize}
  \item Authentication systems: prove its identity to someone using a
    password without reavealing anything about the secret.
  \item Prove that a praticipant behavior is correct according to the
    protocol (e.g. integrity of ballots in vote).
  \item Group signature, secure multiparty computation, e-cash ...
  \end{itemize}
\end{block}
\end{frame}



% \begin{frame}
% \frametitle{Interactive Zero Knowledge Proofs}

% \begin{block}{} In an interactive zero knowledge proof, a prover \textit{P} interacts with a verifier \textit{V} to demonstrate the validity of an assertion without revealing anything about the assertion to the verifier.
% \end{block}

% {An Example: The Cave Story (1)}

% \begin{itemize}
%   \item a cave shaped a circle
%   \item a magic door at one side
%   \item an entrance at the other side
%   \item Victor will pay Peggy only if she knows the secret
%   \item Peggy won't tell the secret until she would have been paid.
% \end{itemize}

% \end{frame}
% %----------------------------------------------------------------------------


\begin{frame}
\frametitle{Cave example (0)}

\ \\
 \begin{columns}[c] % the "c" option specifies center vertical alignment
 \column{5.25cm}

\includegraphics[height=4cm,width=6cm]{grotte_0.jpg} 
 \column{5cm} Door with a secret code
\end{columns}
\end{frame}


\begin{frame}
\frametitle{Cave example (I)}

V waits outside while P chooses a path \\

\ \\

\includegraphics[height=4cm,width=6cm]{grotte_1}

\end{frame}

%-----------------------------------------------------------------------------
\begin{frame}
\frametitle{Cave example (II)}

V enters and shouts the name of a path\\

\ \\

\includegraphics[height=4cm,width=6cm]{grotte_2}

\end{frame}

%-----------------------------------------------------------------------------
\begin{frame}
\frametitle{Cave example (III)}

P returns along the desired path (using the secret if necessary)\\

\ \\
 \begin{columns}[c] % the "c" option specifies center vertical alignment
\column{6cm}

\includegraphics[height=4cm,width=6cm]{grotte_3}
 \column{5.75cm}
\pause
$A$ =  ``P does not know the secret''
 
is equivalent to say  ``P is lucky''

$$Pr[A] = \frac{1}{2}$$ 

\pause

After $k$ tries, 

$$Pr[A] = (\frac{1}{2})^k$$ 

\pause
$\overline{A}$ = ``P knows the secret'', then
$$Pr[\overline{A}] = 1 - Pr[A] = 1 -  (\frac{1}{2})^k$$

\end{columns}

\end{frame}

%-----------------------------------------------------------------------------

% \section{Funny example: Rubik's Cube}

% \begin{frame}
% \frametitle{Rubik's Cube}

% Assume Alice knows how to solve the Rubik's Cube.\\

% \begin{center}
%   \includegraphics[width=3.2cm]{Rubiks_cube_scrambled}
% \end{center}

% \begin{block}{Question ?}
% She wants to prove to Bob she has the skill to solved a given
% scrambled Rubik's cube without revealing it.  How can she do it?
% \end{block}
% \end{frame}

% \begin{frame}
% \frametitle{Rubik's Cube}

% Alice scrambles the cube and proposed a new cube to Bob

% \begin{center} 
% ~ \hfill 
%   \includegraphics[width=3cm]{Rubiks_cube_scrambled} \hfill
%   \includegraphics[width=3cm]{rubiks-cube} \hfill
%   \includegraphics[width=3.2cm]{cube} \hfill ~

% ~ \hfill $1$ \hfill $2$ \hfill $3$ \hfill ~
% \end{center}

% Bob asks Alice from the current position ($2$) to go back to the initial
% position ($1$) or to solve it ($3$).\\

% \ \\

% Repeating this process $k$ times Bob is convinced that Alice knows
% the secret with a probability $1/2^k$.
% \end{frame}


\begin{frame}
\frametitle{Graph 3-coloring is NP-complete: \textcolor{red}{$\bullet$}
  \textcolor{green}{$\bullet$} \textcolor{blue}{$\bullet$} }

\begin{center}
\only<1-1>{
\begin{tikzpicture}

\node[draw,circle,fill=gray!50] (A) at (0,0) {1} ;
\node[draw,circle,fill=gray!50] (B) at (4,0) {2} ;
\node[draw,circle,fill=gray!50] (C) at (4.5,4) {3} ;
\node[draw,circle,fill=gray!50] (D) at (2,4.5) {4} ;
\node[draw,circle,fill=gray!50] (E) at (-.5,4) {5} ;
\node[draw,circle,fill=gray!50] (F) at (1,2.6) {6} ;
\node[draw,circle,fill=gray!50] (G) at (2,3.5) {7} ;
\node[draw,circle,fill=gray!50] (H) at (3,2.5) {8} ;
\node[draw,circle,fill=gray!50] (I) at (3,1) {9} ;
\node[draw,circle,fill=gray!50] (J) at (1,1) {\scriptsize{10}} ;

\draw[-] (A) -- (E);
\draw[-] (A) -- (J);
\draw[-] (A) -- (B);
\draw[-] (B) -- (I);
\draw[-] (B) -- (C);
\draw[-] (C) -- (H);
\draw[-] (C) -- (D);
\draw[-] (D) -- (G);
\draw[-] (D) -- (E);
\draw[-] (E) -- (F);
\draw[-] (F) -- (H);
\draw[-] (F) -- (I);
\draw[-] (G) -- (J);
\draw[-] (G) -- (I);
\draw[-] (H) -- (J);

\end{tikzpicture}
}
\only<2->{
\begin{tikzpicture}

\node[draw,circle,fill=red!75] (A) at (0,0) {1} ;
\node[draw,circle,fill=green!75] (B) at (4,0) {2} ;
\node[draw,circle,fill=blue!75] (C) at (4.5,4) {3} ;
\node[draw,circle,fill=red!75] (D) at (2,4.5) {4} ;
\node[draw,circle,fill=blue!75] (E) at (-.5,4) {5} ;
\node[draw,circle,fill=green!75] (F) at (1,2.6) {6} ;
\node[draw,circle,fill=blue!75] (G) at (2,3.5) {7} ;
\node[draw,circle,fill=red!75] (H) at (3,2.5) {8} ;
\node[draw,circle,fill=red!75] (I) at (3,1) {9} ;
\node[draw,circle,fill=green!75] (J) at (1,1) {\scriptsize{10}} ;

\draw[-] (A) -- (E);
\draw[-] (A) -- (J);
\draw[-] (A) -- (B);
\draw[-] (B) -- (I);
\draw[-] (B) -- (C);
\draw[-] (C) -- (H);
\draw[-] (C) -- (D);
\draw[-] (D) -- (G);
\draw[-] (D) -- (E);
\draw[-] (E) -- (F);
\draw[-] (F) -- (H);
\draw[-] (F) -- (I);
\draw[-] (G) -- (J);
\draw[-] (G) -- (I);
\draw[-] (H) -- (J);

\end{tikzpicture}
}

Petersen graph
\end{center}
\end{frame}

% \begin{frame}
% \frametitle{Graph 3-coloring}


% \begin{definition}{3-coloring}
%   A 3-coloring of a graph is an assignment of $3$ colors to vertices
%   such that no pair of adjacent vertices are assigned to the same
%   color.
% \end{definition}

% \begin{block}{3-coloring Problem}
% Given a graph $G$, the problem of deciding if the graph $G$ is
% 3-colorable is an NP problem. (cf Garey and Johnson Book)
% \end{block}

% Problem: Alice wants to prove to Bob she knows a $3$-coloring $c$ of a
% given graph $G$.

% \end{frame}

\begin{frame}
  \frametitle{P wants to prove to V his  $3$-coloring of $G=(E,V)$}
%\footnote{O. Goldreich, S. Micali,
%      A. Wigderson: Proofs that Yield Nothing But their Validity and a
%      Methodology of Cryptographic Protocol Design. FOCS 1986 }}

P selects a permutation $\pi$ of the 3 colors.
\begin{center}
 \begin{columns}[c] % the "c" option specifies center vertical alignment
 \column{.5cm}
%)= q w e r t y u i o
 \column{.5cm}
$\pi($ %q w e r t y u i o
 \column{2.7cm}
\begin{tikzpicture}[scale=.5]

\node[draw,circle,fill=red!75] (A) at (0,0) {1} ;
\node[draw,circle,fill=green!75] (B) at (4,0) {2} ;
\node[draw,circle,fill=blue!75] (C) at (4.5,4) {3} ;
\node[draw,circle,fill=red!75] (D) at (2,4.5) {4} ;
\node[draw,circle,fill=blue!75] (E) at (-.5,4) {5} ;
\node[draw,circle,fill=green!75] (F) at (1,2.6) {6} ;
\node[draw,circle,fill=blue!75] (G) at (2,3.5) {7} ;
\node[draw,circle,fill=red!75] (H) at (3,2.5) {8} ;
\node[draw,circle,fill=red!75] (I) at (3,1) {9} ;
\node[draw,circle,fill=green!75] (J) at (1,1) {\scriptsize{10}} ;

\draw[-] (A) -- (E);
\draw[-] (A) -- (J);
\draw[-] (A) -- (B);
\draw[-] (B) -- (I);
\draw[-] (B) -- (C);
\draw[-] (C) -- (H);
\draw[-] (C) -- (D);
\draw[-] (D) -- (G);
\draw[-] (D) -- (E);
\draw[-] (E) -- (F);
\draw[-] (F) -- (H);
\draw[-] (F) -- (I);
\draw[-] (G) -- (J);
\draw[-] (G) -- (I);
\draw[-] (H) -- (J);

\end{tikzpicture}
%q w e r t y u i o
 \column{.5cm}
)=% q w e r t y u i o
 \column{2.7cm}
\begin{tikzpicture}[scale=.5]

\node[draw,circle,fill=blue!75] (A) at (0,0) {1} ;
\node[draw,circle,fill=red!75] (B) at (4,0) {2} ;
\node[draw,circle,fill=green!75] (C) at (4.5,4) {3} ;
\node[draw,circle,fill=blue!75] (D) at (2,4.5) {4} ;
\node[draw,circle,fill=green!75] (E) at (-.5,4) {5} ;
\node[draw,circle,fill=red!75] (F) at (1,2.6) {6} ;
\node[draw,circle,fill=green!75] (G) at (2,3.5) {7} ;
\node[draw,circle,fill=blue!75] (H) at (3,2.5) {8} ;
\node[draw,circle,fill=blue!75] (I) at (3,1) {9} ;
\node[draw,circle,fill=red!75] (J) at (1,1) {\scriptsize{10}} ;

\draw[-] (A) -- (E);
\draw[-] (A) -- (J);
\draw[-] (A) -- (B);
\draw[-] (B) -- (I);
\draw[-] (B) -- (C);
\draw[-] (C) -- (H);
\draw[-] (C) -- (D);
\draw[-] (D) -- (G);
\draw[-] (D) -- (E);
\draw[-] (E) -- (F);
\draw[-] (F) -- (H);
\draw[-] (F) -- (I);
\draw[-] (G) -- (J);
\draw[-] (G) -- (I);
\draw[-] (H) -- (J);

\end{tikzpicture}
%q w e r t y u i o
 \column{1.5cm}
%)= q w e r t y u i o

\end{columns}
\end{center}
\pause

% \begin{enumerate}
% \item Alice chooses a permutation $\pi$ of the $3$ colors ( $\pi o c$
%   is still a $3$-coloring of the graph $G$). And she transmits to Bob
%   $e_u = H (\pi(c(u)) || r_u)$ for $u \in V$ and $r_u$ random value.
% \item Bob asks colors for $u$ and $v$ in $V$.
% \item Alice answers $ r_u, r_v , \pi(c(u)), \pi(c(v))$
%   which allows Bob to confirm messages send by Alice.
% \end{enumerate}

% Given a permutation $\pi$

% $A \rightarrow B : \forall u \in V, e_u = H (\pi(c(u)) || r_u)$ \\

% $B \rightarrow A : u , v $  \\ 

% $A \rightarrow B : r_u, r_v, \pi(c(u)), \pi(c(v))$  \\


 \begin{columns}[c] % the "c" option specifies center vertical alignment
 \column{3.25cm}
\begin{center}
\includegraphics[width=2cm]{pascal.jpg}

\visible<2->{Chooses $\forall u \in V, r_u$}
\end{center}
 \column{6.5cm}
  
\begin{center}
\visible<3->{$\rightarrow  \forall u \in V, e_u = H (\pi(c(u)) || r_u) \rightarrow $}


\visible<5->{$ \longleftarrow  u_i, u_j \longleftarrow $ }


\visible<6->{$\longrightarrow r_{u_i}, r_{u_j}, \pi(c(u_i)), \pi(c(v_j)) \longrightarrow $}

\ \\

\visible<7->{V accepts, if $e_{u_i} = H (\pi(c(u_i)) || r_{u_i}) $ and
$e_{u_j} = H (\pi(c(u_j)) || r_{u_j}) $}
\end{center}

 \column{3.25cm}
\begin{center}
\includegraphics[width=2cm]{vercingetrorix.jpg}

\visible<4->{Chooses  $i$ and $j$}
\end{center}
\end{columns}

\end{frame}

% \begin{frame}
% \frametitle{Graph 3-coloring}

% Playing several time this procedure Bob is convinced that Alice has a
% 3-coloring of $G$. 


% \begin{block}{Completeness}
% If Alice knows the coloring then Bob will accept her proof.
% \end{block}


% \begin{block}{Soundness}
% If Alice does not know the coloring then Bob will detect it with
% probability $\frac{1}{\# edges}$
% \end{block}


% \begin{block}{Zero-knowledge}
%   Bob just sees two random colors. Hence he learns nothing about the
%   3-coloring of $G$.
% \end{block}

% %RK : ZKP are sensible to Man in the middle attack.

% \end{frame}





\begin{frame}
  \frametitle{Schnorr Protocol, 1991}

  Let $G_q$ a cyclic group of order $q$ with a public generator $g$

\begin{block}{Goal}
  P wants to prove the knowledge of $x$, where $y=g^x$
\end{block}


 \begin{columns}[c] % the "c" option specifies center vertical alignment
 \column{3.25cm}
\begin{center}
\includegraphics[width=2cm]{pascal.jpg}

\visible<2->{Chooses a random $r$}
\end{center}
 \column{5cm}
  
\begin{center}
\visible<3->{$\longrightarrow t=g^r \longrightarrow $}

\ \\

\visible<5->{$ \longleftarrow c \longleftarrow $ }

\ \\

\visible<6->{$\longrightarrow s= r + x \cdot c \longrightarrow $}

\ \\

\visible<7->{V accepts, if $ t \cdot y^{c}= g^s$}
\end{center}

 \column{3.25cm}
\begin{center}
\includegraphics[width=2cm]{vercingetrorix.jpg}

\visible<4->{Chooses a random $c$}
\end{center}
\end{columns}

\visible<8->{$$t \cdot y ^c = g^r \cdot (g^x)^c  = g^{r + x \cdot c}= g^s $$}

\end{frame}

 \section{Conclusion}

  \begin{frame}
\frametitle{Today}
\begin{enumerate}
\item Historic of Cryprography
\item Cryptographic primitives
\item Properties security
\end{enumerate}
  \end{frame}

\begin{frame}
\frametitle{Ron Rivest}

\begin{center}
{\bf ``Once you have something on the Internet, you are telling the
world, please come hack me.''}

\ \\

\includegraphics[width=3cm]{Rivest.jpg}
\end{center}

\end{frame}
  

\end{document}