Calcul d'une clé privée RSA

Calcul d'une clé privée RSA - Algo - Programmation

Marsh Posté le 18-01-2010 à 17:04:21    

Bonjour à tous, dans un programme je doit utiliser un cryptage RSA donc les clés seront générées depuis un mot de passe
Je n'en suis qu'au début mais je rencontre d'hors et déjà un problème lors de la définition des clés, en fonction des chiffres entrés au début (qui par la suite seront calculés par un autre algo) il est parfois impossible de définir une clé privée
Voici mon code:

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  4. int pgcd(int a, int b)
  5. {
  6.   int k = 1, d = 1;
  7.   for (k = 1; k <= a && k <= b; k++)
  8.     if (a % k == 0 && b % k == 0)
  9.       d = k;
  10.   return d;
  11. }
  13. int main()
  14. {
  15.     printf("Lancement du programme\n" );
  16.     int p=35422;
  17.     printf("p=%d\n", p);
  18.     int q=38877;
  19.     printf("q=%d\n", q);
  20.     int n=p*q;
  21.     printf("n=%d\n", n);
  22.     int f=(p-1)*(q-1);
  23.     printf("f=%d\n", f);
  24.     int i=0;
  25.     int PGCD1=0;
  26.     int e=0;
  27.     if(p>q)
  28.     {
  29.         e=p-1;
  30.     }
  31.     else
  32.     {
  33.         e=q-1;
  34.     }
  35.     while(PGCD1 != 1)
  36.     {
  37.         while(i==0)
  38.             if(p<e && q<e && e<f)
  39.             {
  40.                 i=1;
  41.             }
  42.             else
  43.             {
  44.                 e++;
  45.             }
  46.         PGCD1 = pgcd(e, f);
  47.         if(PGCD1!=1)
  48.         {
  49.             e++;
  50.         }
  51.     }
  52.     printf("e=%d\n", e);
  53.     int d=0;
  54.     i=0;
  55.     if(p>q)
  56.     {
  57.         d=p-1;
  58.     }
  59.     else
  60.     {
  61.         d=q-1;
  62.     }
  63.     while(i==0&&d<f)
  64.     {
  65.         if(e*d%f==1 && p<d && q<d && d<f)
  66.         {
  68.             i=1;
  69.         }
  70.         else
  71.         {
  72.             d++;
  73.         }
  74.     }
  75.     if(i==1)
  76.     {
  77.         d=d-1;
  78.         printf("d=%d", d);
  79.     }
  80.     else
  81.     {
  82.         printf("Impossible de definir une cle privee" );
  83.     }
  84.     return 0;
  85. }


 
En lançant ce programme tout ce passe bien et la console affiche:

Code :
  1. Lancement du programme
  2. p=35422
  3. q=38877
  4. n=1377101094
  5. f=1377026796
  6. e=38879
  7. d=596684466


 
Si par contre à la ligne 16 je remplace la valeur de p par "35422" la console affiche

Code :
  1. Lancement du programme
  2. p=35472
  3. q=38877
  4. n=1379044944
  5. f=1378970596
  6. e=38879
  7. Impossible de definir une cle privee


 
Cela vient t'il d'une erreur dans mon code?
Est-ce un problème connu et y a t'il une méthode simple pour l'éviter?
Ou dois-je redéfinir p chaque fois qu'aucune clé privée ne peux être générée?
 
Merci d'avance pour vos réponses
 
Nico-teeN

Reply

Marsh Posté le 18-01-2010 à 17:04:21   

Reply

Marsh Posté le 19-01-2010 à 11:58:20    

On m'a signalé sur un autre forum que p et q devaient être des nombres premiers, le problème à donc été résolu par l'ajout des fonctions suivantes

Code :
  1. int test_nombre_premier(int a)
  2. {
  3.   int i;
  4.   int compter;
  5.   int test;
  6.   test = compter = 0;
  7.   for (i = 2; i < a; i++, compter++)
  8.     if (a % i == 0)
  9.       test = 1;
  10.   if (!test)
  11.     return 1;
  12.   else
  13.     return 0;
  14. }
  16. int transfo_premier(int a)
  17. {
  18.     int i=0;
  19.     while(i==0)
  20.     {
  21.         if(test_nombre_premier(a))
  22.             i=1;
  23.         else
  24.             a++;
  25.     }
  26.     return a;
  27. }


 
ainsi que des lignes

Code :
  1. p=transfo_premier(p);
  2. et
  3.     q=transfo_premier(q);


Juste après la définition de p et q
 
Merci toute fois à ceux qui ont lu ce message dans l'espoir de m'apporter leur aide :)
 
Reste le problème du calcul de d, qui est déjà affreusement long et le sera bien trop lorsque j'utiliserais de grand chiffres
 
Si quelqu'un à une idée pour calculer d sachant e*d%n=1 et p,q<d<f je suis preneur car la je suis un peu paumé
 
Edit: Second problème résolu grace à l'algorithme d'euclide étendu


Message édité par Nico-teeN le 19-01-2010 à 20:01:27
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed