使用有限域的加法 ElGamal 密碼系統

我正在嘗試實現 Cramer 等人指定的 ElGamal 密碼系統的修改版本。在“一種安全且最優效率的多權威選舉方案”中，它具有密文之間的加性同態性，而不是原始版本，它呈現乘性同態性。

最大的問題（一如既往）是論文在“小”細節上令人討厭地稀缺。這是我到目前為止所擁有的：

1. 配置參數

• 大小 $ p $
• 大小 $ q $
• 消息空間

2. 密鑰生成

• 選擇一個素數 $ p $ 給定的“密鑰大小”，確保 $ p - 1 $ 有一個很大的素因數 $ q $ （給定大小）
• 挑選 $ g $ 作為循環群的生成器 $ \mathbb{Z}_{q}^* $
• 生成一個隨機數， $ s \in \mathbb{Z}_{q} $ , 併計算 $ h = g^s \pmod q $
• 公鑰是 $ (g, h) $ 和私鑰是 $ (s) $

3. 預計算

• 由於該方案需要計算離散對數以執行解密（見下文），因此消息必須很小，因此我們預先計算每個 $ g^m \pmod q $ 我們將它們儲存在查找表中

4. 加密

• 選擇一個隨機值 $ \alpha \in \mathbb{Z}_{q} $
• 計算 $ (x, y) = (g^{\alpha} \pmod q, h^{\alpha} g^m \pmod q) $

5. 解密

• $ y x^{-s} \pmod q \equiv h^{\alpha} g^m g^{-s \alpha} \pmod q \equiv g^{s \alpha} g^m g^{-s \alpha} \pmod q \equiv g^m \pmod q $
• 我們使用預先計算的查找表來查找相應的消息， $ m $ , 對於計算 $ g^m \pmod q $

問題：

1. 我不確定每個操作的隱含模數是否為 $ q $ ，因為我將自己添加到上述公式中。有人可以澄清一下嗎？論文省略了…
2. 如果，確實，操作的模是 $ q $ ，那麼我需要將它添加到公鑰中，對嗎？如果我這樣做，該計劃不會變得不安全嗎？
3. 關於私鑰，論文沒有指定從中選擇它的集合，我假設它是 $ \mathbb{Z}_{q} $ . 它是否正確？
4. 應該是什麼大小 $ p $ （以位為單位）以獲得與 RSA 1024 提供的類似的安全性？
5. 的大素數的大小（以位為單位）應該是多少 $ p - 1 $ ?

1. 據我從你的描述中可以看出，模數是 $ p $ . 要將兩個組元素相乘，您需要計算 $ xy \mod p $ ; 因為發電機 $ g $ 你選擇有期 $ q $ 一切都會好起來的。
2. 不， $ p $ , $ q $ ， 和 $ g $ 可以（而且必須）全部公開。這是 ElGamal，而不是我們正在談論的 RSA - 安全性來自（假定的）採用離散對數而不是因式分解的難度。
3. 是的。
4. 5. 關於算法和密鑰大小的 Ecrypt 報告http://www.ecrypt.eu.org/documents.html是一個很好的地方。這不是一個簡單的問題，因為它取決於您認為求解離散對數的難度（並且將來會如此）。

Helios 投票系統 ( http://heliosvoting.org ) 中使用了加法 ElGamal（在 Python 中）的現有開源實現，您可能想看看。

引用自：https://crypto.stackexchange.com/questions/3321