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

Question

Как работает умножение Монтгомери в ускорении процесса шифрования для вычисления c = m^e% n, используемого при шифровании RSA? Я понимаю, что умножение Монтгомери может эффективно умножать * 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)

Преобразование в форму montgomery до умножения и повторного умножения m * m в цикле for , возвращаясь к нормальному миру в конце шага. Мне любопытно узнать, есть ли другой способ вычислить операцию 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-шифрование работает с оптимизацией умножения montgomery?

Answer 1

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

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

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

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

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