计算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解密中,你应该只使用整数。