Optimisation de RSA en C, calcul de d

13 mars 2019 à 19:25:21

Bonjour a tous,

J'ai un probleme quant à la realisation d'un programme simple de creation d'un algorithme de chiffrement en RSA. Tout fonctionne mais lorsque que je demande a mon programme de generer une clé superieur a 8 bits, je pense que la boucle while permettant de calculer la clé privé d devient donc presque une boucle infinie tellement la difficulté à trouvé d est importante.

J'ai fais plusieurs recherches et je bloque la dessus vraiment...

Merci d'avance pour votre futur aide.

void new_key(char *public_key, char *private_key, int size) {
	//p
	mpz_t p;
	mpz_init(p);
	random_prime_mpz(&p, size / 2);
	//q
	mpz_t q;
	mpz_init(q);
	random_prime_mpz(&q, size / 2);
	//n
	mpz_t n;
	mpz_init(n);
	mpz_mul(n, p, q);
	
	//p-1
	mpz_t p1;
	mpz_init(p1);
	mpz_sub_ui(p1, p, 1);
	//q-1
	mpz_t q1;
	mpz_init(q1);
	mpz_sub_ui(q1, q, 1);
	//phiN
	mpz_t phiN;
	mpz_init(phiN);
	mpz_mul(phiN, p1, q1);
	
	//e
	mpz_t e;
	mpz_t result;
	mpz_init(e);
	mpz_init(result);
	//random_mpz(&e, size / 2);
	mpz_set_ui(e, 2);
	mpz_gcd(result, e, phiN);
	
	while(mpz_cmp_ui(result, 1) != 0) {
		//random_mpz(&e, size / 2);
		mpz_add_ui(e, e, 1);
		mpz_gcd(result, e, phiN);
	}
	
	//d
	mpz_t d;
	mpz_init(d);
	mpz_set_ui(d, 0);
	mpz_mul(result, d, e);
	mpz_mod(result, result, phiN);
	while(mpz_cmp_ui(result, 1) != 0) {
		mpz_add_ui(d, d, 1);
		mpz_mul(result, d, e);
		mpz_mod(result, result, phiN);
	}
	
	//c
	mpz_t c;
	mpz_init(c);
	mpz_set_ui(c, 10000000);
	//c_crypted
	mpz_t c_crypted;
	mpz_init(c_crypted);
	mpz_powm(c_crypted, c, e, n);
	//c_decrypted
	mpz_t c_decrypted;
	mpz_init(c_decrypted);
	mpz_powm(c_decrypted, c_crypted, d, n);
	
	printf("=================================\n");
	gmp_printf("p = %Zd\n", p);
	gmp_printf("q = %Zd\n\n", q);
	gmp_printf("n = %Zd\n", n);
	gmp_printf("phiN = %Zd\n", phiN);
	gmp_printf("e = %Zd\n", e);
	gmp_printf("d = %Zd\n\n", d);
	gmp_printf("c = %Zd\n", c);
	gmp_printf("c_crypted = %Zd\n", c_crypted);
	gmp_printf("c_decrypted = %Zd\n", c_decrypted);
	printf("=================================\n");
}

void random_mpz(mpz_t *mpz, int size) {
	char number[10] = {"0123456789"};
	char number_first[10] = {"123456789"};
	char str[4000];
	int a = randombytes_uniform(9);
	str[0] = number_first[a];
	int i;
	for(i = 1; i != size; i++) {
		a = randombytes_uniform(10);
		str[i] = number[a];
	}
	mpz_set_str(*mpz, str, 10);
}

void random_prime_mpz(mpz_t *mpz, int size) {
	char number[10] = {"0123456789"};
	char number_first[10] = {"123456789"};
	char str[4000];
	int a = randombytes_uniform(9);
	str[0] = number_first[a];
	int i;
	for(i = 1; i != size; i++) {
		a = randombytes_uniform(10);
		str[i] = number[a];
	}
	mpz_set_str(*mpz, str, 10);
	mpz_nextprime(*mpz, *mpz);
}

neuneutrinos

15 mars 2019 à 10:20:29

Tu dis que d est trop long à être calculé ?

Vu ton code , je confirme c'est assez brute-force !
d est l'inverse de e modulo phi

et ta démarche (qui fonctionnne mais assez lent ) est de dire que si d est l'inverse de e modulo phi, alors d*e doit valoir 1 modulo phi.
Et de progresser de 1 en 1 jusqu'à ce que la propriété soit valide.

Mais ce n'est pas une manière efficace.

Une autre manière est de partir de :
d*e % phi = 1
<=> k : relatif
d*e = 1 + k*phi
<=>
d*e - k*phi = 1 <=== equation diophantienne detected /!\

