Chapitre 4 : Cryptage à clef publique 

2. Cryptage RSA 

La méthode RSA est due à Rivest, Shamir et Adleman (1977). Chaque personne garde secrets deux grands nombres premiers et ,  ici congrus à 2 modulo 3, et la clef publique est le produit de ces deux nombres :  ..La méthode repose sur le fait qu'il est facile de tester la primalité d'un nombre mais très difficile de le décomposer en facteurs premiers. Ici, pour des raisons de rapidité, on ne prendra que des nombres pas trop grands. La commande ifactor décompose les nombres en facteurs premiers. Avec l'option easy, l'opération s'arrête dès qu'on a deux facteurs. La décomposition complète prend plus de temps : 

>	restart: n:=8012940887713968000041:

 

>	depart:=time(): ifactor(n,easy); temps_du_calcul:=time()-depart;

 

 

 

>	depart:=time(): ifactor(n);      temps_du_calcul:=time()-depart;

 

 

 

3. Transformation d'une suite de caractères en un nombre 

On commence par numériser l'alphabet : 

>	restart:Alphabet:=abcdefghijklmnopqrstuvwxyz;

 

 

>	nb_lettres:=length(Alphabet);

 

 

>	for ni to nb_lettres do lettre[ni]:=substring(Alphabet,ni..ni);od:

 

>	lettre[0]:=` `:

 

>	for ni from 0 to nb_lettres do image_lettre[lettre[ni]]:=ni;od:

 

On transforme  les textes comme si les nombres qui représentent les lettres étaient écrits en base 27, le nombre de lettres plus une unité. Ainsi dans le texte moi, la lettre m étant le 13ème caractère, la lettre o étant le 15ème caractère, et la lettre i étant le 9ème caractère,  moi est traduit en   13*27+ 15*27^2 + 9*27^3 = 188433, autrement dit image_lettre[m]*27 + image_lettre[o]*27^2 + image_lettre[i]*27^3}   = 188433. La procédure transforme  effectue cette opération : 

 

>	13*27+15*27^2+9*27^3;

 

 

>	transforme := proc(expression)  local ni,resul,element;global nb_lettres; resul := 0;  for ni to length(expression) do  element:=image_lettre[substring(expression,ni..ni)]; resul := resul+element*(nb_lettres+1)^ni; od; end;

 

 

La procédure detransforme est l'opération inverse : 

>	detransforme := proc(nb)    local ni,liste,s;global nb_lettres;  liste := convert(nb,base,nb_lettres+1);    s:=seq(lettre[ni],ni = liste);     cat(s);   end;

 

 

Application : 

>	mm:=transforme(`exportation ou utilisation de moyens ou de prestations cryptologiques`);

 

 

>	detransforme(mm);

 

 

4. Codage 

Tout d'abord, il vous faut deux nombres premiers congrus à 2 modulo 3 ; la commande  ithprime(n) retourne le n-ième nombre premier ; vous vérifierez que ithprime(30001)} et ithprime(30002)} sont tous deux convenables et on en fait le produit pour obtenir un nombre appelé : 

>	p[alpha]:=ithprime(30001);q[alpha]:=ithprime(30002); p[alpha] mod 3, q[alpha] mod 3;n[alpha]:=p[alpha]*q[alpha];

 

 

 

 

 

Le codage consiste alors à élever mm au cube modulo : 

>	liste_a_coder := convert(mm,base,n[alpha]);

 

 

>	code[alpha] := nombre -> nombre^3 mod n[alpha];

 

 

>	liste_a_decoder := map(code[alpha],liste_a_coder);

 

 

5. Décodage 

Le décodage consiste à élever mm^3 à la puissance modulo   : 

 

>	k[alpha] := (2*(p[alpha]-1)*(q[alpha]-1) + 1)/3;

 

 

>	55^k[alpha];

 

Error, numeric exception: overflow 

Maple refuse d'élever à une telle puissance ! On peut par contre utiliser la méthode d'exponentiation rapide exposée dans le chapitre précédent : 

>	expomodulo:=proc(xx,nn,mm) local x,n,resul; x:=xx mod mm; resul:=1; n:=nn; while n>0 do   if type(n,odd) then resul:=resul*x mod mm; n:=n-1;     else x:=x*x mod mm; n:=n/2 fi; end do;resul;end;

 

 

>	decode[alpha] :=nombre->expomodulo(nombre,k[alpha],n[alpha]);

 

 

>	liste_decode[alpha] :=map(decode[alpha],liste_a_decoder);

 

 

>	Retour:=proc(liste_decode,n_code) local retour,nb_de_termes,i,x; retour:=0:x:=1; nb_de_termes := nops(liste_decode); for i to nb_de_termes do   retour := retour + liste_decode[i]*x;   x:=x*n_code; od: retour; end;

 

 

>	retour:=Retour(liste_decode[alpha],n[alpha]);

 

 

>	detransforme(retour);

 

 

6. Envoi d'un message de α vers ß 

L'émetteur α du message mm vers le destinataire ß chiffrera le message en effectuant .  

 

>	p[beta]:=ithprime(30003);q[beta]:=ithprime(30004); p[beta] mod 3, q[beta] mod 3;n[beta]:=p[beta]*q[beta]; k[beta] := (2*(p[beta]-1)*(q[beta]-1) + 1)/3;

 

 

 

 

 

 

>	code[beta] := nombre -> nombre^3 mod n[beta]; decode[beta] :=nombre->expomodulo(nombre,k[beta],n[beta]);

 

 

 

>	mmp:=map(code[beta],map(decode[alpha],liste_a_coder));

 

 

7. Réception d'un message de α par ß 

Le destinataire ß décryptera le message venant de α en effectuant : 

 

>	mmp1:=map(code[alpha],map(decode[beta],mmp));

 

 

>	retour:=Retour(mmp1,n[alpha]);

 

 

>	detransforme(retour);

 

 

8. Interception d'un message de α par γ 

Si une troisième personne intercepte le message, il doit être incapable (ne connaissant pas  et mais seulement ) de décrypter ce message : 

>	p[gamma]:=ithprime(30008);q[gamma]:=ithprime(30009); p[gamma] mod 3, q[gamma] mod 3;n[gamma]:=p[gamma]*q[gamma]; k[gamma] := (2*(p[gamma]-1)*(q[gamma]-1) + 1)/3;

 

 

 

 

 

 

>	code[gamma] := nombre -> nombre^3 mod n[gamma]; decode[gamma] :=nombre->expomodulo(nombre,k[gamma],n[gamma]);

 

 

 

>	mmp1:=map(code[alpha],map(decode[gamma],mmp));

 

 

>	retour:=Retour(mmp1,n[alpha]);detransforme(retour);

 

 

 

On ne trouve qu'un vrai charabia !