電子署名

出典: フリー百科事典『ウィキペディア（Wikipedia）』

電子署名（でんししょめい）とは、電子的な文書に付与する、電子的な徴象であり、紙文書での印やサインに相当する機能を意図したものである。主に本人確認、偽造・改竄の防止のために用いられる。

電子署名を実現する仕組みとしては、公開鍵暗号方式に基づくデジタル署名が有力である。日本では電子署名及び認証業務に関する法律（電子署名法）にて、RSA、DSA、ECDSA の3方式を指定している。いずれも公開鍵暗号方式に基づく方式である。

[編集] 概要

我々は日常、文章の文責者が自分である事を保証する為に、紙に印を押したり、署名を書いたりする。しかし印や署名は紙媒体に書かれた文章には有効な文責者保証手段であるものの、電子的に書かれた文書に対してはそうではない。そもそも電子的な文章に直接印を押したり署名を書いたりする事はできないし、仮に紙媒体に付与した印や署名をスキャナで取り込んで文書に付与しても、スキャナで取り込んだ印や署名は簡単にコピー＆ペーストできるので、文責者を保証する効果がない。

この為電子的な文書の文責者を保証するには通常の印や署名とは異なる別の仕組みが必要である。このような仕組みとして電子署名がある。通常の印や署名の代わりに文書に電子署名を付与する事で文章の文責者を保証する事ができる。

[編集] 電子署名のモデル

電子署名方式には鍵生成アルゴリズム、署名(生成)アルゴリズム、検証アルゴリズムという３つのアルゴリズムがある。

鍵生成アルゴリズムは事前準備にあたるアルゴリズムで、署名をしたいと思うユーザは事前にこのアルゴリズムを行う必要がある。ユーザがこのアルゴリズムを実行すると、アルゴリズムはそのユーザの公開鍵および秘密鍵(と呼ばれるデータ)を出力する。印鑑に例えていうと、秘密鍵は印鑑に対応するもので、公開鍵は印鑑照合に使う台紙に対応するものである。

ユーザは鍵生成アルゴリズムを実行する際、セキュリティ・パラメータと呼ばれる値をこのアルゴリズムに入力する。セキュリティ・パラメータは、署名文を偽造する事の困難さを表した尺度である。

さらに鍵生成アルゴリズムには乱数も入力される。鍵生成アルゴリズムが実行される度に異なる乱数が選ばれるので、ユーザ毎に異なる公開鍵・秘密鍵ペアが割りふられる事になる。

各ユーザは秘密鍵を秘密裡に保管し、公開鍵を皆に公開する。よってユーザの秘密鍵を知っているのはそのユーザ自身だけであるが、それに対しユーザの公開鍵を知っているのは全てのユーザである事になる。

公開鍵、秘密鍵の事をそれぞれ検証鍵、署名鍵ともいう。

一度事前準備をすませたユーザは何度でも文章に署名する事ができる。文章に署名するには、署名生成アルゴリズムにメッセージを入力する。すると署名生成アルゴリズムはメッセージに対する署名者の署名文を出力する。署名を作成したユーザをその署名文に対する署名者という。署名者は日常語でいう「文責者」にあたる。

署名者は署名文を作成する際、メッセージのみならず自分の秘密鍵をも入力する。署名者の秘密鍵を知っているのは署名者自身だけであるので、署名者以外の人は同じ方法で署名を作成する事ができない。この事が署名文の作成者を識別する根拠になる。

署名者はメッセージとそれに対する署名文を他のユーザに送る。

メッセージと署名文を受け取ったユーザ(検証者)は、これらを入力して検証アルゴリズムを実行する事で署名文が正しいかどうかを検証する事ができる。この際検証者は検証アルゴリズムに署名者(だと推定されるユーザ)の公開鍵も入力する。(公開鍵は公開情報だったので、検証者は署名者の公開鍵を知る事ができる)。

検証アルゴリズムは署名文が本当にそのユーザによって作成されたか否かを判定し、その結果を出力する。検証アルゴリズムが署名文を正当(valid)だと判断した事を、「検証アルゴリズムがA署名文を受理(accept)した」、もしくは「署名文が検証を通過した」という。それに対し検証アルゴリズムが署名文を不当(invalid)だと判断したを、「検証アルゴリズムがA署名文を棄却(reject)した」、もしくは「署名文が検証を通過しなかった」という。

[編集] 補足 (公開鍵の認証)

公開鍵を公開する際、どの公開鍵が誰のものであるのかが分からなくならないようにしなければならない。前述したように、公開鍵は印鑑照合用の台紙に対応するものなので、自分の公開鍵を偽る事で様々な不正ができてしまうからである。各公開鍵を、公開鍵の持ち主と対応させる方法は幾つか知られているが、代表的な方法は以下の二つである。

信頼できる第三者機関(Trusted Third party)が各人のIDと公開鍵を対応付けた表（公開鍵簿）を作成し、公開する。
信頼できる第三者機関（達）が認証局を運営し、PKIの仕組みを用いる事で各人のIDと公開鍵を対応付ける。

[編集] 電子署名方式の定義

