群と楕円曲線とECDH鍵共有

初めに

ここでは暗号でよく使われる数学的な概念である群を紹介します。
そして楕円曲線暗号のPythonによる実装その1（有限体とECDH鍵共有）で紹介したECDH鍵共有を群の言葉を使って見直します。

掛け算の重要な性質

群(group)とは日常的に使われる掛け算を抽象化した数学用語です。掛け算は $2 \times 3=6$, $4 \times 5 = 20$ といったものです。
掛け算は次の性質を持っています。

1. 3個以上の数字を掛けるとき、掛ける順序を変えても変わらない。例 : $(2 \times 3) \times 4 = 6 \times 4 = 24.$ $2 \times (3\times4) = 2\times 12 = 24.$
2. 数字に1を掛けても値は変わらない。例 : $123 \times 1 = 123.$
3. 逆数を掛けると1になる。例 : $5 \times (1/5) = 1.$

1番目の性質は結合法則が成り立つといいます。これはかなり重要な性質で、たとえばべき乗 $3^5$ を計算するときに

$$3^5=(((3\times 3)\times 3)\times 3)\times 3 = ((9\times 3)\times 3)\times 3 = (27\times 3)\times 3=81\times 3=243$$

と前から順に計算しても、

$$3^5=((3\times 3)\times (3\times 3))\times 3 = (9\times 9)\times 3 = 81\times 3=243$$

と計算しても結果は同じとなり、楽に計算できる方法を選べます。

2番目の性質を「演算に対する単位元1がある」といいます。

3番目の性質は「○倍する」というある操作に対して、それをキャンセルする操作があるという意味です。
暗号では暗号化した後、元の値を復号しなくてはいけません。そのときにキャンセルに相当する操作がよく使われます。

群の定義

前節の性質を定式化します。
集合 $G$ と $G$ の任意の要素 $a$, $b$ に対して $G$ のある値が決まる関数 $f:G \times G \rightarrow G$ に対して

1. （結合法則）$a$, $b$, $c \in G$ に対して $f(f(a,b),c)=f(a,f(b,c))$ が成り立つ。
2. （単位元の存在）ある $e \in G$ が存在し、任意の $a$ に対して $f(a,e)=f(e,a)=a$ が成り立つ。
3. （逆元の存在）任意の $a \in G$ に対して、ある $r \in G$ が存在し、 $f(a,r)=f(r,a)=e$ が成り立つ。この $r$ を $a$ の逆元といい、 $a^{-1}$ と書く。

$f$ を使って書くのがわずらわしいので $f(a, b)$ のことを$a$ と $b$ の積と呼び、$a\cdot b$ とか $ab$ と書くと、それぞれ成り立って欲しい式は

1. $(ab)c = a(bc).$
2. $ae = ea = a.$
3. $ar=ra=e.$

となります。 $G$ の要素を元ともいいます。単位元 $e$ を1と書くことも多いです。
集合や演算の中身を気にせず、上記性質を満たすものがあればそれを全て同じ群という言葉で扱おうという意図です。
なお、単位元はある特定の要素が全ての要素に対して成り立つ性質、逆元は、要素それぞれに対して決まり、全ての要素に対して逆元の存在を要請することに注意してください。

群の例

0以外の分数の集合

$G$ を0以外の分数の集合とし、演算を通常の積で定義します。0は逆数が存在しないので除外しています。すると結合法則が成り立ち、$1 \in G$ が単位元、任意の $a \in G$ に対して逆数 $1/a$ が $a$ の逆元です。

実数値の2x2行列で逆行列が存在するもの全体の集合

演算を行列の掛け算、単位元は単位行列、逆元は逆行列とすると群となります（ここで詳細は確認しません）。この場合、行列の積 $ab$ は $ba$ と同じとは限らないので注意が必要です。

整数の集合 ℤ

整数の集合に演算を普通の掛け算、1を単位元とすると結合法則と単位元の性質は満たします。しかし、 $\pm 1$ 以外の逆数は存在しないため群にはなりません。
代わりに演算を掛け算ではなく足し算（ $f(a,b)=a+b$ ）、単位元を0、任意の $a \in ℤ$ に対して逆元を $-a$ とすると群になります。

1. $f(f(a,b),c)=f(a+b,c)=(a+b)+c=a+(b+c)=f(a, b+c)=f(a,f(b,c)).$
2. $f(a,0)=a+0=0+a=f(0,a).$
3. $a+(-a)=(-a)+a=0.$

