No.316 - 高校数学で理解する楕円曲線暗号の数理(2) [科学]
\(\newcommand{\bs}[1]{\boldsymbol{#1}} \newcommand{\mr}[1]{\mathrm{#1}} \newcommand{\br}[1]{\textbf{#1}} \newcommand{\ol}[1]{\overline{#1}} \newcommand{\sb}{\subset} \newcommand{\sp}{\supset} \newcommand{\al}{\alpha} \newcommand{\sg}{\sigma}\newcommand{\cd}{\cdots}\)
16. 楕円曲線上の点
有限体 \(\bs{F}_p\) の元 \(x\) と \(y\) のぺア \((x,\:y)\) の集合を \(\bs{F}_p^{\:2}\) と記述します。集合 \(\bs{F}_p^{\:2}\) の元で楕円曲線上の "点" はどれだけあるでしょうか。まず、楕円曲線の式を満たす \(\bs{F}_p^{\:2}\) の元がどのように計算できるかを調べます。
平方数と平方根
楕円曲線の式を、
と書くとき、\(z\)(\(z\neq0\))が \(\bs{F}_p\) での平方数なら、\(y\) の解が2つ求まります。ここで、次の命題が成立します。
\(\bs{F}_p\) で考えているので「平方数」と書きましたが、整数の世界では平方剰余です。つまり、\(x^2=a\:(\mr{mod}\:n)\) となるような \(x\) が存在する \(a\) が「\(n\) を法とする平方剰余」です。16.1 の証明ですが、12.1(No.313)により、\(z\) は \(\bs{F}_p^{*}\) の生成元(の一つ)を \(g\) として、
と表現できます。つまり、命題の条件は、
です。このとき \(k\) は偶数のはずです。なぜなら、もし \(k\) が奇数だとすると、\(k\dfrac{p-1}{2}\) は \(p-1\) で割り切れないので、
と表現できます。すると、
となり、\(g^t=1\:(1\leq t < p-1)\) になりますが、これは \(g\) が生成元であることと矛盾します。従って \(k\) は偶数です。そうすると \(k=2m\) とおいて、
となり、\(z\) は平方数になります。逆に、
と表現されるとすると、フェルマの小定理 3.1をつかって、
となり、\(\bs{z^{\frac{p-1}{2}}=1}\) と 「\(\bs{z}\) が平方数」は同値であることが証明できました。
なお、フェルマの小定理によって、 \((z^{\frac{p-1}{2}})^2=1\) なので、\(z^{\frac{p-1}{2}}\) は \(1\) か \(-1(=p-1)\) のどちらかです。従って、
ということになります。「平方数ではない」は、整数の世界では「平方非剰余」です。
平方根を求める
\(z\) は平方数だとわかったとき、実際に \(\bs{F}_p\) で \(y\)(= \(z\) の平方根)を求める手段が必要になります。整数であれば平方根を求めるのは容易ですが、\(\bs{F}_p\) ではそうはいきません。特に、楕円曲線暗号で使われる \(p\) は10進数で数10桁以上の巨大素数なので、総当たりで求めたり、解の存在範囲を限定していって求めるわけにはいかないのです。以下が解を求めるアルゴリズムです。
\(p\equiv3\:(\mr{mod}\:4)\) の場合
この場合は
が解の一つとなります(もう一つの解は \(-y\) で、つまり \(p-y\))。確認してみると、
となって、確かに \(y\) が解であることがわかります。
\(p\equiv1\:(\mr{mod}\:4)\) の場合
この場合は「トネリ-シャンクスのアルゴリズム」で解を求めることができます(Tonelli は19世紀イタリア、Shanks は20世紀米国の数学者)。以下のアルゴリズムは Wikipedia を参考にしました。
\(p\equiv1\:(\mr{mod}\:4)\) の場合、\(p-1\) は \(4\) の倍数です。\(p-1\) を素因数分解したときの \(2\) のべき乗を \(S\) とすると、\(p-1\) は、
と表現できます。ここで、\(\bs{F}_p\) において平方数ではない数 \(w\) を(どれでもよいから)一つ選びます。つまり、
\(w^{\frac{p-1}{2}}=-1\)
となる数 \(w\) です。\(\bs{F}_p\) においては平方数とそうでない数が半々なので、この選択は容易です。次に、4つの数を、
と定義します。このように定義すると、\(c_0,\:\:t_0,\:\:y_0\) は次の「性質」を持ちます。
\(\begin{eqnarray}
&&\:\:(c_0)^{2^{S_0-1}}&=(w^Q)^{2^{S-1}}\\
&&&=w^{Q\cdot2^{S-1}}\\
&&&=w^{\frac{p-1}{2}}\\
&&&=-1\\
\end{eqnarray}\)
\(\begin{eqnarray}
&&\:\:(t_0)^{2^{S_0-1}}&=(z^Q)^{2^{S-1}}\\
&&&=z^{Q\cdot2^{S-1}}\\
&&&=z^{\frac{p-1}{2}}\\
&&&=1\\
\end{eqnarray}\)
\(\begin{eqnarray}
&&\:\:y_0^{\:2}&=\left(z^{\frac{Q+1}{2}}\right)^2\\
&&&=z^{Q+1}\\
&&&=t_0\cdot z\\
\end{eqnarray}\)
まとめると、
です。もし、\(t_0=1\) なら、3番目の式により \(z\) の平方根は \(y_0\) および \(-y_0\:(=p-y_0)\) ですが、そうはなりません。\(S_0=1\) なら \(t_0=1\) となりますが、\(S_0=S\geq2\) だからです。
そこで、\(\{\:S_i,\) \(c_i,\) \(t_i,\) \(y_i\:\}\) の4数の組の列 \((i=0,\:1,\:2,\:\cd\:)\) を順次作り、上記の「性質」を保ちつつ、ある時点で \(t_i=1\) になることを目指します。\(t_i=1\) になったとしたら、そのときの \(\pm y_i\) が \(z\) の平方根です。\(i=1\) に対応する4数の組は次のようにします。
このように定義すると、次のように「性質」が保たれることが分かります。
\(\begin{eqnarray}
&&\:\:(c_1)^{2^{S_1-1}}&=\left((c_0)^{2^{S_0-S_1}}\right)^{2^{S_1-1}}\\
&&&=(c_0)^{2^{S_0-1}}\\
&&&=-1\\
\end{eqnarray}\)
\(\begin{eqnarray}
&&\:\:(t_1)^{2^{S_1-1}}&=(t_0)^{2^{S_1-1}}\cdot\left((c_0)^{2^{S_0-S_1}}\right)^{2^{S_1-1}}\\
&&&=(t_0)^{2^{S_1-1}}\cdot(c_0)^{2^{S_0-1}}\\
&&&=-(t_0)^{2^{S_1-1}}\\
\end{eqnarray}\)
ここで、最後の式からマイナスを取って、
\((t_0)^{2^{S_1-1}}=X\)
とおくと、\(S_1\) の定義から \((t_0)^{2^{S_1}}=1\) なので、
\(X^2=(t_0)^{2^{S_1}}=1\)
となり、\(X\) は \(\bs{F}_p\) における方程式 \(X^2=1\) の解です。つまり、
\(X=1,\:-1\)
です。ところが \(X=1\) とすると、
\((t_0)^{2^{S_1-1}}=1\)
となりますが、\(S_1\) は \(0 < S_1 < S_0\) で \((t_0)^{2^{S_1}}=1\) を満たす最小の数と定義したにも関わらず、\(S_1\) より小さい \(S_1-1\) が定義を満たすことになってしまって矛盾します。従って \(X=-1\) であり、結局、
\(\begin{eqnarray}
&&\:\:(t_1)^{2^{S_1-1}}&=-X\\
&&&=1\\
\end{eqnarray}\)
となります。さらに、
\(\begin{eqnarray}
&&(y_1)^2&=(y_0)^2\cdot\left((c_0)^{2^{S_0-S_1-1}}\right)^2\\
&&&=t_0\cdot z\cdot(c_0)^{2^{S_0-S_1}}\\
&&&=t_0\cdot(c_0)^{2^{S_0-S_1}}\cdot z\\
&&&=t_1\cdot z\\
\end{eqnarray}\)
と計算できます。まとめると、
となって、\(i=1\) においても「性質」が成り立つことが分かりました。ここで仮に、\(\bs{t_1=1}\) なら \(\bs{(y_1)^2=z}\) となって、\(\bs{z}\) の平方根は \(\bs{\pm y_1}\) になります。
この計算で重要なことは \(S_1 < S_0\) であり、同様のやり方で \(\{\:S_i,\) \(c_i,\) \(t_i,\) \(y_i\:\}\) \((i=0,\:1,\:2,\:\cd\:)\) の4数の組の列を順次作っていくと、\(\bs{S_i}\) は単調減少することです。さらに、\(S_i=1\) なら \(t_i=1\) になることもポイントです。
以上のプロセスを進めて、\(i=0,\:1,\:2,\:3,\:\cd\) のとき、
と定義すると、
の「性質」が成り立つことを数学的帰納法で証明します。\(i=0,\:1\) で成り立つことは上で既に確認しました。\(i\) のときに「性質」が成り立つと仮定すると、\(i+1\) でも成り立つことが次のように分かります。基本的には上の \(i=1\) での計算と同じです。
\(\begin{eqnarray}
&&\:\:(c_{i+1})^{2^{S_{i+1}-1}}&=\left((c_i)^{2^{S_i-S_{i+1}}}\right)^{2^{S_{i+1}-1}}\\
&&&=(c_i)^{2^{S_i-1}}\\
&&&=-1\\
\end{eqnarray}\)
\(\begin{eqnarray}
&&\:\:(t_{i+1})^{2^{S_{i+1}-1}}&=(t_i)^{2^{S_{i+1}-1}}\cdot\left((c_i)^{2^{S_i-S_{i+1}}}\right)^{2^{S_{i+1}-1}}\\
&&&=(t_i)^{2^{S_{i+1}-1}}\cdot(c_i)^{2^{S_i-1}}\\
&&&=-(t_i)^{2^{S_{i+1}-1}}\\
\end{eqnarray}\)
ここで、
\((t_i)^{2^{S_{i+1}-1}}=X\)
とおくと、\(S_{i+1}\) の定義によって \((t_i)^{2^{S_{i+1}}}=1\) なので、
\(X^2=(t_i)^{2^{S_{i+1}}}=1\)
となり、\(X\) は \(\bs{F}_p\) における方程式 \(X^2=1\) の解です。つまり、
\(X=1,\:-1\)
です。ところが \(X=1\) とすると、
\((t_i)^{2^{S_{i+1}-1}}=1\)
となりますが、\(S_{i+1}\) は \(0 < S_{i+1} < S_i\) で \((t_i)^{2^{S_{i+1}}}=1\) を満たす最小の数としたにも関わらず、\(S_{i+1}\) より小さい \(S_{i+1}-1\) が定義を満たすことになってしまい、矛盾します。従って \(X=-1\) であり、
\(\begin{eqnarray}
&&\:\:(t_{i+1})^{2^{S_{i+1}-1}}&=-X\\
&&&=1\\
\end{eqnarray}\)
です。また、
\(\begin{eqnarray}
&&\:\:(y_{i+1})^2&=(y_i)^2\cdot\left((c_i)^{2^{S_i-S_{i+1}-1}}\right)^2\\
&&&=t_i\cdot z\cdot(c_i)^{2^{S_i-S_{i+1}}}\\
&&&=t_i\cdot(c_i)^{2^{S_i-S_{i+1}}}\cdot z\\
&&&=t_{i+1}\cdot z\\
\end{eqnarray}\)
と計算できます。まとめると
となり、\(i\) のときに成り立つと仮定すると \(i+1\) でも成り立つことが分かりました。これで、\(i=0,\:1,\:2,\:3,\:\cd\) で成り立つことが数学的帰納法で証明できました。
\(i=0,\:1,\:2,\:3,\:\cd\) のどこかで \(t_i=1\) となれば、そのときの \(\pm y_i\) が \(z\) の平方根です。\(S_i\) は単調減少であり、かつ、\(S_i=1\) なら \(t_i=1\) です。\(t_i=1\) となる \(i\) がなかなか見つからなくても、\(S_i\) が \(1\) まで減少すれば必ず見つかるので、\(z\) の平方根が求まります。
このアルゴリズムを実験してみます。4 で割って1余る素数 \(p\) として、 \(p=2^S+1\) 型の素数を選びます。\(S=8\) のとき \(p=257\) は素数なので、
\(p=257,\:\:Q=1,\:\:S=8\)
とおきます。計算してみると \(\bs{F}_{257}\) において \(11,\:13\) は平方数です。また、平方数でない数として \(3\) を選ぶことができます。そこでまず、
\(p=257,\:\:Q=1,\:\:S=8,\)
\(z=11,\:\:w=3\)
とおくと、
\(\begin{eqnarray}
&&\:\:S_0&=S&=8\\
&&\:\:c_0&=w^Q&=3\\
&&\:\:t_0&=z^Q&=11\\
&&\:\:y_0&=z^{\frac{Q+1}{2}}&=11\\
\end{eqnarray}\)
が初期値です。ここからアルゴリズムに沿って \(\{\:S_i,\) \(c_i,\) \(t_i,\) \(y_i\:\}\) \((i=1,\:2,\:\cd\:)\) を計算してみると、結果は、
となり、\(\bs{F}_{257}\) における \(11\) の平方根の1つは \(221\) と求まりました。もう1つは \(257-221=36\) です。実際、
\(221^2=48841=190\cdot257+11\)
\(\phantom{2}36^2=\phantom{4}1296=\phantom{25}5\cdot257+11\)
なので正しい結果です。\(z=13\) もやってみると、
となり、\(\bs{F}_{257}\) における \(13\) の平方根(の1つ)は \(28\) です。
\(28^2=784=3\cdot257+13\)
であり、アルゴリズムの確認ができました。
楕円曲線上の点の総数
\(\bs{F}_p\) 上の楕円曲線、\(E(a,\:b,\:p)\) の点の数がどの程度になるのでしょうか。以降、群 \(E(a,\:b,\:p)\) の元の数(群位数)を \(\#E\) と書きます。前回の No.315「高校数学で理解する楕円曲線暗号の数理(1)」の最後にあげた例だと、
でした。この \(\#E(a,\:b,\:p)\) を評価する式があります。「ハッセの定理」です(Helmut Hasse は20世紀ドイツの数学者)。この定理によると、
であり、\(\#E\) は \(p+1\) の周辺、\(\pm2\sqrt{p}\) の範囲です。この意味を考えてみます。\(\bs{F}_p\) 上の楕円曲線を
で表わし、\(\bs{F}_p\) において \(z\) を \(0\) から \(p-1\) まで振ったときの \(y^2=z\) の解の総数を求めます。\(z\) を、\(\bs{F}_p^{*}\) の生成元 \(g\) を使って、
と表すと、
となり、\(\bs{F}_p^{\:2}\) における解、\((z,\:y)\) の総数は \(p\) となります。では、\(\bs{F}_p^{\:2}\) における楕円曲線上の点、\((x,\:y)\) の総数はどうなるでしょうか。\(x\) が \(\bs{F}_p\) の全ての元に渡るとき、\(z\) が \(\bs{F}_p\) で均等にバラつくとは限りません。しかし \((x,\:y)\) の総数は「だいたい \(p\) に近い値」だと考えられます。
つまり、群 \(E(a,\:b,\:p)\) の元で、零元 \(\mathcal{O}\) 以外の \(\bs{F}_p^{\:2}\) に属するものは、だいたい \(p\) 個あると考えられる。従って \(\#E\) は 零元 \(\mathcal{O}\) を含んで \(p+1\) に近い値だと考えられます。これが「ハッセの定理」の直感的理解です。
別の観点から言うと、任意に選んだ \(x\) に対して、もし \(z\) が平方数なら \(y\) が2つ存在し、楕円曲線上の点が2つ求まります。ハッセの定理から言えることは、そうなる確率は、任意の \(x\) についてほぼ \(0.5\) ということです。\(p\) が大きくなると、\(p+1\) に対する \(2\sqrt{p}\) の比率は極めて小さくなるからです。
\(\#E\) を具体的に求めるアルゴリズムは、1985年にオランダ出身の数学者、レネ・ショーフ(Rene Schoof。英語読みでスクーフとも書かれる)が開発しました。その「ショーフのアルゴリズム」は、数学用語で言うと最初の「決定論的多項式時間アルゴリズム」です。平たく言うと「計算結果が100%正しいと数学的に保証される(=決定論的)計算可能な(=多項式時間)アルゴリズム」です。「ショーフのアルゴリズム」の具体的内容は、ここでは割愛します。
17. 楕円曲線暗号
楕円曲線暗号を構成する上で必要になるのが、有限群における「位数」の概念です。次の位数の話はすべての有限群に共通するので、群の演算を乗法的に書くことにします(掛け算、冪乗、単位元 \(e\)、などの記法を使います)。No.315 でやったように、演算を加法と考えても全く同じことになります。
位数
元の数が有限個の群 \(G\) を「有限群」といい、その元の個数を「群位数(group order)」と呼びます。群位数を \(|G|\) と表します。群の演算則だけから次のことが言えます。
単位元 \(e\) でない群 \(G\) の元を \(a\) とします。\(a\) の冪乗 \(a^n(1\leq n)\) の \(n\) を増やしていくと、ある時点で \(a^n=e\) となります。その理由ですが、
という \(|G|\) 個の元を考えてみます。もし \(|G|\) 個が全て相異なると、どれかが \(e\) のはずです。全てが相異なる元ではないとき、
となったとすると、両辺に \(a\) の逆元を \(i\) 回掛けて、
が得られます。\(1\leq j-i < |G|\) なので、この範囲に \(e\) があります。そこで、つぎのように元 \(a\) の位数を定義できます。
さらに、元の位数については次の命題が成り立ちます。
これはラグランジュの定理と呼ばれるものです。この定理が成り立つ理由は次の通りです。有限群 \(G\) の任意の元を \(a\) とし、集合 \(A\) を、
とします。集合 \(A\) の元は全て相異なります。なぜなら、もし、
となったとすると、両辺に \(a\) の逆元を \(i\) 回掛けて、
となり、\(d\) が \(a^d=e\) となる最小の数であるという位数の定義に反するからです。さらに、集合 \(A\) の任意の元の逆元は集合 \(A\) に含まれます。つまり、\(a^d=e\) なので \(a^j(1\leq j < d)\) に対して \(a^{d-j}(1\leq d-j < d)\) が逆元です(ということは集合 \(A\) もまた群であり、これを \(G\) の部分群と言います)。
集合 \(A\) が \(G\) の全ての元を尽くしているなら 17.2 は成立します。そこで、集合 \(A\) に含まれない \(G\) の元があったとし、それを \(b_1\) とします。集合 \(A\) の全ての元に左から \(b_1\) を掛けて、集合 \(B_1\) を作ります。つまり、
です。集合 \(A\) の元は全て相異なるので、集合 \(B_1\) の元も全て相異なります。さらに、集合 \(B_1\) の元で集合 \(A\) の元と同じものはありません。なぜなら、もし、
だとすると、\(a^i\) の逆元、\(a^{d-i}\)を右から掛けて、
となりますが、\(1\leq j-i < d\) なので、これは \(b_1\) が集合 \(A\) の元であることを意味していて仮定に反します。つまり、集合 \(B_1\) の元で集合 \(A\) の元と同じものはありません。
集合 \(A\) と \(B_1\) で \(G\) の元の全てを尽くしているなら、\(2d=|G|\) となって 17.2 は証明できたことになります。そうではない場合、集合 \(A\) と \(B_1\) に含まれない \(G\) の元の一つを \(b_2\) として、集合 \(B_2\) を、
と定義します。そうすると先ほど同じように、集合 \(B_2\) の元は全て相異なり、かつ、集合 \(A\) との重複はありません。さらに、集合 \(B_2\) の元は集合 \(B_1\) の元とも重複しません。なぜなら、もし、
だとすると、\(a^i\) の逆元、\(a^{d-i}\)を右から掛けて、
となりますが、\(1\leq j-i < d\) なので、\(b_2\) が 集合 \(B_1\) の元という意味になり仮定に反します。つまり、集合 \(B_2\)の元は集合 \(B_1\) の元と重複しません。
以上の操作は \(G\) の元が残っている限り \(B_3B_4\:\cd\) と続けられます。そしてある時点で 残っている \(G\) の元がちょうど切りのよいところで無くなるはずです。\(B_{n-1}\) まで作ったときに \(G\) の元の全てを尽くしたとしたら、\(n_d=|G|\) です。これで 17.2 が証明できました。17.2 から直ちに次の2つが結論づけられます。
これは、群位数 \(|G|\) が 元 \(a\) の位数の倍数なのでそうなります。\(p\) を素数とし、\(G\) が \(p\) 未満の自然数からなる乗法群 \(\bs{F}_p^{*}\) だとすると、\(|G|=p-1\) なので、フェルマの小定理( 3.1 )そのものです。
また、\(n\) 未満の自然数で \(n\) と互いに素なものの集合を \(G\) とすると、\(G\) は \(\mr{mod}n\) の乗算に関して閉じた集合になり、逆元も定義できるので(2.3 参照)、群となります(= 既約剰余類群)。オイラー関数を用いると \(|G|=\varphi(n)\) と表せて、オイラーの定理( 7.1 )になります。
つまり 17.3 は、フェルマの小定理の一般化であると同時に、フェルマの小定理を一般化したオイラーの定理をさらに一般化したものと言えるでしょう。
素数の約数は \(1\) と素数自身しかないので、単位元以外の元の位数は群位数に等しくなります。従って、群位数が素数の群では任意の元 \(a\) の冪乗が群全体に "バラける" ことになります。
楕円曲線暗号の構成
スカラー倍
ここから具体的な楕円曲線暗号のしくみに入ります。楕円曲線上の \(\bs{F}_p^{\:2}\) の点と零元 \(\mathcal{O}\) が作る加法群を \(E(a,\:b,\:p)\) とし、その群位数を \(\#E\) と書きます。楕円曲線暗号では \(E(a,\:b,\:p)\) における「スカラー倍」の演算を利用します。
楕円曲線上の \(\bs{F}_p^{\:2}\) の点の一つを \(G=(G_x,\:G_y)\) とし、\(d\) を \(G\) の位数、\(n\) を \(1\leq n\) の整数とします。\(G\) の \(n\) 倍(=スカラー倍)を \(nG\) と書き、
と定義します。この定義から、
です。また、\((dk)G=\mathcal{O}\) \((k=1,\:2,\:3,\:\cd)\) です。スカラー倍は「倍」という名前がついているため、整数と楕円曲線上の点の掛け算のように誤解しそうですが、掛け算ではありません。
です。従って、\(n,\:\:m\) を整数とすると次のような式が成り立ちます。
\((1)\) 式には、整数の乗算とスカラー倍が混在しています。また \((2)\) 式に整数の加算の \(+\) と、楕円曲線上の点の加算の \(+\) が混在していますが、意味するところは明確でしょう。さらに、
も成り立ちます。つまり、スカラー倍の "スカラー" の部分が式の場合、\(d\) を法とする演算でよいことになります。\(d\) は素数なので \(d\) を \(q\) と書くと、 "スカラー" 部分の式は有限体 \(\bs{F}_q\) での演算と言えます。たとえば \((4)\) は、
と記述できます。
\(nG\) を求める計算は、\(E(a,\:b,\:p)\) の2倍式と加法式を使って可能です。例として \(133G\) の場合だと、\(133=2^7+2^2+1\) なので、
となります。つまり、\(E(a,\:b,\:p)\) の2倍式を7回使って、
と順次計算し、加法式を2回使うと \(133G\) が求まります。これは \(n\) がたとえ巨大数であっても可能です。\(2^{256}\) は10進数で約80桁(256ビット)の巨大数ですが、それでも256回程度の2倍算と最大で256回程度の加算をすれば \(nG\) が求まります。このあたりは 4.2 の「冪剰余の計算アルゴリズム」と同じです。もちろん冪剰余と違って、2倍算も加算も単純な掛け算ではありません。\(E(a,\:b,\:p)\) の群演算は、定義式どおりの少々ややこしい式です。しかし計算が可能なことは確かです。
離散対数
スカラー倍の演算を、
\(P=nG\)
とします。上に書いたように、この計算は高速に可能ですが、その逆、つまり \(P\) と \(G\) を知って \(n\) 求めるのは困難になります。この \(n\) を求める問題を、加法群 \(E(a,\:b,\:p)\) における「離散対数問題」と呼びます。離散対数問題を解くのが不可能になるのは、\(G\) の位数 \(d\) が10進数で数10桁以上といった巨大数の場合です。その場合、\(P\) は \(d\) 種のバリエーションをとるので、\(n\) を求めるのは不可能になります。
位数 \(d\) が巨大数である \(G\) を求める方法の一つは、\(p\) を巨大な素数とし、群位数 \(\#E\) も素数であるような \(E(a,\:b,\:p)\) を選ぶことです。そうすると 17.4 により、零元 \(\mathcal{O}\) 以外の \(E(a,\:b,\:p)\) の全ての元の位数 \(d\) は \(\#E\) になり、その \(\#E\) は \(p+1\) の近辺にあるので、\(G\) をどのように選ぼうとも位数 \(d\) は巨大素数になります。
\(\#E\) が素数である \(E(a,\:b,\:p)\) では、任意の元 \(P\) と \(G\) について、\(nG=P\) となる \(n\) が唯一存在することになります。このことを、
と書くと、\(G\) は実数における通常の対数の "底(base)" に相当します。\(G\) は \(E(a,\:b,\:p)\) の元 = \(\bs{F}_p^{\:2}\) の元なので、\(G\) を「ベースポイント(base point)」と呼びます。このペースポイントを含め、楕円曲線暗号では、
が公開されます。そして暗号化通信では、\(d\) より小さい数 \(k\) をランダムに選び
とします。公開鍵だけを知っても秘密鍵は計算できない。これが楕円曲線暗号の原理です。なお、 \(\#E\) が 素数でなくても、位数 \(d\) が巨大素数である \(G\) を選ぶことで、楕円曲線暗号は成立します。
スカラー倍のイメージをつかむため、\(p\) がごく小さい数の場合で実験してみます。計算してみると、\(p=29,\:\:a=-1(=28),\:\:b=1\) のとき \(\#E=37\) となって、群位数が素数になります。\(y^2=x^3-x+1\) の解の一つは \((0,\:1)\) なので、これをベースポイント \(G\) としてスカラー倍を順次計算してみると次の通りとなります。
群位数が素数なので \(G\) の位数は \(37\) となり、群位数と一致します。この計算を \(\bs{F}_p^{\:2}\) の平面に表示すると次の通りです。\(G\) と \(36G\) は赤丸、\(2G\) ~ \(35G\) は黒丸です。矢印は加算を示し、赤矢印は \(G+G\) と \(35G+G\) の加算です。
スカラー倍を繰り返すごとに "楕円曲線" 上の合計\(36\)点を通り、それが乱雑に変化することが分かります。
振り返ってみると、RSA暗号(No.311)の安全性は巨大数の因数分解の困難性に依存しているのでした。またディフィー・ヘルマンの鍵交換(No.313)は、乗法群 \(\bs{F}_p^{*}\) における離散対数問題を解くことの困難性に依存しています。これらに使われる演算はいずれも整数の乗除算です。それに対して楕円曲線暗号に使われるのは、整数の乗除算よりは遙かに複雑な、楕円曲線上の加法群における「加算」です。ここに楕円曲線暗号の解読しにくさの要因があります。
実用的な楕円曲線暗号で公開するパラメータをどうやって作るか、その一例をあげます。
\(\#E\) が素数なので、\(G\) の位数 \(d\) は \(\#E\) に等しくなります。なお、\(\#E\) がたまたま \(p\) と一致すると離散対数問題が解けることが分かっているので、③ でそのようなケースを排除しておきます。
この決め方では、群位数 \(\#E\) の計算と素数判定を繰り返すことになり、多大な計算時間がかかることは想像に難くありません。しかしパラメータは1度計算すれば暗号通信の仕様として公開し、皆がそれを使えばいいわけです。最初の1回だけの計算時間より、その後の通信の安全性の方が重要です。
楕円曲線暗号のパラメータの一例を次に掲げます。secp160r1 という名称で公開されているパラメータです。群位数 \(\#E\:( > p)\) は素数です。\(p,\:\#E\) ともに10進で49桁の数です。
secp160r1
ちなみに、計算してみると、
\(\dfrac{\#E-(p+1)}{2\sqrt{p}}\fallingdotseq0.978\)
であり、\(\#E\) は「ハッセの定理」の上限付近にあります。
楕円曲線暗号版ディフィー・ヘルマンの鍵交換(ECDH)
楕円曲線暗号とは、以上のような「有限体上の楕円曲線が構成する加法群を利用した暗号方式」の総称です。その例として、ディフィー・ヘルマンの鍵共有(= DH、No.313「高校数学で理解する公開鍵暗号の数理」参照)を楕円曲線暗号で実現できます(ECDH と略称される)。鍵共有のプロセスは次のように進みます。しかるべき「公開鍵センター」が、皆が使う公開鍵として、
をオープンにして(暗号通信の仕様書として公開して)おきます。以下のスカラー倍演算はすべて \(\bs{F}_p\) で行います。Alice と Bob が秘密鍵を共有したい場合、
します。乱数 \(k_A\) は Alice の秘密鍵として秘匿します。次に同様に、
します。もちろん \(k_B\) は秘匿します。そして、
とします。この作り方から \(K_A=K_B=K\) となるので、楕円曲線上の点である秘密鍵 \(K\) を共有できたことになり、以降はこれを使って暗号化通信(公開鍵ではない、高速な暗号化通信)を行います。使った秘密鍵は通信が終わったら捨てます。もちろん、\(K=(K_x,\:K_y)\) の \(K_x\) だけを秘密鍵としてもよいわけです。
原理は、オリジナルのディフィー・ヘルマンの鍵交換(DH)と全く同じです。ただ、オリジナルが \(\bs{F}_p^{*}\) での離散対数問題を利用していたのに対し、ECDH は \(E(a,\:b,\:p)\) での離散対数問題を利用した暗号であることが違います。
メッセージ伝送とデジタル署名
以降、前提として、
が公開されているものとします。
メッセージ伝送
楕円曲線暗号によるメッセージ伝送方式の例として「楕円曲線 ElGamal 暗号」をとりあげます。これは、\(\bs{F}_p\) における離散対数問題を利用した ElGamal 暗号(No.313「高校数学で理解する公開鍵暗号の数理」の「13. 離散対数暗号」参照)の「楕円曲線版」です。
この暗号では、送るべきメッセージを \(m\)(=整数)とするとき、\(m\) を \(\bs{F}_p\) 上の楕円曲線の点 \(M=(x,\:y)\) と対応付けます。その対応付けの方法は送信者と受信者であらかじめ合意しておく必要があります。そのやり方の例として、\(m\) を \(\dfrac{d}{100}\) 未満の数となるように選びます。そして、
\(x=m\cdot100+i\:\:(i=0,\:1,\:2,\:\cd,\:99)\)
の \(100\) 個の中から、
\(x^3+ax+b\)
が平方数となるような \(x\) を選びます。\(x\) の約半数は \(y^2=x^3+ax+b\) を満たす \(y\) があるので、\(100\)個を試せば必ず \(x\) が見つかります。そこで \(x^3+ax+b\) の平方根を計算して \(y\) を求め、
\(M=(x,\:y)\)
を伝送するメッセージとします(\(y\) は2つありますが、どちらかを選びます)。\(M\) から \(m\) への復元は、\([\cd]\) を \(\cd\) を超えない最大の整数(=ガウス記号)として、
\(m=\left[\dfrac{x}{100}\right]\)
で可能です(=切り捨て除算)。この \(100\) に大きな意味はなく、コンピュータで実装するときには演算回数を減らすために \(2^n\) となる数を選ぶのがベターでしょう。
楕円曲線 ElGamal 暗号によるメッセージ伝送は次のように進みます。Bob から Alice にメッセージ \(m\) を送る例です。
まず、Alice と Bob は「楕円曲線暗号版ディフィー・ヘルマンの鍵交換(ECDH)」を使って秘密鍵 \(k_A\) と \(k_B\) を決め、公開鍵 \(k_AG\) と \(k_BG\) を交換しておきます。
Bob の暗号化手順
Alice の復号化手順
デジタル署名
Bob から Alice にメッセージ \(m\) (楕円曲線上の点としては \(M\))を送るとき、次のようにしてデジタル署名を付加できます。ベースポイント \(\bs{G}\) の位数 \(\bs{d}\) は素数ですが、この素数を \(\bs{q}\) とも書き、スカラー倍における "スカラー部分の演算" を有限体 \(\bs{\bs{F}_q}\) での演算として表記します。また、ハッシュ関数を \(H(\:)\) と書きます(No.311「高校数学で理解するRSA暗号の数理(2)」の "補記" 参照)。
Bob の署名手順
Alice の検証手順
このデジタル署名のアルゴリズムは、ECDSA (Elliptic Curve Digital Signature Algorithm) と呼ばれるもので、メッセージ \(m\) の暗号化方式が「楕円曲線 ElGamal 暗号」でなくても通用します。一般に、メッセージ伝送方式とデジタル署名方式は独立です。
上にも書いたように、楕円曲線暗号とは「有限体上の楕円曲線が構成する加法群を利用した暗号方式」の総称です。「楕円曲線暗号版ディフィー・ヘルマンの鍵交換(ECDH)」や「楕円 ElGamal 暗号」以外にも種々の方式が提案され、実用化されています。
18. 結合則が成り立つことの検証と証明
前回の No.315 で、"結合則が成り立つ" ことの証明を後回しにしたので、ここに書きます。楕円曲線暗号は、楕円曲線上の有理点が群になることに依存した暗号です。その "群" であることの要件の一つは結合則が成り立つことであり、楕円曲線暗号の数学的背景として是非とも確認しておきたいところです。
楕円曲線上の3点について、
\((P_1+P_2)+P_3=P_1+(P_2+P_3)\)
となるのが結合則ですが、加法は数式で示されています。そこでまず、数式を使って簡単な例で確かめてみます。
数式による確認(トライアル)
図15:楕円曲線の例2
\(y^2=x^3-x+1\)
楕円曲線として、No.315 の図15でとりあげた、
\(y^2=x^3-x+1\)
を例とし、この楕円曲線上に2つの固定点と1つの任意点を取って計算してみます。使う記号は次の通りです。
\(P_1=(0,\:1)\)
\(P_2=(p,\:q)\:\:\:(q^2=p^3-p+1)\)
\(P_3=(1,\:1)\)
\(P_4=P_1+P_2\)
\(P_5=P_4+P_3=(P_1+P_2)+P_3\)
\(P_6=P_2+P_3\)
\(P_7=P_1+P_6=P_1+(P_2+P_3)\)
\(P_5=P_7\) が示せれば結合則が成り立っています。以下、No.315 の加法式(第2形)、
を使って計算を進めると次のようになります。
途中、\(x_5\) の計算で \(q^2\) を \(p^2-p+1\) で置き換えました。さらに、\(\lambda_4=\dfrac{p^2-1}{q+1}\) を使って \(\lambda_5\) の式から \(\lambda_4\) を消去すると、
\(\lambda_5=\dfrac{-p^2+2q+3}{(p+1)(q+1)}\)
となります。これを用いて \(y_5\) を計算すると、
となり、\(P_5=(x_5,\:y_5)\) が求まりました。
ここで \(\lambda_6=\dfrac{p^2+p}{q+1}\) を使って \(\lambda_7\) の式から \(\lambda_6\) を消去すると、
\(\lambda_7=-\dfrac{2(p^2+p-q-1)}{(p+1)(q+1)}\)
となります。この \(\lambda_7\) を使って \(y_7\) を計算すると、
となり、\(P_7=(x_7,\:y_7)\) が求まりました。以上の計算で、\(P_5=(\)\(x_5,\:y_5\)\()\) と \(P_7=(\)\(x_7,\:y_7\)\()\) は同じ点であることが分かり、この例では結合則が検証できました。
もちろんこれで結合則が証明できたわけではありません。しかし上の検証から分かるように、加法式によって結合則を証明するには計算が膨大になると推測できます。そこで次に、数式処理ソフトを使って証明します。
数式による証明(SymPy)
再度、記号の定義をはっきりさせます。
群の要件の一つである結合則を証明するために、楕円曲線上の3点を、\(P_1,\:\:P_2,\:\:P_3\) とし、
\(P_1=(x_1,\:y_1)\)
\(P_2=(x_2,\:y_2)\)
\(P_3=(x_3,\:y_3)\)
とします。
\(y_1^2=x_1^3+ax_1+b\)
\(y_2^2=x_2^3+ax_2+b\)
\(y_3^2=x_3^3+ax_3+b\)
です。このとき、
\((P_1+P_2)+P_3=P_1+(P_2+P_3)\)
であれば結合則が成り立ちます。これを示すため、\(P_4,\:P_5,\:P_6,\:P_7\) を、
\(P_1+P_2=P_4\)
\(P_4+P_3=P_5\)
\(P_2+P_3=P_6\)
\(P_1+P_6=P_7\)
\(P_i=(x_i,\:y_i)\:\:(4\leq i\leq7)\)
と定義して、
\(P_5\:=\:P_7\)
であることを証明します。そのためには、
\(x_5=x_7\)
を示せれば十分です。以降で、Python のライブラリ SymPy の数式処理機能を使って、\(x_5=x_7\) であることを証明します。そのためのコードと実行結果を掲げますが、ポイントは、
\(y_i^2=x_i^3+ax_i+b\:\:(1\leq i\leq3)\)
の関係を使って、計算途中の要所要所で、\(y_1,\:y_2,\:y_3\) の2乗以上の項を無くすことです。次のコードでは ellipse_substitute 関数がそれを行っています。
実行結果
この実行結果より、\(x_5\) と \(x_7\) の差異は厳密に \(0\) であり、\(x_5=x_7\) であることが証明されました。
このコードの ellipse_substitute 関数の補足ですが、SymPy のメソッドの cancel は、式を有理式の形(\(\tfrac{p}{q}\) の形。\(p,\:q\) は多項式)にととのえます。また subs は、式を別の式(ないしは値)で置き換えます。従って、関数は次の処理をします。
\(y_i^4\) の置き換えは、\(y_i^2\) の置き換えと同時に SymPy で処理されます。\(y_i^5\) 以上の項は、このコードでは発生しません。ちなみに、\(x_5\) と \(x_7\) を有理式の形で、
\(x_5=\dfrac{A}{B},\:\:x_7=\dfrac{C}{D}\)
と表わしたときの \(A,\:B,\:C,\:D\) は次の通りです。\(A,\:C\) は72項、\(B,\:D\) は40項もあるので手計算は無理ですが、SymPy で確認すると \(AD=BC\) が成り立っています。
\(A=x_1^4x_2^2x_3+\)\(x_1^4x_2x_3^2+\)\(6x_1^3x_2^3x_3-\)\(x_1^3x_2^2x_3^2+\)\(x_1^2x_2^4x_3-\)\(x_1^2x_2^3x_3^2+\)\(x_1x_2^4x_3^2+\)\(y_1y_2(-2ax_1^2+\)\(4ax_1x_2-\)\(4ax_1x_3-\)\(2ax_2^2-\)\(4ax_2x_3-\)\(8bx_3-\)\(4x_1^2x_2x_3-\)\(2x_1^2x_3^2-\)\(4x_1x_2^2x_3+\)\(4x_1x_2x_3^2-\)\(2x_2^2x_3^2)+\)\(y_1y_3(2ax_1^2+\)\(4ax_1x_2-\)\(6ax_2^2+\)\(8bx_1-\)\(8bx_2+\)\(6x_1^2x_2^2-\)\(4x_1x_2^3-\)\(2x_2^4)+\)\(y_2y_3(-6ax_1^2+\)\(4ax_1x_2+\)\(2ax_2^2-\)\(8bx_1+\)\(8bx_2-\)\(2x_1^4-\)\(4x_1^3x_2+\)\(6x_1^2x_2^2)+\)\(a^2(x_1^3-\)\(x_1^2x_2+\)\(x_1^2x_3-\)\(x_1x_2^2+\)\(6x_1x_2x_3+\)\(x_2^3+\)\(x_2^2x_3)+\)\(2ab(x_1^2-\)\(2x_1x_2+\)\(4x_1x_3+\)\(x_2^2+\)\(4x_2x_3)+\)\(8b^2x_3+\)\(a(x_1^4x_2+\)\(x_1^4x_3-\)\(x_1^3x_2^2+\)\(2x_1^3x_2x_3+\)\(x_1^3x_3^2-\)\(x_1^2x_2^3+\)\(10x_1^2x_2^2x_3-\)\(x_1^2x_2x_3^2+\)\(x_1x_2^4+\)\(2x_1x_2^3x_3-\)\(x_1x_2^2x_3^2+\)\(x_2^4x_3+\)\(x_2^3x_3^2)+\)\(2b(x_1^4-\)\(4x_1^3x_2+\)\(2x_1^3x_3+\)\(6x_1^2x_2^2+\)\(2x_1^2x_2x_3+\)\(x_1^2x_3^2-\)\(4x_1x_2^3+\)\(2x_1x_2^2x_3-\)\(2x_1x_2x_3^2+\)\(x_2^4+\)\(2x_2^3x_3+\)\(x_2^2x_3^2)\)
\(B=x_1^4x_2^2-\)\(2x_1^4x_2x_3+\)\(x_1^4x_3^2+\)\(6x_1^3x_2^3+\)\(2x_1^3x_2^2x_3-\)\(4x_1^3x_2x_3^2+\)\(x_1^2x_2^4+\)\(2x_1^2x_2^3x_3+\)\(6x_1^2x_2^2x_3^2-\)\(2x_1x_2^4x_3-\)\(4x_1x_2^3x_3^2+\)\(x_2^4x_3^2+\)\(y_1y_2(-4ax_1-\)\(4ax_2-\)\(8b-\)\(4x_1^2x_2+\)\(4x_1^2x_3-\)\(4x_1x_2^2-\)\(8x_1x_2x_3+\)\(4x_2^2x_3)+\)\(a^2(x_1^2+\)\(6x_1x_2+\)\(x_2^2)+\)\(8ab(x_1+\)\(x_2)+\)\(8b^2+\)\(2a(3x_1^3x_2-\)\(x_1^3x_3+\)\(2x_1^2x_2^2+\)\(x_1^2x_2x_3+\)\(3x_1x_2^3+\)\(x_1x_2^2x_3-\)\(x_2^3x_3)+\)\(4b(x_1^3+\)\(x_1^2x_2-\)\(x_1^2x_3+\)\(x_1x_2^2+\)\(2x_1x_2x_3+\)\(x_2^3-\)\(x_2^2x_3)\)
\(C=x_1^2x_2^4x_3-\)\(x_1^2x_2^3x_3^2-\)\(x_1^2x_2^2x_3^3+\)\(x_1^2x_2x_3^4+\)\(x_1x_2^4x_3^2+\)\(6x_1x_2^3x_3^3+\)\(x_1x_2^2x_3^4+\)\(y_1y_2(2ax_2^2+\)\(4ax_2x_3-\)\(6ax_3^2+\)\(8bx_2-\)\(8bx_3+\)\(6x_2^2x_3^2-\)\(4x_2x_3^3-\)\(2x_3^4)+\)\(y_1y_3(-6ax_2^2+\)\(4ax_2x_3+\)\(2ax_3^2-\)\(8bx_2+\)\(8bx_3-\)\(2x_2^4-\)\(4x_2^3x_3+\)\(6x_2^2x_3^2)+\)\(y_2y_3(-4ax_1x_2-\)\(4ax_1x_3-\)\(2ax_2^2+\)\(4ax_2x_3-\)\(2ax_3^2-\)\(8bx_1-\)\(2x_1^2x_2^2+\)\(4x_1^2x_2x_3-\)\(2x_1^2x_3^2-\)\(4x_1x_2^2x_3-\)\(4x_1x_2x_3^2)+\)\(a^2(x_1x_2^2+\)\(6x_1x_2x_3+\)\(x_1x_3^2+\)\(x_2^3-\)\(x_2^2x_3-\)\(x_2x_3^2+\)\(x_3^3)+\)\(2ab(4x_1x_2+\)\(4x_1x_3+\)\(x_2^2-\)\(2x_2x_3+\)\(x_3^2)+\)\(8b^2x_1+\)\(a(x_1^2x_2^3-\)\(x_1^2x_2^2x_3-\)\(x_1^2x_2x_3^2+\)\(x_1^2x_3^3+\)\(x_1x_2^4+\)\(2x_1x_2^3x_3+\)\(10x_1x_2^2x_3^2+\)\(2x_1x_2x_3^3+\)\(x_1x_3^4+\)\(x_2^4x_3-\)\(x_2^3x_3^2-\)\(x_2^2x_3^3+\)\(x_2x_3^4)+\)\(2b(x_1^2x_2^2-\)\(2x_1^2x_2x_3+\)\(x_1^2x_3^2+\)\(2x_1x_2^3+\)\(2x_1x_2^2x_3+\)\(2x_1x_2x_3^2+\)\(2x_1x_3^3+\)\(x_2^4-\)\(4x_2^3x_3+\)\(6x_2^2x_3^2-\)\(4x_2x_3^3+\)\(x_3^4)\)
\(D=x_1^2x_2^4-\)\(4x_1^2x_2^3x_3+\)\(6x_1^2x_2^2x_3^2-\)\(4x_1^2x_2x_3^3+\)\(x_1^2x_3^4-\)\(2x_1x_2^4x_3+\)\(2x_1x_2^3x_3^2+\)\(2x_1x_2^2x_3^3-\)\(2x_1x_2x_3^4+\)\(x_2^4x_3^2+\)\(6x_2^3x_3^3+\)\(x_2^2x_3^4+\)\(y_2y_3(-4ax_2-\)\(4ax_3-\)\(8b+\)\(4x_1x_2^2-\)\(8x_1x_2x_3+\)\(4x_1x_3^2-\)\(4x_2^2x_3-\)\(4x_2x_3^2)+\)\(a^2(x_2^2+\)\(6x_2x_3+\)\(x_3^2)+\)\(8ab(x_2+\)\(x_3)+\)\(8b^2+\)\(2a(-\)\(x_1x_2^3+\)\(x_1x_2^2x_3+\)\(x_1x_2x_3^2-\)\(x_1x_3^3+\)\(3x_2^3x_3+\)\(2x_2^2x_3^2+\)\(3x_2x_3^3)+\)\(4b(-\)\(x_1x_2^2+\)\(2x_1x_2x_3-\)\(x_1x_3^2+\)\(x_2^3+\)\(x_2^2x_3+\)\(x_2x_3^2+\)\(x_3^3)\)
3次曲線による証明
コンピュータを使った(=数式処理ソフトによる)証明では、なんとなく、証明した気になりません。その理由は、SymPy が正しい(バグがない)ことに依存しているからです。そこで以下は、シルヴァーマン、テイト著「楕円曲線論入門」にある証明を紹介します。これは、楕円曲線を含む3次曲線の性質を用いた証明で、本質をついた議論になっています。
結合則が成り立つのは、楕円曲線上の加法を「3次曲線と直線の交点」で決めていることに理由があります。「楕円曲線論入門」に、結合則が成り立つことを示した次の図があります。加法群の零元 \(\mathcal{O}\) を楕円曲線上にとった場合の図です。
楕円曲線上に点 \(P\)、\(Q\)、\(R\) をとったとき、
となるのが結合則ですが、
です。ここで \(\!*\!\) の記号は、\(A\!*\!B\) と書くと \(A\) と \(B\) を結ぶ直線が楕円曲線と交わる点(で \(A\)、\(B\) 以外の点)の意味です。\(\mathcal{O}\) は零元でした。従って、結合則を証明するためには、
が証明できればよいことになります。言葉で書くと、
となります。上の図はそれを表しています。以下の証明では同じことですが、次を示します。
これは楕円曲線上の2点、\((P+Q)\!*\!R\) と \(P\!*\!(Q+R)\) が等しい(= 図11)ことと同じなので、以降は 18.1 が成り立つことを示します。そのためにまず、次の命題 18.2 を証明します。この証明の筋道は「楕円曲線論入門」に書かれているものです。
これは「ケーレー・バカラック(Cayley-Bacharach)の定理」と呼ばれるものの一部です(Cayleyは英国、Bacharachはドイツの数学者。バカラックは英語読み。いずれも19世紀)。この定理は、
というもので、その3次元曲線の場合が 18.2 です。ここで言う3次曲線とは次の一般形で表される "3次曲線のすべて" であり、楕円曲線もその一部です。
\([\)3次曲線の一般形\(]\)
\(ax^3+bx^2y+cxy^2+dy^3+ex^2+fxy+gy^2+hx+iy+j=0\)
10個の係数(=パラメータ)、\(a,\:b,\:\:\cd\:,\:i,\:j\) を決めると3次曲線が一つ決まります。もちろん、各係数を定数倍した曲線は同じ曲線です。つまり、この形の3次曲線の係数は実質的に "9次元" と言えます。3次曲線なので \(a,\:b,\:c,\:d\) のうち少なくとも一つは \(0\) でないものがあります。その係数で全体を割れば、係数の数は9個になることからもわかります。9次元なので「相異なる8点を通る3次曲線」は無数にあります。
そこで、相異なる8点を通る3次曲線が一般的にどういう式で表現できるかを考えます。相異なる8点の座標を、
とします。まず、3次曲線が \(P_1\) を通るということは、10個のパラメータは次の制約条件を満足しなければなりません。
\(x_1^3a+x_1^2y_1b+x_1y_1^2c+y_1^3d+x_1^2e+x_1y_1f+y_1^2g+x_1h+y_1i+j=0\)
これは 10個の変数 \(a\) ~ \(j\) についての線型方程式(1次方程式)なので、係数を変数の前に記述しました。同様にして、3次曲線が \(P_2\) から \(P_8\) を通ることから7個の制約条件が得られます。これらをまとめると、
の、合計8つの制約条件が得られます。8個の点を通る3次曲線の10個のパラメータは、この8つの制約条件(連立1次方程式)を満たさなければなりません。ということは、\(10-8=2\) で、これらのパラメータは、制約条件のない自由な2つのパラメータで表現できることになります。
たとえば \(a\) と \(b\) を "2つのパラメータ" に選ぶと、残りの \(c\) ~ \(j\) は、\(\al_na+\beta_nb\:(n=c\:\cd\:j)\) という「\(a\) と \(b\) の1次式」で表現できます(\(\al_n,\:\beta_n\) は連立1次方程式の係数で決まる値)。しかしこれでは \(a=0\) かつ \(b=0\) のときに、すべてのパラメータが \(\bs{0}\) という自明な解しか得られません。\(x^3\) の項と \(x^2y\) の項がない3次曲線はいくらでもありうるので、自明ではない解の中に \(a=0,\:b=0\) となるものは当然あるはずです。つまり、\(\al_na+\beta_nb\) の形は連立1次方程式の解の全部は表していません。
では、上記の連立1次方程式の「自明ではない解すべてを表す一般解」はどういう形でしょうか。それには8つの方程式を満たす独立な数値の組(=連立1次方程式の解)を2組用意します。つまり無数にある解の中から2つをピックアップし、それをベクトル表現で、
とします。"独立" とはこの場合、2つの数値群が異なった3次曲線を表現しているということです。そして、同時に \(0\) にはならない新たな2つのパラメータを導入します。それを \(\lambda_1,\:\:\lambda_2\) とすると、
が連立1次方程式の一般解(不定解)になります。自由な2つのパラメータの1次式で表現されていて、8つの方程式を満たすことが明らかだからです。この一般解をもとに3次曲線の方程式を表現します。そこで、
の2つの関数を考えると、\(f_1=0\) の3次曲線と \(f_1=0\) の3次曲線は、共に8点を通ります。従って、
は8点を通り、2つの自由なパラメータで表現された3次曲線群です。従って、これが \(P_1,\:\:P_2,\:\:\cd\:,\:\:P_8\) を通るすべての3次曲線を表す一般形です。
以上を踏まえて命題 18.2 を検討します。命題を再掲すると、
でした。この前半の2つの3次曲線の関数式を
とします。\(F_1=0\) も \(F_2=0\) も9点、\(P_1,\:\:P_2,\:\:\cd\:,\:\:P_9\) を通る3次曲線です。従って \(F_1=0\) と \(F_2=0\) は \(P_1,\:\:P_2,\:\:\cd\:,\:\:P_8\) の8点を通る2つの3次曲線でもある。ということは、\(P_1,\:\:P_2,\:\:\cd\:,\:\:P_8\) の8点を通るすべての3次曲線は、
で表されます。従って、命題の後半に出てくる別の3次曲線 \(D\) が \(P_1,\:\:P_2,\:\:\cd\:,\:\:P_8\) の8点を通るとすると、\(D\) は \(F=\lambda_1F_1+\lambda_2F_2=0\) で表現できます。
ここでよく考えてみると、3次曲線 \(F=0\) は9点目の \(P_9\) を通るのでした。従って \(D\) も \(P_9\) を通ります。これで 18.2 が成り立つことが証明できました。以上を振り返ってまとめると次のようになります。
この "まとめ" で述べているように、8つの点を通る3次曲線は無数に存在します。8つの点を通る3次曲線は(一般には)一意に定まりません。そこで点を1つ増やすと、9つの点を通る3次曲線は(一般には)一意に定まります(9次元だから)。しかし、その9点が「2つの3次曲線の交点である9点」なら状況が変わります。その9点は独立ではなく、8点が決まれば残りの1点は自動的に決まる。従って、8点を通るすべての3次曲線は残りの1点も通ることになります。この例を図で示すと次の通りです。2つの3次曲線、\(C_1\) と \(C_2\) を、
\(C_1\::\)
\(C_2\::\)
とします。この2つの3次曲線は9つの点、\(P_1\) ~ \(P_9\) で交差します。それを正確に図示すると図19の通りです。
ここで、\(C_1,\:C_2\) とは別の、\(P_1\) ~ \(P_8\) の8つの点を通る3次曲線を作ると、それも \(P_9\) を通ります(図20)。図20 で、黄・緑・青の3つの3次曲線がその例です。
18.2 を踏まえて、楕円曲線の加法群で結合則が成り立つことを証明しますが、証明のポイントは、相異なる3つの直線を "3次曲線" として扱うことです。この扱いがなぜ可能かと言うと、3つの直線を、
としたとき、
からです。もちろん、\(F_L=0\) という曲線の方程式は、3次曲線の一般形の係数 \(a,\:b,\:\:\cd\:,\:i,\:j\) に特別の関係を持ち込んだものです。だからこそ3つの直線を表現しているわけです(数学用語で言うと "退化した" 3次曲線)。しかし特別の関係があるとしても 18.2 を証明した議論の筋道には全く影響しません。
具体的な例をあげると、次の通りです。まず、3次曲線との交点が3つある直線を2つ描き(赤で示す)、交点を \(P_1,\:P_2,\:P_3\)、\(P_4,\:P_5,\:P_6\) とします(図21)。
次に、\(P_1\) と \(P_4\) を結ぶ直線と、\(P_3\) と \(P_6\) を結ぶ直線を緑で描き、3次曲線との交点をそれぞれ \(P_7,\:\:P_8\) とします(図22)。
こうした上で、\(P_2\) と \(P_5\) を結ぶ直線を緑で、\(P_7\) と \(P_8\) を結ぶ直線を赤で描きます(図23)。
ここで、
\(C_1\) : 3次曲線
\(C_2\) : 赤の3直線
\(C_3\) : 緑の3直線
とすると、\(C_1,\:\:C_2,\:\:C_3\) の 3つの "3次曲線" はすべて \(P_1\) ~ \(P_8\) の8点を通ります。すると 18.2 によって、この3つの "3次曲線" ははすべて、\(P_1\) ~ \(P_8\) 以外の、ある特別な点(=図23の点線丸印)を通ります。言い換えると、
ことになります。
以上を踏まえて、結合則を証明すべき図11を再掲します。図11 と図23 は数学的に全く同じであることが、以降の証明のポイントです。
証明すべきことは 18.1 の、
でした。図11で、
とすると、\(C_1\)(点線) と \(C_2\)(実線)は次の9つの点を通ります。
\(C_1\) と \(C_2\) が9つの点を通るのはそういう風に作図したからです。一方、楕円曲線は \(T\) 以外の \(P_1\) ~ \(P_8\) の8点を通ります。なぜならその8点は楕円曲線上の点として作ったからです。ところが \(T\) だけは違っていて、楕円曲線上の点として作ったのではなく2直線の交点です。しかし 18.2 によって楕円曲線は \(T\) も通ることになります。
これで、楕円曲線上の有理点が作る加法群で結合則が成り立つことの証明が完成しました。
零元を無限遠点にとる加法群ではどうなるでしょうか。この場合は「射影平面での3次曲線」を考える必要があります。射影平面での3次曲線の一般形は、
\([\)射影平面における3次曲線の一般形\(]\)
\(AX^3+BX^2Y+CXY^2+DY^3+EX^2Z+FXYZ+GY^2Z+\)
\(HXZ^2+IYZ^2+JZ^3=0\)
ですが、証明の筋道は \(xy\) 平面と全く同じです。というのも、証明のコアのところは「10変数の連立1次方程式(方程式数が8)の不定解が、一般形でどう表現できるか」であり、曲線方程式の未知数が \((x,\:y)\) の2つであっても \((X,\:Y,\:Z)\) の3つであっても証明の論理に影響がないからです。
というわけで、楕円曲線暗号で実際に使われる「無限遠点を零元にした加法群」においても結合則が成り立つのでした。
19. パスカルの定理
最後に余談ですが、18.2(ケーレー・バカラックの定理)から証明できる別の定理があります。「パスカルの定理」です。これはパスカルが16歳のときに発表した「円錐曲線試論」にあります。最も一般的な形で言うと次の通りです。
これは非常に美しい定理です。どんな円錐曲線かを言っていないし(円、楕円、放物線、双曲線)、円錐曲線上の6点の位置も、その順序も何も言ってない。それにもかかわらず「同一直線上にある」という、シンプルで強い断定が結論にくる ・・・・・・。個人的経験を言うと、高校生時代にこの定理を知ってその "不思議さ" が印象的だったことを覚えています。
この定理の例を図24と図25、図26に示します。\(Q_1\) を \(P_7\)、\(Q_2\) を \(P_8\)、\(Q_3\) を \(T\) と書きました。円錐曲線が円か楕円であり、6点を円・楕円の周上に順に(= 一周するように)とった場合には、パスカルの定理は、
と簡潔に表現できます(図24)。図25の楕円上の点の位置は図24と同じですが、名前付けが違います。しかし3点が同一線上に並ぶのは同じです。このように6点は楕円上のどの位置にどの順序で配置してもよいわけです。
定理の証明は次の通りです。3次曲線、\(C_1,\:\:C_2,\:\:D\) を、
とします。\(C_1\) と \(C_2\) は 、\(P_1\) ~ \(P_8\) と \(T\) を通ります。そういう風に作図したからです。一方、\(D\) は \(P_1\) ~ \(P_8\) を通ります。そうすると 18.2 より \(D\) は \(T\) も通ります。\(D\) は \(P_7\) と \(P_8\) を通るように作図しましたが、\(T\) を通るようには作図していません。それでも \(T\) を通る。
その \(T\) は、\(D\) の円錐曲線部分にはありません。なぜなら、\(T\) は直線 \(P_3P_4\) 上に(ないしは直線 \(P_6P_1\) 上に)ありますが、円錐曲線と直線の交点は高々2つであり、\(P_3,\:\:P_4\) が(ないしは \(P_6,\:\:P_1\) が)すでに円錐曲線上にあるからです。従って \(T\) は \(D\) の直線部分にあるしかない。これで証明が終わりました。
パスカルの定理のよくある証明は、円の場合に補助円を用いて証明し、それを "斜めから見たら" 楕円でも成り立つ、とするものです。しかしこの定理は、すべての円錐曲線(=2次曲線の一般形、\(ax^2+bxy+cy^2+dx+ey+f=0\) で表される曲線)で成り立つことが上の証明から分かります。
ちなみに、パスカルの定理は「円錐曲線」を「2直線」に置き換えても、交点ができるように点を配置すれば成り立ちます(パップスの定理と呼ばれる。パップスは4世紀のアレキサンドリアの数学者)。
図27 パップスの定理
軸を含む平面で円錐を2分割すると(平行でない)2直線になり、それは(退化した)円錐曲線とも言えますが、たとえ平行な2直線であっても2次曲線の一般形で表現できるので定理は成り立ちます。
楕円曲線暗号は「楕円曲線上の有理点による加法群」の上に作られた暗号ですが、
のでした。
補足:素数判定アルゴリズム
公開鍵暗号で使われる巨大素数の判定アルゴリズム(ミラー・ラビン法)を、
No.369「高校数学で理解する素数判定の数理」
に書きました。
(前回の No.315 より続く)
16. 楕円曲線上の点
有限体 \(\bs{F}_p\) の元 \(x\) と \(y\) のぺア \((x,\:y)\) の集合を \(\bs{F}_p^{\:2}\) と記述します。集合 \(\bs{F}_p^{\:2}\) の元で楕円曲線上の "点" はどれだけあるでしょうか。まず、楕円曲線の式を満たす \(\bs{F}_p^{\:2}\) の元がどのように計算できるかを調べます。
平方数と平方根
楕円曲線の式を、
\(\left\{
\begin{array}{l}
\begin{eqnarray}
&&y^2=z&\\
&&z=x^3+ax+b&\\
\end{eqnarray}
\end{array}\right.\)
と書くとき、\(z\)(\(z\neq0\))が \(\bs{F}_p\) での平方数なら、\(y\) の解が2つ求まります。ここで、次の命題が成立します。
16.1 | 平方数である条件 |
\(z\) を \(0\) ではない \(\bs{F}_p\) の元とする。
\(z^{\frac{p-1}{2}}=1\) であるとき(かつ、そのときに限り)\(z\) は平方数である(= オイラーの規準)。 |
\(\bs{F}_p\) で考えているので「平方数」と書きましたが、整数の世界では平方剰余です。つまり、\(x^2=a\:(\mr{mod}\:n)\) となるような \(x\) が存在する \(a\) が「\(n\) を法とする平方剰余」です。16.1 の証明ですが、12.1(No.313)により、\(z\) は \(\bs{F}_p^{*}\) の生成元(の一つ)を \(g\) として、
\(z=g^k\)
と表現できます。つまり、命題の条件は、
\(g^{k\frac{p-1}{2}}=1\)
です。このとき \(k\) は偶数のはずです。なぜなら、もし \(k\) が奇数だとすると、\(k\dfrac{p-1}{2}\) は \(p-1\) で割り切れないので、
\(k\dfrac{p-1}{2}=s(p-1)+t\)
\((1\leq t < p-1)\)
\((1\leq t < p-1)\)
と表現できます。すると、
\(\begin{eqnarray}
&&g^{k\frac{p-1}{2}}&=g^{s(p-1)+t}\\
&&&=(g^{p-1})^s\cdot g^t=g^t\\
\end{eqnarray}\)
となり、\(g^t=1\:(1\leq t < p-1)\) になりますが、これは \(g\) が生成元であることと矛盾します。従って \(k\) は偶数です。そうすると \(k=2m\) とおいて、
\(z=(g^m)^2\)
となり、\(z\) は平方数になります。逆に、
\(z=y^2\)
と表現されるとすると、フェルマの小定理 3.1をつかって、
\(\begin{eqnarray}
&&z^{\frac{p-1}{2}}&=(y^2)^{\frac{p-1}{2}}\\
&&&=y^{p-1}\\
&&&=1\\
\end{eqnarray}\)
となり、\(\bs{z^{\frac{p-1}{2}}=1}\) と 「\(\bs{z}\) が平方数」は同値であることが証明できました。
なお、フェルマの小定理によって、 \((z^{\frac{p-1}{2}})^2=1\) なので、\(z^{\frac{p-1}{2}}\) は \(1\) か \(-1(=p-1)\) のどちらかです。従って、
\(z^{\frac{p-1}{2}}=\phantom{-}1\) のとき、\(z\) は平方数
\(z^{\frac{p-1}{2}}=-1\) のとき、\(z\) は平方数ではない
\(z^{\frac{p-1}{2}}=-1\) のとき、\(z\) は平方数ではない
ということになります。「平方数ではない」は、整数の世界では「平方非剰余」です。
平方根を求める
\(z\) は平方数だとわかったとき、実際に \(\bs{F}_p\) で \(y\)(= \(z\) の平方根)を求める手段が必要になります。整数であれば平方根を求めるのは容易ですが、\(\bs{F}_p\) ではそうはいきません。特に、楕円曲線暗号で使われる \(p\) は10進数で数10桁以上の巨大素数なので、総当たりで求めたり、解の存在範囲を限定していって求めるわけにはいかないのです。以下が解を求めるアルゴリズムです。
\(p\equiv3\:(\mr{mod}\:4)\) の場合
この場合は
\(y=z^{\frac{p+1}{4}}\)
が解の一つとなります(もう一つの解は \(-y\) で、つまり \(p-y\))。確認してみると、
\(\begin{eqnarray}
&&y^2&=\left(z^{\frac{p+1}{4}}\right)^2=z^{\frac{p+1}{2}}\\
&&&=z^{\frac{p-1}{2}}\cdot z=z\\
\end{eqnarray}\)
となって、確かに \(y\) が解であることがわかります。
\(p\equiv1\:(\mr{mod}\:4)\) の場合
この場合は「トネリ-シャンクスのアルゴリズム」で解を求めることができます(Tonelli は19世紀イタリア、Shanks は20世紀米国の数学者)。以下のアルゴリズムは Wikipedia を参考にしました。
\(p\equiv1\:(\mr{mod}\:4)\) の場合、\(p-1\) は \(4\) の倍数です。\(p-1\) を素因数分解したときの \(2\) のべき乗を \(S\) とすると、\(p-1\) は、
\(p-1=Q\cdot2^S\) \(Q\) は奇数、 \(S\geq2\) |
と表現できます。ここで、\(\bs{F}_p\) において平方数ではない数 \(w\) を(どれでもよいから)一つ選びます。つまり、
\(w^{\frac{p-1}{2}}=-1\)
となる数 \(w\) です。\(\bs{F}_p\) においては平方数とそうでない数が半々なので、この選択は容易です。次に、4つの数を、
\(\begin{eqnarray}
&&S_0&=S\\
&&c_0&=w^Q\\
&&t_0&=z^Q\\
&&y_0&=z^{\frac{Q+1}{2}}\\
\end{eqnarray}\) |
と定義します。このように定義すると、\(c_0,\:\:t_0,\:\:y_0\) は次の「性質」を持ちます。
\(\begin{eqnarray}
&&\:\:(c_0)^{2^{S_0-1}}&=(w^Q)^{2^{S-1}}\\
&&&=w^{Q\cdot2^{S-1}}\\
&&&=w^{\frac{p-1}{2}}\\
&&&=-1\\
\end{eqnarray}\)
\(\begin{eqnarray}
&&\:\:(t_0)^{2^{S_0-1}}&=(z^Q)^{2^{S-1}}\\
&&&=z^{Q\cdot2^{S-1}}\\
&&&=z^{\frac{p-1}{2}}\\
&&&=1\\
\end{eqnarray}\)
\(\begin{eqnarray}
&&\:\:y_0^{\:2}&=\left(z^{\frac{Q+1}{2}}\right)^2\\
&&&=z^{Q+1}\\
&&&=t_0\cdot z\\
\end{eqnarray}\)
まとめると、
\(\begin{eqnarray}
&&(c_0)^{2^{S_0-1}}&=-1\\
&&(t_0)^{2^{S_0-1}}&=\phantom{-}1\\
&&(y_0)^2&=t_0\cdot z\\
\end{eqnarray}\) |
です。もし、\(t_0=1\) なら、3番目の式により \(z\) の平方根は \(y_0\) および \(-y_0\:(=p-y_0)\) ですが、そうはなりません。\(S_0=1\) なら \(t_0=1\) となりますが、\(S_0=S\geq2\) だからです。
そこで、\(\{\:S_i,\) \(c_i,\) \(t_i,\) \(y_i\:\}\) の4数の組の列 \((i=0,\:1,\:2,\:\cd\:)\) を順次作り、上記の「性質」を保ちつつ、ある時点で \(t_i=1\) になることを目指します。\(t_i=1\) になったとしたら、そのときの \(\pm y_i\) が \(z\) の平方根です。\(i=1\) に対応する4数の組は次のようにします。
\(S_1\) : \(0 < S_1 < S_0\) で、\((t_0)^{2^{S_1}}=1\) を満たす最小の数
\(S_1=S_0-1\) と置くと、\((t_0)^{2^{S_0-1}}=1\) だったので、\(S_0-1\) は \(S_1\) の候補です。もしこれが最小なら \(S_1\) そのものです。従って条件に合う \(S_1\) を必ず選ぶことができます。
\(\begin{eqnarray} &&c_1&=(c_0)^{2^{S_0-S_1}}\\ &&t_1&=t_0\cdot(c_0)^{2^{S_0-S_1}}\\ &&y_1&=y_0\cdot(c_0)^{2^{S_0-S_1-1}}\\ \end{eqnarray}\) |
このように定義すると、次のように「性質」が保たれることが分かります。
\(\begin{eqnarray}
&&\:\:(c_1)^{2^{S_1-1}}&=\left((c_0)^{2^{S_0-S_1}}\right)^{2^{S_1-1}}\\
&&&=(c_0)^{2^{S_0-1}}\\
&&&=-1\\
\end{eqnarray}\)
\(\begin{eqnarray}
&&\:\:(t_1)^{2^{S_1-1}}&=(t_0)^{2^{S_1-1}}\cdot\left((c_0)^{2^{S_0-S_1}}\right)^{2^{S_1-1}}\\
&&&=(t_0)^{2^{S_1-1}}\cdot(c_0)^{2^{S_0-1}}\\
&&&=-(t_0)^{2^{S_1-1}}\\
\end{eqnarray}\)
ここで、最後の式からマイナスを取って、
\((t_0)^{2^{S_1-1}}=X\)
とおくと、\(S_1\) の定義から \((t_0)^{2^{S_1}}=1\) なので、
\(X^2=(t_0)^{2^{S_1}}=1\)
となり、\(X\) は \(\bs{F}_p\) における方程式 \(X^2=1\) の解です。つまり、
\(X=1,\:-1\)
です。ところが \(X=1\) とすると、
\((t_0)^{2^{S_1-1}}=1\)
となりますが、\(S_1\) は \(0 < S_1 < S_0\) で \((t_0)^{2^{S_1}}=1\) を満たす最小の数と定義したにも関わらず、\(S_1\) より小さい \(S_1-1\) が定義を満たすことになってしまって矛盾します。従って \(X=-1\) であり、結局、
\(\begin{eqnarray}
&&\:\:(t_1)^{2^{S_1-1}}&=-X\\
&&&=1\\
\end{eqnarray}\)
となります。さらに、
\(\begin{eqnarray}
&&(y_1)^2&=(y_0)^2\cdot\left((c_0)^{2^{S_0-S_1-1}}\right)^2\\
&&&=t_0\cdot z\cdot(c_0)^{2^{S_0-S_1}}\\
&&&=t_0\cdot(c_0)^{2^{S_0-S_1}}\cdot z\\
&&&=t_1\cdot z\\
\end{eqnarray}\)
と計算できます。まとめると、
\(\begin{eqnarray}
&&(c_1)^{2^{S_1-1}}&=-1\\
&&(t_1)^{2^{S_1-1}}&=\phantom{-}1\\
&&(y_1)^2&=t_1\cdot z\\
\end{eqnarray}\) |
となって、\(i=1\) においても「性質」が成り立つことが分かりました。ここで仮に、\(\bs{t_1=1}\) なら \(\bs{(y_1)^2=z}\) となって、\(\bs{z}\) の平方根は \(\bs{\pm y_1}\) になります。
この計算で重要なことは \(S_1 < S_0\) であり、同様のやり方で \(\{\:S_i,\) \(c_i,\) \(t_i,\) \(y_i\:\}\) \((i=0,\:1,\:2,\:\cd\:)\) の4数の組の列を順次作っていくと、\(\bs{S_i}\) は単調減少することです。さらに、\(S_i=1\) なら \(t_i=1\) になることもポイントです。
以上のプロセスを進めて、\(i=0,\:1,\:2,\:3,\:\cd\) のとき、
\(S_{i+1}\) : \(0 < S_{i+1} < S_i\) で、\((t_i)^{2^{S_{i+1}}}=1\) を満たす最小の数 \(\begin{eqnarray} &&c_{i+1}&=(c_i)^{2^{S_i-S_{i+1}}}\\ &&t_{i+1}&=t_i\cdot(c_i)^{2^{S_i-S_{i+1}}}\\ &&y_{i+1}&=y_i\cdot(c_i)^{2^{S_i-S_{i+1}-1}}\\ \end{eqnarray}\) |
と定義すると、
\(\begin{eqnarray}
&&(c_i)^{2^{S_i-1}}&=-1\\
&&(t_i)^{2^{S_i-1}}&=\phantom{-}1\\
&&(y_i)^2&=t_i\cdot z\\
\end{eqnarray}\) |
の「性質」が成り立つことを数学的帰納法で証明します。\(i=0,\:1\) で成り立つことは上で既に確認しました。\(i\) のときに「性質」が成り立つと仮定すると、\(i+1\) でも成り立つことが次のように分かります。基本的には上の \(i=1\) での計算と同じです。
\(\begin{eqnarray}
&&\:\:(c_{i+1})^{2^{S_{i+1}-1}}&=\left((c_i)^{2^{S_i-S_{i+1}}}\right)^{2^{S_{i+1}-1}}\\
&&&=(c_i)^{2^{S_i-1}}\\
&&&=-1\\
\end{eqnarray}\)
\(\begin{eqnarray}
&&\:\:(t_{i+1})^{2^{S_{i+1}-1}}&=(t_i)^{2^{S_{i+1}-1}}\cdot\left((c_i)^{2^{S_i-S_{i+1}}}\right)^{2^{S_{i+1}-1}}\\
&&&=(t_i)^{2^{S_{i+1}-1}}\cdot(c_i)^{2^{S_i-1}}\\
&&&=-(t_i)^{2^{S_{i+1}-1}}\\
\end{eqnarray}\)
ここで、
\((t_i)^{2^{S_{i+1}-1}}=X\)
とおくと、\(S_{i+1}\) の定義によって \((t_i)^{2^{S_{i+1}}}=1\) なので、
\(X^2=(t_i)^{2^{S_{i+1}}}=1\)
となり、\(X\) は \(\bs{F}_p\) における方程式 \(X^2=1\) の解です。つまり、
\(X=1,\:-1\)
です。ところが \(X=1\) とすると、
\((t_i)^{2^{S_{i+1}-1}}=1\)
となりますが、\(S_{i+1}\) は \(0 < S_{i+1} < S_i\) で \((t_i)^{2^{S_{i+1}}}=1\) を満たす最小の数としたにも関わらず、\(S_{i+1}\) より小さい \(S_{i+1}-1\) が定義を満たすことになってしまい、矛盾します。従って \(X=-1\) であり、
\(\begin{eqnarray}
&&\:\:(t_{i+1})^{2^{S_{i+1}-1}}&=-X\\
&&&=1\\
\end{eqnarray}\)
です。また、
\(\begin{eqnarray}
&&\:\:(y_{i+1})^2&=(y_i)^2\cdot\left((c_i)^{2^{S_i-S_{i+1}-1}}\right)^2\\
&&&=t_i\cdot z\cdot(c_i)^{2^{S_i-S_{i+1}}}\\
&&&=t_i\cdot(c_i)^{2^{S_i-S_{i+1}}}\cdot z\\
&&&=t_{i+1}\cdot z\\
\end{eqnarray}\)
と計算できます。まとめると
\(\begin{eqnarray}
&&(c_{i+1})^{2^{S_{i+1}-1}}&=-1\\
&&(t_{i+1})^{2^{S_{i+1}-1}}&=\phantom{-}1\\
&&(y_{i+1})^2&=t_{i+1}\cdot z\\
\end{eqnarray}\) |
となり、\(i\) のときに成り立つと仮定すると \(i+1\) でも成り立つことが分かりました。これで、\(i=0,\:1,\:2,\:3,\:\cd\) で成り立つことが数学的帰納法で証明できました。
\(i=0,\:1,\:2,\:3,\:\cd\) のどこかで \(t_i=1\) となれば、そのときの \(\pm y_i\) が \(z\) の平方根です。\(S_i\) は単調減少であり、かつ、\(S_i=1\) なら \(t_i=1\) です。\(t_i=1\) となる \(i\) がなかなか見つからなくても、\(S_i\) が \(1\) まで減少すれば必ず見つかるので、\(z\) の平方根が求まります。
このアルゴリズムを実験してみます。4 で割って1余る素数 \(p\) として、 \(p=2^S+1\) 型の素数を選びます。\(S=8\) のとき \(p=257\) は素数なので、
\(p=257,\:\:Q=1,\:\:S=8\)
とおきます。計算してみると \(\bs{F}_{257}\) において \(11,\:13\) は平方数です。また、平方数でない数として \(3\) を選ぶことができます。そこでまず、
\(p=257,\:\:Q=1,\:\:S=8,\)
\(z=11,\:\:w=3\)
とおくと、
\(\begin{eqnarray}
&&\:\:S_0&=S&=8\\
&&\:\:c_0&=w^Q&=3\\
&&\:\:t_0&=z^Q&=11\\
&&\:\:y_0&=z^{\frac{Q+1}{2}}&=11\\
\end{eqnarray}\)
が初期値です。ここからアルゴリズムに沿って \(\{\:S_i,\) \(c_i,\) \(t_i,\) \(y_i\:\}\) \((i=1,\:2,\:\cd\:)\) を計算してみると、結果は、
\(0\) | \(8\) | \(3\) | \(11\) | \(11\) |
\(1\) | \(6\) | \(81\) | \(120\) | \(99\) |
\(2\) | \(5\) | \(136\) | \(129\) | \(52\) |
\(3\) | \(4\) | \(249\) | \(253\) | \(133\) |
\(4\) | \(3\) | \(64\) | \(1\) | \(221\) |
となり、\(\bs{F}_{257}\) における \(11\) の平方根の1つは \(221\) と求まりました。もう1つは \(257-221=36\) です。実際、
\(221^2=48841=190\cdot257+11\)
\(\phantom{2}36^2=\phantom{4}1296=\phantom{25}5\cdot257+11\)
なので正しい結果です。\(z=13\) もやってみると、
\(0\) | \(8\) | \(3\) | \(13\) | \(13\) |
\(1\) | \(7\) | \(9\) | \(117\) | \(39\) |
\(2\) | \(6\) | \(81\) | \(225\) | \(94\) |
\(3\) | \(4\) | \(249\) | \(256\) | \(191\) |
\(4\) | \(1\) | \(256\) | \(1\) | \(28\) |
となり、\(\bs{F}_{257}\) における \(13\) の平方根(の1つ)は \(28\) です。
\(28^2=784=3\cdot257+13\)
であり、アルゴリズムの確認ができました。
楕円曲線上の点の総数
\(\bs{F}_p\) 上の楕円曲線、\(E(a,\:b,\:p)\) の点の数がどの程度になるのでしょうか。以降、群 \(E(a,\:b,\:p)\) の元の数(群位数)を \(\#E\) と書きます。前回の No.315「高校数学で理解する楕円曲線暗号の数理(1)」の最後にあげた例だと、
\(\#E(2,\:4,\:109)=127\)
\(\bs{F}_{109}\) 上の楕円曲線 \(y^2=x^3+2x+4\) の点の数は無限遠点を含んで \(127\)) |
でした。この \(\#E(a,\:b,\:p)\) を評価する式があります。「ハッセの定理」です(Helmut Hasse は20世紀ドイツの数学者)。この定理によると、
\(p+1-2\sqrt{p}\leq\#E\leq p+1+2\sqrt{p}\)
であり、\(\#E\) は \(p+1\) の周辺、\(\pm2\sqrt{p}\) の範囲です。この意味を考えてみます。\(\bs{F}_p\) 上の楕円曲線を
\(\left\{
\begin{array}{l}
\begin{eqnarray}
&&y^2=z&\\
&&z=x^3+ax+b&\\
\end{eqnarray}
\end{array}\right.\)
で表わし、\(\bs{F}_p\) において \(z\) を \(0\) から \(p-1\) まで振ったときの \(y^2=z\) の解の総数を求めます。\(z\) を、\(\bs{F}_p^{*}\) の生成元 \(g\) を使って、
\(z=\left\{
\begin{array}{l}
\begin{eqnarray}
&&0&\\
&&g^k\:\:(k=1,\:2,\:\:\cd\:,\:p-1)&\\
\end{eqnarray}
\end{array}\right.\)
と表すと、
\(z=0\) のとき、解は\(1\)個 | |
\(k\) が偶数のとき、解は\(2\)個 | |
\(k\) が奇数のとき、解は無し |
となり、\(\bs{F}_p^{\:2}\) における解、\((z,\:y)\) の総数は \(p\) となります。では、\(\bs{F}_p^{\:2}\) における楕円曲線上の点、\((x,\:y)\) の総数はどうなるでしょうか。\(x\) が \(\bs{F}_p\) の全ての元に渡るとき、\(z\) が \(\bs{F}_p\) で均等にバラつくとは限りません。しかし \((x,\:y)\) の総数は「だいたい \(p\) に近い値」だと考えられます。
つまり、群 \(E(a,\:b,\:p)\) の元で、零元 \(\mathcal{O}\) 以外の \(\bs{F}_p^{\:2}\) に属するものは、だいたい \(p\) 個あると考えられる。従って \(\#E\) は 零元 \(\mathcal{O}\) を含んで \(p+1\) に近い値だと考えられます。これが「ハッセの定理」の直感的理解です。
別の観点から言うと、任意に選んだ \(x\) に対して、もし \(z\) が平方数なら \(y\) が2つ存在し、楕円曲線上の点が2つ求まります。ハッセの定理から言えることは、そうなる確率は、任意の \(x\) についてほぼ \(0.5\) ということです。\(p\) が大きくなると、\(p+1\) に対する \(2\sqrt{p}\) の比率は極めて小さくなるからです。
\(\#E\) を具体的に求めるアルゴリズムは、1985年にオランダ出身の数学者、レネ・ショーフ(Rene Schoof。英語読みでスクーフとも書かれる)が開発しました。その「ショーフのアルゴリズム」は、数学用語で言うと最初の「決定論的多項式時間アルゴリズム」です。平たく言うと「計算結果が100%正しいと数学的に保証される(=決定論的)計算可能な(=多項式時間)アルゴリズム」です。「ショーフのアルゴリズム」の具体的内容は、ここでは割愛します。
17. 楕円曲線暗号
楕円曲線暗号を構成する上で必要になるのが、有限群における「位数」の概念です。次の位数の話はすべての有限群に共通するので、群の演算を乗法的に書くことにします(掛け算、冪乗、単位元 \(e\)、などの記法を使います)。No.315 でやったように、演算を加法と考えても全く同じことになります。
位数
元の数が有限個の群 \(G\) を「有限群」といい、その元の個数を「群位数(group order)」と呼びます。群位数を \(|G|\) と表します。群の演算則だけから次のことが言えます。
単位元 \(e\) でない群 \(G\) の元を \(a\) とします。\(a\) の冪乗 \(a^n(1\leq n)\) の \(n\) を増やしていくと、ある時点で \(a^n=e\) となります。その理由ですが、
\(a^1,\:a^2,\:\:\cd\:,\:a^{|G|}\)
という \(|G|\) 個の元を考えてみます。もし \(|G|\) 個が全て相異なると、どれかが \(e\) のはずです。全てが相異なる元ではないとき、
\(a^j=a^i(1\leq i < j\leq|G|)\)
となったとすると、両辺に \(a\) の逆元を \(i\) 回掛けて、
\(a^{j-i}=e\)
が得られます。\(1\leq j-i < |G|\) なので、この範囲に \(e\) があります。そこで、つぎのように元 \(a\) の位数を定義できます。
17.1 | 位数の定義 |
有限群 \(G\) の任意の元 \(a\) について、
\(a^d=e\) r となる最小の\(d\) を \(a\) の "位数(order)" と言う。 |
さらに、元の位数については次の命題が成り立ちます。
17.2 | 位数と群位数 |
有限群 \(G\) の任意の元 \(a\) の位数を \(d\) とすると、\(d\) は群位数 \(|G|\) の約数である。 |
これはラグランジュの定理と呼ばれるものです。この定理が成り立つ理由は次の通りです。有限群 \(G\) の任意の元を \(a\) とし、集合 \(A\) を、
\(A=(a^1,\:a^2,\:\cd\:,\:a^d=e)\)
とします。集合 \(A\) の元は全て相異なります。なぜなら、もし、
\(a^j=a^i(1\leq i < j\leq d)\)
となったとすると、両辺に \(a\) の逆元を \(i\) 回掛けて、
\(a^{j-i}=e\)
となり、\(d\) が \(a^d=e\) となる最小の数であるという位数の定義に反するからです。さらに、集合 \(A\) の任意の元の逆元は集合 \(A\) に含まれます。つまり、\(a^d=e\) なので \(a^j(1\leq j < d)\) に対して \(a^{d-j}(1\leq d-j < d)\) が逆元です(ということは集合 \(A\) もまた群であり、これを \(G\) の部分群と言います)。
集合 \(A\) が \(G\) の全ての元を尽くしているなら 17.2 は成立します。そこで、集合 \(A\) に含まれない \(G\) の元があったとし、それを \(b_1\) とします。集合 \(A\) の全ての元に左から \(b_1\) を掛けて、集合 \(B_1\) を作ります。つまり、
\(B_1=(b_1a^1,\:b_1a^2,\:\cd\:,\:b_1a^d)\)
です。集合 \(A\) の元は全て相異なるので、集合 \(B_1\) の元も全て相異なります。さらに、集合 \(B_1\) の元で集合 \(A\) の元と同じものはありません。なぜなら、もし、
\(b_1a^i=a^j(1\leq i < j\leq d)\)
だとすると、\(a^i\) の逆元、\(a^{d-i}\)を右から掛けて、
\(b_1a^d=a^{d-i+j}\)
\(b_1=a^{d-i+j}=a^{j-i}\)
\(b_1=a^{d-i+j}=a^{j-i}\)
となりますが、\(1\leq j-i < d\) なので、これは \(b_1\) が集合 \(A\) の元であることを意味していて仮定に反します。つまり、集合 \(B_1\) の元で集合 \(A\) の元と同じものはありません。
集合 \(A\) と \(B_1\) で \(G\) の元の全てを尽くしているなら、\(2d=|G|\) となって 17.2 は証明できたことになります。そうではない場合、集合 \(A\) と \(B_1\) に含まれない \(G\) の元の一つを \(b_2\) として、集合 \(B_2\) を、
\(B_2=(b_2a^1,\:b_2a^2,\:\cd\:,\:b_2a^d)\)
と定義します。そうすると先ほど同じように、集合 \(B_2\) の元は全て相異なり、かつ、集合 \(A\) との重複はありません。さらに、集合 \(B_2\) の元は集合 \(B_1\) の元とも重複しません。なぜなら、もし、
\(b_2a^i=b_1a^j(1\leq i < j\leq d)\)
だとすると、\(a^i\) の逆元、\(a^{d-i}\)を右から掛けて、
\(b_2=b_1a^{d-i+j}=b_1a^{j-i}\)
となりますが、\(1\leq j-i < d\) なので、\(b_2\) が 集合 \(B_1\) の元という意味になり仮定に反します。つまり、集合 \(B_2\)の元は集合 \(B_1\) の元と重複しません。
以上の操作は \(G\) の元が残っている限り \(B_3B_4\:\cd\) と続けられます。そしてある時点で 残っている \(G\) の元がちょうど切りのよいところで無くなるはずです。\(B_{n-1}\) まで作ったときに \(G\) の元の全てを尽くしたとしたら、\(n_d=|G|\) です。これで 17.2 が証明できました。17.2 から直ちに次の2つが結論づけられます。
17.3 | |
有限群 \(G\) の任意の元 \(a\) について、
\(a^{|G|}=e\) である。 |
これは、群位数 \(|G|\) が 元 \(a\) の位数の倍数なのでそうなります。\(p\) を素数とし、\(G\) が \(p\) 未満の自然数からなる乗法群 \(\bs{F}_p^{*}\) だとすると、\(|G|=p-1\) なので、フェルマの小定理( 3.1 )そのものです。
また、\(n\) 未満の自然数で \(n\) と互いに素なものの集合を \(G\) とすると、\(G\) は \(\mr{mod}n\) の乗算に関して閉じた集合になり、逆元も定義できるので(2.3 参照)、群となります(= 既約剰余類群)。オイラー関数を用いると \(|G|=\varphi(n)\) と表せて、オイラーの定理( 7.1 )になります。
つまり 17.3 は、フェルマの小定理の一般化であると同時に、フェルマの小定理を一般化したオイラーの定理をさらに一般化したものと言えるでしょう。
17.4 | 群位数が素数の群 |
有限群 \(G\) の群位数 \(|G|\) が素数だとすると、
単位元 \(e\) を除く \(G\) の全ての元の位数は \(|G|\) である。 |
素数の約数は \(1\) と素数自身しかないので、単位元以外の元の位数は群位数に等しくなります。従って、群位数が素数の群では任意の元 \(a\) の冪乗が群全体に "バラける" ことになります。
楕円曲線暗号の構成
スカラー倍
ここから具体的な楕円曲線暗号のしくみに入ります。楕円曲線上の \(\bs{F}_p^{\:2}\) の点と零元 \(\mathcal{O}\) が作る加法群を \(E(a,\:b,\:p)\) とし、その群位数を \(\#E\) と書きます。楕円曲線暗号では \(E(a,\:b,\:p)\) における「スカラー倍」の演算を利用します。
楕円曲線上の \(\bs{F}_p^{\:2}\) の点の一つを \(G=(G_x,\:G_y)\) とし、\(d\) を \(G\) の位数、\(n\) を \(1\leq n\) の整数とします。\(G\) の \(n\) 倍(=スカラー倍)を \(nG\) と書き、
\(nG=\overbrace{G+G+\:\cd\:+G}^{n}\)
と定義します。この定義から、
\(dG=\mathcal{O}\)(零元)
です。また、\((dk)G=\mathcal{O}\) \((k=1,\:2,\:3,\:\cd)\) です。スカラー倍は「倍」という名前がついているため、整数と楕円曲線上の点の掛け算のように誤解しそうですが、掛け算ではありません。
\(\bs{nG}\) は、\(\bs{\bs{F}_p}\) 上の楕円曲線の点 \(\bs{G}\) を、楕円曲線の加法式を使って \(\bs{n}\) 回加算した結果という意味
です。従って、\(n,\:\:m\) を整数とすると次のような式が成り立ちます。
\((1)\:\:n(mG)=(nm)G=(mn)G=m(nG)\)
\((2)\:\:(n+m)G=nG+mG\)
\((2)\:\:(n+m)G=nG+mG\)
\((1)\) 式には、整数の乗算とスカラー倍が混在しています。また \((2)\) 式に整数の加算の \(+\) と、楕円曲線上の点の加算の \(+\) が混在していますが、意味するところは明確でしょう。さらに、
\((3)\:\:n\equiv m\:\:(\mr{mod}\:d)\) なら \(nG=mG\)
\((4)\:\:nm\equiv1\:\:(\mr{mod}\:d)\) なら \(m(nG)=G\)
\((4)\:\:nm\equiv1\:\:(\mr{mod}\:d)\) なら \(m(nG)=G\)
も成り立ちます。つまり、スカラー倍の "スカラー" の部分が式の場合、\(d\) を法とする演算でよいことになります。\(d\) は素数なので \(d\) を \(q\) と書くと、 "スカラー" 部分の式は有限体 \(\bs{F}_q\) での演算と言えます。たとえば \((4)\) は、
\((4)\:\:n^{-1}(nG)=G\)
と記述できます。
\(nG\) を求める計算は、\(E(a,\:b,\:p)\) の2倍式と加法式を使って可能です。例として \(133G\) の場合だと、\(133=2^7+2^2+1\) なので、
\(133G=2^7G+2^2G+G\)
となります。つまり、\(E(a,\:b,\:p)\) の2倍式を7回使って、
\(2^1G,\:\:2^2G,\:\:\cd\:\:,\:\:2^6G,\:\:2^7G\)
と順次計算し、加法式を2回使うと \(133G\) が求まります。これは \(n\) がたとえ巨大数であっても可能です。\(2^{256}\) は10進数で約80桁(256ビット)の巨大数ですが、それでも256回程度の2倍算と最大で256回程度の加算をすれば \(nG\) が求まります。このあたりは 4.2 の「冪剰余の計算アルゴリズム」と同じです。もちろん冪剰余と違って、2倍算も加算も単純な掛け算ではありません。\(E(a,\:b,\:p)\) の群演算は、定義式どおりの少々ややこしい式です。しかし計算が可能なことは確かです。
離散対数
スカラー倍の演算を、
\(P=nG\)
とします。上に書いたように、この計算は高速に可能ですが、その逆、つまり \(P\) と \(G\) を知って \(n\) 求めるのは困難になります。この \(n\) を求める問題を、加法群 \(E(a,\:b,\:p)\) における「離散対数問題」と呼びます。離散対数問題を解くのが不可能になるのは、\(G\) の位数 \(d\) が10進数で数10桁以上といった巨大数の場合です。その場合、\(P\) は \(d\) 種のバリエーションをとるので、\(n\) を求めるのは不可能になります。
位数 \(d\) が巨大数である \(G\) を求める方法の一つは、\(p\) を巨大な素数とし、群位数 \(\#E\) も素数であるような \(E(a,\:b,\:p)\) を選ぶことです。そうすると 17.4 により、零元 \(\mathcal{O}\) 以外の \(E(a,\:b,\:p)\) の全ての元の位数 \(d\) は \(\#E\) になり、その \(\#E\) は \(p+1\) の近辺にあるので、\(G\) をどのように選ぼうとも位数 \(d\) は巨大素数になります。
\(\#E\) が素数である \(E(a,\:b,\:p)\) では、任意の元 \(P\) と \(G\) について、\(nG=P\) となる \(n\) が唯一存在することになります。このことを、
\(\mr{log}_GP=n\)
と書くと、\(G\) は実数における通常の対数の "底(base)" に相当します。\(G\) は \(E(a,\:b,\:p)\) の元 = \(\bs{F}_p^{\:2}\) の元なので、\(G\) を「ベースポイント(base point)」と呼びます。このペースポイントを含め、楕円曲線暗号では、
\(E(a,\:b,\:p)\) : 楕円曲線 | |
\(G=(G_x,\:G_y)\) : ベースポイント | |
\(d\) : \(G\) の位数(素数) |
が公開されます。そして暗号化通信では、\(d\) より小さい数 \(k\) をランダムに選び
公開鍵 : \(kG\) | |
秘密鍵 : \(k\) |
とします。公開鍵だけを知っても秘密鍵は計算できない。これが楕円曲線暗号の原理です。なお、 \(\#E\) が 素数でなくても、位数 \(d\) が巨大素数である \(G\) を選ぶことで、楕円曲線暗号は成立します。
スカラー倍のイメージをつかむため、\(p\) がごく小さい数の場合で実験してみます。計算してみると、\(p=29,\:\:a=-1(=28),\:\:b=1\) のとき \(\#E=37\) となって、群位数が素数になります。\(y^2=x^3-x+1\) の解の一つは \((0,\:1)\) なので、これをベースポイント \(G\) としてスカラー倍を順次計算してみると次の通りとなります。
\(\phantom{11}G=(\:\phantom{1}0,\phantom{1}1\:)\) | \(19G=(\:10,11\:)\) |
\(\phantom{1}2G=(\:22,10\:)\) | \(20G=(\:20,\phantom{1}8\:)\) |
\(\phantom{1}3G=(\:27,13\:)\) | \(21G=(\:25,12\:)\) |
\(\phantom{1}4G=(\:\phantom{1}9,24\:)\) | \(22G=(\:17,24\:)\) |
\(\phantom{1}5G=(\:14,18\:)\) | \(23G=(\:\phantom{1}5,11\:)\) |
\(\phantom{1}6G=(\:11,25\:)\) | \(24G=(\:28,\phantom{1}1\:)\) |
\(\phantom{1}7G=(\:23,20\:)\) | \(25G=(\:\phantom{1}1,28\:)\) |
\(\phantom{1}8G=(\:12,\phantom{1}8\:)\) | \(26G=(\:\phantom{1}3,\phantom{1}5\:)\) |
\(\phantom{1}9G=(\:26,\phantom{1}8\:)\) | \(27G=(\:\phantom{1}2,\phantom{1}6\:)\) |
\(10G=(\:\phantom{1}2,23\:)\) | \(28G=(\:26,21\:)\) |
\(11G=(\:\phantom{1}3,24\:)\) | \(29G=(\:12,21\:)\) |
\(12G=(\:\phantom{1}1,\phantom{1}1\:)\) | \(30G=(\:23,\phantom{1}9\:)\) |
\(13G=(\:28,28\:)\) | \(31G=(\:11,\phantom{1}4\:)\) |
\(14G=(\:\phantom{1}5,18\:)\) | \(32G=(\:14,11\:)\) |
\(15G=(\:17,\phantom{1}5\:)\) | \(33G=(\:\phantom{1}9,\phantom{1}5\:)\) |
\(16G=(\:25,17\:)\) | \(34G=(\:27,16\:)\) |
\(17G=(\:20,21\:)\) | \(35G=(\:22,19\:)\) |
\(18G=(\:10,18\:)\) | \(36G=(\:\phantom{1}0,28\:)\) |
\(37G=\mathcal{O}\) |
群位数が素数なので \(G\) の位数は \(37\) となり、群位数と一致します。この計算を \(\bs{F}_p^{\:2}\) の平面に表示すると次の通りです。\(G\) と \(36G\) は赤丸、\(2G\) ~ \(35G\) は黒丸です。矢印は加算を示し、赤矢印は \(G+G\) と \(35G+G\) の加算です。
図18:\(\bs{E(-1,\:1,\:29)}\)(零元を除く)
\(\#E=37,\:\:G=(0,\:1),\:\:d=37\) |
スカラー倍を繰り返すごとに "楕円曲線" 上の合計\(36\)点を通り、それが乱雑に変化することが分かります。
振り返ってみると、RSA暗号(No.311)の安全性は巨大数の因数分解の困難性に依存しているのでした。またディフィー・ヘルマンの鍵交換(No.313)は、乗法群 \(\bs{F}_p^{*}\) における離散対数問題を解くことの困難性に依存しています。これらに使われる演算はいずれも整数の乗除算です。それに対して楕円曲線暗号に使われるのは、整数の乗除算よりは遙かに複雑な、楕円曲線上の加法群における「加算」です。ここに楕円曲線暗号の解読しにくさの要因があります。
実用的な楕円曲線暗号で公開するパラメータをどうやって作るか、その一例をあげます。
|
\(\#E\) が素数なので、\(G\) の位数 \(d\) は \(\#E\) に等しくなります。なお、\(\#E\) がたまたま \(p\) と一致すると離散対数問題が解けることが分かっているので、③ でそのようなケースを排除しておきます。
この決め方では、群位数 \(\#E\) の計算と素数判定を繰り返すことになり、多大な計算時間がかかることは想像に難くありません。しかしパラメータは1度計算すれば暗号通信の仕様として公開し、皆がそれを使えばいいわけです。最初の1回だけの計算時間より、その後の通信の安全性の方が重要です。
楕円曲線暗号のパラメータの一例を次に掲げます。secp160r1 という名称で公開されているパラメータです。群位数 \(\#E\:( > p)\) は素数です。\(p,\:\#E\) ともに10進で49桁の数です。
secp160r1
\(\begin{eqnarray}
&&p=&1461501637330902918203684\\
&&&832716283019653785059327\\
&&& (=2^{160}-2^{31}-1)\\
&&&\\
&&a=&1461501637330902918203684\\
&&&832716283019653785059324\\
&&& (=p-3)\\
&&b=&1632357913061681105466049\\
&&&19403271579530548345413\\
&&&\\
&&\#E=&1461501637330902918203687\\
&&&197606826779884643492439\\
&&&\\
&&G_x=&4258262317238883504465415\\
&&&92701409065913635568770\\
&&G_y=&2035201141629041078739914\\
&&&57957346892027982641970\\
&&&\\
&&d=&1461501637330902918203687\\
&&&197606826779884643492439\\
&&& (=\#E)\\
\end{eqnarray}\)
ちなみに、計算してみると、
\(\dfrac{\#E-(p+1)}{2\sqrt{p}}\fallingdotseq0.978\)
であり、\(\#E\) は「ハッセの定理」の上限付近にあります。
楕円曲線暗号版ディフィー・ヘルマンの鍵交換(ECDH)
楕円曲線暗号とは、以上のような「有限体上の楕円曲線が構成する加法群を利用した暗号方式」の総称です。その例として、ディフィー・ヘルマンの鍵共有(= DH、No.313「高校数学で理解する公開鍵暗号の数理」参照)を楕円曲線暗号で実現できます(ECDH と略称される)。鍵共有のプロセスは次のように進みます。しかるべき「公開鍵センター」が、皆が使う公開鍵として、
\(E(a,\:b,\:p)\) : 楕円曲線 | |
\(G=(G_x,\:G_y)\) : ベースポイント | |
\(d\) : \(G\) の位数(素数) |
をオープンにして(暗号通信の仕様書として公開して)おきます。以下のスカラー倍演算はすべて \(\bs{F}_p\) で行います。Alice と Bob が秘密鍵を共有したい場合、
暗号文による通信の開始にあたって、Alice は \(0 < k_A < d\) である乱数 \(k_A\) を発生させ、\(k_AG\) を Alice の公開鍵として(盗聴されている通信路を介して) Bob に送付
します。乱数 \(k_A\) は Alice の秘密鍵として秘匿します。次に同様に、
Bob は \(0 < k_B < d\) である乱数 \(k_B\) を発生させ、\(k_BG\) を Bob の公開鍵として(盗聴されている通信路を介して) Alice に送付
します。もちろん \(k_B\) は秘匿します。そして、
Alice は \(K_A=k_Ak_BG\) を共有の秘密鍵
Bob は \(K_B=k_Bk_AG\) を共有の秘密鍵
Bob は \(K_B=k_Bk_AG\) を共有の秘密鍵
とします。この作り方から \(K_A=K_B=K\) となるので、楕円曲線上の点である秘密鍵 \(K\) を共有できたことになり、以降はこれを使って暗号化通信(公開鍵ではない、高速な暗号化通信)を行います。使った秘密鍵は通信が終わったら捨てます。もちろん、\(K=(K_x,\:K_y)\) の \(K_x\) だけを秘密鍵としてもよいわけです。
原理は、オリジナルのディフィー・ヘルマンの鍵交換(DH)と全く同じです。ただ、オリジナルが \(\bs{F}_p^{*}\) での離散対数問題を利用していたのに対し、ECDH は \(E(a,\:b,\:p)\) での離散対数問題を利用した暗号であることが違います。
メッセージ伝送とデジタル署名
以降、前提として、
\(E(a,\:b,\:p)\) : 楕円曲線 | |
\(G=(G_x,\:G_y)\) : ベースポイント | |
\(d\) : \(G\) の位数(素数) |
が公開されているものとします。
メッセージ伝送
楕円曲線暗号によるメッセージ伝送方式の例として「楕円曲線 ElGamal 暗号」をとりあげます。これは、\(\bs{F}_p\) における離散対数問題を利用した ElGamal 暗号(No.313「高校数学で理解する公開鍵暗号の数理」の「13. 離散対数暗号」参照)の「楕円曲線版」です。
この暗号では、送るべきメッセージを \(m\)(=整数)とするとき、\(m\) を \(\bs{F}_p\) 上の楕円曲線の点 \(M=(x,\:y)\) と対応付けます。その対応付けの方法は送信者と受信者であらかじめ合意しておく必要があります。そのやり方の例として、\(m\) を \(\dfrac{d}{100}\) 未満の数となるように選びます。そして、
\(x=m\cdot100+i\:\:(i=0,\:1,\:2,\:\cd,\:99)\)
の \(100\) 個の中から、
\(x^3+ax+b\)
が平方数となるような \(x\) を選びます。\(x\) の約半数は \(y^2=x^3+ax+b\) を満たす \(y\) があるので、\(100\)個を試せば必ず \(x\) が見つかります。そこで \(x^3+ax+b\) の平方根を計算して \(y\) を求め、
\(M=(x,\:y)\)
を伝送するメッセージとします(\(y\) は2つありますが、どちらかを選びます)。\(M\) から \(m\) への復元は、\([\cd]\) を \(\cd\) を超えない最大の整数(=ガウス記号)として、
\(m=\left[\dfrac{x}{100}\right]\)
で可能です(=切り捨て除算)。この \(100\) に大きな意味はなく、コンピュータで実装するときには演算回数を減らすために \(2^n\) となる数を選ぶのがベターでしょう。
楕円曲線 ElGamal 暗号によるメッセージ伝送は次のように進みます。Bob から Alice にメッセージ \(m\) を送る例です。
まず、Alice と Bob は「楕円曲線暗号版ディフィー・ヘルマンの鍵交換(ECDH)」を使って秘密鍵 \(k_A\) と \(k_B\) を決め、公開鍵 \(k_AG\) と \(k_BG\) を交換しておきます。
Bob の暗号化手順
\(m\) を楕円曲線上の点 \(M\) に変換する。 | |
\(0 < k < d\) である乱数 \(k\) を発生させる。 | |
楕円曲線上の2点、\(M_1=kG\)、 \(M_2=M+kk_AG\) を計算し、\((M_1,\:\:M_2)\) のペア を暗号化メッセージとして Alice に送る。 | |
送信が終わると \(k\) は捨てる。 |
Alice の復号化手順
暗号の作り方から \(\begin{eqnarray} &&\:\:M&=M_2-kk_AG\\ &&&=M_2-k_AM_1\\ \end{eqnarray}\) なので、\(M_2-k_AM_1\) を計算して \(M\) を求める。この計算は \(k_A\) を知っている Alice にしかできない。 | |
\(M\) から メッセージ \(m\) を復元する。 |
デジタル署名
Bob から Alice にメッセージ \(m\) (楕円曲線上の点としては \(M\))を送るとき、次のようにしてデジタル署名を付加できます。ベースポイント \(\bs{G}\) の位数 \(\bs{d}\) は素数ですが、この素数を \(\bs{q}\) とも書き、スカラー倍における "スカラー部分の演算" を有限体 \(\bs{\bs{F}_q}\) での演算として表記します。また、ハッシュ関数を \(H(\:)\) と書きます(No.311「高校数学で理解するRSA暗号の数理(2)」の "補記" 参照)。
Bob の署名手順
\(1 < k < q-1\) である乱数を発生させる。 | |
\(kG\) を計算し、\(kG=(x,\:y)\) とおく。 | |
メッセージ \(m\) から ハッシュ値 \(h=H(m)\) を得る。\(H()\) は安全なハッシュ関数。 | |
\(s=(h+xk_B)\cdot k^{-1}\) を計算して \((x,\:s)\) をデジタル署名として Alice に送る。\(k_B\) は Bob の秘密鍵、\(k^{-1}\) は \(\bs{F}_q\) での \(k\) の逆数である。この計算は、秘密鍵とメッセージの両方を知っている者だけができる。なお、\(1 < k < q-1\) なので \(\bs{F}_q\) において \(k\neq k^{-1}\) である。 | |
送信が終わったら、乱数の \(k\) は捨てる。 |
Alice の検証手順
受け取ったメッセージ \(m\) から ハッシュ値 \(h=H(m)\) を計算する。 | |
\(h\)、Bob の署名 \((x,\:s)\)、ベースポイント \(G\)、Bob の公開鍵 \(k_BG\) から、次のスカラー倍計算を行って \(R\) を求める(スカラー部分の演算は \(\bs{F}_q\) での演算)。 \(R=(R_x,\:R_y)=s^{-1}(hG+x(k_BG))\)
ここで、
\(\begin{eqnarray} &&\:\:s^{-1}&=((h+xk_B)\cdot k^{-1})^{-1}\\ &&&=k\cdot(h+xk_B)^{-1}\\ \end{eqnarray}\) である。また、スカラー倍の計算部分は、 \(hG+x(k_BG)=(h+xk_B)G\) と変形できる。従って、\(R\) は、 \(\begin{eqnarray} &&\:\:R&=k\cdot(h+xk_B)^{-1}\cdot(h+xk_B)G\\ &&&=kG=(x,\:y)\\ \end{eqnarray}\) となるから、\((R_x,\:R_y)=(x,\:y)\) のはずである。 | |
受け取った署名の \(x\) を見て、\(x=R_x\) なら署名は Bob のものであり、かつ、メッセージは改竄されていないことが確証できる。 |
このデジタル署名のアルゴリズムは、ECDSA (Elliptic Curve Digital Signature Algorithm) と呼ばれるもので、メッセージ \(m\) の暗号化方式が「楕円曲線 ElGamal 暗号」でなくても通用します。一般に、メッセージ伝送方式とデジタル署名方式は独立です。
上にも書いたように、楕円曲線暗号とは「有限体上の楕円曲線が構成する加法群を利用した暗号方式」の総称です。「楕円曲線暗号版ディフィー・ヘルマンの鍵交換(ECDH)」や「楕円 ElGamal 暗号」以外にも種々の方式が提案され、実用化されています。
18. 結合則が成り立つことの検証と証明
前回の No.315 で、"結合則が成り立つ" ことの証明を後回しにしたので、ここに書きます。楕円曲線暗号は、楕円曲線上の有理点が群になることに依存した暗号です。その "群" であることの要件の一つは結合則が成り立つことであり、楕円曲線暗号の数学的背景として是非とも確認しておきたいところです。
楕円曲線上の3点について、
\((P_1+P_2)+P_3=P_1+(P_2+P_3)\)
となるのが結合則ですが、加法は数式で示されています。そこでまず、数式を使って簡単な例で確かめてみます。
数式による確認(トライアル)
図15:楕円曲線の例2
\(y^2=x^3-x+1\)
楕円曲線として、No.315 の図15でとりあげた、
\(y^2=x^3-x+1\)
を例とし、この楕円曲線上に2つの固定点と1つの任意点を取って計算してみます。使う記号は次の通りです。
\(P_1=(0,\:1)\)
\(P_2=(p,\:q)\:\:\:(q^2=p^3-p+1)\)
\(P_3=(1,\:1)\)
\(P_4=P_1+P_2\)
\(P_5=P_4+P_3=(P_1+P_2)+P_3\)
\(P_6=P_2+P_3\)
\(P_7=P_1+P_6=P_1+(P_2+P_3)\)
\(P_5=P_7\) が示せれば結合則が成り立っています。以下、No.315 の加法式(第2形)、
\(P_0=P_1+P_2\)
\(\left\{
\begin{array}{l}
\begin{eqnarray}
&&x_0=\lambda^2-x_1-x_2&\\
&&y_0=\lambda(x_1-x_0)-y_1&\\
&&\lambda=\dfrac{x_1^2+x_1x_2+x_2^2-1}{y_1+y_2}&\\
\end{eqnarray}
\end{array}\right.\)
を使って計算を進めると次のようになります。
\(P_4\) | \(=(x_4,\:y_4)=P_1+P_2\) | |
\(=(0,\:1)+(p,\:q)\) | ||
\(\lambda_4\) | \(=\dfrac{p^2-1}{q+1}\) | |
\(x_4\) | \(=\lambda_4^2-p\) | |
\(y_4\) | \(=-\lambda_4x_4-1\) | |
\(=\lambda_4p-\lambda_4^3-1\) |
\(P_5\) | \(=\) | \((x_5,\:y_5)\) | |
\(=\) | \(P_4+P_3=P_3+P_4\) | ||
\(=\) | \((1,\:1)+(x_4,\:y_4)\) | ||
\(\lambda_5\) | \(=\) | \(\dfrac{x_4^2+x_4}{\lambda_4p-\lambda_4^3}=\dfrac{p-\lambda_4^2-1}{\lambda_4}\) |
\(x_5\) | \(=\) | \(\lambda_5^2-x_4-1\) | |
\(=\) | \(\lambda_5^2-\lambda_4^2+p-1\) | ||
\(=\) | \(\dfrac{-p^2+2q+3}{(p+1)^2}\) |
途中、\(x_5\) の計算で \(q^2\) を \(p^2-p+1\) で置き換えました。さらに、\(\lambda_4=\dfrac{p^2-1}{q+1}\) を使って \(\lambda_5\) の式から \(\lambda_4\) を消去すると、
\(\lambda_5=\dfrac{-p^2+2q+3}{(p+1)(q+1)}\)
となります。これを用いて \(y_5\) を計算すると、
\(y_5\) | \(=\) | \(\lambda_5(1-x_5)-1\) | |
\(=\) | \(\tfrac{p^2(x_5-1)-p(q+1)-2qx_5+q-3x_5+2}{(p+1)(q+1)}\) | ||
\(=\) | \(\tfrac{-2p^4-p^3(q+7)+p^2(3q+5)+p(q+7)-11(q+1)}{(p+1)^3(q+1)}\) |
となり、\(P_5=(x_5,\:y_5)\) が求まりました。
\(P_6\) | \(=\) | \((x_6,\:y_6)\) | |
\(=\) | \(P_2+P_3=P_3+P_2\) | ||
\(=\) | \((1,\:1)+(p,\:q)\) | ||
\(\lambda_6\) | \(=\) | \(\dfrac{p^2+p}{q+1}\) | |
\(x_6\) | \(=\) | \(\lambda_6^2-p-1\) | |
\(y_6\) | \(=\) | \(\lambda_6(1-x_6)-1\) | |
\(=\) | \(\lambda_6(p+2-\lambda_6^2)-1\) |
\(P_7\) | \(=\) | \((x_7,\:y_7)=P_1+P_6\) | |
\(=\) | \((0,\:1)+(x_6,\:y_6)\) | ||
\(\lambda_7\) | \(=\) | \(\dfrac{x_6^2-1}{y_6+1}=\dfrac{(\lambda_6^2-p-1)^2-1}{\lambda_6(p+2-\lambda_6^2)}\) |
\(x_7\) | \(=\) | \(\lambda_7^2-x_6\) | |
\(=\) | \(\lambda_7^2-\lambda_6^2+p+1\) | ||
\(=\) | \(\dfrac{p^2}{\lambda_6^2}-p+1\) | ||
\(=\) | \(\dfrac{-p^2+2q+3}{(p+1)^2}\) |
ここで \(\lambda_6=\dfrac{p^2+p}{q+1}\) を使って \(\lambda_7\) の式から \(\lambda_6\) を消去すると、
\(\lambda_7=-\dfrac{2(p^2+p-q-1)}{(p+1)(q+1)}\)
となります。この \(\lambda_7\) を使って \(y_7\) を計算すると、
\(y_7\) | \(=\) | \(-\lambda_7x_7-1\) | |
\(=\) | \(\tfrac{p^2(\lambda_7-1)-2p-(2q+3)\lambda_7-1}{(p+1)^2}\) | ||
\(=\) | \(\tfrac{-2p^4-p^3(q+7)+p^2(3q+5)+p(q+7)-11(q+1)}{(p+1)^3(q+1)}\) |
となり、\(P_7=(x_7,\:y_7)\) が求まりました。以上の計算で、\(P_5=(\)\(x_5,\:y_5\)\()\) と \(P_7=(\)\(x_7,\:y_7\)\()\) は同じ点であることが分かり、この例では結合則が検証できました。
もちろんこれで結合則が証明できたわけではありません。しかし上の検証から分かるように、加法式によって結合則を証明するには計算が膨大になると推測できます。そこで次に、数式処理ソフトを使って証明します。
数式による証明(SymPy)
再度、記号の定義をはっきりさせます。
楕円曲線上の有理点の加法式 楕円曲線、\(y^2=x^3+ax+b\)上の有理点を、 \(P_1=(x_1,\:y_1)\) \(P_2=(x_2,\:y_2)\) \(y_1^2=x_1^3+ax_1+b\) \(y_2^2=x_2^3+ax_2+b\) とし、\(P_0\) を \(P_0=P_1+P_2\) \(P_0=(x_0,\:y_0)\) \(\lambda=\dfrac{y_2-y_1}{x_2-x_1}\) \(x_0=\lambda^2-x_1-x_2\) \(y_0=\lambda(x_1-x_0)-y_1\) と定義する。楕円曲線上の有理点はこの加法によって群となる(従って、結合則が成り立つ)。 |
群の要件の一つである結合則を証明するために、楕円曲線上の3点を、\(P_1,\:\:P_2,\:\:P_3\) とし、
\(P_1=(x_1,\:y_1)\)
\(P_2=(x_2,\:y_2)\)
\(P_3=(x_3,\:y_3)\)
とします。
\(y_1^2=x_1^3+ax_1+b\)
\(y_2^2=x_2^3+ax_2+b\)
\(y_3^2=x_3^3+ax_3+b\)
です。このとき、
\((P_1+P_2)+P_3=P_1+(P_2+P_3)\)
であれば結合則が成り立ちます。これを示すため、\(P_4,\:P_5,\:P_6,\:P_7\) を、
\(P_1+P_2=P_4\)
\(P_4+P_3=P_5\)
\(P_2+P_3=P_6\)
\(P_1+P_6=P_7\)
\(P_i=(x_i,\:y_i)\:\:(4\leq i\leq7)\)
と定義して、
\(P_5\:=\:P_7\)
であることを証明します。そのためには、
\(x_5=x_7\)
を示せれば十分です。以降で、Python のライブラリ SymPy の数式処理機能を使って、\(x_5=x_7\) であることを証明します。そのためのコードと実行結果を掲げますが、ポイントは、
\(y_i^2=x_i^3+ax_i+b\:\:(1\leq i\leq3)\)
の関係を使って、計算途中の要所要所で、\(y_1,\:y_2,\:y_3\) の2乗以上の項を無くすことです。次のコードでは ellipse_substitute 関数がそれを行っています。
import sympy as sy
x1, y1 = sy.symbols('x1, y1')
x2, y2 = sy.symbols('x2, y2')
x3, y3 = sy.symbols('x3, y3')
a , b = sy.symbols('a, b')
P1 = [x1, y1]
P2 = [x2, y2]
P3 = [x3, y3]
def ellipse_add(P1, P2):
u1, v1 = P1
u2, v2 = P2
L = (v2 - v1)/(u2 - u1)
u = L**2 - u1 - u2
v = L*(u1 - u) - v1
return [u, v]
def ellipse_substitute(expr):
w = sy.cancel(expr)
y1sq = x1**3 + a*x1 + b
w = w.subs(y1**3, y1sq*y1)
w = w.subs(y1**2, y1sq)
y2sq = x2**3 + a*x2 + b
w = w.subs(y2**3, y2sq*y2)
w = w.subs(y2**2, y2sq)
y3sq = x3**3 + a*x3 + b
w = w.subs(y3**3, y3sq*y3)
w = w.subs(y3**2, y3sq)
return sy.cancel(w)
P4 = ellipse_add(P1, P2)
P5 = ellipse_add(P4, P3)
x5 = ellipse_substitute(P5[0])
P6 = ellipse_add(P2, P3)
P7 = ellipse_add(P1, P6)
x7 = ellipse_substitute(P7[0])
diff = ellipse_substitute(x5 - x7)
print(f"x5 - x7 = {diff}")
|
実行結果
x5 - x7 = 0
|
この実行結果より、\(x_5\) と \(x_7\) の差異は厳密に \(0\) であり、\(x_5=x_7\) であることが証明されました。
このコードの ellipse_substitute 関数の補足ですが、SymPy のメソッドの cancel は、式を有理式の形(\(\tfrac{p}{q}\) の形。\(p,\:q\) は多項式)にととのえます。また subs は、式を別の式(ないしは値)で置き換えます。従って、関数は次の処理をします。
入力を有理式に変換する。 | |
\(y_i^3\) の項を \((x_i^3+ax_i+b)y_i\) に置き換える | |
\(y_i^2\) の項を \((x_i^3+ax_i+b)\) に置き換える | |
有理式に変換した結果を返す |
\(y_i^4\) の置き換えは、\(y_i^2\) の置き換えと同時に SymPy で処理されます。\(y_i^5\) 以上の項は、このコードでは発生しません。ちなみに、\(x_5\) と \(x_7\) を有理式の形で、
\(x_5=\dfrac{A}{B},\:\:x_7=\dfrac{C}{D}\)
と表わしたときの \(A,\:B,\:C,\:D\) は次の通りです。\(A,\:C\) は72項、\(B,\:D\) は40項もあるので手計算は無理ですが、SymPy で確認すると \(AD=BC\) が成り立っています。
\(A=x_1^4x_2^2x_3+\)\(x_1^4x_2x_3^2+\)\(6x_1^3x_2^3x_3-\)\(x_1^3x_2^2x_3^2+\)\(x_1^2x_2^4x_3-\)\(x_1^2x_2^3x_3^2+\)\(x_1x_2^4x_3^2+\)\(y_1y_2(-2ax_1^2+\)\(4ax_1x_2-\)\(4ax_1x_3-\)\(2ax_2^2-\)\(4ax_2x_3-\)\(8bx_3-\)\(4x_1^2x_2x_3-\)\(2x_1^2x_3^2-\)\(4x_1x_2^2x_3+\)\(4x_1x_2x_3^2-\)\(2x_2^2x_3^2)+\)\(y_1y_3(2ax_1^2+\)\(4ax_1x_2-\)\(6ax_2^2+\)\(8bx_1-\)\(8bx_2+\)\(6x_1^2x_2^2-\)\(4x_1x_2^3-\)\(2x_2^4)+\)\(y_2y_3(-6ax_1^2+\)\(4ax_1x_2+\)\(2ax_2^2-\)\(8bx_1+\)\(8bx_2-\)\(2x_1^4-\)\(4x_1^3x_2+\)\(6x_1^2x_2^2)+\)\(a^2(x_1^3-\)\(x_1^2x_2+\)\(x_1^2x_3-\)\(x_1x_2^2+\)\(6x_1x_2x_3+\)\(x_2^3+\)\(x_2^2x_3)+\)\(2ab(x_1^2-\)\(2x_1x_2+\)\(4x_1x_3+\)\(x_2^2+\)\(4x_2x_3)+\)\(8b^2x_3+\)\(a(x_1^4x_2+\)\(x_1^4x_3-\)\(x_1^3x_2^2+\)\(2x_1^3x_2x_3+\)\(x_1^3x_3^2-\)\(x_1^2x_2^3+\)\(10x_1^2x_2^2x_3-\)\(x_1^2x_2x_3^2+\)\(x_1x_2^4+\)\(2x_1x_2^3x_3-\)\(x_1x_2^2x_3^2+\)\(x_2^4x_3+\)\(x_2^3x_3^2)+\)\(2b(x_1^4-\)\(4x_1^3x_2+\)\(2x_1^3x_3+\)\(6x_1^2x_2^2+\)\(2x_1^2x_2x_3+\)\(x_1^2x_3^2-\)\(4x_1x_2^3+\)\(2x_1x_2^2x_3-\)\(2x_1x_2x_3^2+\)\(x_2^4+\)\(2x_2^3x_3+\)\(x_2^2x_3^2)\)
\(B=x_1^4x_2^2-\)\(2x_1^4x_2x_3+\)\(x_1^4x_3^2+\)\(6x_1^3x_2^3+\)\(2x_1^3x_2^2x_3-\)\(4x_1^3x_2x_3^2+\)\(x_1^2x_2^4+\)\(2x_1^2x_2^3x_3+\)\(6x_1^2x_2^2x_3^2-\)\(2x_1x_2^4x_3-\)\(4x_1x_2^3x_3^2+\)\(x_2^4x_3^2+\)\(y_1y_2(-4ax_1-\)\(4ax_2-\)\(8b-\)\(4x_1^2x_2+\)\(4x_1^2x_3-\)\(4x_1x_2^2-\)\(8x_1x_2x_3+\)\(4x_2^2x_3)+\)\(a^2(x_1^2+\)\(6x_1x_2+\)\(x_2^2)+\)\(8ab(x_1+\)\(x_2)+\)\(8b^2+\)\(2a(3x_1^3x_2-\)\(x_1^3x_3+\)\(2x_1^2x_2^2+\)\(x_1^2x_2x_3+\)\(3x_1x_2^3+\)\(x_1x_2^2x_3-\)\(x_2^3x_3)+\)\(4b(x_1^3+\)\(x_1^2x_2-\)\(x_1^2x_3+\)\(x_1x_2^2+\)\(2x_1x_2x_3+\)\(x_2^3-\)\(x_2^2x_3)\)
\(C=x_1^2x_2^4x_3-\)\(x_1^2x_2^3x_3^2-\)\(x_1^2x_2^2x_3^3+\)\(x_1^2x_2x_3^4+\)\(x_1x_2^4x_3^2+\)\(6x_1x_2^3x_3^3+\)\(x_1x_2^2x_3^4+\)\(y_1y_2(2ax_2^2+\)\(4ax_2x_3-\)\(6ax_3^2+\)\(8bx_2-\)\(8bx_3+\)\(6x_2^2x_3^2-\)\(4x_2x_3^3-\)\(2x_3^4)+\)\(y_1y_3(-6ax_2^2+\)\(4ax_2x_3+\)\(2ax_3^2-\)\(8bx_2+\)\(8bx_3-\)\(2x_2^4-\)\(4x_2^3x_3+\)\(6x_2^2x_3^2)+\)\(y_2y_3(-4ax_1x_2-\)\(4ax_1x_3-\)\(2ax_2^2+\)\(4ax_2x_3-\)\(2ax_3^2-\)\(8bx_1-\)\(2x_1^2x_2^2+\)\(4x_1^2x_2x_3-\)\(2x_1^2x_3^2-\)\(4x_1x_2^2x_3-\)\(4x_1x_2x_3^2)+\)\(a^2(x_1x_2^2+\)\(6x_1x_2x_3+\)\(x_1x_3^2+\)\(x_2^3-\)\(x_2^2x_3-\)\(x_2x_3^2+\)\(x_3^3)+\)\(2ab(4x_1x_2+\)\(4x_1x_3+\)\(x_2^2-\)\(2x_2x_3+\)\(x_3^2)+\)\(8b^2x_1+\)\(a(x_1^2x_2^3-\)\(x_1^2x_2^2x_3-\)\(x_1^2x_2x_3^2+\)\(x_1^2x_3^3+\)\(x_1x_2^4+\)\(2x_1x_2^3x_3+\)\(10x_1x_2^2x_3^2+\)\(2x_1x_2x_3^3+\)\(x_1x_3^4+\)\(x_2^4x_3-\)\(x_2^3x_3^2-\)\(x_2^2x_3^3+\)\(x_2x_3^4)+\)\(2b(x_1^2x_2^2-\)\(2x_1^2x_2x_3+\)\(x_1^2x_3^2+\)\(2x_1x_2^3+\)\(2x_1x_2^2x_3+\)\(2x_1x_2x_3^2+\)\(2x_1x_3^3+\)\(x_2^4-\)\(4x_2^3x_3+\)\(6x_2^2x_3^2-\)\(4x_2x_3^3+\)\(x_3^4)\)
\(D=x_1^2x_2^4-\)\(4x_1^2x_2^3x_3+\)\(6x_1^2x_2^2x_3^2-\)\(4x_1^2x_2x_3^3+\)\(x_1^2x_3^4-\)\(2x_1x_2^4x_3+\)\(2x_1x_2^3x_3^2+\)\(2x_1x_2^2x_3^3-\)\(2x_1x_2x_3^4+\)\(x_2^4x_3^2+\)\(6x_2^3x_3^3+\)\(x_2^2x_3^4+\)\(y_2y_3(-4ax_2-\)\(4ax_3-\)\(8b+\)\(4x_1x_2^2-\)\(8x_1x_2x_3+\)\(4x_1x_3^2-\)\(4x_2^2x_3-\)\(4x_2x_3^2)+\)\(a^2(x_2^2+\)\(6x_2x_3+\)\(x_3^2)+\)\(8ab(x_2+\)\(x_3)+\)\(8b^2+\)\(2a(-\)\(x_1x_2^3+\)\(x_1x_2^2x_3+\)\(x_1x_2x_3^2-\)\(x_1x_3^3+\)\(3x_2^3x_3+\)\(2x_2^2x_3^2+\)\(3x_2x_3^3)+\)\(4b(-\)\(x_1x_2^2+\)\(2x_1x_2x_3-\)\(x_1x_3^2+\)\(x_2^3+\)\(x_2^2x_3+\)\(x_2x_3^2+\)\(x_3^3)\)
3次曲線による証明
コンピュータを使った(=数式処理ソフトによる)証明では、なんとなく、証明した気になりません。その理由は、SymPy が正しい(バグがない)ことに依存しているからです。そこで以下は、シルヴァーマン、テイト著「楕円曲線論入門」にある証明を紹介します。これは、楕円曲線を含む3次曲線の性質を用いた証明で、本質をついた議論になっています。
結合則が成り立つのは、楕円曲線上の加法を「3次曲線と直線の交点」で決めていることに理由があります。「楕円曲線論入門」に、結合則が成り立つことを示した次の図があります。加法群の零元 \(\mathcal{O}\) を楕円曲線上にとった場合の図です。
図11:結合則 |
「楕円曲線論入門」より引用 |
|
\((P+Q)+R=P+(Q+R)\)
となるのが結合則ですが、
\((P+Q)+R=((P+Q)\!*\!R)*\mathcal{O}\)
\(P+(Q+R)=(P\!*\!(Q+R))*\mathcal{O}\)
\(P+(Q+R)=(P\!*\!(Q+R))*\mathcal{O}\)
です。ここで \(\!*\!\) の記号は、\(A\!*\!B\) と書くと \(A\) と \(B\) を結ぶ直線が楕円曲線と交わる点(で \(A\)、\(B\) 以外の点)の意味です。\(\mathcal{O}\) は零元でした。従って、結合則を証明するためには、
\((P+Q)\!*\!R=P\!*\!(Q+R)\)
が証明できればよいことになります。言葉で書くと、
\(P+Q\) と \(R\) を通る直線が楕円曲線と交わる点を \(T_1\) とし、\(P\) と \(Q+R\) を通る直線が楕円曲線と交わる点を \(T_2\) とすると、 \(T_1\) と \(T_2\) は同じ点である |
となります。上の図はそれを表しています。以下の証明では同じことですが、次を示します。
18.1 | 結合則 |
\(P+Q\) と \(R\) を結ぶ直線と、\(Q+R\) と \(P\) を結ぶ直線の交点を \(T\) とすると、楕円曲線は \(T\) を通る。 |
これは楕円曲線上の2点、\((P+Q)\!*\!R\) と \(P\!*\!(Q+R)\) が等しい(= 図11)ことと同じなので、以降は 18.1 が成り立つことを示します。そのためにまず、次の命題 18.2 を証明します。この証明の筋道は「楕円曲線論入門」に書かれているものです。
18.2 | 3つの3次曲線の交差 |
2つの3次曲線、\(C_1\) と \(C_2\) が相異なる9点、\(P_1,\:\:P_2,\:\:\cd\:,\:\:P_9\) を通るとする。 別の3次曲線 \(D\) が 9点のうちの8点、\(P_1,\:\:P_2,\:\:\cd\:,\:\:P_8\) を通るとき、\(D\) は \(P_9\) も通る。 |
これは「ケーレー・バカラック(Cayley-Bacharach)の定理」と呼ばれるものの一部です(Cayleyは英国、Bacharachはドイツの数学者。バカラックは英語読み。いずれも19世紀)。この定理は、
\(d_1\)次曲線と \(d_2\)次曲線が \(d_1d_2\)個の異なる交点で交わるとき、別の \((d_1+d_2-3)\)次曲線が交点のうちの \((d_1d_2-1)\)個を通ると、その別の曲線は残りの\(1\)点も通る
というもので、その3次元曲線の場合が 18.2 です。ここで言う3次曲線とは次の一般形で表される "3次曲線のすべて" であり、楕円曲線もその一部です。
\([\)3次曲線の一般形\(]\)
\(ax^3+bx^2y+cxy^2+dy^3+ex^2+fxy+gy^2+hx+iy+j=0\)
10個の係数(=パラメータ)、\(a,\:b,\:\:\cd\:,\:i,\:j\) を決めると3次曲線が一つ決まります。もちろん、各係数を定数倍した曲線は同じ曲線です。つまり、この形の3次曲線の係数は実質的に "9次元" と言えます。3次曲線なので \(a,\:b,\:c,\:d\) のうち少なくとも一つは \(0\) でないものがあります。その係数で全体を割れば、係数の数は9個になることからもわかります。9次元なので「相異なる8点を通る3次曲線」は無数にあります。
そこで、相異なる8点を通る3次曲線が一般的にどういう式で表現できるかを考えます。相異なる8点の座標を、
\(P_1=(x_1,\:y_1)\)
\(P_2=(x_2,\:y_2)\)
\(\vdots\)
\(P_8=(x_8,\:y_8)\)
\(P_2=(x_2,\:y_2)\)
\(\vdots\)
\(P_8=(x_8,\:y_8)\)
とします。まず、3次曲線が \(P_1\) を通るということは、10個のパラメータは次の制約条件を満足しなければなりません。
\(x_1^3a+x_1^2y_1b+x_1y_1^2c+y_1^3d+x_1^2e+x_1y_1f+y_1^2g+x_1h+y_1i+j=0\)
これは 10個の変数 \(a\) ~ \(j\) についての線型方程式(1次方程式)なので、係数を変数の前に記述しました。同様にして、3次曲線が \(P_2\) から \(P_8\) を通ることから7個の制約条件が得られます。これらをまとめると、
\(\left\{
\begin{array}{l}
\begin{eqnarray}
&&x_1^3a+x_1^2y_1b+\:\cd\:+y_1i+j=0&\\
&&x_2^3a+x_2^2y_2b+\:\cd\:+y_2i+j=0&\\
&&\:\:\vdots&\\
&&x_8^3a+x_8^2y_8b+\:\cd\:+y_8i+j=0&\\
\end{eqnarray}
\end{array}\right.\)
の、合計8つの制約条件が得られます。8個の点を通る3次曲線の10個のパラメータは、この8つの制約条件(連立1次方程式)を満たさなければなりません。ということは、\(10-8=2\) で、これらのパラメータは、制約条件のない自由な2つのパラメータで表現できることになります。
たとえば \(a\) と \(b\) を "2つのパラメータ" に選ぶと、残りの \(c\) ~ \(j\) は、\(\al_na+\beta_nb\:(n=c\:\cd\:j)\) という「\(a\) と \(b\) の1次式」で表現できます(\(\al_n,\:\beta_n\) は連立1次方程式の係数で決まる値)。しかしこれでは \(a=0\) かつ \(b=0\) のときに、すべてのパラメータが \(\bs{0}\) という自明な解しか得られません。\(x^3\) の項と \(x^2y\) の項がない3次曲線はいくらでもありうるので、自明ではない解の中に \(a=0,\:b=0\) となるものは当然あるはずです。つまり、\(\al_na+\beta_nb\) の形は連立1次方程式の解の全部は表していません。
では、上記の連立1次方程式の「自明ではない解すべてを表す一般解」はどういう形でしょうか。それには8つの方程式を満たす独立な数値の組(=連立1次方程式の解)を2組用意します。つまり無数にある解の中から2つをピックアップし、それをベクトル表現で、
\(\bs{V}_1=(a_1,\:b_1,\:\cd\:,\:j_1)\)
\(\bs{V}_2=(a_2,\:b_2,\:\cd\:,\:j_2)\)
\(\bs{V}_2=(a_2,\:b_2,\:\cd\:,\:j_2)\)
とします。"独立" とはこの場合、2つの数値群が異なった3次曲線を表現しているということです。そして、同時に \(0\) にはならない新たな2つのパラメータを導入します。それを \(\lambda_1,\:\:\lambda_2\) とすると、
\(\lambda_1\bs{V}_1+\lambda_2\bs{V}_2\)
が連立1次方程式の一般解(不定解)になります。自由な2つのパラメータの1次式で表現されていて、8つの方程式を満たすことが明らかだからです。この一般解をもとに3次曲線の方程式を表現します。そこで、
\(\begin{eqnarray}
&&f_1=&a_1x^3+b_1x^2y+\:\cd\\
&&&\cd\:+h_1x+i_1y+j_1\\
&&f_2=&a_2x^3+b_2x^2y+\:\cd\\
&&&\cd\:+h_2x+i_2y+j_2\\
\end{eqnarray}\)
の2つの関数を考えると、\(f_1=0\) の3次曲線と \(f_1=0\) の3次曲線は、共に8点を通ります。従って、
\(\lambda_1f_1+\lambda_2f_2=0\)
は8点を通り、2つの自由なパラメータで表現された3次曲線群です。従って、これが \(P_1,\:\:P_2,\:\:\cd\:,\:\:P_8\) を通るすべての3次曲線を表す一般形です。
以上を踏まえて命題 18.2 を検討します。命題を再掲すると、
2つの3次曲線、\(C_1\) と \(C_2\) が相異なる9点、\(P_1,\:\:P_2,\:\:\cd\:,\:\:P_9\) を通るとする。 別の3次曲線 \(D\) が 9点のうちの8点、\(P_1,\:\:P_2,\:\:\cd\:,\:\:P_8\) を通るとき、\(D\) は \(P_9\) も通る。 |
でした。この前半の2つの3次曲線の関数式を
\(C_1\::\:F_1=0\)
\(C_2\::\:F_2=0\)
\(C_2\::\:F_2=0\)
とします。\(F_1=0\) も \(F_2=0\) も9点、\(P_1,\:\:P_2,\:\:\cd\:,\:\:P_9\) を通る3次曲線です。従って \(F_1=0\) と \(F_2=0\) は \(P_1,\:\:P_2,\:\:\cd\:,\:\:P_8\) の8点を通る2つの3次曲線でもある。ということは、\(P_1,\:\:P_2,\:\:\cd\:,\:\:P_8\) の8点を通るすべての3次曲線は、
\(F=\lambda_1F_1+\lambda_2F_2=0\)
で表されます。従って、命題の後半に出てくる別の3次曲線 \(D\) が \(P_1,\:\:P_2,\:\:\cd\:,\:\:P_8\) の8点を通るとすると、\(D\) は \(F=\lambda_1F_1+\lambda_2F_2=0\) で表現できます。
ここでよく考えてみると、3次曲線 \(F=0\) は9点目の \(P_9\) を通るのでした。従って \(D\) も \(P_9\) を通ります。これで 18.2 が成り立つことが証明できました。以上を振り返ってまとめると次のようになります。
|
この "まとめ" で述べているように、8つの点を通る3次曲線は無数に存在します。8つの点を通る3次曲線は(一般には)一意に定まりません。そこで点を1つ増やすと、9つの点を通る3次曲線は(一般には)一意に定まります(9次元だから)。しかし、その9点が「2つの3次曲線の交点である9点」なら状況が変わります。その9点は独立ではなく、8点が決まれば残りの1点は自動的に決まる。従って、8点を通るすべての3次曲線は残りの1点も通ることになります。この例を図で示すと次の通りです。2つの3次曲線、\(C_1\) と \(C_2\) を、
\(C_1\::\)
\(x^3+\tfrac{1}{20}xy^2+\tfrac{1}{10}y^3-\tfrac{1}{10}x^2+\tfrac{1}{10}y^2-3x-y-\tfrac{2}{5}=0\)
\(C_2\::\)
\(\tfrac{1}{10}x^3+\tfrac{1}{20}x^2y+y^3+\tfrac{1}{10}x^2-\tfrac{1}{10}y^2-x-3y-\tfrac{2}{5}=0\)
とします。この2つの3次曲線は9つの点、\(P_1\) ~ \(P_9\) で交差します。それを正確に図示すると図19の通りです。
図19:9点で交差する2つの3次曲線、\(\bs{C_1,\:C_2}\) |
ここで、\(C_1,\:C_2\) とは別の、\(P_1\) ~ \(P_8\) の8つの点を通る3次曲線を作ると、それも \(P_9\) を通ります(図20)。図20 で、黄・緑・青の3つの3次曲線がその例です。
図20:8点を通る3次曲線は9点目も通る |
8点(たとえば \(P_1\) ~ \(P_8\))を通る3次曲線は \(P_9\) も通る(黄・緑・青の3つの曲線の例)。青色の3次曲線は2つの成分があるが、9点を通っている。 一般に3次曲線は(独立な)9点から一意に決まる(2次曲線の場合は5点から一意に決まる)。しかし、その9点が2つの3次曲線の交点であるとき、その9点は独立ではなく、8点が決まれば残りの1点は決まってしまう。つまり、9点のうちの8点を通る全ての3次曲線は、残りの1点も通る。 |
18.2 を踏まえて、楕円曲線の加法群で結合則が成り立つことを証明しますが、証明のポイントは、相異なる3つの直線を "3次曲線" として扱うことです。この扱いがなぜ可能かと言うと、3つの直線を、
\(f_1=a_1x+b_1y+c_1=0\)
\(f_2=a_2x+b_2y+c_2=0\)
\(f_3=a_3x+b_3y+c_3=0\)
\(f_2=a_2x+b_2y+c_2=0\)
\(f_3=a_3x+b_3y+c_3=0\)
としたとき、
\(F_L=f_1\cdot f_2\cdot f_3=0\) で表される2次元平面上の点の集合は3つの直線を表しているが、3次曲線の一般形であることに違いはない
からです。もちろん、\(F_L=0\) という曲線の方程式は、3次曲線の一般形の係数 \(a,\:b,\:\:\cd\:,\:i,\:j\) に特別の関係を持ち込んだものです。だからこそ3つの直線を表現しているわけです(数学用語で言うと "退化した" 3次曲線)。しかし特別の関係があるとしても 18.2 を証明した議論の筋道には全く影響しません。
具体的な例をあげると、次の通りです。まず、3次曲線との交点が3つある直線を2つ描き(赤で示す)、交点を \(P_1,\:P_2,\:P_3\)、\(P_4,\:P_5,\:P_6\) とします(図21)。
図21:3次曲線と2直線の交点(1) |
次に、\(P_1\) と \(P_4\) を結ぶ直線と、\(P_3\) と \(P_6\) を結ぶ直線を緑で描き、3次曲線との交点をそれぞれ \(P_7,\:\:P_8\) とします(図22)。
図22:3次曲線と2直線の交点(2) |
こうした上で、\(P_2\) と \(P_5\) を結ぶ直線を緑で、\(P_7\) と \(P_8\) を結ぶ直線を赤で描きます(図23)。
図23:3次曲線と2組の3直線の交点 |
ここで、
\(C_1\) : 3次曲線
\(C_2\) : 赤の3直線
\(C_3\) : 緑の3直線
とすると、\(C_1,\:\:C_2,\:\:C_3\) の 3つの "3次曲線" はすべて \(P_1\) ~ \(P_8\) の8点を通ります。すると 18.2 によって、この3つの "3次曲線" ははすべて、\(P_1\) ~ \(P_8\) 以外の、ある特別な点(=図23の点線丸印)を通ります。言い換えると、
直線 \(\bs{P_2\:P_5}\) と直線 \(\bs{P_7\:P_8}\) の交点は3次曲線上にある
ことになります。
以上を踏まえて、結合則を証明すべき図11を再掲します。図11 と図23 は数学的に全く同じであることが、以降の証明のポイントです。
図11:結合則 |
「楕円曲線論入門」より引用 |
証明すべきことは 18.1 の、
\(P+Q\) と \(R\) を結ぶ直線と、\(Q+R\) と \(P\) を結ぶ直線の交点を \(T\) とすると、楕円曲線は \(T\) を通る。 |
でした。図11で、
\(C_1\) : 点線の3直線から成る "3次曲線"
\(C_2\) : 実線の3直線から成る "3次曲線"
\(C_2\) : 実線の3直線から成る "3次曲線"
とすると、\(C_1\)(点線) と \(C_2\)(実線)は次の9つの点を通ります。
\(\mathcal{O}\) | |
\(P\) | |
\(Q\) | |
\(R\) | |
\(P\!*\!Q\) | |
\(Q\!*\!R\) | |
\(P+Q\) | |
\(Q+R\) | |
\(P+Q\) と \(R\) を結ぶ直線と、\(Q+R\) と \(P\) を結ぶ直線の交点 |
\(C_1\) と \(C_2\) が9つの点を通るのはそういう風に作図したからです。一方、楕円曲線は \(T\) 以外の \(P_1\) ~ \(P_8\) の8点を通ります。なぜならその8点は楕円曲線上の点として作ったからです。ところが \(T\) だけは違っていて、楕円曲線上の点として作ったのではなく2直線の交点です。しかし 18.2 によって楕円曲線は \(T\) も通ることになります。
これで、楕円曲線上の有理点が作る加法群で結合則が成り立つことの証明が完成しました。
零元を無限遠点にとる加法群ではどうなるでしょうか。この場合は「射影平面での3次曲線」を考える必要があります。射影平面での3次曲線の一般形は、
\([\)射影平面における3次曲線の一般形\(]\)
\(AX^3+BX^2Y+CXY^2+DY^3+EX^2Z+FXYZ+GY^2Z+\)
\(HXZ^2+IYZ^2+JZ^3=0\)
ですが、証明の筋道は \(xy\) 平面と全く同じです。というのも、証明のコアのところは「10変数の連立1次方程式(方程式数が8)の不定解が、一般形でどう表現できるか」であり、曲線方程式の未知数が \((x,\:y)\) の2つであっても \((X,\:Y,\:Z)\) の3つであっても証明の論理に影響がないからです。
というわけで、楕円曲線暗号で実際に使われる「無限遠点を零元にした加法群」においても結合則が成り立つのでした。
19. パスカルの定理
最後に余談ですが、18.2(ケーレー・バカラックの定理)から証明できる別の定理があります。「パスカルの定理」です。これはパスカルが16歳のときに発表した「円錐曲線試論」にあります。最も一般的な形で言うと次の通りです。
19.1 | パスカルの定理 |
円錐曲線上に異なる6点、\(P_1\) ~ \(P_6\) をとる。
直線 \(P_1P_2\) と \(P_4P_5\) の交点を \(Q_1\) 直線 \(P_2P_3\) と \(P_5P_6\) の交点を \(Q_2\) 直線 \(P_3P_4\) と \(P_6P_1\) の交点を \(Q_3\) とすると、\(Q_1,\:\:Q_2,\:\:Q_3\) は同一直線上にある。 |
これは非常に美しい定理です。どんな円錐曲線かを言っていないし(円、楕円、放物線、双曲線)、円錐曲線上の6点の位置も、その順序も何も言ってない。それにもかかわらず「同一直線上にある」という、シンプルで強い断定が結論にくる ・・・・・・。個人的経験を言うと、高校生時代にこの定理を知ってその "不思議さ" が印象的だったことを覚えています。
この定理の例を図24と図25、図26に示します。\(Q_1\) を \(P_7\)、\(Q_2\) を \(P_8\)、\(Q_3\) を \(T\) と書きました。円錐曲線が円か楕円であり、6点を円・楕円の周上に順に(= 一周するように)とった場合には、パスカルの定理は、
円・楕円に内接する6角形の対辺が作る2直線の交点3つは同一直線上にある
と簡潔に表現できます(図24)。図25の楕円上の点の位置は図24と同じですが、名前付けが違います。しかし3点が同一線上に並ぶのは同じです。このように6点は楕円上のどの位置にどの順序で配置してもよいわけです。
図24 パスカルの定理(1)楕円 |
図25 パスカルの定理(2)楕円 |
\(P_1\) ~ \(P_6\) の座標を図24と同じにし、名前付けを変えた。 |
図26 パスカルの定理(3)双曲線 |
定理の証明は次の通りです。3次曲線、\(C_1,\:\:C_2,\:\:D\) を、
赤色の "3次曲線" | |
青色の "3次曲線" | |
\(P_7\) と \(P_8\) を(\(T\) とは関係なく)結んだ直線と円錐曲線が作る、黒色の "3次曲線" |
とします。\(C_1\) と \(C_2\) は 、\(P_1\) ~ \(P_8\) と \(T\) を通ります。そういう風に作図したからです。一方、\(D\) は \(P_1\) ~ \(P_8\) を通ります。そうすると 18.2 より \(D\) は \(T\) も通ります。\(D\) は \(P_7\) と \(P_8\) を通るように作図しましたが、\(T\) を通るようには作図していません。それでも \(T\) を通る。
その \(T\) は、\(D\) の円錐曲線部分にはありません。なぜなら、\(T\) は直線 \(P_3P_4\) 上に(ないしは直線 \(P_6P_1\) 上に)ありますが、円錐曲線と直線の交点は高々2つであり、\(P_3,\:\:P_4\) が(ないしは \(P_6,\:\:P_1\) が)すでに円錐曲線上にあるからです。従って \(T\) は \(D\) の直線部分にあるしかない。これで証明が終わりました。
パスカルの定理のよくある証明は、円の場合に補助円を用いて証明し、それを "斜めから見たら" 楕円でも成り立つ、とするものです。しかしこの定理は、すべての円錐曲線(=2次曲線の一般形、\(ax^2+bxy+cy^2+dx+ey+f=0\) で表される曲線)で成り立つことが上の証明から分かります。
ちなみに、パスカルの定理は「円錐曲線」を「2直線」に置き換えても、交点ができるように点を配置すれば成り立ちます(パップスの定理と呼ばれる。パップスは4世紀のアレキサンドリアの数学者)。
図27 パップスの定理
軸を含む平面で円錐を2分割すると(平行でない)2直線になり、それは(退化した)円錐曲線とも言えますが、たとえ平行な2直線であっても2次曲線の一般形で表現できるので定理は成り立ちます。
楕円曲線暗号は「楕円曲線上の有理点による加法群」の上に作られた暗号ですが、
楕円曲線上の有理点で加法群を構成できることと、パスカルの定理が成り立つことには、意外にも共通の数学的理由がある
のでした。
補足:素数判定アルゴリズム
公開鍵暗号で使われる巨大素数の判定アルゴリズム(ミラー・ラビン法)を、
No.369「高校数学で理解する素数判定の数理」
に書きました。
(2024.3.18)
2021-07-24 10:52
nice!(0)