RSA密码系统的Montgomery模块化乘法的最终减法 [英] Final subtraction in montgomery modular multiplication for an RSA cryptosystem
问题描述
我对应该如何绕过 radix- 2蒙哥马利模数乘法，用于模幂运算.以下两篇论文提出了绕开减法运算的条件.
I'm confused about how one might supposedly bypass the final subtraction of the modulus in radix-2 montgomery modular multiplication, when used in a modular exponentiation algorithm. The following two papers put forward the conditions for bypassing the subtraction.
- Montgomery Exponentiation with no Final Subtractions: Improved Results
- Montgomery Multiplication Needs no Final Subtractions
我不完全了解预处理和后处理"的要求，以消除在蒙哥马利乘法结束时重复减去模数的需求.
在阅读了以上论文后，我的理解是，要消除最终的减法，您必须:
My understanding after reading the above papers is that, to eliminate the final subtractions, you must:
-
将每个输入操作数零扩展为两个模幂
Zero-extend each input operand to the modular exponentiation by two
e.g. new[2049 downto 0] = (0, 0, old[2047 downto 0])
我已经对可运行的算法进行了这些修改，但是结果不符合我的预期，我也不明白为什么. 因此，我认为我在误解这些论文中的内容，或者遗漏了关键步骤.
I've made these modifications to a working algorithm, however the results are not as I expect and I do not understand why. Therefore, I assume I am misinterpreting something in these papers, or leaving out a critical step.
让我们在(类似C的伪代码)中引用我的(工作的)基2蒙哥马利模幂函数.请注意，我将操作数宽度扩展了两个最高有效的零数字(只是为了确保我没有溢出).它们曾经只有2048位.
Let us refer to my (working) radix-2 montgomery modular exponentiation function in (C-like pseudocode). Note that I have extended the operand width by two most-significant zero digits (just to make sure I'm not overflowing). They used to only be 2048 bits.
let NUM_BITS = 2048
let rsaSize_t be a 2050-bit vector type
// Montgomery multiplication: outData = XYr^(-1) modulo M,
// where the radix r=2^n (n=NUM_BITS)
function montMult( rsaSize_t X, // Multiplier
rsaSize_t Y, // Multiplicand
rsaSize_t M, // Modulus
rsaSize_t outData) // Result
{
rsaSize_t S = 0; // Running sum
for (i=0; i<NUM_BITS; i++)
{
if (X.bit(i)==1) // Check ith bit of X
S += Y;
if (S.bit(0)==1) // check LSB of S
S += M;
S = S >> 1; // Rightshift 1 bit
}
// HERE IS THE FINAL SUBTRACTION I WANT (NEED) TO AVOID
if (S >= M)
{
S -= M;
}
outData = S.range(NUM_BITS-1,0);
}
// montgomery modular exponentiation using square and multiply algorithm
// computes M^e modulo n, where we precompute the transformation of the
// base and running-partial sum into the montgomery domain
function rsaModExp( rsaSize_t e, // exponent
rsaSize_t n, // modulus
rsaSize_t Mbar, // precomputed: montgomery residue of the base w.r.t. the radix--> (2^2048)*base mod n
rsaSize_t xbar, // precomputed: montgomery residue of 1 w.r.t. the radix--> 2^2048 mod n
rsaSize_t *out) // result
{
for (i=NUM_BITS-1; i>=0; i--)
{
montMult(xbar, xbar, n, xbar); // square
if (e.bit(i)==1)
montMult(Mbar, xbar, n, xbar); // multiply
}
// undo montgomery transform
montMult(xbar, 1, n, out);
}
我在报纸上缺少什么吗?我不认为这是一个实现错误，因为我的代码与论文中提出的完全匹配.我认为我可能是一个概念上的错误.任何和所有帮助表示赞赏.
Am I missing something in the papers? I do not believe this is an implementation error, as my code matches exactly what is put forth in the papers. I believe that I might be a conceptual error. Any and all help appreciated.
谢谢！
推荐答案
不确定不确定的实现有什么问题(如果我理解得很好，您所展示的是可行的).为了使用Walter优化来计算M^e mod n，如果您的数字都适合2048位，则需要:
Not sure what's wrong with your non-working implementation (if I understood well, what you show is a working one). In order to use the Walter optimization to compute M^e mod n, if your numbers all fit in 2048 bits, you need:
let NUM_BITS = 2050 // 2048 + 2
n < 2^(NUM_BITS - 2) // precondition
M < 2 * n // precondition
let R = 2^(2 * NUM_BITS) mod n // pre-computed once for all
let M' = montMult(M, R, n) // bring M in Montgomery form
let C' = montExp(M', e, n) // Montgomery exponentiation
let C = montMult(C', 1, n) // bring C' in normal form
最重要:请不要忘记检查前提条件.
Most important: do not forget to check the preconditions.
蒙哥马利乘法包括NUM_BITS(在您的情况下为2050)迭代(if-A-bit-set-add-B，if-odd-add-n，div-by-2)，最低有效位优先，并且所有数字都用NUM_BITS(在您的情况下为2050)位表示.
The Montgomery multiplications comprise NUM_BITS (2050 in your case) iterations (if-A-bit-set-add-B, if-odd-add-n, div-by-two), least significant bit first, and all numbers are represented on NUM_BITS (2050 in your case) bits.
蒙哥马利的幂运算还包括NUM_BITS(在您的情况下为2050)迭代(平方，if-e-bit-set-mult)，最高有效位在前，并且所有数字均表示在NUM_BITS(在您的情况下为2050)大小写)位.希望对您有所帮助.
The Montgomery exponentiation also comprises NUM_BITS (2050 in your case) iterations (square, if-e-bit-set-mult), most significant bit first, and all numbers are represented on NUM_BITS (2050 in your case) bits. Hope it helps.
这篇关于RSA密码系统的Montgomery模块化乘法的最终减法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
