\documentclass[a4,portrait]{seminar}

\usepackage{latexsym}
\usepackage{amssymb,amsfonts,amsmath,amsthm}
\usepackage{fancybox}
\usepackage{semlayer}
\usepackage[italian]{babel}

%\input{righe}
\input{seminar.bug}
\input{seminar.bg2}
 
% Increase slide height (\slidewidth in portrait mode) but reduce text height
\addtolength{\voffset}{5cm}
\addtolength{\slidewidth}{1.5cm}
\extraslideheight{1.8cm}
 
% Header and footer inside the frame
\newslideframe{HeaderLeft}{%
\boxput(-0.92,0.93){\makebox[0cm][l]{\Large \sezione}}{#1}}
\newslideframe{HeaderRight}{%
\boxput(0.92,0.93){\makebox[0cm][r]{\Large \theslide}}{#1}}
\newslideframe{HeaderRule}{\boxput(0,0.88){\rule{8.1cm}{2pt}}{#1}}
%\newslideframe{FooterRule}{\boxput(0,-0.88){\rule{8.1cm}{2pt}}{#1}}
%\newslideframe{Footer}{\boxput(0,-0.94){\Large My organization}{#1}}
 
\slideframe*{HeaderLeft}
\slideframe*{HeaderRight}
\slideframe*{HeaderRule}
%\slideframe*{FooterRule}
%\slideframe*{Footer}
 
\slidepagestyle{empty}

\newcommand{\cri}[1]{$\mathrm{#1}$}
\newcommand{\mabb}[1]{\mathbb{#1}}
 
 
% oggetti matematici
\def\NN{{{\mabb{N}}}}
\def\ZZ{{{\mabb Z}}}
\def\QQ{{{\mabb Q}}}
\def\RR{{{\mabb R}}}
\def\u{{{\bf 1}}}
\def\implica{{{\Rightarrow}}}
\def\impligiu{{{\Downarrow}}}
\def\implisu{{{\Uparrow}}}
 
\newcommand{\zsupz}[1][p]{{\ZZ_{\!/\!#1\ZZ}}}
\newcommand{\pol}[1][p]{\mathfrak{#1}}
\newcommand{\zsunz}{\zsupz[n]}
\newcommand{\zsuppz}{\zsupz[p^2]}
\newcommand{\mcm}{\mathrm{mcm}}
\newcommand{\MCD}{\mathrm{MCD}}
\newcommand{\XOR}{\mathrm{XOR}}
\newcommand{\GF}{\mathrm{GF}}
\newcommand{\carmi}{\lambda}
\newcommand{\Ogr}{\mathrm{O}}
\newcommand{\opi}{\mathrm{o}}
\newcommand{\ord}{\mathrm{ord}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\algoris}{\rightarrow}
%\newcommand{\Pr}{\mathrm{Pr}}
\newcommand{\al}[1]{\mathcal{#1}}
\newcommand{\gen}[1]{\ensuremath{\langle {#1} \rangle}}
\newcommand{\ps}[1][s]{\pol ({#1})}
 
%
% Abbreviazioni
%
 
\newcommand{\tc}{ tale che }
\newcommand{\okuc}{Okamoto-Uchiyama}

%
% FUNZIONI E SIMBOLI PER LA TESI
%
 
\newcommand{\DiHe}{\mathrm{DH}}
\newcommand{\LD}{\mathrm{LD}}
\newcommand{\RSA}{\mathrm{RSA}}
\newcommand{\clP}{\ensuremath{P}}
\newcommand{\clPP}{\ensuremath{PP}}
\newcommand{\clNP}{\ensuremath{NP}}

%
% Partecipanti ai protocolli
%

\def\CC{{{\mathbf C}}}
%\def\BB{{{\mathbf B}}}
\def\AA{{{\mathbf A}}}
\def\EE{{{\mathbf E}}}
\def\DD{{{\mathbf D}}}
\def\Fi{{{\mathbf F}}}

\newcommand{\sezione}{}

\newcommand{\Sezione}[1]{
 \renewcommand{\sezione}{#1}
}

\newcommand{\Titolo}[1]{%
\begin{center}
\large\bf%
\shadowbox{#1}%
\end{center}%
\vspace{1ex minus 1ex}}

\newcommand{\Titolino}[1]{%
\begin{center}
\large\bf%
#1%
\end{center}%
\vspace{1ex minus 1ex}}

%\newcommand{\entrylabel}[1]{\mbox{\textsf{#1}}\hfil}

\newenvironment{proto}%
  {\begin{list}{}{\renewcommand{\makelabel}[1]{[\makebox[24pt]{##1}] \hfil}%
    \settowidth{\labelwidth}{[\makebox[24pt]{}]}%
    \setlength{\leftmargin}{\labelwidth}%
    \addtolength{\leftmargin}{\labelsep}%
    \setlength{\itemindent}{0cm}%
   }}%
  {\end{list}}

\newenvironment{elenco}[1]%
  {\begin{list}{}{\renewcommand{\makelabel}[1]{$\al{##1}$ \hfil}%
    \settowidth{\labelwidth}{$\al{#1}$}%
    \setlength{\leftmargin}{\labelwidth}%
    \addtolength{\leftmargin}{\labelsep}%
   }}%
  {\end{list}}

\begin{document}

\Sezione{Crittografia: a cosa serve}

\begin{slide*}

 \Titolo{Crittografia classica}
 \begin{itemize}
 \item Trasmissione di segreti.
 \end{itemize}
 Protocolli a due, codici simmetrici.

 \bigskip

 \Titolo{Crittografia moderna}
 \begin{itemize}
 \item Autenticazione
  \begin{itemize}
  \item Verifiche di identit\`a
   \begin{itemize}
   \item Frima digitale
   \item Controllo login
   \end{itemize}
  \item Verifiche di integrit\`a
   \begin{itemize}
   \item Integrit\`a file
   \item Integrit\`a messaggi
   \end{itemize}
  \end{itemize}
 \end{itemize}
 Protocolli pubblici, codici asimmetrici.

\end{slide*}

\Sezione{Crittografia: come funziona}

\begin{slide*}
 \Titolo{Trasmissione segreta}
% \begin{tabular}{@{}c@{}c@{}c@{}c@{}c@{}}
%Messaggio & & Messaggio & & Messaggio \\
 \begin{tabular}{@{}ccccc@{}}
  chiaro & Codifica & cifrato & Decodifica & chiaro \\
  $m$ & $\algoris\!\!\fbox{$\al{C}$}\!\!\algoris$ & $x$ &
      $\algoris\!\!\fbox{$\al{D}$}\!\!\algoris$ & $m$ \\
 \end{tabular}
 \bigskip

 \Titolino{Protocollo simmetrico}
 \begin{tabular}{@{}ccccc@{}}
  ~~~m~~~ & $\algoris\!\!\fbox{$\al{C}^s_K$}\!\!\algoris$ & ~~~$x$~~~ &
      $\algoris\!\!\fbox{$\al{D}^s_K$}\!\!\algoris$ & ~~~$m$~~~ \\
 \end{tabular}
 \medskip

 Si usa una sola chiave, nota sia a chi deve cifrare sia a chi
 deve decifrare
 \Titolino{Protocollo asimmetrico}
 \begin{tabular}{@{}ccccc@{}}
  ~~~$m$~~~ & $\algoris\!\!\fbox{$\al{C}_{K_c}$}\!\!\algoris$ & ~~$x$~~ &
      $\algoris\!\!\fbox{$\al{D}_{K_d}$}\!\!\algoris$ & ~~~$m$~~~ \\
 \end{tabular}
 \medskip

 Le due chiavi sono distinte, una pu\`o essere resa pubblica
 mentre la seconda rimane segreta

\end{slide*}

\begin{slide*}

 \Titolino{Uso misto}

I protocolli simmetrici sono pi\'u efficienti; i due sistemi vengono
usati in coppia. Il protocollo asimmetrico cifra una chiave \emph{effimera}.

\medskip

 \begin{tabular}{@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}c@{}}
&&$K_s$&$\rightarrow$&\fbox{$\al{C}_{K_c}$}&$\rightarrow$&$k$ \\
&&$\downarrow$&&&&$\downarrow$\\
$m$&$\rightarrow$&\fbox{$\al{C}_{K_s}^s$}&$\rightarrow$&$x$&$\rightarrow$&$(k,x)$&$\rightarrow$&$x$&$\rightarrow$&\fbox{$\al{D}_{K_s}^s$}&$\rightarrow$&$m$\\
&&&&&&$\downarrow$&&&&$\uparrow$\\
&&&&&&$k$&$\rightarrow$&\fbox{$\al{D}_{K_d}$}&$\rightarrow$&$K_s$ \\
 \end{tabular}

\bigskip

 \Titolo{Firma digitale}
 \begin{tabular}{@{}ccccc@{}}
  testo & Firma & firmato & Verifica &  \\
  $m$ & $\algoris\!\!\fbox{$\al{F}_{K_f}$}\!\!\algoris$ & $(m,f)$ &
      $\algoris\!\!\fbox{$\al{V}_{K_v}$}\!\!\algoris$ & S\'{\i}/No \\
 \end{tabular}
\end{slide*}

\Sezione{Protocolli algebrici: RSA}

\begin{slide*}

Due primi $p,q$; usiamo il prodotto $n = pq$.\\
Messaggi in $M = \zsunz$. {\overlay1 Cifrati in $X= \zsunz$.}\\
Due esponenti $ cd \equiv 1 \pmod{\phi(n)}$.
\bigskip
{\overlay1
 \Titolo{Trasmissione segreta}
}
 \begin{proto}
 \item[PUB] $K_{\overlay1 c}=(n, c)$
 \item[PRI] $K_{\overlay1 d}=(n, d)$ {\overlay1 , \emph{fattorizzazione $n=pq$}}
{\overlay1 \item[CIF] $\al{C}_{K_c}(m) \algoris x \equiv m^c \pmod n$
 \item[DEC] $\al{D}_{K_d}(x) \algoris x^d \equiv m^{cd} \equiv m \pmod n$
}
 \end{proto}

\bigskip
\hrule

{\overlay1 \begin{tabular}{@{}ccccc@{}}
  $M \ni m$ & $\algoris\!\!\fbox{$\al{C}_{K_c}$}\!\!\algoris$ & $m^c$ &
      $\algoris\!\!\fbox{$\al{D}_{K_d}$}\!\!\algoris$ & $m^{cd}$ \\
 \end{tabular} }
\bigskip

{\overlay1
Il protocollo RSA \`e il pi\'u semplice da descrivere e il pi\'u usato dei
protocolli asimmetrici, ma {\bf non} il pi\'u sicuro.}
\end{slide*}

\addtocounter{slide}{-1}

\begin{slide*}

Due primi $p,q$; usiamo il prodotto $n = pq$.\\
Messaggi in $M = \zsunz$. {\overlay1 Firme in $F=\zsunz$.}\\
Due esponenti $ cd \equiv 1 \pmod{\phi(n)}$.
\bigskip
{\overlay1
 \Titolo{Firma digitale}
}
 \begin{proto}
 \item[PUB] $K_{\overlay1 v}=(n, c){\overlay1 =K_c}$
 \item[PRI] $K_{\overlay1 f}=(n, d){\overlay1 =K_d}$
{\overlay1 \item[FIR] $\al{F}_{K_f}(m) \algoris f \equiv m^d \pmod n$
 \item[VER] $\al{V}_{K_v}(m,f)$ verifica se $m \equiv f^c \pmod n$
}
 \end{proto}

\bigskip
\hrule

{\overlay1 In realt\`a non \`e necessario che venga trasmesso anche il
messaggio, pu\`o essere ricavato dalla firma $f$.}
\bigskip

{\overlay1 \begin{tabular}{@{}ccccc@{}}
  $m$ & $\algoris\!\!\fbox{$\al{F}_{K_f}$}\!\!\algoris$ & $m^d$ &
      $\algoris\!\!\fbox{$\al{V}_{K_v}$}\!\!\algoris$ & $m^{dc}\equiv m$ \\
 \end{tabular} }

\end{slide*}

\begin{slide*}
 \Titolo{Dimostrazione funzionamento}
Dal protocollo sappiamo che
 \begin{itemize}
 \item $n=pq$
 \item $cd\equiv 1 \pmod{\phi(n)}$
 \end{itemize}
Per la definizione della $\phi$ di Eulero
 \begin{itemize}
 \item $\phi(n)=\phi(p)\phi(q) = (p-1)(q-1)$
 \end{itemize}
Per il piccolo teorema di Fermat:
 \begin{itemize}
 \item $\forall m \in \NN,\, m^p \equiv m^{\phi(p)+1} \equiv m \pmod p$
 \item $\forall m \in \NN,\, m^q \equiv m^{\phi(q)+1} \equiv m \pmod q$
 \end{itemize}
Per il teorema cinese dei resti
 \begin{itemize}
 \item $m^{cd} \equiv m^{\phi(p)\phi(q)+1} \equiv m \pmod{pq}$
 \end{itemize}
 \bigskip

 In realt\`a \`e sufficiente $\carmi(n)=\mcd(\phi(p), \phi(q))$
\end{slide*}


\Sezione{Protocolli algebrici: ElGamal}

\begin{slide*}

Un solo primo $p$.
Un generatore $\gen{g}=\zsupz^*$.\\
Un elemento $\alpha\equiv g^a \pmod p$.\\
Messaggi in $M = \zsupz^*$. {\overlay1 Cifrati in $X= \zsupz^2$.}
\bigskip

{\overlay1
 \Titolo{Trasmissione segreta}
}
 \begin{proto}
 \item[PUB] $K_{\overlay1 c}=(p, \alpha, g)$
 \item[PRI] $K_{\overlay1 d}=(a)$
{\overlay1 \item[CIF] $b \in \zsupz^*$, $\al{C}_{K_c}(m) \algoris x = (g^b,m\alpha^b)$
 \item[DEC] $\al{D}_{K_d}(x) \algoris (m\alpha^b)(g^b)^{-a} \equiv m \pmod p$
 {\overlay2 \\$ (p)$ \\ $(p)$}
}
 \end{proto}
\bigskip
\hrule
\bigskip

{\overlay1 Il protocollo ElGamal, a pari condizioni \`e pi\'u sicuro
dell'RSA. Se al posto di $p$ si usa $n=pq$ la maggior sicurezza \`e dimostrabile.}

\end{slide*}

\addtocounter{slide}{-1}

\begin{slide*}

Un solo primo $p$.
Un generatore $\gen{g}=\zsupz^*$.\\
Un elemento $\alpha\equiv g^a \pmod p$.\\
Messaggi in $M = \zsupz^*$. {\overlay1 }
\bigskip

{\overlay1
 \Titolo{Firma digitale}
}
 \begin{proto}
 \item[PUB] $K_{\overlay1 v}=(p, \alpha, g){\overlay1 = K_c}$
 \item[PRI] $K_{\overlay1 f}=(a){\overlay1 = K_d}$
{\overlay1 \item[FIR] $r \in \zsupz[(p-1)]^*, \quad x\equiv g^b\pmod{p}$,\\
 $\phantom{l}m \equiv xa+ry \pmod{p-1}$,\\ $\phantom{l}\al{F}_{K_f}(m)
 \algoris f = (x,y)$
 \item[VER] $\al{V}_{K_v}$ verifica che $ \alpha^xx^y \equiv g^m \pmod p$
}
 \end{proto}
\bigskip
\hrule
\bigskip

{\overlay1 La verifica funziona perch\'e\\
$ \alpha^x x^y \equiv g^{K_dx}g^{ry} \equiv g^{K_dx + ry} \equiv g^m
\pmod p$\\
ed $r$ \`e invertibile modulo $p-1$.}

\end{slide*}


\Sezione{SSH}

\begin{slide*}
\Titolo{Obiettivo}

rendere sicura la gestione remota
di un account.

\begin{itemize}
\item controllare l'identit\`a della macchina\\
Per evitare che la password vada al server
sbagliato e difendere da
\emph{man in the middle}.
\item cifrare il resto della connessione\\
La password non passa in chiaro, neppure
altre password di collegamenti in cascata.
\item evitare che la connessione venga \emph{scippata}
\item[-] pu\`o comprimere la connessione
\item[-] pu\`o trasferire finestre X
\end{itemize}

\Titolo{File}

{\small
\begin{verbatim}
bodrato@socrate 12:07:36 ~>ls .ssh
authorized_keys  identity         known_hosts
config           identity.pub     random_seed
\end{verbatim}}


\end{slide*}

\Sezione{SSH versus \emph{man in the middle}}
\begin{slide*}

\Titolino{Prima connessione}

{\scriptsize
\begin{verbatim}
bodrato@socrate 11:39:58 ~>ssh gauss.dm.unipi.it
Host key not found from the list of known hosts.
Are you sure you want to continue connecting? no
\end{verbatim}}

\Titolino{Attacco o amnesia}

{\scriptsize
\begin{verbatim}
bodrato@socrate 11:42:04 ~>ssh posso.dm.unipi.it
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@      WARNING: HOST IDENTIFICATION HAS CHANGED!       @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now
(man-in-the-middle attack)! It is also possible
that the host key has just been changed.
Please contact your system administrator.
Add correct host key in /home/bodrato/.ssh/known_hosts to
get rid of this message. Agent forwarding is disabled to
avoid attacks by corrupted servers. X11 forwarding is
disabled to avoid attacks by corrupted servers.
Are you sure you want to continue connecting (yes/no)? no
\end{verbatim}}


\end{slide*}

\Sezione{SSH: autenticazione RSA}
\begin{slide*}
{\footnotesize
\begin{verbatim}

@socrate>ssh-keygen
Initializing random number generator...
Generating p:  .........++ (distance 260)
Generating q:  ...++ (distance 64)
Computing the keys...
Testing the keys...
Key generation complete.
Enter file in which to save the key
  (/home/bodrato/.ssh/identity):
Enter passphrase:
Enter the same passphrase again:
Your identification has been saved in
 /home/bodrato/.ssh/identity.
Your public key is:
1024 33 152589...644337 bodrato@socrate
Your public key has been saved in
 /home/bodrato/.ssh/identity.pub
@socrate>scp .ssh/identity.pub posso:
bodrato@posso.dm.unipi.it's password:

@posso>cat identity.pub >>.ssh/authorized_keys
@posso>rm identity.pub

@socrate>ssh posso
Last login: Mon Mar 13 11:15:43 2000 from linuz
@posso>
\end{verbatim}
}
\end{slide*}

\Sezione{SSH: Esempio avanzato}
\begin{slide*}
\Titolo{Posta remota}
\Titolino{sotto KDE}
~/.kde/share/applnk/apps/postaremota.kdelnk

{\tt\footnotesize
SwallowExec=ssh -n cibs xbiff -name cibsbiff\\
SwallowTitle=cibsbiff\\
Exec=ssh -C -t -x cibs pine\\
Terminal=1\\
}

\Titolino{senza KDE}

{\tt ssh -f -n cibs xbiff}

{\tt xterm -e ssh -C -t -x cibs pine}

\end{slide*}



\Sezione{Quanto fidarsi}
\begin{slide*}
\begin{itemize}
\item Nessuna dimostrazione di sicurezza per protocolli asimmetrici
\item La segretezza dell'algoritmo {\bf non} aumenta la sicurezza
\item Buoni protocolli in un programma scritto male non danno
sicurezza
\item Un buon programma usato male non d\`a sicurezza
\end{itemize}

\end{slide*}

\end{document}
