公開鍵暗号と署名方式の誤り解説

真面目な解説記事を書きました. 詳しくは暗号と署名の話を見てください.

高木浩光@自宅の日記 - 公開鍵暗号方式の誤り解説の氾濫をそろそろどげんかせんとを, すがさん (id:FTTH) にIDコールされたので見た.

そういえば, IPA (情報処理推進機構) の問題でも同じような間違いがありました. 情報処理技術者試験の問題 - 186::Diaryで書いたものを再掲.

問47 公開鍵暗号方式を用いて文書のディジタル署名を行う場合,鍵の関係に関する記述のうち,適切なものはどれか。

  1. ア 暗号化鍵は公開しないが,復号鍵は公開する。
  2. イ 暗号化鍵は公開するが,復号鍵は公開しない。
  3. ウ 暗号化鍵,復号鍵とも公開しない。
  4. エ 暗号化鍵,復号鍵とも公開する。

正解はアです.

追記

一般的に言うと、専門家が非専門家の誤りを指摘するというのはなかなか難しい作業である。非専門家の読者の関心を集めるように書かなければそもそも読まれない。どのような誤解に基づくものかを見いだして指摘する必要がある。「専門家の視点と一般向けの視点は別なのですよ」というありがちな言い訳をされないように注意しなければならない。重箱の隅をつつく揚げ足取りと思われないようにし、過剰な指摘をしないよう注意しないといけない。加えて、感情的に反発されないように配慮しないと書けないと考える人もいるだろう。専門家であるが故に、指摘でミスをすれば職業上の信用を失うことになりかねず、慎重になってしまう。

反省すること頻りです.

追記2

高木さんの指摘について.

原理から学ぶネットワーク・セキュリティ 第3回 公開鍵と秘密鍵を作るアルゴリズム, 波多浩昭 / 日経Linux, 2007年11月27日

デフィーの着想は,鍵を2種類に分けるというものでした(図2)。一つめの鍵は,それまでと同様に大切に扱う鍵で「秘密鍵」といいます。もう一つの鍵は「公開鍵」です。秘密鍵があれば,ある手順により公開鍵を容易に作り出せます。しかし公開鍵から秘密鍵は作り出すことができない,もしくは作り出すのに天文学的な時間が必要となるというものです。

この秘密鍵と公開鍵はペアで不思議な動作をします。(略)今度は秘密鍵で宝箱を閉めてみます。すると,今後はそのペアとなっている公開鍵でなければ箱は開きません。箱を閉めた秘密鍵を使っても箱は開かないのです。不思議な箱と不思議な鍵です。デフィーとヘルマンはこの仕組みで,鍵交換問題をどのように解決したのでしょうか?(略)
(略:186)

明記していない略は高木さんによる.

実はその連載第3回ってDiffie and Hellmanの説明としてはそんなに間違ってないんですよね. 暗号化関数と復号関数が対称という話はDiffieとHellmanが1976年 *1 “New Directions in Cryptography”に書いちゃってるんですね. Diffie and Hellman (IEEE Trans. on IT, 1976) からまず公開鍵暗号系の定義を引くと,

A public key cryptosystem is a pair of families {E_K}_{K∈{K}} and {D_K}_{K∈{K}} of algorithms representing invertible transformations,
E_K:{M}→{M}
D_K:{M}→{M}
on a finite mesage space {M}, such that

  1. for every K∈{K}, E_K is the inverse of D_K,
  2. for every K∈{K} and M∈{M}, the algorithms E_K and D_K are easy to compute,
  3. for almost every K∈{K}, each easily computed algorithm equivalent to D_K is computationally infeasible to derive from E_K,
  4. for every K∈{K}, it is feasible to compute inverse pairs E_K and D_K from K.

この定義では鍵は1つで, 暗号化と復号を関数が担う. なので, 公開鍵 = 暗号化関数, 秘密鍵 = 復号関数 と読むと実は間違っていないと.

しかも, このときの定義だと公開鍵暗号方式は決定性でE_KとD_Kを合成すると恒等写像. 彼らは, 4章で署名と認証方式を扱っていて, そこでは一方向性関数の逆関数の話が出てきます. 実際に引くと以下:

A public key cryptosystem can be used to produce a true one-way authentication system as follows. If user A wishes to send a message M to user B, he &lquot;deciphers&rquo; it in his secret deciphering key and sends D_A(M). When user B receives it, he can read it, and be assured of its authenticity by &lquot;enciphering&rquot; it with user A' s public enciphering key E_A. B also saves D_A(M) as proof that the message came from A. Anyone can check this claim by operating on D_A(M) with the publicly known operation E_A to recover M. Since only A could have generated a message with this property, the solution to the one-way authentication problem would follow immediately from the development of public key cryptosystems.

なので, 原理から学ぶネットワーク・セキュリティ 第3回 公開鍵と秘密鍵を作るアルゴリズム - p.2 公開鍵暗号でなりすましと改ざんを防御の説明もDiffie and Hellmanの枠組みを説明しているところなので, 間違っていないと.

ただ, この素朴な話では他の暗号系を説明出来ないという補足はライターがすべきだと思います.

*1:俺が生まれる6年前