初めに
『暗号技術のすべて』（IPUSIRON）を読んでいたら、私が知ってる楕円ElGamal暗号と少し違う方式（変種）が紹介されていました。
「なるほど、そういうのもあるのだな」と思ったのですが、よく考えると安全性が損なわれているのではと思って考えたことを書いてみます。
単に、不勉強な私が知らなかっただけで大昔からの既知の事実だと思いますが、探してもあまり見当たらなかったのでまとめておきます。
楕円ElGamal暗号
まずは『現代暗号の誕生と発展』（岡本龍明）でも紹介されている、私が知っていた方式を、記号を変えて紹介します。用語は楕円ElGamal暗号も参照してください。
記号の定義
0 以上 r 以下の整数の集合を [0, r], そこからランダムに整数 x を選ぶことを x ← [0, r] と書くことにします。
G を楕円曲線の点 P を生成元とする素数位数 r の巡回群 \langle P \rangle = \Set{0, P, 2P, \dots, (r-1)P} とします。G, P, r は公開パラメータです。
鍵生成
s ← [0, r-1] をとり、Q:=sP \in G とします。s が秘密鍵で Q が公開鍵です。
暗号化
平文 M \in G に対して、乱数 t ← [0, r-1] をとり、公開鍵 Q を使って Enc_Q(M;t):=(M+tQ,tP) \in G^2 を暗号文とします。
復号
暗号文 c:=(C_1,C_2) \in G^2 に対して Dec_s(c):=C_1-s C_2 \in G とします。
暗号化・復号の妥当性
M の暗号文 c:=Enc_Q(M;t)=(C_1, C_2) を復号しましょう。
C_1=M+tQ, C_2=tP, Q=sP なので
Dec_s(c)=C_1-s C_2=(M+tQ)-s(tP)=M+tsP-stP=M
となって元の平文に戻ります。
平文空間の注意
上記の方式で要素 M は G の元、つまり楕円曲線の点であることに注意してください。
通常平文は、ある範囲の整数値 m なので m をどうにかして楕円曲線の点 M に変換しなければなりません。
そして、復号するときは逆に M から元の整数値 m を復元できなくてはなりません（1対1の対応）。この対応は暗号化とは異なり、誰でも計算できる操作であり、埋め込みと呼ばれます。
M = Encode(m).\\m = Decode(M).
どのように埋め込みを実現するかというテーマだけで沢山の論文があるので省略し、ここではそういう写像があるんだなという程度で進めます。
楕円ElGamal暗号の注意点や、整数値 m の範囲を小さくして代数的に扱いやすくする楕円lifted ElGamal暗号も参照してください。
平文空間と暗号文空間の対応
暗号文空間は G の要素が2個なので G^2 です。
ここで、G^2 の任意の点 (C_1, C_2) をとりましょう。C_2 \in G なので C_2=tP となる t \in [0, r-1] がただ一つ存在します。ここで t を具体的に求める必要はありません。
M:=C_1-tQ と定義します。このようにしたところで、M を乱数 t で暗号化すれば Enc_Q(M;t)=(M+tQ, tP)=(C_1,C_2) となります。
つまり、暗号文空間は G^2 の全体となります（暗号化が全射ということ）。したがって、
Enc_Q : G\times [0, r-1] \ni (M, t) \mapsto (M+tQ, tP) \in G^2
は全単射となり、r^2 個の平文と乱数のペア (M, t) と r^2 個の暗号文 (C_1, C_2) がきれいに1対1に対応しています。そのためDDH仮定の元でIND-CPA安全となりました。
DDH仮定については楕円曲線暗号の安全性 DLPとCDHとDDHを参照してください。
楕円ElGamal暗号の変種1
さて、長くなりましたが準備が終わったので『暗号技術のすべて』p.404で紹介されていた楕円ElGamal暗号の変種1（以下V1方式）です。
暗号化
G の要素 M に対して、t ← [0, r-1] をとり、公開鍵 Q を使って (M+tQ,tP) を計算するところまでは同じで最後の M+tQの「+」を楕円曲線の点の加算ではなく、楕円曲線の定義体(𝔽_p)^2の要素として加算します。紛らわしいのでこちらの演算を+'と表記します。
Enc'_Q(M;t):=(M+'tQ,tP) \in (𝔽_p)^2\times G.
ちなみに『暗号技術のすべて』p.404の鍵生成アルゴリズム動作4と暗号化アルゴリズム動作2の「ℤ_p から x (resp. r) をランダムに選択して」は「ℤ_r から x (resp. r) をランダムに選択して」の間違いですね。
復号
与えらえたc=(C_1, C_2) \in (𝔽_p)^2 \times Gに対して
Dec'_s(c)=C_1-' s C_2 \in G
とする。ここで-'は楕円曲線の点の減算ではなく、(𝔽_p)^2の減算とします。+, - を +', -' に変えても同じものを足して引いたら元に戻るという性質は変わらないので暗号文を復号したらちゃんと元の平文に戻ります。
V1方式の考察
利点
楕円加減算の代わりに、(𝔽_p)^2 の加減算を使うので計算コストが少し小さくなるのが利点です。ただ暗号化・復号ともに計算コストの主要因は楕円スカラー倍算なのでその利点はとても小さい（多分1%ない）です。
欠点その1
それに対して欠点はいくつか考えられます。
平文と乱数のペアの個数は r^2 個で X:=(𝔽_p)^2 の p^2 個よりも少ないです。しかし、X の中でどの点が暗号文として有効なのかは、秘密鍵で s C_2 を計算し、C_1-'s C_2 が G に入っていることを確認するまで分かりません。
通常方式では受け付けた暗号文が G^2 の元であることを公開情報のみですぐ確認できます。それに対して、V1方式は秘密鍵でスカラー倍算をする必要があり、コストがとても高くてDOS攻撃につながる可能性があります。
欠点その2
平文 M を (𝔽_p)^2 の元として計算するということは、暗黙にアフィン座標を仮定しているので無限遠点は表現できません。たとえば「O=(0,0) とする（(0,0) \not\in G を仮定）」というような恣意的な設定が必要です。
欠点その3
IND-CPA安全であるためには、
- 攻撃者が2個の平文M_1, M_2を選んで挑戦者に送り、
- 挑戦者がどちらかの平文を選んで暗号化したものを攻撃者に送り、
- 攻撃者がどちらの平文が選ばれたかを当てる、
というゲームが50%の確率でしか当たらないといけません。
しかし、攻撃者が M_1=0 と M_2(\neq 0) を選んで暗号化したものを返してもらったとします。先程のように O=(0,0) としていたとすると、O を選んでいたら暗号文は楕円の点です。
そうでない M_2 を選ぶとかなりの確率で楕円の点でなくなります。したがって攻撃者はどちらの平文が選ばれたか当てられます。
より一般の M_1 と M_2 を選んだとしても、与えられた暗号文 (C_1, C_2) の C_1 に対して C_1-'M_1 と C_1-'M_2 を計算したら、かなりの確率で片方は楕円の点ではないでしょう。
どちらが選ばれたかばれてしまいます。
というわけでV1方式は安全ではありません。
その他の楕円ElGamal暗号の変種
下記の方法は、いくつかの日本語の書籍で紹介されているそうです（詳細未確認）。
V2方式
そもそも平文を楕円曲線の点にエンコードせずに M=(m_1, m_2) \in (𝔽_p)^2 とする。その後はV1方式と同じ
V3方式
L を r のビット長として、平文を m \in [0, 2^L-1] とする。
暗号化は、t ← [0, r-1] をとり、tQ を計算してその x 座標を (tQ)_x \in 𝔽_p として
Enc_Q(m;t)=((tQ)_x \oplus m, tP) \in [0, 2^L-1] \times G
とする。ここで \oplus は排他的論理和。
c=(v,C_2) の復号は
Dec_s(c)=v \oplus (s C_2)_x = m.
V4方式
排他的論理和ではなく 𝔽_p の乗算を使う。
平文を m \in (𝔽_p)^* として Enc_Q(m;t)=((tQ)_x m, tP) \in 𝔽_p \times G とする。
などの方式があるようです。
V2~V4方式の考察
雑に考えますが、
- V2方式
- 平文空間のサイズ p^2 に対して乱数の個数 p が少ないので乱数で平文の情報を隠しきれない。
- V1方式と同じく (0, 0) とそれ以外の暗号文の区別がつく。
- V3方式
- V2方式と同じく平文空間のサイズ 2^L に対して乱数の個数が少ないので平文の情報を隠しきれない。
- ゲームで平文 0 と 1 を選ぶと暗号文は (tQ)_x か (tQ)_x \oplus 1 のどちらか。
-
𝔽_p の任意の元が楕円曲線の x 座標になるとは限らないので (tQ)_x \oplus 1 が x 座標にならなければ区別できてしまう。
- V4方式
- V3方式とほぼ同様の欠点。m=0 を暗号化できない。
などから、これらの変種は使うべきではないと思われます。
ハッシュ関数と組み合わせたElGamal暗号
V3方式で tQ の x 座標を使ったところが問題だったので、そこをハッシュ関数 H に通した、
Enc_Q(m;t)=(H(tQ) \oplus m, tP)
という方式があります。
ハッシュ関数を適切にとると、DDH仮定にハッシュ関数をからめた問題の困難性を仮定することで、安全なことが知られています。
楕円ElGamal暗号の便利な特長である準同型性を捨てて、IND-CCA2安全な方向に進んだものとしてはPSEC-KEMやCramer-Shoup暗号などがあります。
まとめ
ElGamal暗号の楕円曲線を使ったバージョンには、最後の楕円加算の処理を省く変種がいくつかありますが、使わない方がよいでしょう。
Discussion