RSA 密码系统蒙哥马利模乘法的最终减法

我对如何绕过模数的最终减法感到困惑radix-2 蒙哥马利模乘法 https://pdfs.semanticscholar.org/cbfd/5f286cf3a54025356cff90cd17ab083fafc1.pdf，当用于模幂算法时。下面两篇论文提出了绕过减法的条件。

• 没有最终结果的蒙哥马利指数 减法：改进结果 https://link.springer.com/content/pdf/10.1007%2F3-540-44499-8_23.pdf
• 蒙哥马利乘法不需要最后的 减法 http://colinandmargaret.co.uk/Research/CDW_ELL_99.pdf

我不完全理解“预处理和后处理”需要什么来消除蒙哥马利乘法末尾重复模数减法的需要。

读完上述论文后我的理解是，要消除最后的减法，你必须：

1. 将每个输入操作数零扩展到模幂乘以 2

   e.g. new[2049 downto 0]  = (0, 0, old[2047 downto 0]) 
   

2. 将蒙哥马利乘法内的循环界限增加两倍，以便再执行两次循环迭代

我已经对工作算法进行了这些修改，但是结果并不像我预期的那样，我不明白为什么。因此，我认为我误解了这些论文中的某些内容，或者遗漏了一个关键步骤。

让我们参考我的（工作中的）radix-2 蒙哥马利模幂函数（类似 C 的伪代码）。请注意，我已将操作数宽度扩展了两个最高有效的零数字（只是为了确保不会溢出）。它们过去只有 2048 位。

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);
}

我在报纸上漏掉了什么吗？我不认为这是一个实现错误，因为我的代码与论文中提出的完全匹配。我相信我可能是一个概念错误。任何和所有的帮助表示赞赏。

Thanks!

不确定您的非工作实施有什么问题（如果我理解得很好，您所展示的是一个工作实施）。为了使用 Walter 优化来计算M^e mod n，如果您的数字都适合 2048 位，您需要：

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

最重要的: 不要忘记检查先决条件。

蒙哥马利乘法包括NUM_BITS（在你的情况下是2050）迭代（if-A-bit-set-add-B，if-odd-add-n，div-by-two），最低有效位在前，所有数字都表示在NUM_BITS（在你的例子中是2050）位。

蒙哥马利求幂还包括NUM_BITS（在你的情况下是2050）迭代（平方，if-e-bit-set-mult），最高有效位在前，所有数字都表示在NUM_BITS（在你的例子中是2050）位。希望能帮助到你。