證明修改拉賓簽名的性質
我試圖證明“修改拉賓簽名方案”的屬性之一：
如果 $ \gcd(x, n) = 1 $ ， 然後 $ x^{\frac{(p−1)(q−1)}{2}} \equiv 1 \pmod n $
這就是我到目前為止所得到的……
證明
讓 $ p $ 和 $ q $ 是素數，使得 $ p \equiv 3 \pmod 4 $ 和 $ q \equiv 3 \pmod 4 $
$$ p = 4 t_1 + 3 , , q = 4 t_2 + 3 ,,,,,,,,,,-(I) $$
然後 （ $ s $ =奇數）
$$ \frac{\phi(n)}{2} = 2 s\ $$
從“歐拉定理”我們知道
$$ x^{\phi(n)} \equiv 1 \pmod n $$
兩邊取平方根
$$ x^{\frac{\phi(n)}{2}} \equiv \sqrt{1} \pmod n $$
假設
$$ x^{\frac{\phi(n)}{2}} \equiv -1 \pmod n , \text{ i.e. } , x^{2s} \equiv -1 \pmod n\ \implies x^{2s} -1 = nk $$
替換值 $ p, q $ 從 $ (I) $ 我們得到
$$ x^{\text{even}} = (\text{odd})k + 1 $$
現在，我想證明
$$ x^{\text{even}} \neq (\text{odd})k + 1 $$
……但我有點卡在這裡。
任何人都可以幫我完成修改拉賓簽名屬性之一的證明嗎？
簡而言之：當你計算模數時 $ n = pq $ ，你真的是同時計算東西模 $ p $ 和模 $ q $ . 這就是中國剩餘定理的要點。所以要證明 $ a = b \pmod n $ , 你只需要證明 $ a = b \pmod p $ 和 $ a = b \pmod q $ .
模組 $ p $ , 對於任何 $ x $ 這不是的倍數 $ p $ , $ x^{p-1} = 1 \pmod p $ （這是費馬小定理）。所以， $ x^{k(p-1)} = 1^k = 1 \pmod p $ 對於任何整數 $ k $ . 現在， $ p $ 和 $ q $ 是大素數，所以它們是奇數。它遵循 $ q-1 $ 是偶數，因此 $ (q-1)/2 $ 是一個整數。所以 $ x^{(p-1)(q-1)/2} = 1 \pmod p $ . 模數也一樣 $ q $ 出於同樣的原因。通過 CRT，你得到模數的結果 $ n $ .
請注意，雖然 Rabin 的密碼系統定義為 $ p = 3 \pmod 4 $ 和 $ q = 3 \pmod 4 $ , 這些性質並不是證明 $ x^{(p-1)(q-1)/2} = 1 \pmod n $ . 它也適用於 $ p = 1 \pmod 4 $ 或者 $ q = 1 \pmod 4 $ . 唯一的要求是 $ x $ 對兩者都比較重要 $ p $ 和 $ q $ ，這正是 $ \mathrm{gcd}(x,n) = 1 $ 方法。