ディジタル署名は公開鍵暗号と対称関係にあるのか
『暗号技術のすべて』の第7章を参考にしました。 ディジタル署名（電子署名）についてです。
ディジタル署名はよく「公開鍵暗号とは対称関係である」といわれますが、そうではないということを説明していきます。
ディジタル署名とは
署名とは、「本人であることを明らかにするために自分の氏名を記すこと」です。
- 現実世界：文書に捺印
- 電子的：電子文書に捺印に相当するデータを付与
このように電子的に署名することを ディジタル署名といいます。
ディジタル署名アルゴリズム
ディジタル署名は、
の3つのアルゴリズムで構成されます。 今回は、内部構造は気にせずに入出力だけ書いていきます。
鍵生成アルゴリズム
- 入力：k（セキュリティパラメータ）
- 出力：vk（検証鍵）、sk（署名鍵）
検証鍵は誰でも参照できるようにし、署名鍵は他人には秘密にするものです。
署名作成アルゴリズム
- 入力：m（平文）、sk（署名鍵）
- 出力：σ（署名）
入力に平文が含まれるので、署名は、平文によって異なるデータとなります。
署名検証アルゴリズム
- 入力： m（平文）、σ（署名）、vk（検証鍵）
- 出力：0 or 1
検証が成立すれば1、成立しなければ0を出力します。
ディジタル署名の誤解
アルゴリズムを見ると分かる通り、検証鍵が公開されており、 署名鍵が秘密にされていることから、公開鍵暗号と対比し、
- 検証鍵＝公開鍵
- 署名鍵＝秘密鍵
と捉え，
と説明されることがありますがこれは大きな誤解です。
公開鍵暗号からディジタル署名が作れるのか？
署名作成アルゴリズムに公開鍵暗号の復号アルゴリズム、
署名検証アルゴリズムに公開鍵暗号の暗号アルゴリズムを
用いることでディジタル署名アルゴリズムもどきを
作成することが出来ます（下図）。
これのどこが問題なのでしょうか？ 実は、署名検証アルゴリズムに問題があります。 同一の平文に対して、異なる暗号文を出力するような暗号のアルゴリズムを 署名検証アルゴリズムで用いると、検証のための m' が実行したタイミングによって 異なるので、検証がうまくいきません。
結論
以前の記事 で紹介したRSA暗号のように平文空間と暗号文空間が同じな確定的暗号なら 問題ないですが、ElGamal暗号のような確率的暗号では、このような構成に することはできません。
