TP2 - Vernam

Objectifs

1. Comprendre le fonctionnement des portes logiques et de l'opérateur XOR ;
2. Savoir convertir des données entre binaire, hexadécimal et ASCII ;
3. Mettre en œuvre le chiffrement de Vernam en Python ;

TD

Les questions se répondent sur feuille (ou word).
La programmation (à la fin) se fait sur python.

Introduction

Le chiffrement de Vernam est une méthode de chiffrement symétrique utilisant une clé de chiffrement utilisée qu'une seule fois, appelée masque jetable.

Point histoire

En 1917, Gilbert Vernam, ingénieur chez AT&T Bell Labs, met au point un dispositif pour sécuriser les téléscripteurs militaires. Son objectif : rendre illisible toute communication interceptée sur la ligne.

Le système repose sur une bande perforée utilisée comme clé, détruite après chaque transmission : c'est le principe du masque jetable.
Lors de la crise des missiles de Cuba (1962), ce système a été adopté par les États-Unis et l'URSS pour le célèbre téléphone rouge.

L'opération centrale du chiffrement est le XOR (ou exclusif), appliqué bit à bit entre le message et la clé.

Portes logiques

Les portes logiques sont des opérateurs binaires : elles prennent des bits (0 ou 1) en entrée et produisent un bit en sortie selon l'opération effectuée. Leurs comportements sont résumés dans des tables de vérité.

On distingue 6 grandes portes : NOT, AND, OR, NAND, NOR et XOR.

Rappel : NOT et AND

NOT inverse la valeur d'entrée :

A	NOT A
0	1
1	0

AND vaut 1 si et seulement si toutes les entrées valent 1 :

A	B	A AND B
0	0	0
0	1	0
1	0	0
1	1	1

Exercices

