Security Akademeia

目次 †

目次
宣伝
拡張ElGamal暗号の仕様
完全性
安全性
- DDH仮定⇒IND-CPA安全
参考文献

↑

宣伝 †

　当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。

　暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。

　興味がある方は宣伝サイトを参照してください。Amazonでも発売中です。

↑

拡張ElGamal暗号の仕様 †

　公開鍵暗号は鍵生成アルゴリズム・暗号化アルゴリズム・復号アルゴリズムの3つのアルゴリズムで構成される。よって、拡張ElGamal暗号も3つのアルゴリズムで構成されている。

↑

鍵生成アルゴリズム †

　セキュリティパラメータを入力とする。

1：q|p-1を満たす大きな素数p,qを生成する。

2：位数がqとなる、 $\mathbb{Z}_q^*$ の元αを生成する。

3：0≦x＜qとなるxをランダムに選択し、次のようにyを計算する。

$y=\alpha^x~\pmod{p}$

4：公開鍵pk=(p,q,α,y)、秘密鍵sk=xを出力する。

↑

暗号化アルゴリズム †

　αで構成される巡回群の元を平文mとし、mとpkを入力とする。

1：0≦r＜qとなるrをランダムに選択する。

2：次のようにc1,c2を計算する。

$c_1=\alpha^r~\pmod{p}$

$c_2=my^r~\pmod{p}$

3：ステップ2で計算したc1,c2を組として、暗号文cとする。そのc=(c1,c2)を出力する。

↑

復号アルゴリズム †

　暗号文c=(c1,c2)、skを入力とする。

1： $\frac{c_2}{c_1^x}~\pmod{p}$ を計算して出力する。

↑

アルゴリズムの補足 †

　以上の3つのアルゴリズムが拡張ElGamal暗号の仕様になる。いくつか補足したい部分がある。

↑

扱っている群について †

　ElGamal暗号で用いた群は $\mathbb{Z}_q^*$ であった。 $\mathbb{Z}_q^*$ の部分群をうまく使うことで、 $\mathbb{Z}_q^*$ のときのDL問題・CDH問題・DDH問題よりも解くのが困難になるのである。HがGの部分群であるとは、HがGの部分集合であり、なおかつHがGと演算が同じであると定義される。

　部分群を用いた方が問題が困難になるという事実を利用したのが拡張ElGamal暗号である。そのため、拡張ElGamal暗号の鍵生成アルゴリズムの中に、 $\mathbb{Z}_q^*$ の部分群を使うための準備が含まれているのである。

↑

鍵生成アルゴリズムのp,qの生成方法 †

　鍵生成アルゴリズムのステップ1における「q|p-1」とは、qがp-1を割り切るという意味である。例えば、p=2q+1の関係などがそうである。このような関係である素数p,qは次のように生成することができる。

1：大きな素数qを生成する。

2：乱数rを選び、 $p=2rq+1$ とする。

3：pが素数かどうかを確認し、素数でないならステップ1に戻る。もしpが素数であれば、(p,q)はq|p-1を満たしている。

↑

αの存在保証 †

　また、鍵生成アルゴリズムのステップ2において、位数（元の位数）という言葉が登場している。gの位数kとは、 $g^k~\pmod{p}=1$ を満たすような最小の値のことである。

　ステップ2で主張する位数がqとなる $\mathbb{Z}_q^*$ の元αが存在することを保証するのは、ステップ1によってq|p-1が成り立つからである。これは元の位数と原始元に関係する定理から言える。

↑

αの生成方法 †

　そして、このαの生成方法は、 $\mathbb{Z}_q^*$ の原始元gを求めて、 $\alpha~=g^{2r}~\pmod{p}$ を計算すればよい。このαの位数はqになっている。即ち、 $\alpha^q~\equiv~1~\pmod{p}$ が成り立つ。しかも、このαの位数はqのみである。この事実は次のように証明できる。

　p-1=2rqかつ $\alpha~=g^{2r}~\pmod{p}$ より、

$\alpha^q$
$=(g^{2r})^q$
$=g^{2rq}$
$=g^{p-1}$ 　（p-1=2rq）
$=1~\pmod{p}$ 　（∵フェルマーの小定理）

　また、 $\alpha^i~\equiv~1~\pmod{p}$ となるi（1≦i＜q）が存在すると仮定すると、

（左辺）
$=\alpha^i$
$\equiv~(g^{2r})^i$
$=g^{2ri}$

と計算できるので、 $g^{2ri}~\equiv~1~\pmod{p}$ が成り立つ。

　ここでgの位数は2ri＜2rq=p-1より小さい。これはgが原始元であることに反する。

