Algoritmo.tex

% ================================ L'ALGORITMO ========================================

\chapter{L'Algoritmo}

% ======================================================================================

% ---------------------------- SECTION: INTRODUZIONE ----------------------------------

%\newpage

\section{Introduzione}

\index{AES}

\textsf{\small In questo capitolo, tratteremo il funzionamento dell'algoritmo di AES con una panoramica dall'alto, per poi affrontare nel prossimo capitolo, più in dettaglio, la sua matematica.}

% ----------------- SECTION: I TRE CONCETTI DIETRO LA CRITTOGRAFI ----------------------

%\newpage

\section{I tre concetti dietro la Crittografia} %TODO: Le tre idee/concetti/principi dietro la/alla Crittografia

\index{Shannon} \index{diffusione} \index{confusione} \index{teoria dell'informazione} \index{simmetrica}

\textsf{\small Alla base della crittografia, ci sono due importanti proprietà dei cifrari a chiave simmetrica, elaborati dal padre della teoria dell'informazione, Claude Elwood Shannon, ovvero: \emph{diffusione} e \emph{confusione}.} \\

\textsf{\small Il principio della \emph{confusione} vela la connessione tra il messaggio originale e il testo cifrato.} %TODO: messaggio/testo; [per esempio cifrario di cesare (con annessa immagine volendo)]

\textsf{\small La proprietà di \emph{diffusione}, invece, riguarda lo scombussolamento della posizione dei caratteri del messaggio.} %TODO: [un semplice esempio potrebbe essere la trasposizione delle colonne in una matrice oppure non lo scrivo.]

\index{segretezza della chiave}

\textsf{\small Un altro importante concetto è quello della \emph{segretezza della chiave}, ovvero che l'algoritmo alla base del cifrario è conosciuto, è pubblico, ma la sola conoscenza di questo non è sufficiente per poter conseguire l'accesso alle informazioni, perché per poter attingerle sarà necessario conoscere la chiave segreta.} %TODO: nella/della chiave; attingere/ottenere; attingerle/acquisire/raggiungere; concetto/astrazione

\begin{figure}[H]
	\centering
	\includegraphics[width=1\textwidth, height=1\textheight, keepaspectratio]{./images/theory_of_information/confusion-and-diffusion.png}
	\caption{Confusione e Diffusione}
	\label{fig:confusion_and_diffusion}
\end{figure}

% ------------------- SECTION: UNA PANORAMICA SULL'ALGORITMO --------------------------

\section{Una panoramica sull'Algoritmo}

%TODO: itemize?
%TODO: forse dovrei semplificarlo un attimo e parlarne più con calma prima di passare alle liste delle operazioni.

\index{state matrix} \index{matrice di stato} \index{sub-bytes} \index{mix columns} \index{shift rows} \index{add round key}

\textsf{\small I dati di input vengono caricati in una matrice 4x4, anche chiamata \emph{state matrix} (matrice di stato), dove ogni cella rappresenta 1 byte di informazione e su queste compiamo diverse operazioni: \emph{sub bytes} (sostituzione dei bytes), \emph{shift rows} (spostamento delle righe), \emph{mix columns} (mescolamento delle colonne), \emph{add round key} (aggiunta della chiave del round) per un numero di volte, di rounds pari alla grandezza della chiave.} %TODO: oppure metterli in un itemize?

\begin{figure}[H]
	\centering
	\includegraphics[width=0.8\textwidth, height=0.8\textheight, keepaspectratio]{./images/aes/key_size_and_number_of_rounds.png}
	\caption{Key Size e Numero di Rounds}
	\label{fig:aes_key_size_number_of_rounds}
\end{figure}

\index{XOR}

\textsf{\small Nel primo round svolgiamo uno XOR tra il messaggio d'input e la chiave segreta.}

\textsf{\small Lo \emph{XOR} (\emph{E\textbf{X}clusive-\textbf{OR}}) bit-a-bit è un'operazione di mascheratura dei bit, dove se i due bit di input sono diversi, allora produrrà un 1 in uscita, altrimenti se sono uguali, uno zero.} 

\begin{figure}[H]
	\centering
	\includegraphics[width=0.6\textwidth, height=0.6\textheight, keepaspectratio]{./images/XOR/XOR-Truth-Table.png}
	\caption{Tabella della verità dello XOR}
	\label{fig:xor_truth_table}
\end{figure}

\subsection{Perché lo XOR è usato in crittografia?}

\index{XOR} \index{AND} \index{OR} \index{NOT}

\begin{itemize}
	\item \textsf{\small Lo XOR non \emph{leaka} informazioni sull'input originale.} %TODO: magari leaka non è proprio il top come parola, non esiste nemmeno in italiano
	\item \textsf{\small Lo XOR è una \emph{involutory function} (funzione involutoria) tale che se la applichi due volte riottieni il testo originale.}
	\item \textsf{\small L'output dello XOR dipende da entrambi gli input. Non è così per le altre operazioni (AND, OR, NOT, ecc.).}
\end{itemize}

\fleuron

%TODO: magari semplificare questa parte.

\subsection{Key Expansion | Key Schedule}

\index{key expansion} \index{key schedule} \index{rounds} \index{chiavi}

\textsf{\small Per poter elaborare i rounds, l'algoritmo ha bisogno di molte chiavi, una per round, queste vengono tutte derivate dalla chiave iniziale.}

%TODO: Fare una subsection?: titolo: "Come vengono ottenute le chiavi per ogni round?" oppure no? KEY EXPANSION/KEY SCHEDULE
%TODO: Per poter eseguire/elaborare i rounds, l'algoritmo ha bisogno di molte chiavi [una per round?], queste vengono tutte derivate dalla chiave iniziale. (volendo scrivere: Questo è uno dei motivi per cui AES viene criticato, perché tutte le chiavi vengono derivate dalla chiave originale).

\textsf{\small Il procedimento per ricavarle è questo: }

\index{XOR} \index{round constant}

\begin{enumerate}
	\item \textsf{\small Sposta la prima cella dell'ultima colonna della precedente chiave in fondo alla colonna.} %TODO: spostare
	\item \textsf{\small Ogni byte viene posto in una substitution box che lo mapperà in qualcos'altro.} %TODO: (S-box) dopo substitution box; specificare cosa quel qualcos'altro.
	\item \textsf{\small Viene effettuato uno XOR tra la colonna e una \emph{round constant} (costante di round) che è diversa per ogni round.} %TODO: approfondire come è diversa.
	\item \textsf{\small Infine viene realizzato uno XOR con la prima colonna della precedente chiave.}
	%\item \textsf{\small }
\end{enumerate}

\index{XOR}

\textsf{\small Per le altre colonne, vengono semplicemente eseguiti degli XOR con la stessa colonna della precedente chiave.} %TODO: rimuovere la parte tra parentesi? ovvero la parte procedimento un po' più complicato o approfondirla?; (eccetto per le chiavi a 256 bit che hanno un procedimento un po' più complicato)

\begin{figure}[H]
	\centering
	\includegraphics[width=0.8\textwidth, height=0.8\textheight, keepaspectratio]{./images/key_expansion/key_expansion.png}
	\caption{Key Expansion}
	\label{fig:key_expansion}
\end{figure}

\index{AES}

\textsf{\small La singola chiave viene espansa in 11 chiavi per AES-128, 13 per AES-192 e 15 per AES-256.}

\index{RotWord} \index{SubWord} \index{Rcon} \index{XOR}

\textsf{\small Ogni byte della chiave viene inserita in vari arrays, in cui verranno eseguite delle specifiche operazioni: \emph{RotWord}, \emph{SubWord}, \emph{Rcon} e infine verranno eseguiti degli XOR tra loro.}

\begin{figure}[H]
	\centering
	\includegraphics[width=0.6\textwidth, height=0.6\textheight, keepaspectratio]{./images/key_expansion/AES-Key_Schedule_128-bit_key.png}
	\caption{Key Expansion}
	\label{fig:key_expansion2}
\end{figure}

\subsubsection{RotWord}

\index{RotWord}

\textsf{\small Questa funzione ruota una word di 32 bits.}

\begin{figure}[H]
	\centering
	\includegraphics[width=0.4\textwidth, height=0.4\textheight, keepaspectratio]{./images/key_expansion/key_schedule-rot_word.png}
	\caption{Rot Word}
	\label{fig:rot_word2}
\end{figure}

\subsubsection{SubWord}

\index{SubWord}

\textsf{\small La funzione \emph{SubWord} sostituisce una word di 32 bits con l'S-BOX.}

\begin{figure}[H]
	\centering
	\includegraphics[width=0.4\textwidth, height=0.4\textheight, keepaspectratio]{./images/key_expansion/subWord.png}
	\caption{Sub Word}
	\label{fig:sub_word2}
\end{figure}

\subsubsection{Rcon}

\index{Rcon} \index{round constant}

\textsf{\small Questa funzione ricorsiva permette di generare delle costanti di round, attraverso questa formula:}

\begin{itemize}
	\item \textsf{\small il round\_constant(1) = 1.}
	\item \textsf{\small round\_constant(i) = $2 \cdot \text{round\_constant}(i - 1) \text{se round\_constant(i - 1) < 0x80}$}
	\item \textsf{\small round\_constant($2 \cdot \text{round\_constant(i - 1)}$) $ \oplus \hspace{0.3mm} \text{0x11B } \ge 0x80$ }
\end{itemize}

\subsection{I Rounds}

\index{rounds} \index{mix columns}

\textsf{\small Dopo aver ottenuto le chiavi, vengono compiuti i vari rounds.} 

\textsf{\small Per ogni round, eseguiamo questi passaggi, tranne per l'ultimo dove non effettuiamo il passaggio delle \emph{Mix Columns}, perché non aumenterebbe la sicurezza e semplicemente rallenterebbe: } %TODO: [magari approfondire il perché rallenterebbe]

\index{sub bytes} \index{shift rows} \index{mix columns} \index{add round key} \index{confusione} \index{segretezza della chiave} \index{diffusione} \index{Shannon}

\begin{itemize}
	\item[] \textsf{\small Applichiamo il principio di \emph{confusione} attraverso il passaggio \emph{Sub-bytes}.}
	\item \textsf{\small \underline{\emph{Sub-bytes}}: Ogni byte viene mappato in un diverso byte attraverso una s-box. Questo step applica la proprietà di \emph{confusione} di Shannon, perché oscura la relazione tra ogni byte.}
	\item[] \textsf{\small Applichiamo la proprietà di \emph{diffusione}:}
	\item \textsf{\small \underline{\emph{Shift Rows}}: La seconda riga della matrice viene spostata di 1 verso sinistra. La terza riga di 2 posizioni e la quarta di 3 (sempre verso sinistra).}
	\item \textsf{\small \underline{\emph{Mix Columns}}: Ogni bit delle colonne della matrice (di stato) vengono mischiate.} %TODO: Approfondire come vengono mischiate
	\item[] \textsf{\small Applichiamo la proprietà di \emph{segretezza della chiave}:}
	\item \textsf{\small \underline{\emph{Add Round Key}}: Viene applicata la chiave del prossimo round attraverso uno XOR.} %TODO: applicata, meglio trovare un altro verbo
\end{itemize}

\begin{figure}[H]
	\centering
	\includegraphics[width=0.5\textwidth, height=0.5\textheight, keepaspectratio]{./images/aes/flowcharts/aes_flowchart.png}
	\caption{AES Rounds Flowchart}
	\label{fig:aes_flowchart2}
\end{figure}

\index{rounds}

\textsf{\small Più rounds aggiungiamo, più sicurezza, ma questo porterebbe a un rallentamento dell'algoritmo e quindi delle performance.}
\textsf{\small Per questo serve un compromesso tra sicurezza e prestazioni.}

\index{AES} \index{rounds}

\textsf{\small Quando AES era in sviluppo venne trovata una scorciatoia attraverso 6 rounds, per evitare ciò, sono stati aggiunti 4 rounds extra, come \emph{margine di sicurezza}.} %TODO: Quando AES era in sviluppo venne trovata una scorciatoia attraverso 6 rounds, [come possiamo notare ogni bit di output di un round dipende da ogni bit dei due rounds precedenti ] per evitare questo sono stati aggiunti 4 rounds extra, come \emph{margine di sicurezza}. %TODO: magari approfondire?

\subsection{Add Round Key}

\index{add round key} \index{Galois} \index{XOR} \index{round} \index{matrice di stato}

\textsf{\small Viene aggiunto (ovvero nella matematica di Galois viene eseguito un'operazione di XOR) tra la matrice di stato (16 bytes = 4 words) e la chiave di round (anch'essa 16 bytes).}

\begin{figure}[H]
	\centering
	\includegraphics[width=0.7\textwidth, height=0.7\textheight, keepaspectratio]{./images/aes/add_round_key.png} 
	\caption{Add Round Key}
	\label{fig:add_round_key2}
\end{figure}

%\vspace{-1.62cm}

\textsf{\small Per esempio, nell'immagine sopra, BA $ \oplus $ E2 = 58 $ \Leftrightarrow 10111010 \oplus 11100010 = 1011000 $.}

\subsection{Sub Bytes}

\index{sub bytes}

\textsf{\small Ognuno dei 16 bytes della matrice di stato viene sostituito con il corrispondente byte della S-BOX.}

\begin{figure}[H]
	\centering
	\includegraphics[width=.9\textwidth, height=.9\textheight, keepaspectratio]{./images/aes/aes-s-box-no-background.png}
	\caption{S-BOX}
	\label{fig:sbox}
\end{figure}

\textsf{\small Come si evince dall'esempio nell'immagine il valore 95, prendendo la nona riga e la quinta colonna, viene sostituito con il valore 2A.}

\subsection{Shift Rows}

\index{shift rows}

\textsf{\small Rotazione della seconda, terza e quarta riga.}

\begin{figure}[H]
	\centering
	\includegraphics[width=.9\textwidth, height=.9\textheight, keepaspectratio]{./images/aes/aes-shift-rows.png}
	\caption{Shift Rows}
	\label{fig:shift_rows2}
\end{figure}

\begin{itemize}
	\item \textsf{\small Shift della seconda riga di 1 posizione a sinistra.}
	\item \textsf{\small Shift della terza riga di 2 posizioni a sinistra.}
	\item \textsf{\small Shift della quarta riga di 3 posizioni a sinistra.}
\end{itemize}

\subsection{Mix Columns}

\index{mix columns} \index{matrice dello stato}

\textsf{\small Ogni byte della matrice dello stato è combinato usando una trasformazione lineare invertibile.} %TODO: viene 

\begin{figure}[H]
	\centering
	\includegraphics[width=.9\textwidth, height=.9\textheight, keepaspectratio]{./images/aes/mixcolumns.png}
	\caption{Mix Columns}
	\label{fig:mix_columns2}
\end{figure}

\textsf{\small Le equazioni per ricavare la nuova colonna: }

\textsf{\small $ NC_0 = galois\_multiplication 1 (C_0) \oplus galois\_multiplication 2 (C_1) \oplus C_2 \oplus C_3 $}

\textsf{\small $ NC_1 = C_0 \oplus galois\_multiplication 1 (C_1) \oplus galois\_multiplication 2 (C_2) \oplus C_3 $}

\textsf{\small $ NC_2 = C_0 \oplus C_1 \oplus galois\_multiplication 1 (C_2) \oplus galois\_multiplication 2 (C_3) $ }

\textsf{\small $ NC_3 = galois\_multiplication 2 (C_0) \oplus C_1 \oplus C_2 \oplus galois\_multiplication 1 (C_3) $}

\subsection{Le modalità di AES}

\index{AES} \index{modalità}

\textsf{\small AES non può essere utilizzato così com'è, ma necessita di essere adoperato in combinazione a una modalità. } %TODO: AES non può essere usato così com'è, ma necessita di essere utilizzato in combinazione a una modalità .
\textsf{\small Una modalità è un sistema per trasformare l'efficacia di un algoritmo crittografico.} %TODO: processo/sistema/procedimento; aumentare/incrementare/trasformare/avanzare;

\index{AES} \index{ECB} \index{CBC} \index{CFB} \index{OFB} \index{CTR}

\textsf{\small Di seguito, alcune delle modalità di AES: }

\begin{itemize}
	\item \textsf{\small \textbf{ECB} (\emph{\textbf{E}lectronic \textbf{C}ode \textbf{B}ook})}
	\item \textsf{\small \textbf{CBC} (\emph{\textbf{C}ipher \textbf{B}lock \textbf{C}haining})}
	\item \textsf{\small \textbf{CFB} (\emph{\textbf{C}ipher \textbf{F}eed\textbf{B}ack)}}
	\item \textsf{\small \textbf{OFB} (\emph{\textbf{O}utput \textbf{F}eed\textbf{B}ack)}}
	\item \textsf{\small \textbf{CTR} (\emph{\textbf{C}oun\textbf{t}e\textbf{r} mode})}
	%\item \textsf{\small }
\end{itemize} 

% -------------------------------- FINE CAPITOLO --------------------------------------