cryptographie avec maple

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: **~~vaness~~**

coucou à tous alors je suis en L3 Math-Info et j'ai vraiment besoin de votre aide .. je suis un module de Cryptographie, module 50% math et 50% informatique .. et j'ai un devoir à faire sur Maple pour mercredi .. problème je connais pas du tout Maple !
donc deja j'aimerais savoir si vous connaissez un lien ou je pourrais télécharger ce logiciel gratuitement de préférence (version 9.5 aussi de préférence c'est celle qu'il y a à la fac)
et ensuite j'ai deux petits exos, deux programmes à faire sur la théorie des nombres premiers

EXO 1 : à l'aide de Rand et Random, fabriquer un générateur aléatoire de grands nombres premiers, pusi un générateur aléatoire d'entiers premiers avec un entier donné

EXO 2 : Etant donné un nombre e (grand en pratique) premier avec un nombre n (trés grand en pratique), calculer son inverse d modulo n

j'imagine que pour quelqu'un qui connait un peu le logiciel, ça doit être assez rapide donc si quelqu'un pouvait m'aider ..

merci à vous


Posted by: gol_di_grosso

Je ne pense pas que tu puisse télécharger maple gratuitement vu qu'il est payant.
Tu peux utiliser xcas qui resemble un peu et qui est gratuit
pour l'exo 1 va voir l'aide et regarde comment fonctionne random il doit y avoir un min et un max à donner en argument
pour le 2 si tu veux un grand nombre premier tu peux utiliser nextprime qui donne le nombre premier suivant celui que tu donne en argument.
pour trouver l'inverse modulo n il doit y a voir la fonction avec bezout genre iabcuv


Posted by: **~~vaness~~**

merci pour la réponse .. pour Maple on peut même pas télécharger une démo ? j'en ai besoin juste pour ce dm je pense pas que j'en servirai aprés


Posted by: gol_di_grosso

Citation:
Posté par **~~vaness~~**
merci pour la réponse .. pour Maple on peut même pas télécharger une démo ? j'en ai besoin juste pour ce dm je pense pas que j'en servirai aprés

apparament y a ça
(v7.5) mais ça me parait bizarre...
sinon pour ce que tu as à faire, xcas fera la même chose que maple


Posted by: **~~vaness~~**

j'ai réussi à me procurer maple 9.5 par une copine donc j'ai essayé de voir comment ça marchait à peu prés, j'ai lu quelques trucs
donc pour faire un générateur de grands nombres premiers j'ai trouvé cette formule qui marche bien
t := 100:
p := nextprime(rand(10^(t-1)..10^t)()); q := nextprime(rand(10^(t-1)..10^t)());

ça donne des entiers premiers à 100 chiffres

le problème maintenant c'est comment faire la même chose mais en produisant des entiers premiers avec un nombre n fixé au départ ? je vois pas vraiment


Posted by: **~~vaness~~**

recoucou ! je vais encore vous embêter avec mon truc mais je dois rendre mon TP lundi et j'ai finis par comprendre pas mal de truc, j'ai trouvé quelques algo et tutos trés utiles mais j'ai un soucis dans le tout dernier exo (je mettrai mon code à la fin)

