%        File: crittografia.tex
%
% (c) Copyright 2009 Andrea Lo Pumo aka AlpT <alpt@freaknet.org>
%
% This source code is free software; you can redistribute it and/or
% modify it under the terms of the GNU General Public License as published 
% by the Free Software Foundation; either version 2 of the License,
% or (at your option) any later version.
%
% This source code is distributed in the hope that it will be useful,
% but WITHOUT ANY WARRANTY; without even the implied warranty of
% MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
% Please refer to the GNU Public License for more details.
%
% You should have received a copy of the GNU Public License along with
% this source code; if not, write to:
% Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
%

\documentclass[a4paper]{article}
%%% 	 Orientamento	      %%%
%\usepackage[landscape]{geometry}
%%%			      %%%

\usepackage{xr-hyper}
\usepackage{amath}

\externaldocument[AI-]{algebraI}[../../algebra/1/algebraI.pdf]
\externaldocument[AL-]{alineare}[../../algebra/lineare/alineare.pdf]
\externaldocument[GII-]{geometriaII}[../../geometria/2/geometriaII.pdf]
\externaldocument[AC-]{complementi}[../../algebra/complementi/complementi.pdf]
\ifpdf
\newcommand{\AI}[1]{\T{[AI,\ref{AI-#1},pg.\pageref{AI-#1}]}}
\newcommand{\AL}[1]{\T{[AL,\ref{AL-#1},pg.\pageref{AL-#1}]}}
\newcommand{\GII}[1]{\T{[GII,\ref{GII-#1},pg.\pageref{GII-#1}]}}
\newcommand{\AC}[1]{\T{[AC,\ref{AC-#1},pg.\pageref{AC-#1}]}}
\else
\newcommand{\AI}[1]{\T{[AI,x.y.z,pg.xx]}}
\newcommand{\AL}[1]{\T{[AL,x.y.z,pg.xx]}}
\newcommand{\GII}[1]{\T{[GII,x.y.z,pg.xx]}}
\newcommand{\AC}[1]{\T{[AC,x.y.z,pg.xx]}}

% add label debugging if we are not compiling pdf.
\let\oldlabel\label
\renewcommand{\label}[1]{ [#1] \oldlabel{#1}}
\fi


\begin{document}
\title{Crittografia}
\author{AlpT (@freaknet.org)\\
\small{\url{http://freaknet.org/alpt}}
}


\pagenumbering{roman}
\maketitle{}

\begin{abstract}
Questo testo e' una rielaborazione personale degli appunti presi durante
il corso di Teoria dei Codici e Crittografia, tenuto dal Prof. Re Riccardo presso il dipartimento di
Matematica, Catania, A.A. 2008/2009.\\
Saro' ben lieto di correggere ogni eventuale errore che mi comunicherai.

Buon lettura.
\begin{center}
	\verb|^_^|
\end{center}
\end{abstract}

\input{gpl}

\clearpage
\tableofcontents
\clearpage
\pagenumbering{arabic}

\let\oldsection\section
\renewcommand{\section}[1]{\oldsection{#1}\ilabel{#1}}
\let\oldsubsection\subsection
\renewcommand{\subsection}[1]{\oldsubsection{#1}\ilabel{#1}}
\let\oldsubsubsection\subsubsection
\renewcommand{\subsubsection}[1]{\oldsubsubsection{#1}\ilabel{#1}}


\def\RE#1#2{\T{[RE,#1,pg.#2]}}   %% Appunti di Re modificati a penna
\def\QUA#1#2{\T{[QUA,#1,pg.#2]}} %% Appunti sul quaderno
%% Quando trascrivi le proposizioni qui, come \ilabel usa \ilabel{QUA#1#2}
%% e sostituisci QUA con \def\QUA#1#2{\see{QUA#1#2}} 


\def\.{\cdot}
\def\Z{{\mathbb{Z}}}
\newcommand{\pmin}[2]{P_{\T{min}}\pton{#1,#2}}
\def\orto#1{{#1}^{\perp }}
\def\N{{\mathbb{N}}}
\def\R{{\mathbb{R}}}

\section{Varie}
\begin{defn}
	Con $|[n]_b|$ indichiamo il numero di cifre di $n$ in base $b$
\end{defn}
\begin{prop}
Sia $n\in \N$, allora
\eal{&|[n]_b|=\floor{\log_bn}+1
}
e' il numero di cifre di $n$ scritto in base $b$
\end{prop}
\begin{proof}
	\eal{&n=n_0+n_1b+n_2b^2+\dots+n_kb^k\NN
	\T{ dove } k=
	\max{k\in \N\;|\; b^k\le n} 
	\> b^k\le n <b^{k+1}
	\> k\le \log_bn < k+1 \> \floor{\log_bn} = k=|[n]_b|-1
	}
\end{proof}
\begin{prop}
	Diffie-Helmann.\\
	Sia $F_q$ un campo finito e $F_q^*=\gen{g}$,
	\eal{&1.\;\;A\T{ sceglie un intero $0\le a\le q-1=|F_q^*|$ }\NN
	2.\;\;B \T{ scegliere un intero $0\le b\le q-1$ }\NN
	3.\;\;A\T{ trasmette a $B$ $g^a$ }\NN
	4.\;\;B\T{ trasmette $g^b$ }\NN
	5.\;\;\T{La chiave comune che useranno $A$ e $B$ sara' $g^{ab}$}
	}
	$A$ e $B$ sono in grado di calcolare $g^{ab}$ perche' conoscono
	rispettivamente $(a,g^b)$ e $(b,g^a)$.\\
	La supposizione di Diffie-Helmann dice: se $C$ conosce solo $g^a$ e
	$g^b$, allora per calcolare
	$g^{ab}$,  dovra' prima calcolare $a$ e $b$
	risolvendo  il logaritmo discreto:
	\eal{&\log g^b,\;\;\log g^a
	}
	Il logaritmo discreto e' un problema non polinomiale.\\

	Il protocollo Diffie-Helmann non puo' essere usato senza firma
	digitale, perche' altrimenti $C$ puo' fare dello spoofing:
	\eal{&
	A: g^a \longrightarrow  C \NN
	C: g^c \longrightarrow A\NN
	B: g^b \longrightarrow  C \NN
	C: g^c \longrightarrow B\NN
	\T{chiave tra $A,C$: $g^{ac}$, chiave tra $B,C$: $g^{bc}$}
	}
\end{prop}
\section{Tempistica}
\begin{defn}
	Date due successioni $\pgra{x_n},\pgra{y_n}\( \mathbb{C}$, poniamo
	\eal{&x_n=O(y_n)\definizione{\=}\exists C\in \mathbb{R}\;\exists N\in
	\mathbb{N}:\;\;
	|x_n|\le C|y_n|\;\;\forall n> N
	}
	Questa definizione si puo' estendere su funzioni di tipo
	$\N^m\longrightarrow \mathbb{C}$.\\
	In pratica $f(n)=O(g(n))$ vuol dire che $f(n)$ e' limitata da $g$, a meno
	di una costante. Quindi cresce meno rapidamente di quanto cresce
	$g$.\\
	Usiamo la seguente convenzione:
	\eal{&a=b+O(y_n)\definizione{\=} a-b=O(y_n)}
\end{defn}
\begin{prop}\label{Ovarie}
	\eal{&1.\;\;\lim_{n\to \8} \frac{f(n)}{g(n)} = k \> f(n)=O(g)\NN
	2.\;\;O(kg(n))=O(g(n))\NN
	3.\;\;O(\log_bn) =O(\log_2n)\NN
	4.\;\;f(x)\in \R[x] \> O(f(n))=O(n^{\deg f})
	}
\end{prop}
\begin{proof}
	\step{}{Dim $3.$}
	\begin{prova}
		\eal{&\log_bn=\frac{\log_2n}{\log_2b}
		}	
		e quindi con la $2.$ si ha la tesi.
	\end{prova}
\end{proof}
\def\time{{\oname{Time}}}
\begin{defn}
	Sia $f$ un algoritmo. Indichiamo con $\time(f(n))$ il numero di
	operazione elementari che $f$ impiega per calcolare $f(n)$. Come
	operazioni elementari consideriamo quelle logiche tra due bit.
\end{defn}
\def\MCD{{\oname{MCD}}}
\def\Bezout{{\oname{Bezout}}}
\begin{prop}\label{TempiInN}
	Siano $a,b\in \N$
	\eal{&1.\;\;\time(a+b)= 
	O(\max\pton{\floor{\log_2a}, \floor{\log_2b}})\NN
	2.\;\;\time(ab)= 
	O({\floor{\log_2a} \floor{\log_2b}})\NN
	3.\;\;\time(a/b)=O(\max\pton{\floor{\log_2a}, \floor{\log_2b}}^2)\NN
	4.\;\;\time(\MCD(a,b))=O(\floor{\log_2}^3)\NN
	5.\;\;\time(\Bezout(a,b))=O(\floor{\log_2}^3)
	}
	dove $\Bezout(a,b)=(\lambda,\mu)$ tali che $\MCD(a,b)=\lambda a+\mu
	b$.
\end{prop}
\begin{proof}
	\step{}{}
	\begin{prova}
	Si adopera il classico algoritmo di addizione: si scrivono le cifre di
	$a$ e $b$ in due righe e si fanno le addizioni delle cifre (bit) con
	riporto. Se $a>b$, allora $\time(a+b)=O(k)$ dove $k$ e' il numero di
	cifre (bit) di $a$.
	\end{prova}
	\step{}{}
	\begin{prova}
		Si adopera la classica moltiplicazione. Si conta quante
		addizioni si fanno. Se $a\ge b$ si ottiene
		$\time(ab)=h\time(a+b)=hO(k)O(hk)$. Dove $h$ e' il numero di
		bit di $b$.
	\end{prova}
	\step{}{}
	\begin{prova}
		Si utilizza l'algoritmo di divisione classico e si conta
		quante sottrazioni si fanno.
	\end{prova}
	\step{}{}
	\begin{prova}
		Si utilizza l'algoritmo euclideo per il MCD e si conta quanti
		passi si adoperano:
\begin{align*}
	&a=bq_1+r_1\\
	&b=r_1q_2+r_2\\
	&r_1=r_2q_3+r_3\\
	&r_2=r_3q_4+r_4\\
	&\vdots\NN
	r_{j}=r_{j+1}q_{j+2}+r_{j+2}\NN
	\quad\vdots\\
	&r_{n-3}=r_{n-2}q_{n-1}+r_{n-1}\\
	&r_{n-2}=r_{n-1}q_{n}+r_{n}\\
	&r_{n-1}=r_{n}q_{n+1}+0\NN
	d=r_n
\end{align*}
\step{}{$r_{j+1}<\frac{1}{2}r_{j-1}$, ovvero $r_{j+2}$ e' piu' che
dimezzato rispetto a $r_{j-1}$}
		\begin{prova}
			\case{$r_j\le \frac{1}{2}r_{j-1}$}
			\begin{prova}
				\eal{&r_{j-1}=r_jq_{j+1}+r_{j+1}
				\ubrace{\>}{\T{resto della divisione}} 
				r_{j+1} < r_j \le \frac{1}{2}r_{j-1}
				}
			\end{prova}
			\case{$r_j > \frac{1}{2}r_{j-1}$}
			\begin{prova}
				$r_{j+1}$ e' il resto della divisione 
				$r_{j-1}/r_j$. Ma $r_j$ e' piu' della meta' di
				$r_{j-1}$, quindi il quoziente e'
				$q_{j+1}=1$ e 
				\eal{&r_{j-1}=r_jq_{j+1}+r_{j+1}
				= r_j+r_{j+1} \> r_{j+1}= r_{j-1}-r_j 
				< r_{j-1} - \frac{1}{2}r_{j-1} =
				\frac{1}{2}r_{j-1}
				}
			\end{prova}
		\end{prova}
		Passiamo quindi affermare che ogni due passi $r_j$ e' piu' che
		dimezzato, quindi il numero di passi $t$ e' $<\log_2 r_1$, 
		\eal{&r_1 < b \le  a \> t < \floor{\log_2 a}+1=k
		}
		Ad ogni passo eseguiamo una divisione e una addizione:
\eal{&\time(MCD(a,b))= (\time(a+b)+\time(a/b))t <
(\time(a+b)+\time(a/b))k= (O(k)+O(k^2))k \>\NN
\> \time(MCD(a,b))= O(k^3)
		}
	\end{prova}
	\step{}{}
	\begin{prova}
	L'algoritmo per Bezout consiste nel calcolare $\MCD(a,b)$ con Euclide
	facendo delle sostituzioni ad ogni passo (vedi AlgebraI). Ad ogni
	sostituzione si effettua una moltiplicazione e una addizione, quindi
\eal{&\time(\Bezout)= \time(\MCD(a,b))+(\time(a+b)+\time(a/b))t
=2O(k^3)=O(k^3)
	}
	\end{prova}

\end{proof}
\def\Z{{\mathbb{Z}}}
\begin{prop}\label{TempiInZn}
	In $\Z_n$, si ha:
	\eal{&1.\;\;\time(a+b)= 
	O(\log_2n)\NN
	2.\;\;\time(ab)= 
	O(\log_2^2n)\NN
	3.\;\;\time(\inv a)=O(\log_2^3n)
	}
\end{prop}
\begin{proof}
	\step{}{1. e 2.}
	\begin{prova}
		
	In $\Z_n$ le rappresentazioni minime di $a,b$ sono tali che
	$|[a]_2|,|[b]_2|\le |[n]_2|$. Quindi applicando la \see{TempiInN} si
	ha la tesi.
	\end{prova}
	\step{}{}
	\begin{prova}
		Per calcolare $\inv a$ si deve usare l'algoritmo di euclide:
\eal{&\T{sia }b=\inv a\NN
ab=1\;\Z_n \= ab-\lambda n=1 \= ba-\lambda n =1
\> (b,\lambda)=\Bezout(a,n)
	}
	Quindi per \see{TempiInN} si ha la tesi.
	\end{prova}
\end{proof}
\begin{prop}
	Algoritmo della quadrature successive.\\
Sia $m\in \N$.
Per calcolare $b^m\;\;\Z_n$ scriviamo $m$ in base due:
$m=m_0+m_12+\dots+m_k2^k,\;\;m_i\in\pgra{0,1}$,allora
\eal{&b^m=\prod_{i=0}^{k}b^{m_i2^i}
}
poiche' $m_i=0$ oppure $m_i=1$, possiamo cosi' scrivere il prodotto:
\eal{&a_0=b,\;\;b_0=\sist{b&m_0=1\\
1& m_0=0}\NN
a_{i+1}=a_i^2,\;b_{i+1}=\sist{b_ia_{i+1} & m_{i+1}=1\\
b_i& m_{i+1}=0}
}
Tutte le moltiplicazioni si intendono in $\Z_n$.\\

Al massimo effettuiamo $k=\floor{\log_2 m}$ moltiplicazioni, quindi per la \see{TempiInZn} si ha:
\eal{&\time = O(\floor{\log_2 m }\floor{\log_2n}^2)}

Nota:
\eal{&(b,n)=1 \> b^{\varphi(n)}=1\;\;\Z_n\NN
m \ubrace{=}{\T{divisione}} \varphi(n)q + m',\;m'<\varphi(n) \NN
\qq \> b^m=b^{m'}\;\Z_n
}
\end{prop}

%%%%%%%%%
\printindex
\end{document}