Rsa
RSA 最低有效位預言機攻擊
我一直在閱讀有關 RSA 攻擊的資訊，並且遇到了一種可以稱為最低有效位 (LSB) 預言機攻擊的方法。
為了清楚起見，讓我們定義 RSA 素數 $ (p, q) $ , 私鑰 $ d $ 和公鑰 $ (e, N) $ 在哪裡 $ N $ 是模數。
現在假設存在一個將解密給定密文的預言機 $ C $ 使用私鑰 $ d $ 並檢查解密密碼的奇偶性。即，如果解密的密碼分別是偶數或奇數，它將返回真或假。
如果攻擊者截獲加密的明文 $ C = P^e \mod N $ 他可以乘以 $ 2^e\mod N $ （基本上是原始明文的兩倍）並將其發送到預言機。預言機將解密並找到 $ 2P\mod N $ . 現在如果 $ 2P>N $ 那麼餘數將是奇數，因為 $ N $ 很奇怪。如果 $ 2P<N $ 那麼其餘的將保證是偶數。攻擊者現在將知道 $ P<N/2 $ （oracle 甚至返回）或 $ P>N/2 $ （甲骨文返回奇數）。
這是我被卡住的部分，因為顯然你可以以某種方式迭代地應用這個原則並通過迭代地縮小 $ P $ 完全恢復 $ P $ 在 $ \log_{2}N $ 迭代。我無法看到迭代將如何工作。
如果可能的話，我更喜歡提示而不是完全寫出的解決方案，因為我會從自己做的事情中學到更多。我只需要在正確的方向上輕輕一點。非常感激。
這是迭代的下一步，應該很容易理解：
讓我們在 2P 和 4P 上呼叫預言機：
- 回答（偶數，偶數）的意思是， $ P<N/4 $ （這仍然很容易：否則 2P 或 4P 將大於 N）。
- （偶數，奇數）表示 $ N/4\le P<N/2 $ .
- （奇，偶）是什麼意思 $ N/2\le P<3N/4 $
- （奇，奇）是什麼意思 $ 3/4N\le P<N $ .
如果繼續將 P 的因子乘以 2，則得到下一輪迭代，其中“奇數”表示區間的上半部分，“偶數”表示區間的下半部分。