題名:暗号について

五郎の入り口に戻る

日付:1999/3/25

 

この文章について

暗号化

暗号解読

共有鍵暗号

共有鍵暗号の問題点

公開鍵暗号

電子署名

電子署名の方法

実例:PGP

電子すかしの目的について

電子すかしの具体的な方法 

電子透かしに要求される性質

電子透かしの関連技術・応用

終わりに

参考文献


この文章について

この文章はO'Reilly社発行、Simson Garfinkel著、山本和彦監訳、株式会社ユニテック訳の「PGP-暗号メールと電子署名」をベースに、インターネット上のホームページから得た情報、及び私が見聞きしたあやしげな話を使って、暗号化、電子署名、電子透かしの方法と簡単な理屈についてまとめたものである。

この本-「PGP−暗号メールと電子署名」だが-は結構読みやすく、かつ興味深いエピソードもたくさんのっているから是非本書を読むことを勧めるが、時としてはこの厚い本を全部読んでいる暇などない、ということもあるかもしれない。おまけに私自身について言えば、とても物事を忘れやすいたちだから今まで何度暗号について「さらりと勉強」したか覚えていないほどだが、そのたびにきれいに忘れてしまう。そのたびに分厚い本をめくる、ということはいいかげんに終わりにしたいものだ。

この文章はそれらの問題に対処するために書いたものである。従って暗号に関するキーワードは(少なくとも私が目にできて、かつなんとなく理解できた範囲では)拾ったつもりだ。これだけ書いても3日たてば私は「公開鍵暗号って何のことだっけ」と考えているかもしれないが、そのときはこの文章を読めばさすがの私も「ああ、なるほど」と思い出すに違いない。

加えてもう一つ理由がある。

私が今働いている会社は「コンピュータに近いところの設計」が売り物のはずだ。(少なくとも私はそう聞いて入社した)実際にはこれは単なる妄想というか大嘘なのだが、世の中に願望が現実と見えてしまう人は私が思っているよりもたくさんいるのである。そしてその方針に従えば「社員たるものすべからく「コンピュータに近いところ」の分野の自己啓発にいそしむべきだ」ということになるのである。

実際この「やたらと自己啓発を奨励する」のは人材派遣会社に共通する特徴である。(今給料をもらっている会社は自分で人材派遣会社だとはかたくなに認めようとしないが、実体はそうだ)早い話自分の会社では何も教育をするわけにはいかないので、(客先で使われている身で、研修などにいけるわけがない)ほかの人材派遣会社と差別化をはかろうと思えばいきおい「自己啓発」に頼らざるを得ないわけだ。

さて、私の上司は社の方針に従って1999年3月末までに何か本を読んでマニュアルをまとめることを命じた。最初に渡された本は「オンライントランザクション入門」という本だが、この本は訳文がひどくとても読めたものではない。おまけに内容も支離滅裂でおよそ役に立ちそうにない。

そうはいっても、一応私も給料をもらっている身分だ。わがままをいわずにその本の要約版を少しは作ったのである。そこにある日とんでもない悲劇がやってくる。Windowsの操作になれていない私はちょと馬鹿なことをやってファイルを全部ふっとばしてしまったのだ。書きかけの原稿はどこかに行ったしそれとともに私のやる気もどこかへ消え失せてしまった。

そこに目に付いたのがこの本である。訳は見事だし、内容も100倍もまともだ。おまけに暗号化の必要性はこれから高まることはあっても減ることはあるまい。となればちょっとだけ矛先を替えてもまあ問題はなさそうである。そう考えた私はこの「暗号化」についてまとめることとしたのである。内容に興味がもてて、少なくとも私にとっては役に立ち、しかも会社の無意味な「指導」に対してなんらかの反論材料となるのであれば、まあやる気もでるというものである。そしてたぶんこの文章はいつの日か私のホームぺージにのることになるのだろう。(実際私はこの文章をMicrosoft Wordを使って書いているが文書フォーマットはhtmlなのだ)

内容としては、まず暗号化とは何かから始まって、二つの大きな暗号方式、共有鍵暗号と公開鍵暗号について述べる。次に公開鍵暗号のアプリケーションの一つである電子署名についてふれて、それらがどのように使われるか、という事を示すためにフリーの暗号化プログラム、PGPについて簡単に述べる。最後にこれは本書の範囲を超えるのだが、インターネット上であさった情報を元に暗号化と関係の深い分野「電子透かし」について述べる。

文中「本書」と書いてあればそれは「PGP-暗号メールと電子署名」のことである。またこの文章は基本的に私が理解できた内容だけを勝手に構成したものだから書いてある内容に嘘があればそれは基本的に私のせいだ。たぶんその可能性のほうが本書に誤りがある可能性より遙かに高いだろう。

 

