デジタル署名とは、書面上の手書き署名のセキュリティ特性を模倣するために用いられる公開鍵暗号技術の一種である。

## 概要

デジタル署名は通常3つのアルゴリズムからなる。一つは"鍵ペア"を生成する鍵生成アルゴリズム。もう一つは、利用者の秘密鍵を用いて署名を生成するアルゴリズム、それと利用者の公開鍵を用いて署名を検証するアルゴリズムである。署名生成処理で作り出されたデータも"デジタル署名"と呼ぶ。

デジタル署名は"メッセージ"の認証機能を提供する。メッセージは、電子メール、契約書、あるいはより複雑な暗号プロトコルで送受されるデータでも何でも良い。

認証局が発行する公開鍵証明書では、認証局の社会的な信頼性を担保に、利用者の公開鍵と利用者の結びつきを保証している。その際、証明書が(公開鍵使用者が信頼する)認証局によって発行されたものであることを証明するために、デジタル署名が使われている。

デジタル署名はしばしば電子署名(署名の意図を伝える任意の電子データを指す上位語)を実装する為に用いられるが、全ての電子署名がデジタル署名を用いる訳ではない。

日本、アメリカおよび欧州連合を含めて幾つかの国では、電子署名は法律上の意義がある。しかしながら、電子署名に関する法律は、その法律上の重要性をやや曖昧にしておき、暗号によるデジタル署名に関して法を適用できるか否かについて、必ずしも明確にしない。

## 定義

デジタル署名は一般的には3つのアルゴリズムから成る。

- 鍵生成アルゴリズムG - 署名者の"鍵ペア"(PK, SK)を生成する。PKは公開する検証鍵、そしてSKは秘密にする署名鍵である。
- 署名生成アルゴリズムS - メッセージmと署名鍵SKを入力とし、署名σを生成する。
- 署名検証アルゴリズムV - メッセージm、検証鍵PK、署名σを入力とし、承認または拒否を出力する。

主に2つの特性が必要とされる。第一に、正当な署名鍵で生成された署名は、対応する検証鍵によって常に承認されること。つまり、署名鍵SKと検証鍵PKが対応する鍵ペアである場合、任意のメッセージmについて、V (m, PK, S (m, SK))は承認が出力される必要がある。第二に、いかなる攻撃者であっても(PKを知っているだけでは)有効な署名を生成する事は困難であることである。

## 歴史

著名な論文である「New Directions in Cryptography」において、ホイットフィールド・ディフィー(Whitfield Diffie)およびマーティン・ヘルマン(Martin Hellman)はデジタル署名という理論体系が存在するという推測とその概念について初めて著した。

程なく、ロナルド・リベスト(Ronald Rivest)、アディ・シャミア(Adi Shamir)、およびレオナルド・エーデルマン(Len Adleman)は、基本的なデジタル署名に用いる事ができるRSAアルゴリズムを開発した(これはただ単に概念実証としての役目だけを果たす事に注意されたい。単純なRSA署名は安全ではない)。デジタル署名を提供し広く市販された最初のソフトウェア・パッケージは、RSAアルゴリズムを用いて1989年に発売されたLotus Notes 1.0である。

基本的なRSA署名は以下のように算出される。RSA署名鍵を生成するために、2つの大きな素数の積である係数Nと一緒に、φがオイラーのφ関数である時e d = 1 mod φ(N)を満たす整数eおよびdを含むRSA鍵ペアを一つ単に生成する。署名者の公開鍵はNとeから成り、署名者の秘密鍵はdを含む。

メッセージmに署名するため、署名者はσ=m mod Nを計算する。検証するために、受信者はσ = m mod Nを照合する。

前述のように、この基本的な仕組みはあまり安全ではない。攻撃を防ぐため、まず最初にメッセージmに暗号ハッシュ関数を適用し、それからその結果に前述のRSAアルゴリズムを適用する事ができる。このやり方は所謂ランダム・オラクル・モデルにおいて安全を証明できる。

その他のデジタル署名方式は、RSAに次いですぐ、最初にランポート署名(Lamport signature)、マークル署名(Merkle signature、別名" マークル木"(Merkle tree)あるいは単に" ハッシュ木"(Hash tree))、そしてラビン署名(Rabin signature)が開発された。

