RSA – code Mupad - envoi de message crypté sous forme numérique

Le code est divisé en morceaux représentant chacun une étape

Les textes en rouge sont du code MuPad et doivent être inscrits dans des paragraphes de calcul (Insert Calaulation, raccourci : cmd-I pour Mac ou CTRL-I sur PC). Les textes en noir sont à inscire dans des paragraphes textes entre deux

Après chaque morceau de code, insérer un paragraphe calcul pour tester les fonctions définues sur un exemple

Il vaut toujours mieux fractionner le code en petits morceaux qu'on puisse tester séparément!!

Ce code Mupad vous permet

Créer des fonctions utiles

Notes sur les fonctions internes de Mupad utilisées

Convertir un texte en une suite de nombres et vice-versa

texte2nombres := numlib::toAscii:
nombres2texte := numlib::fromAscii:
base := 128: // taille du jeu de caractères

Regroupement d'une liste de nombres par blocs de k nombres

nombres2blocs := proc(liste, k)
// regrouper la liste par blocs de k nombres
local n, nblocs, m;
begin
 n := nops(liste): // nombre de termes de la liste donnée
 m := -n mod k: // nombre de termes à ajouter pour obtenir un multiple de k
 nblocs := (n+m)/k: // nombre de blocs
 liste1 := liste . [126 $ i = 1..m]: // ajout de m termes
 [[liste1[l*k + i] $ i = 1..k] $ l = 0..nblocs-1]: // regroupement
end_proc:

Conversion des blocs en grands nombres

// convertir un bloc de nombres en un grand nombre
bloc2nombre := proc(liste,base)
 local x;
begin
 x := 0:
 for y in liste do
  x := x*base + y:
 end_for:
 x:
end_proc:
// convertir une suite de blocs en une suite de grands nombres
blocs2nombres := (liste,base)->[bloc2nombre(l,base) $ l in liste]:

Réciproque :

conversion d'une liste de grands nombres en une liste simple de nombres

grandnombre2bloc := proc(nombre,base,taille)
 local x, reste, quotient;
begin
 x := [0 $ i = 1..taille]:
 quotient := nombre:
 reste := 0:
 for i from 1 to taille do
  j := taille - i + 1:
  reste := quotient mod base:
  quotient := floor(quotient/base):
  x[j] := reste:
 end_for:
 x:
end_proc:
//
grandsnombres2nombres := (nombres,base,taille)->
   _concat(grandnombre2bloc(nombre,base,taille) $ nombre in nombres);
//

Choix des clés de cryptage - décryptage

// adapter ces deux nombres puis choisissez e ci-dessous
// pour déterminer vos clés – publique et secrète
// deux grands nombres quelconques d'environ 25 à 30 chiffres
pp := 100000001231231321544566456:
qq := 23456789547687543546876545654:
nom := "Tartempion2": // mettez votre nom !!
//
// =========================================================
p := nextprime(pp):
// calcule le premier nombre premier après p
q := nextprime(qq):
n := p*q:
phi_n := (p-1)*(q-1):
// affiche les paramètres d'encryptage
hold(p)=p, hold(q)=q;
hold(n)=n;
hold(phi_n) = phi_n;
hold(phi_n) = factor(p-1)*factor(q-1);
// =========================================================
// on doit choisir un nombre premier avec phi_n = Φ(n)
// comme code d'encryptage e – la procédure ci-dessous
// cette procédure calcule le plus petit nombre premier possible
// =========================================================
e := 5:
e2 := 2:
while gcd(e2, phi_n) > 1 do
 e2 := nextprime(e2+1);
end_while:
e := e2;
// =========================================================
// calculer le code de décryptage d = inverse de e mod phi_n
// =========================================================
d := powermod(e, -1, phi_n):
// inverse de e modulo phi_n
print(Typeset, hold(e)=e,hold(d)=d);
// Afficher mon code privé
print(NoNL, "\n=============================="):
print(NoNL, "\nClé privée : \n n = " . n . " ;\n");
print(NoNL, " d = " . d . " ; \nAuteur : " . nom);
// Annoncer son code public (texte à envoyer)
print(NoNL, "\n=============================="):
print(NoNL, "\nVoici ma clé publique : \n n = " . n . " ;\n");
print(NoNL, " e = " . e . " ; \nAuteur : " . nom);
print(NoNL, "\n==============================");

Fonctions de cryptage / décryptage (d'une liste de grands nombres)

cryptage := (liste,n,e)->[powermod(x,e,n) $ x in liste];

Procédures globale pour envoyer un message crypté / décrypter un message reçu

Procédure pour envoi d'un message crypté

qui rassemble en une les procédures ci-dessus

envoicrypte := proc(texte,n,e,destinataire)
 local nombres, blocs, blocscryptes, i, ll;
begin
 nombres := texte2nombres(texte): // obtenir liste de nombres
 taille_blocs := floor(ln(n)/ln(base)): // calculer la taille des blocs
 blocs := nombres2blocs(nombres,taille_blocs): // regrouper par blocs
 grandsnombres := blocs2nombres(blocs,base): // convertir en grands nombres
 blocscryptes := cryptage(grandsnombres,n,e): // encrypter
 ll := nops(blocs):
 i := 1:
// Afficher mon code privé
print(NoNL, "\n=============================="):
print(NoNL, "\nClé privée : \n n = " . n . " ;\n");
print(NoNL, " d = " . d . " ; \nAuteur : " . nom);
 print(NoNL, "\n=====================\nMon message crypté :\n"):
 print(NoNL, " à : " . destinataire . " \n n = " . n . "\n e = " . e):
 print(NoNL, "\n taille des blocs : " . taille_blocs ):
 print(NoNL, "\n message chiffré : \n["):
 for x in blocscryptes do
  print(NoNL, "\n " . x);
  if i < ll then
   print(NoNL, ","):
  end_if:
  i := i+1:
 end_for;
 print(NoNL, "\n]\n=====================\n"):
 blocscryptes:
end_proc;

Procédure pour décrypter un message crypté reçu

decrypter := proc(blocscryptes,n,d)
 local nombres, blocsdecryptes, blocs, taille_blocs;
begin
 blocsdecryptes := cryptage(blocscryptes,n,d); // décryptage des grands nombres
 taille_blocs := floor(ln(n)/ln(base)): // calcul de la taille des blocs
 nombres := grandsnombres2nombres(blocsdecryptes,base,taille_blocs);
// reconstituer la liste de nombres
 textedecrypte := numlib::fromAscii(nombres); // reconstituer le texte en clair
end_proc:

Un exemple pour tester

Paramètres

p := 100000001231231321544566477;
q := 23456789547687543546876545669;
n := 2345678983649488348679762549080463834066343577896938113;
e := 3;
d := 1563785989099658899119841683682449523431712472983883979;
message := "Le RSA est genial, mais il serait impossible de faire les calculs sans ordinateurs !!!";
messagecrypte := envoicrypte(message,n,e,"Tartempion");
messagedecrypte := decrypter(messagecrypte,n,d);
print(NoNL, hold(messagedecrypte) = messagedecrypte . "\n"):