ElGamal
(Contribution de Lutin Noir)
Brève présentation du schéma de signature ElGamal :
Je vais essayer d’expliquer au mieux comment fonctionne le schéma de chiffrement ElGamal, dont les détails sont donnés dans ElGamal: Algorythmes à clés puliques:
Tous d’abord voici comment fonctionne le système de signature :
Un utilisateur A veut signer un message M. Il choisit d’abord un nombre premier p, puis deux nombres g et x inférieurs à p. Ensuite il doit calculer y :
y = g^x mod p (^ = puissance)
L’utilisateur A a maintenant ses clés publiques (p, g, y) et sa clé privée (x) qu’il ne doit pas diffuser. Désormais, il est en mesure de signer un message M, et un utilisateur B peut vérifier que c’est bien A qui a signé le message. Pour ce faire, A choisit un nombre k tel que k et (p-1) soient premiers entre eux. Ensuite il calcule :
a = g ^ k mod p
Puis il utilise l’algorithme d’Euclide pour résoudre l’équation suivante :
M = (x*a + k*b) mod (p-1)
Ou
b = ( k ^ (-1) ) * ( M – x*a) mod (p-1)
Maintenant l’utilisateur A a la signature du message M, c’est le couple (a,b). B peut maintenant vérifier que c’est bien A qui a signé M grâce aux clés publiques de A. Pour ce faire il doit vérifier que :
y^a * a^b mod p = g ^ M mod p
Si les deux membres de l’équation sont égaux alors la signature est valide et B sait que A a bien signé le message M.
Supposons maintenant qu’un utilisateur C veuille se faire passer pour A et signer le message M. Plusieurs possibilités se présentent à lui (bien entendu dans la mesure où ceci est réalisable), il peut soit trouver la clé privée de A, soit forger une signature qui vérifiera l’équation
Comment C peut-il trouver x ? Et bien il lui suffit de résoudre y = g^x mod p : c’est le problème des logarithmes discrets (ou DLP).
Comme je ne maîtrise pas encore assez bien ce domaine des mathématiques pour l’expliquez correctement, je vous suggère de lire le chapitre 3 (p. 103) de Hanbook of Applied Cryptography qui explique très bien ce qu’est un DLP et comment il est possible de le résoudre (enfin quand ceci est le cas) et notamment grâce au l’algorithme de Pollard Rho.
Vous pouvez aussi lire le texte de Pierrick Gaudry qui explique cela très bien.