蒙哥馬利還原
我正在上一門硬體密碼學課程並研究一個專注於蒙哥馬利還原的問題。
所以根據定義：計算 $ a * b \text{ mod } N $
- 挑選 $ R $ ， 英石 $ R > N $ , $ gcd(R,N) = 1 $
- 計算 $ N^{-1} \text{ mod }R $
- $ a’ = a * R \text{ mod } N $
- $ b’ = b * R \text{ mod } N $
- $ c’ = (a’ * b’) * R^{-1} \text{ mod } N $
- $ c = c’* R^{-1} \text{ mod } N $
宣稱： $ c ≡ a * b \text{ mod } N $
證明： $ c’R^{-1} ≡ (a’b’)R^{-1} R^{-1} ≡ (a’ * R^{-1}) * (b’ * R^{-1}) ≡ a * b \text{ mod } N $
如果 $ R=2^k, x * R, ÷ R, \text{ mod } R $ 是實現模冪運算的微不足道的選擇。
現在我被要求解決這個問題，給出以下 25 模 109 wrt 128。我的問題是因為我只有 $ a= 25 $ , 這是否意味著沒有 $ b $ 價值？如果是這樣的話，我可以忽略計算 $ b’ = b * R \text{ mod } N $ 表達式，並將其從計算中刪除 $ c $ 方程？
查閱課堂上的成績單，他處理的一個例子與這個問題非常相似。從根本上說，您正在嘗試解決問題 c = (T + T(-N^-1) (mod R)N)/R (mod N)。我建議在 Excel（或您選擇的其他工具）中創建一個方程。使用範例問題的輸入（範例輸入：T=69，N=109，R=128，-N^-1 = 27）測試您的方程。當您確信您的方程適用於該問題時（範例問題解決方案 = 61），然後插入該問題的值。提示：對於這個問題，T = 25。
答案是 30：
$$ T=25, N=109, -(N)^{-1} = 27, R=128 $$ $$ \Rightarrow T(R^{-1}) \bmod N $$ $$ \Rightarrow m=T*(-N)^{-1} \bmod R \Rightarrow m= 2527 \bmod 128 \Rightarrow m=35 $$ $$ \Rightarrow t= (T+m \cdot N)/R \Rightarrow (25+(35109))/128 \Rightarrow t=30 $$