Окончательное вычитание в модульном умножении Монтгомери для криптосистемы RSA

Question

Я запутался в том, как можно предположительно обойти окончательное вычитание модуля в модульном умножении Монтгомери с основанием радикса-2 при использовании в модульном алгоритме возведения в степень. Следующие две статьи выдвигают условия для обхода вычитания.

• Экспонирование Монтгомери без окончательных вычитаний: улучшенные результаты
• Умножение Монтгомери не нуждается в окончательных вычитаниях

Я не совсем понимаю, что требуется с точки зрения "предварительной обработки и постобработки", чтобы исключить необходимость повторного вычитания модуля в конце умножения Монтгомери.

Насколько я понимаю после прочтения вышеупомянутых работ, для устранения окончательных вычитаний вы должны:

1. Расширение нуля каждого входного операнда до модульного возведения в степень на два

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

2. Увеличьте границу цикла внутри умножения Монтгомери на два, чтобы выполнить еще две итерации цикла

Я внес эти изменения в работающий алгоритм, однако результаты не такие, как я ожидаю, и я не понимаю, почему. Поэтому я полагаю, что я неправильно истолковываю что-то в этих статьях или упускаю важный шаг.

Давайте обратимся к моей (рабочей) модульной функции возведения в степень radix-2 montgomery в (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);
}

Я что-то упускаю в газетах? Я не верю, что это ошибка реализации, поскольку мой код точно соответствует тому, что изложено в статьях. Я считаю, что я могу быть концептуальной ошибкой. Любая помощь приветствуется.

Спасибо!

Answer 1

Не уверен, что не так с вашей нерабочей реализацией (если я правильно понял, то, что вы показываете, является работающей). Для того, чтобы использовать оптимизацию Вальтера для вычисления 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 в вашем случае) биты. Надеюсь, поможет.