Le cryptosystème RSA

Dans le système RSA, chaque symbole (lettre, chiffre, caractères spéciaux, espace blanc) correspond à un nombre de trois chiffres (par exemple). Un message M sera donc envoyé converti en un nombre entier positif. Chaque utilisateur du système donne, dans un répertoire public, sa clef, qui consiste en une paire d'entier positif (n,e). Le premier entier, n, est égal au produit de deux nombres p et q, qui ne sont connus que du propriétaire de la clef. Le deuxième nombre e ( < pq), est premier relativement à p-1 et à q-1.
Lorsque Bob veut transmettre un message chiffré à Alice dont la clef publique est (n,e), il doit procéder ainsi:
 • convertir un morceau du message en un nombre entier X (ce nombre doit être inférieur à n);
 • chiffrer le nombre X en calculant (X^e) modulo n et le transmettre.
Lorsqu'Alice reçoit le message, elle le déchiffre en utilisant les opérations suivantes:
 • déchiffrer le nombre reçu en l'élevant à la puissance d modulo n, où d est l'inverse de e modulo (p-1)(q-1);
 • convertir le nombre X obtenu en une chaîne de caractères pour pouvoir lire le message.
Tout le sel de la méthode réside dans le fait que d est facile à calculer si l'on connaît p, q et e, mais que l'opération inverse (trouver p et q à partir de n et e) est pratiquement impossible.
Si p et q sont suffisamment grands, disons 160 chiffres ou plus, et s'ils sont choisis au hasard, le décryptement est pratiquement impossible par des méthodes actuellement connues. En fait, il pourrait être décrypté, mais cela demanderait un temps prohibitif.

Création des clefs

Écrivez tout d'abord une procédure FirstPrimeAbove qui nous renvoie le premier nombre premier plus grand qu'un nombre m donné.

Ecrivez votre module ici.

Fonctions utilisées: PrimeQ, While, Module.

Nous allons maintenant nous construire une clef publique afin que quelqu'un puisse nous envoyer un message secret. 
Cherchons deux nombres premiers p et q suffisamment grands:

p = FirstPrimeAbove[10^20]

q = FirstPrimeAbove[9^20]

Calculons le produit n=p q

n = p q

Choisissons (au hasard) un exposant e en vérifiant bien que e est premier relativement à (p-1)(q-1):

e = 35431

Rappel: e et (p-1)(q-1) sont premiers entre eux si le plus grand diviseur commun entre e et (p-1)(q-1) est 1.

Ecrivez ici une instruction qui vérifie que (p - 1)*(q - 1)et e sont premiers entre eux

Fonction utilisée: GCD.

Notre clef publique est donnée par:

{n, e}

Procédure de chiffrement/déchiffrement

Transformation d'une chaîne de caractères en blocs de nombres entiers de longueur L

Entrons un message secret quelconque:

messageClair = "Je vous aime à la folie!";

Les 32 premiers codes ASCII ne nous intéressent pas. Nous prenons les suivants et leur ajoutons 100 afin d'avoir dans tous les cas un nombre à 3 chiffres, ce qui nous facilitera la vie. Transformez ces lettres en nombres.

nombresClairs=(Ecrivez votre instruction ici)

Nous transformons tous ces nombres en strings, puis nous en faisons une chaîne de caractères unique.

messageChiffré = 
      Apply[StringJoin, Map[ToString, nombresClairs]]

Il s'agit maintenant de couper cette chaîne en blocs de même longueur. Calculez le nombre de sous-chaînes nécessaires pour avoir des blocs de longueur L. Ajoutez si nécessaire des 0 en début de la chaîne pour avoir une longueur multiple de L:

L = 5;     
Ecrivez les instructions manquantes ici.

Fonctions utilisées: StringLength, While, Mod, StringInsert, Quotient.

Coupons maintenant cette chaîne en sous-chaînes de longueur L, puis convertissons ces sous-chaînes en nombres entiers:

nombres = 
      ToExpression[
        Table[t[i] = 
            StringTake[
              messageChiffré, {1 + L (i - 1), L i}], {i, 1, 
            nbSousChaines}]]

RSA

Chiffrement

Connaissant notre clef publique, n'importe qui pourra nous envoyer un message secret:

nombresChiffrés=(Ecrivez votre instruction ici)

Fonction utilisée: PowerMod

Bob nous enverra donc comme message les nombres ci-dessus.

Déchiffrement

Puisque NOUS (et seulement nous), Alice, connaissons p et q, nous déchiffrons en élevant le nombre reçu à la puissance d modulo n, où d est l'inverse de e modulo (p-1)(q-1). Calculons d et déchiffrons.

d = PowerMod[e, -1, (p - 1) (q - 1)]

Écrivez l'instruction qui déchiffrera le message secret:

nombresDéchiffrés=(Ecrivez votre instruction ici)

Fonction utilisée: PowerMod

Transformation des blocs de nombres entiers en une chaîne de caractères

Transformons d'abord les nombres en strings:

liste = Map[ToString, nombresDéchiffrés]

Chaque bloc doit avoir une longueur L. Il faut donc rajouter des 0 devant les blocs trop courts avant de tout regrouper.Attention! Il ne faut pas rajouter de 0 devant le premier bloc (sauriez-vous dire pourquoi?)!

Ecrivez les instructions manquantes ici.

Fonctions utilisées: Length, For, While, StringLength, StringInsert

On peut maintenant concaténer les sous-chaînes en une seule, puis la redécouper en blocs de longueur 3.

listeDéchiffrée = 
        Apply[StringJoin, liste];
nbSousChaines = StringLength[listeDéchiffrée]/3; 
    nombresDéchiffrés = 
      ToExpression[
        Table[t[i] = 
            StringTake[
              listeDéchiffrée, {1 + 3 (i - 1), 
                3 i}], {i, 1, nbSousChaines}]]

Il n'y a plus qu'à transformer les nombres en lettres pour lire le message.

Ecrivez votre instruction ici

Exercices

Exercice 1

Construisez-vous une clef publique (pas trop grande quand même!) et échangez des messages secrets avec vos voisins.

Exercice 2

Vous avez intercepté le message suivant:

messageChiffré = {1, 337163324640220454705977128, 
          286137102820537280990513232, 836460990207150541607724217, 
          324242347705790301135202115, 941186392858264600473252547, 
          892465272270895256214303737, 560080129744097130173264121, 
          488511945518913753865430758, 39202899256354926171705690, 
          978885433698573715356549195, 40096831720729235046075184, 
          164300994547493244707559453, 909103515332937269919466157, 
          936631233541651185472002476, 708171349819762787941519160, 
          23855109156791281955874017};

Sachant que l'envoyeur a utilisé des blocs de longueur 5 et que ce message est destiné à une personne dont la clef publique est: (1138845475286514481820218141, 181), essayez de décrypter ce message.
 
 Indication: utilisez la primitive FactorInteger pour essayer de trouver p et q.
 Constatations?

Références

Schneier Bruce, Cryptograghie appliquée, International THOMSON Publishing France, 1997
Vuilleumier Bernard, Top secret !, CLUB MATH, Lettre (n^o) 25, 1er novembre 1993