1 Ce qu'est un système cryptographique

Dans la situation générique exposée plus haut, on appelle texte clair l'information qu'Alice veut envoyer à Bob. Il faut bien comprendre qu'il peut s'agir ici de n'importe quel type de données, le terme « texte » étant employé largement. Par exemple, Alice pourrait vouloir envoyer un texte en français, un morceau de musique, ou un fichier informatique. Le texte clair est chiffré et ensuite envoyé à travers un canal vers Bob.

Un système cryptographique comporte cinq composantes de base:

1. Un ensemble fini de blocs de texte clair possibles, que l'on identifie $P$. Un exemple d'un tel ensemble pourrait être les 26 lettres de l'alphabet ou les deux valeurs possibles d'un bit.
2. Un ensemble fini de blocs de texte chiffré possibles, que l'on identifie $C$.
3. Un ensemble fini de clés possibles, que l'on identifie $K$. La clé pourrait être un nombre, un mot-clé, un paquet de cartes dans un ordre prédéterminé.
4. Un ensemble de règles de chiffrement possibles, que l'on identifie $E$. Il s'agit ici de transformations mathématiques distinctes mais semblables.
5. Un ensemble de règles de déchiffrement possibles, que l'on identifie $D$.

Ces composantes sont liées d'une façon spéciale: pour toute clé de chiffrement $k\in K$, une règle de chiffrement $e_{k}\in E$ lui est associée, ainsi que la règle de déchiffrement correspondante $d_{k}\in D$. La fonction de chiffrement $e_{k}$ opère sur un bloc de texte clair $p\in P$ et en fait un bloc de texte chiffré $c\in C$, c'est-à-dire que $e_{k}:P\rightarrow C$. La règle de déchiffrement $d_{k}$ opère en sens contraire: $d_{k}:C\rightarrow P$.

La propriété la plus importante est le fait que

$$d_{k}(e_{k}(p))=p$$

pour tout bloc de texte de clair $p\in P$. Cette relation indique que le déchiffrement du texte chiffré donnera toujours le texte clair. Sans cette propriété, il serait impossible de retrouver l'information du départ.

De façon pratique, un bon système cryptographique sera un système où

• $e_{k}(p)$ est facile à calculer rapidement;
• il est très difficile de trouver $d_{k}$ à partir de la valeur de $e_{k}(p)$ si l'on ne connait pas $k$.

On atteindra le deuxième but de deux façon: en augmentant l'étendue de $K$ de façon à augmenter le nombre de $k$ possibles, et en utilisant une fonction $e_{k}$ qui ne donne absolument aucun indice sur la nature de $d_{k}$. Une telle fonction est dite irréversible. La plupart des fonctions arithmétiques sont réversibles. Par exemple, si la fonction de chiffrement est $e_{k}(p)=c=p^{2}$ et qu'on obtient une valeur de $c$ égale à , on pourra savoir que $p=3$ en utilisant la fonction inverse $d_{k}(c)=p=\frac{c-1}{2}$ (voir figure 1).

Figure 1: $d_{k}(c)=\frac {c-1}{2}$

Toutefois, si la fonction de chiffrement est, par exemple, une fonction du type $e_{k}(p)=p^{2}$, il pourra exister plusiers de valeurs de $p$ possibles pour chaque $c$ (voir figure 2).

Figure 2: $d_{k}(c)=\sqrt {c}$

Ce type de fonction irréversible est utilisée dans les algorithmes modernes les plus puissants. Elle tire son pouvoir de l'arithmétique modulaire, laquelle fut utilisée dès le tout début, lorsque la cryptographie elle-même faisait ses débuts.