Arithmétique

Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
Madlord
Membre Naturel
Messages: 35
Enregistré le: 06 Oct 2008, 12:32

Arithmétique

par Madlord » 17 Déc 2013, 17:41

Bonjour,
Mon sujet porte sur le décryptage d'une chaîne cryptée par RSA.
Soit x le message la fonction publique qui code le message est :

Pour décoder le message la fonction est :

Il nous faut donc trouver d.
On connait , e et n. On connait aussi p et q qui sont les seuls facteurs premiers de n différents de 1 et n.
On sait que :

car p et q sont premiers.
De plus le cours dit que :
Si on pose . d existe car e est premier avec .
Alors :

Tout d'abord, je ne comprend pas comment on passe à la dernière partie de l'équation, a moins que mais je ne vois pas pourquoi.
Comment à partir de n et e retrouver d puisqu'il y a l'inconnue qui vient ajouter son grain de sel dans l'histoire ?



L.A.
Membre Irrationnel
Messages: 1709
Enregistré le: 09 Aoû 2008, 16:21

par L.A. » 17 Déc 2013, 18:25

Bonsoir.

Peut-être que ceci peut t'aider...

Si d est une solution de

de = 1 [phi(n)]

alors tout entier dans la classe de d modulo phi(n) est solution de la même équation, et tous ces entiers permettent de décoder le message. Donc la question du choix de lambda n'est pas un problème.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21709
Enregistré le: 11 Nov 2009, 21:53

par Ben314 » 17 Déc 2013, 18:27

Salut,
Toute "l'astuce" du chmilblick, c'est que Z/nZ=Z/(pq)Z est isomorphe en temps qu'anneau à Z/pZ x Z/qZ.
En particulier le groupe multiplicatif (Z/nZ)* des éléments inversibles de Z/nZ contient exactement (p-1)(q-1) éléments ( indicatrice d'euler).
Comme l'ordre d'un élément divise l'ordre du groupe, cela implique que, pour tout x premier avec n, on a et qu'en conséquence, pour n'importe quel entier , on a donc tu n'as absolument pas besoin de connaitre la valeur de pour mener à bien les calculs.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Madlord
Membre Naturel
Messages: 35
Enregistré le: 06 Oct 2008, 12:32

par Madlord » 17 Déc 2013, 19:22

Bonjour,
Tout d'abord merci de vos réponses, j'ai toutefois des questions à poser. Si peut on en déduire que ?

Si oui il faut donc trouver l'élément inversible de e pour trouver la valeur de d, il faut donc poser comment trouver b et a, on peut faire en essayant simplement des valeurs jusqu'à trouver la bonne, le problème est qu'ici de e = 11 mais et n = 1760250096402811749199611608575084934851613507070884458068671022833817662936408929077786843687914521447812500504132975035459244678032179536523212946815460293715097607 (un nombre de 166 chiffres) ça risque d'être long de demander à un ordinateur de trouver un a et b par force brute.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21709
Enregistré le: 11 Nov 2009, 21:53

par Ben314 » 17 Déc 2013, 20:48

Madlord a écrit:Bonjour,
Tout d'abord merci de vos réponses, j'ai toutefois des questions à poser. Si peut on en déduire que ?

Non, ça n'a absolument rien à voir : tu mélange la structure additive de l'anneau Z/nZ et sa structure multiplicative.
Par exemple, si n=15, l'ordre d'un d donné pour la structure additive c'est le plus petit e tel que dxe=d+d+d...+d (e fois)=0 [15] (où 0 est le neutre de l'addition)
L'ordre du même d (s'il est premier avec 15) pour la structure multiplicative c'est le plus petit f tel que d^f=dxdxd...xd (f fois)=1 [15] (où 1 est le neutre de la multiplication)
L'ensemble Z/15Z contient 15 éléments (les classes de 0,1,...15) donc l'ordre additif d'un élément divise toujours 15 (c'est donc 1,3,5 ou 15)
Alors que l'ensemble des éléments inversibles de Z/15Z (qui forme un groupe) ne contient que éléments, à savoir {1,2,4,7,8,11,13,14} donc l'ordre multiplicatif d'un de ces éléments divise toujours 8.
Donc si par exemple tu as pour un certain x inversible modulo 15, tout ce que tu peut en déduire, c'est que est un multiple de l'ordre de x (qui est lui même un diviseur de 8)
Par contre, si tu as pour tout x inversive modulo 15, comme on sait que le groupes des inversibles de Z/nZ est cyclique lorsque n est impair, celà signifie que est un multiple de
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Madlord
Membre Naturel
Messages: 35
Enregistré le: 06 Oct 2008, 12:32

par Madlord » 17 Déc 2013, 21:11

Donc si j'ai bien comprit on a , j'ai bien peur de n'avoir pas saisi le résonement qui pourrait m'amener à la réponse.

Avatar de l’utilisateur
Ben314
Le Ben
Messages: 21709
Enregistré le: 11 Nov 2009, 21:53

par Ben314 » 17 Déc 2013, 21:42

Madlord a écrit:Donc si j'ai bien comprit on a , j'ai bien peur de n'avoir pas saisi le résonement qui pourrait m'amener à la réponse.

Faut dire que j'ai toujours pas bien compris ce que tu connaissait et ce que tu cherchais...
Dans ce genre de bricolage, en général, tout le monde connait n et e et seul celui qui a divulgué le n et le e connait les deux facteurs premiers p1 et p2 tels que n=p1.p2 (et on estime que vu les connaissances actuelles et les vitesses des ordis, il est très peu probable que qui que ce soit trouve p1 et p2 en connaissant n).
Le type qui connait p1 et p2 connait bien sûr (mais personne d'autre) et, pour décoder, il lui suffit d'appliquer l'algo. d’Euclide étendu à et e pour trouver deux entiers c et d tels que (ce qui va trés vite) et le en question lui permet de décoder.
Qui n'entend qu'un son n'entend qu'une sonnerie. Signé : Sonfucius

Madlord
Membre Naturel
Messages: 35
Enregistré le: 06 Oct 2008, 12:32

par Madlord » 17 Déc 2013, 22:08

Ah, il me semblait avoir dit dans mon premier message qu'on connaissait n, pet q tel que , désolé si je n'ai pas été clair. Du coup on connait , donc la il ne me reste plus qu'à exécuter l'algorithme d'Euclide pour trouver k et d dans merci de tes réponses.

 

Retourner vers ✯✎ Supérieur

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 10 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 ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite