楕円曲線暗号

わからん。

楕円曲線暗号 (ECC) の数学的基礎

楕円曲線暗号の安全性は、有限体上の楕円曲線がなす群における離散対数問題 (Elliptic Curve Discrete Logarithm Problem, ECDLP) の困難性に根拠を置いています。

---

1. 楕円曲線上の群構造

まず、体 $K$ 上で定義されるワイエルシュトラス方程式
$y^2=x^3+ax+b$
（ただし、$4a^3+27b^2\ne 0$）の解 $(x,y)\in K\times K$ と、無限遠点 $\mathcal{O}$ を元とする集合を考えます。

この集合には、幾何的な加算を定義することで、$\mathcal{O}$ を単位元とするアーベル群を構成できます。

• 単位元: 無限遠点 $\mathcal{O}$
• 加算 ($P+Q$): 異なる2点 $P,Q$ を通る直線が曲線と交わるもう1つの点を$R^{\prime }$とし、そのx軸に対する対称点を $R$ とすると、$P+Q=R$ と定義します。
• 2倍算 ($2P$): 点 $P$ における接線が曲線と交わるもう1つの点を$R^{\prime }$とし、そのx軸に対する対称点を $R$ とすると、$2P=R$ と定義します。
• 逆元 ($-P$): 点 $P(x,y)$ の逆元は、x軸に対して対称な点 $(x,-y)$ です。

---

2. 有限体への適用

暗号で実際に用いるのは、実数体 $\mathbb{R}$ ではなく、位数 $p$（$p$ は素数）の有限体（素体） ${\mathbb{F}}_p$ です。
方程式は $\mathrm{mod}p$ で考えられ、曲線上の点の集合 $E({\mathbb{F}}_p)$ もまた有限アーベル群をなします。この群の位数を位数 (order) と呼びます。

スカラー倍算 ($kP$) は、この群における加算を $k$ 回繰り返す操作です。
$kP=\underset{k\text{ times}}{\underbrace{P+P+\cdots +P}}$
このスカラー倍算は、バイナリ法（Double-and-Add） などを用いれば効率的に計算できます。

---

3. 離散対数問題 (ECDLP)

ECDLPとは、ベースポイントとなる生成元 $G$ と、スカラー倍算の結果である点 $Q=dG$ が与えられたときに、整数 $d$ を求める問題です。

• 秘密鍵: 整数 $d$
• 公開鍵: 点 $Q$

$d$ と $G$ から $Q$ を計算するのは容易ですが、$Q$ と $G$ から $d$ を求めるのは非常に困難です。これがECCの安全性の根幹です。

---

P-256 (secp256r1) の具体的なパラメータ

P-256は、secp256r1 とも呼ばれる具体的な曲線の規格です。以下のパラメータで定義されます。

1. 素体 ${\mathbb{F}}_p$

• 素数 $p$: 256ビットの素数で、特定の構造を持つメルセンヌ素数に近い形をしています。
  $p=2^{256}-2^{224}+2^{192}+2^{96}-1$
  この特殊な形により、 $\mathrm{mod}p$ の計算（特に剰余算）を高速に行うことができます。

2. 曲線の係数

• 係数 $a$: $a=-3$
• 係数 $b$: NISTが公開している特定の256ビットの整数。
  $b=\text{41058363725152142129326129780047268409114441015993725554835256314039467401291}$

これにより、曲線の方程式は $y^2\equiv x^3-3x+b(\mathrm{mod}p)$ となります。

3. 群のパラメータ

• 生成元 (ベースポイント) $G$: 曲線上の特定の点 $(G_x,G_y)$。
• 位数 $n$: $G$ によって生成される巡回部分群の位数。$n$ も256ビットの素数です。
  $n=\text{FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551}$ (16進数)
  秘密鍵 $d$ は、$1\le d<n$ の範囲からランダムに選ばれます。

---

ECDSA のアルゴリズム

ECDSAは、この群構造を利用して署名を生成・検証します。

• $H$: ハッシュ関数 (SHA-256など)
• $z$: 署名対象メッセージのハッシュ値 $H(m)$ を整数に変換したもの。

署名生成

1. 秘密鍵 $d$ を用意する。
2. 一時的な秘密鍵（nonce）$k$ を、$1\le k<n$ の範囲からランダムに生成する。
3. スカラー倍算を行い、点 $(x_1,y_1)=kG$ を計算する。
4. $r=x_1(\mathrm{mod}n)$ を計算する。$r=0$ なら $k$ を選び直す。
5. $s=k^{-1}(z+rd)(\mathrm{mod}n)$ を計算する。$s=0$ なら $k$ を選び直す。
6. 署名はペア $(r,s)$ となる。

注意: $k$ の値は絶対に再利用してはならず、推測不可能でなければなりません。$k$ が漏洩・重複すると、署名から秘密鍵 $d$ が算出されてしまいます。

署名検証

1. 公開鍵 $Q$ を用意する。
2. $u_1=s^{-1}z(\mathrm{mod}n)$ を計算する。
3. $u_2=s^{-1}r(\mathrm{mod}n)$ を計算する。
4. 点 $(x_1,y_1)=u_{1}G+u_{2}Q$ を計算する。
5. $x_1(\mathrm{mod}n)=r$ が成立すれば、署名は正当である。

この検証が成立する理由は、
$(x_1,y_1)=u_{1}G+u_{2}Q=s^{-1}zG+s^{-1}r(dG)=s^{-1}(z+rd)G=(k^{-1}(z+rd){)}^{-1}(z+rd)G=kG$
となり、署名時に計算した点と一致するためです。