OU exclusif
Un article de Wikipédia, l'encyclopédie libre.
Vous avez de Le OU exclusif, souvent appelé XOR (eXclusive OR), est un opérateur logique de l'algèbre de Boole. A deux événements, qui peuvent avoir chacun la valeur VRAI ou FAUX, il associe un résultat qui a lui-même la valeur VRAI ou FAUX.
Cet opérateur est très utilisé en électronique, en informatique, et aussi en cryptographie du fait de ses propriétés intéressantes. Son symbole est traditionnellement un signe plus dans un cercle: « ⊕ ».
Sommaire |
[modifier] Définition
Appelons A et B les deux événements considérés. Convenons de représenter leur valeur ainsi :
- 1 = VRAI
- 0 = FAUX
L'opérateur XOR est défini par sa table de vérité, qui indique pour toutes les valeurs possibles de A et B la valeur du résultat R :
| Table de vérité de XOR | ||
| A | B | R = A ⊕ B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Comme on peut le voir, l'opérateur logique XOR, ou OU exclusif, peut se définir par la phrase suivante :
- Le résultat est VRAI si un et un seul des événements A et B est VRAI.
Il se différencie de l'opérateur OU inclusif, qui donne en outre un résultat VRAI lorsque A et B ont tous les deux la valeur VRAI.
En informatique, cet opérateur peut s'utiliser pour combiner deux bits, valant chacun 0 ou 1, en appliquant les règles définies par la table précédente, le résultat étant lui-même la valeur d'un bit.
[modifier] Quelques propriétés mathématiques
- A ⊕ A = 0 (on le vérifie facilement sur la table pour les 2 valeurs possibles de A)
- A ⊕ 0 = A
- A ⊕ 1 = A|, où | est l'opérateur NON, qui prend la valeur opposée de 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
[modifier] Exemple d'utilisation en cryptographie
Considérons un document en clair à chiffrer. Il consiste en une suite de bits. Dans la méthode de chiffrement par flot, on se procure par ailleurs une suite de bits de même longueur, totalement aléatoire, qu'on appelle clé de chiffrement. On traite un à un les bits du clair, en combinant chacun avec le bit de même rang dans la clé de chiffrement.
Appelons A un bit en clair et B le bit de même rang de la suite aléatoire.
Le chiffrement consiste à calculer le bit C par : C = A ⊕ B . C est le chiffré de A.
Pour déchiffrer C on utilise à nouveau le bit B de la suite aléatoire et on calcule : C ⊕ B.
Le résultat donne A, le bit de clair, car C ⊕ B = A ⊕ B ⊕ B = A ⊕ 0 = A, en utilisant les deux premières propriétés ci-dessus .
Cette méthode est l'une des manières d'effectuer un chiffrement symétrique, où la même clé sert à chiffrer et déchiffrer.
Ce système, bien que très simple dans son principe, peut s'avérer inviolable si la suite de bits de la clé est vraiment aléatoire. Cette dernière ne doit en outre être 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éatoire» qui s'avère être le plus difficile à mettre en œuvre. Mais lorsque la clé est vraiment aléatoire --- techniquement, qu'elle est tirée selon la distribution uniforme parmi toutes les suites possibles de cette longueur --- 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.
Voir aussi l'article : masque jetable
[modifier] Illustration
Voici un exemple numérique de la méthode précédente :
M = 0110101011010100 (message en clair)
K = 0101011011100110 (la clé ; à garder secrète bien évidemment)
Convenons que le symbole ⊕ représente ici l'application de l'opérateur XOR à chacun des bits :
Chiffrement : C = M ⊕ K = 0011110000110010 (message chiffré)
Déchiffrement : M = C ⊕ K = 0110101011010100 (message déchiffré)
[modifier] Histoire
Ce système de chiffrement a été utilisé pour le téléphone rouge, en fait un télex, 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.
|
|
 |
Portail de l'électricité et de l'électronique – Accédez aux articles de Wikipédia concernant l'électricité et l'électronique. |