　よって、 $\alpha^i~\equiv~1~\pmod{p}$ となるi（1≦i＜q）は存在しない。ゆえに、αの位数はqのみである。　□

↑

巡回群＜α＞について †

　 $\alpha^q~\equiv~1~\pmod{p}$ が成り立つため、任意の整数iに対して $\alpha^i$ は $\alpha^{i~\pmod{q}}~\pmod{p}$ と考えればよい。つまり、αの指数部はmod qの世界で考えればよいのである。

　よって、このαの巡回群はq個であり、この巡回群の要素は $1~\pmod{p},\alpha~\pmod{p},\alpha^2~\pmod{p},~\cdots,~\alpha^{q-1}~\pmod{p},$ になる。この巡回群を＜α＞と定義する。

↑

完全性 †

　アルゴリズムが定義されたならば、まず完全性を確認する必要がある。（公開鍵暗号の）完全性とは復号アルゴリズムを実行すると、平文に戻ることである。つまり、 $\frac{c_2}{c_1^x}~\pmod{p}$ を式展開して、mになれば完全性が成り立つ。

$\frac{c_2}{c_1^x}~\pmod{p}$
$=\frac{my^r}{\alpha^{rx}}$
$=\frac{m\alpha^{xr}}{\alpha^{rx}}$
$=m$ 　□

　よって、完全性が示された。

↑

安全性 †

↑

DDH仮定⇒IND-CPA安全 †

[定理]＜α＞に対するDDH問題が困難であるならば、拡張ElGamal暗号はIND-CPA安全である。

　即ち、＜α＞に対するDDH仮定の下で、拡張ElGamal暗号はIND-CPA安全である。

[証明]これを証明するために対偶で考える。つまり、IND－CPA安全を解くアルゴリズムAが存在するならば、＜α＞に対するDDH問題を解くアルゴリズムBが存在することを示すことができればよい。ここでAの成功確率を(1/2)+εとする。

　証明には帰着法を使う。Aの力を利用して、Bを構成することができ、そのBの成功確率がε以上であればよいのである。

　まずBの構成を示す。
　Bに(α,β,γ,δ)=(α,αx,αy,αz)が与えられるとする。Bの目的はうまく細工をすることにより、Aの力を利用して、z=xy mod qかどうかを有意な確率で判定することである。
　Bは(α,β,γ,δ)を入力とし、pk=(p,q,α,β)をAに公開鍵として与える。このとき、このpkが拡張ElGamal暗号の公開鍵と同じ分布の必要があるが、p,q,α,βすべて同一なため敵はBの中で動作していることに気が付かないので、問題ない。
　次に、AはCPA攻撃者なので2つの平文m0,m1を外に送る。AはBの内部でm0,m1を送信する。Bはそれらを受け取ったら、1ビットのbをランダムに選択する。そして、Bはc=(γ,mbγ)を暗号文としてAに送信する。ここでBが細工しているのである。このcも拡張ElGamal暗号の仕様通りに作られた(c1,c2)とまったく同一の分布を示すため、AはBの中にいることに気付かないため、問題ない。つまり、Aはcが細工されているのに気付かないのである。
　Aは最後にbの推測として $\tilde{b}$ をローカル出力する。
　Bは $\tilde{b}$ を見て、 $b~=~\tilde{b}$ が成り立っていれば1（ここではz=xyが成り立っていることを意味する）を出力し、 $b~\not{=}~\tilde{b}$ が成り立っていれば0（ここではz≠xyが成り立っていることを意味する）をローカル出力する。
　以上でBの構成は完了である。

　次に、Bの成功確率を調べる必要がある。

[1]z=xyの場合

　pkとcは拡張ElGamal暗号の仕様通りのpk,cと分布がまったく同一である。
　よって、仮定よりAは $\frac{1}{2}~+~\epsilon$ 以上の確率で、 $b~=~\tilde{b}$ となる $\tilde{b}$ を出力するはずである。

　ゆえに、z=xyの場合にBは $\frac{1}{2}~+~\epsilon$ 以上の確率で1を出力する。つまり、Bは $\frac{1}{2}~+~\epsilon$ 以上の確率でz=xyであることを判定できる。

[2]z≠xyの場合

　pkは拡張ElGamal暗号の仕様通りのpkと分布がまったく同一である。また、c=(γ,mbγ)=(γ,mbαz)である。zが一様ランダムに取られているので、 $\alpha^z$ は $\mathbb{Z}_q^*$ 上で一様分布しており、 $m_b~\alpha^z$ も $\mathbb{Z}_q^*$ 上で一様分布である。よって、このcは完全にbの情報を隠している。よって、Aは $\frac{1}{2}$ の確率でしか、 $b~=~\tilde{b}$ となる $\tilde{b}$ を出力するしかない。