Умножение Монтгомери в RSA: c=m^e%n

Question

Как работает Montgomery Multiplication в ускорении процесса шифрования для вычисления c=m^e%n, используемого в шифровании RSA? Я понимаю, что умножение Монтгомери может эффективно умножить a * b% n, но при попытке найти m ^ e% n существует ли более эффективный способ умножения m*me количество раз, чем просто циклическое повторение и вычисление умножения Монтгомери каждый раз?

mpz_class mod(mpz_class &m, mpz_class &exp, mpz_class &n) {
        //End goal is to return m^exp%n
//      cout << "Begin mod";
        mpz_class orig_m = m; //the original message
        mpz_class loc_m = m;  //local value of m (to be changed as you cycle through)
        cout << "m: " << m << " exp: " << exp << " n: " << n << endl;

        //Conversion to the montgomery world
        mpz_class mm_xp = (loc_m*r)%n;
        mpz_class mm_yp = (orig_m*r)%n;

        for(int i=0; i < exp-1; i++) //Repeat multiplaction "exp" number of times
        {
                 mm(mm_xp, mm_yp, n); //montgomery multiplication algorithm returns m*orig_m%n but in the montgomery world form
        }

        mm_xp = (mm_xp*r_p)%n; //convert from montgomery world to normal numbers
        return mm_xp;
}

Я использую библиотеки gmp, чтобы я мог работать с большими числами здесь. r и r_p предварительно рассчитываются в отдельной функции и являются глобальными. В этом примере я работаю с полномочиями 10 (хотя я понимаю, что было бы более эффективно работать с полномочиями 2)

Я преобразую в форму Монтгомери до умножения и повторяю умножение m*m в цикле for, возвращая обратно в нормальный мир в конце шага m ^ e. Мне любопытно узнать, есть ли другой способ вычисления операции m ^ e% n другим способом, а не просто циклический переход по циклу for? На данный момент я считаю, что это является узким местом вычислений, однако я вполне могу ошибаться.

фактический шаг умножения Монтгомери происходит в функции ниже.

void mm(mpz_class &ret, const mpz_class &y, const mpz_class &n)
{
        mpz_class a = ret*y;

        while(a%r != 0)
        {
                a += n;
        }
        ret = a/r; //ret*y%n in montgomery form
//      cout << ret << endl;
}

Это вообще, как шифрование RSA работает с оптимизацией умножения Монтгомери?

Answer 1

Нет не хочешь делать e умножения m сам по себе для вычисления RSA.

Обычно вы хотите сделать мод, выполнив повторное возведение в квадрат (есть и другие возможности, но это простая, которая подходит для многих типичных целей).

В предыдущем посте по RSA я включил реализацию, которая использовала pow_mod функция. Что, в свою очередь, использовал mul_mod функция. Умножение Монтгомери является (в основном) реализацией этого mul_mod функция, которая лучше подходит для работы с большими числами. Однако, чтобы сделать это полезным, вам нужно что-то, по крайней мере, в общем порядке pow_mod функция, а не просто цикл, чтобы сделать e звонки в mul_mod,

Учитывая величину чисел, задействованных в реальном использовании RSA, попытка вычислить моду, используя только повторное умножение, вероятно, займет годы (вполне возможно, довольно много лет), чтобы завершить даже одно шифрование. Другими словами, другой алгоритм - это не просто приятная оптимизация - он абсолютно необходим для практического использования.

Чтобы выразить это в алгоритмических терминах, поднятие A ^B с использованием простого умножения в основном равно O(B). Делая это с помощью алгоритма повторного возведения в квадрат, показанного там, это в основном O(log B). Если B очень большой, разница между ними огромна.