當 p=q 並且你有來自 Tonelli-Shanks 的根源時如何解密 Rabin 消息

我一直在嘗試解密用拉賓加密的消息作為挑戰。我對密碼學很陌生，這些挑戰中的很多都是新的。

我已經分解了 n 並確定了 p=q，我認為它非常弱。幾個小時後，我發現使用擴展 gcd 進行解密的建議不起作用。

該站點上的類似文章建議使用 Tonelli Shanks 來獲取根，我已經這樣做了。然後繼續說使用 Hensel 來獲取原始值，這將幫助我解碼消息，但是我不熟悉如何實現這一點，到目前為止還沒有得到一個合理的解決方案，所以想問求助。

我的價值觀是：

n = 64703986196590532550677581867968606868573389071252692910980134129544137251401009133960328088692271842214498048655106618080254509684622363068406743573918979874641476333101257493419006081088753833559346504226066744706781644205324359031963711461737816475092631177676839385116576945754784715871099567521310291121
c = 60176314581676071043291067556352196274798660837188399828657574988742539250919925123769575021091715252070984470036260674221672743791229186519807702970426856963367776191049481817101068301897617186674960557150362771617316082251276579987076557148986523477838971190589062577795308359830070072697195634741564991953
p = q = 8043878802952623586394638108236704902850439411184561583961128617599719871469109041598304494567727280429349828456316270041563810531926784203271836896365511
root0 = 2187931274452861858404184425736861076518005991476611501855956036160679792394841793895180158176546375577356726244165298846056538405976359097397665134536364 
root1 = 5855947528499761727990453682499843826332433419707950082105172581439040079074267247703124336391180904851993102212150971195507272125950425105874171761829147

我們被給予 $ n>4 $ 和密文 $ c\in(0,n) $ 用於教科書拉賓加密。我們想解決 $ x\in[0,n) $ 方程 $ x^2\bmod n=c $ . 我們發現 $ n $ 是一個平方，計算 $ p=\sqrt n $ ，發現是素數，求解 $ y^2\bmod p=c\bmod p $ 產生兩個根 $ y_0\in(0,p/2) $ 和 $ y_1=p-y_0 $ ，現在想要原始方程的解。

每一個 $ x\in[0,n) $ 可以唯一地寫為 $ x=y+z,p $ 和 $ y\in[0,p) $ 和 $ z\in[0,p) $ .

如果 $ x=y+z,p $ 是一個解決方案 $ x^2\equiv c\pmod{p^2} $ ，那麼這也產生模 $ p $ 自從 $ p $ 劃分 $ p^2 $ ， 因此 $ y^2\equiv c\pmod p $ ，因此我們早期的工作確實產生了 $ y $ .

現在 $ (y+z,p)^2\equiv c\pmod{p^2} $ 變成 $ y^2+2,y,z,p\equiv c\pmod{p^2} $ ， 那是

$ 2,y,z,p\equiv c-y^2\pmod{p^2} $ ， 那是

$ \exists k\in\mathbb Z,,2,y,z,p+k,p^2=c-y^2 $ ， 那是

$ \exists k\in\mathbb Z,,2,y,z+k,p=(c-y^2)/p $ ， 那是

$ c-y^2 $ 可以被 $ p $ 和 $ 2,y,z\equiv(c-y^2)/p\pmod p $ ， 那是

$ c-y^2 $ 可以被 $ p $ 和 $ z\equiv(2,y)^{-1},((c-y^2)/p)\pmod p $

因此我們檢查 $ c-{y_0}^2\bmod p=0 $ （除非我們在計算中犯錯，否則它必須成立 $ y_0 $ )，

計算 $ b_0=(c-{y_0}^2)/p\bmod p $ ， 然後 $ z_0=(2,y_0)^{-1},b_0\bmod p $ ,

那麼 $ x_0=y_0+z_0,p $ ，這是一種解決方案。它不能為零。另一個是 $ x_1=p^2-x_0 $ .

引用自：https://crypto.stackexchange.com/questions/85851