まちゅダイアリー

■ 暗号化と署名は対称じゃないよという話

高木浩光＠自宅の日記 - 公開鍵暗号方式の誤り解説の氾濫をそろそろどげんかせんとより。

これらの解説は誤っている。これらは、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 … 無理やりまとめると

最低限これだけ知っておけばいいと思った。

1. 暗号化と署名では必要となる条件が違う。暗号化の場合は他の人が暗号文を復号できないことが大切。署名の場合は他の人が署名を偽造できないことが大切。
2. ふつうは、暗号文は元に戻す（復号する）ことができるが、署名は元に戻すことができない。
3. 元に戻すことができないので、署名を「秘密鍵で暗号化」と説明することは正しくない。
4. RSA暗号はたまたま、暗号化と署名のどちらにも使える性質を持っている。

■ 署名はハッシュ関数やMACの延長で説明したほうがいいのでは？

それじゃ、署名って何よ？って話になってくるけど、暗号と署名の話 - 186::Diaryの説明を読む限りは、暗号化の延長線として話をするよりも、メッセージダイジェストやMACの延長線として話をすればいいんじゃないかと思った。 そもそも要件が違うものを暗号化と一緒に説明するから混乱する訳で。 説明のたたき台として、Rubyのコードで書いてみる。

ハッシュ関数

まずは普通のハッシュ関数を使ったダイジェストから。ある意味、誰でも作れる署名。

# 署名（ハッシュ値）の生成
signature = SHA1::hexdigest(message)

# 署名（ハッシュ値）の検証
if (sigunature == SHA1::hexdigest(message)) {
  puts 'OK'
} else {
  puts 'NG'
}

これは、Webサイトでファイルを配布しているときに、一緒に *****.sha1 などのファイルが置かれていたりするもの。 コマンドラインからだと sha1sum などで生成と検証ができる。 でもこれだと、誰でもダイジェストが作れちゃう。そこで、次にMACの登場。これは、限られた人だけが作れる署名。

MAC（メッセージ認証コード）

# 署名（MAC）の生成
sha1 = Digest::SHA1.new
signature = HMAC::hexdigest(sha1, key, message)

# 署名（MAC）の検証
sha1 = Digest::SHA1.new
if (sigunature == HMAC::hexdigest(sha1, key, message)) {
  puts 'OK'
} else {
  puts 'NG'
}

第一引数のsha1は使うハッシュ関数を指定しているだけ。大切なのは key が増えたこと。 このkeyを知らないと署名を作ることができない。 MACの場合は署名と検証の鍵が同じなので、検証する人が署名を作ることができる。

最後は公開鍵暗号を応用したデジタル署名。 Rubyのコードは適当…なのでこのままじゃ動かない。

デジタル署名

# 署名（デジタル署名）の生成
signature = Tekito::sign(signkey, message)

# 署名（デジタル署名）の検証
if (Tekito::verify(verifykey, message, signature)) {
  puts 'OK'
} else {
  puts 'NG'
}

こんどは署名用の鍵と検証用の鍵が別になってる。 なので、検証者が署名を作ることはできない。

署名の検証は暗号文の復号とは違う

3つのコードを比べて気がつくと思うけど、どれも署名 signature を元のデータ message に戻したりしていない。

# 署名（ハッシュ値）の検証
if (sigunature == SHA1::hexdigest(message))

# 署名（MAC）の検証
if (sigunature == HMAC::hexdigest(sha1, key, message))

# 署名（デジタル署名）の検証
if (Tekito::verify(verifykey, message, signature))

ハッシュ値とMACの場合は、元のデータmessageから署名を作ってみて、元の署名signatureと一致するかどうかを比較しているだけ。 デジタル署名は元のデータから署名を作ることができない（できると偽造だから）けど、代わりにtrue/falseを返すverify関数がある。

※ 本来のデジタル署名はハッシュ関数と組み合わせて使うんだけど、ここでは意図的に話を簡略化している。

署名 signature から元のデータ message に戻せるわけじゃないので、署名 signature を作ることを「秘密鍵で暗号化」というのは変という話。 だから、暗号化と署名を対にして説明するよりも、ハッシュ関数→MAC→デジタル署名の流れで説明したほうが分かりやすいと思う。 と思って、結城さんの暗号技術入門の目次を読むと、ちゃんと「第II部 認証」で「第7章 ハッシュ関数」「第8章 メッセージ認証コード」「第9章 デジタル署名」という流れになっていた。すごい。

■ ツッコミへのお返事

なぜか自分の日記に自分でツッコミが入れられないので、いただいたツッコミにここでお返事。

この点を考えると, 「鍵を逆さにすると署名が構成できる」いう説明はRSAに限定したとしても問題があります.

「暗号鍵Eと復号鍵Dを入れ替えて使う」というのはp,q,dを公開するのではなくp,q,dで暗号化するという意味で書きました。ちょっと紛らわしかったですね。すみません。

ツッコミ感謝です。