(電子)署名方式((でんし)しょめいほうしき、(digital) signature scheme)は平均多項式時間確率アルゴリズムの三つ組み(G,S,V)である。

Gは鍵生成アルゴリズム(かぎせいせいあるごりずむ、key generation algorithm)と呼ばれ、1^kを入力されると公開鍵・秘密鍵ペア(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_pk(m,s)=ACCEPTとなるとき、署名文sは、（公開鍵pk,および平文mに関し）検証を通る（accept,「validである」ともいう）といい、そうでないとき検証を通らない(reject, 「invalidである」ともいう)。

[編集] 要件

電子署名(G,S,V)は次の要件を満たさねばならない：
Correctness：正当な署名者が作った署名文は、検証を通過する。
Security：検証を通過するのは正当な署名者が作った署名文に限る。

ただしここで「正当な署名者」というのは、検証に用いた公開鍵に対応する秘密鍵の持ち主を指す。

[編集] 要件の厳密な定義

[編集] 正当性の厳密な定義

任意の平文mに対し、
$\mathrm{Pr}(V_{\mathbf{pk}}(m,s)=\mathbf{ACCEPT}|(\mathbf{pk},\mathbf{sk})\gets G(1^k), s\gets S_{\mathbf{sk}}(m))$ はoverwhelming。

[編集] 安全性の厳密な定義

電子署名の安全性(Security)の要件をより厳密に定義する。「検証を通過するのは正当な署名者が作った署名文に限る」というのが、いかなる条件下でいかなる目標を達する事を指すのかによって電子署名方式の安全性の定義は数種類に存在するが、単に「安全」といった場合選択文書攻撃に対する存在的偽造不能性(Existencial Unforgeability against Chosen Message Attack, EU-CMAと略す）を指す事が普通なので、ここではこの定義を紹介する。

準備
$Σ = (G, S, V)$ を電子署名方式とし、kをセキュリティ・パラメータとする。 Aを電子署名方式 $Σ$ に対する攻撃者とする。攻撃者Aを用いて、次のような実験(experiment ゲーム(game)とも言う)を行なう。
まず1^kを入力として鍵生成アルゴリズムを走らせ、公開鍵・秘密鍵ペア(pk,sk)を作る。そしてpkとkを攻撃者Aに渡す。
攻撃者Aは実験の最中、署名オラクルO(sk,・)に任意の回数アクセスする事ができる。署名オラクルとは、攻撃者Aから平文mを送信されると、秘密鍵skを使ってmに対する署名文s=S_sk(m)を作成し、sをAに送信するオラクルの事である。
攻撃者Aの目標は、平文mと署名文sとの組(m,s)で検証を通り、しかも署名オラクルOにmを送信していないものを出力する事。そのような(m,s)を作成できればAの勝ち、そうでなければAの負けである。
以上の実験をより形式的に書くと、以下の通り。

Experiment

$(\mathbf{pk},\mathbf{sk})\gets G(1^k)$

$(m,s) \gets A^{O(\mathrm{sk},\cdot)}(1^k,\mathbf{pk})$

If(

A

が $O(\mathbf{sk},\cdot)$ に

m

を聞いた事がある) Return LOSE

If( $V_{\mathbf{pk}}(m,s)=\mathbf{Reject}$ ) Return LOSE

Return WIN

実験でAが勝つ確率を $\mathbf{Succ}_{\Sigma}^k(A)$ と書く事にする。(注：この記号は比較的良く使われるものの、必ずしも皆の合意がとれた記号ではないので、使用するときには一言説明が必要である)。
ただしここで確率はG,S,V,Aの内部乱数をランダムに選んだときのもの。

定義
$Σ = (G, S, V)$ を電子署名方式とする。任意の平均多項式時間確率アルゴリズムAに対し、 $\mathbf{Succ}_{\Sigma}^k(A)$ がkに関しnegligibleなとき、電子署名方式 $Σ$ は選択文書攻撃に対し存在的偽造不能であるという。

[編集] 代表的な電子署名方式

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署名と同程度の効率を持つ。
ランダムオラクルは暗号理論の研究でよく使用される概念で、ハッシュ関数が「十分ランダムに振舞う」という事を理想化した概念である。ランダムオラクル仮定は「ランダムオラクルが存在する」という仮定であるが、ランダムオラクルはあくまで現実を理想化したものであり現実的には存在し得ないものである。

Cramer-Shoup署名はランダムオラクルのような理想化された仮定を用いないで安全性が示せる(もので、かつ効率的な)初めての署名方式で、強RSA仮定のもとCMA-EUF安全である事が示されており、RSA暗号の数倍程度の計算量で署名作成・検証を行なう事ができる。

ElGamal署名やSchnorr署名のような素体の乗法群上の離散対数問題を基にした署名方式は素体の乗法群の代わりに楕円曲線群を用いる事で計算量を少なくし、しかも署名長を短くする事ができる。楕円曲線群を用いたElGamal署名、Schnorr署名をそれぞれ楕円ElGamal署名、楕円Schnorr署名と呼ぶ。

カテゴリ: 暗号技術