「電子署名」の版間の差分
m +link: デジタル署名 |
m 電子署名（ 2008年3月25日 (火) 12:17）から定義の項をコピー；いったん保存 |
||
| 52行目: | 52行目: | ||
電子署名法は、電子文書はその内容について本人による電子署名が行われているときは真正に成立したものと推定すると規定している（3条）が、これは民事訴訟法228条4項の電子文書版ということができる。 |
電子署名法は、電子文書はその内容について本人による電子署名が行われているときは真正に成立したものと推定すると規定している（3条）が、これは民事訴訟法228条4項の電子文書版ということができる。 |
||
==電子署名方式の定義== |
|||
'''(電子)署名方式'''((でんし)しょめいほうしき、(digital) signature scheme)は平均多項式時間確率アルゴリズムの三つ組み(G,S,V)である。 |
|||
# Gは'''鍵生成アルゴリズム'''(かぎせいせいあるごりずむ、key generation algorithm)と呼ばれ、1<sup>k</sup>を入力されると'''公開鍵'''・'''秘密鍵'''ペア(pk,sk)を出力する。ただしここでkは'''セキュリティ・パラメータ'''。 |
|||
# Sは'''署名アルゴリズム'''(しょめいあるごりずむ、signing algorithm)と呼ばれ、''''平文'''mと秘密鍵skの組(m,sk)を入力されると、平文mに対する'''(電子)署名文'''((でんし)しょめいぶん, (digital) signature)sを出力する。 |
|||
# Vは'''検証アルゴリズム'''(けんしょうあるごりずむ、verification algorithm)と呼ばれ、平文m、署名文s、公開鍵pkの組(m,s,pk)を入力されると文字列ACCEPTもしくはREJECTを出力する。V<sub>pk</sub>(m,s)=ACCEPTとなるとき、署名文sは、（公開鍵pk,および平文mに関し）'''検証を通る'''（accept,「'''valid'''である」ともいう）といい、そうでないとき'''検証を通らない'''(reject, 「'''invalid'''である」ともいう)。 |
|||
==要件== |
|||
電子署名(G,S,V)は次の要件を満たさねばならない：<br> |
|||
'''Correctness'''：正当な署名者が作った署名文は、検証を通過する。<br> |
|||
'''Security'''： 検証を通過するのは正当な署名者が作った署名文に限る。 |
|||
ただしここで「正当な署名者」というのは、検証に用いた公開鍵に対応する秘密鍵の持ち主を指す。 |
|||
==要件の厳密な定義== |
|||
<!--===Correctnessの厳密な定義===--> |
|||
===正当性の厳密な定義=== |
|||
任意の平文mに対し、<br> |
|||
<math>\mathrm{Pr}(V_{\mathbf{pk}}(m,s)=\mathbf{ACCEPT}|(\mathbf{pk},\mathbf{sk})\gets |
|||
G(1^k), s\gets S_{\mathbf{sk}}(m))</math>は[[overwhelming]]。<br> |
|||
<!--===Securityの厳密な定義===--> |
|||
===安全性の厳密な定義=== |
|||
電子署名の安全性(Security)の要件をより厳密に定義する。 |
|||
「検証を通過するのは正当な署名者が作った署名文に限る」というのが、いかなる条件下でいかなる目標を達する事を指すのかによって電子署名方式の安全性の定義は数種類に存在するが、単に「安全」といった場合'''選択文書攻撃に対する存在的偽造不能性'''(Existencial Unforgeability against Chosen Message Attack, EU-CMAと略す）を指す事が普通なので、ここではこの定義を紹介する。 |
|||
'''準備'''<br> |
|||
<math>\Sigma=(G,S,V)</math>を電子署名方式とし、kをセキュリティ・パラメータとする。 |
|||
Aを電子署名方式<math>\Sigma</math>に対する攻撃者とする。 |
|||
攻撃者Aを用いて、次のような'''実験'''(experiment '''ゲーム'''(game)とも言う)を行なう。 |
|||
<br> |
|||
まず1<sup>k</sup>を入力として鍵生成アルゴリズムを走らせ、公開鍵・秘密鍵ペア(pk,sk)を作る。そしてpkとkを攻撃者Aに渡す。 |
|||
<br> |
|||
攻撃者Aは実験の最中、'''署名オラクル'''O(sk,・)に任意の回数アクセスする事ができる。 |
|||
署名オラクルとは、攻撃者Aから平文mを送信されると、秘密鍵skを使ってmに対する署名文s=S<sub>sk</sub>(m)を作成し、sをAに送信するオラクルの事である。 |
|||
<br> |
|||
攻撃者Aの目標は、平文mと署名文sとの組(m,s)で検証を通り、しかも署名オラクルOにmを送信していないものを出力する事。 |
|||
そのような(m,s)を作成できればAの勝ち、そうでなければAの負けである。 |
|||
<br> |
|||
以上の実験をより形式的に書くと、以下の通り。 |
|||
<br> |
|||
<br> |
|||
'''Experiment''' |
|||
:<math>(\mathbf{pk},\mathbf{sk})\gets G(1^k)</math> |
|||
:<math>(m,s) \gets A^{O(\mathrm{sk},\cdot)}(1^k,\mathbf{pk})</math> |
|||
:If(<math>A{}</math>が<math>O(\mathbf{sk},\cdot)</math>に<math>m{}</math>を聞いた事がある) Return ''LOSE'' |
|||
:If(<math>V_{\mathbf{pk}}(m,s)=\mathbf{Reject}</math>) Return ''LOSE'' |
|||
:Return ''WIN'' |
|||
<br> |
|||
実験でAが勝つ確率を<math>\mathbf{Succ}_{\Sigma}^k(A)</math>と書く事にする。(注：この記号は比較的良く使われるものの、必ずしも皆の合意がとれた記号ではないので、使用するときには一言説明が必要である)。 |
|||
<br> |
|||
ただしここで確率はG,S,V,Aの内部乱数をランダムに選んだときのもの。 |
|||
<br> |
|||
'''定義'''<br> |
|||
<math>\Sigma=(G,S,V)</math>を電子署名方式とする。 |
|||
任意の平均多項式時間確率アルゴリズムAに対し、 |
|||
<math>\mathbf{Succ}_{\Sigma}^k(A)</math>がkに関し[[negligible]]なとき、 |
|||
電子署名方式<math>\Sigma</math>は'''選択文書攻撃に対し存在的偽造不能である'''という。 |
|||
==代表的な電子署名方式== |
|||
[[RSA暗号#RSA署名|RSA署名]]、[[ElGamal署名]]、[[DSA]]署名、[[Schnorr署名]]、[[Cramer-Shoup署名]]、[[楕円ElGamal署名]]、[[楕円Schnorr署名]]等様々な署名方式が知られている。 |
|||
RSA署名、ElGamal署名はそれぞれ[[RSA問題]]、[[素体]]の[[乗法群]]上の[[離散対数問題]]を基にした署名方式である。この二つの署名方式は暗号理論の研究の初期に提案された署名方式である為特に有名であるが、RSA署名は、（教科書的なRSA署名は、存在的偽造可能であることが自明なので）CMA-EUF安全ではないし、ElGamal署名は、（CMA-EUF安全であろうと予想されているものの)CMA-EUF安全であるかどうか分かっていない。DSAはElGamal署名の変形版で米国NISTの標準暗号になっているが、安全性については同様である。 |
|||
Schnorr署名は素体の乗法群上の離散対数問題の困難性と[[ランダムオラクル]]仮定のもとCMA-EUF安全である事が示されている署名方式で、ElGamal署名と同程度の効率を持つ。<br> |
|||
ランダムオラクルは暗号理論の研究でよく使用される概念で、ハッシュ関数が「十分ランダムに振舞う」という事を理想化した概念である。ランダムオラクル仮定は「ランダムオラクルが存在する」という仮定であるが、ランダムオラクルはあくまで現実を理想化したものであり現実的には存在し得ないものである。 |
|||
Cramer-Shoup署名はランダムオラクルのような理想化された仮定を用いないで安全性が示せる(もので、かつ効率的な)初めての署名方式で、[[強RSA仮定]]のもとCMA-EUF安全である事が示されており、RSA暗号の数倍程度の計算量で署名作成・検証を行なう事ができる。 |
|||
ElGamal署名やSchnorr署名のような素体の乗法群上の離散対数問題を基にした署名方式は素体の乗法群の代わりに[[楕円曲線]]群を用いる事で計算量を少なくし、しかも署名長を短くする事ができる。楕円曲線群を用いたElGamal署名、Schnorr署名をそれぞれ楕円ElGamal署名、楕円Schnorr署名と呼ぶ。 |
|||
==関連項目== |
==関連項目== |
||
2008年4月29日 (火) 09:28時点における版
電子署名（でんししょめい）とは、電磁的記録（電子文書）に付与する、電子的な徴証であり、紙文書における印やサイン（署名）に相当する役割をはたすものである。主に本人確認、偽造・改竄の防止のために用いられる。
電子署名を実現する仕組みとしては、公開鍵暗号方式に基づくデジタル署名が有力である。日本では電子署名及び認証業務に関する法律（電子署名法）にて、RSA、DSA、ECDSA の3方式を指定している。いずれも公開鍵暗号方式に基づく方式である。
電子署名の必要性
ある文書についてその作成者として文書に記載されている者（作成名義人）がある場合、その文書が本当にその作成名義人によって作成されたものであることは、通常はその文書に付されたその作成者の署名や印によって証明される。しかし、電子文書にはもちろん直接印を押したり署名を付することはできない。紙に付した印や署名をスキャナで取り込み、その画像を文書に付与しても、スキャナで取り込んだ印や署名は簡単にコピー＆ペーストできるため証明力がない。
電子取引を普及させるためには（特に金額が大きいなど重要なものについては）、取引に用いる電子文書について、作成者の保証と内容的な同一性（非改ざん性）を実現する仕組みが必要となる。つまり、通常の紙文書に用いる印や署名に相当する（電子文書の作成者を証明することが可能な）仕組みであり、（本来電子文書は改ざんが容易であるので）電子文書が改ざんされないような、あるいは改ざんされた場合にそのことが明瞭となる仕組である。
電子署名のモデル
電子署名方式には鍵生成アルゴリズム、署名(生成)アルゴリズム、検証アルゴリズムという3つのアルゴリズムがある。
鍵生成アルゴリズムは事前準備にあたるアルゴリズムで、署名をしたいと思うユーザは事前にこのアルゴリズムを行う必要がある。ユーザがこのアルゴリズムを実行すると、アルゴリズムはそのユーザの公開鍵および秘密鍵（と呼ばれるデータ）を出力する。印鑑に例えていうと、秘密鍵は実印に対応するもので、公開鍵は印鑑照合に使う台紙（印鑑証明書）に対応するものである。
ユーザは鍵生成アルゴリズムを実行する際、セキュリティ・パラメータと呼ばれる値をこのアルゴリズムに入力する。セキュリティ・パラメータは、署名文を偽造することの困難さを表した尺度である。さらに鍵生成アルゴリズムには乱数も入力される。鍵生成アルゴリズムが実行される度に異なる乱数が選ばれるので、ユーザ毎に異なる公開鍵・秘密鍵ペアが割り振られることになる。
各ユーザは秘密鍵（実印に相当）を他人が使用することができないように保管する一方、公開鍵（印鑑証明書に相当）を皆に公開する。よってユーザの秘密鍵を知っている（使うことができる）のはユーザ自身だけであるのに対し、そのユーザの公開鍵は全てのユーザが容易に知りうることになる。公開鍵、秘密鍵をそれぞれ検証鍵、署名鍵ともいう。
一度事前準備をすませたユーザは何度でも秘密鍵（署名鍵）を用いて電子文書に電子署名することができる。電子署名するには、まず署名生成アルゴリズムにメッセージを入力する。すると署名生成アルゴリズムはメッセージに対する署名者の署名文を出力する。署名を作成したユーザをその署名文に対する署名者という。
署名者は署名文を作成する際、メッセージとともに自分の秘密鍵を入力する。署名者の秘密鍵を知っている（使うことができる）のは署名者本人だけのはずなので、署名者以外の人は同じ方法で同じ署名を作成することはできないことになり、この性質が電子署名を付した電子文書の作成者を識別する根拠になる。
署名者はメッセージとそれに対する署名文を他のユーザに送る。
メッセージと署名文を受け取ったユーザ（検証者）は、これらを入力して検証アルゴリズムを実行する事で署名文が正しいかどうかを検証することができる。この際検証者は検証アルゴリズムに署名者（だと推定されるユーザ）の公開鍵（検証鍵）も入力する。（公開鍵は公開情報なので、検証者は署名者の公開鍵を知ることができる）。
検証アルゴリズムは署名文が本当にそのユーザによって作成されたか否かを判定し、その結果を出力する。 検証アルゴリズムが署名文を正当(valid)だと判断したことを、「検証アルゴリズムがA署名文を受理(accept)した」、もしくは「署名文が検証を通過した」という。それに対し検証アルゴリズムが署名文を不当(invalid)だと判断したことを、「検証アルゴリズムがA署名文を棄却(reject)した」、もしくは「署名文が検証を通過しなかった」という。
補足 （公開鍵の認証）
公開鍵を公開する際には、信頼できる第三者機関を介して公開することが望ましい。各公開鍵を、公開鍵の持ち主と対応させる方法は幾つか知られているが、代表的な方法は以下の二つである。
- 信頼できる第三者機関(Trusted Third party)が各人のIDと公開鍵を対応付けた表（公開鍵簿）を作成し、公開する。
- 信頼できる第三者機関（達）が認証局を運営し、PKIの仕組みを用いる事で各人のIDと公開鍵を対応付ける。
電子文書の真正な成立の推定
民事訴訟法は、「文書は、その成立が真正であることを証明しなければならない。」と規定する（228条1項）。民事訴訟では、ある文書をその作成者として記載されている者（作成名義人）によって作成されたものとして証拠に用いるには、まずそのこと（その文書が本当にその作成名義人によって作成されたものであること＝真正な成立）を証明しなくてはならない。
例えば、甲が乙を訴えた訴訟において、甲・乙の署名押印がある契約書を甲が証拠として用いるには、（甲自身については自認すれば良いとして、）乙が本当にその契約書作成したということをまず証明しなければならない。しかし過去のある時点で行われた（作成という）行為を証明するのはなかなか困難なことである場合が少なくない。
その負担を緩和するため、民事訴訟法は228条4項で「私文書は、本人又はその代理人の署名又は押印があるときは、真正に成立したものと推定する。」と規定し、229条1項では、「文書の成立の真否は、筆跡又は印影の対照によっても、証明することができる」と規定している。
これにより、甲は契約書にある乙の（ものとして付されている）署名押印が確かに乙のものであるということを証明すれば、反証されない限りその契約書を証拠として用いることができるのである。そして、その契約書に乙の実印による押印がされていて、かつその印影が乙の印鑑証明書のそれと一致するのであれば、その押印が乙の意思によるものであることもまた経験則上容易に推定される。
乙の実印による押印と印鑑証明書が付されていることによってその契約書は、（それに反する事実を乙が証明しない限り）真正な成立の証明に多大な労力を費やすことなく証拠として用いることができるわけである。
電子署名法は、電子文書はその内容について本人による電子署名が行われているときは真正に成立したものと推定すると規定している（3条）が、これは民事訴訟法228条4項の電子文書版ということができる。
関連項目
- 暗号理論
- 電子証明書
- 電子署名及び認証業務に関する法律（電子署名法）
- データ完全性