Diffie-Hellman
使用 QR 組進行 El Gamal 加密時的消息空間
我的教科書指出，當我們使用組時，DDH 假設不滿足 $ \mathbb{Z}/p \mathbb{Z} $ 並展示了使用歐拉準則的攻擊。之後，它指出應該使用二次殘差組（ $ \operatorname{QR} $ ） 超過 $ \mathbb{Z}/p \mathbb{Z} $ ， 在哪裡 $ p=2q+1 $ 是一個安全的素數。
我查看了 El Gamal 加密方案（它使用 DDH 假設）並看到，我們要加密的消息必須位於我們選擇的組中。如果這個組是 $ \mathbb{Z}/p \mathbb{Z} = {1,2,3,\ldots ,p-1} $ 我們可以加密每條消息，即不大於 $ p-1 $ . 但是，如果我們使用組 $ \operatorname{QR} $ 結束了 $ \mathbb{Z}/p \mathbb{Z} $ ，我認為有些消息（即 $ (p-1)/2 $ 許多）無法加密。
如果這是真的，在實踐中如何解決這個問題？
如果這是真的，在實踐中如何解決這個問題？
實際上，在實踐中，我們通常根本不使用 El Gamal，而是使用集成加密方案 ( IES )，它基於相同的難題解決相同的問題，但無需擔心二次殘差 (或同態屬性，或需要計算逆，這是可行但煩人的）。
現在，如果我們必須使用 El Gamal（例如，因為我們需要利用同態屬性），那麼，避免 QR 問題的一種方法是在加密之前簡單地對明文進行平方（因此我們加密的明文總是一個二維碼）。然後，在解密時，我們將計算平方根（並取兩個可能值中較小的一個）。這意味著明文僅限於範圍 $ (0, (p-1)/2) $ ，但該範圍內的任何值都可以加密。