fonction pow et int long causant des problèmes

J’essaie d’implémenter le schéma de chiffrement RSA. Ca fait plutot comme ca:

encrypted data = ((message)^e) % n et decrypted data = ((encrypted data)^d) % n

J’ai essayé de mettre cela en œuvre dans c. Voici le code:

 #include  #include  #include  int main(){ long int num = 3255859; long int encrypt =(int)pow((double) num,3) % 33; printf("%ld\n",encrypt); return 0; } 

J’ai compilé ceci en utilisant gcc -Werror -g -o encrypt encrypt.c -lm

C’est la sortie que j’obtiens = -2 , ce qui est évidemment faux. Lorsque j’essaie ce code pour des nombres plus petits, j’obtiens le bon résultat. Par exemple:

quand je règle num = 2 , j’obtiens le bon résultat qui est 8

Je sais que je suis en train de taper mal ou que je suis à court de limites quelque part. J’ai besoin d’utiliser ce code pour chiffrer de grands nombres comme celui du code ci-dessus.

Pourriez-vous s’il vous plaît indiquer où je me trompe.

Merci

MODIFIER:

Ok selon la suggestion de @Micael Oliver, voici le code modifié:

 #include  #include  #include  int main(){ unsigned long long num = 3255859; long long encrypt =(long long)pow((double) num,3) % 33; printf("%llu\n",encrypt); long long decrypt =(long long)pow((double) encrypt,7) % 33; printf("%llu\n",decrypt); return 0; } 

voici la sortie de ce code:

 Notra:Desktop Sukhvir$ gcc -Werror -g -o encrypt encrypt.c -lm Notra:Desktop Sukhvir$ ./encrypt 18446744073709551608 18446744073709551614 

ce qui est évidemment faux car le 2e coup aurait dû être 3255859

Votre code contient un mélange de nombres non signés et signés – vous devriez essayer d’éviter cela lorsque cela est possible. De plus, vous essayez d’utiliser %llu sur une signature longue longue – vous devez utiliser %lld dans ce cas.

Mais il y a un problème plus subtil en jeu ici. Dans cette ligne:

 long long encrypt =(long long)pow((double) num,3) % 33; 

pow renvoie un double , ce qui ne garantit pas toute la précision recherchée. Vous finirez par perdre quelques chiffres si vous jouez trop long long . Malheureusement, C ne fournit pas une bonne alternative pour calculer les exponentielles, vous devrez donc implémenter quelque chose vous-même ou utiliser une bibliothèque (certaines des autres réponses en ont suggéré d’autres).

Si vous souhaitez en implémenter un vous-même, vous trouverez sur Wikipedia un article intéressant sur l’exposition rapide par quadrature: Exponentiation par quadrature

Ils fournissent un pseudo-code qui devrait être évident pour coder en C.

Enfin, en général, votre code sera limité par la taille de long long ou par le type de votre choix. En fin de compte, pour les grands nombres, vous devriez utiliser une autre bibliothèque ou trouver un meilleur algorithme. Dans ce cas, vous calculez une puissance, puis vous prenez un module, ce qui est exactement ce que les algorithmes d’exposition modulaire peuvent accomplir sans devoir traiter avec ces bibliothèques. Vous pouvez trouver un article Wikipedia ici: Exponentiation modulaire

Une suggestion était d’utiliser un autre type de données comme long long:

 3255859^3 == 34514116960466804779 ULLONG_MAX == 18446744073709551615 // this is the minimum guaranteed 

Donc, non signé longtemps peut ne pas fonctionner. En général, changer de type de données a ses limites. Une autre approche plus robuste que vous pouvez envisager consiste à utiliser sans BPF. gmp manuel –

– Vous pouvez également télécharger gmp sur ce site.

extrait de code:

 #include  #include  #include  #include  int main() { mpz_t rop, base, exp, mod; mpz_init2(rop,128); mpz_init2(base,128); mpz_init2(exp,128); mpz_init2(mod,128); mpz_set_ui(base, 3255859); mpz_set_ui(exp, 3); mpz_set_ui(mod, 33); mpz_powm_sec (rop, base, exp, mod); gmp_printf ("result %Zd\n", rop); return 0; } 

Tant que vos nombres sont au maximum deux fois plus petits que le type dans lequel vous travaillez, vous pouvez faire quelque chose comme ceci:

 (((num * num) % 33) * num) % 33 

En général, pour tout ce qui est pratique à des fins cryptographiques, vous aurez besoin de valeurs beaucoup plus grandes et d’un framework informatique pour travailler avec des nombres à 1024 bits ou plus. Pour cela, vous pouvez utiliser le code existant (je recommanderais libtommath de libtomcrypt , certainement pas GMP) ou écrivez le vôtre.