05 déc. 2015

Propriétés du chiffrement ElGamal

Après avoir découvert les principes du chiffrement asymétrique ElGamal, nous allons aborder les propriétés remarquables de ce système de chiffrement. Ici aussi vous pourrez tester les algorithmes et vous faire une idée avec des valeurs suffisamment petites pour rester lisibles.

Les calculs sont toujours réalisés par votre navigateur. Vous pouvez afficher le code source de la page pour visualiser les codes javascript. Ceux-ci sont volontairement écrits de façon linéaire pour faire clairement apparaître les formules utilisées.

Comme certaines formules mathématiques sont relativement complexes, nous allons utiliser la bibliothèque BigInteger de Peter Olson pour manipuler de grands entiers. Cette bibliothèque peut gérer sans problème des nombres de 2048 bits ou 610 chiffres. Il s’agit de la taille recommandée de nos jours pour s’assurer de la robustesse du chiffrement.

Création de clé

Nous avons vu que pour créer la clé publique (p,g,y) à partir de la clé privée sk, il suffit de calculer y = g^sk modulo p où g est un groupe cyclique de p.

Dans l’algorithme d’ElGamal généralisé, on utilise également un nombre q copremier de p. On peut alors vérifier que g^(p-1)/q est différent de 1 pour que g soit un groupe cyclique.

Voici le code javascript qui permet essentiellement d’illustrer l’usage de la bibliothèque BigInteger :

 var p = bigInt('29'); var g = bigInt('6'); var sk = bigInt('3');
 var y = g.modPow(sk,p);

 var cg = g.modPow( (p.subtract(1)).divide(q) , p);

La bibliothèque Math::BigInt de Perl a une syntaxe objet très proche :

 use Math::BigInt;

 my $pa = Math::BigInt->new('29'); my $g = Math::BigInt->new('6'); my $sk = Math::BigInt->new('3');
 my $y = $g->bmodpow($sk,$p);

 my $cg = $g->bmodpow( ($p->bsub(1))->bdiv($q) , $p);

La plupart des langages de programmation disposent de bibliothèques spécifiques pour gérer les très grands entiers.

Calcul de clés publiques
Clé publique :
Groupe cyclique g : (doit être différent de 1)

On peut noter le nombre premier de 15 chiffres.

Chiffrement, déchiffrement

Pour chiffrer un secret, il faut utiliser les éléments (p,g,y) de la clé publique du destinataire, suivant les formules suivantes :
alpha = g^r modulo p
beta = secret . y^r modulo p
Le message chiffré est composé du couple (alpha,beta). Il faut noter le nombre r qui est un nombre aléatoire non diffusé et permet d’obtenir des valeurs variables de alpha et beta à chaque nouveau chiffrement d’un même secret.

Pour déchiffrer, le destinataire utilise sa clé privée sk:
dechiffre = beta . alpha^{p - sk - 1} modulo p

(Le message chiffré ci-dessous sera utilisé dans d’autres formulaires)

Chiffre / déchiffre pour Alice (29,6,13)
aléa de calcul interne :
Message chiffré reçu par Alice :
Message déchiffré par Alice:

Double chiffrement

ElGamal permet de chiffrer plusieurs fois le même message :
alphaR = alpha . g^r modulo p
betaR = beta . y^r modulo p

L’algorithme de déchiffrement est identique quel que soit le nombre de chiffrements.

Re Chiffre / déchiffre pour Alice (29,6,13)
Message chiffré reçu par Alice :
Message rechiffré reçu par Alice :
Message déchiffré par Alice:

Chiffrement pour Alice ET Bob

Il est possible de créer une clé partagée entre Alice et Bob où Alice et Bob doivent coopérer pour déchiffrer les messages reçus.
Il faut alors utiliser les mêmes nombres p et g. Dans notre exemple, la clé secrète de Alice ska a pour valeur 3. On peut alors calculer ya. La clé secrète de Bob skb a pour valeur 7. On calcul alors yb.
La clé secrète commune skab = ska + skb et yab = ya . yb modulo p

