Trouver des cles pour RSA

[invite7553e94d]

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 :

//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 ?
-----

[invite3f53d719]

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

[invite3f53d719]

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é )

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

[invite7553e94d]

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.

[A voir en vidéo sur Futura]

[invited04d42cd]

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".

[invite3f53d719]

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...

[invite3f53d719]

Lu,

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 11²¹⁵⁴¹ 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

[invited04d42cd]

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

[invite7553e94d]

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

[invite7553e94d]

J'ai un nouvel algorithme :

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

[invite7553e94d]

Il y a une erreur, un ) en trop.

Autre chose d'intrigant, voila mon code qui permet de cripter :

		$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 !!!

[inviteb9b852ac]

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.

[inviteb9b852ac]

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.

[invite7553e94d]

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

[inviteb9b852ac]

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 2³¹ = 2,15.10⁹. 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).

[invite7553e94d]

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.

[inviteb9b852ac]

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

[invite3f53d719]

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...

[invited04d42cd]

Quel langage faut-il donc utiliser

[invite3f53d719]

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

[invited04d42cd]

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

[invite7553e94d]

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

[invite3f53d719]

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

[inviteb9b852ac]

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).

[invite7553e94d]

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).

[inviteb9b852ac]

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

[invite7553e94d]

Voici mon code complet permettant de creer des cles :

<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)

[invite7553e94d]

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.

[invite3f53d719]

Bah si tu lisais les messages aussi... Je t'ai donné un algorithme qui marche:

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

[invite3f53d719]

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