得到一個一個a使得二次餘數有解 (Rabin)
我的任務是實現 Rabin 簽名。我在選擇填充時遇到了麻煩
$$ x^2 \equiv a \pmod n $$ 有解決辦法。 在這種情況下， $ n=p\cdot q $ 是複合的，其中 $ p $ 和 $ q $ 是素數 $ p\equiv3\pmod 4 $ 和 $ q\equiv3\pmod 4 $ .
- 如何檢查是否存在解決方案？
- 有什麼正式的方法可以找到 $ a $ ?
方程 $ a = x^2 \bmod N $ 最多有 $ 4 $ 解決方案 $ x $ .
如果有解決方案 $ a $ 都是平方模 $ p $ 和 $ q $ . 這可以通過計算符號的勒讓德來檢查 $ x $ 模組 $ p $ 和模 $ q $ .
假設兩個勒讓德符號為 +1，當 $ p \equiv 3 \pmod 4 $ , 的平方根 $ a $ 模組 $ p $ 是（誰）給的 $ x_p = a^{(p+1)/4} \bmod p $ ; 另一個平方根模 $ p $ 是（誰）給的 $ -x_p $ ; 和類似的模 $ q $ . 平方根模 $ N $ 然後通過中文餘數（CRT）得到： $ x_1 = \mathrm{CRT}(x_p,x_q) $ , $ x_2 = \mathrm{CRT}(-x_p,x_q) $ , $ x_3 = \mathrm{CRT}(x_p,-x_q) $ , $ x_4 = \mathrm{CRT}(-x_p,-x_q) $ .
例如，假設 $ p = 852151 $ 和 $ q = 376963 $ （注意 $ p,q \equiv 3 \pmod 4 $ ）。所以 $ N = pq = 321229397413 $ . 也讓 $ a = 187078154864 $ . 經驗證，勒讓德符號 $ a $ 模組 $ p $ 是 $ +1 $ , 和類似的模 $ q $ .
從前面的公式，我們得到 $ x_p = 295070 $ 和 $ x_q = 21456 $ . 的四個平方根 $ a $ 然後通過中文餘數得到： $ 184209776740 $ , $ 156318284370 $ , $ 164911113043 $ ， 和 $ 137019620673 $ .
備註1：勒讓德符號 $ a $ 模組 $ p $ 是（誰）給的 $ a^{(p-1)/2} \bmod p $ .
備註2：給定 $ x_p $ 和 $ x_q $ , $ \mathrm{CRT}(x_p,x_q) = x_p + p[i_p(x_q - x_p)\bmod q] $ 和 $ i_p = p^{q-2} \bmod q $ .