デジタル署名（デジタルしょめい）とは、書面上の手書き署名のセキュリティ特性を模倣するために用いられる公開鍵暗号技術の一種である。 概要 デジタル署名は通常3つのアルゴリズムからなる。一つは"鍵ペア"を生成する鍵生成アルゴリズム。もう一つは、利用者の秘密鍵を用いて署名を生成するアルゴリズム、それと利用者の公開鍵を用いて署名を検証するアルゴリズムである。署名生成処理で作り出されたデータも"デジタル署名"と呼ぶ。
デジタル署名は"メッセージ"の認証機能を提供する。メッセージは、電子メール、契約書、あるいはより複雑な暗号プロトコルで送受されるデータでも何でも良い。
認証局が発行する公開鍵証明書では、認証局の社会的な信頼性を担保に、利用者の公開鍵と利用者の結びつきを保証している。その際、証明書が（公開鍵使用者が信頼する）認証局によって発行されたものであることを証明するために、デジタル署名が使われている。
デジタル署名はしばしば電子署名（署名の意図を伝える任意の電子データを指す上位語）を実装する為に用いられるUS ESIGN Act of 2000が、全ての電子署名がデジタル署名を用いる訳ではない。
日本日本国の電子署名及び認証業務に関する法律、アメリカおよび欧州連合を含めて幾つかの国The University of VirginiaState of WI National Archives of Australiaでは、電子署名は法律上の意義がある。しかしながら、電子署名に関する法律は、その法律上の重要性をやや曖昧にしておき、暗号によるデジタル署名に関して法を適用できるか否かについて、必ずしも明確にしない。
定義
デジタル署名は平均多項式時間確率アルゴリズムの三つ組み(G,S,V)で定義できる。 鍵生成アルゴリズムG - 1kを入力すると公開鍵・秘密鍵ペア(pk,sk)を出力する。ただしここでkはセキュリティ・パラメータ。pkは公開する検証鍵、そしてskは秘密にする署名鍵ともいわれる。 署名生成アルゴリズムS - 平文mと秘密鍵skの組(m,sk)を入力すると、平文mに対する電子署名文sを出力する。 署名検証アルゴリズムV - 平文m、署名文s、公開鍵pkの組(m,s,pk)を入力すると文字列ACCEPT（検証通過、Validである）もしくはREJECT（検証非通化、invalidである）を出力する。その平文の真正性の主張を承認または拒否を出力する。
主に2つの特性が必要とされる。
第一に、正当な署名鍵で生成された署名は、対応する検証鍵によって常に承認されること。つまり、署名鍵skと検証鍵pkが対応する鍵ペアである場合、任意の平文mについて、V (m, pk, S (m, sk))は承認が出力される必要がある。
第二に、いかなる攻撃者であっても（pkを知っているだけでは）有効な署名を生成する事は困難であることである。
要件 デジタル署名(G,S,V)は次の要件を満たさねばならない。ただしここで「正当な署名者」というのは、検証に用いた公開鍵に対応する秘密鍵の持ち主を指す。
Correctness：正当な署名者が作った署名文は、検証を通過する。 Security： 検証を通過するのは正当な署名者が作った署名文に限る。
正当性の厳密な定義 任意の平文mに対し、
はoverwhelming。
安全性の厳密な定義 デジタル署名の安全性(Security)の要件をより厳密に定義する。 「検証を通過するのは正当な署名者が作った署名文に限る」というのが、いかなる条件下でいかなる目標を達する事を指すのかによってデジタル署名方式の安全性の定義は数種類に存在するが、単に「安全」といった場合選択文書攻撃に対する存在的偽造不能性(Existencial Unforgeability against Chosen Message Attack, EU-CMAと略す）を指す事が普通なので、ここではこの定義を紹介する。
準備
をデジタル署名方式とし、kをセキュリティ・パラメータとする。 Aをデジタル署名方式に対する攻撃者とする。 攻撃者Aを用いて、次のような実験(experiment ゲーム(game)とも言う)を行なう。
まず1kを入力として鍵生成アルゴリズムを走らせ、公開鍵・秘密鍵ペア(pk,sk)を作る。そしてpkとkを攻撃者Aに渡す。
攻撃者Aは実験の最中、署名オラクルO(sk,・)に任意の回数アクセスする事ができる。 署名オラクルとは、攻撃者Aから平文mを送信されると、秘密鍵skを使ってmに対する署名文s=Ssk(m)を作成し、sをAに送信するオラクルの事である。
攻撃者Aの目標は、平文mと署名文sとの組(m,s)で検証を通り、しかも署名オラクルOにmを送信していないものを出力する事。 そのような(m,s)を作成できればAの勝ち、そうでなければAの負けである。
以上の実験をより形式的に書くと、以下の通り。
Experiment
If(がにを聞いた事がある) Return LOSE If() Return LOSE Return WIN
実験でAが勝つ確率をと書く事にする。(注：この記号は比較的良く使われるものの、必ずしも皆の合意がとれた記号ではないので、使用するときには一言説明が必要である)。
ただしここで確率はG,S,V,Aの内部乱数をランダムに選んだときのもの。
定義
をデジタル署名方式とする。 任意の平均多項式時間確率アルゴリズムAに対し、 がkに関しnegligibleなとき、 デジタル署名方式は選択文書攻撃に対し存在的偽造不能であるという。
代表的なデジタル署名方式 RSA署名、ElGamal署名、DSA署名、Schnorr署名、Cramer-Shoup署名、楕円ElGamal署名、楕円曲線DSA署名、楕円Schnorr署名など様々な署名方式が知られている。
RSA署名、ElGamal署名はそれぞれ素因数分解問題、素体の乗法群上の離散対数問題を基にした署名方式である。この二つの署名方式は、暗号理論の研究の初期に提案された署名方式であるので特に有名である。しかし、RSA署名は（教科書的なRSA署名は、存在的偽造可能であることが自明なので）CMA-EUF安全ではないし、ElGamal署名は（CMA-EUF安全であろうと予想されているものの）CMA-EUF安全であるかどうか分かっていない。DSA署名はElGamal署名の変形版であって米国NISTの標準暗号になっているが、安全性については同様である。
Schnorr署名は、素体の乗法群上の離散対数問題の困難性とランダムオラクル仮定のもとでCMA-EUF安全であることが示されている署名方式であり、ElGamal署名と同程度の効率をもつ。 ランダムオラクルは、暗号理論の研究でよく使用される概念であって、ハッシュ関数が「十分ランダムに振る舞う」ということを理想化した概念である。ランダムオラクル仮定は、「ランダムオラクルが存在する」という仮定であるが、ランダムオラクルはあくまで現実を理想化したものであり、現実的には存在し得ない。
Cramer-Shoup署名は、ランダムオラクルのような理想化された仮定を用いないで安全性が示せる（もので、かつ効率的な）初めての署名方式であり、強RSA仮定のもとでCMA-EUF安全であることが示されていて、RSA暗号の数倍程度の計算量で署名作成・検証が行なえる。
ElGamal署名、DSA署名、Schnorr署名のような素体の乗法群上の離散対数問題を基にした署名方式は、素体の乗法群の代わりに楕円曲線群を用いて計算量を少なくし、しかも署名長を短くすることができる。楕円曲線群を用いたElGamal署名、Schnorr署名を、それぞれ楕円ElGamal署名、楕円曲線DSA署名、楕円Schnorr署名と呼ぶ。
歴史 1976年、著名な論文である「New Directions in Cryptography」において、ホイットフィールド・ディフィー（Whitfield Diffie）およびマーティン・ヘルマン（Martin Hellman）はデジタル署名という理論体系が存在するという推測とその概念について初めて著した。彼らはそのようなスキームが落とし戸付き一方向性置換である関数に基づいて存在すると推測しただけであった。"New Directions in Cryptography", IEEE Transactions on Information Theory, IT-22(6):644-654, Nov. 1976."Signature Schemes and Applications to Cryptographic Protocol Design", Anna Lysyanskaya, PhD thesis, MIT, 2002.
程なく、ロナルド・リベスト（Ronald Rivest）、アディ・シャミア（Adi Shamir）、およびレオナルド・エーデルマン（Len Adleman）は、基本的なデジタル署名に用いる事ができるRSAアルゴリズムを開発した"A Method For Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, 21(2): 120-126, Feb. 1978.（これはただ単に概念実証としての役目だけを果たす事に注意されたい。単純なRSA署名は安全ではない例えば、任意の整数rはm=reに「署名」し、m1、m2に対する2つの有効な署名s1、s2の積s1s2は、積m1m2の有効な署名となる。）。デジタル署名を提供し広く市販された最初のソフトウェア・パッケージは、RSAアルゴリズムを用いて1989年に発売されたLotus Notes 1.0である。
基本的なRSA署名は以下のように算出される。RSA署名鍵を生成するために、2つの大きな素数の積である係数Nと一緒に、φがオイラーのφ関数である時e d = 1 mod φ(N)を満たす整数eおよびdを含むRSA鍵ペアを一つ単に生成する。署名者の公開鍵はNとeから成り、署名者の秘密鍵はdを含む。
メッセージmに署名するため、署名者はσ=md mod Nを計算する。検証するために、受信者はσe = m mod Nを照合する。
前述のように、この基本的な仕組みはあまり安全ではない。攻撃を防ぐため、まず最初にメッセージmに暗号ハッシュ関数を適用し、それからその結果に前述のRSAアルゴリズムを適用する事ができる。このやり方は所謂ランダム・オラクル・モデルにおいて安全を証明できる。
その他のデジタル署名方式は、RSAに次いですぐ、最初にランポート署名（Lamport signature）"Constructing digital signatures from a one-way function.", Leslie Lamport, Technical Report CSL-98, SRI International, Oct. 1979.、マークル署名（Merkle signature、別名" マークル木"（Merkle tree）あるいは単に" ハッシュ木"（Hash tree））"A certified digital signature", Ralph Merkle, In Gilles Brassard, ed., Advances in Cryptology -- CRYPTO '89, vol. 435 of Lecture Notes in Computer Science, pp. 218-238, Spring Verlag, 1990.、そしてラビン署名（Rabin signature）"Digitalized signatures as intractable as factorization." Michael O. Rabin, Technical Report MIT/LCS/TR-212, MIT Laboratory for Computer Science, Jan. 1979が開発された。
1988年、シャフィ・ゴールドワッサー、シルビオ・ミカリ、ロナルド・リベストはデジタル署名方式のセキュリティー要件を最初に厳格に定義したS. Goldwasser, S. Micali, and R. Rivest. "A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks". SIAM J. Computing 17(2): 281-308 (1988). Conference version published in 1984.。彼らは攻撃モデルの段階を次のように示した。 唯鍵攻撃（Key-Only Attack）では、公開されている検証鍵だけを前提とした攻撃が行われる。 既知文書攻撃（Known Message Attack）では、既知の様々な文書の有効な署名を前提とした攻撃が行われるが、攻撃者に文書は選択されない。 選択文書攻撃（Chosen Message Attack）では、攻撃者は最初に選択した任意の文書への署名を入手し、その署名を前提とした攻撃が行われる。
彼らは攻撃結果の段階も次のように示した。 全面的解読（total break）とは、署名鍵を再生されるという結果をもたらすものである。 普遍的偽造（universal forgery）攻撃とは、任意の文書の署名も偽造できる署名アルゴリズムが発見されるという結果をもたらすものである。 選択的偽造（selective forgery）攻撃とは、敵に選択された文書の署名が偽造されるという結果をもたらすものである。 存在的偽造（existential forgery）とは、ただ単に敵に知られていない何らかの有効な文書/署名の対が発見されるだけという結果をもたらすものである。
また彼らは、選択文書攻撃でさえ対抗し存在的偽造でさえ防ぐ事が初めて立証できる、GMR署名方式も提示した。"A digital signature scheme secure against adaptive chosen-message attacks.", Shafi Goldwasser, Silvio Micali, and Ronald Rivest. SIAM Journal on Computing, 17(2):281-308, Apr. 1988.
殆どの初期の署名方式は類似していた。それらは、RSA関数などの落とし戸置換（trapdoor permutation）の使用か、あるいはラビン署名方式の場合は合成数Nを法とする二乗の計算を必要とする。落とし戸置換族は、パラメータで指定される置換の集まりであり、その置換の順方向への計算は容易だが、逆方向への計算は困難である。しかしながら、全てのパラメータについて逆方向の計算を容易にする"落とし戸"が存在する。パラメータを公開鍵、落とし戸を秘密鍵とし、また暗号化は順方向へ復号は逆方向へ置換を計算する事に対応させれば、落とし戸置換は公開鍵暗号システムとしてみなす事ができる。また、落とし戸置換はデジタル署名方式とみなす事もでき、秘密鍵を用いた逆方向の計算を署名と考え、また順方向の計算は署名を検証するためにされると考えればよい。署名は復号に相当し検証は暗号化に相当するという対応により、デジタル署名は公開鍵暗号方式を踏まえて説明される事が多いが、これはデジタル署名を算出する唯一の方法ではない。
直接使われると、この種類の署名方式は存在的偽造への唯鍵攻撃に対して脆弱である。偽造文書を作り出すため、攻撃者は任意の署名σを取り出し、そしてその署名に対応する文書mを見つけ出すために検証処理を使用する。"Modern Cryptography: Theory & Practice", Wenbo Mao, Prentice Hall Professional Technical Reference, New Jersey, 2004, pg. 308. しかしながら、実際にはこの種類の署名が直接使われる事は無い。もっと正確に言えば、署名される文書は、最初にハッシュ化されて短い要約（メッセージ・ダイジェスト）となり、要約に対して署名処理がなされる。その結果、この偽造攻撃はσに対応するハッシュ関数の出力を生成するだけである。ハッシュ関数の出力は元の文書の有用性に繋がる物ではなく、攻撃を招く事にはならない。ランダム・オラクル・モデルでは、署名のこのhash-and-decrypt形式は、選択文書攻撃でさえ存在的偽造は不可能である。
文書全体の代わりにそのようなハッシュ（またはメッセージ・ダイジェスト）に署名する幾つかの理由がある。 効率性: 一般的にハッシュを計算する事は実際に署名する事より遥かに速いので、署名は非常に短くなり従って時間を節約するようになる。 互換性: 文書は通常ビット列であるが、ある署名方式は他の定義域で動作する（例えばRSAの場合、合成数Nを法とする整数）。ハッシュ関数は任意の入力を適切な形式へ変換する事に使う事ができる。 完全性: ハッシュ関数が無い場合は、"署名すべき"文章は、署名方式が直接処理できるように小さい単位に分割されなければならないであろう。しかしながら、署名された部分の受信者は、全ての部分が適切な順番で存在しているかどうか、認識する事ができない。
デジタル署名の利点 以下はデジタル署名をコミュニケーションに適用する最も一般的な理由である。
認証 文書を送信する実体に関する情報がしばしばその文書に含まれる事があるが、その情報は不正確である可能性がある。デジタル署名は文書の発信元を認証する事に使う事ができる。デジタル署名に用いる秘密鍵の所有権が特定の利用者へ結び付けられる時は、有効な署名は文書がその利用者から送信されたという事を示す。送信者の真正性について高い信頼度の重要性は、金融に関する内容の時に特に明白である。例えば、ある銀行の支店がある口座の残高について変更を要求する指示を本店へ送る場面を仮定する。もしそのようなメッセージが権限が与えられた発信元から本当に送信されたという事を本店が確信していなければ、そのような要求に応える事は致命的な過ちになる事になる。
完全性 多くの筋書きでは、文書の送信者と受信者は文書が転送中に改竄された事が無いという確信を必要とするであろう。暗号は文書の内容を隠蔽するが、それを理解せずに暗号化された文書には改変の可能性がある（頑強性がある物として知られている幾つかの暗号アルゴリズムはこれを防止するが、その他は防止しない）。しかしながら、もし文書がデジタル署名されていたならば、文書のどんな改変でも署名が無効になるであろう。更に、有効な署名がなされた新しい文書を生成するために、文書とその署名を改変する効果的な方法はない。なぜならば、これはまだ多くのハッシュ関数で計算的に実行不可能であると見なされている（衝突耐性参照）。
デジタル署名の欠点 その実用性にもかかわらず、デジタル署名は私たちが解決を願う全ての問題を単独で解決する訳ではない。
リプレイ攻撃 デジタル署名スキーム自体は、有効な署名済みメッセージが記録され、リプレイ攻撃で悪意を持って再利用されることを防ぐことはできない。 例えば、支店が署名されたメッセージで銀行振込を一度だけ正当に要求することがある。 銀行がメッセージ内でどの取引が既に行われたかを検出するための取引IDのシステムを使用していない場合、誰かが同じ署名済みメッセージを何度も不正に再利用して口座を空にすることができてしまう。
署名の一意性と展性 署名自体は、それが署名するメッセージを一意に識別するために使用することはできない。一部の署名スキームでは、すべてのメッセージが同じ署名者からの多数の有効な署名を持つ可能性があり、秘密鍵を知らなくても、ある有効な署名を別の署名に変換することが容易な場合がある。
デジタル署名と信頼できるタイムスタンプの関連性 本来、デジタル署名アルゴリズムとプロトコルは構成する文書が署名された日付と時刻に関する確実性を提供しない。署名者は署名にタイムスタンプを載せているかも載せていないかも知れない。また文書自体に日付が記載されているかも知れない。しかしその後に読む人は、例えば署名者が署名の日時を実際より前にしていないと確信できない。デジタル署名に加えて信頼できるタイムスタンプを使用する事で、その様な悪用を実行不可能にする事ができる。
否認防止
暗号の世界では、否認という単語はメッセージに対する責任を放棄するあらゆる行為を指す(司法の世界における否認とは意味合いが大きく異なる)。メッセージの受信者は、その署名者と完全性に関する主張を強固にするために、第三者（例えば裁判所）へ署名されたメッセージを示す事ができる。そのため受信者は、後になって容易に否認されないようにするため、送信者の署名を強く主張する事ができる。しかしながら、利用者が秘密鍵の秘匿性を失う事は、その鍵を用いた（そして表面上その利用者'から'の）全てのデジタル署名は疑わしい、という事を意味するであろう。それでもなお、利用者の署名鍵を拒否せずに、利用者は署名されたメッセージを否認できない。それは信頼できるタイムスタンプが無いという事実によって悪化する。したがって、（鍵が危殆化した後に）新しく作られた文書は古いものやそれ以上に複雑な署名鍵の失効から切り離す事はできない。公開鍵に関連する利用者鍵を証明し署名を否認する事ができないように、通常は認証局はリポジトリと呼ばれる公開鍵の公開データベースを保持する。期限切れの証明書は普通はそのデータベースから削除される。データの否認防止サービスが提供される場合、ある期間に古い証明書を保持する事は、認証局のセキュリティポリシーと責任の問題である。
更なるセキュリティ対策 ICカードへの秘密鍵の格納 全ての公開鍵暗号システムは、秘密鍵の機密を守り続ける事に完全に依存する。秘密鍵は利用者のコンピュータ上に格納し、（例えば）そのコンピュータのパスワードで保護できるが、これには以下の2つの欠点がある。 利用者は当該コンピュータ上の文書しか署名できない。 秘密鍵のセキュリティは、多くのPCとオペレーティングシステムで信頼できない事で悪名高い、そのコンピュータのセキュリティに完全に依存する。
より安全な代案はICカードに秘密鍵を格納する事である。多くのICカードはを持つように意図的に設計される（しかしながら、かなり多くの設計は、Ross Andersonと彼の生徒達に破られた）。典型的な実装では、文書から計算されたハッシュ値がICカードに送られる。ICカードのCPUが格納されている利用者の秘密鍵を用いてそのハッシュ値を暗号化し、そしてそれを返す。通常は、利用者は暗証番号やPINコードを入力する事で（従って2要素認証を準備して）自分のICカードを活性化訳注: 鍵を使える状態にする事しなければならない。秘密鍵がICカードの外部へ決して出ないように賢明に準備される（しかし必ずしも行われるとは限らない）事に注意されたい。もしICカードが盗まれても、その泥棒はデジタル署名を生成するためにまだPINコードを必要とするようになる。これはデジタル署名のセキュリティを暗証番号システムのセキュリティに格下げするが、しかしそれでもなお多くのPCより安全である。しかしながら緩和訳注: 前文の「reduces the security of the scheme to that of the PIN system」の事か?する要因はその秘密鍵である。もし秘密鍵をICカード上で生成しICカードへ格納した場合、通常、秘密鍵を複製する事は容易ではないと見なされ、従ってしばしば厳密に一つだけ存在する事が当然と考えられる。従って、ICカードの紛失は所有者に見つけられる可能性がある訳注: 物理的媒体であるICカードは複製する事が困難であるため、後述の「ソフトウェアだけで保護された秘密鍵」と異なり、秘密鍵が漏洩した事が物理的媒体の紛失という目に見える形で発見されるという事を意味していると思われる。そして対応する証明書は直ちに失効しても良い（実際にはすべきである）。ソフトウェアだけで保護された秘密鍵は複製する事が容易である恐れが有り、そしてそのような危殆化を発見する事は遥かに困難である。
個別のキーボードを備えたICカード読取り装置の使用 ICカードの活性化のためにPINコードを入力する事は、一般的にテンキーパッドを必要とする。幾つかのカード読取り装置はそれ自身のテンキーパッドがある。これは、PCに内蔵されたカード読取り装置を使用し、そしてそのコンピュータのキーボードを使用してPINを入力するより安全である。（所有者/オペレータの意思で、あるいは意思ではなく -- 例えばウイルスなどによって）キーロガーが動いているコンピュータではPINコードが漏洩する恐れがある。専門のカード読取り装置はソフトウェアやハードウェアの改竄に対して（鉄壁ではないが）脆弱ではなく、多くの場合EAL3の認証を受けている。またもちろん、そのような全ての装置に対する盗聴攻撃は可能である。
その他のICカード設計 今までのところ小さなセキュリティの証であるにも関わらず、ICカードの設計は活発な分野であり、それら特定の問題を回避する事を目的としたICカードの体系がある。
信頼されたアプリケーションだけを用いたデジタル署名の使用 デジタル署名が書面による署名と主に違う事の一つは、利用者が何に署名するか本人が"見ることができない"という事である。利用者のアプリケーションは秘密鍵を用いてデジタル署名アルゴリズムによって暗号化されるためにハッシュコードを提示する。利用者PCの制御を盗んだ攻撃者は、利用者のアプリケーションを外部の"代用品"とすげ換える可能性が有り、それは事実上、利用者自身のコミュニケーションを攻撃者のコミュニケーションへすげ換える事である。従って、悪意のあるアプリケーションは、利用者の原本を画面上に表示するが、攻撃者自身の（恐らく有益でない）文書を署名アプリケーションに提示する事で、無意識の利用者を任意の文書に署名するよう騙す事ができる。
この筋書きから防御するために、利用者アプリケーション（ワードプロセッサ、メールソフトなど）と署名アプリケーション間に、認証システムを設定できる。その概念は利用者アプリケーションと署名アプリケーション両方がお互いの完全性を検証するための幾つかの手段を与える事である（例えば、署名アプリケーションは全ての要求がデジタル署名されたバイナリ訳注: 実行形式ファイルから行われる事を必要としても良い）。
ネットワーク接続されたハードウェアセキュリティモジュールの使用 クラウドベースのデジタル署名サービスとローカルで提供されるサービスの主な違いの1つはリスクである。政府、金融、医療機関、決済処理業者など、多くのリスク回避型の企業は、署名が検証され、安全であることを保証するために、FIPS 140-2レベル3やFIPS 201認証などのより安全な基準を要求する。
WYSIWYS（What You See Is What You Sign）