進行模冪運算的高效函式/算法/方法

我正在做這個項目，我需要一個 RSA 密鑰，我想知道是否有更有效的方法 $ g^a \bmod n $ 除了計算 $ g^a $ 然後在除法時找到餘數？

在密碼學中，效率是不夠的。您還需要安全計算。考慮 Python 中的標準重複平方實現；

def fast_power(base, power):
   result = 1
   while power > 0:
       # If power is odd
       if power % 2 == 1:
           result = (result * base) % MOD

       # Divide the power by 2
       power = power // 2
       # Multiply base to itself
       base = (base * base) % MOD

   return result

條件是側通道攻擊的if攻擊點。可以測量功率使用並確定指數位。下圖或類似的研究圖像可以顯示攻擊的想法。

如果您使用 RSA 簽名，則可以顯示您的私人指數。平方可以比乘法更快地實現，在這種情況下，它也可以被利用。因此，您需要恆定的時間來防止這種情況發生。python庫包含pow(a,e,n)基於重複平方的冪模，它不安全。以下版本的重複平方方法總是計算(result * base) % MOD並在不需要時丟棄它。這可能有助於減輕攻擊，但是，如果有足夠解析度的儀器，這仍然可以被追踪。此外，在編譯期間，請確保編譯器不會刪除此緩解措施。預設情況下，像 Cray 的編譯器CC可以丟棄未使用的計算作為優化。下面的算法給出了一個名稱為square 並且總是相乘算法。

def constant_time_power(base, power):
   result = 1
   while power > 0:
       # else to prevent leak
       if power % 2 == 1:
           result = (result * base) % MOD
       else:
           result_temp = (result * base) % MOD //will be discarded.

       # Divide the power by 2
       power = power // 2
       # Multiply base to itself
       base = (base * base) % MOD

   return result

正如上面提到的程式碼，由於程式碼包含未使用的程式碼，因此可以通過帶有死程式碼消除技術的編譯器來優化上述程式碼。一些編譯器具有禁用本地優化的編譯指示指令。可以使用恆定時間條件副本，而不是依賴編譯器指令及其錯誤、更改等。下面顯示了這一點；

def constant_time_power_with_conditional_copy(base, power):
   result = 1
   while power > 0:
       # constant-time conditional copy
       sBit = power%2==1        
       result = ((result * base) % MOD)*sBit+(1-sBit)*result

       # Divide the power by 2
       power = power // 2
       # Multiply base to itself
       base = (base * base) % MOD

   return result

---

著名的GMP 庫mpn_sec_powm有其標準的安全版本mpn_powm。

該函式被設計為對任何兩個相同大小的參數都採用相同的時間並具有相同的記憶體訪問模式，假設函式參數放置在相同的位置並且在函式進入時機器狀態相同。此功能旨在用於加密目的，其中需要對側通道攻擊的彈性。

還有其他模乘法，例如 Barret 或 Montgomery。他們也有恆定時間的實現。例如基於蒙哥馬利

• 2009 年Gopal 等人的模冪運算的快速和恆定時間實現。

引用自：https://crypto.stackexchange.com/questions/75408