Devoir sur RSA

Devoir sur RSA#

Objectifs#

  • Démontrer une propriété mathématiques avec des nombres premiers en utilisant les congruences

  • Implémenter un algorithme

Consignes#

Vous répondrez aux questions signalées par 📐 en utilisant votre cours et vos connaissances. la rédaction comptera pour une part importante de l’évaluation.

Vous répondrez aux questions signalées par 🐍 en écrivant

  • une fonction conforme au nom de l’énoné (snake_case)

  • une description de la fonction sous la forme d’un docstring

  • un exemple d’utilisation de la fonction dans la docstring

  • un jeu d’exemple avec assert

  • optionnellement : des indications de type.

Des fonctions utiles vous seront données en annexe.

L’algorithme kidRSA#

Pour commencer#

  1. 🐍 📐 Donner le nom des concepteurs de l’algorithme RSA

  2. 🐍 📐 Expliquer brièvement le principe général de RSA, du point de vue mathématiques

Le principe de l’algorithme kidRSA#

On choisit quatre entiers \(a1, a2, b1, b2\). On calcule ensuite

  • \(M = a1 × b1 - 1\)

  • \(e = a2 × M + a1\)

  • \(d = b2 × M + b1\)

  • \(n = \frac{e×d - 1}{M}\)

  1. 📐 Donner la factorisation de \(n\).

  2. 📐 Calculer \(ed \mod n\).

  3. 📐 Quelle condition faut-il ajouter pour que le calcul de \(m × e \mod n\) puisse être effectif ?

  4. 📐 Expliquer pourquoi la connaissance de \((e, n)\) ne permet pas facilement de trouver \(d\).

  5. 📐 Proposer une méthode pour trouver \(d\) à partir de \((e,n)\).

On appelle \((e,n)\) la clef publique du message et \((d,n)\) la clef secrète du message.

Un exemple#

  1. 🐍 📐 Calculer \(e, d, n\) avec \(a1 = 5, \)b1 = 3, a2 = 7, b2 = 5$.

  2. 🐍 📐 Donner les clefs publiques et secrètes.

  3. 📐 Donner le message secret correspondant au nombre \(m = 97\), puis montrer que \((d,n)\) permet bien de retrouver 97.

Implémentation 🐍#

  1. Écrire une fonction genere_clefs() qui renvoie (e, d, n) conformément à la spécification du principe.

  2. Écrire une fonction chiffre_message(message, clef) qui renvoie la version chiffrée d’un message. Chaque caractère du message est remplacé par son point de code, exprimé en décimal sur lequel sera appliqué la transformation.

    Autrement dit, la fonction chiffre_message renvoie une liste de nombre de même longueur que la chaine message.

  3. Écrire une fonction dechiffre_message(message_chiffre, clef) qui déchiffre le message.

«Casser» cette implémentation de kidRSA#

On suppose qu’on connait \((e, n) = (53447,5185112)\) et que le message obtenu est

 [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]

  1. 🐍 📐 Donner une méthode simple pour retrouver le message.

  2. 🐍 Proposer une amélioration pour éviter que la méthode précédente puisse être utilisée.

  3. 📐 Expliquer pourquoi trouver \(d\) revient à chercher toutes les valeurs \(d\) comprises entre \(1\) et \(n-1\) telles que \(n | ed - 1\).

  4. 📐 Reformuler \(ed \equiv 1 \mod n\) avec l’égalité de Bézout.

  5. 📐 Utiliser l’algorithme d’Euclide étendu pour trouver \(d\) avec \(e = 19432624025979826176\) et \(n = 230884490440319\)

Le monde réel#

  1. 🐍 📐 Donner la taille des clefs recommandées pour les implémentations réelles de RSA

  2. 🐍 Quelle technologie pourrait casser cet algorithme ?

  3. 📐 Quel développement mathématique pour casser cet algorithme ?

Pour compléter, une lecture pertinente |: https:|//culturemath.ens.fr/thematiques/lycee/voyage-au-coeur-de-la-cryptographie

Contenu