Elgamal-Encryption
是否可以對 elgamal 密碼系統進行二次殘差攻擊？
我了解這種攻擊如何在精神撲克上發揮作用，但我無法看到如何在 Elgamal 中應用它。
首先，關於二次殘差的一些背景：
- 二次殘差 (QR) 是一個數字 $ x $ 這樣存在一些數字 $ y $ 和 $ x \equiv y^2 \pmod p $ （在哪裡 $ p $ 是我們正在談論的模數-我將在此處隱含），並且無關緊要 $ y $ 是，只有這樣一個 $ y $ 存在。
- 存在一個有效的測試，我們可以確定是否有任何值 $ x $ 是不是二維碼。
- 價值 $ x \times y $ 是 q QR 如果兩者都有 $ x, y $ 是 QR，或者都不是。如果一個是 QR 而另一個不是，那麼 $ x \times y $ 不會是。
- 價值 $ x^n $ 是 QR，如果有的話 $ x $ 是 QR 或 $ n $ 是偶數（或兩者） - 如果 $ x $ 不是 QR 並且 $ n $ 是奇數，那麼 $ x^n $ 也不會是 QR。
考慮到這一點，消息的 El Gamal 加密 $ m $ 是對：
$$ (g^r, h^r \times m) $$
在哪裡 $ g $ 是眾所周知的生成器， $ h $ 是公鑰（我們假設攻擊者知道，並且它將是 $ g $ 提升到某種未知的力量），以及 $ r $ 是加密器選擇的隨機數（因此未知）。
我們要做的是確定是否 $ h^r $ 是否是 QR（這可能聽起來有點棘手，因為我們不知道 $ h^r $ ，所以我們不能使用我們的有效測試）。但是，我們可以根據以下情況進行推斷：
- 如果 $ h $ 是一個二維碼，那麼 $ h^r $ 也會如此。
- 如果 $ h $ 不是 QR，這意味著 $ g $ 也不是 QR（因為 $ h $ 是 $ g $ 提升到一定的權力）。在這種情況下，我們檢查是否 $ g^r $ 是否是 QR - 如果是，則 $ r $ 是偶數（所以 $ h^r $ 是一個二維碼）。如果 $ g^r $ 不是二維碼，那麼 $ r $ 很奇怪（所以 $ h^r $ 不是二維碼）。
一旦我們確定了這一點，我們就會檢查是否 $ h^r \times m $ 是一個二維碼。如果 QR-ness $ h^r $ 和 $ h^r \times m $ 是相同的（即，兩者都是 QR，或者都不是），那麼 $ m $ 必須是二維碼。如果它們不同， $ m $ 不能是 QR。
因此，在所有情況下，我們都可以確定是否 $ m $ 通過檢查密文和公鑰，是否是 QR。