TP 3 - Les chiffrements asymétriques

Auteur·rice

Affiliations

Chiffrement El Gamal

Le chiffrement d’El Gamal est un protocole de cryptographie asymétrique inventé par Taher El Gamal en 1984 et qui repose sur le problème du logarithme discret.

Génération des clés

La première étape du schéma de chiffrement consiste à produire une pair de clés : la clé publique et la clé secrète (ou clé privée). La première servira à chiffrer les messages et la deuxièmes à les déchiffrer.

Pour générer sa pair de clés, il faut d’abord choisir un nombre premier $p$ et un générateur $g$ pour $\mathbb{Z}/p \mathbb{Z}$.

Ensuite, il faut choisir un $s$ de $\mathbb{Z}/p \mathbb{Z}$ qui constituera la clé privée, et calculer $h = g^s \mod p$.

Pour terminer, la clé publique est $(p, g, h)$.

Chiffrement

Pour chiffrer un message $M$ encodé comme un entier de $\mathbb{Z}/p \mathbb{Z}$ avec la clé publique $(p, g, h)$, il faut tirer au hasard un aléa $r$ dans $\mathbb{Z}/p \mathbb{Z}$ et calculer $C_1 = g^r \mod p$ et $C_2 = (M \cdot (h^r \mod p))$. Ansi le chiffré $C$ est composé de ces deux nombres : $C = (C_1, C_2)$.

Déchiffrement

Ayant accès à $C = (C_1, C_2)$ et à la clé privée $s$, pour déchiffrer il suffit de calculer :

\[ (C_2 \cdot ((C_1)^s \mod p)^{-1} \mod p) \mod p \]

pour retrouver le message $M$.

Exercice 1

Écrivez une fonction Python3 key(k) qui permet de générer une pair de clé El Gamal, avec un module compris entre $2^k$ et $2^{k + 1} - 1$.

La taille est importante ! Plus vos clés seront de grands nombres, plus elles seront sûres. Le “paramètre de sécurité” est donc le nombre de bits du module $p$, autrement dit son logarithme binaire $k$.

Astuce

Vous aurez peut-être l’usage de la fonction randprime de la bibliothèque sympy (éventuellement à installer en utilisant la commande pip install sympy) et de la fonction randint de la bibliothèque standard random. Pour calculer $x^n \mod p$ vous devrez utiliser pow(x, n, mod=p) car (x ** n) % p ne marche pas pour les grands nombre.

Choisissez comme module un nombre premier $p$ au hasard compris entre $2^{k} et $2^{k + 1} - 1$.
Choisissez comme génératuer un nombre $g$ au hasard compris entre $2$ et $p - 1$.

Remarque

Votre “générateur n’en est peut-être pas un ! Pour gagner du temps, on ne vous demande pas de le vérifier : la procédure de chiffrement/déchiffrement marche encore, mais votre clé sera plus facile à casser, car il y aura plusieurs valeurs possibles pour $s$, en plus de celle qui sera vraiment votre clé secrète.

Choisissez comme secret un nombre $s$ au hasard compris entre $2$ et $p - 1$.
Calculez $h$.

Exercice 2

Écrivez une fonction Python3 encrypt(K, M) qui permet de chiffrer un nombre $M$ avec le chiffrement d’El Gamal.

Exercice 3

Écrivez une fonction Python3 decrypt(K, C) qui permet de déchiffrer un chiffré $(C_1, C_2)$ avec le chiffrement d’El Gamal.

Vous pouvez utiliser l’inverse de $x$ modulo $p$ (s’il existe) par pow(x, -1, mod=p).

Exercice 4

Fondamentalement, le chiffrement d’El Gamal s’applique à des nombres. Mais très souvent, les message qu’on souhaite chiffrer sont plutôt des textes ! Pour chiffrer des textes, il faut donc passer par une étape préalable de numérisation des caractères qui le composent.

Écrivez une fonction en Python3 encode(text) qui converti une chaîne de caractères $texte$ en un nombre entier. Il y a plusieurs manière de faire cela, voici celle que nous proposons ici :

Chaque caractère est encodé par son code ASCII décimal, composé de 1, 2 ou 3 chiffres. Étant donné un caractère $c$, le code ASCII correspondant est obtenu par ord(c).
Les codes ASCII des caractères sont transformés en str puis ramenés sur 3 chiffres en ajoutant si nécessaire des $0$ à gauche.
Les chaînes représentant les codes ASCII sur 3 chiffres sont concaténées les unes à la suite des autre pour obtenir une seul (grande) chaîne, ensuite transformée en int.

Écrivez une fonction Python3 decode(number) effectuant l’opération inverse : étant donné un nombre entier $number$, retrouver la chaîne de caractères texte qu’il représente.

Pour cela, utilisez la fonction chr. Étant donné un code ASCII donné $num$, la caractère associé est obtenu par chr(num).

Pour récupérer les codes ASCII des différents caractères, vous voudrez peut-être utiliser le reste % et le quotient //de la division par $1000$.

Testez vos fonction d’encodage/décodage. On doit avoir, pout tout message $M$:

\[ M = decode(encode(M)) \]

Exercice 5

À ce state, vous pouvez chiffrer, déchiffrer des messages entre vous.

Un voisin vous communique sa clé publique. Vous pouvez donc lui envoyer des messages chiffrés.
Choisissez un message texte ((très) court ! puisque le nombre encodant votre message ne doit pas dépasser son module). Convertissez-le en nombre. Chiffrez le nombre. Envoyez le cryptogramme résultant à votre voisin.
Votre voisin déchiffre le cryptogramme. Puis il décode le nombre obtenu et retrouve votre texte.

Exercice 6

Pour pouvoir échanger des messages aussi longs que vous voulez, écrivez une fonction qui découpe les entiers trop longs pour en faire plusieurs messages.

Exercice 7

Écrire une fonction exp_basique(x, n, p) qui, pour trois entiers positifs $x, n$ et $p$ donnés en entrée, calcule de manière basique (sans utiliser la bibliothèque math) l’exponentielle modulaire :

\[ x^n \mod p \]

L’algorithme d’exponentiation rapide permet également de calculer le nombre :

\[ x^n \mod p \]

mais en utilisant l’algorithme récursif suivant :

\[ puissance(x, n) = \begin{cases} x, &\text{si } n = 1 \\ puissance(x^2, n / 2), &\text{si } n \text{ est pair} \\ x \cdot puissance(x^2, (n - 1) / 2), &\text{si } n \text{ est impair} \end{cases} \]

Écrire une fonction exp_rapide(x, n, p) implémentant cet algorithme.

Calculez le nombre suivant, avec les deux méthodes :

\[ 123456789^{123456789} \mod 987654321 = ? \]

Que constatez-vous ?