C15.4 : TD - Chiffrement KidRSA

Dans ce TP, nous allons utiliser une version plus simplifiée du chiffrement RSA nommée KidRSA.

Principe de l’algorithme KidRSA

• On choisit 4 entiers : \(a_1\), \(b_1\), \(a_2\) et \(b_2\).

• On calcule les entiers suivants :

\(M = a_1 × b_1 - 1\)
\(e = a_2 × M + a1\)
\(d = b_2 × M + b1\)
\(n = (e × d – 1) / M\)

• La clé publique est l’ensemble des deux entiers \((e, n)\).

• La clé privée est l’ensemble des deux entiers \((d, n)\).

• Pour chiffrer un message représenté par un entier \(m_{clair}\) plus petit que \(n\), on effectue l’opération \((e × m_{clair}) \bmod n\) où \(\bmod\) est l'opérateur modulo.

• Pour déchiffrer un message représenté par un entier \(m_{chiff}\) plus petit que \(n\), on effectue l’opération \((d × m_{chiff}) \bmod n\).

1. Le chiffrement RSA est un « chiffrement asymétrique ». Expliquer la signification de ce terme.

Partie A : Implémentation du chiffrement KidRSA

Un exemple (avec des petits nombres)

Prenons \(a_1 = 5\), \(b_1 = 3\), \(a_2 = 7\) et \(b_2 = 5\).

2. Calculer \(M\), \(e\), \(d\) et \(n\).

3. En déduire la clé publique et la clé privée.

4. A chaque caractère, on associe son point de code unicode.

On pourra utiliser les fonctions ord(caractere) et chr(entier) qui permettent de connaitre le point de code d’un caractère et inversement.

On s’intéresse à la lettre 'a' dont le point de code unicode est 97.

4.a. Qu’elle valeur obtient-on en chiffrant la lettre 'a' ?

4.b. Montrer que le déchiffrement à l’aide de la clé privée est correct.

Implémentation en Python du chiffrement KidRSA

5. Écrire le code de la fonction genere_cles_publique_et_privee(a1, b1, a2, b2), qui calcul et retourne la clé publique (e, n) et la clé privée (d, n) sous forme de deux tuples à partir des quatre entiers a1, b1, a2, b2 passés en paramètres.

6. Écrire le code de la fonction chiffre_message(m, cle) qui prend une chaine de caractère m et un tuple cle en paramètres et renvoie le message chiffré sous la forme d’une liste de nombre entiers.

7. Écrire la fonction dechiffre_message(li, cle) qui déchiffre un message li qui est une liste de nombres entiers et renvoie le message déchiffré sous la forme d’une chaîne de caractères.

Tests de cette implémentation en Python de KidRSA

On choisit comme valeurs \(a_1 = 13\), \(b_1 = 32\), \(a_2 = 69\) et \(b_2 = 35\).

8. Donner les valeurs de la clé publique et de la clé privée.

9. Donner la liste chiffrée correspondant à la chaîne de caractères 'NSI' en utilisant la clé publique.

10. Vérifier que le déchiffrement de la liste obtenue avec la clé privée redonne bien le message 'NSI'.

Partie B : Décryptage du chiffrement KidRSA par la force brute

La force brute

Un message a été chiffré avec KidRSA à l’aide de la clé publique suivante \((e, n) = (53447, 5185112)\).

Voici le message chiffré obtenu :

[3580949, 2084433, 3687843, 4436101, 4489548, 1710304, 4329207, 4542995, 3901631, 1710304, 4061972, 3687843, 1710304, 3527502, 4222313, 4436101, 4436101, 1710304, 3687843, 4168866, 1710304, 4168866, 4436101, 3901631, 1710304, 3367161]

On souhaite décrypter le message chiffré pour retrouver le message clair. Pour cela, on a besoin de connaître la clé privée \((d, n)\). Comme on connait déjà \(n\) (\(n = 5185112\)), il faut trouver une méthode pour calculer \(d\).

La relation entre les nombres \(e\), \(d\) et \(n\) des clés publique et privée donne : \(e×d-1=n×M\).

On en déduit que \((e×d-1)\) est divisible par \(n\).

Pour trouver l’entier \(d\) qui fait partie de la clé privée, comme on connait déjà \(e\) et \(n\), il suffit d’étudier parmi toutes les valeurs de \(d\) comprises entre \(1\) et \(n-1\), celle qui vérifie la condition « \(e × d - 1\) est divisible par \(n\) ».

On appelle ce type d’attaque « attaque par force brute » car on doit étudier (dans le pire des cas) tous les entiers \(d\) inférieurs à \(n\), ce qui peut être long si \(n\) est grand.

11. Écrire le corps de la fonction bruteForceKidRSA(e, n) qui calcule et qui renvoie le premier entier \(d\) inférieur à \(n\) qui vérifie la relation « \(e×d-1\) est divisible par \(n\) ».

