拉賓解密

最近我在研究Rabin 密碼系統。但是在算法的解密部分，有兩種方法可以解密密碼。

第一個解決方案 $ p $ 和 $ q $ 等於 $ 3\pmod4 $ 對我來說很清楚。但是第二個解決方案 $ p $ 和 $ q $ 可以是任何素數不是。在第二個解決方案中：（HAC的算法 3.39，求平方根以素數為模 $ p $ ):

輸入：一個奇數素數 $ p $ 和一個正方形 $ a\in Q_p $ .

輸出：兩個平方根 $ a $ 模組 $ p $ .

1. 隨機選擇 $ b\in\mathbb Z_p $ 直到 $ b^2-4a $ 是二次非殘差模 $ p $ ， IE， $ \left({b^2-4a\over p}\right)=-1 $ .
2. 讓 $ f $ 成為多項式 $ x^2−bx+a $ 在 $ \mathbb Z_p $ .
3. 計算 $ r=x^{(p+1)/2}\bmod f $ 使用算法 2.227（注： $ r $ 將是一個整數）。
4. 返回 $ (r,−r) $ .

問題：

1. 在第一步中，我只是隨機選擇一個是否正確 $ b $ 在範圍內 $ 0 $ 至 $ (p-1) $ 並在此替換它 $ \left({b^2-4a\over p}\right)=-1 $ 計算價值 $ a $ ? 如果它是正確的 $ a $ 有任何其他條件可以遵循。
2. 第二名 $ f $ 多項式，我也選擇隨機是否正確 $ x $ 在範圍內 $ 0 $ 至 $ (p-1) $ 併計算 $ f $ 與 $ x $ 我選擇。如果它是正確的，那麼值 $ x $ 我選擇的和結果 $ f $ 需要其他條件嗎？

注意：假設熟悉有限環 $ \mathbb Z_w $ 、多項式環和標準符號；見最後一節。

問題的拉賓密碼系統中的解密涉及解決 $ m $ 方程 $ m^2\equiv a\pmod{p,q} $ . 這是通過解決 $ m^2\equiv a\pmod p $ 和 $ m^2\equiv a\pmod q $ （在大多數情況下每個產生兩個解），使用中國剩餘定理將它們組合起來（在大多數情況下產生四個解），並以某種方式選擇正確的一個。

問題中引用的算法是一種解決方法 $ m^2\equiv a\pmod p $ 為任何（大）素數工作 $ p $ ，而不是局限於這種情況 $ p\equiv3\pmod4 $ . 請參閱this以證明其正確性。

回答問題：

1. 不，算法的第 1 步與問題 1 中所述不同。 $ a $ 是算法的給定值，因此不計算。 $ b $ 在範圍內隨機挑選 $ [0,p) $ 和勒讓德符號 $ \left({b^2-4a\over p}\right) $ 被計算（可能：如 $ (b^2-4a)^{(p-1)/2}\bmod p $ 結果 $ p-1 $ 取而代之 $ -1 $ )，直到那 $ -1 $ . 這需要平均大約兩個隨機數 $ b $ .
2. 不，算法的第 3 步與問題 2 中所述不同。 $ r $ 使用多項式算術模多項式計算 $ f $ , 沒有專門的 $ x $ （這與所需的沒有直接關係 $ m $ ）。碰巧結果總是一個常數多項式 $ r $ ， 和 $ m=r $ 是一個解決方案； $ m=-r $ 或等效地 $ m=p-r $ 也是一種解決方案。

---

制定的例子： $ p=41 $ , $ q=53 $ , $ a=1945 $ ， 尋找 $ m $ 這樣 $ m^2\equiv a\pmod{p,q} $ . $ a $ 是我們試圖破譯的密文，因此是給定的。我獲得了 $ a=1945 $ 通過任意選擇 $ m=92 $ , 和計算 $ m^2\bmod(p;q) $ .

中國剩餘定理在以下三個外部/左側項目符號中規定了整體解決策略：

