\( %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Mes commandes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \newcommand{\multirows}[3]{\multirow{#1}{#2}{$#3$}}%pour rester en mode math \renewcommand{\arraystretch}{1.3}%pour augmenter la taille des case \newcommand{\point}[1]{\marginnote{\small\vspace*{-1em} #1}}%pour indiquer les points ou le temps \newcommand{\dpl}[1]{\displaystyle{#1}}%megamode \newcommand{\A}{\mathscr{A}} \newcommand{\LN}{\mathscr{N}} \newcommand{\LL}{\mathscr{L}} \newcommand{\K}{\mathbb{K}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\R}{\mathbb{R}} \newcommand{\C}{\mathbb{C}} \newcommand{\M}{\mathcal{M}} \newcommand{\D}{\mathbb{D}} \newcommand{\E}{\mathcal{E}} \renewcommand{\P}{\mathcal{P}} \newcommand{\G}{\mathcal{G}} \newcommand{\Kk}{\mathcal{K}} \newcommand{\Cc}{\mathcal{C}} \newcommand{\Zz}{\mathcal{Z}} \newcommand{\Ss}{\mathcal{S}} \newcommand{\B}{\mathbb{B}} \newcommand{\inde}{\bot\!\!\!\bot} \newcommand{\Proba}{\mathbb{P}} \newcommand{\Esp}[1]{\dpl{\mathbb{E}\left(#1\right)}} \newcommand{\Var}[1]{\dpl{\mathbb{V}\left(#1\right)}} \newcommand{\Cov}[1]{\dpl{Cov\left(#1\right)}} \newcommand{\base}{\mathcal{B}} \newcommand{\Som}{\textbf{Som}} \newcommand{\Chain}{\textbf{Chain}} \newcommand{\Ar}{\textbf{Ar}} \newcommand{\Arc}{\textbf{Arc}} \newcommand{\Min}{\text{Min}} \newcommand{\Max}{\text{Max}} \newcommand{\Ker}{\text{Ker}} \renewcommand{\Im}{\text{Im}} \newcommand{\Sup}{\text{Sup}} \newcommand{\Inf}{\text{Inf}} \renewcommand{\det}{\texttt{det}} \newcommand{\GL}{\text{GL}} \newcommand{\crossmark}{\text{\ding{55}}} \renewcommand{\checkmark}{\text{\ding{51}}} \newcommand{\Card}{\sharp} \newcommand{\Surligne}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\SurligneMM}[2]{\text{\colorbox{#1}{ #2 }}} \newcommand{\norm}[1]{\left\lVert#1\right\rVert} \renewcommand{\lim}[1]{\underset{#1}{lim}\,} \newcommand{\nonor}[1]{\left|#1\right|} \newcommand{\Un}{1\!\!1} \newcommand{\sepon}{\setlength{\columnseprule}{0.5pt}} \newcommand{\sepoff}{\setlength{\columnseprule}{0pt}} \newcommand{\flux}{Flux} \newcommand{\Cpp}{\texttt{C++\ }} \newcommand{\Python}{\texttt{Python\ }} %\newcommand{\comb}[2]{\begin{pmatrix} #1\\ #2\end{pmatrix}} \newcommand{\comb}[2]{C_{#1}^{#2}} \newcommand{\arrang}[2]{A_{#1}^{#2}} \newcommand{\supp}[1]{Supp\left(#1\right)} \newcommand{\BB}{\mathcal{B}} \newcommand{\arc}[1]{\overset{\rotatebox{90}{)}}{#1}} \newcommand{\modpi}{\equiv_{2\pi}} \renewcommand{\Re}{Re} \renewcommand{\Im}{Im} \renewcommand{\bar}[1]{\overline{#1}} \newcommand{\mat}{\mathcal{M}} \newcommand{\und}[1]{{\mathbf{\color{red}\underline{#1}}}} \newcommand{\rdots}{\text{\reflectbox{$\ddots$}}} \newcommand{\Compa}{Compa} \newcommand{\dint}{\dpl{\int}} \newcommand{\intEFF}[2]{\left[\!\left[#1 ; #2\right]\!\right]} \newcommand{\intEFO}[2]{\left[\!\left[#1 ; #2\right[\!\right[} \newcommand{\intEOF}[2]{\left]\!\left]#1 ; #2\right]\!\right]} \newcommand{\intEOO}[2]{\left]\!\left]#1 ; #2\right[\!\right[} \newcommand{\ou}{\vee} \newcommand{\et}{\wedge} \newcommand{\non}{\neg} \newcommand{\implique}{\Rightarrow} \newcommand{\equivalent}{\Leftrightarrow} \newcommand{\Ab}{\overline{A}} \newcommand{\Bb}{\overline{B}} \newcommand{\Cb}{\overline{C}} \newcommand{\Cl}{\texttt{Cl}} \newcommand{\ab}{\overline{a}} \newcommand{\bb}{\overline{b}} \newcommand{\cb}{\overline{c}} \newcommand{\Rel}{\mathcal{R}} \newcommand{\superepsilon}{\varepsilon\!\!\varepsilon} \newcommand{\supere}{e\!\!e} \makeatletter \newenvironment{console}{\noindent\color{white}\begin{lrbox}{\@tempboxa}\begin{minipage}{\columnwidth} \ttfamily \bfseries\vspace*{0.5cm}} {\vspace*{0.5cm}\end{minipage}\end{lrbox}\colorbox{black}{\usebox{\@tempboxa}} } \makeatother \def\ie{\textit{i.e. }} \def\cf{\textit{c.f. }} \def\vide{ { $ {\text{ }} $ } } %Commande pour les vecteurs \newcommand{\grad}{\overrightarrow{Grad}} \newcommand{\Vv}{\overrightarrow{v}} \newcommand{\Vu}{\overrightarrow{u}} \newcommand{\Vw}{\overrightarrow{w}} \newcommand{\Vup}{\overrightarrow{u'}} \newcommand{\Zero}{\overrightarrow{0}} \newcommand{\Vx}{\overrightarrow{x}} \newcommand{\Vy}{\overrightarrow{y}} \newcommand{\Vz}{\overrightarrow{z}} \newcommand{\Vt}{\overrightarrow{t}} \newcommand{\Va}{\overrightarrow{a}} \newcommand{\Vb}{\overrightarrow{b}} \newcommand{\Vc}{\overrightarrow{c}} \newcommand{\Vd}{\overrightarrow{d}} \newcommand{\Ve}[1]{\overrightarrow{e_{#1}}} \newcommand{\Vf}[1]{\overrightarrow{f_{#1}}} \newcommand{\Vn}{\overrightarrow{0}} \newcommand{\Mat}{Mat} \newcommand{\Pass}{Pass} \newcommand{\mkF}{\mathfrak{F}} \renewcommand{\sp}{Sp} \newcommand{\Co}{Co} \newcommand{\vect}[1]{\texttt{Vect}\dpl{\left( #1\right)}} \newcommand{\prodscal}[2]{\dpl{\left\langle #1\left|\vphantom{#1 #2}\right. #2\right\rangle}} \newcommand{\trans}[1]{{\vphantom{#1}}^{t}{#1}} \newcommand{\ortho}[1]{{#1}^{\bot}} \newcommand{\oplusbot}{\overset{\bot}{\oplus}} \SelectTips{cm}{12}%Change le bout des flèches dans un xymatrix \newcommand{\pourDES}[8]{ \begin{itemize} \item Pour la ligne : le premier et dernier caractère forment $#1#2$ soit $#4$ en base 10. \item Pour la colonne : les autres caractères du bloc forment $#3$ soit $#5$ en base 10. \item A l'intersection de la ligne $#4+1$ et de la colonne $#5+1$ de $S_{#8}$ se trouve l'entier $#6$ qui, codé sur $4$ bits, est \textbf{\texttt{$#7$}}. \end{itemize} } \)

Avant de commencer

Introduction

La cryptographie est une science et un peu plus. Quelque part entre l'art et la guerre. "Art" parce que cette science use et abuse de technique magnifique (mathématiques). "Guerre" parce tout message est attaqué, torturé, malmené pour révéler ses secrets. %Pourquoi la cryptographie ? %Plaçons-nous dans un contexte familier : internet. A l'ère du numérique la quasi-totalité des informations circulent sur le web et pour la majeure partie d'entre elle en claire (l'adresse IP, les mails, l'historique des pages web visitées etc...) et il n'est pas nécessaire d'être un as de l'informatique pour intercepter ces données (même sans logiciel espion) ! Télécharger des films, séries ou musiques est à la porté de tous. Il est devenu difficile de "posséder" numériquement quelque chose. Beaucoup de données sont interceptables. %L'idée très vite apparu, bien avant l'ère numérique d'ailleurs, est non pas de cacher les informations, mais de les rendre bien visible aux yeux de tous... en les brouillant !

Définition


La stéganographie est l'art qui vise à dissimuler l'existence d'un message.

Remarque

En 484 av. J.-C., Xerxès Ier, roi des Perses, décide de préparer une armée gigantesque pour envahir la Grèce. Quatre ans plus tard, lorsqu'il lance l'offensive, les Grecs sont depuis longtemps au courant de ses intentions. C'est que Démarate, ancien roi de Sparte réfugié auprès de Xerxès, a appris l'existence de ce projet et décide de transmettre l'information à Sparte :
il prit une tablette double, en gratta la cire, puis écrivit sur le bois même les projets de Xerxès ; ensuite il recouvrit de cire son message : ainsi le porteur d'une tablette vierge ne risquait pas d'ennuis.

Remarque

Histiée incite son gendre Aristagoras, gouverneur de Milet, à se révolter contre son roi, Darius, et pour ce faire,
il fit raser la tête de son esclave le plus fidèle, lui tatoua son message sur le crâne et attendit que les cheveux eussent repoussé ; quand la chevelure fut redevenue normale, il fit partir l'esclave pour Milet.
Aujourd'hui encore on peut utiliser la stéganographie pour transmettre une information en modifiant subtilement les pixels d'une image par exemple. Néanmoins la stéganographie à ses limites et il est vite apparut nécessaire de dissimuler l'information tout en la rendant visible ! C'est la cryptographie.

Définition


La cryptographie cryptographie est la science qui vise à protéger l'information en la rendant illisible à toute personne qui n'a pas les moyens de la déchiffrer. Le message chiffré est appelé un cryptogramme.

Définition


La cryptanalyse est une science qui consiste à tenter de déchiffrer un message ayant été chiffré. Le processus par lequel on tente de comprendre un message chiffré est appelé une attaque.

Définition


La cryptologie englobe la cryptographie et la cryptanalyse.
Dans ce cours, la cryptologie est "une excuse pour faire des mathématiques". A chaque chapitre on introduit une méthode de chiffrement qui nécessite pour son indentation, sa compréhension et le déploiement de techniques d'attaques, l'introduction d'outils mathématiques. Pour être tout à fait rigoureux il faudrait d'abord définir les outils mathématiques offrant le meilleur formalisation des cryptosystème. Nous pensons que nous gagnerons en clarté en se permettant quelques liberté avec la "Rigueur".

Quelques outils

Définition


\( \bullet\)
Le chiffrement ou cryptage est le processus de transformation d'un message clair de façon à le rendre incompréhensible.

\( \bullet\)
Le déchiffrement ou décryptage est le processus de reconstitution du message clair à partir du message chiffré.
Dans la pratique les processus de transformation et de reconstitution sont paramétrés par des fonctions elles-mêmes paramétrées par des clefs.

Définition


Un système cryptographique ou cryptosystème est constitué de
  1. un espace de clefs \( \mathcal{K}\) ,
  2. une fonction de chiffrement et une fonction de déchiffrement paramétrées par les éléments de \( \mathcal{K}\) .
Ces données devant satisfaire la propriété de déchiffrement :
Pour \( k\in \mathcal{K}\) , notons \( C_k\) la fonction de chiffrement, \( D_k\) la fonction de déchiffrement (paramétrées par \( k\) ) et \( M\) un message claire \[\forall k\in\mathcal{K},\ \forall M,\ D_{k}\Big(C_k(M)\Big)=M\]

Remarque

La propriété de déchiffrement se traduit par le fait que pour chaque "manière" de crypter il existe un moyen de décrypter pour retrouver le message original.
On prendra garde au vocabulaire. Nous parlerons majoritairement de (dé)cryptage ou (dé)chiffrement et en aucun cas de (dé)codage. Pour faire simple, le codage est un dictionnaire d'échange : les lettres du message claire sont transformés en d'autre symbole comme ceux que l'on trouve dans les magazines pour enfants
Img/codage.jpg
Puisque nous voulons "faire des opérations dans le texte" nous utiliserons notre langage préféré : le nombre. Dans tout ce cours notre codage, c'est à dire notre langage de préférence, sera \[ \begin{array}{|*{13}{c|}} \hline A&B&C&D&E&F&G&H&I&J&K&L&M\\\hline 00&01&02&03&04&05&06&07&08&09&10&11&12\\\hline \end{array} \] \[ \begin{array}{|*{13}{c|}} \hline N&O&P&Q&R&S&T&U&V&W&X&Y&Z\\\hline 13&14&15&16&17&18&19&20&21&22&23&24&25\\\hline \end{array} \]