Certains exemples et textes de ce TP sont tirés de Exercices et Problèmes de cryptographie de Damien Vergnaud, 3ème édition ainsi que de Codes et Cryptologie de Christine Bachoc.
import numpy as np
import math
import random
import time
Jusqu'à maintenant, nous n'avions vu en TP que des méthodes de cryptographie symétrique dans lesquelles la clef de chiffrement sert également de clef de déchiffrement et doit donc rester secrète pour pouvoir garantir la confidentialité des messages. Vous avez pu, au TP3, transmettre un message chiffré à votre voisin(e). Pour que celui/celle-ci puisse le déchiffrer, vous avez également dû lui fournir la clef de chiffrement ou, dans le cas plus précis du LFSR, les informations permettant à votre voisin(e) de calculer la clef de chiffrement. C'est ce que l'on appelle l'échange des clefs. Il s'agit d'un problème crucial dès que l'on utilise une technique de chiffrement symétrique. Si Alice veut envoyer un message à Bob sans que celui-ci puisse être lu par Oscar, elle ne peut pas envoyer à la fois le message et la clef puisque, si Oscar intercepte ces informations, il sera en mesure de lire le message. Il est donc necessaire de définir un protocole d'échange de clef.
La cryptographie asymétrique, aussi appelé cryptographie à clef publique (à opposer à la cryptographie symétrique/à clef secrete), permet de résoudre la problématique le l'échange de clef.
Dans un système de cryptographie asymétrique, les interlocuteurs possèdent chacun une clef composée de deux parties : une partie publique que tout le monde est en mesure de voir et une partie privée que seul le propriétaire de la clef connait. Ainsi, si l'on considère deux protagonistes Alice et Bob, Alice possède une clef $k_A = (k_A^{pub},k_A^{priv})$ et Bob possède une autre clef $k_B = (k_B^{pub},k_B^{priv})$
La fonction de chiffrement $E$ est paramétrée par la partie publique de la clef du destinataire tandis que la fonction de déchiffrement $D$ est paramétrée par la partie privée de la clef du destinataire.
Ainsi, si Alice souhaite envoyer un message à Bob, elle chiffre son message $m$ en utilisant la partie publique de la clef de Bob (aucun problème puisque tout le monde à accès aux clefs publiques) : $$ c = E_{k_B^{pub}}(m) $$
Bob déchiffrera le chiffré $c$ en utilisant la partie privée de sa clef (qu'il est le seul à connaitre) : $$ m = D_{k_B^{priv}}(c)$$
Ainsi tout le monde peut écrire des messages à Bob en utilisant la clef publique de Bob mais seul Bob peut les déchiffrer grâce à sa clef privée. (Par abus de langage, on dit souvent "clef privée (resp. publique)" au lieu de "la partie privée (resp. publique) de la clef")
Pour que ce système fonctionne, il faut que la partie publique et la partie privée de la clef permettent de définir des opérations $E$ et $D$ réciproques ($ D_{k^{priv}} = E_{k^{pub}}^{-1}$) et que le calcul de la clef privée de quelqu'un connaissant sa clef publique soit impossible (ou, plus justement, infaisable dans des temps raisonnables).
Ce principe de la cryptographie asymétrique a été formalisé par Diffie et Hellmann en 1976 mais aucune solution concrète n'avait été proposée à ce moment. Il a fallu attendre le chiffrement RSA, proposé par Rivest, Shamir et Adleman un an plus tard pour pouvoir implémenter le chiffrement asymétrique.
RSA propose une application concrète du principe du chiffrement asymétrique en se basant sur la difficulté à factoriser des entiers de grande taille.
Une clef RSA $k = (k^{pub},k^{priv})$ est définie à partie des paramètres suivants :
Alors $k^{pub} = (N,e)$ et $k^{priv} = (N,d)$
Définition : On appelle indicatrice d'Euler, notée $\varphi$, la fonction, qui à tout entier naturel $n$ non nul associe le nombre d'entiers compris entre $1$ et $n$ (inclus) et premiers avec n:
\begin{array}{ccccl}\varphi &:&\mathbb {N} ^{*}&\longrightarrow &\mathbb {N} ^{*}\\&&n&\longmapsto &\mathrm {card} (\{m\in \mathbb {N} ^{*}~|~m\leqslant n~{\text{et}}~pgcd (m,n) = 1\}).\end{array}Note : ne pas confondre "nombre premier avec n" et "nombre premier" ! $5$ est un nombre premier mais $5$ n'est pas premier avec $30$. $10$ n'est pas premier mais $10$ est premier avec $11$
Question 1 (indicatrice d'Euler) : Calculer à la main $\varphi(1)$, $\varphi(4)$ et $\varphi(11)$ et complétez la partie "tests" de la cellule ci-dessous avec vos résultats. Ecrire une fonction
phi(n)qui calcule l'indicatrice d'Euler d'un entiern$\in \mathbb {N}^{*}$. A quoi est égale l'indicatrice d'Euler d'un nombre premier ?
Note : A tout moment, vous pouvez réutiliser des fonctions écrites dans les TP précédents.
def phi(n):
return "TODO"
# Tests
try:
assert phi(1) == #TODO
assert phi(4) == #TODO
assert phi(11) == #TODO
assert phi(21) == 12 # Premiers avec 21 : [1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20]
assert phi(30) == 8 # Premiers avec 30 : [1, 7, 11, 13, 17, 19, 23, 29]
assert phi(31) == 30 # Premiers avec 31 : Nombres de 1 à 30
print("phi : OK")
except:
print("phi : ERREUR")
Propriété : Pour tout $u$, $v \in \mathbb {N}^{*} $ tels que $u$ et $v$ sont premiers entre eux (i.e. $pgcd(u,v) = 1$), $\varphi (uv) = \varphi (u)\varphi (v)$
Question 2 (indicatrice d'Euler pour la multiplication de nombres premiers) : A quoi est égal $\varphi (uv)$ avec $u$ et $v$ premiers ? Coder la fonction
phiPremier(u,v)qui calcule $\varphi (uv)$ avec $u$ et $v$ premiers
Solution :
def phiPremier(u,v):
'''
u et v sont des nombres premiers
'''
return "TODO"
try:
assert phiPremier(11,31) == 300
assert phiPremier(17,11) == phi(17*11)
print("phiPremier : OK")
except:
print("phiPremier : ERREUR")
Question 3 (Exemple RSA) : Prenons $p = 11$, $q = 17$ et $e = 7$. Calculer $k^{pub}$ et $k^{priv}$.
N = "TODO"
e = "TODO"
d = "TODO"
print("kpub = (" + str(N) + "," + str(e) + ")" )
print("kpriv = (" + str(N) + "," + str(d) + ")")
Question 4 (Validité) :
- Ecrire une fonction
estPremier(n)qui vérifie que n (entier strictement positif) est un nombre premier.- Ecrire une fonction
estValide(p,q)qui vérifie que le couple (p,q) est un couple d'entiers valide pour le chiffrement RSA.- Ecrire une fonction
choixE(p,q)qui propose une valeur de e pertinente
def estPremier(n):
'''
n est un entier strictement positif
'''
return "TODO"
try:
assert estPremier(1) == True
assert estPremier(2) == True
assert estPremier(11) == True
assert estPremier(17) == True
assert estPremier(21) == False
print("estPremier : OK")
except:
print("estPremier : ERREUR")
def estValide(p,q):
return "TODO"
try:
assert estValide(11,17) == True
assert estValide(11,11) == False
assert estValide(11,21) == False
print("estValide : OK")
except:
print("estValide : ERREUR")
def choixE(p,q):
return "TODO"
try:
assert choixE(11,17) in listeInversibles(phiPremier(11,17))
print("choixE : OK")
except:
print("choixE : ERREUR")
Question 5 (RSA) : Ecrire une fonction
genPubPriv(p,q)qui, si le couple (p,q) est valide, renvoie une proposition de clef publique/clef privée.
def genPubPriv(p,q):
return "TODO"
print(genPubPriv(11,17))
Un attaquant, pour déterminer $k^{priv}$ aura accès à $k^{pub}$, c'est à dire à $N$ et $e$. Or, pour calculer le $d$ de $k^{priv}$, il aura besoin de calculer $\varphi(N)$ : soit en trouvant les deux facteurs premiers $p$ et $q$ de $N$, soit en comptant le nombre de nombres premiers avec $N$. Ces opérations sont difficiles voire impossibles à réaliser en temps raisonnable par des méthodes connues actuellement pour des grands entiers (longueur de $p$ et $q$ supérieure à 512 bits). C'est là où réside la force du chiffrement asymétrique RSA.
Voici les fonctions de chiffrement $E_{k^{pub}}$ et déchiffrement $D_{k^{priv}}$ pour RSA. Remarquez que les messages à chiffrer/déchiffrer sont des éléments de $\mathbb{Z}/N\mathbb{Z}$ avec $N=pq$
\begin{align*} E_{k^{pub}} \colon \mathbb{Z}/N\mathbb{Z} &\to \mathbb{Z}/N\mathbb{Z}\\ m &\mapsto c = m^e \end{align*}\begin{align*} D_{k^{priv}} \colon \mathbb{Z}/N\mathbb{Z} &\to \mathbb{Z}/N\mathbb{Z}\\ c &\mapsto m = c^d \end{align*}Question 6 (Chiffrement) : Ecrire une fonction
chiffrementRSA(msgClair,k_pub)qui effectue le chiffrement demsgClair(de type int) à l'aide de la fonction de chiffrement et de la clef publique donnée (k_pubest une liste à deux éléments $N$ et $e$).
def chiffrementRSA(msgClair,k_pub):
return "TODO"
try:
assert chiffrementRSA(9,[143, 7]) == 48
assert chiffrementRSA(89,[143, 7]) == 67
assert chiffrementRSA(89,[187, 119]) == 166
print("chiffrementRSA : OK")
except:
print("chiffrementRSA : ERREUR")
Question 7 (Déchiffrement) : Ecrire une fonction
dechiffrementRSA(msgChiffre,k_priv)qui effectue le déchiffrement demsgChiffre(de type int) à l'aide de la fonction de déchiffrement et de la clef privee donnée (k_privest une liste à deux éléments $N$ et $d$).
def dechiffrementRSA(msgChiffre,k_priv):
return "TODO"
try:
assert dechiffrementRSA(48,[143,103]) == 9
assert dechiffrementRSA(80,[187, 109]) == 48
print("dechiffrementRSA : OK")
except:
print("dechiffrementRSA : ERREUR")
Encore une fois, on peut remarquer que l'attaquant a besoin du $d$ de $k^{priv}$ pour déchiffrer le message. Cette clef ne peut être calculée qu'en factorisant $N$ en ses deux facteurs premiers $p$ et $q$ (ou en calculant directement $\varphi(N)$, opération tout aussi compliquée pour des grands nombres $N$). En pratique les nombres premiers $p$ et $q$ doivent être très grands pour que la factorisation de $N$ soit une opération impossible en temps raisonnable.
Question 8 (p et q grands) : Tester la generation de clefs publique et privée, le chiffrement et le déchiffrement d'un message avec des valeurs de $p$ et $q$ plus importantes (à 4 chiffres par exemple). Que remarquez-vous ?
Le chiffrement RSA, et les chiffrements asymétriques en général, permettent de résoudre le problème de l'échange des clefs du chiffrement symétrique puisque plus aucun échange n'est nécessaire. Cependant, ces types de chiffrement ne peuvent pas se substituer complètement aux chiffrements symétriques car les opérations de chiffrement et déchiffrement prennent trop de temps pour être utilisées régulièrement pour coder de longs messages. Les chiffrements symétriques et asymétriques sont donc souvent tous les deux utilisés pour chiffrer un message :
Activité (synthèse) :
- Chiffrez un message en utilisant un masque jetable généré de façon pseudo-aléatoire (cf. TP3) et envoyez à votre voisin(e) le message chiffré.
- Demander ensuite à votre voisin(e) de générer sa clef RSA (à partir de nombres premiers de 3 chiffres) et de vous transmettre la partie publique de cette clef. Servez-vous de celle-ci pour lui transmettre de manière confidentielle la clef secrete de votre masque.
- Votre voisin(e) arrive t-il à déchiffrer votre message ?
Chaque étudiant doit réaliser un chiffrement et un déchiffrement !
Remarque : le module existant Crypto.RSA de Python permet de générer des clefs d'une taille spécifiée, de chiffrer et déchiffrer des messages de manière plus efficace.
(pip install crypto)