RSA – code Mupad pour exercice semi-manuel

Notes sur les fonctions internes de Mupad utilisées

Base et clés de cryptage/décryptage

b := 95:
pp := 5000:
qq := 2000:
nom := "Tartempion2": // mettez votre nom !!
// =========================================================
p := nextprime(pp):
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(n) = factor(n);
print("Mupad a factorisé " . n . "sans difficulté!"):
hold(phi_n) = phi_n;
phi_n = factor(phi_n);
print(Typeset, "Choisir maintenant pour e un nombre premier avec " . phi_n);

Choisir pour e un nombre premier avec phi_n

e := 3:
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==============================\n");
hold(_mod)(hold(_mult)(e, d),phi_n) = (e * d) mod phi_n;

Cryptage / décryptage d'un grand nombre

M0 := 123456;
M1 := powermod(m0,e,n); // crypter le message avec e
M2 := powermod(m1,d,n); // décrypter le message crypté avec d

Message transformé en liste de petits nombres

message := "Sevelin 44";
nombres := numlib::toAscii(message);
// décaler la numérotation de 32
nombres := map(nombres, x->x-32);

Regrouper par blocs de 3 nombres

(copier le résultat précédent et mettre les crochets manuellement)

blocs := [[51, 69, 86] , [69, 76, 73], [78, 0, 20], [20, 63, 63]];

Calculer les grands nombres

grandsnombres := [51*b^2 + 69*b + 86 , 69*b^2 + 76*b + 73, 78*b^2 + 0*b + 20, 20*b^2 + 63*b + 63];

Encoder / décoder les grands nombres

Essai sur le premier de ces nombres

nombretest := 466916;
powermod(nombretest,e,n):
print(%):

Ce nombre est plus grand que 95³ : il devra être décomposé en un bloc de 4 nombres

Vérification : décoder ce grand nombre résultat pour retrouver le grand nombre initial

powermod(1507266, d, n);

Encoder cette liste de 4 grands nombres

grandsnombrescryptes := [powermod(x, e, n) $ x in grandsnombres];

Pour décomposer ces grands nombres en base b = 95,
créons une procédure qui renvoie en une fois le quotient et le reste de la division par 95,
ce qui nous facilitera les calculs

qr := x->[x div b, x mod b];
// donne comme résultat la liste [quotient, reste]

Calculs successifs pour décomposition en base b=95

// [1507266, 4289549, 4975755, 166204]
qr(1507266);

........................

qr(15865);

...........................

qr(167);

............................

qr(1);

Vérification : recomposer le grand nombre

1*b^3+72*b^2+0*b+91;

On peut maintenant automatiser un peu
en reprenant à chaque fois le quotient
(premier nombre de la liste de deux nombres x[1])
et en n'affichant que le reste (le segond nombre x[2])

Premier nombre

x := 1507266:
x := qr(x): print(x[2]):
x := qr(x[1]): print(x[2]):
x := qr(x[1]): print(x[2]):
x := qr(x[1]): print(x[2]):

Quatrième

x := 4289549:
x := qr(x): print(x[2]):
x := qr(x[1]): print(x[2]):
x := qr(x[1]): print(x[2]):
x := qr(x[1]): print(x[2]):

Troisième...

x := 4975755:
x := qr(x): print(x[2]):
x := qr(x[1]): print(x[2]):
x := qr(x[1]): print(x[2]):
x := qr(x[1]): print(x[2]):

Quatrième

x := 166204:
x := qr(x): print(x[2]):
x := qr(x[1]): print(x[2]):
x := qr(x[1]): print(x[2]):
x := qr(x[1]): print(x[2]):

Voici maintenant la liste de petits nombres correspondant au message crypté

nombrescryptes := [1, 72, 0, 91, 5, 0,28,14, 5, 76,31, 35, 0, 18, 39, 49];

Transformer ces nombres en message

// décaler de 32
nombrescryptesdecales := map(nombrescryptes,x->x+32);
// convertir la liste de nombres en texte
messagecrypte := numlib::fromAscii(nombrescryptesdecales);
print(%);

Note : copier le message formaté ci-dessus vers un traitement de texte fait apparaître l'espace qui peut apparaître au début et «échappe» la barre oblique inversée (antistlash) en la doublant ou les guillemets