Introduction au chiffrement asymétrique ElGamal

Il existe un certain nombre de tutoriels pour utiliser des logiciels de chiffrement et un bon nombre de cours de maths sur le sujet, par contre, il y a assez peu de documentation sur les principes informatique mis en oeuvre pour faire du chiffrement. Cette série de billets va chercher à expliquer un certain nombre de notions en utilisant des exemples simples, si possible reproductibles avec une calculatrice. Plutôt que croire sur parole que ces technologies sont sûres, nous essayerons, comme ci-contre Saint Thomas, de les mettre en oeuvre pour nous faire notre propre idée.

Le chiffrement est un sujet d’actualité où l’on entend beaucoup de bêtises. Il faut déjà rappeler que le chiffrement est indispensable à tout le monde et est déjà largement répandu. Nous possédons tous des données qu’il faut protéger : nos codes d’accès et les données qui nous permettent de nous identifier, d’identifier des proches, les données concernant notre santé, nos revenus, nos moyens de payement, nos bulletins de vote, … Ces données doivent être protégés des escrocs qui sauraient les exploiter à leur avantage ou de nos erreurs de manipulation qui mettraient ces données à disposition d’escrocs.

Chiffrement

Pour commencer il faut définir le «chiffrement». «Chiffrer» c’est masquer un texte pour qu’il ne soit lisible que par son destinataire.
Un texte «chiffré» doit être «déchiffré» lorsqu’il est nécessaire de le lire. Une clé d’accès permet de chiffrer et de déchiffrer le document chiffré. «Décrypter» c’est l’action de lire un texte chiffré sans posséder les clés. Notez que «crypter / cryptage» n’ont aucun sens puisqu’il s’agirait de l’inverse de décrypter : masquer un texte sans connaître la clé de chiffrement !! (C’est un truc pour détecter les ignorants).

Le chiffrement existe depuis très longtemps. César masquait ses messages secrets en décalant chaque lettre du message par la troisième lettre suivante de l’alphabet. Le décalage c’est l’«algorithme» : la façon de faire. 3 est la clé secrète. Son destinataire doit connaître l’algorithme et la clé secrète pour déchiffrer et lire le texte. Ce type d’algorithme est assez facile à décrypter en utilisant par exemple la fréquence d’usage de chaque lettre de la langue parlée : les amateurs de Scrabble savent bien que le E est la lettre la plus fréquente en français.

Chiffrement symétrique

Depuis César la science du chiffrement a fait de grand progrès. On dispose maintenant d’algorithmes qui peuvent être connus de tous. AES (qui remplace DES depuis 2001) est actuellement l’algorithme le plus sûr. Si la clé secrète est suffisamment aléatoire (elle ne peut pas être devinée) et longue (essayer toutes les possibilités prend trop de temps), un texte chiffré avec AES n’est pas décryptable malgré toute la puissance de calcul dont nous disposons sur la planète Terre.
Le chiffrement avec AES n’est pas le sujet de ce billet mais il faut noter, comme pour le chiffre de César, que le chiffrement et le déchiffrement se font avec la même clé. On parle alors de chiffrement «symétrique». La difficulté est de transmettre la clé secrète au destinataire sans risque qu’elle soit copiée au passage par un escroc.

Chiffrement asymétrique

Le chiffrement «asymétrique», apparu à la fin des années 1970, permet de chiffrer un message en connaissant une clé du destinataire connue de tous : on parle de clé publique. Cette clé publique est accessible à tous mais elle permet seulement de chiffrer et en aucun cas de déchiffrer ou décrypter le message chiffré. Le destinataire utilise sa clé privée et secrète pour déchiffrer et lire le message. Naturellement il existe un lien mathématique fort et non réversible entre la clé secrète et la clé publique. C’est le principe qui est utilisé par exemple lorsque vous consultez un site en httpS : le serveur met à disposition une clé publique que votre navigateur utilise pour chiffrer toutes les communications avec le serveur. Seul le serveur qui dispose de la clé privée comprend les commandes reçues de votre navigateur. Il n’est pas possible pour un intermédiaire d’intercepter la communication entre votre navigateur et le serveur.
Le chiffrement asymétrique utilise des fonctions mathématiques à sens unique. Une fonction largement utilisée est la factorisation d’entiers : si p et q sont deux nombres premiers (divisible uniquement par eux mêmes), le calcul de x = pq ne pose pas de problème. Par contre, dans l’autre sens, il est extrêmement difficile de retrouver p et q si l’on connaît uniquement x*. Les courbes elliptiques sont d’autres fonctions à sens unique dont l’usage se répand dans le domaine du chiffrement.

