计算pow（a，b）mod n
我想计算一个用于RSA解密的b mod n。 我的代码（如下）返回错误的答案。 这有什么问题？
unsigned long int decrypt2(int a,int b,int n) { unsigned long int res = 1; for (int i = 0; i < (b / 2); i++) { res *= ((a * a) % n); res %= n; } if (b % n == 1) res *=a; res %=n; return res; } 您可以尝试这个C ++代码。 我用它有32位和64位整数。 我相信我是从SO那里得到的。
template T modpow(T base, T exp, T modulus) { base %= modulus; T result = 1; while (exp > 0) { if (exp & 1) result = (result * base) % modulus; base = (base * base) % modulus; exp >>= 1; } return result; }
您可以在文献中找到此算法和相关讨论。 244的
Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.). Wiley. ISBN 978-0-471-11709-4.
为了计算用于RSA解密的pow(a,b) % n ，我遇到的最佳算法是Primality Testing 1） ，如下所示：
int modulo(int a, int b, int n){ long long x=1, y=a; while (b > 0) { if (b%2 == 1) { x = (x*y) % n; // multiplying with base } y = (y*y) % n; // squaring the base b /= 2; } return x % n; }
有关详细信息，请参阅以下参考
1） Primality测试：非确定性算法 – topcoder
通常它是这样的：
while (b) { if (b % 2) { res = (res * a) % n; } a = (a * a) % n; b /= 2; } return res;
我看到的唯一实际逻辑错误是这一行：
if (b % n == 1)
这应该是这样的：
if (b % 2 == 1)
但是你的整体设计是有问题的：你的函数执行O（b）乘法和模数运算，但你使用b / 2和a * a意味着你的目标是执行O（log b）运算（这通常是模幂运算的方式）已经完成了）。
执行原始电源操作非常昂贵，因此您可以应用以下逻辑来简化解密。
从这里开始 ，
现在说我们要加密消息m = 7，
c = m ^ e mod n = 7 ^ 3 mod 33 = 343 mod 33 = 13。
因此密文c = 13。要检查我们计算的解密
m’= c ^ d mod n = 13 ^ 7 mod 33 = 7。
请注意，我们不必在此处计算功率7的全部值13。 我们可以利用这个事实
a = bc mod n =（b mod n）。（c mod n）mod n
所以我们可以将一个可能很大的数字分解成它的组件，并结合更简单，更小的计算结果来计算最终值。计算m’的一种方法如下： –
请注意，任何数字都可以表示为2的幂之和。因此，首先要计算的值
13 ^ 2,13 ^ 4,13 ^ 8，…通过重复对模33的连续值求平方.13 ^ 2 =169≡4,13^ 4 = 4.4 = 16,13 ^ 8 = 16.16 =256≡25。
然后，由于7 = 4 + 2 + 1，我们得到m’= 13 ^ 7 = 13 ^（4 + 2 + 1）= 13 ^ 4.13 ^ 2.13 ^ 1
≡16x 4 x 13 =832≡7mod 33
你想计算(a^b)%n ，还是a^(b%n) ？
如果你想要第一个，那么你的代码只有在b是偶数时才有效，因为那个b / 2 。 “ if b%n==1 ”是不正确的，因为你不关心这里的b%n ，而是关于b%2 。
如果你想要第二个，那么循环是错误的，因为你循环b / 2次而不是（b％n）/ 2次。
无论哪种方式，您的function都不必要地复杂。 你为什么要循环到b / 2并尝试每次乘以2 a？ 为什么不直接循环直到b和多次在每一次。 这将消除许多不必要的复杂性，从而消除潜在的错误。 您是否认为通过将循环次数减半来使程序更快？ 坦率地说，这是一个糟糕的编程实践：微优化。 它并没有多大帮助：你仍然乘以相同的次数，你所做的就是减少测试循环的次数。 如果b通常较小（如一个或两个数字），那就不值得了。 如果b很大 – 如果它可能是数百万 – 那么这是不够的，你需要一个更激进的优化。
另外，为什么%n每次都通过循环？ 为什么不在最后做一次呢？
对于RSA， int通常是不够的（除非你正在处理小的简化示例）
你需要一个数据类型，可以存储高达2 256 （对于256位RSA密钥）或2 512对于512位密钥等的整数
我认为你有两个问题。 一，你只是在结束时检查一个奇数指数，而不是每次都通过循环; 二，你对奇数指数的检查是错误的。
这是一个递归版本，适用于我在网上找到的几个例子。
unsigned long int decrypt2(int a,int b,int n) { unsigned long int res; if (b == 0) { res = 1; } else if (b % 2 == 1) { res = a * decrypt2( a, b-1, n ); } else { res = decrypt2( a, b/2, n ); res = (res*res)%n; }
使用快速取幂可能…..给出与上面的模板相同的o（log n）
int power(int base, int exp,int mod) { if(exp == 0) return 1; int p=power(base, exp/2,mod); p=(p*p)% mod; return (exp%2 == 0)?p:(base * p)%mod; }
计算pow（a，b）mod n
-
OP代码的一个关键问题是
a * a。 当a足够大时，这是int溢出（未定义的行为）。res的类型与a * a的乘法无关。解决方案是确保：
1）乘法用2x宽数学或
2） 模数n，n*n <= type_MAX + 1 -
没有理由返回比模数类型更宽的类型，因为结果总是由该类型表示。
// unsigned long int decrypt2(int a,int b,int n) int decrypt2(int a,int b,int n) -
使用无符号数学肯定更适合OP的RSA目标。
// (a^b)%n // n != 0 // Test if unsigned long long at least 2x values bits as unsigned #if ULLONG_MAX/UINT_MAX - 1 > UINT_MAX unsigned decrypt2(unsigned a, unsigned b, unsigned n) { unsigned long long result = 1u % n; // Insure result < n, even when n==1 while (b > 0) { if (b & 1) result = (result * a) % n; a = (1ULL * a * a) %n; b >>= 1; } return (unsigned) result; } #else unsigned decrypt2(unsigned a, unsigned b, unsigned n) { // Detect if UINT_MAX + 1 < n*n if (UINT_MAX/n < n-1) { return TBD_code_with_wider_math(a,b,n); } a %= n; unsigned result = 1u % n; while (b > 0) { if (b & 1) result = (result * a) % n; a = (a * a) % n; b >>= 1; } return result; } #endif
#include ... static_cast(std::pow(a,b))%n
但我最好的选择是你溢出int（IE：数字是两个大的int）在功率上我有同样的问题创建完全相同的function。
我正在使用这个function：
int CalculateMod(int base, int exp ,int mod){ int result; result = (int) pow(base,exp); result = result % mod; return result; }
我解析变量结果因为pow给你一个double，而对于使用mod你需要两个int类型的变量，无论如何，在RSA解密中，你应该只使用整数。