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
Cryptographie avec maple
17 messages
- Page 1 sur 1
par gol_di_grosso » 23 Mar 2008, 00:35
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
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
par gol_di_grosso » 23 Mar 2008, 13:00
par Anonyme » 24 Mar 2008, 18:41
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
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
par Anonyme » 04 Avr 2008, 21:15
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
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
par gol_di_grosso » 05 Avr 2008, 11:16
re
Quand tu écris PHI:=(P-1)(Q-1);, met plutôt PHI:=(P-1)*(Q-1); (avec le *)
et sinon quand à cet endroit :
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
Quand tu écris PHI:=(P-1)(Q-1);, met plutôt PHI:=(P-1)*(Q-1); (avec le *)
et sinon quand à cet endroit :
**~~vaness~~** a écrit:> 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
par gol_di_grosso » 05 Avr 2008, 11:50
**~~vaness~~** a écrit:merci je vais essayer
D1:=D1 mod PHI je le rajoute avant la fonction igdcdex c'est ça ?
non, juste après
par gol_di_grosso » 05 Avr 2008, 11:53
**~~vaness~~** a écrit: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
par Anonyme » 05 Avr 2008, 11:59
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
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
par gol_di_grosso » 05 Avr 2008, 12:01
**~~vaness~~** a écrit: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
par Anonyme » 05 Avr 2008, 12:30
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
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
par gol_di_grosso » 05 Avr 2008, 12:47
**~~vaness~~** a écrit: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 ?
par gol_di_grosso » 05 Avr 2008, 13:59
**~~vaness~~** a écrit: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.
17 messages
- Page 1 sur 1
Qui est en ligne
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 11 invités
Tu pars déja ?
Fais toi aider gratuitement sur Maths-forum !
Créé un compte en 1 minute et pose ta question dans le forum ;-)
Identification
Pas encore inscrit ?
Ou identifiez-vous :