我正在尝试为 RSA 加密系统编写解密函数,对于非常小的数字,一切似乎都工作正常,但有时输出不正确(我认为原因可能是浮点错误或某种堆栈溢出)。
导致我出现问题的过程可以简化为 (11^23) mod 187,但我将包含完整代码以防有人想看。我知道答案应该是 88,因为它是 Simon Singh 博士在“The Code Book”的附录 J 中使用的示例(我还使用 Wolfram Alpha 进行了检查)。然而,我得到了 149 的结果。然而,对于较小的数字,它与 Wolfram Alpha 一致。
我的想法是我需要使用以下知识来简化模幂运算:
a^b = a^c * a^d [ 其中 c + d = b ]
但是,我仍然不能 100% 确定这是否是这个问题,这是我的第一个堆栈溢出吗? (我仍然不是 100% 确定这意味着什么)。在有人问我之前,不,这不是任何类型的家庭作业,如果这个问题看起来微不足道,我很抱歉。如果每个人都认为这太难做到,我愿意使用 gmp.h,但如果我完全诚实的话,我宁愿不使用。我的代码在下面(前半部分是计算私钥,我认为这与我遇到的问题无关,但我已经包含它以防万一我错了),我真的希望你们能帮忙,谢谢你非常提前。
#include <iostream>
#include <math.h>
using namespace std;
unsigned int modinv(unsigned int u, unsigned int v)
{
unsigned int inv, u1, u3, v1, v3, t1, t3, q;
int iter;
u1 = 1;
u3 = u;
v1 = 0;
v3 = v;
iter = 1;
while (v3 != 0)
{
q = u3 / v3;
t3 = u3 % v3;
t1 = u1 + q * v1;
u1 = v1; v1 = t1; u3 = v3; v3 = t3;
iter = -iter;
}
if (u3 != 1)
return 0;
if (iter < 0)
inv = v - u1;
else
inv = u1;
return inv;
}
int main()
{ long unsigned int p = 17;
long unsigned int q = 11;
long unsigned int phi = (p-1)*(q-1);
long unsigned int e = 7;
long unsigned int c = 11;
long unsigned int n = p*q;
long unsigned int d = modinv (e,phi);
{
cout << fmod (pow (c, d), n);
}
return 0;
}
最佳答案
11^23 大约等于 2^80。只有 2^53 以内的整数才能精确表示为 double float 。因此 fmod(pow(c, d), n)) 返回一个近似值。这不适用于密码学。
已添加您可以使用重复平方进行模幂运算。查看维基百科关于“通过平方求幂”的文章
关于c++ - 简化模幂 C++,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22054657/