問題描述
我想計(jì)算 ab mod n 以用于 RSA 解密.我的代碼(如下)返回不正確的答案.有什么問題嗎?
I want to calculate ab mod n for use in RSA decryption. My code (below) returns incorrect answers. What is wrong with it?
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;
}
推薦答案
你可以試試這個(gè) C++ 代碼.我已經(jīng)將它用于 32 位和 64 位整數(shù).我確定我是從 SO 那里得到的.
You can try this C++ code. I've used it with 32 and 64-bit integers. I'm sure I got this from SO.
template <typename T>
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;
}
你可以在 p. 的文獻(xiàn)中找到這個(gè)算法和相關(guān)的討論.244 的
You can find this algorithm and related discussion in the literature on p. 244 of
施奈爾，布魯斯 (1996).應(yīng)用密碼學(xué):C 語(yǔ)言中的協(xié)議、算法和源代碼，第二版(第 2 版).威利.ISBN 978-0-471-11709-4.
Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.). Wiley. ISBN 978-0-471-11709-4.
<小時(shí)>
請(qǐng)注意，在此簡(jiǎn)化版本中，乘法 result * base 和 base * base 可能會(huì)溢出.如果模數(shù)大于 T 寬度的一半(即大于最大 T 值的平方根)，則應(yīng)改用合適的模乘算法 -請(qǐng)參閱使用原始類型進(jìn)行模乘的方法的答案.
Note that the multiplications result * base and base * base are subject to overflow in this simplified version. If the modulus is more than half the width of T (i.e. more than the square root of the maximum T value), then one should use a suitable modular multiplication algorithm instead - see the answers to Ways to do modulo multiplication with primitive types.
這篇關(guān)于計(jì)算 pow(a,b) mod n的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！