1984年、シャフィ・ゴールドワッサー、シルビオ・ミカリ、ロナルド・リベストはデジタル署名方式のセキュリティー要件を最初に厳格に定義した。彼らは攻撃モデルの段階を次のように示した。

1. 唯鍵攻撃(Key-Only Attack)では、公開されている検証鍵だけを前提とした攻撃が行われる。
2. 既知文書攻撃(Known Message Attack)では、既知の様々な文書の有効な署名を前提とした攻撃が行われるが、攻撃者に文書は選択されない。
3. 選択文書攻撃(Chosen Message Attack)では、攻撃者は最初に選択した任意の文書への署名を入手し、その署名を前提とした攻撃が行われる。

彼らは攻撃結果の段階も次のように示した。

1. 全面的解読(total break)とは、署名鍵を再生されるという結果をもたらすものである。
2. 普遍的偽造(universal forgery)攻撃とは、任意の文書の署名も偽造できる署名アルゴリズムが発見されるという結果をもたらすものである。
3. 選択的偽造(selective forgery)攻撃とは、敵に選択された文書の署名が偽造されるという結果をもたらすものである。
4. 存在的偽造(existential forgery)とは、ただ単に敵に知られていない何らかの有効な文書/署名の対が発見されるだけという結果をもたらすものである。

また彼らは、選択文書攻撃でさえ対抗し存在的偽造でさえ防ぐ事が初めて立証できる、GMR署名方式も提示した。

殆どの初期の署名方式は類似していた。それらは、RSA関数などの落とし戸置換(trapdoor permutation)の使用か、あるいはラビン署名方式の場合は合成数Nを法とする二乗の計算を必要とする。落とし戸置換族は、パラメータで指定される置換の集まりであり、その置換の順方向への計算は容易だが、逆方向への計算は困難である。しかしながら、全てのパラメータについて逆方向の計算を容易にする"落とし戸"が存在する。パラメータを公開鍵、落とし戸を秘密鍵とし、また暗号化は順方向へ復号は逆方向へ置換を計算する事に対応させれば、落とし戸置換は公開鍵暗号システムとしてみなす事ができる。また、落とし戸置換はデジタル署名方式とみなす事もでき、秘密鍵を用いた逆方向の計算を署名と考え、また順方向の計算は署名を検証するためにされると考えればよい。署名は復号に相当し検証は暗号化に相当するという対応により、デジタル署名は公開鍵暗号方式を踏まえて説明される事が多いが、これはデジタル署名を算出する唯一の方法ではない。

直接使われると、この種類の署名方式は存在的偽造への唯鍵攻撃に対して脆弱である。偽造文書を作り出すため、攻撃者は任意の署名σを取り出し、そしてその署名に対応する文書mを見つけ出すために検証処理を使用する。しかしながら、実際にはこの種類の署名が直接使われる事は無い。もっと正確に言えば、署名される文書は、最初にハッシュ化されて短い要約(メッセージ・ダイジェスト)となり、要約に対して署名処理がなされる。その結果、この偽造攻撃はσに対応するハッシュ関数の出力を生成するだけである。ハッシュ関数の出力は元の文書の有用性に繋がる物ではなく、攻撃を招く事にはならない。ランダム・オラクル・モデルでは、署名のこのhash-and-decrypt形式は、選択文書攻撃でさえ存在的偽造は不可能である。

文書全体の代わりにそのようなハッシュ(またはメッセージ・ダイジェスト)に署名する幾つかの理由がある。

- 効率性: 一般的にハッシュを計算する事は実際に署名する事より遥かに速いので、署名は非常に短くなり従って時間を節約するようになる。
- 互換性: 文書は通常ビット列であるが、ある署名方式は他の定義域で動作する(例えばRSAの場合、合成数Nを法とする整数)。ハッシュ関数は任意の入力を適切な形式へ変換する事に使う事ができる。
- 完全性: ハッシュ関数が無い場合は、"署名すべき"文章は、署名方式が直接処理できるように小さい単位に分割されなければならないであろう。しかしながら、署名された部分の受信者は、全ての部分が適切な順番で存在しているかどうか、認識する事ができない。

