RSA中的蒙哥馬利乘法：c = m^e％n

蒙哥馬利乘法是如何在RSA加密中使用加速計算c = m^e％n的加密過程的？我知道蒙哥馬利乘法可以有效地乘a * b％n，但是當試圖找到m^e％n時，是否有比乘以m * me次數更有效的方法，而不是每次循環和計算蒙哥馬利乘法？RSA中的蒙哥馬利乘法：c = m^e％n

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加密如何與蒙哥馬利乘法優化一起工作嗎？

來源

2016-03-03 drewtu2

不，你不想用m自己乘e來計算RSA。

您通常要通過重複平方（有其他可能性，但這是一個簡單的適用於許多典型目的）的方法來執行mod n。

在previous post on RSA中，我包含一個使用pow_mod函數的實現。這反過來又使用了一個mul_mod函數。蒙哥馬利乘法（基本上）是該函數的一個實現，它更適合於處理大量數據。然而，爲了使它有用，您至少需要一些至少按照pow_mod函數的一般順序進行的操作，而不僅僅是使e調用mul_mod的循環。考慮到實際使用RSA所涉及的數量的大小，嘗試計算僅使用重複乘法的mod n可能需要幾年（很可能相當幾年）才能完成單個加密。換句話說，一個不同的算法不僅僅是一個很好的優化 - 它是絕對必要的使用，實際上。使用簡單乘法提高A ^B基本上是O（B）。用它在那裏顯示的重複平方算法來做，它基本上是O（log B）。如果B非常大，兩者之間的差異是巨大的。

來源

2016-03-03 01:59:47

RSA中的蒙哥馬利乘法：c = m^e％n

回答

相關問題