• 我們先解決 $ m^2\equiv a\pmod p $ . 在整個第一個項目符號（包括下面的 1./2./3./4.）中，我們在有限環中執行 $ (\mathbb Z_p,+,\times) $ 因此可以替換任何數量 $ u $ 不是指數 $ u\bmod p $ . 尤其是 $ m^2\equiv a\pmod p $ 變成 $ m^2\equiv 18\pmod{41} $ .

  1. 我們試著 $ b=2 $ , 計算 $ (b^2-4a)^{(p-1)/2}\bmod p $ ， 那是 $ (4-72)^{20}\bmod41 $ ， 那是 $ 14^{20}\bmod41 $ ， 那是 $ 40 $ ， 那是 $ p-1 $ ; 因此這個選擇 $ b=2 $ 驗證 $ \left({b^2-4a\over p}\right)=-1 $ 我們堅持下去。
  2. 我們設置多項式 $ f=x^2−b,x+a $ 係數在 $ \mathbb Z_p $ ， 那是 $ f=x^2+39x+18 $ 係數在 $ \mathbb Z_{41} $ ; $ x $ 是多項式的變數，沒有特定的值。
  3. 我們計算多項式 $ x^{(p+1)/2}\bmod f $ 那是 $ x^{21}\bmod f $ , 使用多項式算術模多項式 $ f $ . 指數的二進製表示 $ 21 $ 是10101，通過從左到右的二進制取冪，我們將計算 $ x^2 $ , $ x^4 $ , $ x^5 $ , $ x^{10} $ , $ x^{20} $ , 最後 $ x^{21}\bmod f $ .

  更準確地說，我們從 $ x^1\bmod f $ 10101並從左到右跳過最左邊的掃描1；對於其中的每個數字（因此對於0 1 0 1），我們將先前的結果平方 $ x^k\bmod f $ （因此將前一個指數加倍 $ k $ )，那麼如果掃描的數字是1我們乘以 $ x $ （從而增加指數 $ k $ 一個）。這如下：

  + 我們計算 $ x^2\bmod f $ ， 那是 $ x^2-(x^2+39x+18) $ ， 那是 $ 2x+23 $ （注意：我們減少所有係數模 $ p $ ).
  + 我們計算 $ x^4\bmod f $ ， 那是 $ {(x^2)}^2\bmod f $ ， 那是 $ (2x+23)^2\bmod f $ ， 那是 $ 4x^2+10x+37\bmod f $ ， 那是 $ 4x^2+10x+37-4(x^2+39x+18) $ ， 那是 $ 18x+6 $ .
  + 我們計算 $ x^5\bmod f $ ， 那是 $ (x^4)x\bmod f $ ， 那是 $ (18x+6)x\bmod f $ ， 那是 $ x+4 $ .
  + 我們計算 $ x^{10}\bmod f $ ， 那是 $ {(x^5)}^2\bmod f $ ， 那是 $ (x+4)^2\bmod f $ ， 那是 $ 10x+39 $ .
  + 我們計算 $ x^{20}\bmod f $ ， 那是 $ {(x^{10})}^2\bmod f $ ， 那是 $ (10x+39)^2\bmod f $ ， 那是 $ 37x+8 $ .
  + 我們計算 $ x^{21}\bmod f $ ， 那是 $ (x^{20})x\bmod f $ ， 那是 $ (37x+8)x\bmod f $ ， 那是 $ 31 $ （正如預期的那樣， $ x $ 術語已經消失）。
  

  4. 因此 $ m^2\equiv a\pmod p $ 有解決方案 $ m\in{10,31}\pmod p $ .

• 我們同樣解決 $ m^2\equiv a\pmod q $ , 有解決方案 $ m\in{14,39}\pmod q $ .

• 我們結合這些來解決 $ m^2\equiv a\pmod{p,q} $ , 有解決方案 $ m\in{92,728,1445,2081}\pmod{p,q} $ .

---

一些定義和事實。

對於整數 $ w>0 $ ，根據定義， $ u\equiv v\pmod w\iff w\ \text{ divides }\ u-v $ .

關係 $ \equiv\pmod w $ 是整數環上的等價關係 $ (\mathbb Z,+,\times) $ 並與其運營商兼容。它的等價類形成有限環 $ (\mathbb Z_w,+,\times) $ ，根據定義。

符號 $ v\bmod w $ 代表歐幾里得除法的餘數 $ v $ 經過 $ w $ . 它認為 $ u=v\bmod w\iff 0\le u<w\ \text{ and }\ u\equiv v\pmod w $ .

符號 $ u=v\bmod w $ 必須理解為 $ u=(v\bmod w) $ ， 很像 $ u=v+w $ 方法 $ u=(v+w) $ ; 什麼時候 $ u\equiv v\pmod w $ 或等效地 $ u=v\pmod w $ 指出 $ u $ 和 $ v $ 是等效的模 $ w $ . 可以通過前面的左括號找到等效的模符號 $ \bmod $ ，這永遠不會發生在 $ \bmod $ 是一個運算符。

為了 $ k>0 $ , 它認為

$$ \begin{align} u&\equiv v\pmod w&&\iff u\bmod w\ =\ v\bmod w\ u&\equiv v\pmod w&&\iff (u\bmod w)\equiv v&&\pmod w\ u^k&\equiv v\pmod w&&\iff (u\bmod w)^k\equiv v&&\pmod w \end{align} $$ 根據中國剩餘定理，如果 $ w $ 和 $ w’ $ 是互質的（如果 $ w $ 和 $ w $ 是不同的素數），那麼

$$ u\equiv v\pmod{w;w’}\iff u\equiv v\pmod w\ \text{ and }\ u\equiv v\pmod{w’} $$ 什麼時候 $ p $ 是素數， $ (\mathbb Z_p,+,\times) $ 是一個有限域。

可除性和模的定義可以擴展到多項式 $ (\mathbb Z_p,+,\times) $ ，形成執行步驟3的多項式環。

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