[RSA] Besoin d'une info

[invite11095089]

Bonjour à tous,

Je viens de m'inscrire particulièrement pour cette question. J'aimerais avoir une précision sur un point de l'algorithme RSA,plus précisément au décryptage.
La clé privée étant composé du couple (d, n), pour trouver d, j'ai trouvé sur le net, deux moyens :
le plus utilisé e*d % phi(n) = 1 et un autre d = e^-1 % phi(n). J'aimerais avoir plus explications sur ce dernier, comment on le trouve, ect... ?

Merci d'avance, A++
-----

[invite11095089]

UP

Le message est peut-etre à changer de catégorie car il est plus orienté math...

[JPL]

Voila, c'est déplacé.

[invite11095089]

Merci bien.
En espérant qu'il y est plus de réponse ici...

[A voir en vidéo sur Futura]

[invited927d23c]

Bonjour,

La clé privée étant composé du couple (d, n), pour trouver d, j'ai trouvé sur le net, deux moyens :
le plus utilisé e*d % phi(n) = 1 et un autre d = e^-1 % phi(n). J'aimerais avoir plus explications sur ce dernier, comment on le trouve, ect... ?

Pour résoudre e*d % phi(n) = 1 il suffit d'appliquer l'algorithme d'Euclide étendu, à condition de connaître phi(n), ce qui nécessite de connaître sa décomposition en facteurs premier...

e*d % phi(n) = 1 <=> e*d + k*phi(n) = 1

Pour la deuxième je vois malheureusement pas trop, on peut l'écrire comme ça :

e^-1 % phi(n) = d <=> d + k*phi(n) = e^-1

Mais que représente e^-1? d est normalement appelé l'inverse de e modulo phi(n). Donc e^-1 = d? mais ça ne donne pas de sens.

J'espère que quelqu'un d'autre pourra nous éclairer.

[invite11095089]

Merci pour ta réponse Witten, pour le la 1er, j'étais au courant. C'est surtout la 2eme qui m'embete, comme toi apparamment...

Mince, j'ai remarqué une erreur, c'est pas phi(n) mais n.
n= p*q
phi(n) = (p-1) * (q-1)
J'edite mes messages

A++, si quelqu'un peut nous éclairer.

[invite11095089]

Oups non non pour trouver d, on utilise bien phi(n) désolé

[invitea0f3dac8]

J'ai du mal à comprendre ton problème avec les notations que tu utilises (essaye d'apprendre un peu de LaTeX pour clarifier un peu tout ça !).

Je peux sinon avancer quelques idées en supposant :



que ce que tu considère comme la clé privée, c'est le coupe de nombres premiers qui sert à calculer . N qui constitue avec (qui lui doit être premier avec ) la clé publique est donc connue mais il est impossible de remonter à p et q (la sécurité de l'algorithme repose dessus) car ce sont des nombres premiers volontairement choisis très grands. Comme tu dois t'en douter, il n'y a pas de règle mathématique pour calculer un nombre premier, on sait juste à quelles conditions on le considère comme premier. En particulier se sont des ordinateurs qui tournent pendant des milliers d'heures et qui se chargent de vérifier ces conditions avec des algorithmes probabilistes. Actuellement la plus grande factorisation de N l'a été pour un nombre de 200 chiffres.

que tu t'es mal exprimé et que ce que tu considères comme clé privée c'est la clé publique, c'est à dire avec la clé de cryptage qui doit être un nombre premier avec (cf plus haut) et que correspond à l'inverse de dans . Pour ce faire il faut résoudre soit une identité de bezout : que l'on peut résoudre avec l'algorithme d'eucilde étendu ce qui n'est pas possible manuellement pour de grandes valeurs de mais résolvable facilement pour de petites valeurs ( étant pris conventionellement petit). Tout dépend donc de la clé publique .



Pour information, si est très grand et que deux personnes utilise le même mais des et différents mais premiers entre eux et qu'une troisième veut leur envoyer à chacun le même message qui sera crypté en et alors un hacker, s'il réussi a intercepter et peut alors les décrypter et trouver en résolvant l'identité de Bezout : . On aura alors soit soit .

D'après mes cours à l'INSA de Lyon.

Tchao.

[invite11095089]

Salut Slasher2610 et merci pour ta réponse.

Aparamment on utilise pas les même lettres pour définir les clés.

que ce que tu considère comme la clé privée, c'est le coupe de nombres premiers

Pour moi la clé privée : (d, n)
n = p*q
phi(n) = (p-1)*(q-1)
e*d % phi(n) = 1

Mais, on peut trouver p et q, par la factorisation de n non ?

que tu t'es mal exprimé et que ce que tu considères comme clé privée c'est la clé publique, c'est à dire (e, N)

Mh, je considère bien la clé publique comme (e, n)
e et phi(n) premiers entre eux
phi(n) = (p-1)*(q-1)

A part les problèmes de lettre je pense que j'ai pas dit d'autres bétise ^^ ....

Mais ce que je veux ca voir, c'est ceci : d = e^-1 % phi(n)
d = 1/e % (p-1) * (q-1)
D'où ca sort ?

Merci encore.
A++

[invite6b1e2c2e]

Salut,

A priori,
e*d=1 %phi(n) est équivalent à dire d = e^{-1} %phi(n).
C'est juste dire qu'il y a unicité de l'inverse -quand elle existe- dans .

__
rvz

[invite11095089]

Mh ok ok merci beacoup !!!