## デジタル署名の利点

以下はデジタル署名をコミュニケーションに適用する最も一般的な理由である。

### 認証

文書を送信する実体に関する情報がしばしばその文書に含まれる事があるが、その情報は不正確である可能性がある。デジタル署名は文書の発信元を認証する事に使う事ができる。デジタル署名に用いる秘密鍵の所有権が特定の利用者へ結び付けられる時は、有効な署名は文書がその利用者から送信されたという事を示す。送信者の真正性について高い信頼度の重要性は、金融に関する内容の時に特に明白である。例えば、ある銀行の支店がある口座の残高について変更を要求する指示を本店へ送る場面を仮定する。もしそのようなメッセージが権限が与えられた発信元から本当に送信されたという事を本店が確信していなければ、そのような要求に応える事は致命的な過ちになる事になる。

### 完全性

多くの筋書きでは、文書の送信者と受信者は文書が転送中に改竄された事が無いという確信を必要とするであろう。暗号は文書の内容を隠蔽するが、それを理解せずに暗号化された文書には改変の可能性がある(頑強性がある物として知られている幾つかの暗号アルゴリズムはこれを防止するが、その他は防止しない)。しかしながら、もし文書がデジタル署名されていたならば、文書のどんな改変でも署名が無効になるであろう。更に、有効な署名がなされた新しい文書を生成するために、文書とその署名を改変する効果的な方法はない。なぜならば、これはまだ多くのハッシュ関数で計算的に実行不可能であると見なされている(衝突耐性参照)。

## デジタル署名の欠点

その実用性にもかかわらず、デジタル署名は私たちが解決を願う全ての問題を単独で解決する訳ではない。

### デジタル署名と信頼できるタイムスタンプの関連性

本来、デジタル署名アルゴリズムとプロトコルは構成する文書が署名された日付と時刻に関する確実性を提供しない。署名者は署名にタイムスタンプを載せているかも載せていないかも知れない。また文書自体に日付が記載されているかも知れない。しかしその後に読む人は、例えば署名者が署名の日時を実際より前にしていないと確信できない。デジタル署名に加えて信頼できるタイムスタンプを使用する事で、その様な悪用を実行不可能にする事ができる。

### 否認防止

暗号の世界では、否認という単語はメッセージに対する責任を放棄するあらゆる行為を指す(司法の世界における否認とは意味合いが大きく異なる)。メッセージの受信者は、その署名者と完全性に関する主張を強固にするために、第三者(例えば裁判所)へ署名されたメッセージを示す事ができる。そのため受信者は、後になって容易に否認されないようにするため、送信者の署名を強く主張する事ができる。しかしながら、利用者が秘密鍵の秘匿性を失う事は、その鍵を用いた(そして表面上その利用者'から'の)全てのデジタル署名は疑わしい、という事を意味するであろう。それでもなお、利用者の署名鍵を拒否せずに、利用者は署名されたメッセージを否認できない。それは信頼できるタイムスタンプが無いという事実によって悪化する。したがって、(鍵が危殆化した後に)新しく作られた文書は古いものやそれ以上に複雑な署名鍵の失効から切り離す事はできない。公開鍵に関連する利用者鍵を証明し署名を否認する事ができないように、通常は認証局はリポジトリと呼ばれる公開鍵の公開データベースを保持する。期限切れの証明書は普通はそのデータベースから削除される。データの否認防止サービスが提供される場合、ある期間に古い証明書を保持する事は、認証局のセキュリティポリシーと責任の問題である。

## 更なるセキュリティ対策

### ICカードへの秘密鍵の格納

全ての公開鍵暗号システムは、秘密鍵の機密を守り続ける事に完全に依存する。秘密鍵は利用者のコンピュータ上に格納し、(例えば)そのコンピュータのパスワードで保護できるが、これには以下の2つの欠点がある。

- 利用者は当該コンピュータ上の文書しか署名できない。そして
- 秘密鍵のセキュリティは、多くのPCとオペレーティングシステムで信頼できない事で悪名高い、そのコンピュータのセキュリティに完全に依存する。

