C15 Sécurisation des communications

Ce cours s'inspire largement de celui de G. Lassus (merci pour les illustrations)

Activités

Activité 1 : Chiffrement symétrique

Opération xor
En Python, on peut effectuer un ou exclusif bit à bit sur les représentations binaires de deux entiers à l'aide de l'opérateur ^. Par exemple pour effectuer 28 ^ 42:
- Convertir 28 en binaire : \((28)_{10} = (11100)_2\)
- Convertir 42 en binaire : \((42)_{10} = (101010)_2\)
- Effectuer un xor bit à bit :
  En effet, on rappelle que \(A \bigoplus B\) vaut 1 lorsque \(A\) ou \(B\) vaut 1 mais pas les deux à la fois (d'où le nom ou exclusif)
- Convertir le résultat en entier : \((110110)_2 = (54)_{10}\)
  
  a. Vérifier en utilisant Python, qu'on obtient bien 28 ^ 42 = 54
  
  b. Comme dans l'exemple ci-dessus, calculer 65 ^ 42, vérifier votre résultat avec Python.
  
  c. Calculer (65 ^ 42)^42, que remarquez-vous ?
  
  d. A l'aide d'un programme Python, vérifier que pour tout entier n compris entre 0 et 255, on a : (n ^ 42) ^ 42 = n
  
  Note
  
  On admet, sans démonstration que l'opération xor est symétrique c'est à dire que pour tout entier n et m : (n ^ m) ^ m = n.
Chiffrement avec xor
On décide d'utiliser l'opération xor pour chiffrer un message, on choisit un entier compris entre 0 et 255 qui sert de clé de chiffrement. Pour chiffrer un message, on effectue un xor entre le code ascii de chaque caractère du message et la clé de chiffrement. Par exemple, pour coder le mot NSI avec la clé 42 :
- On récupère les codes ascii de chaque lettre : N : 78, S : 83 et I : 73.
- On effectuer un xor avec la clé de chiffrement 42 : 78^42 = 100, 83^42 = 121, 73 ^ 42 = 99
- On remplace avec le caractère ayant ce code ascii : 100 : d, 121 : y, 99 : c
- Le chiffrement de NSI est donc dyc
  
  a. Ecrire une fonction python chiffre_xor qui prend deux arguments (le texte à chiffrer et la clé de chiffrement) et renvoie le message chiffré. Par exemple chiffre_xor("NSI",42) doit renvoyer dyc.
  Aide
  
  On rappelle qu'en python :
  - la fonction ord renvoie le code ascii du caractère donné en paramètre. Par exemple, ord("N") renvoie 78.
  - la fonction chr renvoie le caractère dont le code ascii est donné en paramètre. Par exemple, chr(100) renvoie d.
  b. Expliquer et justifier comment peut s'effectuer le déchiffrage d'un message avec cette technique. Quelle est la clé de déchiffrement ?
  
  c. Déchiffrer le message qARE\E\F@REVIAÚF@@Z sachant que la clé de chiffrement était 51.
  
  d. Un chiffrage est dit symétrique lorsque les clés de chiffrement et de de déchiffrement doivent être secrètes (elles peuvent donc être identiques ou alors la connaissance de l'une permet aisément d'obtenir l'autre). Le chiffrement par xor défini ci-dessus est-il symétrique ?
  
  e. Le chiffrement par le code de César est-il symétrique ?
  
  f. Dans le cas d'un chiffrement symétrique, deux personnes peuvent-elles s'échanger des messages si elles n'ont pas encore convenu ensemble d'une clé de chiffrement ? En déduire un inconvénient de cette méthode de chiffrement.
Note

Pour prolonger cette activité on pourra faire l'exercice 3 de ce sujet de Bac 2021 dont la correction se trouve ici. En effet, cet exercice traite du chiffrement par xor en utilisant une chaîne de caractère comme clé.

Activité 2 : Chiffrement asymétrique

Dans un chiffrement asymétrique, la clé de chiffrement est publique et donc n'importe qui peut chiffrer un message. La clé de déchiffrement est par contre privée (et seul celui qui la possède peut déchiffrer). Le principe est donc qu'on ne peut pas (ou pas "facilement") déduire de la clé de chiffrement (publique), la clé de déchiffrement (secrète). Le principe d'un chiffrement asymétrique est illustré ci-dessous (crédit : G. Lassus): Dans cette activité, après quelques rappels mathématiques, nous allons détailler chacune de ses étapes sur un exemple très connu de chiffrement asymétrique : l'algorithme RSA des initiales de ses trois inventeurs (Ron Rivest, Adi Shamir et Leonard Adelman). Pour plus de détails historique, voir par exemple ce site

Attention

La compréhension de l'algorithme demande des notions d'arithmétique qui pourront sembler ardues aux élèves ne faisant pas l'enseignement de spécialités mathématiques. Ces prérequis, sont présentés en début d'activité. On pourra simplement retenir pour résumer et façon imparfaite que dans le chiffrement RSA :

la clé publique est un très grand nombre \(n\) (plusieurs centaines de chiffres) choisi de façon à être le produit de deux nombres premiers,
la clé privée est le couple \((p,q)\) de nombres premiers tels que \(n=p\times q\),
étant donnée la taille de \(n\), il est difficile (impossible avec la puissance de calcul actuelle des ordinateurs) de retrouver \(p\) et \(q\) à partir de \(n\). Et donc la connaissance de la clé publique ne permet pas d'en déduire celle de la clé privée.

Arithmétique modulaire
a. Il est 22h, quelle heure sera-t-il 8h plus tard ?

b. Si vous avez répondu 6h (et pas 30h à la question précédente), vous venez de faire de l'arithmétique modulaire, en effet vous n'avez conservé que le reste dans la division euclidienne par 24:
\(30 = 1 \times 24 + 6\) on écrira que \(30 \equiv 6 [24]\) et on lira \(30\) est égal à \(6\) modulo \(24\) (ce qui peut se traduire par leur différence est un multiple de 24, c'est donc la même heure sur des jours différents).

c. Vérifier (en faisant la division euclidienne) que \(42 \equiv 18 [24]\)

d. Vérifier (en faisant la division euclidienne) que \(103 \equiv 7 [24]\)

e. Compléter : \(13 \equiv \dots [5]\)

f. Compléter : \(42 \equiv \dots [7]\)
Nombres premiers et nombres premiers entre eux.

a. Rappeler la définition d'un nombre premier. Les nombres suivants sont-ils premiers (justifier) : 12, 21, 29, 1 ?

b. On dit que deux nombres sont premiers entre eux lorsque leur pgcd vaut 1, par exemple 12 et 5 sont premiers entre eux mais pas 33 et 27 (leur pgcd vaut 3). Donner la liste des nombres premiers avec 12 et inférieurs à 12.
Algorithme RSA - étape 1 : création de la clé publique et de la clé privée
- Choisir deux nombres premiers \(p\) et \(q\) très grands. Pour disposer d'un exemple simple nous prendrons \(p=3\) et \(q=11\)
- Calculer le produit \(n = p\times q\). Dans notre exemple \(n = 3 \times 11 = 33\).
- Choisir un nombre premier \(e\) premier avec \(\phi(n) = (p-1)(q-1)\). Dans notre exemple, on choisit \(e=3\) qui est bien premier avec \(20\) (comme \(p=3\) et \(q=11\), \(\phi(33)=(p-1)(q-1)=20\)).
- La clé publique d'Alice est le couple \((e,n)\) et donc dans notre exemple le couple \((3,33)\). Rappelons que dans la réalité \(n\) est un nombre très grand.
- Pour déterminer la clé privé, il faut trouver un nombre \(d\) tel que \(ed \equiv 1 [\phi(n)]\). Dans notre exemple il s'agit donc de trouver \(d\) tel que \(3d \equiv 1 [20]\), le nombre 7 convient.
  
  Note
  
  On dit que \(d\) est un inverse de \(e\) modulo \(\phi(n)\) (leur produit vaut 1 modulo \(\phi(n)\)). Dans la pratique un algorithme permet la détermination de \(d\).
- Le couple \((d,n)\) est la clé privée qui permet le déchiffrage. Dans notre exemple c'est donc \((7,33)\).
Soit le couple de nombre premiers \((p,q)\) avec \(p=5\) et \(q=13\) :

a. Calculer \(n\) et \(\phi(n)\).

b. Justifier que \((9,65)\) ne peut pas être une clé publique.

c. Vérifier que \((11,65)\) est une clé publique.

d. Vérifier que 35 est un inverse de 11 modulo 48.

e. En déduire la clé privée.

Important

En résumé, la clé publique est \((e,n)\) et la clé publique est \((d,n)\). Puisque \(d\) et \(e\) sont inverses l'un de l'autre modulo \(\phi(n)=(p-1)(q-1)\) on peut penser qu'il est simple de retrouver l'un à partir de l'autre, dans la pratique cela est extrêmement difficile car on ne connaît pas \(\phi(n)\). En effet, \(n\) étant très grand, il est difficile de calculer \(p\) et \(q\), car il n'existe pas d'algorithme efficace permettant de factoriser des nombres possédant plusieurs centaines de chiffres.
Algorithme RSA - étape 2 : chiffrer un message
Pour envoyer un nombre secret \(S\) en le chiffrant avec l'algorithme RSA de clé publique \((e,n)\), il faut calculer \(S^e [n]\). Rappelons que dans notre exemple la clé publique pour chiffrer est \((3,33)\). Par exemple, pour envoyer le nombre secret 4, on calcule \(4 ^ 3 [33] = 31\) et on envoie 31.

a. Chiffrer le nombre secret 10 avec la clé \((3,33)\)

b. Chiffrer le nombre secret 17 avec la clé \((11,65)\)
Algorithme RSA - étape 3 : déchiffrer un message
Pour déchiffrer un message \(M\) de clé privée \((d,n)\) il suffit de l'élever à la puissance \(d\) et de calculer le reste dans la division euclidienne par \(n\). Rappelons que dans notre exemple exemple \(d=7\) et \(n=33\). Si on reçoit le le message \(M = 31\) on doit calculer : \(31^7 = 27512614111\) puis chercher le reste modulo 33 : \(27512614111 [33] = 4\), on retrouve bien le message de départ qui était 4.

Note

Cela repose sur le résultat suivant : si \(e\) et \(d\) sont inverses modulo \(\phi(n)\) alors \(M^{ed} \equiv M [n]\). Pour une démonstration, on pourra consulter cette page

a. Déchiffrer le nombre secret 18 avec la clé \((7,33)\).

b. Même question pour le nombre secret 90 avec la clé \((11,65)\).
Vous pouvez utiliser cet outil en ligne afin de vérifier vos réponse à cette activité.

Important

Le protocole https qui permet de sécuriser les transmissions sur le Web utilise à la fois :

un chiffrement asymétrique pour la génération de clés de chiffrement identiques chez le serveur et le client
un chiffrement symétrique (aujourd'hui AES) pour l'échange des données.

Voir cette page pour plus de détails.

Cours

Vous pouvez télécharger une copie au format pdf du diaporama de synthèse de cours présenté en classe :

Diaporama de cours

Attention

Ce diaporama ne vous donne que quelques points de repères lors de vos révisions. Il devrait être complété par la relecture attentive de vos propres notes de cours et par une révision approfondie des exercices.

Exercices

Exercice 1 : Vocabulaire

Expliquer en quelques phrases la différence entre un chiffrement symétrique et un chiffrement asymétrique.
Donner un exemple de chiffrement symétrique.
Donner un exemple de chiffrement asymétrique.

Exercice 2 : Chiffre de César

Rappeler le principe du chiffrement de César
Ecrire en Python, une fonction chiffre_cesar qui prend en argument un texte et une clé de chiffrement c et renvoie le texte chiffré par la méthode de César avec un décalage de c emplacements. Par souci de simplicité, on supposera que le texte n'est composé que des 26 lettres majuscules de l'alphabet et on ne chiffre ni les espaces ni les symboles de ponctuation.
Aide

On rappelle qu'en python :
- la fonction ord renvoie le code ascii du caractère donné en paramètre. Par exemple, ord("N") renvoie 78.
- la fonction chr renvoie le caractère dont le code ascii est donné en paramètre. Par exemple, chr(100) renvoie d.
- n%26 donne le reste dans la division euclidienne de n par 26.
Le chiffre de César peut-être cassé par analyse fréquentielle, comme expliqué ci-dessous :
En utilisant cette technique, écrire un programme Python permettant de déchiffrer le message suivant :
```
PFOJC JCIG OJSN FSIGGW O RSQCRSF QS ASGGOUS
Q SGH HFSG PWSB AOWG WZ FSGHS SBQCFS PSOIQCID O TOWFS
```
Décoder de nouveau le message précédent en utilisant la bibliothèque sympy

Exercice 3 : Factorisation

On rappelle que la fiabilité de l'algorithme rsa est lié à la difficulté de trouver en connaissant un nombre \(n\) les deux nombres premiers \(p\) et \(q\) tels que \(n = pq\). Cet exercice a pour but de le vérifier. Le module Crypto de python permet de générer des nombres premiers de n'importe quelle taille :

from Crypto.Util import number
from Crypto.Random import get_random_bytes 

# Taille des nombres (en bits)
n_length = 20

# Génération de deux nombres premiers p et q de cette taille
p = number.getPrime(n_length,randfunc=get_random_bytes)
q = number.getPrime(n_length,randfunc=get_random_bytes)

Recopier ce programme, le tester et le compléter afin de calculer \(n = pq\).
Ecrire une fonction factorise qui prend en argument un entier n et renvoie deux entiers p et q tels que n = p*q.

Aide

On pourra utiliser l'algorithme très simple qui consiste à essayer toutes les divisions possibles jusqu'à en trouver une dont le reste est 0.
Tester votre fonction factorise et vérifier qu'elle permet de retrouve p et q à partir de n
Modifier la valeur du paramètre n_length et mesurer les temps d'execution.

Attention

Ne pas choisir une valeur trop élevé pour n_length, prendre par exemple 21 puis 22, 23, ... et observer l'augmentation correspondante du temps de calcul.
Prévoir le temps d'execution pour n_length = 100
La majorité des sites Web actuel utilise actuellement des clés de longueur 1024. Quel serait le temps d'exécution prévisible de votre programme pour casser une de ces clés ?

Lien

La vidéo ci-dessous revient sur l'algorithme RSA et donne les longueurs des plus longues clés cassées à ce jour.

Exercice 4 : Autorité de certification

Comme vu en cours, une autorité de certification assure de l'identité d'un site afin d'éviter des attaques du type homme du milieu, sans laquelle on pourrait se connecter à un site tiers en pensant qu'il s'agit par exemple de sa banque en ligne. Les requêtes https peuvent être observées à partir de la console de firefox. Pour cela :

Lancer Firefox et ouvrir la console (menu outils supplémentaires > console du navigateur ou avec le raccourci clavier Ctrl+Shift+J) et sélectionner l'onglet Requêtes (à droite)
Dans la barre d'adresse du navigateur taper wikipedia.fr, les requêtes défilent dans la console, cliquer sur la requête : GET https://www.wikipedia.fr puis l'onglet sécurité à droite. Retrouver les informations suivantes :
- La version du protocole TLS utilisé
- Le nom de l'autorité de certification
- La période de validité du cerfificat d'identité

Exercice 5 : Implémentation de l'algorithme RSA

On rappelle que l'algorithme rsa impose de trouver l'inverse d'un nombre \(d\) modulo \(\phi(n)\). Cela peut être fait en utilisant l'algorithme d'Euclide étendu

Proposer une implémentation en Python de cet algorithme.
Proposer une implémentation en Python de l'algorithme de chiffrement rsa