Fonction OU exclusif

La fonction OU exclusif, fréquemment nommée XOR, est un opérateur logique de l'algèbre de Boole. À deux opérandes, qui peuvent avoir chacun la valeur VRAI ou FAUX, il associe un résultat qui a lui-même la valeur VRAI uniquement si les deux...



Catégories :

Cryptologie - Fonction logique - Électronique numérique - Électronique

Page(s) en rapport avec ce sujet :

  • On nomme "fonction logique" une entité acceptant plusieurs valeurs... Voici par exemple ce à quoi pourrait ressembler un chronogramme de l'opérateur ET :... La fonction OU EXCLUSIF est représenté par un plus encerclé : Logique combinatoire.... occupe 2 bits : un bit pour la somme (S) et un pour la retenue (R).... (source : obligement.free)
  • la Fonction OU exclusif est la plus courante...... d'une extraction manuelle, l'opérateur doit sélectionner des régions rectangulaires ou..... ajoutant une valeur calculée suivant les plans de bits chiffrés.... (source : share.esi)
  • Avec ce commutateur vous pouvez inverser les valeurs logiques des composants DDE. Un courant d'électricité implique le plus souvent que le Bit correspondant... (source : art-systems)

La fonction OU exclusif, fréquemment nommée XOR (eXclusive OR), est un opérateur logique de l'algèbre de Boole. À deux opérandes, qui peuvent avoir chacun la valeur VRAI ou FAUX, il associe un résultat qui a lui-même la valeur VRAI uniquement si les deux opérandes ont des valeurs différentes.

Cet opérateur est particulièrement utilisé en électronique, en informatique, et aussi en cryptographie du fait de ses propriétés intéressantes. Son symbole est habituellement un signe "PLUS" dans un cercle : «⊕».

Définition

Appelons A et B les deux opérandes reconnus. 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 l'ensemble des valeurs envisageables 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 opérandes A et B est VRAI

ou

Le résultat est VRAI si les deux opérandes A et B ont des valeurs différentes

ou

Le résultat est VRAI si un nombre impair d'entrées est vrai (ceci est en particulier applicable quand deux ou plusieurs opérateurs logiques XOR se cascadent (générateurs de bit de parité)

Il se différencie de l'opérateur OU inclusif, car il donne un résultat FAUX quand A et B ont simultanément la valeur VRAI. Son symbole se différencie aussi de l'opérateur OU inclusif dont le symbole est simplement un "PLUS" : «+».

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.

Avec des portes logiques ET/OU, A XOR B = (A ET non B) OU (non A ET B).

Quelques propriétés mathématiques

Exemple d'utilisation en cryptographie

Considérons un document numérique à chiffrer, il consiste en une suite de bits. Dans la méthode de chiffrement par flot, on doit disposer d'autre part une suite de bits de même longueur, complètement aléatoire, qu'on nomme clé de chiffrement. On traite un à un les bits du document en clair, en le combinant avec le bit de même rang de 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 = AB. C est le chiffré de A.

Pour déchiffrer C on utilise à nouveau le bit B de la suite aléatoire et on calcule : CB.

Le résultat donne A, le bit de clair, car CB = ABB = A0 = 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é permet de chiffrer et déchiffrer.

Ce dispositif, quoique particulièrement 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 en particulier le mot «aléatoire» qui s'avère être le plus complexe à mettre en œuvre. Mais quand la clé est vraiment aléatoire --- techniquement, qu'elle est tirée selon la distribution uniforme parmi l'ensemble des suites envisageables de cette longueur --- ce dispositif est idéalement 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 l'unique chiffrement aboutissant à une sécurité absolue, en principe.

Voir aussi l'article : masque jetable

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 bien entendu)

Convenons que le symbole ⊕ représente ici l'application de l'opérateur XOR à chacun des bits :

Chiffrement : C = MK = 0011110000110010 (message chiffré)

Déchiffrement : M = CK = 0110101011010100 (message déchiffré)

Histoire

Ce dispositif 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 dispositif de masque jetable était aussi employé par les espions soviétiques. Certains masques furent utilisés plus d'une fois (quelquefois avec des années d'intervalle) ce qui permit aux services du chiffre anglais de déchiffrer certains messages.

Autres applications en cryptographie

La totalité des chiffreurs symétriques utilise l'opérateur XOR. Le nouvel algorithme de cryptographie haute sécurité symétrique ÆS (Rijndæl) surtout, en utilise un très grand nombre.

Application en électronique

Exemple d'utilisation : Le Circuit intégré 7486 TTL ou le circuit intégré CMOS 4070 intègre quatre portes logiques du type OU exclusif. Illustration : Exemple : La lampe s'allume si on appuie sur «a» ou «b» uniquement, mais pas si on appuie sur «a» et «b» simultanément.

Schéma
Fonctions logiques(5-a).png
Équation
L = a \oplus b
L = (\bar{a}°+(aar{b})
Chronogramme
Fonctions logiques(5-d).png
Symbole IEC
Fonctions logiques(5-e).png
Symbole ANSI (appelé aussi militaire)
XOR ANSI.svg

Application en informatique

Outre les utilisations liées à la cryptographie, la fonction OU exclusif sert à remettre rapidement la valeur d'une variable (fréquemment un registre) à zéro. Prenons par exemple le code en assembleur qui utilise le OU exclusif pour remettre la valeur du registre eax à zéro :

xor eax, eax

Ce dernier s'exécute plus rapidement que le code intuitif suivant :

mov eax, 0

Application en électricité domestique

Une application utilisée de l'opérateur logique OU exclusif en électricité domestique est dans les salles ou une ampoule peut être allumée ou éteinte par deux interrupteurs positionnés près de deux entrées. Chacun des deux interrupteurs peut soit allumer ou éteindre l'ampoule quelle que soit la position de l'autre interrupteur. Pour obtenir une telle fonctionnalité, on doit brancher les deux interrupteurs pour former un opérateur XOR.

Voir aussi

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Fonction_OU_exclusif.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu