OU exclusif

Un article de Freepedia.

Le ou exclusif (eXclusive OR) est un opérateur logique 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 traditionnellement un signe plus dans un cercle: « ⊕ ». Cependant, cet opérateur fait double emploi avec le signe mathématique "différent de", qui sur des valeurs booléennes a exactement la même signification.

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:

La sortie est VRAI équivaut à dire que seulement l'une des entrées est VRAI

Table de vérité de XOR
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.

S = A ⊕ B = A.B| + A|.B

Cet opérateur nous permet de faire au niveau des bits ce 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.

Quelques propriétés :

• A ⊕ A = 0 (A étant toujours identique à lui-même, le résultat sera obligatoirement 0)
• A ⊕ 0 = A
• A ⊕ 1 = A|
• A ⊕ A| = 1
• commutativité A ⊕ B = B ⊕ A
• associativité A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C
• A ⊕ B = A ⊕ B ⊕ A.B
• A ⊕ B = C alors C ⊕ B = A
  

---

Explication de cette dernière propriété :

Créons 4 bits, (A, B, C et H) tels que :

A ⊕ B = C et C ⊕ B = H

Le but de cette démonstration est de prouver que H = A

En « Xorisant » membre à membre les égalités précédentes on obtient : (A ⊕ B) ⊕ (C ⊕ B) = C ⊕ H

ce qui ici, en vertu de la commutativité du « Xor », est équivalent à  : (A ⊕ B) ⊕ (B ⊕ C) = H ⊕ C

ou encore, en vertu de l'associativité, à : A ⊕ B ⊕ B ⊕ C = C ⊕ H

ce qui équivaut à A ⊕ C = H ⊕ C

ce qui implique : A = H

Ainsi on a bien :

A ⊕ B = C et C ⊕ B = A

Sommaire 1 Cryptographie 1.1 Problème annexe 1.2 Application 1.3 Histoire

Cryptographie

Voir aussi l'article : masque jetable

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é, générée aléatoirement, est au moins aussi longue que le message à chiffrer et qu'elle ne soit utilisée qu'une seule fois (on parle de masque jetable, ou encore de «one-time pad»). Dans cette phrase, c'est surtout le mot «aléatoirement» qui s'avère être le plus difficile à mettre en œuvre. En revanche, lorsque la clé est vraiment aléatoire --- techniquement, qu'elle est tirée selon la distribution uniforme parmi les clés possibles --- ce système est parfaitement sûr, en un sens rigoureusement défini par Claude Shannon, en 1949, dans un article fondateur «Communications theory of secrecy systems». Il convient d'ajouter que c'est le seul chiffrement qui satisfait cette sécurité absolue en théorie.

Problème annexe

Corollaire : tout fichier licite peut être transformé en fichier illicite de même taille par un ou exclusif avec un fichier donné facile à créer de toutes pièces (puisque c'est le ou exclusif du fichier licite et de l'illicite), ce qui rend l'opération de preuve de culpabilité très délicate et non exempte d'arbitraire.

Application

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 évidemment)

Chiffrement: S = A ⊕ B S = 0011110000110010 (message chiffré)

Déchiffrement: A = S ⊕ B A = 0110101011010100 (message déchiffré)

Sans la clé, il est impossible de déchiffrer le message puisque n'importe quel message M de longueur égale au message original est un déchiffrage possible. Il suffit pour cela de prendre la clé C = S ⊕ M.

Histoire

Ce système de chiffrement a été utilisé pour le téléphone rouge, en fait un telex, reliant directement le Kremlin à la Maison Blanche, les clés transitant alors par valises diplomatiques. Le système de masque jetable était également employé par les espions soviétiques. Certains masques furent utilisés plus d'une fois (parfois avec des années d'intervalle) ce qui permit aux services du chiffre anglais de déchiffrer certains messages.