このように群は集合と演算のセットで決まります。同じ集合であっても演算の決め方で群になったり、ならなかったりします。
なお、 $a$ と $b$ の足し算を群の演算の積 $ab$ と表記すると混乱しやすいので、演算自体を $a+b$ を書いて加法群と呼ぶことがあります。

可換群

普段扱う掛け算は順序を入れ換えても同じです。
$ab = ba.$
しかし、前節の行列の群の例のように、群の定義に演算の順序を入れ換えても同じという性質（これを可換という）は入っていません。
群の全ての要素について $ab=ba$ が成り立つとき可換群、あるいはアーベル群といいます。整数の集合に足し算で演算を定義した群も可換群です。暗号では可換群を扱うことが多いです。

楕円曲線の点の集合

楕円曲線上の点の集合 $G$ に対して楕円曲線の点の足し算を演算とすると $G$ は加法群になります（演算が可換なので）。この場合整数の加法群と同様、単位元は0、$a$ の逆元は $-a$ です。

なお、先程の整数の加法群と逆に、楕円曲線の点 $a$, $b$ の「足し算」を $ab$ と掛け算表記で扱う場合があります。この場合は単位元（無限遠点0）を $1$ や $e$ と書き、逆元も $-a$ ではなく $a^{-1}$ と表記します。乗法群ということがあります。
楕円曲線の点の集合を群として扱うとき、加法表記と乗法表記のどちらを採用するかは論文や本によって異なるので混乱しないようにしてください。
ただ、その違いは単なる言葉や表記の問題です。本質は演算が群の定義を満たすかどうかです。

べき乗と離散対数問題

群の結合法則により、 $n$ 個の $a$ を掛けた値 $a^n = a \times \cdots \times a$ は前から順に掛け算しなくても、 $a$, $a^2$, $a^4=({a^2})^2$, $a^8=({a^4})^2, \cdots$ と2のべき乗の値を計算して必要なものを掛けることで $\log(n)$ の回数で計算できます。
加法群としての楕円曲線の点 $P$ を $n$ 倍するときも $P$, $2P$, $4P=2(2P)$, $8P=2(4P), \cdots$ を計算して必要なものを足して計算しました（楕円曲線の点の整数倍参照）。
一般に（可換群とは限らない）群 $G$ の要素 $a$ に対して $a^n$ は $\log(n)$ のオーダーで計算できます。

逆に「群 $G$ の要素 $a$, $b=a^n$ が与えられたときに、 その整数 $n$ を求めよ」という問題を離散対数問題DLPといいます。
群 $G$ が分数の集合や整数の集合を加法群とみなしたとき、DLPは容易に解けます。
しかし、楕円曲線のパラメータを適切に選んだとき、現在のコンピュータではDLPを解くのは不可能です（と信じられています）。

DH鍵共有

離散対数問題が困難な群 $G$ に対してDH鍵共有は次のように記述出来ます。

1. $G$ の要素 $g$ で $g^n$ のDLPが困難なものを選び固定して公開する。
2. アリスは秘密の整数 $a$ を選び、 $g^a$ を計算してボブに渡す。
3. ボブは秘密の整数 $b$ を選び、 $g^b$ を計算してアリスに渡す。
4. アリスはボブがからもらった $g^b$ を $a$ 乗して $({g^b})^a=g^{ab}$ を計算する。
5. ボブはアリスがからもらった $g^a$ を $b$ 乗して $({g^a})^b=g^{ab}$ を計算する。

$({g^b})^a=({g^a})^b$ が成り立つところでも結合法則を利用しています。DLPの困難さから、 $g^a$ や $g^b$ を第三者に盗聴されても $a$, $b$, $g^{ab}$ は分からないということを利用して秘密に鍵共有します（厳密にはDLPの困難さの仮定ではなくDH仮定ですが）。

暗号で使われるDH鍵共有

新しいDLP困難な群を構成できれば新しいDH鍵共有ができます。
昔は大きな素数 $p$ で割った余りの集合の部分集合を乗法群とみなしてDH鍵共有を構成しました。最近のTLSでは楕円曲線の点の集合を加法群とみなしてDH鍵共有するECDH鍵共有が主流です。
量子コンピュータが実用化されても破れないとされている鍵共有方式の一つにCSIDHという方式があります。これはDLPが困難な群を用いているのではないのですが、楕円曲線に対する作用と呼ばれるある種の計算が似た性質を持つことを利用しています。

まとめ

掛け算を抽象化した群や群に対する離散対数問題DLPという概念を紹介しました。
DLPが困難な群を用いるとDH鍵共有を構成できます。楕円曲線暗号の点集合に対するECDH鍵共有が主流ですが、より安全な群の構成も研究されています。