ElGamal暗号
pを素数とするとき、G = Z p ∗ {\displaystyle {\mathbb {Z} }_{p}^{*}} としてはいけない。このような群上ではDDH仮定が破れる。 主な方法は二つある。
巡回群Gを Z p ∗ {\displaystyle {\mathbb {Z} }_{p}^{*}} の部分群とする。
巡回群Gを楕円曲線上で定義する(楕円曲線暗号)。
ここでは上の方法を説明する。
小さな自然数kと大きな素数qに対して、素数pをp = kq+1となるように取る。 まず素数qを選んでから、p = kq + 1が素数かどうかを調べればよい。
g ∈ Z p ∗ {\displaystyle g\in {\mathbb {Z} }_{p}^{*}} を、gの位数がqとなるようにランダムに選ぶ。
G =< g > {\displaystyle G=<g>} は Z p ∗ {\displaystyle {\mathbb {Z} }_{p}^{*}} の部分群となっている。
尚、k=2に対してp = 2q + 1が成り立つ素数の組(p,q)が無限に存在するかどうかは未解決問題である(ソフィー・ジェルマン問題、素数#未解決問題)。
上で"離散対数問題が困難であることを基にした"と書いたがこれは正確な表現では無い。 実際には、DLP仮定ではなく、Computational Diffie-Hellman仮定(CDH仮定)およびDecisional Diffie-Hellman仮定(DDH仮定)を基にしている。 ElGamal暗号が選択平文攻撃に対して完全解読できないということ(OW-CPAであるということ)と、CDH仮定とが同値である。 また、ElGamal暗号が選択平文攻撃のもとIndistinguishabillityをもつということ(IND-CPAであるということ)と、DDH仮定とが同値である。
ElGamal暗号は、選択暗号文攻撃に対しては安全ではない。平文 m {\displaystyle m} に対応する ( c 1 , c 2 ) {\displaystyle (c_{1},c_{2})} から、 2 m {\displaystyle 2m} に対応する暗号文 ( c 1 , 2 c 2 ) {\displaystyle (c_{1},2c_{2})} を作成することができるからである。