DSA 【Digital Signature Algorithm】デジタル署名アルゴリズム

概要

DSA（Digital Signature Algorithm）とは、離散対数問題と呼ばれる数学上の問題を安全性の根拠とするデジタル署名方式の一つ。ElGamal 署名(エルガマル署名)の改良版で、米国政府標準のデジタル署名アルゴリズムとして採用されている。

離散対数問題（DLP：Discrete Logarithm Problem）とは「素数pと自然数gが与えられたとき、ある自然数xに対してgのx乗をpで割った余りyを求めるのは容易だが、yからxを求めるのは困難である」という問題で、DSAではpやgなどからyを含む公開鍵（複数の値の組として表される）を生成し、xを秘密鍵とする。

署名者は送信メッセージのハッシュ値と秘密鍵を含む計算によりデジタル署名を生成してメッセージに添付する。検証者は署名者の公開鍵を取り寄せて検算を行えば、署名が真正で改竄されていないことを確かめることができる。攻撃者が正しい署名を偽造するにはxを割り出さなければならないが、これを効率よく探索する手法は未だ発見されていない。

DSAはすでに知られていたElGamal 署名を元に、1993年にNIST（米国立標準技術研究所）によって連邦情報処理標準FIPS 186として規格化された。2009年改訂のFIPS 186-3では楕円曲線上の離散対数問題を用いるECDSA（Elliptic Curve DSA）も選択できるようになり、従来より短い鍵長で同等の安全性を確保できるようになった。

ハッシュ関数として当初はSHA-1が採用されたが、2000年代に入ると技術の進歩で十分安全とは言えなくなってきたため、2013年に改訂されたFIPS 186-4ではSHA-2も選択できるよう改められた。

(2022.9.12更新)