alors en gros il faut décrire un protocole concret d'échanges RSA entre Alice et Bob
alors Alice veut transmettre un message M à Bod, pour cela elle le transforme en chiffre (c'est ce que fait ma procédure "texteàchiffre")
Bob choisit au hasard deux entiers premiers p et q (ma procédure gene_prem me fait ceci) puis on calcule n=pq et phi=(p-1)(q-1)
ensuite Bob choisit un entier premier avec phi au hasard (fonction gene_prem2)
on calcule à l'aide de igcdex l'inverse de e modulo phi que j'ai apelé d1
puis on crypte le message d'Alice en faisant C=M^e mod n
(j'ai utilisé un algo d'exponentiation rapide que j'ai trouvé dans un tuto parce que ça donne un chiffre trop gros pour Maple)
et normalement Bod peut décrypter le message en faisant C^d1 mod n (j'ai appelé le résultat de cette opération m) .. et normalement m doit être égal au message initial d'Alice M .. mon problème est la, ce n'est pas le cas !
j'ai testé toutes mes fonctions independemment les unes des autres, ça marche, je vois vraiment pas où est le soucis

donc je vous mets mon code


> restart:
> Alphabet:=abcdefghijklmnopqrstuvwxyz:
> nb_lettres:=length(Alphabet):
> for var to nb_lettres do
> lettre[var]:=substring(Alphabet,var..var):
> od:
> lettre[0]:=` `:
> for var from 0 to nb_lettres do
> num_lettre[lettre[var]]:=var:
> od:

> texteachiffre := proc(expression)
> local var,resul,element:
> global nb_lettres:
> resul := 0:
> for var to length(expression) do
> element:=num_lettre[substring(expression,var..var)]:
> resul := resul+element*(nb_lettres+1)^var:
> od:
> end:
> M:=texteachiffre(`bonjour bob`);

> gene_Prem := proc()
> local test::integer:
> test := rand(10^6..10^7)();
> if(isprime(test))
> then
> return test
> else
> return(nextprime(test))
> fi:
> end:
>
> P:=gene_Prem();
> Q:=gene_Prem();
>
> N:=P*Q;
> PHI:=(P-1)(Q-1);

> gene_Prem2 := proc(n::integer)
> local tmp::integer,test::boolean:
> test := false:
> while (test=false) do
> tmp:=rand(10^6..10^7)():
> test := is(igcd(tmp,n)=1):
> od:
> return tmp:
> end:
>
> E:=gene_Prem2(PHI);
> igcd(E,PHI);
>
> igcdex(E,PHI,'D1','V');
> D1;

> #C:= M^E mod N;
>
> 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:
> od:
> resul:
> end:

> C:=expomodulo(M,E,N);

> m:=expomodulo(C,D1,N);

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

merci pour votre aide, ça doit être une erreur débile mais à force d'avoir le nez dedans j'y vois plus rien lol


Posted by: gol_di_grosso

re
Quand tu écris PHI:=(P-1)(Q-1);, met plutôt PHI:=(P-1)*(Q-1); (avec le *)
et sinon quand à cet endroit :
Citation:
Posté par **~~vaness~~**
> igcdex(E,PHI,'D1','V');
> D1;

Il faut prendre D1 entre 0 et PHI-1 ce qui n'est pas le cas avec igcdex()
donc ajoute la ligne D1:=D1 mod PHI;
après c'est possible que ça marche


Posted by: **~~vaness~~**

merci je vais essayer
D1:=D1 mod PHI je le rajoute avant la fonction igdcdex c'est ça ?


Posted by: gol_di_grosso

Citation:
Posté par **~~vaness~~**
merci je vais essayer
D1:=D1 mod PHI je le rajoute avant la fonction igdcdex c'est ça ?

non juste après, il faut que le D1 trouvé par igcdex soit compris entre 0 et PHI-1, sinon ça ne marche pas


Posted by: **~~vaness~~**

d'accord
je viens de le faire et non ça vient pas de la apparemment
D1:=D1 mod PHI m'affiche la même chose que D1 tout court enfin avec les deux exemples que j'ai essayé

j'ai un nombre m assez proche du M du début (même nombre de chiffres) et quand je convertis en texte, ça me donne des lettres décalées de deux ou trois rangs par rapport au message du début ... c'est bizarre


Posted by: gol_di_grosso

Citation:
Posté par **~~vaness~~**
d'accord
je viens de le faire et non ça vient pas de la apparemment
D1:=D1 mod PHI m'affiche la même chose que D1 tout court enfin avec les deux exemples que j'ai essayé

j'ai un nombre m assez proche du M du début (même nombre de chiffres) et quand je convertis en texte, ça me donne des lettres décalées de deux ou trois rangs par rapport au message du début ... c'est bizarre

essaie en mettant un message court genre 3 lettres car avec ce que tu as fait j'ai l'impression que le message doit-être plus petit que P ou Q


Posted by: **~~vaness~~**

ah mais j'ai pas fait gaffe dans mon énoncé que M doit être inférieur à N=P*Q .. c'est pas le cas dans mon exemple


Posted by: **~~vaness~~**

ouééé ça marche ! lol et ben voila c'est ce que je disais une erreur débile .. m'enfin
par contre je me suis arrangée dans ma procédure qui génère des entiers premiers pour que leur produit soit plus grand que M .. mais bon c'est du bricolage un peu, si on change le message en un message plus long, ça marchera plus .. mais bon c'est pas un gros soucis


Posted by: gol_di_grosso

Citation:
Posté par **~~vaness~~**
ouééé ça marche ! lol et ben voila c'est ce que je disais une erreur débile .. m'enfin
par contre je me suis arrangée dans ma procédure qui génère des entiers premiers pour que leur produit soit plus grand que M .. mais bon c'est du bricolage un peu, si on change le message en un message plus long, ça marchera plus .. mais bon c'est pas un gros soucis

oui, pour éviter ce problème il faudrait découper le message en groupe de 4 lettres (par exemple).
PS : ça marche quand même si tu fais pas D1:=D1 mod PHI ?


Posted by: **~~vaness~~**

ben j'ai essayé avec deux exemples et ça marche même si on met pas D1=DI mod PHI mais bon je le laisse quand même on sait jamais
je pense que je vais laisser comme ça, merci beaucoup de ton aide!


Posted by: gol_di_grosso

Citation:
Posté par **~~vaness~~**
ben j'ai essayé avec deux exemples et ça marche même si on met pas D1=DI mod PHI mais bon je le laisse quand même on sait jamais
je pense que je vais laisser comme ça, merci beaucoup de ton aide!

ok, de rien.










-