Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
2418 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  Calcul d'une clé privée RSA

 
 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Calcul d'une clé privée RSA

n°1958577
Nico-teeN
Posté le 18-01-2010 à 17:04:21  profilanswer
 

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

mood
Publicité
Posté le 18-01-2010 à 17:04:21  profilanswer
 

n°1958718
Nico-teeN
Posté le 19-01-2010 à 11:58:20  profilanswer
 

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

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  Calcul d'une clé privée RSA

 

Sujets relatifs
[ C# ] Librairie de calcul de statistiqueAide sur petit tableau de calcul de prix
[DB2] calcul de pourcentages d'une occurenceCalcul auto montant d'un séjour selon dates choisies
Calcul d'une moyenneCalculs et notes de calcul
[HTML/CSS/Javascript] Calcul coté client avec visualisationFaire un calcul sans rafraichir une page php
[OpenOffice] Calcul de prixCréation d'un générateur d'exercices de calcul mental aléatoire
Plus de sujets relatifs à : Calcul d'une clé privée RSA

Forum MesDiscussions.Net, Version 2010.2
(c) 2000-2011 Doctissimo
Page générée en 0.079 secondes

Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR