初めに
公開鍵暗号の一種である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は公開パラメータです。
0以上r未満の整数の集合を[0, r)、そこからランダムに整数xを選ぶことをx ← [0, r)と書くことにします。
鍵生成
s ← [0, r)をとり、Q:=sP \in Gとします。sが秘密鍵でQが公開鍵です。
暗号化
Gの要素Mに対して、t ← [0, r)をとり、公開鍵Qを使ってEnc(Q, M):=(M+tQ,tP)を暗号文とします。暗号文はGの要素2個で表されます。
復号
暗号文c:=(S,T)に対してDec(s,c):=S-sTとします。
楕円ElGamal暗号
ElGamal暗号の群Gとして、特に楕円曲線の点の巡回群を使ったとき楕円ElGamal暗号といいます。このとき、暗号文Mは整数ではなく群Gの要素、すなわち楕円曲線の点であることに注意してください。
暗号化・復号の妥当性
Mの暗号文c:=Enc(P,M)=(S, T)を復号しましょう。S=M+tQ, T=tP, Q=sPなので
Dec(s, c)=S-sT=(M+tQ)-s(tP)=M+tsP-stP=M
となって元の平文に戻ります（tsP=stPだから）。
安全性
Gの離散対数問題DLPが困難なとき、公開鍵Q=sPと公開パラメータPから秘密鍵sは求められません。
また、暗号文cの2番目の要素T=tPからtも求められないので1番目の要素C_1=M+tQからMを求めるのも難しそうです。より詳しい話はまたの機会にします。
暗号化のときに乱数tを使っています。そのため同じ平文Mを暗号化しても毎回異なる暗号文になります。これは公開鍵暗号の例としてよく紹介されている（が使ってはいけない）素朴なRSA暗号には無い利点です。
楕円ElGamal暗号の注意点
楕円曲線は素数pと有限体𝔽_pの要素a, bを固定して定義します。
楕円曲線の点は、y^2=x^3+ax+bを満たす点集合(x,y)で表現されます。Gが位数rの巡回群なら
G=\Set{P=(x,y) \in {𝔽_p}^2|y^2=x^3+ax+b かつ rP=0}\cup 0
です（0はGの単位元）。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