高木さんの話の余波についての誤りの指摘

何で訂正しようとした方の説明が余計変なんだ...
適当に指摘します. あとで細かいところも見るかも.

暗号と署名の話に何故ElGamal暗号方式をひっくり返しただけではダメになるかを書いています. そちらもご覧ください.

暗号化と署名は対称じゃないよという話 - まちゅダイアリー (2008-03-02)

概要: ElGamal暗号は鍵を逆さにした途端にダメになります. 選択暗号文攻撃は関係ありません.

引用
公開鍵暗号についておさらい

厳密な定義は公開鍵暗号 - Wikipediaを参照してもらうとして、とりあえずこんな特徴を持つものと考えるよ。

  • 鍵生成 … 暗号化用の鍵E（公開鍵）と復号用の鍵D（秘密鍵）を用意する
  • 暗号化 … 暗号鍵Eを使うと、平文Mを暗号文Cに変換できる
  • 復号 … 復号鍵Dを使うと、暗号文Cを平文Mに変換できる

図にするとこんな感じかな。ちなみに、 E は Encrypt (暗号化) で D は Decrypt (復号) の略ね。

    鍵E       鍵D
M  ------> C ------> M
   暗号化     復号
※ 他の人が C → M の変換（暗号解読）が可能だと困る

(略)

そのまま署名に使ってみると？

それじゃ、暗号鍵Eを秘密にして復号鍵Dを公開すれば署名になるか？ってことを考える。仕組み自体はさっきと同じ。

    鍵E       鍵D
M  ------> C ------> M
    署名      検証
※ 他の人が M → 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を作ることができる」ような暗号アルゴリズムがあっても、やっぱり暗号化にしか使えない。
まとめると「暗号化と署名では必要となる条件が違うので、普通は暗号アルゴリズムを署名に使えない」ということ。「秘密鍵で暗号化して署名を…」という記述は暗号化と署名が対称な関係に見えちゃうので、確かに誤解のもとかもしれない。

指摘

暗号で使われる問題として離散対数問題が知られています. ElGamal暗号/署名方式の場合を考えると, 群Z_p, Z_pの生成元g, Z_pの要素yが与えられたときに, y=g^x mod pとなるxを求めよという問題です. ここでg^xはgをx回掛けたものという意味です. そこそこ難しい問題だと思われています.

ElGamal暗号の復号鍵Dはxです. 暗号化鍵Eは(p,g,g^x)です. 従って暗号化鍵Eから復号鍵Dを求めるのはまさに離散対数問題であり, 難しそうです.

さて説明の通り, 鍵を逆にしてみましょう. すると, 署名鍵Eがg^xで検証鍵Dが(p,g,x)です. どう考えても, 検証鍵から署名鍵が求まります. なにせgとxがあるので, g^xを求められます.
だから鍵を逆さにするだけだと出来ません. というか鍵を逆さにしてはいけません.

ということなので選択暗号文攻撃というややこしいものを考える前に話が破綻してしまいました.

補足

RSAの場合は暗号化鍵が(n,e), 復号鍵は(p,q,d)です. 署名に使う場合には署名鍵は(p,q,d), 検証鍵が(n,e)です. 署名鍵中のpとqの代わりにnとすると鍵の対称性が言えて, 鍵を交換するという説明になります. 復号鍵や署名鍵にpとqを含める場合には, 鍵を逆さにしてはいけません.

あとRSAなんかでもそうですがメッセージMにそのまま署名を付けてしまうと, まさに選択的暗号文攻撃に弱いという性質の所為で, 選択文書攻撃の下, 任意のメッセージに署名が付けられます.

たとえば, mに署名を付けたい敵は, rをランダムに選んで, 署名者に m r^e を送ります. すると署名者は, m^d rを署名として出力します. このとき, 敵は r を知っているので, mに対する署名 m^d を取り出せます. なので選択的暗号文攻撃を出すとするならば, ハッシュ関数の話は必須です.

公開鍵暗号方式と電子署名 - 狐と学ぶ空想猫力学入門

秘密鍵Aを持つ人のみが暗号化できる性質を使って信憑性を担保する
秘密鍵Aを持つ人のみが作れる情報を使って信憑性を担保する, という言い方が正しいんです. 細かいですが, 復号化とは言わずに復号と言います. 署名の場合については鍵の名前で暗号の鍵との混同が起こりやすいので, 署名鍵/検証鍵という言い方が (俺の) 推奨です.

公開鍵暗号アルゴリズムに必要な条件は

  1. 鍵Aで生成した暗号文は鍵Bで復号化できる
  2. 鍵Bが無い場合には、鍵Aで生成した暗号文の復号化は困難である

の2つ。この前提で鍵Aを公開鍵、鍵Bを秘密鍵にする。
一方、電子署名アルゴリズムに必要な条件は

  1. 鍵Aで生成した暗号文は鍵Bで検証できる
  2. Aが無い場合には、Aで生成した暗号文と同じ文を生成することは困難である

の2つ。この前提で鍵Aを秘密鍵、鍵Bを公開鍵にする。
これらをまとめると

  • 公開鍵暗号方式
    • 秘密鍵Bを持つ人のみが復号化できる性質を使って秘匿通信を行う
  • 電子署名
    • 秘密鍵Aを持つ人のみが暗号化できる性質を使って信憑性を担保する

んで、RSA は両方の条件も満たしてるんで公開鍵暗号にも電子署名としても使えるってことですよね。ってか電子署名に【鍵】って名称を使うことがそもそもの誤解を招く原因になっている気がするなぁ。RSA が両方に使えるっていう歴史的背景も誤解を招いているような気がするし……。

本当にすみません。ってか携帯からのポストした直後に思い出した条件でした。許して(；´Д｀)

追記

Aが無い場合には、Aで生成した暗号文と同じ文を生成することは困難である

じゃなかった。

Aが無い場合には、Bで検証し正当と評価される文を生成することは困難である

が正解。のはず。