| |
|
Le ou exclusif (eXclusif OR) est un opérateur de l'algèbre de boole très utilisé en électronique mais aussi en cryptographie du fait de ses propriétés très intéressantes. Son symbole est un signe plus dans un cercle: "⊕".
Comme on peut le voir dans sa table de vérité, l'opérateur logique OU Exclusif peut se définir par la phrase suivante:
| A | B | S= A ⊕ B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
A et B sont les deux opérandes et S la sortie. On dit que S est à l'état haut (est égal à 1) quand A «ou» B sont à un. Le «ou» est à prendre au sens l'un ou l'autre mais pas les deux en même temps : «Voulez-vous du café ou du thé». On peut aussi dire que l'état haut se produit quand A et B sont différents, ce qui simplifie la compréhension.
Cet opérateur nous permet de faire au niveau des bits que l'on fait déjà depuis des centaines d'années au niveau des caractères. Et quand on sait qu'un caractère est généralement représenté dans un ordinateur par 8 bits, on voit assez facilement la possibilité de complexifier les chiffrements.
On peut remarquer une propriété telle que :
A ⊕ A = 0
A étant toujours identique à lui-même, le résultat sera obligatoirement 0.
Ce qui nous conduit à la propriété suivante:
A ⊕ B = C
C ⊕ B = A
En considérant A comme étant le bit en clair (non chiffré) et B le bit de la clé de chiffrement. Après l'opération on obtient un bit C qui sera le bit une fois chiffré. Enfin, si on effectue une nouvelle opération avec C (le bit chiffré) et B (la clé), on retrouve le bit A non chiffré d'origine. C'est le principe de chiffrement symétrique, la même clé permet de chiffrer et déchiffrer un message.
Ce système, bien que très «simple», peut s'avérer inviolable si la clé, aléatoirement générée, est au moins aussi longue que le message à chiffrer et quelle ne soit utilisée qu'une seule fois. Dans cette phrase, c'est surtout le mot aléatoirement qui s'avère être le plus difficile à mettre en oeuvre.
Maintenant, voici la mise en application de tout cela grâce à un exemple:
A = 0110101011010100 (message en clair)
B = 0101011011100110 (la clé; à garder secrète bien évidement)
Chiffrement: S = A ⊕ B
S = 0011110000110010 (message chiffré)
Déchiffrement: A = S ⊕ B
A = 0110101011010100 (message déchiffré)
On voit bien que sans la clé, il est quasi-impossible de déchiffrer le message; il ne reste plus que la méthode brute : essayer toutes les possibilités, ici 2^16 = 65536 possibilités. Remarquez que de nos jours, 65.536 combinaisons sont assez rapidement calculées avec un bon processeur, mais là il ne s'agit que de chiffrer 2 caractères : pas de quoi raconter une histoire. Chaque caractère supplémentaire multiplie par 256 le nombre de possibilités.