Quelques questions sur rsa

Salut a tous !

Je me suis interesse a l'algorithme de cryptage rsa il y a quelque temps mais j'avoue avoir encore du mal avec certains points.... Si jamais une personne (ou plusieurs.. :p) pouvaient m'apporter leurs lumieres, sa serait super sympa !!

1] J'ai realise un code qui genere des nombres premiers indispensables pour la bonne marche de RSA. Malheureusement, je sius limite par le type de mes donnes (j'utilise un unsigned long int). Je sais que certains parlent de pres de 100 chiffres pour leurs nombres premiers, j'aimerai savoir comment realiser ce genre de prouesse ??

2] La securite de l'algorithme se base sur la longueur des cles de cryptage...  dont la longueur est exprime en bits. Comment representer concraitement cette valeur ?? Parce que dans ma logique, un entier (int) sous windows fait 32 bits (ou 16 je sais plus...) ce qui donne un nombre compris entre -30000 et des poussieres a plus +30000 et quelques... je n'arrive pas a imaginer comment faire pour arriver a atteindre plus...

3] J'ai lu un topic sur la facon de mettre en place la formule. Apres avoir calcule n suivant p et q, choisi un e qui n'a aucun facteur commun avec (p-1)(q-1), ensuite il faut trouver d qui se calcule comme cela :

(e * d) % ((p-1)(q-1)) = 1

et la j'avoue que je seche ... pas moyen de trouver d...

Je remercie d'avance tous ceux (et celles :p) qui pourront me conseiller ou m'orienter vers la bonne marche a suivre...

En vous remerciant

@++ et bon coding !

"Avant même de fonctionner, tout programme est déjà obsolète."

Cette source devrait répondre a tes interrogations: http://www.cppfrance.com/codes/PROGRAMME-CRYPTAGE-RSA_30454.aspx Elle utilise gmp pour gérer les grand entiers. Pour le calcul de d, il se fait grace à l'algorithme de Bezout

Bon je ne connait pas ton niveau en math mais j'espère que tu as quelques connaissances sur les anneaux commutatifs unitaire Z_n.

Donc le probleme est qu'il faut trouver d sachant que:
(e*d) % ((p-1)(q-1)) = 1

Ce qui peut se traduire dans l'anneau Z_m (où je pose m = (p-1)(q-1)):
e*d = 1

C'est à dire que d est l'inverse de e dans Z_m, on sait d'ailleur que cet inverse existe forcement car e est premier avec m. Il faut donc calculer l'inverse de e. C'est la que, si mes souvenirs sont bons, que l'on peut utiliser l'algorithme d'Euclide et le théorème de Bezout:

e*d est congru à 1 modulo m. Il existe donc k appartenant à l'ensemble des entiers relatifs tel que:

e*d = (-k)*m + 1

Précisons ici que on ne travaille plus dans Z_m mais dans Z
Ce qui se transforme de la manière suivante:

