暗号化と署名は対称じゃないよという話
高木浩光＠自宅の日記 - 公開鍵暗号方式の誤り解説の氾濫をそろそろどげんかせんとより。
これらの解説は誤っている。これらは、RSAアルゴリズムを説明するものにはなり得ても、公開鍵暗号方式を説明するものになっていない。公開鍵と秘密鍵が「逆に使える」というのはRSAアルゴリズムがたまたま（まあまあ）そうなだけであって、そのような性質を持たない他の公開鍵暗号方式がたくさん存在する。
暗号鍵（公開鍵）と復号鍵（秘密鍵）を逆にしても使えるのがRSAで、だから「秘密鍵で暗号…」という説明が多いんだけど、それはごく一部の方式でしかないよ、という話。 問題は、この誤解がどういう弊害を生むかなんだろうけど、これについて書くにはちょっと知識が足りない。
なので、ブクマコメントに書かれていた誤解に限定して書くことにする。 以下はコメントからの引用。
鍵Ａで暗号化した暗号文は鍵Ｂでのみ複号できる。ＡとＢどちらを公開するかが公開鍵暗号方式と電子署名の違い、だと思う
確かに、こう考えてしまいがちだけど、これは間違い。 これだと、公開鍵暗号のアルゴリズムは、どれでも署名にも使えることになっちゃう。 でも一般的には、暗号用のアルゴリズムは署名には使えないんだよね。 なるべく分かりやすく書いてみるけど、暗号の専門家じゃないので間違いがあるかも。
※ この誤解は高木さんが問題にしている誤解（署名＝秘密鍵で暗号化）とはちょっと違うので注意。念のため。
公開鍵暗号についておさらい
厳密な定義は公開鍵暗号 - Wikipediaを参照してもらうとして、とりあえずこんな特徴を持つものと考えるよ。
- 鍵生成 … 暗号化用の鍵E（公開鍵）と復号用の鍵D（秘密鍵）を用意する
- 暗号化 … 暗号鍵Eを使うと、平文Mを暗号文Cに変換できる
- 復号 … 復号鍵Dを使うと、暗号文Cを平文Mに変換できる
図にするとこんな感じかな。 ちなみに、 E は Encrypt (暗号化) で D は Decrypt (復号) の略ね。
鍵E 鍵D M ------> C ------> M 暗号化 復号 ※ 他の人が C → M の変換（暗号解読）が可能だと困る
暗号鍵Eをみんなに公開して、復号鍵Dを自分だけが持っていれば、自分だけが暗号文を読むことができる。 このときに重要なのは、当たり前だけど「鍵Dを持っている人だけが暗号文Cを平文Mに変換できる」ということ。 そうじゃないと、誰でも暗号文を読めちゃう。
そのまま署名に使ってみると？
それじゃ、暗号鍵Eを秘密にして復号鍵Dを公開すれば署名になるか？ってことを考える。 仕組み自体はさっきと同じ。
鍵E 鍵D
M ------> C ------> M
署名 検証
※ 他の人が M → C の変換（署名の偽造）が可能だと困る
暗号鍵Eを自分だけがもっていて、復号鍵Dを公開すれば、Cを作れるのは自分だけ。 だから、さっきの暗号文Cがそのまま署名Cとしても使える…と思えるけど、実はここに落とし穴がある。
暗号化と署名では必要となる条件が違う
署名でいちばん大切な条件は、「自分以外の人が署名を作れない」こと。 印鑑を持っていない人にハンコを偽造されると困るのと同じ。
でも、さっきも書いたとおり、暗号化でいちばん大切な条件は、「復号鍵Dを持っていない人が暗号文Cを復号できない」ことであって、「暗号鍵Eを持っていない人が暗号文Cを作れない」ことじゃない。 ちょっと混乱するけど、この違いは実は大きい。 「暗号鍵Eを持っていない人が暗号文Cを作れる」ような暗号アルゴリズムをそのまま署名に使っちゃうと、誰でも署名を偽造できちゃう。
ちなみに、こういう暗号アルゴリズムの例として、ElGamal暗号 - Wikipediaがある。
ElGamal暗号は、選択暗号文攻撃に対しては安全ではない。平文mに対応する(c1,c2)から、2mに対応する暗号文(c1,2c2)を作成することができるからである。
ある文書（m）とその署名（c1,c2）があれば、誰でも別の文書（2m）とその署名（c1,2c2）が作れちゃう。
鍵E 鍵D
m ------> c1,c2 ------> m
署名 検証
鍵D
c1,c2 ------> c1,2c2 ------> 2m
偽署名 検証
※ 鍵Eを持たなくても2mの署名を偽造できる！
これじゃ、署名に使えない。 他にも、「暗号鍵Eから復号鍵Dは作れないけど、復号鍵Dから暗号鍵Eを作ることができる」ような暗号アルゴリズムがあっても、やっぱり暗号化にしか使えない。
※ 追記: 高木さんの話の余波についての誤りの指摘 - 186::Diaryでコメントをいただきました。 ElGamal暗号がまさにこの特徴をもつので、暗号化にしか使えないとのことです。
まとめると「暗号化と署名では必要となる条件が違うので、普通は暗号アルゴリズムを署名に使えない」ということ。 「秘密鍵で暗号化して署名を…」という記述は暗号化と署名が対称な関係に見えちゃうので、確かに誤解のもとかもしれない。
ちなみにRSAでは
RSA暗号の特徴は、「復号鍵Dでも暗号化が可能」で「暗号化と復号のアルゴリズムが同じ」なこと。 図にすると、こうなる。
鍵E 鍵D M ------> C1 ------> M 暗号化 復号
鍵D 鍵E M ------> C2 ------> M 暗号化 復号
暗号化 C1 = M ^ E mod N 復号 M = C1 ^ D mod N
この2つの特徴があるので、鍵Dを使って暗号化することで署名も実現できる。
- 復号鍵Dがないと、暗号文C1を平文Mに戻せない
- C1 から M を計算する方法と、 M から C2 を計算する方法が同じ
ということから、復号鍵Dを持たない人は暗号文を復号（C1→M）できないのと同じように、署名の偽造（M→C2）もできない、と。 これはちょっと乱暴な議論で、厳密にはもっと条件があるんだけど…。
この特徴はRSAに限ったもので、普通の公開鍵暗号では、暗号鍵Eと復号鍵Dを入れ替えて使うことができないし、暗号化と復号のアルゴリズムも同じじゃない。 なので、「暗号鍵Eを秘密にして復号鍵Dを公開する」ことや、「復号鍵Dで暗号化して署名を作る」ということは、普通はできないよ、と。
それじゃあ
RSA以外の署名アルゴリズムは、どうやって署名を実現しているの？ってことなんだけど、これは僕もちゃんと理解していないので分かりやすく書けない。 ということで、暗号技術入門-秘密の国のアリスや、暗号技術大全をお勧め。
追記
ブクマコメントより。
この辺の話はちょっとした(しかし重大な)言葉の問題が糾弾されたり、デファクトスタンダードが一般論化したりとなかなか難しいけど
「wikiはWikipediaのことではない」<=>「公開鍵暗号はRSAのことではない」みたいな話だろうか
Wikipedia は最も普及した Wiki だけど、高木さんの記事を読む限りこの問題はちょっと違うように思える。
暗号の専門家に確認したところ、少なくとも、前者については最初に発表された公開鍵暗号方式がその性質を持たないこと、後者については現に広く使用されている方式がその方法ではないことから、完全なる誤りと言ってよいとのことだった。
秘密鍵で暗号化するRSA署名はあんまり普及してないよってことみたい。 確かに、SSHでログインするときの鍵もDSAが標準だし。（一応RSAも使えるけど）
追記2 … 無理やりまとめると
最低限これだけ知っておけばいいと思った。
- 暗号化と署名では必要となる条件が違う。暗号化の場合は他の人が暗号文を復号できないことが大切。署名の場合は他の人が署名を偽造できないことが大切。
- ふつうは、暗号文は元に戻す（復号する）ことができるが、署名は元に戻すことができない。
- 元に戻すことができないので、署名を「秘密鍵で暗号化」と説明することは正しくない。
- RSA暗号はたまたま、暗号化と署名のどちらにも使える性質を持っている。