content.tex 15.9 KB
Newer Older
Florent Chehab's avatar
Florent Chehab committed
1
2
\section*{Introduction}
\addcontentsline{toc}{section}{Introduction}
Florent Chehab's avatar
update  
Florent Chehab committed
3

Florent Chehab's avatar
update  
Florent Chehab committed
4
La cryptologie comporte deux branches qui se font écho et que nous allons détailler dans ce mémoire : d'une part la \textit{cryptographie} qui a pour objet le chiffrement de messages quels qu'ils soient, et d'autre part la \textit{cryptanalyse} qui s'attarde sur les capacités de déchiffrement \textit{extérieurs}\footnote{Comme expliqué par David Kahn dans \cite{kahn1996codebreakers}, le terme \guill{cryptanalyse} a été introduit par William F. Friedman en 1920 pour palier à l'ambiguïté du terme \guill{déchiffrer} qui caractérisait tout autant le déchiffrement autorisé que non autorisé. Ainsi, la \guill{cryptanalyse} caractérise un déchiffrement non-autorisé, non souhaité par l'auteur du cryptogramme.} de tels cryptogrammes. De part l'utilisation croissante des mathématiques, ces deux \textit{techniques} sont devenues des \textit{sciences} au cours du dernier siècle.
Florent Chehab's avatar
update  
Florent Chehab committed
5

Florent Chehab's avatar
Florent Chehab committed
6
\bigskip
Florent Chehab's avatar
update  
Florent Chehab committed
7
La lecture de l'ouvrage \citetitle{kahn1996codebreakers} de David Kahn \cite{kahn1996codebreakers} apporte un éclairage précis sur des faits marquants de l'Histoire en lien avec la cryptologie. Ces récits permettent une exploration de l'Histoire sous un nouvel angle et des événements prennent ainsi sens. L'histoire de la cryptologie, que nous allons tout d'abord aborder dans ce mémoire, ne sera pas de fait exhaustive : nous nous concentrerons sur les faits marquant du \siecle{XX}, car ces derniers mettent en évidence une efficacité essentielle, et décisive, de la cryptographie et de son pendant la cryptanalyse.
Florent Chehab's avatar
Florent Chehab committed
8
9

\smallskip
Florent Chehab's avatar
update  
Florent Chehab committed
10
Remarquons dès à présent que la cryptologie est un outil si puissant que sont utilisation est redouté des \textit{puissants}. Elle est ainsi restée sous la stricte supervision des gouvernements jusqu'au milieu du \siecle{XX}, se limitant principalement à des usages politique et militaire en vue d'une recherche de confidentialité de l'information. Il a fallu attendre des révolutions techniques comme les cryptosystèmes à clefs publiques et des évolutions législatives pour voir d'autres sphères s'approprier cet outil.
Florent Chehab's avatar
Florent Chehab committed
11
12

\smallskip
Florent Chehab's avatar
update  
Florent Chehab committed
13
Cette appropriation s'est faite à un moment où la technique devenait mature selon plusieurs critères que nous verrons. \todo{parler des critères quelques part} Maturité qui repose sur un changement de paradigme : la robustesse d'un cryptosystème ne repose plus alors sur sa nature secrète mais sur une complexité que nous qualifierons de \guill{calculatoire}.
Florent Chehab's avatar
Florent Chehab committed
14
15
16
17
18
19
20
21
22
23
24
25
26
27


\bigskip
Finalement, notons que ce document cherche à caractériser la course entre la cryptographie et la cryptanalyse. Par nature, la cryptanalyse étant nécessairement effectuée \textit{a posteriori} de la cryptographie, c'est cette dernière qui est toujours avance. L'objectif est donc plus précisément d'étudier cette avance, son impact et les tendances concernant sa longueur. 

\todo{penser à parler de bsafe et de la NSA qui fou son nez}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% FIN INTRO
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\clearpage
Florent Chehab's avatar
update  
Florent Chehab committed
28

