{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"import numpy as np\n",
"import math\n",
"import random\n",
"import time"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# TP5 - Chiffrement asymétrique : RSA \n",
" 2025/2026 - L. Naert, S. Bouchelaghem, T. Godin \n",
"\n",
"_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._"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Usage de l'IA générative : interdit__\n",
"\n",
"\n",
"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 TP précédent, 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. \n",
"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.\n",
"\n",
"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.\n",
"\n",
"## 1 - Principe de la cryptographie asymétrique\n",
"\n",
"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})$\n",
"\n",
"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. \n",
"\n",
"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) :\n",
"$$ c = E_{k_B^{pub}}(m) $$\n",
"\n",
"Bob déchiffrera le chiffré $c$ en utilisant la partie privée de sa clef (qu'il est le seul à connaitre) :\n",
"$$ m = D_{k_B^{priv}}(c)$$\n",
"\n",
"\n",
"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\")\n",
"\n",
"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).\n",
"\n",
"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. \n",
"\n",
"\n",
"_Note_ : A tout moment, vous pouvez réutiliser des fonctions écrites dans les TP précédents."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2 - RSA\n",
"\n",
"RSA propose une application concrète du principe du chiffrement asymétrique en se basant sur la difficulté à factoriser des entiers de grande taille.\n",
"\n",
"Une clef RSA $k = (k^{pub},k^{priv})$ est définie à partie des paramètres suivants : \n",
"- $p$ et $q$ sont deux grands nombres premiers distincts\n",
"- $N = pq$\n",
"- $e$ et $d$ sont des entiers tels que $ed = 1 \\mod \\varphi(N)$ ($d$ est l'inverse de $e$ modulo $\\varphi(N)$)\n",
"\n",
"\n",
"Alors $k^{pub} = (N,e)$ et $k^{priv} = (N,d)$\n",
"\n",
"### a) Indicatrice d'Euler\n",
"\n",
"[_Définition_](https://fr.wikipedia.org/wiki/Indicatrice_d%27Euler) : \n",
"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: \n",
"\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}"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> __Question 1 (indicatrice d'Euler)__ : Calculer à la main $\\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 entier `n` $\\in \\mathbb {N}^{*}$. A quoi est égale l'indicatrice d'Euler d'un nombre premier ?"
]
},
{
"cell_type": "code",
"execution_count": 15,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"phi : OK\n"
]
}
],
"source": [
"import math\n",
"def phi(n):\n",
" res = len([i for i in range(2,n) if math.gcd(i,n)==1])+1\n",
" return res\n",
" \n",
"# Tests\n",
"try:\n",
" assert phi(1) == 1\n",
" # assert phi(4) == #TODO\n",
" # assert phi(11) == #TODO\n",
" assert phi(21) == 12 # Premiers avec 21 : [1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20]\n",
" assert phi(30) == 8 # Premiers avec 30 : [1, 7, 11, 13, 17, 19, 23, 29]\n",
" assert phi(31) == 30 # Premiers avec 31 : Nombres de 1 à 30\n",
" print(\"phi : OK\")\n",
"except:\n",
" print(\"phi : ERREUR\")\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"__Propriété :__ \n",
"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)$\n",
"\n",
"\n",
"> __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\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": []
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"phiPremier : OK\n"
]
}
],
"source": [
"def phiPremier(u,v):\n",
" '''\n",
" u et v sont des nombres premiers\n",
" '''\n",
" return phi(u)*phi(v)\n",
"\n",
"try:\n",
" assert phiPremier(11,31) == 300\n",
" assert phiPremier(17,11) == phi(17*11)\n",
" print(\"phiPremier : OK\")\n",
"except:\n",
" print(\"phiPremier : ERREUR\")\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### b) Clefs RSA\n",
"\n",
"> __Question 3 (Exemple RSA)__ : Prenons $p = 11$, $q = 17$ et $e = 7$. Calculer $k^{pub}$ et $k^{priv}$.\n",
"\n",
"_Rappel_ : A tout moment, vous pouvez réutiliser des fonctions écrites dans les TP précédents."
]
},
{
"cell_type": "code",
"execution_count": 25,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Kpub : (p*q= 187 , e= 7 )\n",
"Kpriv : (p*q= 187 , d= 23 car 7*23 = 161 % phi(187) = 1 avec phi(187)=160)\n"
]
}
],
"source": [
"print(\"Kpub : (p*q=\", 11*17,\", e=\",7,\")\")\n",
"print(\"Kpriv : (p*q=\", 11*17,\", d= 23 car 7*23 = 161 % phi(187) = 1 avec phi(187)=160)\")\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> __Question 4 (Validité)__ : \n",
"- Ecrire une fonction `estPremier(n)` qui vérifie que n (entier strictement positif) est un nombre premier.\n",
"- Ecrire une fonction `estValide(p,q)` qui vérifie que le couple (p,q) est un couple d'entiers valide pour le chiffrement RSA.\n",
"- Ecrire une fonction `choixE(p,q)` qui propose une valeur de $e$ aléatoire pertinente"
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"estPremier : OK\n",
"estValide : OK\n",
"choixE : OK\n"
]
}
],
"source": [
"def listeInversibles(n):\n",
" res = [i for i in range(1,n) if math.gcd(i,n)==1]\n",
" return res\n",
"\n",
"def estPremier(n):\n",
" '''\n",
" n est un entier strictement positif\n",
" '''\n",
" if n <= 1:\n",
" return False\n",
" if n <= 3:\n",
" return True\n",
" if n % 2 == 0:\n",
" return False\n",
"\n",
" limite = int(math.sqrt(n)) + 1\n",
" for i in range(3, limite, 2):\n",
" if n % i == 0:\n",
" return False\n",
" return True\n",
"\n",
"try:\n",
" assert estPremier(1) == False\n",
" assert estPremier(2) == True\n",
" assert estPremier(11) == True\n",
" assert estPremier(17) == True\n",
" assert estPremier(21) == False\n",
" print(\"estPremier : OK\")\n",
"except:\n",
" print(\"estPremier : ERREUR\")\n",
" \n",
" \n",
"def estValide(p,q):\n",
" return p!=q and estPremier(p) and estPremier(q)\n",
"\n",
"\n",
"try:\n",
" assert estValide(11,17) == True\n",
" assert estValide(11,11) == False\n",
" assert estValide(11,21) == False\n",
" print(\"estValide : OK\")\n",
"except:\n",
" print(\"estValide : ERREUR\")\n",
" \n",
"import random\n",
"\n",
"def choixE(p,q):\n",
" z=phiPremier(p,q)\n",
" return random.choice(listeInversibles(z))\n",
" \n",
"try:\n",
" assert choixE(11,17) in listeInversibles(phiPremier(11,17))\n",
" print(\"choixE : OK\")\n",
"except:\n",
" print(\"choixE : ERREUR\")\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> __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 et sinon renvoie un message d'erreur."
]
},
{
"cell_type": "code",
"execution_count": 71,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"([187, 27], [187, 83])\n"
]
}
],
"source": [
"def genPubPriv(p,q):\n",
" if not estValide(p,q) : raise Exception(\"Invalid parameters\")\n",
" n = p*q\n",
" e = choixE(p,q)\n",
" d = [i for i in listeInversibles(phiPremier(p,q)) if i*e%phiPremier(p,q)==1][0]\n",
" return ([n,e],[n,d])\n",
"\n",
"print(genPubPriv(11,17))\n",
"# format de retour souhaité : ([187, 27], [187, 83])"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### c) Chiffrement/Déchiffrement RSA\n",
"\n",
"\n",
"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$\n",
"\n",
"\\begin{align*}\n",
" E_{k^{pub}} \\colon \\mathbb{Z}/N\\mathbb{Z} &\\to \\mathbb{Z}/N\\mathbb{Z}\\\\\n",
" m &\\mapsto c = m^e\n",
"\\end{align*}\n",
"\n",
"\n",
"\n",
"\\begin{align*}\n",
" D_{k^{priv}} \\colon \\mathbb{Z}/N\\mathbb{Z} &\\to \\mathbb{Z}/N\\mathbb{Z}\\\\\n",
" c &\\mapsto m = c^d\n",
"\\end{align*}\n",
"\n",
"\n",
"> __Question 6 (Chiffrement)__ : Ecrire une fonction `chiffrementRSA(msgClair,k_pub)` qui effectue le chiffrement de `msgClair`(de type int) à l'aide de la fonction de chiffrement et de la clef publique donnée (`k_pub` est une liste à deux éléments $N$ et $e$).\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"chiffrementRSA : ERREUR\n"
]
}
],
"source": [
"def chiffrementRSA(msgClair,k_pub):\n",
" return \"todo\"\n",
"\n",
"try:\n",
" assert chiffrementRSA(9,[143, 7]) == 48\n",
" assert chiffrementRSA(89,[143, 7]) == 67\n",
" assert chiffrementRSA(89,[187, 119]) == 166\n",
" print(\"chiffrementRSA : OK\")\n",
"except:\n",
" print(\"chiffrementRSA : ERREUR\")"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> __Question 7 (Déchiffrement)__ : Ecrire une fonction `dechiffrementRSA(msgChiffre,k_priv)` qui effectue le déchiffrement de `msgChiffre`(de type int) à l'aide de la fonction de déchiffrement et de la clef privee donnée (`k_priv` est une liste à deux éléments $N$ et $d$)."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"dechiffrementRSA : ERREUR\n"
]
}
],
"source": [
"def dechiffrementRSA(msgChiffre,k_priv):\n",
" return \"todo\"\n",
"\n",
"try:\n",
" assert dechiffrementRSA(48,[143,103]) == 9\n",
" assert dechiffrementRSA(80,[187, 109]) == 48\n",
" print(\"dechiffrementRSA : OK\")\n",
"except:\n",
" print(\"dechiffrementRSA : ERREUR\")\n",
" "
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"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. \n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"> __Question 8 (p et q grands)__ : Tester la génération de clefs publique et privée, le chiffrement et le déchiffrement d'un message avec des valeurs de $p$ et $q$ à 2, 3 et 4 chiffres. __Dans chacun des cas__, utilisez la fonction time.time() pour chronométrer la durée de :\n",
"> 1) la génération des clefs\n",
"> 2) le chiffrement RSA d'un nombre < n\n",
"> 3) le déchiffrement RSA du chiffré créé à l'étape précédent\n",
"> \n",
"> Que remarquez-vous ?"
]
},
{
"cell_type": "code",
"execution_count": 29,
"metadata": {},
"outputs": [
{
"ename": "NameError",
"evalue": "name 'time' is not defined",
"output_type": "error",
"traceback": [
"\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
"\u001b[1;31mNameError\u001b[0m Traceback (most recent call last)",
"Cell \u001b[1;32mIn[29], line 2\u001b[0m\n\u001b[0;32m 1\u001b[0m \u001b[38;5;66;03m#Exemple à remplir pour des premiers de 2 chiffres\u001b[39;00m\n\u001b[1;32m----> 2\u001b[0m start \u001b[38;5;241m=\u001b[39m \u001b[43mtime\u001b[49m\u001b[38;5;241m.\u001b[39mtime()\n\u001b[0;32m 3\u001b[0m \u001b[38;5;66;03m#generation de clef\u001b[39;00m\n\u001b[0;32m 4\u001b[0m end \u001b[38;5;241m=\u001b[39m time\u001b[38;5;241m.\u001b[39mtime()\n",
"\u001b[1;31mNameError\u001b[0m: name 'time' is not defined"
]
}
],
"source": [
"#Exemple à remplir pour des premiers de 2 chiffres\n",
"start = time.time()\n",
"#generation de clef\n",
"end = time.time()\n",
"print(\"Temps de generation pour des premiers à 2 chiffres : \", end - start, \"secondes\")\n",
"#affichage de la clef\n",
"\n",
"start = time.time()\n",
"#chiffrement\n",
"end = time.time()\n",
"print(\"Temps de chiffrement pour des premiers à 2 chiffres : \", end - start, \"secondes\")\n",
"#affichage du chiffré\n",
"\n",
"start = time.time()\n",
"#dechiffrement\n",
"end = time.time()\n",
"print(\"Temps de dechiffrement pour des premiers à 2 chiffres : \", end - start, \"secondes\")\n",
"#affichage du clair"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"-------\n",
"\n",
"__Activité :__\n",
"La bibliotheque existante cryptography (pip install cryptography) 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. Exécutez les cellules ci-dessous pour générer des clefs de chiffrement, chiffrer et déchiffrer un message. \n",
"Envoyez votre clef publique (voir doc [serialization](https://cryptography.io/en/latest/hazmat/primitives/asymmetric/rsa/#key-serialization)) à votre binome pour qu'il vous envoie un message chiffré et déchiffrez-le (et vice-versa)."
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#!pip install cryptography\n",
"from cryptography.hazmat.primitives.asymmetric import rsa, padding\n",
"from cryptography.hazmat.primitives import hashes, serialization\n",
"\n",
"\n",
"#Génération des clefs\n",
"private_key = rsa.generate_private_key(\n",
" public_exponent=65537,\n",
" key_size=2048\n",
")\n",
"public_key = private_key.public_key()"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#chiffrement (le padding ajoute des bits de façons à mettre le message dans le bon format pour être chiffré)\n",
"\n",
"messageClair = b\"message a chiffrer\"\n",
"ciphertext = public_key.encrypt(messageClair,\n",
" padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()), algorithm=hashes.SHA256(), label=None))\n",
"\n",
"print(ciphertext)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"#dechiffrement\n",
"dechiffre = private_key.decrypt(ciphertext, \n",
" padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),algorithm=hashes.SHA256(),label=None))\n",
"\n",
"print(dechiffre)\n",
"print(dechiffre == messageClair)"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.6"
}
},
"nbformat": 4,
"nbformat_minor": 4
}