Système ElGamal

L’objet de ce billet est plus particulièrement de découvrir, à partir de quelques exemples simples, les principes de fonctionnement d’un algorithme particulier proposé en 1985: le chiffrement ElGamal.

Dans le système ElGamal à partir d’une clé secrète sk, la clé publique est un triplet (p,g,y) où p est un nombre premier, g un groupe cyclique de p et y = g^sk modulo p

La fonction modulo est, pour simplifier, le reste de la division entière (ex: 10 modulo 6 = 4). L’arithmétique modulaire propose des propriétés intéressantes dans la manipulations des nombres entiers.

Création des clés

Nous allons tous de suite faire quelques essais avec de petites valeurs que l’on peut vérifier avec une calculatrice.

Soit un utilisateur Bob avec un clé secrète skb = 5, si on prend p = 17 et g = 6. La clé publique est alors (17, 6, 7).

Une autre utilisatrice Alice a pour clé secrète ska = 3. En réalité p et g devraient être tirés au sort aléatoirement mais nous allons conserver pour notre exemple les mêmes valeurs que Bob. La clé publique de Alice est (17, 6, 12). Ici y est différent puisqu’il dépend de la clé secrète.

Vous pouvez tester ces calculs dans le formulaire ci-dessous:

Calcul de clés publiques

sk :
3
4
5
6
7
p :
13
17
23
29
g :
6
7
8

Clé publique :

Chiffrement / déchiffrement

Si Bob veut envoyer l’information secrète «5» à Alice. Il doit calculer un nombre aléatoire r et deux valeurs alpha et beta.
Avec alpha = ga^r modulo pa où ga et pa proviennent de la clé publique de Alice
et beta = ( secret * (ya^r) ) modulo pa

Alice déchiffrera avec sa clé secrète ska sans connaître r avec la formule :
( beta * (alpha ^{pa - 1 - ska}) ) modulo pa

Chiffre / déchiffre pour Alice (17,6,12)

Message secret :
4
5
6
7
8
Essayez plusieurs fois

aléa de calcul interne :
Message chiffré reçu par Alice :
Message déchiffré par Alice:
Message déchiffré par Bob:

À noter

Avec ces exemples on observe de nous même :

• le même message est chiffré différemment à chaque essai
• le message chiffré est deux fois plus long que le message secret
• les calculs de chiffrement / déchiffrement sont complexes
• rien n’assure que le message secret provient de Bob
• Bob ne déchiffre pas le message pour Alice (dans l’exemple ci-dessus on peut tomber par hasard sur le bon résultat parce que les nombres utilisés sont trop petits)

L’utilisation d’un nombre aléatoire permet d’éviter de trouver la clé en rejouant plusieurs fois le même message. C’est ainsi que les anglais, pendant la seconde guerre mondiale, identifiaient la clé des machines Enigma allemandes en cherchant dans les bulletins météo le mot Wetter.
Il est essentiel de rappeler que le générateur d’aléa est un élément important dans le chiffrement, aussi bien pour le système ElGamal que pour la création des nombres premiers lors de la création des clés. D’ailleurs, en réalité, il est impératif d’utiliser des nombres premiers les plus grands possible et nettement supérieurs à 10000, sinon il est facile de calculer à l’avance des nombres premiers et des clés prévisibles.

