{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Le problème du logarithme discret : Diffie-Hellman et ElGamal\n", "\n", "## Quelques résultats de théorie des groupes\n", "\n", "On connaît déjà quelques exemples de groupes finis : les $({\\mathbb Z}/n{\\mathbb Z})^\\times$, les éléments inversibles de\n", "${\\mathbb Z}/n{\\mathbb Z}$, forment un groupe dont le nombre d'éléments est noté $\\varphi(n)$ (indicateur d'Euler).\n", "\n", "### Le théorème de Lagrange\n", "\n", "On appelle *ordre* d'un élément $g$ d'un groupe fini $G$ (noté multiplicativement, d'élement neutre 1), le plus petit entier positif $m$ tel que $g^m=1$.\n", "\n", "Il existe : puisque $G$ est fini, la suite $g^k$ des puissances de $g$ contient forcément deux éléments égaux, et si $g^k=g^l$, ($k\\lt l$), alors $g^{l-k}=1$.\n", "\n", "On appelle *ordre* du groupe $G$ son nombre d'éléments.\n", "\n", "Ce choix judicieux des définitions permet d'énoncer élégamment le *théorème de Lagrange* :\n", "\n", "**\"Dans un groupe fini, l'ordre de tout élément est un diviseur de l'ordre du groupe.\"**\n", "\n", "En effet, prenons un élément $h$ de $G$, d'ordre $m$ dans un groupe d'ordre $n$. Alors, ou bien $m=n$, et c'est fini, ou bien $m\\lt n$. Dans ce cas,\n", "on peut trouver un élément $g_1$ qui n'est pas dans l'ensemble $H$ des puissances de $h$. \n", "L'ensemble $g_1H=\\{g_1,g_1h,\\ldots,g_1h^{m-1}\\}$ a lui aussi $m$ éléments distincts, dont aucun n'est dans $H$ :\n", "si on avait $g_1h^i = h^j$ alors, $g_1=h^{j-i}$ serait dans $H$. Si on ne peut pas trouver $g_2$ qui ne soit ni dans\n", "$H$, ni dans $g_1H$, alors, l'ordre $n$ de $G$ est $n=2m$, et on a fini. Sinon, on recommence avec $g_2$, et ainsi de\n", "suite, jusqu'à obtenir $G$ comme réunion disjointe d'ensembles $H,g_1H,\\ldots,g_{k-1}H$ ayant tous $m$ éléments,\n", "et alors, $n=km$.\n", "\n", "\n", "\n", "#### Fermat\n", "Si $G=({\\mathbb Z}/p{\\mathbb Z})^\\times$ avec $p$ premier, $n=p-1$, et donc tout élément vérifie $\\bar a^{p-1}=\\bar 1$.\n", "\n", "#### Euler\n", "Si $G=({\\mathbb Z}/n{\\mathbb Z})^\\times$, d'ordre $\\varphi(n)$, tout élément vérifie $\\bar a^{\\varphi(n)}=\\bar 1$.\n", "\n", "#### Calcul de $\\varphi(n)$\n", "\n", "Si $n=p_1^{m_1}\\cdots p_r^{m_r}$ est la décomposition de $n$ en facteurs premiers, le théorème des restes chinois montre que\n", "$${\\mathbb Z}/n{\\mathbb Z} \\simeq {\\mathbb Z}/p_1^{m_1}{\\mathbb Z}\\times\\cdots\\times {\\mathbb Z}/p_r^{m_r}{\\mathbb Z}$$\n", "les opérations s'effectuant composante à composante sur les $r$-uples. Donc, un élément sera inversible si et seulement si ses résidus modulo tous les $p_i^{m_i}$ le sont.\n", "\n", "Il suffit donc de savoir calculer $\\varphi(p^m)$. Les éléments *non inversibles* de ${\\mathbb Z}/p^m{\\mathbb Z}$\n", "sont les entiers $0\\le a\\lt p^m$ qui sont divisibles par $p$, c'est à dire $0,p,2p,3p,\\ldots,(p^{m-1}-1)p$. Il y en a donc\n", "$p^{m-1}$, et $\\varphi(p^m)=p^m-p^{m-1}$.\n", "\n", "Le produit de ces nombres peut s'écrire\n", "$$\\varphi(n)=n\\prod_{p|n}\\left(1-\\frac1p\\right)$$\n", "(produit sur les diviseurs premiers de $n$).\n", "\n", "On peut exprimer cette formule grace à la *fonction de Möbius* $\\mu$\n", "$$\\mu(n) =\n", "\\begin{cases}\n", "1 & \\text{si $n=0$}\\\\\n", "(-1)^r&\\text{si $n=p_1\\cdots p_r$ est produit de $r$ nombres premiers distincts}\\\\\n", "0 & \\text{sinon}\n", "\\end{cases}\n", "$$\n", "\n", "En développant le produit, on a\n", "$$\\varphi(n)=\\sum_{d|n}\\mu(d)\\frac nd.$$\n", "\n", "\n", "\n", "\n", "\n", "Remarquons que $\\varphi(n)$ est aussi le nombre d'élements d'ordre (additif) $n$ dans ${\\mathbb Z}/n{\\mathbb Z}$. En effet, $kx\\equiv 0\\mod n\\Rightarrow n|k$ si et seulement si $x\\wedge n =1$. Pour un diviseur $d$ de $n$, $\\varphi(d)$ est donc le nombre d'éléments d'ordre $d$ dans ${\\mathbb Z}/n{\\mathbb Z}$, et on a\n", "$$n = \\sum_{d|n}\\varphi(d).$$\n", "\n", "\n", "\n", "L'équivalence des deux expressions est un cas particulier de la [formule d'inversion de Möbius](https://fr.wikipedia.org/wiki/Fonction_de_M%C3%B6bius), qui relie deux fonctions $f$ et $g$ sur les entiers positifs \n", "\n", "$$ g(n)= \\sum_{d|n}f(d)\\quad \\Leftrightarrow \\quad f(n)=\\sum_{d|n}\\mu(d)g\\left(\\frac{n}{d}\\right).$$\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Groupes cycliques\n", "\n", "Un groupe formé des puissances d'un seul élément est dit *cyclique* (pourquoi, à votre avis ?).\n", "\n", "Par exemple, le groupe *additif* $({\\mathbb Z}/n{\\mathbb Z},+)$ est cyclique : il est formé des \"puissances additives\" de $\\bar 1$.\n", "\n", "\n", "Le théorème de Lagrange entraîne que *tout groupe fini d'ordre premier est cyclique*.\n", " \n", "La propriété suivant est moins évidente :\n", " *Si $p$ est premier, le groupe multiplicatif $G_p=({\\mathbb Z}/p{\\mathbb Z})^\\times$ est cyclique.*\n", "\n", "Autrement dit, il existe (au moins) un élément $g$, appelé *générateur* ou *élément primitif* dont les puissances modulo\n", "$p$ prennent toutes les valeurs de 1 jusqu'à $p-1$.\n", "\n", "Par exemple, $g=3$ est primitif modulo $p=31$ :" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 3 9 27 19 26 16 17 20 29 25 13 8 24 10 30 28 22 4 12 5 15 14 11 2 6 18 23 7 21 1 " ] } ], "source": [ "p = 31\n", "for i in range(31): print (pow(3,i,31), end=' ')" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "On peut montrer que d'une manière générale, le groupe multiplicatif d'un corps fini est toujours cyclique. \n", "\n", "Dans le cas des entiers modulo $p$, on peut le voir ainsi. Soit $d$ un diviseur de $n=p-1$. Les éléments de $G_p$ qui vérifient $x^d=1$ forment un sous-groupe : si $a^d=1$ et $b^d=1$, alors $(ab)^d=a^db^d=1$. De plus, le polynôme $x^d-1$ a exactement $d$ racines distinctes modulo $p$. En effet, d'après Fermat, \n", "$$x^{p-1}-\\bar 1 = (x-\\bar 1)(x-\\bar 2)\\cdots (x-\\overline{p-1})$$\n", "et $x^d-\\bar 1$ divise ce polynome : c'est dont un produit de $d$ facteurs $x-\\bar a$ distincts.\n", "\n", "Ses racines sont les éléments de $G_p$ dont les ordres sont les diviseurs $c$ de $d$. \n", "Si on note $\\psi(c)$ le nombre d'éléments d'ordre $c$, on a donc\n", "$$d=\\sum_{c|d}\\psi(c)$$\n", "pour tout diviseur $d$ de $n$.\n", "\n", "Par exemple, pour $p=13$, $p-1=12$ et\n", "\n", "* $1 = \\psi(1)$, donc $\\psi(1)=1$ (et 1 est l'unique élément d'ordre 1)\n", "* $2 = \\psi(1)+\\psi(2)=\\psi(2)+1$, donc $\\psi(2)=1$ (-1 est l'unique élément d'ordre 2)\n", "* $3 = \\psi(1)+\\psi(3)=\\psi(3)+1$, donc $\\psi(3)=2$\n", "* $4 = \\psi(1)+\\psi(2)+\\psi(4)=\\psi(4)+2$, donc $\\psi(4)=2$\n", "* $6 = \\psi(1)+\\psi(2)+\\psi(3)+\\psi(6)=\\psi(6)+4$, donc $\\psi(6)=2$\n", "* $12 = \\psi(1)+\\psi(2)+\\psi(3)+\\psi(4)+\\psi(6)+\\psi(12)$ donc $\\psi(12)=12-8=4$\n", "\n", "\n", "Ceci entraîne que $\\psi(p-1)=\\varphi(p-1)\\not=0$, et donc qu'il existe au moins un élément d'ordre $p-1$.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Le logarithme discret\n", "\n", "Dans un groupe cyclique $G$ de générateur $g$, le logarithme $x=\\log_g y$ de $y$ en base $g$ est le plus petit entier $x\\ge 0$ tel que\n", "$$ y = g^x$$\n", "\n", "Par exemple, pour $p=31$ et $g=3$, le logarithme de $23$ dans $G_p$ est $27$ :" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "23" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pow(3,27,31)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il n'existe pas d'algorithme raisonnable pour calculer le logarithme discret dans un grand groupe (sauf dans des cas particuliers).\n", "\n", "Si on prend un grand nombre premier $p$ et un générateur $g$ de $G_p$, on ne peut en général pas calculer $x$ à partir de $y=g^x$.\n", "\n", "## Le protocole de Diffie-Hellman\n", "\n", "Cette technique permet de construire une clé de session connue de deux parties A et B sans jamais la transmettre sur le réseau.\n", "\n", "On choisit un grand nombre premier $p$, tel que le problème du logarithme discret soit difficile dans $G_p$, et $g$ un générateur d'un sous groupe d'ordre $q$ (grand) du groupe $G_p$. \n", "\n", "Le principe est très simple : A tire au hasard un entier $a$ et B tire au hasard un entier $b$ (inférieurs à $q$). \n", "\n", "A envoie à B le nombre $g^a$, B envoie à A le nombre $g^b$ . Ainsi, A et B peuvent tous deux calculer $K=g^{ab}$, \n", "mais un adversaire qui intercepterait la communication ne pourrait pas le faire. A et B utilisent ensuite $K$\n", "comme clé de session." ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 25 124 94 12 133 152 126 144 93 154 9 58 114 11 108 28 32 132 127 2 50 81 21 24 99 137 85 121 19 141 18 116 61 22 49 56 64 97 87 4 100 162 42 48 31 107 3 75 38 115 36 65 122 44 98 112 128 27 7 8 33 157 84 96 62 47 6 150 76 63 72 130 77 88 29 57 89 54 14 16 66 147 1 " ] } ], "source": [ "# Exemple\n", "p = 167 # 167 = 2*83+1 et 83 est premier\n", "g = 25 # g = 5**2, l'ordre d'un sous groupe ne peut être que 2 ou 83, or 25!=1 donc c'est 83\n", "for i in range(84): print (pow(g,i,p), end =' ')" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "31 44 18 48 56\n" ] } ], "source": [ "from random import randint\n", "a = randint(2,p-1)\n", "b = randint(2,p-1)\n", "x = pow(g,a,p)\n", "y = pow(g,b,p)\n", "K = pow(x,b,p) # clef de session\n", "print (a,b,x,y,K)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Le protocole utilisé par ssh est un peu plus compliqué. Les protagonistes sont le serveur S et le client C.\n", "\n", "- C tire un nombre aléatoire $x < q$ et envoie $e = g^x \\mod p$ à S\n", "- S tire un nombre aléatoire $y < q$ et calcule $f = g^y \\mod p$.\n", "- S reçoit $e$ et calcule $K = e^y \\mod p$, puis un hachage\n", "$$H = {\\rm hash}(V_C || V_S || I_C || I_S || K_S || e || f || K)$$\n", "où $V_C$ et $V_S$ sont les chaînes d'identification du client et du serveur, respectivement. $K_S$ est la clé publique du serveur, et $I_C$ et $I_S$ sont des messages qui ont été échangés avant cette phase du protocole. S signe ensuite $H$ (signature $s$) et envoie $(K_S || f || s)$ à C.\n", "- C vérifie que $K_S$ est bien la clé publique de S (en utilisant des certificats ou une base de donnée locale). Il calcule alors à son tour $K = f^x \\mod p$, puis $H$, et enfin vérifie la signature $s$ de $H$.\n", "\n", "Il y a plusieurs choix possibles pour la fonction de hachage (par exemple SHA-1).\n", "\n", "\n", "\n", "Les détails se trouvent dans la [RFC 4253](https://datatracker.ietf.org/doc/html/rfc4253). " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Le cryptosystème d'ElGamal\n", "\n", "Les clefs se construisent à partir d'un grand nombre premier $p$ et d'un générateur $g$ d'un grand sous groupe (d'ordre $q$) de \n", "$G_p=({\\mathbb Z}/p{\\mathbb Z})^\\times$.\n", "\n", "\n", "Chaque utilisateur choisit un entier $x$ (sa clef secrète) et publie $y=g^x\\mod p$.\n", "\n", "\n", "Pour chiffrer un message $m$\n", "(représenté par un entier modulo $p$), on tire un entier aléatoire $k$ et on calcule\n", "$$(c_1,c_2)=(g^k,m\\cdot y^k).$$\n", "\n", "Le destinataire déchiffre avec sa clef secrète en calculant\n", "$$m=\\frac{c_2}{c_1^x}.$$\n", "\n", "On trouvera plus de détails [ici](https://fr.wikipedia.org/wiki/Cryptosyst%C3%A8me_de_ElGamal)." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "42 162 100 39\n", "87 127\n" ] } ], "source": [ "# Exemple - On reprend p = 167, g = 25\n", "x = 42 # La clef secrète\n", "y = pow(g,x,p) # La clef publique est (p,g,y)\n", "m = 100 # Le message\n", "k = randint(2,p-1)\n", "c1, c2 = pow(g,k,p), m*pow(y,k,p) % p \n", "print(x,y,m,k)\n", "print(c1,c2)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "100" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Pour déchiffrer\n", "from ent3 import *\n", "c2*pow(inversemod(c1,p),x,p)%p" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Il y a des clefs faibles. Il faut que le problème du logarithme discret soit difficile dans $G_p$.\n", "\n", "Ce n'est par exemple pas le cas si $p−1$ est un produit de petits facteurs premiers \n", "(l'algorithme de Pohlig-Hellman permet de casser la clef).\n", "\n", "Les clefs les plus résistantes sont celles pour lesquelles $p$\n", "est un *nombre premier sûr*, c'est à dire de la forme $p=2q+1$ avec $q$ premier (on dit alors que $q$ est un [nombre premier de Sophie Germain](https://fr.wikipedia.org/wiki/Nombre_premier_de_Sophie_Germain)). Ces nombres sont rares, et le calcul des clefs est long. On recommande ensuite de choisir pour $g$ un générateur du sous groupe des carrés, qui est d'ordre $q$ premier, et donc cyclique. \n", "\n", "Le problème du logarithme discret est supposé être le plus difficile dans les groupes d'ordre premier.\n", "\n", "On peut utiliser d'autres groupes, par exemple les groupes multiplicatifs des autres corps finis ${\\mathbb F}_q$\n", "(très utilisés pour la construction de codes correcteurs d'erreurs), ou mieux, les groupes associés aux courbes elliptiques sur les corps finis. Ces derniers systèmes, plus complexes et dépendant de mathématiques très sophistiquées, permettent d'avoir des clefs plus courtes à sécurité équivalente, et sont bien adaptés aux environnements embarqués comme les cartes à puces." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Le schéma de signature\n", "\n", "Comme dans la plupart des schémas de signature numérique, un utilisateur signe un document en chiffrant un hachage $h$\n", "avec sa clé secrète, et tout le monde peut alors vérifier la signature au moyen de sa clé publique. \n", "De manière précise, pour signer un entier $0\\le h\\lt p−1$, on tire au hasard un entier $k$ dans ce même intervalle, premier avec $p−1$, et on calcule\n", "$$r=g^k\\mod p,$$\n", "puis\n", "$$s=(h−xr)k^{−1}\\mod p−1.$$\n", "La signature est le couple $(r,s)$.\n", "\n", "Pour vérifier une signature avec la clé publique $y$, on vérifie deux conditions\n", "\\begin{align}\n", "(1)&\\quad 1\\le r\\lt p,\\ 0 \\lt s \\lt p − 1 \\\\\n", "(2)&\\quad g^h\\equiv r^sy^r\\mod p.\n", "\\end{align}" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "53\n" ] } ], "source": [ "# On continue avec p = 167 et g = 25 ...\n", "h = 111 # le hachage à signer\n", "while 1:\n", " k = randint(1,p-2) # on tire k\n", " if gcd(k,p-1)==1: break # on vérifie qu'il est premier avec p-1\n", "l = inversemod(k,p-1) \n", "print(l)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "3 35\n" ] } ], "source": [ "r = pow(g,k,p)\n", "s = ((h-r*x)*l) % (p-1)\n", "print(r,s) # la signature" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "True True\n" ] }, { "data": { "text/plain": [ "True" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# On vérifie\n", "print(1<=r\\xad\\xb9`u\\x85\\x1b]\\xdd\\x01j|\\x0c/\\xce\\x8b\\x1e\\xdc/l\\xd8e\\xb8\\xd7\\xeaQJL\\x040\\xbd\\xaa?A\\xa3\\xdd\\t\\xca\\x1d\\xce\"* y\\xe6\\x000\\x9c`\\xc8JC-\\x16\\xac\\x08\\xc8\\xa7\\x9b\\xb1\\xd64\\xa6\\xcd\\xe6e\\xfcW\\rO\\xf8\\xd4\\x0b,Al\\xaf\\xc8)\\xa5_\\x90\\x1e\\x81H\"\\xe0\\xc3\\x1aH*\\x82\\xe6\\r\\x1e-8\\xc8\\x86\\xb1\\xded\\xce\\xbfA\\xfa', b'\\x8a`*\\xd78#\\xcd\\xe9\\xdb\\x1f\\xde5&@\\xa7\\xbc>i\\x12\\x8eG\\xfb\\x03\\xa4\\x0c\\xde;\\x075\\x99\\x83(\\x1e\\xf8\\x14.\\x98\\xebaZ\\xa1\\xb3\\xec]N\\x81\\xf1\\xfa\\x90Q\\xad\\xd8\\xf7d\":\\xe1\\x89*N\\x18\\xbf\\x94\\xc5\\xa5\\xd1\\x08=\\x9et\\xb3\\xb8\\xdc\\x9b\\xf1?\\x01\\xa3\\xa0\\x99\\xcdi\\xc9\\x1e\\x0bq\\xfe\\xda\\x15O\\xd3\\xd7Z\\xdc\\xd9\\xad\\xdbe\\xf8O^\\xd6\\xd9\\x95\\xbaf\\x9a\\xc5\\x03\\x7f\\xf3\\xfd7a\\x10~\\xcf;\\xe5\\x83\\x7f\\xc0R\\xbbG\\xe6\\xa90')\n", "Le cheval de mon cousin ne mange du foin que le dimanche.\n", "(67729817320127874024460005271867597705960161024138051360059077605893090034717446648293970426282834924646737673233614773116424022634949530078838472905199492070251744835700643158700567706620614244233874687239652990450714993646153934987461571735720862099933933645963554489095187552604869943006740064925414015482, 65894150237041914184975386237670592492354014323188987174351817180360391579463736272270445963735377151075147619650926390128167929837988174605688519430036060114145770990273004862754097135202298974669895869690353174093018149977512064730844219158792358666634018772967954419351911709294576917741163886853557052068)\n", "1\n" ] } ], "source": [ "# g n'est pas toujours primitif dans cette version ...\n", "\n", "M ='Le cheval de mon cousin ne mange du foin que le dimanche.'.encode() # Pyuthon 3 : encodage pour conversion en bytes \n", "C = EG.encrypt(M, 4567) \n", "print (C)\n", "\n", "D = EG.decrypt(C)\n", "print (D.decode())\n", "\n", "s = EG.sign(M, 4567)\n", "print (s)\n", "v = EG.verify(M,s)\n", "print (v)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Avec un exemple réel sous les yeux, on peut maintenant envisager de coder un ElGamal à partir de zéro (ou presque). Un problème à résoudre est celui des clés faibles. On utilisera donc des nombres premiers sûrs. Pour les construire, on tire un entier aléatoire $u$ dans l'intervalle voulu. S'il est pair, on l'incrémente. Ensuite on teste si $u$ ou $2u+1$ est divisible par un petit nombre premier. Si c'est le cas, on l'incrémente de $2$. Sinon, on fait un seul test de Fermat en base 2 sur $2u+1$. En cas de succès, on fait un test de Miller-Rabin sur $u$\n", "\n", "\n", "\n", "Voici une ébauche de programme (utilisant encore quelques fonctions du ent.py de W. Stein) :" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [], "source": [ "from random import randint\n", "from ent3 import *\n", "\n", "# On utilise un p sûr (p=2q+1, q premier)\n", "# q est un premier de Sophie Germain\n", "# On ne doit pas avoir q = (r-1)/2 mod r (r petit permier)\n", "# sinon p serait divisible par r\n", "# La borne 2**16 est recommandée par Wiener\n", "small_primes = primes(2**16)[1:]\n", "\n", "def small_test(u):\n", " for v in small_primes:\n", " a = u%v\n", " if a == 0 or a == (v-1)//2: return False\n", " return True\n", "\n", "def gen_safe_prime(nbits):\n", " u = randint(2**(nbits-2), 2**(nbits-1)-2**(nbits//2))\n", " if u%2 == 0:\n", " u +=1\n", " while not small_test(u):\n", " u+=2\n", " while u < 2**(nbits-1):\n", " if powermod(2,u-1,u) == 1:\n", " p = 2*u+1\n", " if powermod(2,p-1,p)==1:# si u est SG, suffit\n", " if miller_rabin(u):\n", " print (\"OK\")\n", " return p\n", " u += 2\n", " while not small_test(u):\n", " u += 2\n", " return None" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "OK\n" ] }, { "data": { "text/plain": [ "10418282562089589578604814701993384709414688931792548442907004773785866791174608638275587700280726048156680041024393224181439408748029133888690414096326559" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p = gen_safe_prime(512)\n", "p" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 19, "metadata": {}, "output_type": "execute_result" } ], "source": [ "miller_rabin((p-1)//2)" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "True" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "miller_rabin(p)" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "# Pas plus de 1024 bits en un temps raisonnable ...\n", "# On prend un générateur du sous-groupe des\n", "# carrés, qui est d'ordre q premier\n", "\n", "def gen_key(nbits):\n", " p = gen_safe_prime(nbits)\n", " q = (p-1)//2\n", " g = randint(2,p-1)\n", " g = powermod(g,2,p)\n", " x = randint(2,q-1)\n", " y = powermod(g,x,p)\n", " return ((p,q,g,y),x)\n", "\n", "\n", "def encrypt(m, pub_key):\n", " (p,q,g,y) = pub_key\n", " k = randint(1,q-1)\n", " u = powermod(g,k,p); v = m*powermod(y,k,p)\n", " return (u,v)\n", "\n", "def decrypt(c,x,p):\n", " u,v = c\n", " w = inversemod(u,p)\n", " return powermod(w,x,p)*v % p" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "OK\n", "Key: \n", "((161173487310387999358660618695805579570797736004252757809871291807242310898982661651637236798744669616295324291613504010680667268627761152766120282645113110675452146621288309318556987456065365864348577808253380595338636597941966744288761612444868207939763249951500907282392974692180300912560584571644436483467, 80586743655193999679330309347902789785398868002126378904935645903621155449491330825818618399372334808147662145806752005340333634313880576383060141322556555337726073310644154659278493728032682932174288904126690297669318298970983372144380806222434103969881624975750453641196487346090150456280292285822218241733, 36556173367205031481192138833785804073648539300032519247851267634395480176301283869693498267276173209378998500248662786097297364050714670908780780156044402607263060768838584753635132079892783795795847311247885532638721938912486179251642931513712403407218304744997731970450221945594554514405226492010131647399, 125161891419268100713136258956202191348139169273902863394262098501885561574039561778464901348327419042719191763375591136643612343966778433210177336564059489734211347540828770197010471032286042482757243964795380491643661485172413482302131029711432219854798340548594619983169376254645639967035435549352740614356), 70280911437692656785627666258166014527984426009028751036033193721610727107514631872001486120964708202778900056687678023079281848278658028768880915371137245137792471084249582493744214353298145355648741098116110963500184371770788175600929384534480673049790048684937048702882746942909880700649549900342395668541)\n", "92927465673222493287775317998871556071077997502287836846274557397922057675402\n", "(83114241663678872897229178731477816563456437197366593283677599114651193224573812224381795202812201551507353487616378184505653540438092174746602067195883462373031042252534254904029641757973546649254537965704623823790965457954958388767402126816245328208811426333318747912447817557492564621450113929277268151011, 619188048442852045528846371969871919649916658007699244722714722000292714903866142643895825158160224651273546220643526591647789208898694870737196476926387135750780157297643898311332292239169949741024276207090626073827863816490022353906113207671340345240390592982401758829113289046618458078084552355547312771042572016413414043321910138545745611196046255441448755233211717227449626686766)\n", "92927465673222493287775317998871556071077997502287836846274557397922057675402\n" ] } ], "source": [ "K = gen_key(1024)\n", "print (\"Key: \")\n", "print (K)\n", "m = randint(2**255,2**256)\n", "print (m)\n", "c = encrypt(m, K[0])\n", "print (c)\n", "d = decrypt(c, K[1], K[0][0])\n", "print (d)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## L'algorithme de Pohlig-Hellman et l'attaque de Bleichenbacher\n", "\n", "C'est dans les groupes d'ordre premier que le problème du logarithme discret est le plus difficile. Au contraire, si $p-1$ n'a que de petits facteurs premiers, il existe des algorithmes efficaces, comme l'[algorithme de Pohlig-Hellman](https://en.wikipedia.org/wiki/Pohlig%E2%80%93Hellman_algorithm).\n", "\n", "Le principe est le suivant. Pour calculer le logarithme discret $x$ de $h=g^x$ dans un groupe cyclique d'ordre $n$ et de\n", "générateur $g$, si\n", "$$n=p_1^{e_1}p_2^{e_2}\\cdots p_r^{e_r}$$\n", "n'a que de *petits* facteurs premiers $p_i$, on calcule les éléments\n", "\n", "* $g_i = g^{n/{p_i^{e_i}}}$, qui est donc d'ordre $p_i^{e_i}$ par le théorème de Lagrange\n", "* $h_i = h^{n/{p_i^{e_i}}}$, qui appartient au sous-groupe cyclique $\\langle g_i\\rangle$ engendré par $g_i$\n", "* $x_i = \\log_{g_i} h_i$, problème plus facile qu'on peut résoudre par diverses méthodes\n", "\n", "On a $x\\equiv x_i \\mod p_i^{e_i}$, et on reconstitue $x$ par le théorème des restes chinois.\n", "\n", "### Baby step - giant step\n", "Pour calculer les $x_i$, on peut utiliser l'algorithme [baby step - giant step](https://en.wikipedia.org/wiki/Baby-step_giant-step), qui est un compromis temps-mémoire pour la recherche exhaustive.\n", "\n", "Étant donné un groupe cyclique $G$ d'ordre $n$, un générateur $g$ et $h=g^x$, on cherche $x$ sous la forme $x=im+j$ où\n", "$m=\\lceil\\sqrt{n}\\rceil$, $0\\le i,j\\lt m$.\n", "\n", "On précalcule les $g^j$ (dans une table de hachage de clefs $j$), et $g^{-m}$. Alors, $h(g^{-m})^i = g^j$\n", "\n", "On initialise $u=h$ et pour $j$ de 0 à $m-1$, on teste si $u=g^j$. Si oui, on renvoie $im+j$, sinon on fait $u:=ug^{-m}$\n", "et on recommence.\n", "\n" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "1 2 4 8 16 32 64 25 50 100 97 91 79 55 7 14 28 56 9 18 36 72 41 82 61 19 38 76 49 98 93 83 63 23 46 92 81 59 15 30 60 17 34 68 33 66 29 58 13 26 52 1 2 4 8 16 32 64 25 50 100 97 91 79 55 7 14 28 56 9 18 36 72 41 82 61 19 38 76 49 98 93 83 63 23 46 92 81 59 15 30 60 17 34 68 33 66 29 58 13 26 52 1 " ] } ], "source": [ "from ent3 import *\n", "from math import ceil, floor, sqrt\n", "\n", "def bsgs(h,g,n,mulf,powf):\n", "\n", " m = int(ceil(sqrt(n)))\n", " d = {j:powf(g,j) for j in range(m)}\n", " a = powf(g,-m)\n", " u = h\n", " for i in range(m):\n", " for j in range(m):\n", " if u == d[j]: return i*m+j\n", " u = mulf(u,a)\n", " \n", "# Exemple \n", "def mulf(x,y): return (x*y)% 103\n", "def powf(x,k):\n", " if k<0: \n", " x = inversemod(x,103)\n", " k = -k\n", " return powermod(x,k,103)\n", " \n", "for i in range(103): print (pow(2,i,103), end=' ')" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "34" ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "h = pow(2,42,103); h" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "42" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bsgs(34,2,102,mulf,powf)" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "OK\n" ] }, { "data": { "text/plain": [ "525167" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p = gen_safe_prime(20); p" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "262583" ] }, "execution_count": 27, "metadata": {}, "output_type": "execute_result" } ], "source": [ "q=(p-1)//2; q" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [], "source": [ "def mulf(x,y): return (x*y)% p\n", "def powf(x,k):\n", " if k<0: \n", " x = inversemod(x,p)\n", " k = -k\n", " return powermod(x,k,p)" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "323734" ] }, "execution_count": 29, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g = 4\n", "h = pow(g,111111,p); h" ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "111111" ] }, "execution_count": 30, "metadata": {}, "output_type": "execute_result" } ], "source": [ "bsgs(h,g,q,mulf,powf)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Pohlig-Hellman version 1\n", "\n", "On utilise baby step-giant step pour trouver les $x_i$. Ce n'est pas efficace si les $e_i>1$." ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [], "source": [ "from functools import reduce\n", "\n", "def solve_chinese(yy,mm):\n", " assert len(yy) == len(mm), \"Arguments must have same length.\"\n", " k = len(yy); m = reduce(lambda x,y:x*y, mm); x=0\n", " for i in range(k):\n", " u = reduce(lambda x,y:x*y, [mm[j] for j in range(k) if j!=i])\n", " v = inversemod(u,mm[i])\n", " x = (x + yy[i]*v*u) % m\n", " return x\n", "\n", "\n", "def pohlig_hellman1(h,g,p):\n", " n = p-1\n", " ff = factor(n)\n", " r = len(ff)\n", " \n", " def mulf(x,y): \n", " return (x*y)% p\n", " \n", " def powf(x,k):\n", " if k<0: \n", " x = inversemod(x,p)\n", " k = -k\n", " return powermod(x,k,p)\n", " \n", " mm = [pow(ff[i][0],ff[i][1]) for i in range(r)]\n", " print ('mm: ',mm)\n", " gg = [pow(g,n//mm[i],p) for i in range(r)]\n", " print ('gg: ',gg)\n", " hh = [pow(h,n//mm[i],p) for i in range(r)]\n", " \n", " xx = [bsgs(hh[i],gg[i],mm[i],mulf,powf)for i in range(r)]\n", " print ('hh: ',hh)\n", " print ('xx: ',xx)\n", " \n", " return solve_chinese(xx,mm)\n", " \n" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "mm: [2, 5003]\n", "gg: [10006, 25]\n", "hh: [10006, 8926]\n", "xx: [1, 1054]\n" ] }, { "data": { "text/plain": [ "6057" ] }, "execution_count": 32, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pohlig_hellman1(9451,5,10007)" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "9451" ] }, "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pow(5,6057,10007)" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "53 10281500672050559975\n", "Computing ...\n", "mm: [16, 109, 3307, 186161, 11376527]\n", "gg: [3977706731622236597, 10794351375895673062, 9010175095136500157, 3035679229265288799, 6400025164451908865]\n", "hh: [10837460501653388979, 1223524356504489457, 5415912014413668711, 7779342733905718077, 9933792936822973415]\n", "xx: [5, 10, 3172, 32046, 9691519]\n", "123456789\n", "1.0858404636383057\n" ] } ], "source": [ "p = 12214595251480930577\n", "g = 53\n", "h = powermod(g,123456789,p)\n", "print (g,h)\n", "from time import time\n", "a = time()\n", "print (\"Computing ...\")\n", "print (pohlig_hellman1(h,g,p))\n", "print (time()-a)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Pour les groupes cycliques d'ordre $n=p^e$ avec $e>1$, baby step - giant step n'est pas efficace. On peut se ramener à ne l'appliquer qu'à des groupes d'ordre premier, en calculant successivement les chiffres $d_0,\\ldots d_{e-1}$ de $x$ en base $p$.\n", "C'est en fait le point essentiel de Pohlig-Hellman." ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [], "source": [ "def pohlig_hellman(h,g,p):\n", " ff = factor(p-1)\n", " mm = [q**e for q,e in ff]\n", " print (mm)\n", " xx = []\n", " u = inversemod(g,p)\n", " for q,e in ff:\n", " d = {i:pow(g,((p-1)*i)//q,p) for i in range(q)} # il faudrait remplacer cette étape par un BSGS\n", " a = 0\n", " w = h\n", " for j in range(e):\n", " v = pow(w,(p-1)//q**(j+1),p)\n", " for i in d:\n", " if d[i]==v:\n", " a += i*pow(q,j)\n", " w = (pow(u,i*q**j,p)*w) % p\n", " break\n", " xx.append(a)\n", " print (xx)\n", " return solve_chinese(xx,mm)\n", " " ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[(2, 1), (5, 1), (7, 1), (257, 4), (65537, 2)]" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "p = 1311606765290211317831\n", "factor(p-1)" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "188315544505038127198" ] }, "execution_count": 37, "metadata": {}, "output_type": "execute_result" } ], "source": [ "g = 17\n", "h = pow(g,1234567,p); h" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[2, 5, 7, 4362470401, 4295098369]\n", "[1, 2, 5, 1234567, 1234567]\n" ] }, { "data": { "text/plain": [ "1234567" ] }, "execution_count": 38, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pohlig_hellman(h,g,p)" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "mm: [2, 5, 7, 4362470401, 4295098369]\n", "gg: [1311606765290211317830, 9219817919881129457, 785880390810345683336, 1074196675878546094261, 1052424187774988976045]\n", "hh: [1311606765290211317830, 140454899200855728206, 839425818041000397659, 1276251671872571019226, 1137709246113480872298]\n", "xx: [1, 2, 5, 1234567, 1234567]\n" ] }, { "data": { "text/plain": [ "1234567" ] }, "execution_count": 39, "metadata": {}, "output_type": "execute_result" } ], "source": [ "pohlig_hellman1(h,g,p)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## L'attaque de Bleichenbacher\n", "\n", "On pourra partir des petits programme de démonstration ci-dessus pour tester l'attaque de Bleichenbacher sur le schéma de signature d'ElGamal (décrite dans la section 3 de [cet article](http://www-igm.univ-mlv.fr/~jyt/Crypto/5/Bleich96.pdf)). Elle fonctionne quand $p−1=bw$ où $b$ n'a que de petits facteurs premiers (on dit qu'il est lisse, *smooth* en anglais). On peut alors trouver $z$ tel que $g^{wz}\\equiv y^w\\mod p$ par l'algorithme de Pohlig-Hellman. On peut ensuite trouver $k$ et $r$ tels que $r\\equiv g^k\\equiv cw\\mod p$ pour un $c$ entre 0 et $b$. On peut ensuite,sans connaître la clé secrète, forger des signatures sur tout hachage $h$ vérifiant $h\\equiv xr\\mod k\\wedge(p−1)$. En particulier, si $g$ est lisse et divise $p−1$, on peut signer tout $h$ si $p\\equiv 1\\mod 4$ et la moitié des hachages possibles sinon.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "collapsed": true }, "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.8.10" } }, "nbformat": 4, "nbformat_minor": 1 }