Dans l’exemple ci-dessous on constate que Alice ou Bob ne peuvent pas déchiffrer individuellement le message secret:

Chiffre pour Alice (29,6,13) ET Bob (29,6,28)
Message chiffré reçu par Alice ET Bob :
Message déchiffré par Alice :
Message déchiffré par Bob :
Message déchiffré par Alice ET Bob :

On peut également envisager un «chiffrement à seuil» pour partager une clé. Le «seuil» est le nombre minimum et nécessaire pour déchiffrer un message. Ainsi une clé peut être découpée pour 3 personnes et seules les clés de 2 personnes parmi les 3 sont nécessaires pour déchiffrer. Cela fera peut-être l’objet d’un futur billet.

Multiplication homomorphe

Le système ElGamal possède la propriété homomorphe de multiplication, donc :
Enc(a) . Enc(b) = Enc(a . b)
On peut tester cette propriété ici (il faut avoir chiffré une première valeur dans le formulaire initial).

Autre secret pour Alice (29,6,13)
Message chiffré reçu par Alice :
Autre message chiffré reçu par Alice :
Chiffré pour Alice x Autre chiffré pour Alice:
Message déchiffré par Alice :

Cette propriété homomorphe permet d’effectuer des opérations sur des messages chiffrés sans utiliser (et donc exposer) la clé secrète.

Addition “homomorphe”

En réalité le système ElGamal ne possède pas la propriété homomorphe d’addition mais les propriétés des puissances permettent de créer des additions de puissances en multipliant les exposants du nombre g :

Enc(g^a) . Enc(g^b) = Enc(g^a . g^b) = Enc(g^{a + b})

La difficulté est ensuite de résoudre g^{a + b}.

On peut envisager de calculer toutes les solutions possibles en les chiffrant / déchiffrant mais l’opération est longue et expose la clé secrète.
Il est plus sûr et plus rapide de calculer le tableau des logarithmes discrets des solutions possibles.

Addition pour Alice (29,6,13)

L’exemple ci-dessus commence à ressembler à un vote. Les choix de Bob, Carole et Dave pourraient être des bulletins chiffrés. Il n’est pas possible de déterminer le choix de chacun en observant les messages chiffrés. Cependant on se rend également compte que si quelqu’un chiffre g¹⁰⁰ le résultat est totalement faussé.

Vérification

Lorsqu’un texte est déchiffré si celui-ci est intelligible, il est clair que les opérations de chiffrement/déchiffrement ont réussi. Lorsqu’il s’agit uniquement d’un nombre il est difficile d’être aussi affirmatif. La solution est d’ajouter une preuve cryptographique de déchiffrement. Cette preuve ne doit pas exposer la clé secrète.

Preuve à divulgation nulle de connaissance

La preuve de déchiffrement ajoute à chaque message chiffré les éléments A et B suivants:
A = g^w modulo p (w est un nombre aléatoire)
B = y^w modulo p
ainsi que couple challenge-réponse où
challenge est un nombre aléatoire
reponse = w + r . challenge r est le nombre aléatoire qui a permis de calculer alpha et beta

L’opération de vérification devient alors le contrôle des deux égalités suivantes :

g^reponse = A . alpha^challenge
y^reponse = B . (beta/secret)^challenge

Ce contrôle se fait sans usage de la clé secrète sk et sans exposer le nombre aléatoire r utilisé lors du chiffrement.

La difficulté technique est qu’il faut diviser des entiers de façon précise.

Chiffre / déchiffre pour Alice (29,6,13)

Message chiffré reçu par Alice :
Preuves de chiffrement Challenge, réponse

Message déchiffré par Alice:
Vérification :

À retenir

Le système de chiffrement ElGamal permet de chiffrer et déchiffrer des messages avec un système de clés asymétriques mais également d’effectuer un certain nombre d’opérations sur les messages chiffrés : multiplication, addition, vérification tout en protégeant l’élément le plus important d’une système de chiffrement : la clé secrète.

Un futur billet présentera l’assemblage de ces diverses propriétés du système ElGamal pour améliorer la confiance des systèmes de votes électroniques.

lab.yvesago.net

De l'informaTIC