Cryptage RSA - modulo

par **sink64** » 31 Mai 2014, 15:32

Bonjour à tous,
Je me trouve cette année confronté à réaliser un projet pour le cadre de mes études. Mon groupe et moi avons décidé de partir sur le cryptage de messages à partir du code RSA.
Etant doué en maths c'est moi le moteur du groupe mais me voilà en difficulté pour l'apprentissage de ce code.

Je vais vous expliquer rapidement en quoi ça consiste pour vous mettre dans le truc:
trouver 2 nbes premiers p et q
n = p*q
déterminer e en sorte qu'il n'ait pas de diviseurs en commun avec (p-1)*(q-1)
clé publique (e, n)

choisir d tel que e*d mod (p-1)*(q-1)=1 et ça là où je me tape la tête contre les murs :mur:
si je prend 5210783*d mod 5210784=1
comment faire en sorte de déterminer d?

Hésitez pas à m'aider ça me permettrait d'avancer.
Merci pour vôtre temps!

par **jlb** » 31 Mai 2014, 15:37

Salut, tu cherches un couple (u,v) de Bézout pour e et (p-1)(q-1), du coup ue + v(p-1)(q-1) = 1 et modulo (p-1)(q-1) cela te donne ton résultat.

par **sink64** » 31 Mai 2014, 15:49

Donc si je me souviens le théorème de Bézout est de la forme A.u + B.v = PGCD(A,B)
Si je reprend mon exemple de 5210783*d mod 5210784=1 nous prendrions A=5210783 et B=5210784. Ce qui donnerait u=-1 et v=1
Ainsi je pourrais conclure que mon d = u = -1?

par **zygomatique** » 31 Mai 2014, 19:42

salut

peut-être oui ... sauf que d est compris entre 1 et (p- 1)(q - 1) = m

par **sink64** » 31 Mai 2014, 20:04

Salut à toi

Je suis d'accord parce qu'en effet ce -1 me paraissait bien curieux mais d'un autre côté d'après Bézout il ne peut y avoir d'autre couple u, v tel que v soit égale à 1. Et si je décide de changer ce 1 je ne suis plus la méthode de cryptage...

par **jlb** » 31 Mai 2014, 21:06

sink64 a écrit:Salut à toi

Je suis d'accord parce qu'en effet ce -1 me paraissait bien curieux mais d'un autre côté d'après Bézout il ne peut y avoir d'autre couple u, v tel que v soit égale à 1. Et si je décide de changer ce 1 je ne suis plus la méthode de cryptage...

tu travailles modulo quelque chose!! d= -1 +(p-1)(q-1) doit convenir non?

par **sink64** » 01 Juin 2014, 02:39

J'ai pas trop compris la remarque à vôtre réponse...

par **zygomatique** » 01 Juin 2014, 11:24

lorsque l'on a :: ue + vm = 1 alors on

(u - km)e + (v + ke)m = 1 pour tout entier relatif k

il est alors aisé de trouver un k tel que 1 =< v + ke < m = (p - 1)(q - 1)

...

par **sink64** » 01 Juin 2014, 15:35

ouai.... :/
Impossible à résooudre cela avec 3 inconnus

par **sylvainc2** » 01 Juin 2014, 17:07

Il y a un probleme avec tes choix de nombres, tu as pris n=5210784 mais il a 10 facteurs premiers au lieu de 2: tu dois prendre n=pq avec p et q premiers, pour pouvoir calculer ensuite d dans ed=1 mod (p-1)(q-1). Essaye avec d'autres nombres.
PS: habituellement on choisit e=65537 et on vérifie s'il est premier avec (p-1)(q-1).

par **sink64** » 01 Juin 2014, 17:16

Pour que n soit = à 5210784 c'est parce que j'ai pris p=1999 et q=2609 tous les deux premiers. e j'ai décidé de prendre 5210783 car c'est n-1 donc je suis certain qu'ils n'ont pas de facteurs en commun. Ma question c'est comment calculer d à partir d'une méthode clair et rapide à partir de mon exemple. Sachant que c'est simplement un exemple pour que je puisse faire un algorithme pour généraliser avec tous les autres possibilités.

par **sylvainc2** » 01 Juin 2014, 17:36

Oui c'est vrai, 1999*2609=5215391 bon d'accord on prend ce n, donc phi(n)=(p-1)(q-1)=5210784. Remarque que ce nombre n'est pas n c'est phi(n), où phi() est la fonction indicatrice d'Euler. Ensuite on prend e=5210783 si tu veux, qui est premier avec (p-1)(q-1) .

Pour trouver d dans ed=1 mod phi(n) on résoud 5210783d + 5210784v = 1 avec l'algorithme d'Euclide étendu. Tu peux trouver sur le web le détail (sinon regarde mon message sur http://forums.futura-sciences.com/mathematiques-college-lycee/406340-algorithme-deuclide-etendu-ts-spe-math.html)

Si le d calculé ainsi est négatif tu prends d=d+5210784 pour avoir un d positif.

par **sink64** » 01 Juin 2014, 17:49

Oui je faisais allusion à phi() et non à n, "mea culpa".

J'ai tout suivi et en réalisant le calcul je retombe sur d=-1. Et si jexécute ce que vous dites j'en conclus que d=-1+5210784=5210783=e ce qui pourrais venir à dire que e² mod (p-1)(q-1)=1?

par **sylvainc2** » 01 Juin 2014, 18:07

Oui c'est ca. Mathématiquement, ca marche, c'est valide, sauf qu'en pratique c'est une très mauvaise idée d'avoir d=e car la valeur e est connue du public, mais d est la clé secrète. Or si on a d=e (ce qui est le cas ici par un pur hasard) alors automatiquement la clé secrète est cassée. Donc en pratique il faudrait prendre d'autres valeurs pour p et q et e.

Edit: en fait ce n'est pas un hasard. Si on prend e=phi(n)-1 alors on a toujours d=phi(n)-1 comme solution de ed=1 mod phi(n) car ca devient (phi(n)-1)^2 = phi(n)^2-2phi(n)+1 = 1 mod phi(n) ce qui est toujours vrai évidemment. Donc morale de l'histoire: ne jamais choisir e=phi(n)-1...

par **zygomatique** » 01 Juin 2014, 19:13

ouais un choix peu judicieux ...

j'ai fait un TP avec mes TS sur XCAS la dessus

on peut demander à Xcas le premier nombre premier après n pour toute valeur de n

ainsi si tu le demande le premier nombre premier suivant 123456 tu es sur qu'il n'aura pas de diviseur commun avec (p - 1)(q - 1)

...

et évidemment on trouve un d négatif mais il est aisé de se ramener à un d positif compris entre 1 et (p - 1)(q - 1)

...

Cryptage RSA - modulo

Cryptage RSA - modulo

Qui est en ligne