e*d + k*m = 1 (le moins au dessus c'est pour que ce soit plus clair ici)

But du jeu: trouver les valeurs de d et k (mais surtout d !). Là c'est l'algorithme d'euclide, je vais te montrer comment proceder pour un cas simple car c'est chiant à expliquer:

si on prend p=5 et q=7, alors m = (p-1)(q-1) = 30.
je vais prendre pour valeur de e 11 car 11 est premier avec 30. On a donc:

11*d + k*30 = 1

On applique la division euclidienne plusieurs fois:
30 = 11 * 2 + 8
11 = 8 * 1 + 3
8 = 3 * 2 + 2
3 = 2 * 1 + 1

Une fois que tu tombe sur 1 pour le reste tu remonte les résultats par les restes successifs:
1 = 3 - 2 * 1
1 = 3 - (8 - 3*2)
1 = 3*3 - 8
1 = 3*(11-8*1) - 8
1 = 3*11 - 4*8
1 = 3*11 - 4*(30-11*2)
1 = 11*11 - 4*30

on trouve donc que d=11 et k=4. Vérification: 11*e = 11*11 = 121 et 121 est bien congru à 1 modulo 30.

Voila comment trouver d, à la main ça va mais a coder je sais pas trop quelle forme ça peu prendre, cherche si éventuellement il existe des algo bien pour ce genre de calcul, mais tu peux ptete deja essayer de te debrouiller avec ça. Si ya un point sur lequel tu bloque n'hesite pas a me poser une question.

Pour ce qui est des grands nombre de calcul je pense qu'il faut coder le systeme soi-même, a savoir prendre plusieurs int pour un nombre et faires les calculs de retenu ou plus compliqué soi-même. Pour ce qui est d'élevé les nombres à la puissance il y a des algo particulier à appliquer qui ont un temps de calcul en theta(log(n)) je croit car faire la multiplication en boucle pour élever à la puissance c'est beaucoup trop gourmand. Bon courage pour la suite.

neodelphi

Bon après relecture, si tu piges pas l'histoire des Zn c'est pas catastrophique lol, essayes surtout de comprendre l'algo d'euclide si tu connais pas. J'aimerai ajouter que le RSA ça peut etre marant à coder, mais le plus interessant dans le cryptage ici c'est toute la théorie mathématique qu'il y a derrière, car le RSA ça tombe pas du ciel tout à été démontré...

neodelphi

vecchio56 -> merci pour le lien, j'ai telecharger la source, je vais voir ce que sa donne. J'avais deja lu des topics sur la lib gmp mais j'avais envie de coder sa moi meme (pour bien comprendre le truc)... mais c'est vrai que si c'est pas de mon niveaux et que la lib est facile d'acces , pourquoi se priver ?? Merci a toi !

neodelphi -> le moins que l'on puisse dire, c'est que tu mets du coeur a l'ouvrage. Meme si je n'ai pas tout compris (en fait une bonne partie), je te felicite ne serait-ce que pour avoir pris le temps de m'expliquer, ce qui devient rare de nos temps (alala ... :p je parle comme un vieux .. lol) 

Mon niveau en math n'est pas exeptionnel, n'on pas que je ne comprend pas les cours mais je n'en ai pas envie... je prefere apprendre toutes les formules dont j'ai besoin sur le moment et ne pas faire des trucs bidon qu'on nous fait faire en cours (les intergrales, les vecteurs et les equa diff... que du bonheur) et dont je n'ai pas d'utilite immediate... (ce n'est pas un bon raisonnement je sais mais personne n'est parfait..)

Je connaissais euclide mais pas le theoreme de Bezout, encore moins les anneaux commutatifs Zm. Je pense alle faire un tour sur ile des maths pour combler ce probleme. Je suis d'accord avec toi en disant que rsa est tres interessant au niveau des maths et qu'a programmer sa doit etre passionant, c'est bien la raison pour laquelle je me suis lance dans l'aventure ....

J'avais encore une derniere question (je sais j'accumule), c'est sur la longueur de la cle en bits et sur les blocs a crypter, toujours en bits. J'ai lu quelques sources a ce sujet et la plupart du temps, il prenait des blocs de 256 voir 512 bits pour crypter... J'avoue que je ne n'arrive pas a suivre..; (encore lol)

Je tenais a vous remerciez tous les deux pour vos reponses !

@++ et bon coding !

"Avant même de fonctionner, tout programme est déjà obsolète."

Je comprend que certain n'aime pas les math, moi je n'aime pas l'histoire et la géographie... En revanche pour ce qui est des maths je prend souvent un certain plaisir à travailler sur la théorie. Si tu veux te plonger dans les Zn fait quand même attention c'est pas évident (en fait il y a plein de concept à integrer avant pour tout démontrer).

Le théorème de Bezout en revanche est relativement simple (sa démonstration moins):

Si tu as une équation du genre:

a*b + c*d = 1

