Sécuriser les communications¶

Cours¶

A. Méthodes de chiffrement¶

A.I. Problématique¶

Que veut dire "communiquer de manière sécurisée" ? Cela veut dire pouvoir envoyer des messages de manière à préserver :
- la confidentialité : ces messages ne doivent pas pouvoir être lus par quelqu’un d’autre que l’émetteur et le destinataire.
- leur intégrité : ils ne doivent pas pouvoir être modifiés,
- l’authentification de l’émetteur et du destinataire.

Les méthodes décrites dans ce cours permettent d’assurer la confidentialité des messages principalement, et généralement leur intégrité et l’authentification des acteurs impliqués.

A.II. Chiffrement symétrique et asymétrique¶

Définition

Une clé de chiffrement est une information (de n'importe quel type : entier, caractères,...) nécessaire pour chiffrer et déchiffrer un message.

A.II.a. Le chiffrement symétrique¶

Définition

Le chiffrement symétrique repose sur l’utilisation d’une clé qui est la même pour chiffrer et pour déchiffrer le message.

Cette méthode est-elle sécurisée ?

Si deux interlocuteurs possèdent cette clé, il est facile pour eux d’échanger des messages de manière sécurisée (confidentielle, intègre et authentifiant les interlocuteurs).

Quel est son inconvénient ?

Le problème est qu’ils faut que chacun ait préalablement récupéré la clé... en utilisant un autre canal que celui sur lequel ils veulent communiquer (sinon tout le monde l’aura).

A.II.b. Le chiffrement asymétrique¶

Définition

Le chiffrement asymétrique utilise deux clés : une clé publique qui sert à chiffrer le message et une clé privée qui sert à le déchiffrer. La clé publique, comme son nom l’indique, est accessible à tout le monde et tout un chacun peut chiffrer des messages avec. La clé privée n’est connue que du destinataire du message : il est le seul à pouvoir le déchiffrer.

Quel est le principal avantage de cette méthode ?

Il n’y a ici pas besoin d’utiliser un autre canal pour transférer la clé qui permet de chiffrer, car elle est connue de tous.

La communication est-elle sécurisée ?

La confidentialité est assurée, mais pas l'intégrité ni l'authentification : tout le monde ayant la clé publique, un message peut être remplacé par un autre, par quelqu'un d'autre, chiffré avec la même clé.

B. HTTPS (Secure Hypertext Transfer Protocol)¶

En pratique, on utilise généralement une combinaison des deux méthodes : tout d’abord un chiffrement asymétrique pour échanger la clé symétrique qui servira au reste des échanges. Cette méthode est celle utilisée lorsqu’on cherche à établir une connexion avec le serveur d’un site Web en HTTPS.

Solution

TD : Exemples de chiffrements¶

A. Le code de César¶

A.I. Chiffrement symétrique¶

Le codage de César avec une clé de 13 permet de réaliser un chiffrement symétrique. On décale tout simplement chaque lettre de l’alphabet du message initial de 13 pour obtenir le message chiffré :

Lettre initiale	A	B	C	D	E	F	G	H	I	J	K	L	M
Lettre chiffrée	N	O	P	Q	R	S	T	U	V	W	X	Y	Z

Lettre initiale	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
Lettre chiffrée	A	B	C	D	E	F	G	H	I	J	K	L	M

En utilisant cette méthode, chiffrer "INFORMATIQUE".
Vérifier qu’en utilisant la même clé, on parvient à déchiffrer le message.

A.II. Chiffrement asymétrique¶

Comment peut-on obtenir un chiffrement asymétrique en utilisant le principe du codage de César ?
Le mettre en œuvre pour chiffrer "NSI", en utilisant une clé publique de 5 (remplir le tableau ci-dessous). Cela signifie que l'on fait 5 déplacements sur la droite pour coder chaque lettre.

Pour une clé de 5 (chiffrement) :

Lettre initiale	A	B	C	D	E	F	G	H	I	J	K	L	M
Lettre chiffrée

Lettre initiale	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
Lettre chiffrée

Quelle est la clé privée qu’il faut utiliser pour déchiffrer le message ? Compléter le tableau correspondant pour vérifier que l’on peut bien déchiffrer le message.

Pour une clé de .......... (déchiffrement) :

Lettre initiale	A	B	C	D	E	F	G	H	I	J	K	L	M
Lettre chiffrée

Lettre initiale	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
Lettre chiffrée

Déchiffrer le message chiffré à la question 2.

B. Le XOR¶

Rappeler la table de vérité du XOR (ou exclusif) :

a	b	a xor b
0	0
0	1
1	0
1	1

On considère m le message initial, mc le message chiffré et c la clé.
1. Montrer que si mc = m XOR c, alors mc XOR c = (m XOR c) XOR c = m.

Aide : Cela revient à ajouter une colonne dans la table de vérité, correspondant à une expression à exprimer en fonction de a, de b, et de l'opérateur xor.

Que peut-on en déduire sur la méthode pour déchiffrer un message qui a été chiffré avec le XOR ?

A l’aide de la table ASCII fournie ci-dessus, chiffrer le message : "TURING" avec la clé "ENIGMA" en utilisant le XOR sur le code ASCII binaire de chaque lettre. Donner le résultat en binaire.

Convertir le résultat en décimal.

Pour les plus curieux, vous pouvez rechercher sur le Web à quels caractères correspondent les lettres chiffrées (ils ne sont pas dans la liste ci-dessus).

A partir des lettres chiffrées en binaire, vérifier que l’on parvient à déchiffrer le message.
Que faut-il faire si la clé est, par exemple, "NSI" ? (il n'est pas demandé de faire le chiffrement)

C. Le code RSA¶

Le système RSA est basé sur l'utilisation d'entiers qui ne sont pas choisis au hasard : des entiers (très grands en pratique) qui se factorisent en produits de nombres premiers (exemple : 9967 * 9973 = 99400891). C'est un chiffrement asymétrique.

1. Chiffrement¶

Choix de la clé publique

Soit \(N = 437\), le produit de deux nombres premiers : \(437 = 23*19=p*q\).
On considère alors l’entier \(n = (p-1)*(q-1) = 22*18 = 96\) et on choisit \(c = 41\) un nombre premier strictement inférieur à \(n\).
La clé publique pour notre exemple est le couple \((c, N) = (41, 437)\)

Exemple

Prenons la lettre "b", codée en Unicode par le nombre 98.
Pour coder la lettre "b", on détermine le reste dans la division euclidienne de \(98^c\) par \(N\). Ce qui donne ici 110, c’est à dire la lettre "n".

Question : Appliquer la même méthode pour coder la lettre "a" (97 en code ASCII).

2. Déchiffrement¶

Choix de la clé privée

On cherche la clé privée \((d,N)\) (donc \(d\), \(N\) faisant partie de la clé publique).
\(d\) est un entier tel que le reste de la division euclidienne de \(c*d\) par \(n\) est \(1\) (des méthodes mathématiques permettent de déterminer \(d\)).
La clé privée pour notre exemple est : \((d, N) = (29,437)\).

Exemple

Pour décoder la lettre ”n” (codage de "b"), on utilise la clé privée qui est \((29,437)\) : on calcule le reste de la division euclidienne de \(110^d\) par \(N\). Ici, le reste dans la division de \(110^{29}\) par \(437\) donne bien \(98\).

Question : appliquer cette méthode pour déchiffrer le code obtenu dans la partie précédente.

TP : Implémentation de chiffrements¶

Introduction¶

Beaucoup de chiffrements nécessitent de passer par la représentation des caractères sous la forme d'entiers, en utilisant Unicode. Pour avoir la représentation d'un caractère sous forme de nombre, ou réciproquement le caractère correspondant à un nombre donné, on utilise les fonctions Python suivantes :
- La fonction ord qui prend en paramètre un caractère et renvoie sa transcription avec Unicode (intégrant le code ASCII, qui est celui utilisé pour coder des caractères non-spéciaux).
- Sa fonction réciproque chr qui renvoie le caractère correspondant à un nombre Unicode.

Tester la fonction ord sur des lettres majuscules pour obtenir leur code ASCII. Quel est le nombre codant le 'A' ?

code ASCII du 'A' :

Tester la fonction chr avec des entiers divers, puis vérifier que l'on retrouve bien le caractère A lors qu'on met son code ASCII en paramètre.

A. Le XOR¶

Nous allons écrire une fonction chiffrement_xor qui prend en entrée un message sous la forme d'une chaîne de caractères et une clé du même type, et retourne le message chiffré avec le XOR, sous la forme d'une chaîne de caractères également.

Nous allons utiliser :

L'opérateur ^ qui effectue le XOR entre deux nombres x et y avec la syntaxe x^y.
Une clé (symétrique) qui fera la même taille que le message (vous pouvez utiliser l'exemple pris en TD).
Identifier les différentes étapes de l'algorithme, à écrire ci-dessous.

Solution possible

On pourra appliquer les étapes suivantes, pour chaque caractère du message : - récupérer le code ascii du caractère dans une variable,
- récupérer le code ascii du caractère de la clé associé au caractère dans une autre variable,
- calculer le xor entre ces deux nombres,
- ajouter la conversion en caractère de ce résultat au reste du message chiffré.

Implémenter cette fonction xor et afficher le message chiffré.

def xor(message, cle):
    ...


message = ...
cle = ...
print(xor(message, cle))

Aide

Pour chaque caractère à chiffrer, il faut lui associer un caractère de la clé, qui ne fait pas forcément la même taille. Ils n'ont donc pas le même indice !
Utiliser le modulo % et une caractéristique de la clé pour la "répéter"comme fait en TD.

Le XOR permettant de faire un chiffrement symétrique, comment trouve-t-on le message initial ? Faire le test ci-dessous.

Aide

Le XOR étant un chiffrement symétrique, appliquer la même fonction avec la même clé au message chiffré permet d'obtenir à nouveau le message initial.

B. Le code de César¶

Écrire une fonction cesar permettant de chiffrer et (avec une clé privée potentiellement différente) de déchiffrer un message.

On pourra pour cela utiliser n’importe quelle clé publique cle comprise entre 1 et 25.
Le message à chiffrer message sera écrit en majuscules.
On ne chiffre pas les caractères qui ne sont pas des lettres majuscules (on garde le caractère initial).
Ecrire une première version de la fonction, utilisant une variable alphabet contenant toutes les lettres majuscules, pour obtenir l'indice de la lettre chiffrée à partir de l'indice de la lettre non-chiffrée.

def cesar(message, cle):
    alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
    ...

Aide 1

Si l'on dépasse la taille de l'alphabet, il faut revenir au début. Pensez donc au modulo : % !

Aide

Pour obtenir l'indice de la lettre chiffrée, il faut avoir l'indice de la lettre non-chiffrée. On peut l'obtenir en calculant sa position par rapport au A et avec la fonction ord, ou bien avec une fonction auxiliaire qui recherche l'indice d'une occurrence dans une chaîne de caractères.

Tester votre fonction sur le message "CLEOPATRE EST EN DANGER !" :

cle = ...

Ecrire une deuxième version de la fonction, utilisant cette fois-ci un dictionnaire correspondance donnant la correspondance entre chaque lettre majuscule et sa version chiffrée. Ce dictionnaire est généré par compréhension, grâce à la fonction chr et au code ASCII du A.
Tester la fonction sur le message.

def cesar_dico(message, cle):
    correspondance = {chr(i+...): chr((i+cle)...+...) for i in range(26)}
    ...

print(cesar_dico(...))

Déchiffrer le message.

C. Le système RSA¶

Écrire un programme qui chiﬀre et déchiﬀre un message en utilisant le système RSA avec les clés utilisées en TD :
- clé publique : (41, 437)
- clé privée : (29, 437)

On créera une fonction chiffrement_RSA(message, cle_publique) et une fonction dechiffrement_RSA(message_chiffre) qui retournent respectivement le message chiffré (en caractères) et le message déchiffré (en caractères).

On part du principe que la clé publique est connue de tous, et peut donc être utilisée en paramètre de la fonction de chiffrement, alors que la clé privée n'est connue que du destinataire : lui seul a la fonction permettant de déchiffrer le message dans laquelle la clé privée est écrite "en dur".

N.B. : Voici un autre exemple de clés qui peuvent être utilisés : clé publique (103, 697); clé privée (87, 697).

N.B.bis : L'utilisation de ord et chr est de mise car on convertit les caractères en nombres avant de leur appliquer une formule mathématique.

def chiffrement_RSA(message, cle_publique):
    ...


def dechiffrement_RSA(message_chiffre):
    ...


message = ...
cle_publique = ...
#tester le chiffement
#tester le déchiffrement

Pour aller plus loin...

Le calcul du reste dans la division euclidienne d'un grand nombre à une puissance donnée peut être très coûteux en temps. Pour éviter ce problème, on décompose le nombre en puissances de 2, en utilisant l'algorithme d'exponentiation modulaire.

Calculons d'abord efficacement \(x^n\), avec l'algorithme d'exponentiation rapide.
Son principe est expliqué ici : https://fr.wikipedia.org/wiki/Exponentiation_rapide

On en propose une version itérative. Vérifier qu'elle fonctionne bien en rajoutant des tests.

def exponentiation_rapide(x, n):
    p = 1
    while n>0:
        if n%2 == 1:
            p = p*x
            n = n-1
        else:
            x = x*x
            n = n//2
    return p

# tests
...

Proposer une version récursive de cet algorithme (correspondant à la description de Wikipédia) :

def exponentiation_rec(x, n):
    ...

Cet algorithme n'est pas exactement celui qu'on recherche : l'adapter pour obtenir ce résultat modulo une valeur \(m\) :

def exponentiation_mod_rec(x, n, m):
    ...

Adapter les fonctions de chiffrement pour utiliser cette fonction calculant l'exponentiation modulaire :

def chiffrement_rsa_rapide(message, cle_publique):
    ...


def dechiffrement_rsa_rapide(message_chiffre):
    ...


message = ...
cle_publique = ...
#tester le chiffement
#tester le déchiffrement