將大指數計算分解成更小的計算？
我正在嵌入式平台上實現 SRP。它具有加密加速功能，我正在使用其內置的模冪函式，但是它似乎無法處理超過 32 個字節長的指數。我需要使用一個 64 字節長的指數。
有沒有辦法把這個冪分解成模冪函式可以處理的更小的冪？
一種方法使用因式分解指數：如果 $ a=bc $ 然後 $ x^a \equiv x^{bc}\equiv (x^b)^c \mod m, $ 即首先計算 $ y=x^b\mod m $ 接著 $ y^c \mod m $ .
如果指數的最大因子最多有 32 個字節，則此方法將起作用。
否則，您始終可以使用平方和乘冪方法（請參閱https://en.wikipedia.org/wiki/Modular_exponentiation>或<https://en.wikipedia.org/wiki/Modular_exponentiation或 https://en.wikipedia .org/wiki/Exponentiation_by_squaring）循環遍歷指數的單個位。
有沒有辦法把這個冪分解成模冪函式可以處理的更小的冪？
就在這裡。通常，人們會使用預計算來執行此操作，以在每次迭代中處理多於一位的指數，但它應該很好地適應您的情況。
特別是我建議您使用應用密碼學手冊 ( PDF ) 中的算法 14.82。我將在此處重新說明此算法以適應您的需求。讓 $ e $ 成為你的指數，讓 $ e_0 $ 是最低有效的 31 個字節和 $ e_1 $ 是下一個更重要的 31 個字節和 $ e_2 $ 是最重要的 2 個字節。進一步讓 $ g $ 成為你的基點/基本元素。假設該組是用中性元素乘法編寫的 $ 1 $ . （這假設您實際上無法有效地計算 $ g^{2^{256}} $ 因為指數取 $ 33 $ 字節來表示）
現在計算
- $ A\gets 1 $
- $ A\gets A^{2^{248}} $
- $ A\gets A\cdot g^{e_2} $
- $ A\gets A^{2^{248}} $
- $ A\gets A\cdot g^{e_1} $
- $ A\gets A^{2^{248}} $
- $ A\gets A\cdot g^{e_0} $
- 返回 $ A $
使用您的加速引擎執行六個冪運算。
您可能還想探索使用 $ 255 $ 位寬值，看看是否實現了 2 位求冪 $ e_2 $ 在考慮位級編碼可能持有的額外成本的同時，您自己做可能會更便宜。
Side-Channel 注意：如果您的標準元素乘法和指數是恆定時間，則此算法應該是恆定時間。