le théorème de Bezout dit que si a et c sont premiers entre eux, alors il existe forcement des valeurs de b et d vérifiant l'équation. L'algo d'Euclide permet de trouver ces valeurs.

Pour ta seconde question je ne peux pas te donner de réponses parceque je n'en ai tout simplement pas ! Le cryptage RSA marche avec n'importe quelle taille de clef. Le fait que la longueur de la clef soit en 2^n permet peut-etre d'effectuer les calculs plus rapidement...

neodelphi

Salut !
Apres avoir lu et essaye d'apprehender ton explication, j'ai un probleme avec ceci :

Si on prend p=5 et q=7, alors m = (p-1)(q-1) = 30.
je vais prendre pour valeur de e 11 car 11 est premier avec 30. On a donc:

11*d + k*30 = 1

On applique la division euclidienne plusieurs fois:
30 = 11 * 2 + 8
11 = 8 * 1 + 3
8 = 3 * 2 + 2
3 = 2 * 1 + 1

Comment peut tu decourvir que d = 2 et k = 8 ?? Par quelle raisonnement y es-tu parvenu ?? Je n'arrive pas a comprendre d'ou sorte ces 2 chiffres. Et au fait pour le calcul de e, il faut qu'il n'est aucun facteur commun avec le resultat de (p-1)(q-1), faut-il qu'il soit obligatoirement premier avec (p-1) et (q-1) ou juste p et q .... je pensais qu'il fallait juste que le reste de la division de e par (p-1)(q-1) ne devait pas etre un entier (donc un flotant).

Merci !

"Avant même de fonctionner, tout programme est déjà obsolète."

Désolé de répondre si tardivement...

L'astuce avec la division euclidienne c'est de remonter le calcul dans l'autre sens pour trouver les valeurs... Pout ton cas ça donnerai:

3 = 2*1+1  donne 1 = 3 - 2*1
donc on a:
1 = 3 - (2*1) = 3 - 2

8 = 3*2 + 2 donne 2 = 8 - (3*2)
en remplacant 2 de l'expression trois lignes au dessus on trouve:
1 = 3 - (8 - 3*2) = 3 - 8 + 3*2 = - 8 + 3*3

11 = 8*1 + 3 donne 3 = 11 - 8*1
en remplacant on trouve 3:
1 = -8 + 3*(11 - 8*1) = -8 + 3*11 -3*8 = -4*8 + 3*11

30 = 11*2+8 donne 8 = 30 - 11*2
encore en remplacant 8 on trouve:
1 = -4*(30 - 11*2) + 3*11
1 = -4*30 + 8*11 + 3*11
1 = -4*30 + 11*11

Faut un peu s'entraîner c'est pas évident au début...

Pour ce qui est de e il suffit qu'il soit premier avec ((p-1)(q-1)), ce qui reviend à dire que la division de ((p-1)(q-1)) par e est un flottant.

Si c'est tu le programmes, teste pas si c'est flottant ou non, calcule simplement le modulo:

si m = ((p-1)(q-1)) et e premier avec m tu as:
e % m == 0 (en C/C++ et Java)
e mod m == 0 (en Pascal)


neodelphi

Ok lol en relisant le sujet je viend de me rendre compte que j'ai fait le calcul deux fois... Je croyai que c'était ta division euclidienne... Bon je vais donc essayer de détailler:

dans une division euclidienne de a par c:
a = b*c + r - où b est le quotient et r le reste.

Pour la méthode, tu fait
a = b*c + r
et tu divise b par le reste r
b = r*b' + r'
b' = r'*b'' + r''
b'' = r''*b''' + r'''
jusqu'à ce que le reste soit égal à 1.

Ensuite tu remonte:
r''' = b'' - r''*b'''
puis tu remplace r'' grace à l'expression au dessus
r'' = b' - r'*b''
ce qui donne
r''' = b'' - (b' - r'*b'')

A force de remonter tu tombera sur une expression permettant de déduire les valeurs que tu cherche car r''' = 1.

neodelphi