Public-Key
使用有限域的加法 ElGamal 密碼系統
我正在嘗試實現 Cramer 等人指定的 ElGamal 密碼系統的修改版本。在“一種安全且最優效率的多權威選舉方案”中,它具有密文之間的加性同態性,而不是原始版本,它呈現乘性同態性。
最大的問題(一如既往)是論文在“小”細節上令人討厭地稀缺。這是我到目前為止所擁有的:
- 配置參數
- 大小 $ p $
- 大小 $ q $
- 消息空間
- 密鑰生成
- 選擇一個素數 $ p $ 給定的“密鑰大小”,確保 $ p - 1 $ 有一個很大的素因數 $ q $ (給定大小)
- 挑選 $ g $ 作為循環群的生成器 $ \mathbb{Z}_{q}^* $
- 生成一個隨機數, $ s \in \mathbb{Z}_{q} $ , 併計算 $ h = g^s \pmod q $
- 公鑰是 $ (g, h) $ 和私鑰是 $ (s) $
- 預計算
- 由於該方案需要計算離散對數以執行解密(見下文),因此消息必須很小,因此我們預先計算每個 $ g^m \pmod q $ 我們將它們儲存在查找表中
- 加密
- 選擇一個隨機值 $ \alpha \in \mathbb{Z}_{q} $
- 計算 $ (x, y) = (g^{\alpha} \pmod q, h^{\alpha} g^m \pmod q) $
- 解密
- $ 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 $
問題:
- 我不確定每個操作的隱含模數是否為 $ q $ ,因為我將自己添加到上述公式中。有人可以澄清一下嗎?論文省略了…
- 如果,確實,操作的模是 $ q $ ,那麼我需要將它添加到公鑰中,對嗎?如果我這樣做,該計劃不會變得不安全嗎?
- 關於私鑰,論文沒有指定從中選擇它的集合,我假設它是 $ \mathbb{Z}_{q} $ . 它是否正確?
- 應該是什麼大小 $ p $ (以位為單位)以獲得與 RSA 1024 提供的類似的安全性?
- 的大素數的大小(以位為單位)應該是多少 $ p - 1 $ ?
- 據我從你的描述中可以看出,模數是 $ p $ . 要將兩個組元素相乘,您需要計算 $ xy \mod p $ ; 因為發電機 $ g $ 你選擇有期 $ q $ 一切都會好起來的。
- 不, $ p $ , $ q $ , 和 $ g $ 可以(而且必須)全部公開。這是 ElGamal,而不是我們正在談論的 RSA - 安全性來自(假定的)採用離散對數而不是因式分解的難度。
- 是的。
- 關於算法和密鑰大小的 Ecrypt 報告http://www.ecrypt.eu.org/documents.html是一個很好的地方。這不是一個簡單的問題,因為它取決於您認為求解離散對數的難度(並且將來會如此)。
Helios 投票系統 ( http://heliosvoting.org ) 中使用了加法 ElGamal(在 Python 中)的現有開源實現,您可能想看看。