楕円曲線暗号

Takami Torao #EC #ECC #ECDSA
  • このエントリーをはてなブックマークに追加

概要

  1. 概要 [under construction]
  2. 楕円離散対数
  3. 楕円 Diffie-Hellman 鍵共有
  4. 楕円曲線暗号
  5. 楕円曲線 DSA
  6. 参考文献

楕円離散対数

Diffie-Hellman や ElGamal 暗号が有限体として使用している剰余環は 1 次元の数直線であり、その上限を超えると再びゼロから開始する性質を持っていた。これは数直線の端と端を接続して円状に変形したものと同じである。これを 2 次元のユークリッド座標系に置き換えると \(x,y\) はそれぞれの方向の上限を超えると再びゼロから開始し、それぞれ左右と上下を接続したトーラス状の構造となる。

2 次元ベクトル空間においてベクトル \(P\) が明らかなとき、任意の整数 \(n\) に対する \(nP\) の点を求めることは容易だが、\(P\) が明かであっても点 \(nP\) から \(n\) を求めることは難しい。このような \(P\) と \(nP\) が与えられたときに \(n\) を求める問題を楕円離散対数問題 (ECDLP, elliptic curve DLP) と呼ぶ。

楕円 Diffie-Hellman 鍵共有

楕円 Diffie-Hellman 鍵共有 (ECDH 鍵共有) は有限体を使用した Diffie-Hellman 鍵共有を楕円曲線に応用した鍵共有アルゴリズムである。パラメータとしてある位数 \(n\) の楕円曲線 \(E\) とその楕円曲線上のベースポイント \(G\) が共有されていると仮定する。

  1. A は秘密鍵 \(a \in \{1, \ldots,n-1\}\) をランダムに選択し公開鍵 \(aG\) を公開する。
  2. B も同様に秘密鍵 \(b \in \{1, \ldots, n-1\}\) をランダムに選択して公開鍵 \(bG\) を公開する。
  3. A と B の双方が相手の公開鍵に自分の秘密鍵を乗算することで共通の値 \(abG\) を共有することができる。

A も B も送受信する情報は公開鍵 \(xG\) のみであり、楕円曲線上の離散対数問題が解けない限り、公開鍵から秘密鍵 \(a\) または \(b\) を復元することはできない。

楕円 DH 鍵共有は DH 鍵共有より計算速度が速く鍵長も小さい。このためセッションごとに秘密鍵を作り直し共有するコストが低く、暗号通信に前方秘匿性 (PFS; perfect forward security, 秘密鍵が漏洩しても過去に遡って復号化できない性質) を持たせやすくなる。

楕円曲線暗号

ElGamal 暗号の有限体を楕円曲線に置き換えたもの。パラメータとしてある位数 \(n\) の楕円曲線 \(E\) とその楕円曲線上のベースポイント \(G\) が共有されていると仮定する。

鍵生成
A は秘密鍵 \(a \in \{1, \ldots,n-1\}\) をランダムに選択し公開鍵 \(aG\) を公開する。
暗号化
平文 \(m\) を \(E\) 上の点として表現したものを \(M\) とする。B は整数 \(r\) をランダムに選択し、暗号文 \((rG, M+raG)\) を A に送信する。
復号化
A は暗号文と秘密鍵 \(a\) を使用して \((M + raG) - a \times rG = M\) により平文 \(m\) を復元することができる。

ElGamal 暗号と同様に、暗号時に乱数 \(r\) を使用するため秘密鍵 \(a\) や平文 \(m\) が同じであっても暗号文は毎回異なる値となる。

楕円曲線暗号は RSA 暗号と比較してより小さな鍵で同等の安全性を持つ特徴がある。以下は [3] より引用。

RSA 暗号 1024 1219 2048 2832 11393
楕円曲線暗号 138 152 206 245 497

楕円曲線 DSA

有限体を使用する DSA の楕円曲線版。ハッシュ関数 \(h\)、\(q = \min \{ n | nP=0, n \gt 0\}\) とする。

鍵生成
A は秘密鍵 \(a \in \{1, \ldots,n-1\}\) をランダムに選択し公開鍵 \(aG\) を公開する。
署名
A は整数 \(k\) をランダムに選択する。\(kG\) の \(x\) 座標を \(r\) とする。平文 \(m\) に対して \(s = \frac{h(m) + ar}{k} \bmod q\) とし \((r,s)\) を署名とする。
検証
公開鍵 \(aG\) と与えられた平文 \(m\)、署名 \((r,s)\) に対して \[ \frac{h(m)}{s} G + \frac{r}{s} aG = \frac{h(m)}{s} G + \frac{ar}{s} G = \frac{h(m) + ar}{s} G = kG \] を計算する。署名時の設定より、得られた \(kG\) の \(x\) 座標が \(r\) と等しければ署名は正しい。

参考文献

  1. 辻井重男, 笠原正雄, 有田正剛, 境隆一, 只木孝太郎, 趙晋輝, 松尾和人, "暗号理論と楕円曲線", 森北出版 (2008)
  2. J.A. ブーフマン, "暗号理論入門 原書第3版, 丸善出版 (2012)
  3. 光成滋生, "クラウドを支えるこれからの暗号技術", 秀和システム (2015)