ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ» º ElGamal º ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ Algorythmes a clefs puliques: ElGamal ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ I/ Chiffrement d'ElGamal et logarithme discret ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Le chiffrement d'ElGamal est base sur le probleme du logarythme discret. Pour commencer, on decrit ce probleme dans le corps fini ZZp, ou p est un nombre premier (figure 5.1). On rappelle que le groupe ZZp* est cycliqye, et que ses generateurs sont appeles racines primitives modulo p. Le probleme du logarythme discret dans ZZp est l'objet de nombreuses etudes. Le probleme est repute difficile si p est convenablement choisi/ En fait on ne conait aucun alogrythme polynomial pour le resoudre. Pour eviter les attaques connues, p doit avoir au moins 150 chiffres, et p-1 doit avoir au moins un "grand" facteur premier. L'utilite du probleme du logarithme discret en cryptographie provient Figure 5.1: Probleme du logarithme discret dans ZZp ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ» º Instance du probleme: I = (p,à,á) ou p est premier, à î ZZp est primitif, º º et á î ZZp*. º º Question: trouver l'unique a, 0 ó a ò p-2 tel que: º º º º à^a ð á (mod p) º º On note cet entier log á º º à º ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ Figure 5.2: Chiffrement d'ElGamal ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ» º Soit p un nombre premier tel que le probleme du logarythme discret dans ZZp º º soit difficile, et soit à î ZZp* un element primitif. Soit P = ZZp*, º º C=ZZp* mul ZZp* et º º K = { (p,à,a,á) : á = à^a (mod p)} º º Les valeurs p,à & á sont publiques et a est secret. º º Pour K = (p,à,a,á), et pour K î ZZp-1 aleatoire (secret) on definit º º e (x,k) = (y1, y2) º º o£ º º y1 = à^k mod p º º et º º y2 = xá^k mod p º º Pour y1,y2 î ZZp*, on definit º º º º d (y1,y2) = y2(y1^a)^-1 mod p º º K º ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ du fait que calculer des logarithmes discrets est (certainement) difficile, tandis que calculer l'operation inverse d'exponantiation modulaire peut se faire efficacement avec l'algorithme d'exponentiation modulaire. En d'autres termes, l'exponentiation modulo p est une fonction a sens unique pour des nombres premiers p convenables. ElGamal a propose un systeme cryptographique base sur le probleme du logarythme discret (figure 5.2). Le chiffrement d'ElGamal est non deterministe car l'operation de chiffrement depend de x et d'une valeur aleatoire choisi par l'expediteur du message. Il y a donc plusieurs textes chiffres qui correspondent a un meme texte clair. Voici informellement comment le chiffrement d'ElGamal fonctionne. Le texte clair est masque par la multiplication par á^k a partir de à^k. Il peut alors enlever le masque en divisant y2 par á^k pour obtenir x. Voici un petit exemple. Supposons p = 2579, à=2, a=765, et donc á = 2^765 mod 2579 = 949 Supposons que l'expediteur souhaite transmettre le message x = 1299. Pour commencer, elle choisit au hasard k, disons k = 853 et calcule y1 = 2^853 mod 2579 = 435 puis y2 = 1299 mul 949^853 mod 2579 = 2396 Lorsque le destinataire recoit le texte chiffre y = (435,2396), il calcule x = 2396 x (435^765)^-1 mod 2579 = 1299 Qui est bien le texte clair. 1) Calcul du logarithme discret ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Dans toute cette section, on suppose que p est un nombre premier et que à est une racine primitive modulo p. p et à etant fixes, le probleme du logarithme discret peut s'enoncer ainsi: etant donne un á î ZZp*, trouver l'unique a, 0 ó a ò p-2 tel que à^a ð á mod p Le probleme du logarithme discret peut clairement se resoudre par une recherche exhaustive en temps O(p) et avec O(1) memoire (en negligeant les facteurs logarithmiques). Par un pre-calcul de toutes les valeurs à^a possible et le stockage de la table triee des couples (a,à^a mod p suivant leur second membre, on peut resoudre le probleme en temps O(1) mais en espace O(p), avec un pre-calcul de O(p) (en negligeant ici aussi les facteurs logarithmiques). Le premier algorithme non trivial que l'on decrit est un compromis espace-temps du a Shanks. a) Algorithme de Shanks ~~~~~~~~~~~~~~~~~~~~~~~ Sois m = |û(p-1)|. L'algorithme de Shanks est presente sur la figure 5.3. Les etapes 1 et 2 peuvent etre eventuellement pre-executees (cela ne changera toutefois pas la complexite de l'algorithme). On note ensuite que si (j,y) î L1 et (i,y) î L2, alors: à^(mj) = y = áà^-i et donc à^(mj+i) = á Inversement, pour tout á, on peut ecrire log á = mj + i à avec 0 ó j,i ò m-1. Donc la recherche de l'etape 5 aboutira. Figure 5.3: Algorithme de Shanks pour le logarithme discret ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ» º º º 1) calcul à^mj mod p, 0 ó j ò m-1 º º 2) trie les m couples (j,à^mj mod p) suivant leur second membre dans la º º liste L1 º º 3) calcul áà^-i mod p, 0 ó i ò m-1 º º 4) trie les m couples (i,áà^-i mod p) suivant leur second membre dans la º º liste L2 º º 5) cherche les couples (j,y) î L1 et (i,y) î L2 (de meme second membre) º º 6) definis log á = mj + i mod (p-1) º º à º ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ Il est facile de realiser une implementation de l'algorithme utilisant un temps O(m) et un espace O(m) (en negligeant les facteurs logarithmiques). On note que l'etape 5 peut se faire par un parcours (simultane) des deux listes L1 et L2) Voici un exemple illustratif. Exemple: Supposons que p = 809. On cherche log 525. On a donc à = 3, á = 525 et m = |û808| = 29. On a 3 à^29 mod 809 = 99 On calcule tout d'abord les couples (j, 99^j mod 809) pour 0 ó j ò 28. On obtient la liste L1: (0,1) (1,99) (2,93) (3,308) (4,559) (5,329) (6,211) (7,664) (8,207) (9,268) (10,644) (11,654) (12,26) (13,147) (14,800) (15,727) (16,781) (17,464) (18,632) (19,275) (20,528) (21,496) (22,564) (23,15) (24,676) (25,586) (26,575) (27,295) (28,81) La seconde liste contient les couples (i,525 x (3^j)^-1 mod 809), 0 ó j ò 28.On a donc la liste L2: (0,525) (1,175) (2,328) (3,379) (4,396) (5,132) (6,44) (7,554) (8,724) (9,511) (10,440) (11,686) (12,768) (13,256) (14,355) (15,388) (16,399) (17,133) (18,314) (19,644) (20,754) (21,521) (22,713) (23,777) (24,259) (25,356) (26,658) (27,489) (28,163) Si l'on parcourt simultanement les listes L1 et L2 , on trouve (10,644) dans L1 et (19,644) dans L2. Donc on a: log 525 = 29 mul 10 + 19 = 309 3 On peut alors verifier 3^309 ð 525 mod 809 Procedes de Signature: ElGamal ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ I/ La signature ElGamal ~~~~~~~~~~~~~~~~~~~~~~~ Le procede de signature d'ElGamal n'est pas deterministe, tout comme le chiffrement d'ElGamal. Cela entraine que pour un message donne, il existe plusieurs signatures valides. La fonction de verification doit donc etre capable d'accepter comme authentiques toutes les signatures valides. On donne la description du procede de signature ElGamal sur la figure 6.2 Figure 6.2: Signature ElGamal ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ» º º º Soit un nombre premier p tel que le probleme du logarithme discret dans º º ZZp soit difficile, et soit à î ZZp* une racine primitive. Soit P = ZZp*, º º A = ZZp* mul ZZ(p-1) et º º K = {(p,à,a,á):á=à^a mod p} º º Les valeurs p, à & á sont publiques et a est secret º º Pour K = (p,à,a,á) et pour un k î ZZ(p-1)* (secret) on definit º º º º sig (x,k) = (ç,ë) º º K º º o£ º º ç = à^k mod p º º et º º ë = (x - aç)k^(-1) mod (p-1) º º Pour x,ç î ZZ(p-1), on definit º º ver(x,ç,ë) = vrai <=> (á^ç)(ç^ë) ð à^x mod p º º º ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ Si la signature est construite correctement, la verification authentifie la signature car (á^ç)(ç^ë) ð à^(aç) mod p o£ l'on utilise le fait que aç + kë ð x mod (p-1) Le destinataire calcule la signature en utilisant sa clef secrete a, et une valeur aleatoire secrete k (utilisee uniquement pour la signature du message x). La verification s'effectue a l'aide de la cle publique. Prenons un petit exemple. Supposons que l'on prenne p = 467, à = 2 et a = 127 on a á = à^a mod p = 2^217 mod 467 = 132 Si le destinataire souhaite signer le message x = 100 en choisissant la valeur k = 213 (on note que pgcd(213,466) = 1 et que 213^-1 mod 466 = 431). On a ç = 2^213 mod 467 = 29 et ë = (100 - 127 mul 29)431 mod 466 = 51 N'importe qui peut verifier l'authenticite de la signature en verifiant 123^29 mul 29^51 ð 189 mod 467 2^100 ð 189 mod 467 La signature est donc valide. Etudions la securite de la signature ElGamal. Supposons qu'une personne souhaite contrefaire une signature sur le message x sans connaitre a. Si la personne choisit la valeur ç et essaye de trouver le ë correspondant, il doit calculer le logarithme discret log à^x mul á^-ç ç En revanche, si sa strategie est de choisir d'abord ë et de chercher ensuite ç, il doit resoudre l'equation (á^ç)(ç^ë) ð à^x mod p en l'inconnu ç. On ne connait pas de methode de resolution pour ce type de probleme. Cependant, ceci ne semble pas relie a un probleme bien connu tel le probleme du logarithme discret. Il reste egalement la possibilite d'obtenir ë et ç simultanement de telle sorte que (ç,ë) soit une signature valide. Personne n'a trouve de methode pour cela. Inversement personne n'a prouve que c'etait impossible. Si la personne souhaitant decrypter le message sans connaitre les cles choisit ç et ë et cherche a obtenir x,il obtient une fois de plus une instance du probleme du loagrithme discret, c'est a dire le calcul de: log (á^ç)(ç^ë) à il est donc impossible de signer un message aleatoire ainsi. Cependant, il existe une autre methode permettant a Oscar de signer un message aleatoire en choisissant ç,ë et x simultanement: soit i et j des entiers, 0 ó i ò p-2, 0 ó j ò p-2 et pgcd(j,p-1) = 1. On effectue le calcul suivant: ç = (à^i)(á^j) mod p ë = -çj^(-1) mod (p-1) x = -çij^(-1) mod (p-1) ou j^-1 est calcule modulo p-1 (c'est ici que l'on utilise le fait que j est premier avec p-1) (ç,ë) est une signature valide de x. en effet on verifie: (á^ç)(ç^ë) ð (á^(à^iá^j))(((à^i)(á^j))^-(à^i)(á^j)(j^-1)) mod p ð (á^(à^iá^j))(à^(-(ij^-1)(à^i)(á^j))(á^((-à^i)(á^j))) mod p ð à^((-ij^-1)(à^i)(á^j)) mod p ð à^(-çij^-1) mod p ð a^x mod p On illustre cette attaque par un petit exemple. Comme auparavant, on suppose p = 467, à = 2 et á = 132. On suppose qu'un personne souhaitant decrypter le message sans les cles choisisse i = 99 et j = 179 on a j^-1 mod (p-1) = 151. Cette personne calcule: ç = (2^99)(132^179) mod 467 = 117 ë = -117 mul 151 mod 466 = 41 x = 99 mul 41 mod 466 = 331 Donc (174,41) est une signature du message 331, ce que l'on peut verifier en calculant (132^117)(117^41) ð 303 (mod 467) et 2^331 ð 303 (mod 467) La signature est valide.