初めに
公開鍵暗号の一種であるElGamal暗号、特に楕円ElGamal暗号を紹介します。
巡回群
まず用語の説明から始めましょう。G を演算を乗法表記で表す群とします（群の説明は群と楕円曲線とECDH鍵共有参照）。
つまり単位元1があり、掛け算が定義されています。G の要素 g を1個とり、1に g を繰り返し掛けます。g^0=1, g^1=g, g^2,g^3 \dots .
このようにして作った集合 \langle g \rangle:=\Set{1,g,g^2,g^3,\dots} が G に一致するとき、G を巡回群、g を G の生成元といいます。
特に G が有限群（有限集合の群）であるとき、整数 r に対する g^r はどこかで1に戻らないといけません。戻らないと \langle g \rangle が無限集合になってしまうからです。
g^r=1 となる0でない最小の r を g の位数といいます。\langle g \rangle=\Set{1,g,g^2,\dots,g^{r-1}}=G なので g の位数は G の要素数（G の位数という）|G| に等しいです。
位数7の巡回群
巡回群は可換群
G を巡回群とし、g をその生成群とします。すると G の任意の要素は g^i という形で表せます。
すると a, b \in G としたとき、a=g^i, b=g^j と表現できるので ab = g^i g^j = g^{i+j}=g^j g^i = ba となります。つまり任意の巡回群は可換群です。
これ以降、巡回群 G を加法表記（加法群）で表現することにします。生成元も g の代わりに P を使うことにします（単なる記号の入れ換え）。
G の位数を r, G の生成元を P とすると G=\langle P \rangle=\Set{0,P,2P, \dots, (r-1)P}.
ElGamal暗号
G を P を生成元とする位数 r の巡回群とします。G, P, r は公開パラメータです（r は G と P から決まりますが与えておいた方が親切）。
0 以上 r 以下の整数の集合を [0, r]、そこからランダムに整数 x を選ぶことを x ← [0, r] と書くことにします。
鍵生成
s ← [0, r-1] をとり、Q:=sP \in G とします。s が秘密鍵で Q が公開鍵です。
暗号化
G の要素 M に対して、t ← [0, r-1] をとり、公開鍵 Q を使って Enc(Q, M):=(M+tQ,tP) を暗号文とします。暗号文は G の要素2個で表されます。
復号
暗号文 c:=(C_1,C_2) に対して Dec(s,c):=C_1-s C_2 とします。
暗号化・復号の妥当性
M の暗号文 c:=Enc(P,M)=(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
となって元の平文に戻ります（tsP=stP だから）。
安全性
G の離散対数問題DLPが困難なとき、公開鍵 Q=sP と公開パラメータ P から秘密鍵 s は求められません。
また、暗号文 c の2番目の要素 C_2=tP から t も求められないので1番目の要素 C_1=M+tQ から M を求めるのも難しそうです。より詳しい話はまたの機会にします（楕円曲線暗号の安全性 DLPとCDHとDDH参照）。
暗号化のときに乱数 t を使っています。そのため同じ平文 M を暗号化しても毎回異なる暗号文になります。これは公開鍵暗号の例としてよく紹介されている（が使ってはいけない）素朴なRSA暗号には無い利点です。
楕円ElGamal暗号
ElGamal暗号の群 G として、特に楕円曲線の点の巡回群を使ったとき楕円ElGamal暗号といいます。このとき、暗号文 M は整数ではなく群 G の要素、すなわち楕円曲線の点であることに注意してください。
楕円ElGamal暗号の注意点
楕円曲線は素数 p と有限体 𝔽_p の要素 a, b を固定して定義します。
楕円曲線の点は、y^2=x^3+ax+b を満たす点集合 (x,y) （か単位元0）で表現されます。G が位数 r の巡回群なら
G=\Set{P=(x,y) \in {𝔽_p}^2|y^2=x^3+ax+b かつ rP=0}\cup 0
です。G の演算は楕円曲線の点の足し算参照。
暗号化したい数値 m があったとき、それを x 座標とするような点 M \in G がいつも存在するとは限りません。y^2=m^3+am+b となる y が存在するとは限らないのです。
そのため m を G の要素に埋め込むエンコーディングが必要です。たとえば m を少し（たとえば8ビット）左シフトしておき、1増やしながら方程式を満たす値を探す方法があります。Pythonによる実装は次の通りです。
def findPoint(m):
"""
((m<<L)+α, y)となる楕円曲線の点を返す
"""
L=8
for i in range(1<<L):
x = (m<<L) + i
y2 = x**3+a*x+b
if hasSqrt(y2):
if mul((x, y), r) == 0:
return (x, sqrt(y))
else:
raise Exception('not found')
復号するときは点の x 座標を L ビット右シフトして値を取り出します。p が256ビットの素数だとすると v は最大約 256-L ビットの整数となります。有限体の中で平方根を見つける方法についてはまたの機会にします。
この他にもいろいろなエンコーディング方法が提案されています。
まとめ
公開鍵暗号の一つである、ElGamal暗号、特に楕円ElGamal暗号を紹介しました。方式自体はシンプルなのですが実際に使うには細かな約束事や注意が必要になります。
ただこれを変形した楕円Lifted ElGamal暗号は興味深い性質があり、いろいろな応用が考えられています。また紹介しましょう。
Discussion