Florent Chehab's avatar
update  
Florent Chehab committed
29
30
31
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Début pré-20ème
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Florent Chehab's avatar
update  
Florent Chehab committed
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
\section{La cryptologie avant le \siecle{XX}}

\subsection{Origines}

Bien que les faits les plus marquants de la cryptologie se soient déroulés au cours du dernier siècle, la cryptologie est une technique dont les premières traces remontent jusqu'à l'an 1900 avant J.C. : des hiéroglyphes inconnus ont été utilisés sur la pierre tombale du roi Khnoumhotep II \cite{redhat}. Il semble que la volonté n'ait pas été de cacher un message particulier mais plutôt de \textit{mystifier} le tombeau. Nous voyons ici que la cryptographie ne se caractérise fondamentalement que par une transformation de l'écriture. 


\begin{figure}[H]
    \centering
    \includegraphics[width=5cm]{./assets/Skytale.png} 
    \caption{Scytale de Sparte : Illustration (image \href{https://commons.wikimedia.org/wiki/File:Skytale.png}{Wikimedia -- Luringen}) }
    \label{img-scytale-sparte}
\end{figure}


Ce n'est qu'au \siecle{V} avant J.C. que le premier cryptosystème sera intentionnellement employé par les Spartes, un peuple Grecques, pour leurs communications militaires \cite{kahn1996codebreakers}. Il utilisait une scytale (Figure \ref{img-scytale-sparte}) afin d'encoder leurs messages. Il s'agit d'un procédé où des caractères \guill{nuls} \footnote{Des caractères \guill{nuls} sont des caractères qui ne sont d'aucune utilité pour la compréhension du message.} sont insérés à intervalles réguliers afin de rendre le message incompréhensible au premier lecteur venu. Une telle méthode consiste d'une certaine manière à une transposition, c'est-à-dire un procédé par lequel l'ordre des lettres du message d'origine est modifié lors du chiffrement. Il s'agit d'un procédé très utilisé en cryptographie.

David Kahn note dans son livre \cite{kahn1996codebreakers}, nous informe que Lysander, un général Sparte, a du faire face à des accusations d'insubordination suite au déchiffrement de l'un de ses messages. \todo{DOuble tranchant cryptographie}


\bigskip
\textit{Nous avons donc un premier procédé cryptographique avec le chiffrement par transposition. Il en existe de nombreux autres inventés et mis en application au fil des siècles.}

L'un des exemples les plus connus est le chiffrement par substitution employé par Jules César pour communiquer avec ses généraux. Un chiffrement par substitution fait correspondre l'alphabet employé par le texte clair\footnote{Le texte \guill{clair} est le texte original du message qui peut être lu sans déchiffrement.} à un autre alphabet afin de chiffrer le message. Ainsi, César utilisait un chiffrement par substitution qui consistait en un décalage de l'alphabet de trois caractères : un \guill{a} dans le texte en clair devient \guill{d} dans le texte chiffré. Un tel chiffrement à l'avantage d'être simple à mettre en place, mais conserve l'un des caractéristiques clefs des langues qu'est la fréquence des lettres.

\bigskip
Quoiqu'il en soit, la transposition et la substitution sont fondamentalement à la base de tous les cryptosystèmes.


\subsection{La naissance des procédés de cryptanalyse}

Florent Chehab's avatar
update  
Florent Chehab committed
63
64
\todo[inline]{Fin des méthodes intuitives, analyse de la structure du langage   }

Florent Chehab's avatar
up  
Florent Chehab committed
65
\todo[inline]{Viète : recherche de voyelle : analyse de triplets successifs.}
Florent Chehab's avatar
update  
Florent Chehab committed
66

Florent Chehab's avatar
update  
Florent Chehab committed
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
Chiffrer un message c'est lui appliquer une successions de transformations réversibles. La cryptanalyse c'est la recherche de ces transformations réversibles. Il faut attendre le \siecle{IX} pour assister au début de la rationalisation des procédés de cryptanalyse. En effet, jusqu'alors, la cryptanalyse était restée un jeu d'esprit parfois assimilé à de la sorcellerie. Se sont les arabes qui ont étaient les premiers à mathématiser les procédés de cryptanalyses. De fait, le philosophe arabe Al-Kindi (801-873), a beaucoup travaillé sur la langue est à notamment produit les premières tables de fréquences des lettres dans une langue. Il a en effet remarqué que chaque lettre était employé à une fréquence particulière dans chaque langue.

Ainsi fut inventée l'\textit{analyse des fréquences} l'un des procédés les plus emblématiques de la cryptanalyses. De fait, dans le cas de chiffrement par substitution, si le cryptogramme est suffisamment long, il suffit de calculer la fréquence des lettres dans le cryptrogramme puis de comparer ces fréquences avec des tables pour trouver la transformation inverse. Par exemple, en français et en anglais, la lettre la plus utilisée est le \guill{e}.

À cela s'ajoute d'autres procédés comme l'analyse du sens ou des mots probables. Dans un texte en anglais certains mots sont \textit{attendus} comme \guill{the} ou \textit{that}.

\bigskip
Si une mathématisation croissante de la cryptanalyse s'est opérée au fil des siècles, d'autres corps de métier restent essentiels à sa réalisation. Par exemple, les linguistes sont cruciaux pour déterminer les caractéristiques clefs des langues, que les cryptanalistes peuvent ensuite chercher.



\subsection{D'autres méthodes de chiffrement}

Pour tenter de résister à la puissance de l'analyse des fréquences, de nouveaux procédés cryptographiques plus complexes sont apparus. 

Les chiffres\footnote{Un \guill{chiffre} est un procédé de chiffrement/déchiffrement.} polyalphabétiques sont apparus au \siecle{XV} et permettent de chiffrer un message en utilisant successivement différents alphabets. Il s'agit en quelque sorte d'un chiffre par substitution variable : la lettre \guill{a} pourra être chiffrée comme un \guill{d}, puis comme un \guill{z} ou même comme un \guill{a} tout au long du cryptogramme. Les fréquences des lettres s'en retrouve troubler par ces multiples alphabets.

Plusieurs chiffres polyalphabétiques ont été proposés par Leon Battista Alberti (un architecte), Johannes Trithemius (un abbé), Giovan Batista Belaso (un clerc), Giambattista della Porta (un physicien, mathématicien, naturaliste) et Blaise de Vigenère (un diplomate).

Blaise de Vigenère (1523-1596) est un diplomate français qui inventa un chiffre particulièrement nouveau basé sur un système dit à \guill{clef privée}. Un mot-clef est choisi puis est répété autant que nécessaire afin de couvrir toute la longueur de texte clair. Par la suite, chaque lettre constituant le cryptogramme est obtenue par l'addition modulo 26 (nombre de lettre dans l'alphabet latin dans notre cas) de la lettre correspondante du texte claire et du mot clef répétée. Ainsi, à chaque caractère c'est un chiffre de César de décalage la lettre de la clef qui est employé. Les étapes de chiffrement et de déchiffrement se font rapidement à l'aide d'une \textit{table de Vigenère} (Figure \ref{img-table-vigenere}). Ce procédé à l'avantage de ne pas propopager d'erreure et est une amélioration du procédé de chiffrement de proposé par Girolamo Cardano (1501 - 1576) où le texte claire lui-même était la clef (ce qui avait le désavantage de ne pas produire un déchiffrement unique).


\begin{figure}[H]
    \centering
Florent Chehab's avatar
update  
Florent Chehab committed
91
    \includegraphics[width=8cm]{./assets/table_vigenere.png} 
Florent Chehab's avatar
update  
Florent Chehab committed
92
93
94
95
96
    \caption{Table de Vigenère (image \href{http://blogs.univ-poitiers.fr/laurentsignac/2013/10/30/dechiffrer-automatiquement-le-chiffre-de-vigenere/}{Université de Poitiers -- Laurent Signac}) }
    \label{img-table-vigenere}
\end{figure}


Florent Chehab's avatar
update  
Florent Chehab committed
97
98
Le chiffre de Vigenère est resté assez confidentiel au fil des années et à même été réinventé à plusieurs reprises \cite{guillotHistoire} : 
chiffre de Grondsfeld (\textasciitilde 1734), chiffre de Beaufort (XVIII\up{e}), la réglette de Saint-Cyr (1880 -- début XX\up{e}) ou encore le cylindre de Jefferson (XVIII\up{e} -- qui a été utilisé par les États-Unis pendant la Seconde Guerre Mondiale.).
Florent Chehab's avatar
update  
Florent Chehab committed
99

Florent Chehab's avatar
update  
Florent Chehab committed
100
Le chiffre de Vigenère a résisté à la cryptanalyse jusqu'en 1863 lorsque Friedrich Kasiski trouva un test permettant de déterminer la longueur de la clef. En effet une fois cette longueur connue il est possible de remettre à l'œuvre la technique de l'analyse des fréquences. Une autre méthode encore plus performante verra le jour au \siecle{XX} grâce aux travaux de William F. Friedman. 
Florent Chehab's avatar
update  
Florent Chehab committed
101
102
103



Florent Chehab's avatar
update  
Florent Chehab committed
104
105
\bigskip
D'autres systèmes ont également été mis en place en parallèle de ces évolutions pour contrer l'analyse des fréquences. Par exemple, via l'utilisation de codes pré-établis entre les interlocuteurs : ainsi certains mots sont remplacés par des une série de chiffre et de lettres caractéristique établie dans un dictionnaire partagé par les protagonistes. 
Florent Chehab's avatar
update  
Florent Chehab committed
106
107


Florent Chehab's avatar
update  
Florent Chehab committed
108
\subsection{Un idéal}
Florent Chehab's avatar
update  
Florent Chehab committed
109

Florent Chehab's avatar
up  
Florent Chehab committed
110
111
112
113
114
115
116
117
118
119
Nous avons pu voir qu'au fil des siècles que de nombreux chiffres ont été créés. Notons que les procédés de cryptanalyses sont jugés plus critiques que les procédés de chiffrement. En effet, si un procédé cryptograhique est connu comme \textit{cassable} alors il ne peut plus être utilisé. La cryptanalyse peut par exemple offrir un avantage concurrentiel indéniable lors des guerres ; avantage que l'on n'a pas envi de perdre.

Ainsi, l'étendue des capacités cryptanalytiques d'une entité (état, etc.) est rarement connue, il faut souvent attendre plusieurs décennies pour avoir connaissance de certains exploits (Voir \todo{enigma}).

Quoi qu'il en soit, le \textit{chiffre indéchifrable} reste un idéal dont beaucoup ont conscience. David Kahn montre dans \cite{kahn1996codebreakers} que jusqu'au \siecle{XX} (et après) les chiffres les plus sensibles, ceux des monarques, des états ou des armés, finissaient systématiquement \textit{cassés}.

\textit{NB : seul un chiffre sera réellement indéchiffrable}. \todo{vernam}

\bigskip
Conscient que les cryptanalystes talonnent souvent les cryptographes, Auguste Kerckhoff décrit en 1883 dans \citetitle{Kerckhoffs1883} \cite{Kerckhoffs1883} ce que serait un chiffre idéal :
Florent Chehab's avatar
update  
Florent Chehab committed
120
121
122
123
124
125
126
127
128
129
130

\begin{myquote}
    \begin{itemize}
        \item Le système doit être matériellement, sinon mathématiquement indéchiffrable ;
        \item Il faut qu’il n’exige pas le secret, et qu’il puisse sans inconvénient tomber entre les mains de l’ennemi ;
        \item La clef doit pouvoir en être communiquée et retenue sans le secours de notes écrites, et être changée ou modifiée au gré des correspondants ;
        \item Il faut qu’il soit applicable à la correspondance télégraphique ;
        \item Il faut qu’il soit portatif, et que son maniement ou son fonctionnement n’exige pas le concours de plusieurs personnes ;
        \item Enfin, il est nécessaire, vu les circonstances qui en commandent l’application, que le système soit d’un usage facile, ne demandant ni tension d’esprit, ni la connaissance d’une longue série de règles à observer.
    \end{itemize}
\end{myquote}
Florent Chehab's avatar
update  
Florent Chehab committed
131

Florent Chehab's avatar
up  
Florent Chehab committed
132
Le critère formulé en second est l'un des plus critiques et des plus originaux dans le paysage cryptographique de l'époque. Et ce critère ne sera jamais satisfait avant les années 1970.
Florent Chehab's avatar
update  
Florent Chehab committed
133

Florent Chehab's avatar
update  
Florent Chehab committed
134
135
136
137
138
139

\subsection{Des révolutions technologiques}

Télégraphe


Florent Chehab's avatar
update  
Florent Chehab committed
140
141
142
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Fin pré-20ème
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Florent Chehab's avatar
update  
Florent Chehab committed
143
144
145



Florent Chehab's avatar
Florent Chehab committed
146

Florent Chehab's avatar
update  
Florent Chehab committed
147
148
149
150
151
152
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Début début 20ème
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{La cryptologie jusqu'en 1947}

\subsection{La Première Guerre Mondiale}
Florent Chehab's avatar
Florent Chehab committed
153

Florent Chehab's avatar
update  
Florent Chehab committed
154
155
\subsection{La Deuxième Guerre Mondiale}

Florent Chehab's avatar
update  
Florent Chehab committed
156
157
158
Vernam


Florent Chehab's avatar
update  
Florent Chehab committed
159
\subsection{Bilan}
Florent Chehab's avatar
update  
Florent Chehab committed
160
161
Blabla sur Enigma sont on n'a pas su qu'elle avait été cryptanlysée.

Florent Chehab's avatar
update  
Florent Chehab committed
162
163
164
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Fin début 20ème
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Florent Chehab's avatar
Florent Chehab committed
165
166


Florent Chehab's avatar
update  
Florent Chehab committed
167
168
169
170
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Début suite
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{La cryptologie de 1947 à nos jours}
Florent Chehab's avatar
Florent Chehab committed
171

Florent Chehab's avatar
update  
Florent Chehab committed
172
\subsection{La révolution de la technologie de l'information}
Florent Chehab's avatar
Florent Chehab committed
173

Florent Chehab's avatar
update  
Florent Chehab committed
174
\subsection{La révolution des cryptosystèmes à clefs publiques}
Florent Chehab's avatar
Florent Chehab committed
175

Florent Chehab's avatar
update  
Florent Chehab committed
176
\subsection{La standardisation des cryptosystèmes}
Florent Chehab's avatar
Florent Chehab committed
177

Florent Chehab's avatar
update  
Florent Chehab committed
178
179
180
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Fin suite
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Florent Chehab's avatar
Florent Chehab committed
181

Florent Chehab's avatar
update  
Florent Chehab committed
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Début Prédiction
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Prédictions}


\clearpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Fin Conclu
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\section*{Conclusion}
\addcontentsline{toc}{section}{Conclusion}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% FIN conclu
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{./assets/fig_shannon_1.pdf} 
    \caption{Schematic of a general secrecy system, d'après \cite{shannon1949communication}}
\end{figure}
Florent Chehab's avatar
Florent Chehab committed
207
208
209
210




Florent Chehab's avatar
update  
Florent Chehab committed
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{./assets/RSA_fig1.png} 
    \caption{Flow of information
    in conventional cryptographic
    system., d'après \cite{newDirections}}
\end{figure}

\begin{figure}[H]
    \centering
    \includegraphics[width=\textwidth]{./assets/RSA_fig2.png} 
    \caption{Flow of information
    in public key system., d'après \cite{newDirections}}
\end{figure}




\cite{kahn1996codebreakers}
\cite{guillotHistoire}
\cite{redhat}
\cite{newDirections}
\cite{shor1997polynomialtimealgorithmsfor}
\cite{Kerckhoffs1883}