La complexité des calculs et la taille des messages chiffrés font qu’en pratique le système ElGamal n’est pas utilisé pour chiffrer des textes mais plutôt pour chiffrer la clé symétrique à usage unique qui chiffre le texte qui doit rester confidentiel. Cela permet alors également à Bob de relire son message en chiffrant la clé symétrique pour lui même en plus du chiffrement pour Alice. Cette méthode de chiffrement de la clé symétrique est utilisée dans GnuPG, un logiciel libre dérivé de PGP, largement utilisé pour le chiffrement de mail en particulier au travers du plugin Enigmail pour le client de messagerie Thunderbird.

Comme le chiffrement ne permet pas de s’assurer de l’identité de l’expéditeur, il faut ajouter un autre mécanisme : une «signature électronique». Cette signature électronique est une somme d’identification du texte, chiffrée avec la clé publique de l’expéditeur. Cette signature est optionnelle. Elle n’est pas nécessaire si l’on chiffre des informations pour soi-même. Un texte chiffré peut volontairement rester anonyme. Je reviendrais certainement à ce mécanisme de signature électronique dans une futur billet.

Avec ces exemples nous constatons que le chiffrement est par principe sûr. Il faut cependant respecter un certain nombre de contraintes.

Contraintes

Voici le code utilisé dans les formulaires ci-dessus: (il s’agit de code javascript, exécuté par votre navigateur sur votre machine et non sur le serveur)

/** 
*  Calcul de clés publiques ElGamal
**/
function pkform() {
 var sk = document.forms["pkform"].elements["sk"].value;
 var p = document.forms["pkform"].elements["p"].value;
 var g = document.forms["pkform"].elements["g"].value;

 var y = Math.pow(g,sk) % p;

document.getElementById("pk").innerHTML = '(' + p + ',' + g + ',' + y + ')';
}

/**
* Chiffre pour Alice et déchiffre par Alice
**/
function chiffreform() {
 var secret = document.forms["chiffreform"].elements["secret"].value;

 // Alice public key
 var pa = 17; var ga = 6; var ya = 12;
 // Alice secret key
 var ska = 3;

 // Chiffre
 //  Nombre aléatoire
 var r = Math.floor(Math.random() * (pa - 1) ) + 2;
 //  Message chiffré
 var alpha = Math.pow(ga,r) % pa ;
 var beta =  ( secret * Math.pow(ya,r) ) % pa ;

 // Déchiffre
 var res = ( beta * Math.pow(alpha,(pa - 1 - ska)) ) % pa ;


 // Bob public key
 var pb = 17; var gb = 6; var yb = 7;
 // Bob secret key
 var skb = 5;
 // Bob essaie de déchiffrer
 var resb = ( beta * Math.pow(alpha,(pa - 1 - skb)) ) % pa ;


 // Affichage
 document.getElementById("random").innerHTML = r;
 document.getElementById("chiffre").innerHTML = '(' + alpha + ',' + beta + ')';
 document.getElementById("dechiffre").innerHTML = res;
 document.getElementById("BOBdechiffre").innerHTML = resb;
}

Ce code est simple mais cela reste du code de démonstration : avec des nombres premiers supérieurs à 17 le calcul d’exposant va dans certains cas déborder les capacités prévues pour les variables : on risque d’obtenir des nombres négatifs. Les calculs seront faux. Pour du code réel, il faut utiliser des bibliothèques qui gèrent les grands entiers.

Néanmoins écrire du code de chiffrement reste un exercice délicat : il est difficile de s’assurer qu’il n’y a aucune erreur. Faut-il protéger les valeurs secrètes en mémoire ? Le générateur de nombres aléatoires est-il suffisamment aléatoire ? Il est alors préférable d’utiliser des bibliothèques qui ont été vérifiées et auditées.

Conclusion

Maintenant que nous disposons des bases du chiffrement avec le système ElGamal, nous verrons dans un futur billet d’autres propriétés intéressantes de ce système.
Nous verrons en particulier comment chiffrer/déchiffrer pour un groupe. Comment effectuer des calculs sur des données chiffrées. Comment vérifier la qualité du chiffrement sans déchiffrer…