Trouver des cles pour RSA
Répondre à la discussion
Page 1 sur 2 1 DernièreDernière
Affichage des résultats 1 à 30 sur 31

Trouver des cles pour RSA



  1. #1
    prgasp77

    Trouver des cles pour RSA


    ------

    Bonjour, je vous expose mon probleme :

    J'ai cree un systeme de cryptage RSA, il ne me reste plus qu'a trouver des cles. Je parviens a trouver N, phi(N) et E mais le calcul de D me pose probleme. En effet il m'arrive de trouver un D negatif ou qui genere des nombre negatif apres le criptage.
    Le probleme ne vient pas du criptage, il fonctionne avec des cles toutes faites comme N = 851 ; E = 17 ; D = 233.

    Voici mon code php bien documente :
    Code:
    //On "descent" l'egalite Eu_1 + phi(N)v_1 = 1 grace a l'algorithme d'euclide. (PGCD)
    	//On initialise les variables.
    
    $reste[0] = 1; // on initialise $reste[0] != 0.
    $reste1[1] = $phiN;
    $reste2[1] = $e;
    $i = 1; //On initialise $i a 1 pour eviter dans la condition du while $reste[-1]. On corrige cette erreur plutard.
    
    while ($reste[$i-1] != 0) // tant que $reste[$i-1] non nul ...
    	{ //faire ...
    	$reste[$i] = $reste1[$i] % $reste2[$i]; // $reste[$i] = reste de la division euclidienne $reste1[$i]/$reste2[$i]
    	$reste1[$i+1] = $reste2[$i]; // On fait passer les valeur d'une variable a l'autre (PGCD)
    	$reste2[$i+1] = $reste[$i]; // idem
    	$reste[$i+1]  = 1; // peu util ...
    	$i++; // on increment $i de 1
    	} // fin de la boucle while
    $i = $i - 2; //On corrige l'erreur precedente mais on en commet une autre pour pouvoir remonter.
    
    //On "remonte" (methode inconnue)
    
    $u[$i] = 1;
    $v[$i] = 1;
    while ($i > 0) // tant que $i positif ...
    	{ // faire ...
    	$i--; // on decremente $i
    	$u[$i] = $v[$i+1];
    	$v[$i] = $u[$i+1] - (($reste1[$i+1]-$reste[$i+1])/$reste2[$i+1]) * $v[$i+1];
    	}
    echo "D = " . $v[0];
    Voila, une erreur se cache dans ce code (lol). Je me demande si je fais bien d'initialiser $u[$i] a 1 ...
    Qu'en pensez vous ?

    -----
    --Yankel Scialom

  2. #2
    invite3f53d719

    Arrow Re : Trouver des cles pour RSA

    Lu,
    Vu que d est l'inverse de e modulo phi, il existe une fonction intégré à php permettant de faire ca: http://www.nexen.net/docs/php/annote...gmp-invert.php (valable uniquement sous php4).

    Eric

  3. #3
    invite3f53d719

    Re : Trouver des cles pour RSA

    Je pense savoir d'où vien l'erreur... En fait, il n'y en a pas C'est juste que tu te retrouve avec un nombre négatif qui est congru à d modulo phi. Ton algorithme fonctionne, mais il retourne le plus petit nombre en valeur absolue qui est l'inverse de e modulo phi. Pour avoir un d positif, il te suffit de rajouter phi si d est négatif.
    Si en fait c'est ton algo qui merde, je peux te passer le mien (en Java, et pas commenté )
    Code:
    public static int inv(int i, int p)
        {
    	int r = i, r1 = p, aux, u = 1, u1 = 0, q;
    	do
    	{
    	    q = (int)(r/r1);
    	    aux = r;
    	    r = r1;
    	    r1 = aux - r1 * q;
    	    aux = u;
    	    u = u1;
    	    u1 = aux - q * u1;
    	}
    	while (r1 != 0);
    	int n = u;
    	if (r == 1)
    	{
    	    return n;
    	}
    	else
    	{
    	    return -1;
    	}
        }
    En esperant que tu comprennes quelque chose...

    Eric

  4. #4
    prgasp77

    Re : Trouver des cles pour RSA

    Merci de votre aide, mais je vais demander un petit effort suplementaire, desole.
    premierement, je n'ai pas compris ce qu'etait l'inverse d'un modulo. a mod b, inverse => ?
    Deuxiemement, je n'ai jamais etudie le java. Que signifie inv (je suppose que int est integer), aux.

    Ensuite, pourquoi r1 serait != 0 puisque = aux - (r1 * q) = aux - r1* (r/r1) = aux - r = 0 car r = aux.

    Peux-tu stp me commenter un peu ton code. Merci.
    --Yankel Scialom

  5. A voir en vidéo sur Futura
  6. #5
    invited04d42cd

    Re : Trouver des cles pour RSA

    bon avec mes modestes connaissances de seconde, je vais essayer de t'expliquer...
    premierement, je n'ai pas compris ce qu'etait l'inverse d'un modulo. a mod b, inverse => ?
    L'inverse d'un modulo n'"existe" (ce n'est pas le bon terme mais je n'en ai pas d'autres en réserve lol) pas, c'est pour cela que le modulo est utilisé en cryptage : elle n'est pas réversible.
    Regarde :
    a = r(mod q)
    Soit : q * k + r = a
    Si tu as q * k + r = 4 * k + 3, soit 3(mod4), a peut être égal à 7, ou 11, ou 15, etc... Il n'y a pas de limite, d'où la très grande utilité de cette fonction en cryptographie, car elle n'admet pas d'inverse "direct".

  7. #6
    invite3f53d719

    Re : Trouver des cles pour RSA

    Lu,

    Je te conseilles de regarder l'extrait de mon tpe sur RSA, à la fin, tu y trouveras l'algorithme en francais (qui utilise l'algorithme d'Euclide étendu) pour calculer un inverse modulo, ainsi que d'autres choses qui pourront t'être utiles. l'inverse de a mod n est le nombre b tel que a congru à b mod n. http://tpe.crypto.free.fr/index.html..._publique/RSA/

    Eric

    PS: désolé, mais j'ai énormément de mal à relire et à comprendre mon (et le tien aussi) algorithme, et je n'ai pas vraiment le courage de m'y replonger...

  8. #7
    invite3f53d719

    Re : Trouver des cles pour RSA

    Lu,
    Citation Envoyé par easythomas
    L'inverse d'un modulo n'"existe" (ce n'est pas le bon terme mais je n'en ai pas d'autres en réserve lol) pas, c'est pour cela que le modulo est utilisé en cryptage : elle n'est pas réversible.
    La, désolé, mais je pense que tu confond... On peut parfaitement calculer un inverse de a mod b(Cf l'algo d'Euclide étendue), il y en a même une infinité (à condition que PGCD(a,b)=1). Je pense que tu confond avec la fonction puissance, qui elle n'est pas inversible facilement( c'est même presque impossible, d'où l'utilisation dans RSA). Par exemple, tu sais facilement faire 1121541 mod 283, mais pour retrouver 21541 à partir de 11 et de 283, tu es obligé d'essayer tout les exposants possibles, ce qui deviens impensable avec des nombres de plus de 100 chiffres...

    Eric, qui sent qu'il n'est pas clair

  9. #8
    invited04d42cd

    Re : Trouver des cles pour RSA

    en fait, je ne voulais pas dire n'existe pas, mais qu'on ne peut le retrouver, car il y en a une infinité, comme je l'ai dit ensuite. On ne peut donc parler d'un "inverse" proprement dit non ?
    Enfin bon tout cela est obscur pour moi...
    Je sens que je vais moi aussi me lancer dans un script php, c'est diablemeent interessant

  10. #9
    prgasp77

    Re : Trouver des cles pour RSA

    En prog, le modulo est le reste d'une division euclidienne, pas comme en maths. Pour l'inverse modulo j'ai trouve, je vous fait un topo :
    Soit n = inverse modulo de a par b
    alors an mob b = 1
    Dernière modification par prgasp77 ; 24/06/2004 à 02h41.
    --Yankel Scialom

  11. #10
    prgasp77

    Re : Trouver des cles pour RSA

    J'ai un nouvel algorithme :
    Code:
    for ( $m = 1 ; ($m * $phiN + 1) % $e ) != 0 ; $m++ )
    	{
    	}
    $d = ($m * $phiN + 1) / $e;
    echo "D = $d";
    Il ne fonctionne qu'avec de petits nombres ... sniff
    --Yankel Scialom

  12. #11
    prgasp77

    Re : Trouver des cles pour RSA

    Il y a une erreur, un ) en trop.

    Autre chose d'intrigant, voila mon code qui permet de cripter :
    Code:
    		$m = $tabMessage[$i];
    		$k = 1;
    		while ($e != 1)
    			{
    			if ( $e % 2 == 0 ) //Si $e paire ...
    				{
    				$m = ($m * $m) % $n1;
    				$e = $e/2;
    				$k = $k % $n1;
    				}
    			else              // Si $e impaire ...
    				{
    				$k = ($k * $m) % $n1;
    				$m = ($m * $m) % $n1;
    				$e = ($e - 1) / 2;
    				}
    			}
    			$tabIntMessageCripte[$i] = ($k * $m) % $n1;
    Et dans certains cas, le resultat retourne est NEGATIF !!! J'ai verifie, pour que $tabIntMessageCripte[$i] soit negatif, il faut que ($k * $m) % $n1 soit negatif et cela ne peut se produire ssi $k * $m negatif.
    Or au depart $k = 1 et $m > 0. On demontre aisement, par recurence que $m le reste (car egal a son carre modulo $n1, carre > 0 => $m > 0) tout comme on demontre que $k le reste car egal a $k * $m % $n1 (meme remarque, si $k * $m % $n1 > 0 <=> $k * $m > 0 et $k > 0)

    Vous voyez le probleme, j'ai un nombre negatif qui NE PEUT PAS EXISTER !!!
    --Yankel Scialom

  13. #12
    droupi

    Re : Trouver des cles pour RSA

    En informatique, un nombre negatif PEUT EXISTER !!!
    Tu dis pour certaines valeurs, alors donne un exemple de valeur, au lieu de t'étonner de certaines choses.
    Et dévermine ton programme, par exemple en examinant les résultats intermédiaires.

  14. #13
    droupi

    Re : Trouver des cles pour RSA

    Je connais pas PhP, mais je crois qu'il s'appuie sur les mêmes typages qu'en C, donc je serais pas étonné que pour un m > 65536 (tout dépends) tu ais quelques problèmes.

  15. #14
    prgasp77

    Re : Trouver des cles pour RSA

    php est un langage d'amateurs, il n'y a pas de problemes a depasser 65536 ...
    --Yankel Scialom

  16. #15
    droupi

    Re : Trouver des cles pour RSA

    Langage d'amateurs ? Je vois pas ce que ça veut dire. En tout cas, en vérifiant, je confirme que le typage est identique à celui du C, donc sur un processeur courant, un entier à une valeur max de 231 = 2,15.109. Si sur un produit, tu dépasse cette valeur, t'auras des problèmes. Sans étudier ton programme, c'est la réponse la plus raisonnable (quoique qu'avec le modulo, comme cela, je sais pas si t'auras un résultat négatif, mais résultat faux).
    Dernière modification par droupi ; 24/06/2004 à 03h48.

  17. #16
    prgasp77

    Re : Trouver des cles pour RSA

    Je contourne cette limite par des fonction bc (qui limitent un nombre a 10^308) Je ne les ai pas mises ici pour eviter de compliquer le code.
    --Yankel Scialom

  18. #17
    droupi

    Re : Trouver des cles pour RSA

    D'accord, mais si tu les indiques pas, on pourra jamais savoir si tu les utilisent bien en regard du code donné.

  19. #18
    invite3f53d719

    Re : Trouver des cles pour RSA

    Citation Envoyé par prgasp77
    En prog, le modulo est le reste d'une division euclidienne, pas comme en maths. Pour l'inverse modulo j'ai trouve, je vous fait un topo :
    Soit n = inverse modulo de a par b
    alors an mob b = 1
    Excuse moi, j'ai tapé une connerie sans m'en rendre compte (ca m'apprendra à me relire...). L'inverse modulo est bien en maths comme partout ce que tu as dit. Bon, sinon, ton code pour crypter est étrange, car il n'a rien avoir avec RSA... Tu es sur que tu maitrise bien le protocole RSA??? Enfin, une remarque d'ordre générale sur la programmation: quand tu as un problème dans tes algo, c'est toujours très chiant de piger ce qui va pas par la reflexion... Il vaut mieux utiliser un debogueur qui te montrera le problème de suite, car tu pourra voir les valeurs de toutes tes variables à n'importe quelle itération de la boucle. Si tu n'a pas de débogueur, alors affiche tes variables intermédiaires. (ca va beaucoup plus vite que de faire des raisonements par réccurence ).

    Eric, qui te conseille d'aller revoir un site (comme le mien ) sur RSA, et de voir certains trucs d'arithmétique.

    PS: 10^308 est une limite infiniment trop faible pour RSA... Vu que tu calcule des nombres comme 23^e avec e ayant plus de 50 chiffres...

  20. #19
    invited04d42cd

    Re : Trouver des cles pour RSA

    Quel langage faut-il donc utiliser

  21. #20
    invite3f53d719

    Re : Trouver des cles pour RSA

    Bah surement que php possède une solution, mais je ne me suis pas penché sur la question... Java est un bon language pour ca (il y a une classes BigInteger qui permet de prendres des nombres aussi grand que l'on veut), vu que tu peux mettre facilement sur le net ton applet. De plus, cela bouffe les ressources du client, et on du serveur comme php, ce qui est bien plus efficace en cas de surcharge du serveur. Tu peux aussi faire ca en C ou C++ si tu as vraiment besoin de vitesse. Par contre, Java (de même que C et C++) est bien plus compliqué à comprendre que php...

    Eric

  22. #21
    invited04d42cd

    Re : Trouver des cles pour RSA

    droupi a dit que la limite était la même entre php et c
    Bon, je pense que je vais opter pour le c++, et apprendre un nouveau langage
    Mais je ne suis pas sur que cela fonctionne quand même : au bout d'un certain nombre, le processeur plantera, ou alors mettra un temps fou.
    Je ne suis pas sur du tout qu'on puisse arriver a une puissance de 23 avec un exposant supérieur à 50chiffres, cela est meme surement impossible avec un P3 que j'ai :P

  23. #22
    prgasp77

    Re : Trouver des cles pour RSA

    Ce que je vous ai montre n'est pas l'algorithme de chiffrement, mais celui qui permet de trouver des cles (calcul de D ici). Ensuite, j'ai cree une fonction qui permet de gerer les nombres comme des chaines de caracteres et donc de depasser des nombres tels que 10^10^10^10 ... Je pense que ca suffira, plus gros, le serveur fera la gueule
    --Yankel Scialom

  24. #23
    invite3f53d719

    Re : Trouver des cles pour RSA

    Citation Envoyé par easythomas
    droupi a dit que la limite était la même entre php et c
    Bon, je pense que je vais opter pour le c++, et apprendre un nouveau langage
    Mais je ne suis pas sur que cela fonctionne quand même : au bout d'un certain nombre, le processeur plantera, ou alors mettra un temps fou.
    Bon alors, la limite en c n'est absolument pas 65535, c'est la limite pour une variable de type int qui prend 16 bits en mémoire (2^16=65536). Après, tu as d'autre type de variable qui prennent plus de place et qui sont donc plus grandes. Et t'inquiète pas pour ton processeur, il gère très bien ca
    @ prgasp, tu as bien dit "Autre chose d'intrigant, voila mon code qui permet de cripter :". J'en ai donc conclu que le code qui suivait était bien l'algorithme de chiffrement

    Eric

  25. #24
    droupi

    Re : Trouver des cles pour RSA

    Personne n'a dit que la limite en C et en PhP d'un int était 65536. Relisez avant de dire de tels choses.
    Qu'en à passer au C++, cela ne changera pas fondamentalement ce genre de problème. De plus seule la bibliothèque mathématique gère les dépassement de valeur (mais il faut les gérer), si sur un entier int, tu fais une opération arithmétique simple, c'est au programmeur de gérer directement les dépassements de valeur.
    Maintenant sur l'algorithme présenté, s'il y a une valeur négative, c'est qu'il y a une erreur de programmation. N'affecte-tu pas le résultat d'une opération BC dans un int au final ? (Je n'ai aucune idée des conséquences en PhP).

  26. #25
    prgasp77

    Re : Trouver des cles pour RSA

    D'accird, mais ca ne regle pas mon probleme. Puiisque personne trouve l'erreur dans mon algorithme, personne en aurait un tout fait pour trouver des cles pour RSA ? (titre du topic).
    --Yankel Scialom

  27. #26
    droupi

    Re : Trouver des cles pour RSA

    Je ne sais vraiment pas comment je dois le prendre...

    As-tu lu ce que j'ai dit? Il ne suffit pas de nous donner ton algorithme pour que cela marche, car je pense que le problème vient de l'implémentation de ton algo, i.e le programme. Je t'ai demandé des exemples de valeurs pour lesquelles tu as des valeurs négatives. Rien. Je t'ai demandé de nous donner ton programme tel que tu l'as écrit au final, et non du code raccourci. Rien.

    Si tu veux un algorithme ou un programme RSA, il y a :

    www.google.fr

  28. #27
    prgasp77

    Re : Trouver des cles pour RSA

    Voici mon code complet permettant de creer des cles :
    Code:
    <html><body><div align="center"><?php
     /*=====================================================*\
    |*                		 Recuperer le pass	                		 *|
     \*=====================================================*/
    $strPass = $_POST['pass'];
    $tabStrPass = $strPass; // on met chaque lettre du mot dans un index du tableau
    if ( empty($tabStrPass[4]) ) // peu important
    	{
    	echo " Votre mot doit contenir au moins cinq caracteres.<br />";
    	echo "<form action='rsa.htm'><input type='submit' value='Retour' /></form>";     	//10
    	exit;
    	}
    
     /*=====================================================*\
    |*                		 Calculer p, q et E	         	        	          *|
     \*=====================================================*/
    /* On met dans tabNombrePremier les 10 000 premiers nombres premiers
    debut...*/
    $varNombreTeste = 2;
    $tabNombrePremier[1] = 2;
    $NombresTrouves = 1;										//20
    while ($varNombreTeste < 10000)
    	{
    	$varNombreTeste++;
    	$i = 0;
    	while ( $i <= $NombresTrouves )
    		{
    		$i++;
    		if ( $varNombreTeste/$tabNombrePremier[$i] == round($varNombreTeste/$tabNombrePremier[$i]) )
    			{
    			$i = $NombresTrouves +1;						//30
    			}
    		elseif ( $i == $NombresTrouves )
    			{
    			$tabNombrePremier[$i+1] = $varNombreTeste;
    			$NombresTrouves++;
    			}
    		}
    	}
    /* ... et fin */
    $p = $tabNombrePremier[ ord($tabStrPass[0]) + ord($tabStrPass[1]) ];	//$p est un nombre premier choisi selon le pass entré			//40
    $q = $tabNombrePremier[ ord($tabStrPass[2]) + ord($tabStrPass[3]) ];       //idem
    $e = $tabNombrePremier[ ord($tabStrPass[4])];                                      //idem
    echo $p . " --- " . $q . " --- " . $e . "<br />"; //verification de debogage
    
     /*=====================================================*\
    |*                       		Calculer N                     		 *|
     \*=====================================================*/
    $n = bcmul($p , $q); // multiplication
    echo "N = $n";
    echo "<br />";
    												//50
     /*=====================================================*\
    |*                      		 Afficher E                     		 *|
     \*=====================================================*/
    echo "E = $e";
    echo "<br />";
    
     /*=====================================================*\
    |*                    		 Calculer phi(N)                   	*|
     \*=====================================================*/
    $phiN = bcmul($p - 1 , $q - 1);	//multiplication								//60
    
     /*=====================================================*\
    |*    	Calculer D en sachant que ED = 1 mod phi(N)        	          *|
    \*=====================================================*/
    
    for ( $m = 1 ; bcmod( $m * $phiN + 1 , $e ) != 0 ; $m++ ) // bcmod(a,b) = a%b
    	{
    	}
    $d = ($m * $phiN + 1) / $e;
    echo "D = $d";
    
    
    echo "<form action='rsa.htm'><input type='submit' value='Retour' /></form>";								
    
    ?><iframe width="100%" height="70%" src="rsa.htm"></iframe>
    </div></body></html>
    Grace a cette technique, D est toujours positif. En revanche, une tres grande partie des mots entres ('pass') donnent un N et un E qui generent des nombres positifs (pour l'instant, tous les essais ont echoue)
    --Yankel Scialom

  29. #28
    prgasp77

    Re : Trouver des cles pour RSA

    J'ai l'impression de tourner en rond. Alors je vais vous exposer mon probleme a la source :

    Soient p et q deux nombres premiers.
    Soit N = p.q, d'ou phi(N) = (p-1).(q-1) (fonction d'Euler).
    Soit E premier et inferieur a phi(N).

    Il faut trouver l'entier D tel que
    E.D = 1 modulo phi(N)

    exemple :
    p = 23
    q = 37
    E = 17

    N = 851
    phi(N) = 792

    17D = 1 modulo 792 => D = 233 ( 17*233 = 1 modulo 792 car 3961 - 5*792 = 1 )


    Je ne suis ncapable de trouver D (le calcul de l'exemple ne vient pas de moi mais d'un magazine). Je cherche donc une methode (un algo) pour trouver D.


    Merci de m'aider.
    --Yankel Scialom

  30. #29
    invite3f53d719

    Re : Trouver des cles pour RSA

    Bah si tu lisais les messages aussi... Je t'ai donné un algorithme qui marche:
    Code:
    t0 = 0
    t = 1
    q = nombre entier immédiatement inférieur ou égal à b0 / a0
    r = b0 - qa0
    Tant que r > 0 faire
    ***Début
    ******k = t0 - q · t
    ******Si k >= 0 alors k = k (b), sinon k = b - (-k (b))
    ******t0 = t
    ******t = k
    ******b0 = a0
    ******a0 = r
    ******q = nombre entier immédiatement inférieur ou égal à b0 / a0
    ******r = b0 - qa0
    ***Fin
    Si a0<> 1 alors a n' a pas d' inverse modulo b, sinon a-1 (b) = t
    Il utilise l'algorithme d'Euclide comme je l'ai déja dit. Bon, vu que google n'a pas l'air d'être ton ami, je te donne un lien qui t'expliquera tout:http://www.labri.fr/Perso/~betrema/d...y/euclide.html . Il y a meme des algo en c comme exemples.

    @+ Eric

  31. #30
    invite3f53d719

    Re : Trouver des cles pour RSA

    J'ai oublié de te précisé le lien (simple, mais bon...) entre l'algorithme d'Euclide Etendu qui te permet de trouver les coefficients dans l'égalité de Bezout. Imaginons que tu cherches l'inverse de 21 mod 211. Tu trouve grâce à l'algorithme 211 = 10*21 + 1, donc 211 - 10*21 = 1, donc -10*21 congru à 1 mod 211, donc -10 est un inverse de 21 mod 211, CQFD. Bon, là, tu as un nombre négatif, et il suffit d'ajouter 211 à -10 pour trouver un nombre positif. On a bien 201*21 congru à 1 mod 211.

    Eric

Page 1 sur 2 1 DernièreDernière

Discussions similaires

  1. Besoin d'aide pour trouver des composants
    Par invite2de8d382 dans le forum Électronique
    Réponses: 7
    Dernier message: 18/11/2007, 10h45
  2. La composition des clés
    Par invite61942757 dans le forum Chimie
    Réponses: 0
    Dernier message: 28/06/2007, 15h14
  3. [Brun] ou trouver des pieces pour ma tele sony
    Par invite20a9fb02 dans le forum Dépannage
    Réponses: 2
    Dernier message: 28/03/2007, 19h36
  4. Bonjour, aide pour trouver des composants
    Par invite5c2631d5 dans le forum Dépannage
    Réponses: 6
    Dernier message: 05/10/2004, 15h37