pow函数和long int导致问题

我试图恭维RSA加密方案。 它是这样的:

encrypted data = ((message)^e) % ndecrypted data = ((encrypted data)^d) % n

我试图在c中实现这一点。 这是代码:

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

我使用gcc -Werror -g -o encrypt encrypt.c -lm编译了这个

这是我得到的输出= -2 ,这显然是错误的。 当我尝试使用较小数字的代码时,我得到了正确的结果。 例如:

当我设置num = 2 ,我得到的结果是8

我知道我要么输入错误,要么我在某个地方跑出界限。 我确实需要使用此代码来加密像上面代码中的大数字一样的大数字。

你能指出我出错的地方吗?

谢谢

编辑:

好的,根据@Micael Oliver的建议,这里是修改后的代码:

 #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; } 

这是这段代码的输出:

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

这显然是错误的,因为第二次出局应该是3255859

你的代码中有一些未签名和有符号数字的混合 – 你应该尽可能避免这种情况。 此外,您尝试在签名的长%llu上使用%llu – 在这种情况下您应该使用%lld

但是这里有一个更微妙的问题。 在这一行:

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

pow返回一个double ,这不能保证你所需要的所有精度。 当你施展long long时,你最终会失去几位数。 不幸的是,C不能为计算指数提供一个很好的选择,所以你需要自己实现一些东西或者使用一个库(其他一些答案已经提出了一些建议)。

如果你想自己实现一个,可以在维基百科上找到一篇关于通过平方快速求幂的好文章: 通过平方的指数

它们提供了一些伪代码,这些伪代码在C中编码时应该很明显。

但最后,一般来说,您的代码将受到long long的大小或您选择的任何类型的限制。 最终对于大数字,您应该使用其他库,或找到更好的算法。 在这种情况下,您正在计算功率然后采用模数 – 这正是模块化指数算法无需处理这些库即可实现的function。 你可以在这里找到一篇维基百科文章: Modular Exponentiation

一个建议是使用另一种数据类型,如long long:

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

所以,unsigned long long可能无效。 通常,更改数据类型有限制。 您可以考虑的另一个更强大的方法是使用GMP – 免费。 gmp手册 –

– 你也可以在这个网站下载gmp。

代码段:

 #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; } 

只要您的数字最多只是您工作类型的一半,您就可以执行以下操作:

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

通常,对于任何可用于加密目的的东西,您需要更大的值和计算框架才能使用1024+位数。 为此您可以使用现有代码(我建议libtommathlibtomcrypt ,绝对不是 GMP)或自己编写代码。