より安全な代案はICカードに秘密鍵を格納する事である。多くのICカードは耐タンパー性を持つように意図的に設計される(しかしながら、かなり多くの設計は、Ross Andersonと彼の生徒達に破られた)。典型的な実装では、文書から計算されたハッシュ値がICカードに送られる。ICカードのCPUが格納されている利用者の秘密鍵を用いてそのハッシュ値を暗号化し、そしてそれを返す。通常は、利用者は暗証番号やPINコードを入力する事で(従って2要素認証を準備して)自分のICカードを活性化しなければならない。秘密鍵がICカードの外部へ決して出ないように賢明に準備される(しかし必ずしも行われるとは限らない)事に注意されたい。もしICカードが盗まれても、その泥棒はデジタル署名を生成するためにまだPINコードを必要とするようになる。これはデジタル署名のセキュリティを暗証番号システムのセキュリティに格下げするが、しかしそれでもなお多くのPCより安全である。しかしながら緩和する要因はその秘密鍵である。もし秘密鍵をICカード上で生成しICカードへ格納した場合、通常、秘密鍵を複製する事は容易ではないと見なされ、従ってしばしば厳密に一つだけ存在する事が当然と考えられる。従って、ICカードの紛失は所有者に見つけられる可能性がある。そして対応する証明書は直ちに失効しても良い(実際にはすべきである)。ソフトウェアだけで保護された秘密鍵は複製する事が容易である恐れが有り、そしてそのような危殆化を発見する事は遥かに困難である。

### 個別のキーボードを備えたICカード読取り装置の使用

ICカードの活性化のためにPINコードを入力する事は、一般的にテンキーパッドを必要とする。幾つかのカード読取り装置はそれ自身のテンキーパッドがある。これは、PCに内蔵されたカード読取り装置を使用し、そしてそのコンピュータのキーボードを使用してPINを入力するより安全である。(所有者/オペレータの意思で、あるいは意思ではなく -- 例えばウイルスなどによって)キーロガーが動いているコンピュータではPINコードが漏洩する恐れがある。専門のカード読取り装置はソフトウェアやハードウェアの改竄に対して(鉄壁ではないが)脆弱ではない。またもちろん、そのような全ての装置に対する盗聴攻撃は可能である。

### その他のICカード設計

今までのところ小さなセキュリティの証であるにも関わらず、ICカードの設計は活発な分野であり、それら特定の問題を回避する事を目的としたICカードの体系がある。

### 信頼されたアプリケーションだけを用いたデジタル署名の使用

デジタル署名が書面による署名と主に違う事の一つは、利用者が何に署名するか本人が"見ることができない"という事である。利用者のアプリケーションは秘密鍵を用いてデジタル署名アルゴリズムによって暗号化されるためにハッシュコードを提示する。利用者PCの制御を盗んだ攻撃者は、利用者のアプリケーションを外部の"代用品"とすげ換える可能性が有り、それは事実上、利用者自身のコミュニケーションを攻撃者のコミュニケーションへすげ換える事である。従って、悪意のあるアプリケーションは、利用者の原本を画面上に表示するが、攻撃者自身の(恐らく有益でない)文書を署名アプリケーションに提示する事で、無意識の利用者を任意の文書に署名するよう騙す事ができる。

この筋書きから防御するため、認証システムは利用者アプリケーション(ワードプロセッサ、メールソフトなど)と署名アプリケーション間に設定できる。その概念は利用者アプリケーションと署名アプリケーション両方がお互いの完全性を検証するための幾つかの手段を与える事である(例えば、署名アプリケーションは全ての要求がデジタル署名されたバイナリから行われる事を必要としても良い)。

## 幾つかのデジタル署名アルゴリズム

- RSA
- DSA
- ECDSA
- ElGamal署名
- 否認不可署名(Undeniable signature)
- SHA
- EdDSA
- RSA-SHA
- ECDSA-SHA
- Rabin signature algorithm
- Pointcheval-Stern signature algorithm
- Schnorr signature
- Aggregate signature - 集約に対応したデジタル署名: n人の別々の利用者からn個の別々のメッセージでn個の署名が与えられた時、それら全ての署名を一つの短い書名に集約する事が可能。この単一の署名はn人の利用者がn個の元のメッセージへ確かに署名したと検証者に納得させるであろう。