k étant relatif, on peut faire un changement de variable (sachant qu'on se fiche pas mal de sa valeur)
d*e+k*phi =1

Avec l'algorithme d'euclide étendu cela se calcule très bien.
(je te donne un exemple pour t'aider à voir comment le coder)

Ce que l'on cherche :
prenons un exemple avec e = 31 et phi = 881
(d,k) = 31d + 881k = 1

(0,1) = 31*0 + 881*1 = 881
(1,0) = 31*1 + 881*0 = 31

881/31 = 28 reste 13

(0,1)-28*(1,0) = (-28,1) = 13

31/13 = 2 reste 5

(1,0)-2*(-28,1) = (57,-2) = 5

13/5 = 2 reste 3

(-28,1) - 2*(57,-2) = (-142,5) = 3

5/3 = 1 reste 2

(57,-2) - 1*(-142,5) = (199,-7) = 2

3/2 = 1 reste 1

(-142,5) - 1*(199,-7) = (-341,12) = 1 = (d,k)

Vérification 
-341*31 = -10571
881*12 = 10772

d= -341

Dans ce calcul d peut être négatif.

Dans ce cas on se rappelle qu'on est modulo phi

-
Edité par neuneutrinos 15 mars 2019 à 10:21:19

floriandmt

16 mars 2019 à 1:20:28

neuneutrinos a écrit:

Tu dis que d est trop long à être calculé ?

Vu ton code , je confirme c'est assez brute-force !
d est l'inverse de e modulo phi

et ta démarche (qui fonctionnne mais assez lent ) est de dire que si d est l'inverse de e modulo phi, alors d*e doit valoir 1 modulo phi.
Et de progresser de 1 en 1 jusqu'à ce que la propriété soit valide.

Mais ce n'est pas une manière efficace.

Une autre manière est de partir de :
d*e % phi = 1
<=> k : relatif
d*e = 1 + k*phi
<=>
d*e - k*phi = 1 <=== equation diophantienne detected /!\

k étant relatif, on peut faire un changement de variable (sachant qu'on se fiche pas mal de sa valeur)
d*e+k*phi =1

Avec l'algorithme d'euclide étendu cela se calcule très bien.
(je te donne un exemple pour t'aider à voir comment le coder)
Ce que l'on cherche :
prenons un exemple avec e = 31 et phi = 881
(d,k) = 31d + 881k = 1

(0,1) = 31*0 + 881*1 = 881
(1,0) = 31*1 + 881*0 = 31

881/31 = 28 reste 13

(0,1)-28*(1,0) = (-28,1) = 13

31/13 = 2 reste 5

(1,0)-2*(-28,1) = (57,-2) = 5

13/5 = 2 reste 3

(-28,1) - 2*(57,-2) = (-142,5) = 3

5/3 = 1 reste 2

(57,-2) - 1*(-142,5) = (199,-7) = 2

3/2 = 1 reste 1

(-142,5) - 1*(199,-7) = (-341,12) = 1 = (d,k)

Vérification 
-341*31 = -10571
881*12 = 10772

d= -341

Dans ce calcul d peut être négatif.

Dans ce cas on se rappelle qu'on est modulo phi 
-
Edité par neuneutrinos il y a environ 14 heures

Merci avec quelques recherche je suis arrivé à un petit algorithme.

J'arrive maintenant a générer une clé de chiffrement de 1024 bits de façon bien plus rapide, avant j'etait limité a 8 lol ^^'

Je n'arrive pas a monté a 2048 par exemple, je pense que même avec toute les optimisations possible sa doit être trop long pour l’ordinateur...

void bezout_mpz(mpz_t *a, mpz_t *b, mpz_t *d) {
	//a0
	mpz_t a0;
	mpz_init(a0);
	mpz_set(a0, *a);
	//b0
	mpz_t b0;
	mpz_init(b0);
	mpz_set(b0, *b);
	
	//p
	mpz_t p;
	mpz_init(p);
	mpz_set_ui(p, 1);
	//q
	mpz_t q;
	mpz_init(q);
	mpz_set_ui(q, 0);
	//r
	mpz_t r;
	mpz_init(r);
	mpz_set_ui(r, 0);
	//s
	mpz_t s;
	mpz_init(s);
	mpz_set_ui(s, 1);
	
	//c
	mpz_t c;
	mpz_init(c);
	//quotient
	mpz_t quotient;
	mpz_init(quotient);
	//nouveau_r
	mpz_t nouveau_r;
	mpz_init(nouveau_r);
	//nouveau_s
	mpz_t nouveau_s;
	mpz_init(nouveau_s);
	
	while(mpz_cmp_ui(*b, 0) != 0) {
		mpz_mod(c, *a, *b);
		mpz_fdiv_q(quotient, *a, *b);
		
		//gmp_printf("a = %Zd, b = %Zd\n", a, b);
		mpz_set(*a, *b);
		mpz_set(*b, c);
		
		mpz_mul(nouveau_r, quotient, r);
		mpz_sub(nouveau_r, p, nouveau_r);
		
		mpz_mul(nouveau_s, quotient, s);
		mpz_sub(nouveau_s, q, nouveau_s);
		
		mpz_set(p, r);
		mpz_set(q, s);
		mpz_set(r, nouveau_r);
		mpz_set(s, nouveau_s);
		//mpz_clears(c, quotient, r, s);
	}
	
	mpz_set(*d, p);
	mpz_set(*a, a0);
	mpz_set(*b, b0);
	while(mpz_cmp_ui(*d, 0) < 0) {
		mpz_add(*d,*d, *b);
	}
	//gmp_printf("pgcd(%Zd,%Zd)=%Zd*%Zd+(%Zd)*%Zd=%Zd\n", e0, phiN0, p, e0, q, phiN0, e);
}

-
Edité par floriandmt 16 mars 2019 à 1:21:13

melepe

18 mars 2019 à 12:16:15

Deux trois remarques sur ton code :

Tu parles de clefs de 2048 bits, mais tu fais des calculs en base 10. Tu es bien sûr de prendre des entiers de la bonne taille ? Pour du RSA 2048 bits les nombres premiers sont de taille 1024 bits.

Pour calculer l'inverse modulaire, tu pourrais utiliser OpenSSL, mais j'imagine que tu veux tout recoder toi-même, ce qui est mieux pour apprendre.

En ce qui concerne ton algorithme, j'imagine que tu t'es inspiré de https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode ? En soi si tu utilises cette méthode je ne sais pas s'il y a une variante plus rapide. Il faudrait analyser comment fait OpenSSL : https://github.com/openssl/openssl/blob/367ace6870e9cbc8fe21dff2ffe4673a98ea42f8/crypto/bn/bn_gcd.c#L124

Par contre, tu peux gérer tes clefs de façon un peu différente. Par exemple, comme ici :https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Using_the_Chinese_remainder_algorithm où tu n'as plus besoin de calculer les inverses que modulo p, plutôt que modulo (p-1)(q-1).

Enfin, le vrai chiffrement RSA ne consiste pas juste à mettre m à la puissance e, il faut rajouter du padding, de l'aléa... Tu dois aussi vérifier deux trois trucs sur d pour éviter l'attaque de Coppersmith. Tu peux lire l'ensemble des choses à vérifier en lisant la RFC : https://tools.ietf.org/html/rfc3447

floriandmt

18 mars 2019 à 18:41:04

melepe a écrit:

Deux trois remarques sur ton code :

Tu parles de clefs de 2048 bits, mais tu fais des calculs en base 10. Tu es bien sûr de prendre des entiers de la bonne taille ? Pour du RSA 2048 bits les nombres premiers sont de taille 1024 bits.

Pour calculer l'inverse modulaire, tu pourrais utiliser OpenSSL, mais j'imagine que tu veux tout recoder toi-même, ce qui est mieux pour apprendre.

En ce qui concerne ton algorithme, j'imagine que tu t'es inspiré de https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Pseudocode ? En soi si tu utilises cette méthode je ne sais pas s'il y a une variante plus rapide. Il faudrait analyser comment fait OpenSSL : https://github.com/openssl/openssl/blob/367ace6870e9cbc8fe21dff2ffe4673a98ea42f8/crypto/bn/bn_gcd.c#L124

Par contre, tu peux gérer tes clefs de façon un peu différente. Par exemple, comme ici :https://en.wikipedia.org/wiki/RSA_(cryptosystem)#Using_the_Chinese_remainder_algorithm où tu n'as plus besoin de calculer les inverses que modulo p, plutôt que modulo (p-1)(q-1).

Enfin, le vrai chiffrement RSA ne consiste pas juste à mettre m à la puissance e, il faut rajouter du padding, de l'aléa... Tu dois aussi vérifier deux trois trucs sur d pour éviter l'attaque de Coppersmith. Tu peux lire l'ensemble des choses à vérifier en lisant la RFC : https://tools.ietf.org/html/rfc3447

Je te remercie enormement pour ton aide sur mon code.

Oui je me suis inspiré de Wikipedia ^^'... c'est pas glorieux je sais...

Je vais allez lire tout ce que tu m'a donné comme information et si j'ai des questions je reviendrais vers toi

Encore merci de l'aide