\chapterimage{martine_utf8}
\chaptertext{}

\chapter{Théorie de l'information}





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\modeexercice
%\section{Tables utiles}
Début des tables de l'Unicode:
\begin{multicols}{2}
%\begin{figure}
\begin{center}
  \includegraphics[height=13.5cm]{unicode1}

 \includegraphics[height=13.5cm]{unicode2}
\end{center}
%\end{figure}
\end{multicols}

Fonctionnement de l'UTF-8:


\begin{center}
    \begin{tabular}[!h]{|l|l|l|l|l|l|}
      \hline
De& à&1\up{er} octet& 2\up{ème} octet& 3\up{ème} octet& 4\up{ème} octet\\
\hline
$0x0$ & $0x7F$&{\color{black!70} $0$}$b_7b_6b_5b_4b_3b_2b_1$&/&/&/\\
$0x80$                         &                         $0x7FF$&{\color{black!70}
  $110$}$b_{11}b_{10}b_9b_8b_7$&{\color{black!70}$10$}$b_6b_5b_4b_3b_2b_1$&/&/\\
$0x800$                        &                        $0xFFFF$&{\color{black!70}
  $1110$}$b_{16}b_{15}b_{14}b_{13}$&{\color{black!70}$10$}$b_{12}b_{11}b_{10}b_9b_8b_7$&{\color{black!70}$10$}$b_6b_5b_4b_3b_2b_1$&/\\
$0x10000$                      &                      $0x10FFFF$&{\color{black!70}
  $11110$}$b_{21}b_{20}b_{19}$&{\color{black!70} $10$}$b_{18}b_{17}b_{16}b_{15}b_{14}b_{13}$&{\color{black!70}$10$}$b_{12}b_{11}b_{10}b_9b_8b_7$&{\color{black!70}$10$}$b_6b_5b_4b_3b_2b_1$\\
\hline
\end{tabular}
\end{center}




%\section{RECHERCHES}



\begin{exercice}[Décodage de texte brut]
Vous  allez travailler  sur  le  fichier \verb+texte.txt+  à  placer dans  votre
répertoire courant.
Il s'agit d'un fichier rempli de 0 et de 1 encodé en ISO-8859-1.
Commencez par décoder à la main le début du texte:

\begin{verbatim}
01000001011101000111010001100101011011100111010001101001011011110110111000100000

00100001001000000100010101101110001000000110011001100001011010010111010000100000

01100011011001010010000001101101011001010111001101110011011000010110011101100101

\end{verbatim}


Il va  s'agit ensuite de  créer un programme Python  qui va déchiffrer  ce texte
automatiquement.

Vous importerez  le message brut  puis le tranformerez  en une longue  chaîne de
caractères avec:

\begin{pythoncode}
brut = open('texte.txt')
zero_un = brut.read()  
\end{pythoncode}

Il s'agira  ensuite de  lire cette chaîne  par paquets de  8 et  de transformer
chaque paquet  de 8  en caractère  ISO-8859-1 correspondant  grâce à  la fonction
\mintinline[fontsize=\small,fontfamily=txtt]{python}{chr}.
\begin{pythoncode}
In [29]: chr(97)
Out[29]: 'a'
\end{pythoncode}
Vous pourrez construire une fonction 
\mintinline[fontsize=\small,fontfamily=txtt]{python}{octet2int}: 
\begin{pythoncode}
In [27]: octet2int('10001100')
Out[27]: 140
\end{pythoncode}
Décodez  alors \mintinline[fontsize=\small,fontfamily=txtt]{python}{zero_un}  et
ajustez éventuellement votre programme ;-)
Créez ensuite des fonctions qui permettront d'effectuer la démarche inverse.
\end{exercice}








\begin{exercice}[Littérature et chaînes de Markov]
\begin{figure}[ht]
  \centering
  \includegraphics[height=6cm]{markov}
  \caption{\foreignlanguage{russian}{Андрей Андреевич  МАРКОВ}
(1856 -
1922)}
\end{figure}

