電子署名とは

現代暗号の基礎数理 (電子情報通信レクチャーシリーズ) 黒沢馨,尾形わかは

電子署名を学ぶことは、公開鍵暗号を学ぶことと同義です。「現代暗号の基礎数理」を教科書にして学びましょう。

公開鍵暗号系の要素

公開鍵暗号は、３つのアルゴリズムから構成されています。

１、鍵ペア生成アルゴリズム

メッセージ受信者（ボブ）が、公開鍵と秘密鍵のペアを生成し、公開鍵をメッセージ発信者（アリス）にメールなどで通知する。ホームページで公開して万人に閲覧させても良い。公開鍵は方程式の形（数式のパラメーター）を示し、秘密鍵は方程式の整数解です。方程式の変数に解を代入して計算すれば、すぐに方程式が成り立つかどうか、その解が正しいかどうか分かりますね。他方、方程式が与えられても解を算出するには「時間が掛かる」場合がありますね。この秘密鍵と公開鍵の適合性を検証する時間と、公開鍵（方程式）から秘密鍵（解）を探り当てるのに掛かる時間の比率（倍率・非対称性）が、公開鍵暗号の安全性の根拠となります。方程式に解の公式が無い場合、取り得る全ての可能性（256bit=32byteなら、10進数で78桁の数値）をしらみつぶしに試算して、解を探索することになります。例えば、秘密鍵と公開鍵の適合性検証は１秒で完了するが、公開鍵から秘密鍵を割り出すには世界最高のスーパーコンピューターを使っても１億年掛かるという場合には、この暗号は安全だし実用的に使える、ということになります。ちなみに、この公開鍵で定義される方程式というのは、解の公式があるような単純な多項式（２次方程式とか３次方程式）というようなものでもないし、微分して解析的に解けちゃうようなものでもありません。通常は離散対数問題の困難性といわれるものが使われています。最近では、量子コンピューターでも計算できないLWE問題の困難性が提案され、次世代暗号候補として検討されています。

２、暗号化アルゴリズム

アリスが送信したい平文メッセージを、公開鍵を使って暗号化し、暗号文を生成し、ボブに送信する。手紙でも、メールでも、途中に盗聴者が居て、暗号文をコピーして解析することが可能。それでも合理的時間内に解読することはできない。

３、復号化アルゴリズム

暗号文を受領したボブは、秘密鍵を使って復号化して、平文メッセージを取得する。

RSA暗号の場合、暗号化と復号化は、つぎの数式で表現できます。

$$m=(m^e)^d \bmod N$$

ここで、ｍが平文メッセージで、eが暗号化する公開鍵(encrypt key)で、dが復号化する秘密鍵(decrypt key)です。この e と d の順番を入れ替えても数式が同じように成り立つことを利用して電子署名と検証が行われます。

$$m=(m^d)^e \bmod N$$

これは、フェルマーの小定理、

$$a^p \equiv a\pmod{p}$$

を利用したものです。実際の電子署名では、ｍの代わりにｍのハッシュ値である、H(m)が使われます。

$$H(m)=(H(m)^d)^e \bmod N$$

署名文は、

$$H(m)^d \bmod N$$

です。これを作成できるのは秘密鍵を保持しているアリスだけというわけです。ボブは公開鍵を使って、

$$(H(m)^d)^e \bmod N$$

を計算して、これがメッセージのハッシュ値と一致すれば、署名は秘密鍵を持っている人物が行ったと確認できるわけです。要するに、秘密鍵を使って暗号化するのが電子署名で、公開鍵を使って復号化するのが署名検証ということになります。

電子署名の要素

電子署名は、「認証」と「否認不可」の２つの機能を持っています。ボブは署名が確かにアリスのものであると納得できるし、アリスは裁判所など第三者に対してそのメッセージを送信したことを否定できません。

これも公開鍵暗号系と同じで３つのアルゴリズムを使います。

１、鍵ペア生成アルゴリズム

アリスは秘密鍵と公開鍵のペアを生成し、公開鍵をボブも含めて公開し、秘密鍵を秘密に保持する。

２、署名アルゴリズム

アリスはメッセージのハッシュ値と、秘密鍵を用いて、署名を算出する。そして、メッセージと署名をボブに送信する。

３、検査アルゴリズム

ボブは受け取った署名を、公開鍵を使って検査して、アリスが公開鍵に対応する秘密鍵を用いて署名したことを検査する。