ECDSA 【Elliptic Curve Digital Signature Algorithm】楕円曲線DSA

概要

ECDSA（Elliptic Curve Digital Signature Algorithm）とは、楕円曲線上の離散対数問題と呼ばれる数学上の問題を安全性の根拠とするデジタル署名方式。整数の離散対数問題を用いるDSA(デジタル署名アルゴリズム)に比べ短い、鍵長で同等の安全性を実現することができる。

楕円曲線とは y² = x³ + ax + b という形で表される曲線で、この曲線上の二点の座標の関係について特殊な加算法を定義する。ある点Gについて自身を加算することにより「2倍」を求めることができるが、これを繰り返すことで任意のn倍（nG）を求めることができる。また、加算を続けていくとp回後に再びGに戻ってくることが知られており、どのような加算の結果もp個の点のうちのいずれかを指すことになる。

Gをn倍すると点Xに到達する場合に、nとGからXを求めるのは容易な一方、XとGからnを求める（XはGを何倍したものかを割り出す）ことは困難で、効率よく計算する方法は発見されていない。これを楕円曲線上の離散対数問題（ECDLP：Elliptic Curve Discrete Logarithm Problem）という。

送信者は1からpの間でランダムなnを選んで秘密鍵とし、楕円曲線上でGをn倍した点Qを相手方に渡す（誰に見られても良い）公開鍵とする。送信者は署名にあたってランダムなkを選択し、Gをk倍した点のx座標（rとする）を算出する。kとr、メッセージのハッシュ値、秘密鍵を組み合わせて特定の計算を行い、値sを得る。rとsの組み合わせが署名となる。

受信者は受け取ったメッセージのハッシュ値とs値、送信者の公開鍵Qを用いてrに相当する値を算出することができる。これが送信者から署名として送られてきたrに一致すれば、確かに送信者しか知らない秘密鍵nで正しく署名されていると確認することができる。

DSAでは80ビット安全性（攻撃者が解読に最低2⁸⁰回の試行を要する）を得るのに1024ビットの鍵長が必要とされるが、ECDSAでは160ビットの鍵で同程度の安全性を得ることができるとされる。ECDSAはSSHやTLSなど主要な暗号通信方式の仕様の一部として取り入れられており、広く普及が進んでいる。

(2022.3.19更新)