Grand mathématicien  russe, initiateur des probabilités modernes,
grand amateur de poésie, MARKOV n'hésita pourtant pas à s'impliquer dans la
tumultueuse  histoire  de  son   pays.  Il  n'eut  pas  peur  d'affirmer
publiquement son  anti-tsarisme et fut  renvoyé de l'Université.  Il fut
réhabilité après la Révolution.

Nous allons illustrer de manière élémentaire quelques résultats de ses travaux
sur   les   processus   aléatoires  (ou   stochastiques),   c'est-à-dire
l'évolution   dans   le   temps   d'une   variable   aléatoire   appelée
\textit{chaînes  de  \textsc{Markov}} dont  les  applications sont  très
nombreuses, notamment en informatique  (reconnaissance de la langue d'un
texte,  techniques  de  compression,  l'algorithme PageRank  de  Google,
files d'attente, bioinformatique,...)

D'un point de vue plus probabiliste, les chaînes de \textsc{Markov} permettent
d'étudier des variables  aléatoires non indépendantes ce qui est  très délicat à
faire habituellement.

La particularité  des chaînes de \textsc{Markov} est  de représenter des
processus où la probabilité permettant de passer à un instant donné d'un
état présent à un état futur
ne dépend du passé qu'à travers le présent soit: \og la probabilité du
futur  sachant présent  et passé  est égale  à la  probabilité  du futur
sachant le présent\fg{}.

On peut  produire des  textes (ou  de la musique...)  aléatoirement à  l'aide de
chaînes de Markov.  Par exemple, connaissant un couple  de lettres consécutives,
on peut  calculer la probabilité qu'il  soit suivi par telle  lettre en faisant
un calcul de fréquence sur un très grand texte.



Nous allon scréer  un \textit{dictionnaire} dont les clés  seront des $n$-uplets
de longueur arbitraire et les valeurs la liste des lettres (ou des mots) qui suivent ce
$n$-uplet dans le texte.

Soit par exemple le texte:

\begin{quote}
  {\itshape
Maman les petits bâteaux qui vont sur l'eau ont-ils des jambes?
}
\end{quote}
 
Nous allons créer un dictionnaire:

\begin{pythoncode}
{
('Maman', 'les') : ['petits'],
('les', 'petts') : ['bâteaux'],
('petits', 'bâteaux') : ['qui'],
...
}
\end{pythoncode}


ou bien:

\begin{pythoncode}
{
('M', 'a') : ['m'],
('a', 'm') : ['a', 'b'],
...
}
\end{pythoncode}


Ensuite, nous allons partir d'un  $n$-uplet choisi aléatoirement puis construire
un texte en prenant un nouveau caractère  (mot) dans la liste des successeurs de
la clé puis prendre comme nouvelle clé  la clé précédente sans son premier terme
et avec comme nouveau dernier terme le caractère (mot) choisi aléatoirement.

Par exemple:  je tire  $c_1c_2$. Dans  les successeurs de  la paire  $c_1c_2$ je
choisis aléatoirement  $c_3$. Je mets  $c_1$ dans ma  châine et je  prends comme
nouvelle clé $c_2c_3$, etc.

Nous auront besoin de méthodes sur les chaînes de caractères:

\begin{pythoncode}
In [1]: ??str.join
Docstring:
S.join(iterable) -> str

Return a string which is the concatenation of the strings in the
iterable.  The separator between elements is S.  

In [2]: ??str.split
Docstring:
S.split(sep=None, maxsplit=-1) -> list of strings

Return a list of the words in S, using sep as the
delimiter string.  If maxsplit is given, at most maxsplit
splits are done. If sep is not specified or is None, any
whitespace string is a separator and empty strings are
removed from the result.
\end{pythoncode}


Par exemple:

\begin{pythoncode}
In [9]: ''.join(['B','o','n','j','o','u','r'])
Out[9]: 'Bonjour'

In [10]: '/'.join(['B','o','n','j','o','u','r'])
Out[10]: 'B/o/n/j/o/u/r'
  
In [11]: "Bonjour le monde".split(' ')
Out[11]: ['Bonjour', 'le', 'monde']

In [12]: "Bonjour le monde".split('o')
Out[12]: ['B', 'nj', 'ur le m', 'nde']
\end{pythoncode}

On              utilisera             aussi              la             fonction
\mintinline[fontsize=\small,fontfamily=txtt]{python}{open}  qui permet  d'ouvrir
un fichier sous forme d'une liste de caractères. 

On              utilisera             enfin              la             fonction
\mintinline[fontsize=\small,fontfamily=txtt]{python}{numpy.randint(a)}       qui
renvoie un nombre entier naturel strcitement inférieur à $a$.

Vous pourrez créer:

\begin{itemize}
\item une  fonction \mintinline{python}{n_uplets(liste,  long_t)} qui  revoie la
  liste de tous les $n$-uplets extraits de la liste.
\item une fonction \mintinline{python}{repertoire(liste, long_t)} qui renvoie le
  dictionnaire \mintinline{python}{n-uplet : liste des suivants}.
\item  une   fonction  \mintinline{pyton}{choisit_élément(liste)}   qui  choisit
  aléatoirement selon une loi uniforme un élément d'une liste.
\item une fonction \mintinline{python}{clés(dico)} qui renvoie la liste des clés
  d'un dictionnaire.
\item enfin la fonction principale 
\mintinline{python}{genere_Markov(fichier, atomes,  long_t, nb_mots =  100)} qui
renvoie  le  texte généré,  sachant  que  \mintinline{python}{atomes} permet  de
choisir les lettres ou les mots comme unité de génération.
\end{itemize}

Vous récupèrerez  les fichiers \mintinline{python}{txt} pour  travailler en vraie
grandeur.

\vfill

\eject

\begin{pythoncode}
In [27]: genere_Markov('verne.txt', mots, 2)
Londres dans
plusieurs constructions du soir, le témoignaient de la dent du Jardin des ovules,
des volutes, des rhomboldes, des fourmis qui peuplent notre
planète, ou sept
mille cinq cent quarante brasses. Sous cette portion de Conseil.
 -- Remonter à demi pourris, des eaux ; elles battent ?
 -- Et le même pas été éteint, et avec lui :
 « Ami Ned, il marchait à
une chimère, mais la venaison, dont il
ne restait de neuf cents mètres.
 « Et c'est un trente-millième pour un mouvement à voix ne nous
écoute pas cela seul bruit des légumineuses et d'une ouverture qui s'est produit. J'ai beaucoup
hésité.

In [29]: genere_Markov('verne.txt', lettres, 4, 300)
Polypiers les battirière les jourserver, qu'il vivant libergé d'un sur déplat du
capitait le sait sa côtel Grahambé, formaladessaillo, frois, qui peut-être deux. Je n'en qu'il de capide
réservi.
 « Calés de coché sont ce divisir
soures sent. Malaité.
 -- Aloré, foi, retent, je vites noire cachera
\end{pythoncode}








\end{exercice}





\begin{exercice}[Cryptographie: chiffrement par blocs]


\subsubsection{Cryptosystème}

Commençons par une définition:
\setindent{\indentationcours}
\begin{definition}[Cryptosystème (ou système de chiffrement ou chiffre)]
Un  cryptosystème est  un quintuplet
$\langle \PR,\CR,\KR,\ER,\DR\rangle $ tel que:
\begin{itemize}
\item L'ensemble $\PR$ est l'espace des messages en clair (\textit{plaintext} en
      anglais). En général, c'est l'ensemble des chaînes de bits.
\item L'ensemble $\CR$ est l'espace des messages chiffrés (\textit{cyphertext} en
      anglais). En général, c'est aussi l'ensemble des chaînes de bits.
\item L'ensemble $\KR$ est l'espace des clés (\textit{key});
\item $\ER$  est la  famille des fonctions  de chiffrement, qui  vont de
      $\PR$ dans $\CR$;
\item $\DR$  est la  famille des fonctions  de déchiffrement, qui  vont de
      $\CR$ dans $\PR$;
\end{itemize}

Pour chaque élément  $e\in\KR$, il existe un élément  $d\in\KR$ tel que,
pour  tout  message  clair  $m$  de  $\PR$,  il  existe  $D_d\in\DR$  et
$E_e\in\ER$  telles que  $D_d(E_e(m))=m$. Les  fonctions $D_d$  et $E_e$
sont des applications injectives. Il est entendu que $d$ doit
rester secret...

\end{definition}
\setindent{0cm}

\begin{enumerate}
\item On travaille sur des  mots formés des 26 minuscules non accentuées
      de notre alphabet latin et d'une espace qui sont modélisés par les
      entiers de $E=\bigl\{0,1,2,...,26\bigr\}$.

Dans ce  contexte, on  remplace une \og  lettre\fg{} $x$ par  $kx [27]$ avec $k\in E$. Définit-on ainsi un cryptosystème?
\item  Un  cryptosystème  est   un  \textit{chiffrement  par  blocs}  si
      $\PR=\CR=\{0,1\}^n$.   Est-ce  que  le  chiffrement  ROT-13  est  un
      chiffrement par blocs?

\item Pourquoi  les fonctions de chiffrement d'un  chiffrement par blocs
      sont des permutations?
\end{enumerate}

Depuis 2001, le  chiffrement par blocs \og officiel  \fg{} est l'AES qui
opère par blocs de 128 bits.  Une présentation de l'algorithme de chiffrement associé,
\textsc{Rijndael}, et de sa résistance aux attaques est présentée ici :

\href{http://www.cryptis.fr/assets/files/Canteaut-25ans-Cryptis.pdf}{http://www.cryptis.fr/assets/files/Canteaut-25ans-Cryptis.pdf}.


\subsubsection{Classe de permutations}

Nous allons avoir besoin de travailler avec des permutations et plus précisément
dans le groupe $(\mathfrak{S}_n,\circ)$.

Une permutation sera définie par la liste de ses images.
Par exemple, on veut définir 
$$
p = \begin{pmatrix}
  0&1&2&3&4\\
2&0&1&4&3
\end{pmatrix}
$$

par

\begin{pythoncode}
p = Perm([2, 0, 1, 4, 3])
\end{pythoncode}

Pour cela nous  utiliserons la classe suivante dont on  donne un squelette qu'il
va falloir compléter:


\begin{pythoncode}
class Perm :
    """ Groupe des permutations, la loi étant la composition """

    def __init__(self, images = None) :
        """ Permutation définie par son ensemble image """
        self.images = images

    def __repr__(self) :
        return (' ').join( [str(x) for x in self.images] )

    def __add__(self, other) :
        """ fabrique la composée self o other """ 
        return Perm( ??????? )

    def __neg__(self) :
        """ réciproque de self """
        im = self.images
        n = len(im)
        return Perm( ????? )

    def circulaire(self, rangs) :
        """ permutation circulaire de rangs rangs """
        im = self.images
        n = len(im)
        return Perm( ?????? )

    def permute(self,xs) :
        """ si xs = [xs[0], xs[1], xs[2],...], p.permute(xs) = [xs[p(0)], xs[p(1)], xs[p(2)],...] """
        return ??????
\end{pythoncode}


On aura peut-être besoin de créer une  fonction qui trie les couples de nombres,
une fonction qui crée la liste  de couples $[(x_0,y_0), (x_1,y_1),...]$ à partir
de $[x_0,x_1,...]$ et de $[y_0,y_1,...]$.



\subsubsection{Mode ECB}

  ECB: \textit{Electronic  CodeBook}. C'est le plus  simple...et le plus
  vulnérable des modes de chiffrement par blocs.


Voyons sur  un exemple.  On considère une  chaîne de bits  quelconque que
l'on découpe en  blocs de longueur fixe, par exemple  7 (plus pratique
pour ensuite utiliser  l'ASCII: pourquoi?). On rajoute
éventuellement des zéros en bout de chaîne.

Considérons $m=1001001111011$. On rajoute un 0 en bout de chaîne:

$$m'=1001001\ 1110110 =\beta_1\beta_2$$

avec $\beta_1=1001001$ et $\beta_2=1110110$.


On choisit une clé de chiffrement dans 
$\mathfrak{S}_7$ car $\KR= \mathfrak{S}_7$:
$\pi=
\begin{pmatrix}
  2&0&3&1&5&4&6
\end{pmatrix}
$

Alors $E_{\pi}(\beta_1)=0110001$ et $E_{\pi}(\beta_2)=1101110$.

\tikzstyle{vertex}=[draw,fill=black!15,circle,minimum size=20pt,inner sep=0pt]
\tikzstyle{encrypt}=[draw,fill=black!15,rectangle,minimum        size=20pt,inner
sep=0pt]
\begin{center}
\begin{tikzpicture}
    \newcommand{\n}{2}
    \foreach \nr in {0, ..., \n}{
        \node (m\nr) at (0,{(\n-\nr)*2}) {$m_\nr$};
        \node (c\nr) at (4,{(\n-\nr)*2}) {$c_\nr$};
        \node (E\nr)[encrypt] at (2,{(\n-\nr)*2}) {$E$};
        \node (k\nr) at (2,{(\n-\nr)*2+1}) {$k$};

        \draw[->,very thick] (m\nr) -- (E\nr);
        \draw[->,very thick] (k\nr) -- (E\nr);
        \draw[->,very thick] (E\nr) -- (c\nr);
    }

   \node (mx) at (0,-1) {$\vdots$};
   \node (Ex) at (2,-1) {$\vdots$};
   \node (cx) at (4,-1) {$\vdots$};
\end{tikzpicture}
\end{center}

\begin{enumerate}

\item Chiffrez  \og maman\fg{} avec ce cryptosystème  en transformant la
      chaine de lettres en chaînes de bits constituée des codes ASCII de
      ses   caractères.   Le   tableau   ASCII  standard   est-il satisfaisant? Comment y remédier?
\item  Quelle est  la  fonction de  déchiffrement  associée à  l'exemple
      précédent?
\item Déchiffrez $10110111001111$ sachant que la clé de
      chiffrement est $k=
  \begin{pmatrix}
    1&2&0&6&5&4&3
  \end{pmatrix}
$
\item Déchiffrez \og papa\fg{} sachant que c'est le cryptosystème du début qui a été employé.

\item Que se passe-t-il si un bloc chiffré est mal transmis ou perdu?

\item Quelle est la principale faiblesse du mode ECB?


\item Il reste à programmer tout ça...

On aura d'abord besoin de la fonction 
\mintinline[fontsize=\small,fontfamily=txtt]{python}{reduce} de  la bibliothèque
\mintinline[fontsize=\small,fontfamily=txtt]{python}{functools}
qui est en gros définie comme suit:

\begin{pythoncode}
def reduit(loi, xs, neutre) :
    panier = neutre
    for x in xs :
        panier = loi(panier, x)
    return panier
\end{pythoncode}

Complétez alors le squelette suivant:

\begin{pythoncode}
def decoupe_en_blocs(n, bs) :
    """découpe une liste en liste de blocs de longueur n"""
    ????????????

def ecb(cle, bs) :
    """renvoie la liste des permutations des blocs contenus dans une liste"""
    ????

def string2bin(s, n) :
    """ transforme un caractère en sa représentation sur n bits sous forme de liste""" 
    ?????

def bin2string(bs) :
    """ transforme une liste de bits en l'entier décimal correspondant"""
    ????

def cats(xs) :
    """concatène une liste de listes ou de chaînes"""
    ????

def code_bloc_string(code_bloc, cle, n_bits, chaine) :
    """applique un chiffrement par bloc sur une chaîne en donnant le nom du
       chiffrement, sa clé et le nb de bits sur lequel les caractères sont codés """
    ?????
\end{pythoncode}


Par exemple:

\begin{pythoncode}
In [5]: bs = [1,0,0,1,0,0,1,1,1,1,0,1,1]

In [6]: decoupe_en_blocs(7, bs)
Out[8]: [[1, 0, 0, 1, 0, 0, 1], [1, 1, 1, 0, 1, 1, 0]]

In [9]: ecb(Perm([2,0,3,1,5,4,6]), bs)
Out[9]: [[0, 1, 1, 0, 0, 0, 1], [1, 1, 0, 1, 1, 1, 0]]

In [10]: string2bin('(', 7)
Out[12]: [0, 1, 0, 1, 0, 0, 0]

In [13]: bin2string([0, 1, 0, 1, 0, 0, 0])
Out[20]: 40

In [21]: cats(['a', 'u', ' ', 's', 'e', 'c', 'o', 'u', 'r', 's'])
Out[21]: 'au secours'

In [22]: cats([[0,1], [2,3]])
Out[22]: [0, 1, 2, 3]

In [23]: code_bloc_string(ecb, Perm([2,0,3,1,5,4,6]), 7, 'Help')
Out[23]: '0+:h'  
\end{pythoncode}


\end{enumerate}







\subsubsection{Mode CBC}

  CBC:  \textit{Cipher-Block  Chaining}.  Ce  mode  a  été  inventé  par
  \textsc{Ibm} en  1976. Pour  éviter la faiblesse  de l'ECB,  les blocs
  sont maintenant chaînés: chaque bloc en clair est \og XORé\fg{} ou \og
  OUEXé\fg{} avec le bloc crypté précédent avant d'être crypté lui-même.

Pour le premier bloc, on utilise un \textit{vecteur d'initialisation} public.
Avec   les  notations   habituelles,  on   a   donc  $$c_i=E_k(m_i\oplus
c_{i-1}),\quad c_0 = \ve{v_0}$$

\begin{center}
% thanks to http://tex.stackexchange.com/a/75838/5645
\tikzset{XOR/.style={fill=black!15,draw,minimum size=13pt,circle,append after command={
[shorten >=\pgflinewidth, shorten <=\pgflinewidth,]
(\tikzlastnode.north) edge (\tikzlastnode.south)
(\tikzlastnode.east) edge (\tikzlastnode.west)
}
}
}
\tikzstyle{encrypt}=[draw,fill=black!15,rectangle,minimum size=20pt,inner sep=0pt]
\begin{tikzpicture}
\newcommand{\n}{3}
\foreach \nr in {1, ..., \n}{
\node (M\nr) at (0,{(\n-\nr)*2}) {$m_\nr$};
\node (x\nr)[XOR] at (2,{(\n-\nr)*2}) {};
\node (E\nr)[encrypt] at (4,{(\n-\nr)*2}) {$E$};
\node (C\nr) at (6,{(\n-\nr)*2}) {$c_\nr$};
\node (K\nr) at (4,{(\n-\nr)*2+1}) {$k$};
\draw[->,very thick] (M\nr) -- (x\nr);
\draw[->,very thick] (x\nr) -- (E\nr);
\draw[->,very thick] (E\nr) -- (C\nr);
\draw[->,very thick] (K\nr) -- (E\nr);
}
\foreach \nr in {2, ..., \n}{
\pgfmathtruncatemacro{\tmp}{\nr-1}
\draw[->,very thick] (E\tmp) -- (4, {(\n-\tmp)*2-0.5}) -- (2, {(\n-\nr)*2+1.5}) -- (x\nr);
}
\node (IV) at (2,{\n*2-1}) {$\ve{v_0}$};
\draw[->, very thick] (IV) -- (x1);
\node (Mx) at (0,-1) {$\vdots$};
\node (xx) at (2,-1) {$\vdots$};
\node (Ex) at (4,-1) {$\vdots$};
\node (Cx) at (6,-1) {$\vdots$};
\end{tikzpicture}
\end{center}


\begin{enumerate}
\item Quel est le lien entre OUEX et $\bbf_2$?
\item Cryptez l' exemple traité avec ECB en prenant $\ve{v_0}=1010101$.
\item Faites de même avec \og Maman\fg{}.
\item Donnez  une formule  de déchiffrement. Déchiffrer  le cryptogramme
      $101101110011111$ sachant que la clé est 

$k=\begin{pmatrix}
    1&0&2
  \end{pmatrix}
$ et que $\ve{v_0}=001$.
\item Déchiffrez \og Papa\fg{} sachant  que c'est le cryptosystème de la
      question 2. qui a été employé.

\item Un petit programme?...

\end{enumerate}


Ce  mode  est efficace  mais  nécessite  l'utilisation  de fonctions  de
chiffrement  et de  déchiffrement différentes  ce qui  peut  ralentir la
procédure.





\subsubsection{Mode CFB}

 CFB:  \textit{Cipher-FeedBack}. C'est un  mode dérivé  de CFB  qui est
  utilisé  par  OpenPGP,  format  pour  l'échange  sécurisé  de  données
  (paiements sécurisés par exemple)
  largement  utilisé actuellement  mais est  susceptible  d'être attaqué,
  même s'il est très difficile  de mettre en \oe uvre concrètement cette
  attaque:

{\scriptsize
  \href{http://www.cert-ist.com/fra/ressources/Publications\_ArticlesBulletins/Autres/FailledanslechiffrementCFBdOpenPGP/}{http://www.cert-ist.com/fra/ressources/Publications\_ArticlesBulletins/Autres/FailledanslechiffrementCFBdOpenPGP/}
}

Le mode CFB utilise un registre de décalage de taille $r$ inférieure à 
celle de la clé.

On a  besoin d'un vecteur d'initialisation $\ve{v_0}$.  Le message clair
est découpé  en blocs  de longueur $r$.  Ensuite on procède  comme suit,
sachant que  les  $m_j$ sont les blocs en clair de longueur $r$:

\begin{itemize}
\item $t_0=\ve{v_0}$;
\item $s_j=E_k(t_j)$;
\item $g_j$ est  la chaîne constituée des $r$ bits les  plus à gauche de
      $s_j$. Quelle est l'opération arithmétique associée?
\item $c_j=m_j\oplus g_j$;
\item  $t_j=(2^rt_{j-1}+c_{j-1})   \modu  2^n$  (attention!   Il  faut
  travailler en base 2).
\end{itemize}


\begin{center}
% thanks to http://tex.stackexchange.com/a/75838/5645
\tikzset{XOR/.style={fill=black!15,draw,minimum size=13pt,circle,append after command={
[shorten >=\pgflinewidth, shorten <=\pgflinewidth,]
(\tikzlastnode.north) edge (\tikzlastnode.south)
(\tikzlastnode.east) edge (\tikzlastnode.west)
}
}
}
\tikzstyle{encrypt}=[draw,fill=black!15,rectangle,minimum size=20pt,inner sep=0pt]
\begin{tikzpicture}
\newcommand{\n}{3}
\foreach \nr in {1, ..., \n}{
\node (M\nr) at (0,{(\n-\nr)*3}) {$m_\nr$};
\node (x\nr)[XOR] at (2,{(\n-\nr)*3}) {};
\node (E\nr)[encrypt] at (2,{(\n-\nr)*3+1}) {$E$};
\node (K\nr) at (2,{(\n-\nr)*3+2}) {$k$};
\node (C\nr) at (4,{(\n-\nr)*3}) {$c_\nr$};
\draw[->,very thick] (M\nr) -- (x\nr);
\draw[->,very thick] (x\nr) -- (C\nr);
\draw[->,very thick] (K\nr) -- (E\nr);
\draw[->,very thick] (E\nr) -- (x\nr);
}
\foreach \nr in {2, ..., \n}{
\pgfmathtruncatemacro{\tmp}{\nr-1}
\draw[->,very thick] (3, {(\n-\tmp)*3}) -- (3, {(\n-\tmp)*3-0.5}) -- (1, {(\n-\tmp)*3-0.5}) -- (1, {(\n-\nr)*3+1}) -- (E\nr);
}
\node (IV) at (0.5,{\n*3-2}) {$\ve{v_0}$};
\draw[->, very thick] (IV) -- (E1);
\node (Mx) at (0,-1) {$\vdots$};
\node (xx) at (2,-1) {$\vdots$};
\node (Ex) at (4,-1) {$\vdots$};
\end{tikzpicture}
\end{center}



Le déchiffrement fonctionne de manière identique en échangeant les rôles
de $m_j$ et $c_j$ à la quatrième étape: démontrez-le!

\begin{enumerate}
\item Chiffrez \og \textit{ Papa is cool}\fg{} sachant que la clé est $k= 
  \begin{pmatrix}
    3&0&2&1
  \end{pmatrix}
$, que $\ve{v_0}=0101$ et que $r=3$.


\item Déchiffrer  le cryptogramme
      $101101110011111$ sachant que la clé est $k= 
  \begin{pmatrix}
    1&0&2
  \end{pmatrix}
$, que $r=2$ et que $\ve{v_0}=001$.
\end{enumerate}



\end{exercice}




%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "PolyIPT2015_16"
%%% End: 