## 利用の現状—法律と実務

暗号理論あるいは法の規定に関わらず、デジタル署名が無意味にならないための重要な要件を、デジタル署名方式は全てそれぞれ持っている。

- 第一に、質の良いアルゴリズム。幾つかの公開鍵アルゴリズムは、それらに対する実行可能な攻撃が発見されており、安全でなくなる事が知られている。
- 第二に、質の良い実装。優れたアルゴリズム(またはプロトコル)も誤った実装で役に立たなくなるであろう。
- 第三に、秘密鍵は本当に機密が守られたままでなければならない。もし秘密鍵が誰か第三者に知られる事になれば、その者はどこから見ても"完璧な"デジタル署名を作り出せる。
- 第四に、例えば、ボブに属するように要求された公開鍵が実際にボブが所有するように、また逆の場合も同様に、公開鍵の配布は行われなければならない。これは公開鍵基盤を用いて普通に行われる。そして公開鍵$\leftrightarrow$利用者の組み合わせは(認証局と呼ばれる)PKI業者によって証明される。誰でも(一般的には暗号的に保護された身元証明書で具体化される)証明を要求できる「開かれた」PKIでは、誤った証明の可能性は些細な問題ではない。商用のPKI業者は幾つかの公知の問題に悩まされた。そのような過ちは不当に署名された(従って不正に帰属された)文書に導く恐れがある。「閉じた」PKIシステムは更に費用が掛かるが、このように容易に破壊される事はない。
- 第五に、利用者(および彼らのソフトウェア)は署名プロトコルを適切に実行しなければならない。

これら全ての条件が満たされる場合に限り、デジタル署名は実際に、そのメッセージを送信した者を示す証拠になり、またそれ故に、メッセージの内容に対する送信者の同意を示す証拠になる。そのような事の幾つかはこの実状を反映していないにも係わらず、法律の制定は既存の工学の可能性のこの現実を変えられない。

PKIの運営による利益を期待する企業や、または古い問題へ新しい解決策を提唱する技術的先駆者から再三要請されている議会は、デジタル署名を認可、支持、促進、または許可し、そしてそれらの法的影響に備える(または法的影響を限定する)、法律および/また条例を多くの国や自治体で成立した。アメリカ合衆国では最初はユタ州で、間もなくマサチューセッツ州とカリフォルニア州が続いたようである。その他の国も同様に法案を通したりその地域の規則を発行し、また国連にはしばらく活発なモデル法律のプロジェクトが有った(国際連合国際商取引法委員会 (UNCITRAL)の2001年の電子署名に関するUNCITRALモデル法)。場所によって異なるこれらの法律の制定(あるいは提案)は、典型的には、根本的な暗号技術の状態と(楽観的または悲観的に)食い違う予想を具体化し、暗号知識に詳しくないほぼ全ての潜在的な利用者や仕様策定者を混乱させる正味の影響が有った。デジタル署名のための技術標準の選定は多くの法律制定に遅れを取り、提供しようとしている相互運用性、アルゴリズムの選択、鍵長などを統合した技術の立場を多かれ少なかれ遅らせた。

### 署名と暗号化に別々の鍵ペアを使用する事

幾つかの国では、デジタル署名は伝統的なペンと紙の署名にやや似ている地位がある。概して、それらの条件はデジタル署名される物がその文書の署名者をその条件の中に法的に縛りつけるという事を意味する。このような理由により、暗号化と署名のために別々の鍵ペアを用いる事が最適であると考えられる事がよくある。暗号化鍵ペアを用いて(例えば住宅購入について)暗号化された会話ができるが、その人が発した全てのメッセージに法的な署名がされる訳ではない。双方の者が同意に達する場合に限り、彼らの署名鍵で契約書に署名を行い、そしてその場合に限り彼らは特定の文書の条件によって法的に縛られる。署名の後で、その文書は暗号化されたリンクの上で送信できる。