{ "cells": [ { "cell_type": "markdown", "id": "791d5696-8ab1-4678-81ee-1bb4b2516a60", "metadata": {}, "source": [ "# Chiffrement asymétrique El Gamal\n", "Le chiffrement d'El Gamal est un protocole de cryptographie asymétrique\n", "inventé par Taher El Gamal en 1984 et qui repose sur le problème du\n", "logarithme discret." ] }, { "cell_type": "markdown", "id": "c71f661e-3f98-4774-9624-4d04f02a7750", "metadata": { "jp-MarkdownHeadingCollapsed": true }, "source": [ "## Génération des clés\n", "Pour générer sa paire de clés, il faut d'abord choisir un nombre **premier** et un générateur $g$ pour ${\\mathbb Z}/p{\\mathbb Z}$. Ensuite il faut choisir un élément $\\mathsf{s}$ de ${\\mathbb Z}/p{\\mathbb Z}$ qui\n", "constituera la clé privée, et calculer $h=g^{s} \\mod p$. Pour terminer, \n", "la clé publique est $(p,g,h)$." ] }, { "cell_type": "markdown", "id": "92cd1679-59c5-4304-a7af-aac521419c9d", "metadata": { "jp-MarkdownHeadingCollapsed": true }, "source": [ "## Chiffrement\n", "Pour chiffrer un message $M$ encodé comme un entier de ${\\mathbb Z}/p{\\mathbb Z}$ avec la clé publique $(p,g,h)$ il faut tirer au hasard un aléa $r$ dans ${\\mathbb Z}/p{\\mathbb Z}$ et calculer $C_1=g^r \\mod p$ et $C_{2}=(M\\cdot (h^{r}\\mod p)) \\mod p$. Ainsi le chiffré $C$ est composé de ces deux nombres : $$C=(C_{1},C_{2})$$" ] }, { "cell_type": "markdown", "id": "e9ba3635-ecba-47f2-a01e-dd8db83acac6", "metadata": {}, "source": [ "## Déchiffrement\n", "Ayant accès à $C=(C_{1},C_{2})$ et à la clé privée $s$, pour\n", "déchiffrer il suffit de calculer : $$ \\left(C_{2} \\times \\left((C_{1})^{s}\\mod p\\right)^{-1} \\mod p\\right)\\mod p$$ \n", "\n", "pour retrouver le message $M$. " ] }, { "cell_type": "markdown", "id": "c39a1704-2ddf-4049-a340-8c332b98fef0", "metadata": {}, "source": [ "### Q. Génération des clés\n", "Ecrivez une fonction `Sage` **Clefs(k)** qui permet de générer une paire de clefs El Gamal, avec un module compris entre $2^k$ et $2^{k+1}-1$.\n", "\n", "La taille compte ! Plus vos clés seront de grands nombres, plus elles seront sûres. Le \"paramètre de sécurité\" est donc le nombre de bits du module $p$, autrement dit son logarithme binaire $k$. \n", "\n", "Vous aurez peut-être l'usage de la fonction `random_prime` et de la fonction `randint` (on donne un exemple d'utilisation ci-dessous). Pour calculer $x^n \\mod p$ vous devrez utiliser `pow(x, n, mod=p)` car `(x**n)\\%p` ne marche pas pour les grands nombres.\n", "\n", "1) Choisissez comme module un nombre premier $p$ au hasard compris entre $2^k$ et $2^{k+1}-1$.\n", "2) Choisissez comme générateur un nombre $g$ au hasard compris entre $2$ et $p-1$. (Votre générateur n'en est peut-être pas un. Pour gagner du temps, on ne vous demande pas de le vérifier : la procédure de chiffrement/déchiffrement marche encore, mais votre clé sera plus facile à casser, car il y aura plusieurs valeurs possibles pour $s$, en plus de celle qui sera vraiment votre clé secrète.)\n", "3) Choisissez comme secret un nombre $s$ au hasard compris entre $2$ et $p-1$.\n", "4) Calculez $h$." ] }, { "cell_type": "code", "execution_count": 26, "id": "10095820-c4f7-4404-bbed-77ea03e1533a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p = random_prime(200, lbound=100)\n", "p.is_prime()\n", "100 <= p <= 200" ] }, { "cell_type": "code", "execution_count": 27, "id": "028dab7d-40d9-46fe-82c4-897ba9645372", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "4" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "x=randint(2,10)\n", "x" ] }, { "cell_type": "markdown", "id": "ae5c050e-d3b6-4207-9ebd-4410637ad623", "metadata": {}, "source": [ "### Q. Chiffrer un message\n", "Ecrivez une fonction `Sage` **Chiffrer(...)** qui permet de chiffrer un nombre $M$ avec le chiffrement d'El Gamal. Tester votre fonction avec $k=8$ et $M=1000$." ] }, { "cell_type": "code", "execution_count": null, "id": "10cb26d2-4a6d-45bb-a6a3-e04d5c0970ec", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "32d94b77-92ab-4f56-8317-005e7575f178", "metadata": {}, "source": [ "### Q. Déchiffrer un message\n", "Ecrivez une fonction `Sage` **Dechiffrer(...)** qui permet de déchiffrer un chiffré $(C_1,C_2)$ avec le chiffrement d'El Gamal. Tester votre fonction avec les valeurs précédentes.\n", "\n", "Vous pouvez calculer l'inverse de $x$ modulo $p$ (s'il existe) par `pow(x, -1, p)`.\n" ] }, { "cell_type": "code", "execution_count": null, "id": "35bce462-a7c6-405a-8e86-9bca67d03b84", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "ae2f7e9a-6bfd-40ce-9fca-d0e908eb68fb", "metadata": {}, "source": [ "### Encodage de messages\n", "Fondamentalement, le chiffrement d'El Gamal s'applique à des nombres. Mais très souvent, les messages qu'on souhaite chiffrer sont plutôt des _textes_ !\n", "Pour chiffrer des textes, il faut donc passer par une étape préalable de _numérisation_ des caractères qui le composent.\n", "\n", "1) Ecrivez une fonction `Sage` **Encode(texte)** qui convertit une chaîne de\n", "caractères _texte_ en un nombre entier.\n", "Il y a plusieurs manières de faire cela, voici celle que nous proposons ici :\n", " - Chaque caractère est encodé par son code ASCII décimal, composé de 1, 2 ou 3 chiffres.\n", "Étant donné un caractère $c$, le code ASCII correspondant est obtenu par `ord(c)`.\n", " - Les codes ASCII des caractères sont transformés en `str`, puis ramenés sur 3 chiffres en ajoutant si nécessaire des 0 à gauche.\n", " - Les chaînes représentant les codes ASCII sur 3 chiffres sont concaténées les unes à la suite des autres pour obtenir une seule (grande) chaîne, ensuite transformée en `int`.\n", "2) Ecrivez une fonction `Sage` **Decode(nombre)** effectuant l'opération réciproque : étant donné un nombre entier _nombre_, retrouver la chaîne de caractères _texte_ qu'il représente.\n", "\n", "Pour cela, utilisez la fonction `chr`. Étant un code ASCII donné _num_, le caractère associé est obtenu par `chr(num)`.\n", "\n", "Pour récupérer les codes ASCII des différents caractères, vous voudrez peut-être utiliser le reste ($\\%$) et le quotient ($//$) de la division par 1000. \n", "\n", "3) Testez vos fonctions d'encodage/décodage. On doit avoir, pour tout message $M$ : \n", " $$\\texttt{M=Decode(Encode(M))}$$\n" ] }, { "cell_type": "code", "execution_count": null, "id": "bd403b19-e59b-457d-b451-29693ad9c6f5", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "4ea6aeb2-d13a-4be7-9247-3dae99ba7a69", "metadata": {}, "source": [ "### Q. Echanges de messages\n", "À ce stade, vous pouvez chiffrer/déchiffrer des messages entre vous.\n", "1) Un.e voisin.e vous communique sa clé publique. Vous pouvez donc maintenant lui envoyer des messages chiffrés.\n", "2) Choisissez un message _texte_ ((très) court! puisque le nombre encodant votre message ne doit pas dépasser son module). Convertissez-le en _nombre_. Chiffrez ce nombre. Envoyez le cryptogramme résultant à votre voisin.e.\n", "3) Votre voisin.e déchiffre le cryptogramme. Puis il/elle décode le _nombre_ obtenu, et retrouve votre _texte_.\n", "4) [BONUS] Pour pouvoir échanger des messages aussi longs que vous voulez, écrivez une fonction qui découpe les entiers trop longs pour en faire plusieurs messages." ] }, { "cell_type": "markdown", "id": "c2fa1482-0681-4afc-b606-e91697845258", "metadata": {}, "source": [ "## Exponentielle\n", "1) Écrire une fonction $\\texttt{exp\\_basique(x,n,p)}$ qui, pour trois entiers positifs $x,n,p$ donnés en entrée, calcule de manière basique (sans utiliser la bibliothèque Sage) l'exponentielle modulaire $x^n \\mod p $\n", "2) L'algorithme d'_exponentielle rapide_ permet également de calculer le nombre $x^n \\mod p$ mais en utilisant l'algorithme récursif suivant :\n", "\n", "$$ {\\mbox{puissance}}(x,\\,n)=\\left\\{{\\begin{matrix}x,&{\\mbox{si }}n{\\mbox{ = 1}}\\\\{\\mbox{puissance}}(x^{2},\\,n/2),&{\\mbox{si }}n{\\mbox{ est pair}}\\\\x\\times {\\mbox{puissance}}(x^{2},\\,(n-1)/2),&{\\mbox{si n est impair}}\\\\\\end{matrix}}\\right.$$\n", "\n", "Ecrire une fonction $\\texttt{exp\\_rapide(x,n,p)}$ implémentant cet algorithme.\n", "\n", "3) Calculer le nombre suivant, avec les deux méthodes :\n", "$ 123456789^{123456789} \\pmod{987654321} = 598987215$\n", "Que constatez-vous ? " ] }, { "cell_type": "code", "execution_count": null, "id": "85f83056-e6f2-4dc6-b00c-07112649c115", "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "id": "a941ab29-069d-4aba-80e9-7005dd0efc2e", "metadata": {}, "source": [ "# Chiffrement asymétrique RSA\n", "Le schéma Rivest, Shamir, Adleman est un autre exemple de schéma à clé publique. Le but de cet exercice est d'écrire les fonctions permettant de chiffrer et déchiffrer des messages en utilisant RSA. On rappelle ci-dessous les étapes nécessaires :\n", "- Choisir deux nombres premiers $p$ et $q$ et calculer $n=pq$\n", "- Choisir un entier positif $e$ tel que $pgcd(e,\\varphi(n))=1$\n", "- Calculer une valeur de $d$ tel que $de\\equiv 1 \\;mod(\\varphi(n))$\n", "- La clé publique est $pk=(n,e)$ et la clé privée est $sk=(p,q,d)$\n", "- Pour tout message $0