12. En déduire la valeur de \(d\) pour la clé publique proposée puis déchiffrer le message.

Limite de la force brute

La réponse au message chiffré précédent est aussi chiffrée avec KidRSA mais avec une clé publique de longueur beaucoup plus grande.

Voici la clé publique utilisée : \((e, n) = (230884490440319, 194326240259798261076)\).

Et voici le message chiffré obtenu avec la clé publique :

[20548719649188391, 25628178438875409, 27013485381517323, 7388303694090208, 22395795572710943, 26320831910196366, 23319333534472219, 7388303694090208, 26782600891077004, 24011987005793176, 23319333534472219, 7388303694090208, 24704640477114133, 24242871496233495, 25397293948435090, 23781102515352857, 7388303694090208, 25628178438875409, 23550218024912538, 7388303694090208, 26782600891077004, 24011987005793176, 23319333534472219, 7388303694090208, 22626680063151262, 25628178438875409, 26551716400636685, 26551716400636685, 23319333534472219, 26551716400636685, 7388303694090208, 7619188184530527, 2307921366441428724]

13. Essayer de retrouver la clé privée à l’aide de la fonction précédente. Quel est le problème rencontré ?

Partie C : Décryptage avec l'algorithme d'Euclide étendu

L'attaque par force brute n'est pas envisageable lorsque la clé est trop longue. Il existe une méthode plus efficace basée sur l'algorithme d'Euclide étendu. L'algorithme d'Euclide étendu est beaucoup plus efficace que l'attaque par force brute car sa complexité en temps est, dans le pire car, en \(\mathcal O(log(n))\) alors que celle de l'attaque par force brute est en \(\mathcal O(n)\).

Théorème de Bézout

Soient \(a\) et \(b\) deux entiers naturels non nuls.

\(a\) et \(b\) sont premiers entre eux si et seulement si il existe deux entiers relatifs \(u\) et \(v\) tels que \(au+bv=1\)

Algorithme d'Euclide étendu pour trouver \(u\) et \(v\)

On procède comme pour l'algorithme d'Euclide, mais à chaque étape on cherche à écrire le reste \(r\) comme combinaison linéaire de \(a\) et de \(b\).

Exemple

Prenons \(a = 135\) et \(b = 101\) (\(a\) et \(b\) sont premiers entre eux). On cherche \(u\) et \(v\) tels que \(au+bv=1\).

Dividende	Diviseur	q	r	Combinaison linéaire
\(135\)	\(101\)	\(1\)	\(34\)	\(\begin{aligned}[t] 34 &= 135 - 1 × 101 \\ 34 &= 1 × a - 1 × b \end{aligned}\)
\(101\)	\(34\)	\(2\)	\(33\)	\(\begin{aligned}[t] 33 &= 101 - 2 × 34 \\ 33 &= (0 × a + 1 × b) - 2 × (1 × a - 1 × b) \\ 33 &= -2×a + 3×b \end{aligned}\)
\(34\)	\(33\)	\(1\)	\(1\)	\(\begin{aligned}[t] 1 &= 34 - 1 × 33 \\ 1 &= 1 × (1×a - 1×b) - 1 × (-2×a + 3×b) \\ 1 &= 3×a - 4×b \end{aligned}\)

Remarque : le fait que le reste soit égale à \(1\) à la dernière ligne confirme que \(a\) et \(b\) sont premiers entre eux, puisque l'algorithme d'Euclide permet d'obtenir le plus grand multiple commun.

Le principe de l'algorithme KidRSA permet d'écrire que \(e×d - n×M = 1\), où \((e,n)\) est la clé publique, donc \(e\) et \(n\) sont connus.

L'application de l'algorithme d'Euclide étendu permet de trouver \(d\) (et \(M\)).

14. En appliquant l'algorithme d'Euclide étendu "à la main", retrouver la clé privée associé à la clé publique \((17,55)\).

Le code ci-dessous est une implémentation récursive de l'algorithme d'Euclide étendu.

def euclide_etendu(a, b):
    """
    Paramètres :
        a (int) : un entier strictement positif tel que a et b soient premiers entre eux.
        b (int) : un entier strictement positif tel que a et b soient premiers entre eux.
    Valeur renvoyée
        (tpl) : un triplet d'entiers donnant le pgcd, et les deux coefficients de Bézout.
    """
    if a == 0:
        return (b, 0, 1)
    else:
        r, y, x = euclide_etendu(b % a, a)
        return (r, x - (b//a) * y, y)

15. En utilisant la fonction précédente, écrire une fonction qui prend une clé publique en paramètre et renvoie la clé privée correspondant.

16. Retrouver, "informatiquement", les valeurs de la question 14.

17. En déduire la clé privée associée à la clé publique : \((230884490440319, 19432624025979826176)\).

18. Décrypter le message de la question 13.

Compléments

• Lien sur interstices.info : Clés RSA

• Lien : Algorithme d'Euclide étendu sous sa forme récurrente