Rsa
Boneh-DeMillo-Lipton 故障攻擊 (RSA CRT)
我試圖了解對 RSA CRT 簽名的Boneh-DeMillo-Lipton 故障攻擊。
假設我們簽署了一條消息 $ m $ 使用 RSA-CRT：
$ d_p = d \bmod (p-1) $ 和 $ d_q = d \bmod (q-1) $
$ s_p = h(m)^{d_p} \bmod p $ 和 $ s_q \not= h(m)^{d_q} \bmod q $ 在哪裡 $ h $ 是一個雜湊函式
通過 CRT 我們得到 $ s $ 簽名模數 $ n=pq $
我不明白以下斷言：
作為 $ s^e \equiv h(m) \pmod p $ 但 $ s^e \not \equiv h(m) \pmod q $ 我們可以分解 $ n $ 經過 $ p=GCD(s^e - h(m), n) $ .
有人可以向我解釋為什麼 $ p $ 是之間的最大公約數 $ s^e - h(m) $ 和 $ n $ ?
$ q $ 不分 $ s^e-h(m) $ ， 但 $ p $ 確實如此，所以由於 gcd 必須同時劃分 $ s^e-h(m) $ 和 $ n $ 它是 $ p $ . 更明確地說，我們知道 $ p $ 將兩者分開 $ s^e-h(m) $ 和 $ n $ . 的唯一較大除數 $ n $ 也可以被 $ p $ 是 $ n $ 本身，但如果 $ n $ 會分 $ s^e-h(m) $ ， 然後 $ q $ 也會分 $ s^e-h(m) $ ，我們已經假設不成立。