為什麼拉賓加密等同於因式分解？
我不明白我在任何地方都讀過的等價證明（例如，在 Rabin 的論文中或在 Wikipedia 上）。
這是我的反對意見：假設您有一個 Rabin 解密預言機，它接受
n並c返回. 對於給定的and ，它總是返回相同的平方根，但是輸出根的選擇是隨機的，而不是and的組合。在這種情況下，oracle 將在 25% 到 50% 的時間內解密密文（取決於密文的根數），但我不清楚如何在此基礎上考慮因素。c mod n``n``c``n``c``n我同意一個同時彈出
s並r允許一個輕鬆分解的預言n機，但至少 25% 的時間沒有必要這樣做來破壞拉賓。
由於n = pq，那麼當整數模n是平方時，它（通常）有四個平方根。這可以通過推理模p和模q看出：一個正方形有兩個模p根和兩個模q根，這有四種組合。
更準確地說，模素數p，如果y有一個平方根x，它也有另一個平方根 - x。這同樣適用於模q，並進行四種組合。您要尋找的是一對值（a，b），它們都是相同值的平方根（即a 2 = b 2 mod n）、a = b mod p和a = - b mod q（或反之亦然）。如果你有這樣的一對，那麼c = a- b mod n將是一個整數，等於 0 模p但不模q；換句話說，c將是p的倍數，但不是q的倍數，因此**c和n之間的簡單GCD計算將揭示p。
假設您有一個可以計算平方根模的盒子。然後，攻擊是這樣進行的：生成一個隨機的 a模n；計算一個2 mod n並將其發送到盒子。該框將返回平方根b（四個可能的平方根之一）。如果盒子返回a本身，或者n - a，那麼這一輪失敗，攻擊者必須從另一個隨機a重新開始。這發生在 50% 的時間裡。但是，如果該框返回2的另外兩個平方根之一，那麼上面解釋的 GCD 會顯示n的因子。
沒有開箱即用的平方根選擇策略可以阻止這種攻擊，因為攻擊者是完全隨機選擇的。
以上並未表明“拉賓加密等同於分解”。它表明，提取模n平方根的一般能力等同於知道n的因數。這裡的“一般”一詞意味著該能力適用於相當大比例的模數平方值。任何人都可以計算某些值的平方根（例如，如果我們以n為模，而你用值“9”挑戰我，那麼我可以回答該值的平方根為“3”，即使沒有知道n )的因數；但是如果你可以為所有整數模n的不可忽略的部分做到這一點那麼你可以考慮n。
沒有指定 Rabin 加密的實際標準，但如果有，那麼該標準可能需要某種填充，因為如上所述，一個正方形有四個平方根。解密引擎必須選擇哪一個是正確的。一個簡單的策略是添加一些冗餘填充：加密消息m時，通過將**h ( m )附加到m將其轉換為整數x（對於某些雜湊函式h) 然後將整體解釋為整數。然後，在解密時，重新計算雜湊以了解您是否獲得了正確的平方根，而不是其他三個中的一個。（填充還必須包含一些隨機性，以避免對明文施加暴力。）
有了這樣的填充，一個可以解密的盒子可能會返回解密的值，或者它可以說“這不會解密到任何正確填充的東西”。然後上面解釋的攻擊不再起作用；攻擊者必須找到一個值a使得另一個平方根b（既不是a也不是- a）以適當的填充結束，否則解密 oracle 將不會返回它。根據填充的精確定義方式，達到這樣一個值的機率可能太小而無法實際發生。
因此，在提取模n的平方根時等價於因式分解n，但一般不能說實際的拉賓加密等價於因式分解。這取決於填充和使用的細節，目前尚未定義的細節。
又想了5分鐘，我想我解決了自己的問題。
選擇任意消息
m，計算並c=m^2 % n送出c``n給 Rabin 預言機。如果您重複此操作足夠多次（我的意思是可能在 2 次迭代內），您將選擇m這樣一種方式，即 oracle 為您提供±另一個根，然後您可以使用它來分解n。