1
Recopier et compléter la table de vérité de OR :
A	B	A OR B
0	0
0	1
1	0
1	1
OR vaut 1 si au moins une des entrées vaut 1.
Fait
2
Recopier et compléter la table de vérité de NAND (NOT AND - l'inverse de AND) :
A	B	A NAND B
0	0
0	1
1	0
1	1
Fait
3
Recopier et compléter la table de vérité de XOR (OU exclusif) :
A	B	A XOR B
0	0
0	1
1	0
1	1
XOR vaut 1 si les deux entrées sont différentes.
Fait
4
Observer la table XOR. Que peut-on remarquer si on effectue (A XOR B) XOR B ? Vérifier avec les quatre combinaisons possibles. Que peut-on en déduire pour le chiffrement ?
Fait
5
Recopier et compléter la table de vérité de l'expression A NAND (B XOR C) en tenant compte des 8 combinaisons possibles pour trois variables :
A	B	C	B XOR C	A NAND (B XOR C)
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1
Fait

Opérations logiques

Les portes logiques s'appliquent aussi sur des mots binaires (suite de bits), en traitant chaque colonne indépendamment, de gauche à droite.

Exemple : XOR sur deux mots de 4 bits

  1 0 1 1
  0 1 1 0
  -------
  1 1 0 1

On applique XOR colonne par colonne : 1 XOR 0 = 1, 0 XOR 1 = 1, 1 XOR 1 = 0, 1 XOR 0 = 1.

Exercices

1
Effectuer l'opération 0011011101 OR 1001100110. Donner le résultat.
Fait
2
Effectuer l'opération 0011011101 NAND 1001100110. Donner le résultat.
Fait
3
Effectuer l'opération 0011011101 XOR 1001100110. Donner le résultat.
Fait
4
Vérifier la propriété découverte en Q4 de la section précédente : effectuer (0011011101 XOR 1001100110) XOR 1001100110. Que peut-on constater ?
Fait

Traduction binaire-hexadécimal

Table ASCII en hexadécimal

Pour chiffrer avec Vernam, chaque lettre est d'abord convertie en binaire via la table ASCII.

La table se lit par rangée et colonne : la lettre 'a' est dans la rangée 6, colonne 1, donc sa valeur hexadécimale est 61.

Conversion hexadécimal → binaire

Chaque chiffre hexadécimal se convertit en 4 bits :

• 6 → 0110
• 1 → 0001
• Donc 'a' (hex 61) → 01100001 en binaire.
  À l'inverse, pour passer du binaire à l'hexadécimal, on regroupe les bits 4 par 4 depuis la droite, puis on convertit chaque groupe.

Exercices

1
Donner la valeur hexadécimale des lettres 'N', 'S' et 'I' en utilisant la table ASCII.
Fait
2
Convertir ces trois valeurs hexadécimales en binaire (groupes de 8 bits).
Fait
3
Effectuer la conversion inverse : quelles lettres correspondent aux valeurs binaires 01001111 et 01101011 ?
Fait

une vérification

Code incorrect, réessaie !

Chiffrement de Vernam

Algorithme de Vernam

1. Convertir le message en binaire (via ASCII) ;
2. Choisir une clé aléatoire de même longueur que le message ;
3. Convertir la clé en binaire ;
4. Appliquer l'opération XOR bit à bit entre le message et la clé ;
5. Le résultat est le message chiffré. Pour déchiffrer, on applique à nouveau XOR avec la même clé.

Exercices

1
En utilisant le mot TERM et la clé NSIN (convertis en binaire à la section précédente), effectuer l'opération XOR bit à bit.
Fait
2
Regrouper le résultat en groupes de 8 bits et convertir chaque groupe en hexadécimal. Si la valeur hexadécimale correspond à un caractère imprimable dans la table ASCII, donner sa lettre.
Fait
3
Pour déchiffrer, que faudrait-il faire ? Appliquer la méthode sur le résultat obtenu avec la clé NSIN et vérifier qu'on retrouve TERM.
Fait
4
Déchiffrer le message suivant, obtenu avec la clé "LYCEE" :
Position	1	2	3	4	5
Message chiffré (hex)	1D	38	07	28	26
Clé	L	Y	C	E	E
Fait

une vérification

Code incorrect, réessaie !

Programmation

Exercices

1
Écrire une fonction xor(a, b) qui prend deux entiers valant 0 ou 1 et retourne le résultat du XOR entre a et b.
Fait
2
Écrire une fonction chartobin(lettre) qui prend une lettre en paramètre et retourne sa représentation binaire sous forme d'une chaîne de 8 caractères (avec des zéros de remplissage à gauche si nécessaire).
Astuce
Les fonctions ord() et bin() peuvent être utiles. Attention : bin() renvoie une chaîne préfixée par '0b' qu'il faut retirer, et le résultat n'est pas toujours sur 8 bits.
Fait
3
Écrire une fonction bintochar(codeBin) qui prend une chaîne de 8 bits et retourne le caractère ASCII correspondant.
Fait
4
Écrire une fonction vernam(message, cle) qui prend un message et une clé de même longueur et retourne le message chiffré sous forme de chaîne binaire.
Fait
5
Vérifier la propriété fondamentale de Vernam en testant :
message = "TERM"
cle = "NSIN"
chiffre = vernam(message, cle)
dechiffre = vernam(chiffre, cle)
print(dechiffre)  # doit afficher "TERM" ... ou presque, à vous d'adapter !
Que faut-il adapter pour que le déchiffrement fonctionne ? Modifier votre code pour que dechiffre soit bien la chaîne "TERM".
Fait

Un chiffrement parfait ?

Exercices

1
Combien de clés différentes existe-t-il pour un message de 4 lettres avec Vernam ? Comparer avec César et Vigenère avec une clé de 4 caractères.
Fait
2
Peut-on appliquer une analyse de fréquences sur un message chiffré par Vernam ? Pourquoi ?
Fait
3
En 1949, Claude Shannon démontre mathématiquement que Vernam est un chiffrement parfait si et seulement si trois conditions sont réunies. D'après ce que vous avez appris dans ce TP, quelles sont-elles selon vous ?
Fait
4
Malgré sa perfection théorique, Vernam est très peu utilisé en pratique. Pourquoi selon vous ?
Fait