暗号化

最初の一歩とは「暗号化」とは何か?である。実のところ「暗号」の正確な定義、というのを私は知らないが、説明の都合上以下の定義を用いることにする。すなわち

「平文(暗号化されていない通常の文。この文章は平文だ)を何らかの規則に従って変換し、そのままでは第3者にとって何を意味しているかわからないデータに変換すること。また何らかの規則(最初の規則と同一でなくてもよい)によって元の平文に復元できること」

こうした言葉だけではわけがわからないから、一番単純でわかりやすい換字暗号を例にとって説明してみよう。

 

換字暗号とは、元の文字を一定の規則に従って別の記号に置き換える暗号である。よく言われた間違った伝説に、2001年宇宙の旅に出てくる"HAL"というコンピュータの名前は"IBM"を一字づつずらしたものだ、というやつがある。(I→H, B→A、M→L)これも一種の換字暗号といえなくもない。

また定義によれば一定の規則に従って変換さえすればよいので暗号化された結果は別に文字である必要はない。確かシャーロックホームズの作品の中には「踊る人形が並んだ絵」が暗号であった、というやつがあった気がする。同じく小説の中の暗号としては「黄金虫」というのを幼少の頃に読んだ覚えがある。この小説にでてくる暗号化された結果はアルファベットあり、数字有り、記号有りでわけがわからない。以下に示すのがその暗号文だ。(インターネット上で手に入れた暗号文だから、フォントの都合で原文と比べると形が違って見える文字があると思う。まあ説明には支障がないので、気にしないで欲しい)

 

53++!305))6*;4826)4+.)4+);806*;48!8`60))85;]8*:+*8!83(88)5*!;

46(;88*96*?;8)*+(;485);5*!2:*+(;4956*2(5*-4)8`8*; 4069285);)6

