Algorothme RSA utilisant des float

Fermé
azalee - 2 avril 2009 à 11:16
fiddy Messages postés 11069 Date d'inscription samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 - 6 avril 2009 à 17:18
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 samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 844
2 avril 2009 à 12:19
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 jeudi 2 avril 2009 Statut Membre Dernière intervention 23 mars 2010
2 avril 2009 à 12:40
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 samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 844
2 avril 2009 à 12:49
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 jeudi 2 avril 2009 Statut Membre Dernière intervention 23 mars 2010
2 avril 2009 à 12:54
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 jeudi 2 avril 2009 Statut Membre Dernière intervention 23 mars 2010
2 avril 2009 à 13:06
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 samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 844
2 avril 2009 à 13:15
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 samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022
6 avril 2009 à 14:40
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 samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 844 > douss4
6 avril 2009 à 15:02
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 samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022
6 avril 2009 à 16:35
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 samedi 5 mai 2007 Statut Contributeur Dernière intervention 23 avril 2022 1 844 > douss4
6 avril 2009 à 17:18
Exactement ;-))
0

Discussions similaires