Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

OU exclusif

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 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:

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

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

Explications :

A = A, Donc d'après la définition de l'Xor on a A ⊕ A = 0. Créons maintenant 3 autres bits, (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

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 œuvre.

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.