Number-Theory
辨識設置中的二次殘差
假設 Alice 有兩個素數 $ p $ 和 $ q $ 這樣 $ p\equiv q \equiv 3 \pmod 4 $ . $ n=p\cdot q $ 是她身份證明的一部分。一方說鮑勃，向她發送一個隨機二次殘差 $ {}\bmod n $ ， 說 $ x $ . 為了辨識她，Alice 計算 $ y $ , 的平方根 $ x $ 並將其發送給 Bob。他只是驗證 $ y^2\equiv x\pmod n $ .
這樣就完成了驗證，但 Bob 現在可以冒充 Alice。我被困在試圖找到計算平方根模的資訊 $ n $ 洩漏。我猜這與以下事實有關 $ p\equiv q \equiv 3\pmod 4 $ .
我的問題是在此之後，鮑勃如何計算平方根模 $ n? $ 也就是說，如果有人，比如 Eve，給 Bob 一個二次餘數 $ {}\bmod n $ ， 說 $ z $ ，Bob 如何計算平方根，比如說 $ d $ ， IE， $ d^2\equiv z\pmod n $ ，即，Bob 如何讓 Eve 相信她正在與 Alice 通信？
該協議的問題並不在於它允許 Bob 自己執行平方根；是它允許 Bob 推導出 $ n $ 很有可能（這樣，他可以進行平方根運算）。
以下是鮑勃的做法：
- 他選擇一個隨機值 $ 0 < r < n $ , 計算 $ x = r^2 \bmod n $ , 並發送 $ x $ 給愛麗絲。
- 現在， $ x $ 實際上有 4 個平方根模 $ n $ （除非 $ x $ 恰好不是相對質數 $ n $ ; 這是不可能的）。Alice 選擇四個中的一個，並返回該值 $ y $ 給鮑勃。
- Bob 現在有兩個值 $ r $ 和 $ y $ 和 $ r^2 \equiv y^2 (\bmod\ n) $ ，或者換句話說， $ r^2-y^2 = (r-y)(r+y) = kn $ 對於某個整數 $ k $ （注意：這個方程在整數環中，而不是在模數環中 $ n $ ).
- 如果 $ r \ne y $ 和 $ r \ne -y $ （機率 0.5，因為 $ r $ 是隨機選擇的，並且 $ y $ 有 4 個可能的值，其中 2 個滿足其中一個關係，其中 2 個都不滿足），那麼 $ (r-y)(r+y) $ 是的倍數 $ n $ , 但兩者都不 $ (r-y) $ 也不 $ (r+y) $ 是的倍數 $ n $ . 因此，其中之一 $ r-y $ , $ r+y $ 必須是 p 的倍數，另一個必須是 q 的倍數。
也就是說，直接計算 $ gcd( n, r+y ) $ 直接產生的主要因素之一 $ n $ .
這種情況發生的機率為 0.5；如果 Bob 知道 Alice 如何選擇四個可能的平方根中的哪一個（例如，她總是選擇本身是二次餘數的那個），那麼他可以通過在 $ r $ 他選擇。