Partage
  • Partager sur Facebook
  • Partager sur Twitter

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



    • Partager sur Facebook
    • Partager sur Twitter
      15 mars 2019 à 10:20:29

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

      Vu ton code , je confirme :D 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

      • Partager sur Facebook
      • Partager sur Twitter
        16 mars 2019 à 1:20:28

        neuneutrinos a écrit:

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

        Vu ton code , je confirme :D 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 florianbcr 16 mars 2019 à 1:21:13

        • Partager sur Facebook
        • Partager sur Twitter
          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

          • Partager sur Facebook
          • Partager sur Twitter
            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 :p

            Encore merci de l'aide

            • Partager sur Facebook
            • Partager sur Twitter

            Optimisation de RSA en C, calcul de d

            × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
            • Editeur
            • Markdown