ElGamal 加密安全
假設我們在 form 中有 2 個素數
p = 2q + 1。**在 ElGamal 加密中使用循環組
p-1而不是順序組是否安全？q**我找不到任何合適的來源來解釋為什麼我們應該使用 q 作為我們組的順序並避免p-1.大多數網站和消息來源只是說：
使用 q 階循環群
沒有任何解釋。
我嘗試了什麼？ 我假設
p = 11，因此q = 5。我通過將 10 視為我的組順序來進行 ElGamal-Encryption 的所有計算（ $ Z_{p}^{*} $ ):
- 組（G）= { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
- 團體訂單（q）：10
- *發電機（g）：7
- 消息（m）：9
並且解密消息沒有問題。所以我認為它的安全性有問題！
我認為沒有必要提及計算，
q = 10但如果你需要它們，只需在問題下方評論，將它們作為更新引入問題。
使用順序的循環組是否安全 $ p-1 $ 而不是一個有順序的 $ q $ 在 ElGamal 加密中？
- 不，對於較小的值 $ p $ . 這是問題範例中唯一的安全問題。為了現代安全， $ p $ 至少應該是 $ 2048 $ 位（而不是 $ 4 $ -位 $ p=11 $ 在問題中），而不是接近主要力量。下面的任何內容都說 $ 512 $ -少量 （ $ \approx155 $ 十進制數字）很容易從公鑰中恢復私鑰
- 不，如果*«use»*指的是明文集。問題是：從ElGamal 加密的密文中，攻擊者可以發現明文是否 $ m $ 是二次餘數模 $ p $ 與否（也就是說，如果 $ m^{(p-1)/2}\bmod p $ 是 $ 1 $ 或者 $ p-1 $ ）。如何留給讀者作為練習。參考：Dan Boneh、Antoine Joux 和 Phong Q. Nguyen 的Why Textbook ElGamal and RSA Encryption Are Insecure（在AsiaCrypt 2000的會議記錄中），在Yehuda Lindell 的回答中推薦。
此屬性在選擇明文攻擊甚至更弱的概念下破壞了安全性。這可能是一個實際的弱點：如果它在公共班級名冊上被加密了一個名字（使用一個大 $ p $ )，我們可以排除給定密文的大約一半名稱。如果是頭部和尾部具有固定公共值的拋硬幣，對於這些值的大約 50% 的選擇，拋硬幣會洩漏。
安全且通常的選擇是將明文限制為二次殘差組，即 $ m $ 和 $ m^{(p-1)/2}\bmod p=1 $ . 在問題的範例中發生這種情況（可能是偶然的），因為 $ 9^5\bmod11=1 $ . 3. 是的，如果*«use»*指的是 $ g $ 並解決了以上問題：使用安全 $ g $ 生成整個循環組。這就是問題範例中的情況，因為 $ 7^5\bmod11=11-1 $ .
然而，這是不尋常的，因為我們必須限制明文（每 2 個），並且通常我們限制 $ g $ 到同一組，以便回到通用組中的 ElGamal 加密（重新）。這就是消息來源所做的，他們只是說：«使用素數的循環群 $ q $ ».
如前所述，（2）中問題的教科書解決方案是將明文限制為二次殘差的子群。當我們加密一個小的離散集時，這很好：我們可以手工挑選 $ m_i $ 表示集合元素。
但是當我們加密任意數據時，比如班級名冊上的名字，那是行不通的。實際上，這是使用混合加密解決的。但是如果我們想要更接近直接的 ElGamal 加密 $ \mathbb Z_p^* $ ，一個可行的方法是：
- 明文 $ m $ 被限制在一個區間 $ [0,m_{\text{max}}] $ 和 $ m_{\text{max}}<(p-1)/2 $
- 加密 $ m $ 在該時間間隔內，發送方計算 $ m’\gets(m+1)^2\bmod p $ 並使用普通的 ElGamal 加密對其進行加密。注意 $ m’ $ 是二次餘數，阻止了攻擊。
- 接收方破譯後 $ m’ $ ，他們找到兩個模平方根中最小的一個 $ m’ $ （模組 $ p $ ) 使案例如Tonelli-Shanks，然後減去一個來找到 $ m $ .
當心實施中的側通道！