Algorothme RSA utilisant des float

azalee -  
fiddy Messages postés 11069 Date d'inscription   Statut Contributeur Dernière intervention   -
Bonjour,

J'ai essayé d'écrire un algorithme de cryptage (RSA). Le code à bien marché avec des int. J'ai changé les int par des float. Au moment du décryptage la console m'affiche un zéro. Le problème se trouve au niveau de la ligne suivnte : "*M=fmod((*M*C),n);"

Voici mon code :


#include<stdio.h>
#include<conio.h>
#include<math.h>


float pgcd(float x, float y)
{
float r;

while(y!=0)
{
r=fmod(x,y);
x=y;
y=r;
}

return x;

}

int check_prime_number(float x)
{
float sqrt_n;
int i;

if (!fmod(x,2)) return 0;

sqrt_n = sqrt(x);

for (i = 3; i <= sqrt_n; i+=2) {
if (!fmod(x,i)) return 0;
}
return 1;
}

int check_e(float PHI,float e,float p,float q)
{

if((pgcd(PHI,e)==1)&&(e<PHI)&&(e!=p)&&(e!=q))
return 1;
else return 0;
}

float find_d(float PHI, float E)
{
float d=1;

while(fmod((E*d),PHI)!=1)
{
d++;
}


return d;
}

void encrypt(float M, float *C, float e, float n)
{
int i;
*C = 1;
for(i=0;i<e;i++)
*C=fmod((*C*M),n);
*C = fmod(*C,n);

}


void decrypt(float C, float *M, float d, float n)
{
int i;
*M = 1;
for(i=0;i<d;i++)
{
*M=fmod((*M*C),n);
}
*M = fmod(*M,n);

}


void main()
{
float M,c,f,p,q,n,phi,e,d;

do
{
printf("\nDonner p (naturel premier) : ");
scanf("%f",&p);
}while(check_prime_number(p)==0);

do
{
printf("\nDonner q (naturel premier) superieur a %.0f: ",p);
scanf("%f",&q);
}while((check_prime_number(q)==0)||(q<=p));


printf("\nEnter votre cle : ");
scanf("%f",&M);

n = p*q;
phi=(p-1)*(q-1);

do
{

printf("\nDonner e (phi = %.0f ): ",phi);
scanf("%f",&e);

}while(check_e(phi,e,p,q)==0);

encrypt(M,&c,e,n);

printf("\nCle cryptee : %.0f",c);

printf("\n\nEntrer la cle cryptee : ");
scanf("%d",&c);

d=find_d(phi,e);

decrypt(c,&f,d,n);
printf("\nCle decryptee : %.0f",f);
getch();
}


Merci d'avance

4 réponses

fiddy Messages postés 11069 Date d'inscription   Statut Contributeur Dernière intervention   1 846
 
Salut,
Faire du RSA avec des float ?? Quelle idée saugrenue. ^^.
Sinon, l'erreur doit se localiser ici : scanf("%d",&c);
c est un float. Il faut donc utiliser : scanf("%f",&c);
Cdlt
0
douss4 Messages postés 25 Date d'inscription   Statut Membre Dernière intervention  
 
Merci c'est réglé, faute d'inattention. En fait, j'ai utilisé des floats juste pour le format des clé. Si je dois utiliser des clé de 64 bits donc j suis obligée d'utiliser des floats (je vais utiliser DES pour les messages). Mais le problème maintenant c'est que le code ne marche pas pour des nombre de grande taille il plante au niveau du décryptage.
exemple :

J'ai mis p=7, q=17, e=5 et la clé =19 j'ai eu un résultat correcte
Ensuite j'ai mis p=47207 q=49999 e=5 et la clé=476545437 Il plante au niveau du décryptage. J'ai utilisé également p=7, q=17, e=5 mais avec une clé =476545437 j'ai eu le même problème.

Cela ne serait pas par hasard un problème au niveau du Borland C++?
0
fiddy Messages postés 11069 Date d'inscription   Statut Contributeur Dernière intervention   1 846
 
Déjà, la règle est simple. Si tu veux faire du chiffrement, oublie les nombres flottants.
Ensuite, pour les int, tu peux essayer les unsigned long long.
De plus, pour éviter de dépasser la capacité des entiers, tu peux améliorer assez facilement le calcul de l'exponentiation modulaire : https://fr.wikipedia.org/wiki/Exponentiation_modulaire
Et enfin, pour travailler avec les grands nombres, il te faudra te construire un type le permettant. Ou utiliser une bibliothèque le permettant, comme celle d'openssl avec son type BIGNUM.
0
douss4 Messages postés 25 Date d'inscription   Statut Membre Dernière intervention  
 
Ah.. tout cela je connait pas... merci pour la réponse, je vais essayer de me documenter.
0
douss4 Messages postés 25 Date d'inscription   Statut Membre Dernière intervention  
 
Désolée de répondre deux fois, mais je pense que pour une clé de 64 bits je ne peux pas utiliser le type unsigned long int. Une clé de 64 bits donne une nombre maximale égale à 2 puissance 64 (d'après ce que j'ai compris). mais le type unsigned long int donne au maximum le nombre 4 294 967 295. Je ne peux pas utiliser DES avec une si petite clé.
0
fiddy Messages postés 11069 Date d'inscription   Statut Contributeur Dernière intervention   1 846
 
Oui, mais je n'ai pas dit d'utiliser long, mais d'utiliser long long ;-)).
Mais quoiqu'il en soit, il va y avoir du dépassement de capacité, d'où l'intérêt d'utiliser une bibliothèque gérant les grands nombres.
0
douss4 > fiddy Messages postés 11069 Date d'inscription   Statut Contributeur Dernière intervention  
 
bonjour,

J'ai trouvé cette bibliothèque bignum.h : http://webscripts.softpedia.com/script/Snippets/Bignum-H-26680.html


Ce cette bibliothèque la qui me permet d'utiliser le unsigned long long ?
0
fiddy Messages postés 11069 Date d'inscription   Statut Contributeur Dernière intervention   1 846 > douss4
 
unsigned long long est un type natif apparu avec la nouvelle norme du C (C99). Donc tu n'as nullement besoin de bibliothèques pour ça. Par contre, avec celle que tu télécharges, tu devrais pouvoir utiliser BigNum qui te permettra de calculer de très grands nombres.
0
douss4 > fiddy Messages postés 11069 Date d'inscription   Statut Contributeur Dernière intervention  
 
Donc si je comprends bien, il faut que j'utilise BigNum comme étant une structure de donnée que je dois lui attribuer un nlen et un *n. Ensuite pour faire des opérations sur ces bignums je dois utiliser les foncyions suivantes : BigNumAdd, BigNumSub, BigNumMul, BigNumDiv, etc...
0
fiddy Messages postés 11069 Date d'inscription   Statut Contributeur Dernière intervention   1 846 > douss4
 
Exactement ;-))
0