!8)4++;1(+9;48081;8:8+1;48!85;4)485!528806*81(+9;48;(88;4(+?3

4;48)4+;161;:188;+?;

 

このように通常の文字を数字に置き換えてもいいし、見たこともない記号に置き換えたっていいし、その気になれば暗号化された結果を画面上のノイズとしたっていいわけだ。しかし私としては文字を書く方が踊る人形やノイズを書くよりも楽なので、暗号化した文章は文字に変換されることにしておく。

 

さてこの換字暗号は簡単に作れるが、暗号化の方法によっては簡単に解読することができる。前述した「黄金虫」の中での解読方法は以下の通りである。まず前掲の暗号文をじっと見る。

わけのわからない記号の羅列ではあるが、記号ごとの出現頻度をみると結構差があることがわかる。”8”が33回現れていて、次の”;”は26回だ。元となった平文が英語だとすると、英語で一番頻繁に現れる文字は"e"ということになっているらしい。だからとりあえず一番頻度の高い”8”を"e"のことだ、としておく。

次に先ほど解読した"e"を含む一定の文字パターンが何度か現れていないかどうかチェックする。すると終わりが"e"で3文字のパターン";48"が何度かでてくる。終わりが"e"で頻繁に現れる3文字の英単語というと冠詞の"the"が思い浮かぶ。となるとこの3文字の記号はそれぞれ"t","h","e"に対応しているに違いない。こうして3文字が解読できると次にはそれを手がかりとして、、(当時掛け値無しの少年だった私はこうした解読の筋道をどきどきしながら読んだものだ)

このようにしてこの暗号は解読されてしまう。さてこの暗号化の方法にはどのような欠点があったのだろうか(暗号というのは本来解読方法を知らない第3者には読まれないために使われるものである。あっさりと解読されてしまった、というからにはこの暗号化方法には何かの欠点があるはずだ)

 

この解読の方法を見てもわかるとおり、一番の欠点は平文全体にわたって、文字を置き換える方法が同一である、という点である。文章の頭のほうに出てくる"the"も、後ろのほうに出てくる"the"も同じ規則に従って変換される。だから、文章が長くなると規則的なパターンが何度も現れて見破られることになる。

さてずーっと一定のパターンで変換しているから問題が起こるのであるから、パターンを文字毎に変化させればいい、という考え方が生まれる。次のような換字規則はどうだろうか。

最初の文字は1字ずらす。次の文字は3字ずらす。その次は5文字、その次は0文字。。。

つまり平文の一文字一文字に対して何文字ずらすか、という数字列を指定するわけである。この方法によって暗号化された文章は暗号化されたときに使用された数字列を知っていれば元の平文に戻すことができる。このような数字列は暗号化及び復号化に使われるものだから「鍵」と呼ばれる。

さて、こんどの方法はうまく行くように思われる。実際唯一「解読不能」と証明されている暗号化の方法は、この数字列が絶対に循環しない、つまり延々と長く続く、繰り返しのないランダムな数字列を用いた場合の換字暗号なのだ。本書によればホワイトハウスとクレムリンの間のホットラインはこの方法で暗号化されているという噂があるらしい。この本を読むまで気がつかなかったが、確かにホワイトハウスとクレムリンの間の会話を盗聴したい、と思う人間はたくさんいることだろう。

なーんだ。絶対に解読不可能な暗号方法があるなら、それを使えばいいじゃないか。Problem Solved-とはならない。この方法にはいくつもの欠点がある。第一に循環しないランダムな数字列-乱数-を生成する、ということはそれだけで一苦労だ。私が知っている限りでは、乱数の発生というのは場合によっては学士論文や修士論文のテーマにも選ばれるほど難しいことなのである。そしてコピュータの上で自動発生できるのは基本的にどこかで循環している疑似乱数である。

仮に「疑似乱数でいいや」と割り切ったとしても暗号の送り側と受け取り側で同じ数字列(鍵)を共有しなくてはならない、という問題につきあたる。おまけにこの数字列は第3者にもれてはまずいのだ。できれば金庫の奥底深く隠しておきたいが、たとえばクレムリンとホワイトハウスの間の暗号に使用しようとすれば、そういう訳にもいかない。かといってまさかその数字列を電話で伝えるわけにもいかない。(それこそ誰かに盗聴されてしまう)これまた本書によれば、この鍵を共有化するために、政府の職員が手錠でつながれたアタッシュケースをもってアメリカとモスクワの間を往復していると言う。無限に長い数字列を共有するためには、無限回数の政府職員の往復が必要なのだ。

地球存亡の鍵を握るようなホットラインの暗号であれば確かにそうした鍵共有にかかるコストを許容することもできるだろう。しかし我々一般庶民にとってはそんなことはどう考えても可能ではない。ではどうすればいいだろう?すべからく現実世界に生きるものは現実と妥協することを覚えなくてはならない。現実的な妥協というのは、鍵の長さを或程度の有限数に制限することである。一番短い鍵は長さ1で、これは最初に例としてあげた"IBM→HAL"のような場合だ。これは簡単にとける。鍵の長さが2になれば解読はそれよりは難しくなるが、一定以上の長さの暗号文を見ていれば解読が可能である。このように鍵の長さと暗号の強度(第3者による解読のしにくさ)はだいたい正の相関関係にある。(本書には「話はそんなに単純じゃねえ」と書いてあるが)

 

さて鍵の長さ、というのは別になんであらわしてもいいのだが、なぜかビット数で表されることが多いようだ。例えばキャッシュカードの暗証番号は4桁の数字であるから作成可能な鍵の種類は10,000.ビット数で表すと14ビット(本当は2の14乗は16,384だが)である。ではこの4桁の数字(鍵となるわけだが)を使って、換字暗号をつくることを実際にやってみよう。

 

説明を簡単にするために、元となる平文は英語、と限定してしまう。ここでは私の年代前後の方には一番なじみが深いであろう英文であるこの文を用いる

 

平文:"this is a pen"

 

つぎに4桁の数字を鍵として選択する。ここで私は自分のキャッシュカードの暗証番号を書いてしまうほど間抜けではない(実際には一度書いてしまってからこうやってなおしているわけだが)全く不本意なことだが、私はNTT-Softwareという会社から給料をもらうかわりに労働力を提供している。そしてその際、一律にふられる「社員番号」というのが4桁の数字だからこれを使おう。この番号が世間に流通したところで私はいたくもかゆくもない。

鍵:"1982"

さて次にどのような規則で「文字をずらす」か定義しておく。そのために次のような仮想的文字列を定義する。

a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,0,1,2,3,4,5,6,7,8,9,(space)

最後の(space)は空白である。暗号化の際には鍵で指定されるぶんだけ、文字を右にずらす。(space)をこえてはみ出すようだったら、aに戻る。復号化の場合のずらしかたはその反対だ。

 

さて平文の一字一字に鍵の数字をあてはめると

次に先ほどの規則に従ってそれぞれの文字をずらしていく("t"は一文字ずらして"u"。次の"h"は9文字ずらして"q",,)とできあがる暗号文は以下の通りだ。

 

"uqquar0bbixgo"

 

なんだか立派な暗号のような気がするでしょ?この文字列を見ると、先ほどの「黄金虫」的な暗号解読方法が通じないことが見て取れる。2文字目の"h"と3文字目の"i"は両方とも"q"に置き換えられている。だから例えば「"q"がたくさんあるから、"q"は"e"のことだ!」などと叫ぶわけにはいかない。

さて私などがこの文字列を見るとそれだけで「ああ。とても解読なんかできやしない。私は無敵の暗号化プログラムを開発したのだー」と叫ぶところだが、世の中それほど簡単にできてはいない。実際本書によればこの暗号などは何の苦もなく解読されてしまうという。

 

 

暗号解読

先ほど私が作成した異様な暗号化された文字列をみて、眉一つ動かさずに解読してしまう人がおそらく世界中に万で数える規模で存在する、という事実は大変興味深いものだ。私が顔を知っている人間の99%はあの文字列をみて投げ出してしまうほうに私は100円をかける。しかし世の中すべからくその道のプロをあなどってはならない。ふつうの人間には何も意味をもたないか、あるいは不可能と思えることを易々と成し遂げたり、すごい意味を発見したりするのがその道の専門家(プロないしはアマチュア)というものだ。

 

さてこれから「解読されにくい暗号」ということについて書くわけだから、その前に「暗号解読とはどうやるか」ということについてざっと書いてみる。暗号解読にはいくつかの方法がある。

 

(1)総当たり攻撃

これは鍵がわからない場合に、とにかく可能性のある鍵を全部あたってみる方法である。ほとんどの鍵は失敗するが、とにかく一つだけ成功する鍵をみつければいいのだ。

先ほど作った暗号を例にとってこの方法を試してみた。4桁の鍵をすべて使って復号化を試み、10000個の平文を生成させ、そのなかから正解を拾い出す、という構想の元にプログラムを書く。私が作るプログラムだから実行速度などは全く無視してとにかくちゃんと動くことを重視して書いたコードである。だから最適化されているとはとてもいえないが、私の机の上にのっているPC(Pentium II @ 400MHz)で計算させて答えを得るまでに1秒もかからなかった。(正確にはコンマ何秒だと思うが、短すぎて測定ができない)

結果を見てみると、確かに鍵が1982のところでthis is a penなる平文が再現されている。他の文はすべて意味をなさない。(ちなみに鍵1981に対する復号化文は"thit isaa pfn"である。)しかし目的は一つの平文を見つけることだからこれで全く問題はない。

さて総当たり攻撃は、暗号の構造がわかっていて、かつ試すべき鍵のビット数がわかっていれば、理論的にはうまく働くはずだ。しかし実際の世界を考えると、この攻撃に対抗する単純にして効果的な方法は「鍵を長くする」ことである。鍵の長さが無限長になれば解読は不可能になるが、そこまでやらなくても十分に鍵を長くするだけで総当たりに必要な計算処理量は飛躍的に増大し、実質的に解読は不可能になる。

本書に載っている例をあげてみよう。IDEAとよばれる暗号化アルゴリズムがある。以下に示すのはIDEAを使って平文"this is a pen"を暗号化した例だ。

 

pgAAACbM4s8jRqCOh0Ea0AIf4OU76wQaALnLDkwW59LE300jUEIZ0LIH6w===i/eW

先ほど私が安直につくった換字暗号よりもはるかに暗号らしいでしょ。さてこのアルゴリズムが使っている鍵の長さは128ビットである。従って総当たりで鍵を試すためには2の128乗、つまり3.4×10の38乗の鍵を試す必要がある。これがどの程度大きい値かというと、一秒に10億個の鍵を試すことができるコンピュータが10億台あったとしてもすべての鍵を試すためには10の13乗年、つまり10兆年かかることになる。(これは120億年と推定されている宇宙の年齢の約千倍である。)

仮に宇宙に存在する物質の総質量が宇宙がふたたび収縮に向かうより小さくて、永遠に膨張し続けるとする。閉鎖系のエントロピーは増大し、減少しないと言うのは熱力学のなんとか法則だ。従って何百億年だか何千億年だか何兆年かの後にはエントロピーは極大に達し、(つまり無秩序さが極まってしまい)すべての物質はすべからく存在しなくなる、という話を読んだことがある。その何もない暗黒の空間に計算機の固まりが浮かんでいて(この想定自体矛盾を持っているのだが、まあ妄想だから気にしない)ひたすら一つの暗号鍵をみつけるべく計算をしている。そしていつの日か、"Problem Solved. Original plain text is "this is a pen' "というメッセージを出すのだが、それを見るものなど誰もいない、などというのは鬼気迫る妄想であるが実質的な意味はあまりない。世の中のその道の専門家たちは、私が作れるようなプログラムとは全く次元の異なる暗号解読方法を持っているのだ。

 

(2)既知平文攻撃

これは解読者が平文とそれに対応する暗号化文を持っている場合に使われる手法だ。なんでこんなことが起こるのか、と思われるだろうが、たとえば電子メールを丸ごと暗号化したことを考えて欲しい。それが会社間の挨拶に使われる文章だったら、冒頭の文句は「拝啓、貴社ますますご清栄の事とお喜び申し上げます」とかなんとかいう決まり文句だ。この文句を書いたからといって、本当に文書を送る相手の会社がもうかっているなあ、といって喜んでいる人間などこの世に一人もいるわけがない。だから意味はないのだが、暗号化を考えた場合にはこうした定型文はそれだけで、暗号解読の手がかりとなってしまうのである。

こういうばかげた例でなくても(誰が暗号文に定型の挨拶フレーズをつけようと思うだろうか)ハードディスクのなんとかブロックとか、とにかくこうしたケースは思ったよりも多く起こりうる(らしい)平文と暗号文を両方所持していれば解読はそれだけ容易になる。

 

(3)選択平文攻撃

この攻撃方法は、解読者が暗号化を行っている人間に気づかれずに暗号化をさせられることが前提となる。たとえば、電話で受信したメッセージを暗号化して再送する無線のリンクなどである(と本書には書いてある。また案外簡単に実行できると書いてあるが私にはこれが簡単なことかどうかはわからない)。この例だったらおそらくどっかに電話をかけて、メッセージを告げれば、無線でその暗号化の結果が傍受できる、ということなのだろう。

解読者にとって都合のよい平文を暗号化してくれるのだから(しかも前提により相手はそのことに気がついていない)元の平文と暗号文を比べて解読を行うのは既知平文攻撃よりも容易になる。

 

(4)差分暗号攻撃

これは選択平文攻撃の中の一つの方法である。わずかしか違わない多くのテキストを暗号化し、結果を比較する。例えば私が作った暗号化プログラムであれば、平文の文字を少しずつ入れ替えて結果を比較すれば、容易に1982という鍵を導き出すことができるだろう。(もっともこの方法が最初に私が試みた「総当たり攻撃」よりも効率がいいとは、この例に限って言えば定かではないが)

 

さて前述したように我々の日常生活とは関係ないところで、こうした暗号の世界における攻防というのはなされていて、そこでの技術革新だの発見だのがいつもなされているのである。実際どの方法にどういう特徴があり、それが強いものであるか弱いものであるかなどは私がとうてい理解できるところではないし、この文章を読むことになる人(たぶんそんなに多くないと思うのだが)にとっても同様だろう。

しかしながら私にも暗号化の方法には私でも理解できる大きな二つの区分があることだけは間違いないようだ。次にはその二つの大きな方法、及びそれぞれの利害得失(もちろん私がその言葉を理解できた範囲での話だが)について書いてみよう。

 

次の章 


注釈

願望が現実と見えてしまう人:(トピック一覧)かくいう私もその一人かもしれない。本文に戻る

私が理解できた内容だけ:もうちょっとまともな情報が欲しい、と思った場合は例えば「暗号理解.com」からリンクしているサイトを閲覧するのもいいかもしれない。本文に戻る

 

PGP-暗号メールと電子署名:参考文献一覧)この本の値段は忘れたが、値段だけの価値はあると思う。本文に戻る

 

なじみが深いであろう英文:わかる人にはわかると思うが、私が幼少の頃の超人気番組、「8時だよ全員集合」で荒井ちゅうがやっていたギャグである。私が唯一覚えているのは、何か国際会議のようなセッティングで、日本代表である荒井ちゅうが皆に英語で「日本はいったい何やってんのよ!」ってな感じでせめられている。(攻める側は、この番組にレギュラー出演していたゴールデンハーフなるハーフの女の子たちのグループである。彼女たちはどこへ行ったのだろうか。。)そこで最後に立ち上がった荒井ちゅうが一言この言葉を吐くのである。本文に戻る

労働力を提供している:私は幸せな気持ちと共にこの部分を訂正する。「過去において私はNTT-Softwareに労働力を提供していた」と。我が家はKDDIをマイラインプラスで登録し、頭三文字NTTの企業に一円も支払わなくてすむ生活を夢見ている。本文に戻る

 

暗号化した例:後で説明するPGPの「共有暗号だけを使用モード」で暗号化した。鍵が何かは私にもわからない。PGPにパスフレーズを入力して暗号化したのだが、鍵はPGPが生成したらしい。おまけに同じパスフレーズを入れても同じようには暗号化されない、という念の入れようである。本文に戻る