ある平凡助教授の，なんということもない日々 200605

2006 . 04 «
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
» 2006 . 06

長いあいだ関心があったにもかかわらず勉強する機会のなかった雑学のひとつに「暗号理論」がある．ボクが関心をもったきっかけを古い順に挙げてみる:

留学した大学の数学科の科目に cryptography (「暗号理論」と訳せばいいのかな？) があった．「暗号の話だけで数学の一科目として成立するんだろうか？」と，素朴な疑問を持っていた気がする．Cryptographyは---測度と確率とか関数解析とか微分位相幾何学といった数理経済学者としての古典的な一般常識を学ぶのにあまり熱心でなかった自分が---専門の経済理論とは無関係な「雑学」として学びたいと思っていた分野のひとつだった．計算理論などほかの雑学の勉強で手一杯で，着手できなかったけど．
米国から帰国後，暗号は無政府社会の実現と関係があるらしいことを知った． Crypto-anarchy と呼ばれる．
その後再び渡米したときの滞在先だった Caltech の政治学の学部授業で (ボクは参加しなかったけど)，R. Michael Alvarez がインターネットなどによる投票テクノロジーにやけに重点を置いているのを知った．当然，暗号技術の話題もあった．
数学者ジョン・ナッシュ (John Nash; 非協力ゲームのナッシュ均衡で有名) を描いた映画 A Beautiful Mind を見た．ゲーム理論よりも暗号解読の場面の方が多く出て来た．「暗号なんかよりゲーム理論のほうがおもしろいだろ！」と，やや不満に思いつつ見た．
『図解雑学ゲーム理論』 (←おすすめ) を買うために Amazon.co.jp で図解雑学シリーズをチェックしたら，その本の売れ行きがシリーズでトップだった．「現代という時代におけるゲーム理論の重要性を考えれば当然か」と思いつつほかの本も見たら，なぜか『図解雑学暗号理論』もかなり上位にランクされていた．「なんでこんなマニアックで，しかもかなり高度そうな本が？」
さいきん「情報セキュリティー」が流行っているらしい．その産業が「今世紀最大のビジネス」かどうかは知らないが．
さいきん話題の『ダ・ヴィンチ・コード』という映画の「コード」とは暗号のことらしい．

思えば暗号法というのは，よく分かりもせずにだれもが利用だけはしている技術である．(よく分かりもせずに利用している技術というのは多いが，暗号が無形の (?) 技術であるところがなんとなく神秘性を高めている．) 身近な例を挙げれば，skype を通じて女子学生と猥談や次回のエッチの打ち合わせを……いや，共同研究者と研究のアイディアをディスカッションするときにも暗号は使われている．でも，Skype ヘルプに，

「SkypeではRijndaelとも呼ばれるAES (Advanced Encryption Standard)、アメリカ政府機関で機密情報の保持に使用されているアルゴリズムを使っています。Skypeでは256ビットの暗号化、これはつまり合計1.1 x 10⁷⁷の組み合わせがある鍵を使い、個々のSkype通話とインスタントメッセージのデータを積極的に守るため暗号化しています。Skypeでは1024ビットRSAを用いてAESの対称鍵をやり取りします。公開鍵はログイン時にSkypeサーバで1536または2048ビットRSA証書を使い認証されます。」

なんて書いてあっても，「なるほど」と納得できるひとは (おそらく) 少数派だろう．

「雑学」とは言ったが，暗号はボクの専門の社会選択理論とも無関係ではない．社会選択やメカニズム・デザインはルールの設計にかんする学問だ．他の参加者やルールの実行者にいちいち個人情報を知られなければならないようなルールは，望ましくないことが普通だろう．(「知らせなければならない」ではなく「知られなければならない」と書いたのは，中身を知られずに知らせる方法があるため．) 大学キャンパス内の駐車場を申し込むときに，いちいち自分の病名や (ボクは該当しないが) 送り迎えしなければならない隠し子の存在を申告しなければスペースが割り当てられないのはイヤなものだ (怒)！　(クルマを所有する大学職員を貧乏人扱いする必要はない．カネを使えよ！　大学周辺の駐車場の 1.1 倍くらいの値段にすれば，多くの申請者は脱落するはずだ．いや，0.7 倍くらいでもかなり脱落するだろう．オークション方式でもいいかもしれない．)

じっさい以前紹介した Smorodinsky and Tennenholtz (2006) によるメカニズム・デザインのペーパーでも， "zero-knowledge interactive proof systems" (ゼロ知識対話証明システム) などという cryptography の専門用語がさらりと使われていたりする．ちなみに「ゼロ知識対話証明」で解決できそうな問題の例は，社会科学者にとってもとっても興味ぶかいものだろう．いや，ボクだけか？

そんなわけで，とりあえず「サルにもわかる RSA 暗号」を読んでみた．地方大学の助教授でもわかる内容だった．これで長年の恨 (han) をはらすことができて感激だ．ポイントをメモすればこんな感じ:

「共通鍵暗号」のばあい，同じ鍵で暗号化と復号を行う． [追記．大雑把に言えば，暗号化するとき鍵を右に回し，復号するとき同じ鍵を左に回すイメージ．要するに，逆写像が簡単に求められるようになっている．] ある文を相手から伝えてもらうためには，まず鍵を伝えなければはじまらない．「じゃあどうやって鍵を秘密に伝えるの？」というのが問題になるわけだ．
一方，「公開鍵暗号」なら，自分の持つ秘密鍵 B を相手に伝える必要はない．代わりにある公開鍵 A を相手に伝えておく．そして相手に公開鍵 A で暗号化してもらえば，自分は秘密鍵 B で復号できるのだ．公開鍵 A では復号できないので，公開鍵 A は他人に漏れても構わない．
RSA 暗号では，ある 2 つの素数 P, Q の積 PQ を法 (mod) とする世界で，もとの文を公開鍵 A によって暗号化してもらう (積 PQ も相手に伝える)． [追記．暗号化するときに鍵 A を右に回し，複合化するときちがう鍵 B でさらに右に回してもとに戻すイメージ．鍵 A で左回転できたとしてももとの位置には戻らない．要するに，逆写像が簡単には求められないようになっている．] その積 PQ と公開鍵 A から秘密鍵 B を計算して求めるのは理論上可能であり，PQ を素因数分解して P と Q を求めればできる．しかし，ひじょうに大きな数 (といってもたった 129 桁ていどでも) の素因数分解は一般に計算するのが困難である．また，素因数分解を迂回する解法は見つかっていない．つまり公開鍵から秘密鍵を求めるのは事実上不可能という案配だ．

このメモだけ読んでも分からないだろう．ぜひ「サルにもわかる RSA 暗号」を読むといい．ボクはといえば，そのサイトの著者による『図解雑学暗号理論』を買うことにするから．

追記．せっかく「鍵」というアナロジーを使っているのだから，(詩人らしく?) そのアナロジーをさらにおしすすめて「右回転」「左回転」などの概念を導入した説明を追加した．大雑把ながらうまく本質を捉えていると思うがいかがだろうか．