暗号化の方式その１：共有鍵暗号
共有鍵暗号の定義は「メッセージの送信者と受信者が一組の鍵を共有しており、それを用いて平文を暗号化、複合化する方法。」である。言葉が固いが早い話、いままで説明した暗号の例はすべて共有鍵暗号である。暗号化に使われるのと同じ鍵を用いて復号化することを前提としているからだ。またこの方法は通信する両者が同じ鍵を使用するので「対称暗号」とも呼ばれる。
共有鍵暗号には大変たくさんの種類がある（らしい）がその中で有名なものについて簡単に書いておく。
(1)DES
ある男はこれを「デス」と発音した。本当のところどう発音するべきなのかは知らないが。。DESとはData Encryption Standardの略である。５６ビットの鍵を使用する。１９７７年にアメリカの連邦規格に採用され、１９８１年にはANSI標準となった。このことからもわかるとおり、大変有名な暗号化方式で、その破り方についても多くの研究がなされている。
某所で聞いた話では某電気会社は国内の暗号化の学会でワークステーションを数十台使用し、数十日でDESを破ることに成功したという。このことは、一見暗号などは我々と関係ない世界のように思えて、各メーカーは異常な熱意をもってその技術に取り組んでいることを示すものである。この話を聞いたのは１９９２年のことだ。その時代高価なワークステーションを数十台、数十日その目的のためだけにしばりつけておく、というのはパソコン一台購入してもらうのに四苦八苦していた私からすると夢のような話に思えたものである。
本書には「DESを数時間で破ることのできるコンピュータはたくさん存在しているだろう。しかしその所有者は決してそれを認めない」と何度も繰り返し書いてある。暗号というのはおもしろいもので、解読ができた、といってもその事を誇らしげに発表するよりはだまっておいた方がはるかにメリットが大きいものである。たとえばこんな話がある。
第２次大戦中にドイツの暗号を完全に解読していた英国が、それによって知り得た情報をソ連に流すべきか、流さないべきか苦悩した。情報を流せば、その時点では連合国側（ソ連だって連合国だ）の損害を少なくすることができるがドイツ側に暗号を解読していることを知られてしまうかもしれない。そのことに気がついたドイツが暗号を変更すれば長い目で見て連合国の損害はより増大する。。かのごとく暗号のお話はどうにもこうにもややこしい。
暗号の内容は秘密。暗号が解読できた、ということも秘密。暗号が使われていることも秘密。秘密だらけでこの業界で働いているとだんだん性格がおかしくなっていくのではなかろうか。実際某電気メーカーの人（さっきのメーカーとは別の会社）から「暗号の話についてはそれだけをやっている部署が、お客さんとひっそりと、暗—い雰囲気で打ち合わせをしていて、どんなことをしているか全く知りません」と言っていたが。
話がだんだんそれていく。説明を続けよう。
(2)トリプルDES
トリプルDESはDESのアルゴリズムを異なる２つの鍵で３回実行することにより、鍵の長さを２倍（１１２ビット）にする方法である。DESの最大の欠点、と目されているものは鍵の長さが短いことだから、このような改良方法が使用されるのだろう。
本書によれば現在金融機関ではこの方式が用いられているとのこと。
(3)RC2,RC4
Rivest Code #2と#4。後で説明する公開鍵暗号で有名なRSA Data Security社が特許を持つ占有の暗号アルゴリズム。鍵長は１ビットから１０２４ビットまで使用できる。
(4)IDEA
International Data Encryption Algorithmの略。１２８ビットの鍵を使用する暗号で１９９０年に公開された。鍵長が長いので総当たり攻撃はまず不可能。後で暗号化プログラムの例としてとりあげるPGP(Pretty Good Privacy)で使われている方式でもある。
(5)スキップジャック
米国の秘密に包まれた謎の組織（たぶん悪の秘密結社ではないと思うが）国家安全保障局（NSA）開発の非公開アルゴリズム。米国で論議を呼んでいるクリッパーチップの中核をなす。８０ビットの鍵を使用しているので総当たり攻撃で破ることはまず不可能。ただしアルゴリズムが非公開であるから、NSAだけが知っている裏口があるのではないか、という疑問が根強く残るかもしれない。-これは私が勝手に考えたことだ。本書の記述は以下の通りである「スキップジャックは安全かもしれないが、クリッパーチップはそうではない。」
クリッパーチップに関して言えば米国政府がすべての鍵を保持しており、他の誰が盗聴できなくても米国政府だけは盗聴できるという仕組みになっている。（もちろん裁判所から盗聴許可を得た後での話であるが）このことからスキップジャック暗号方式と言うよりはクリッパーチップに関しては様々な論議の的になっている。
かくの通り共有鍵暗号にはいろいろな方式がある。そのアルゴリズムには強いもの（簡単には解読されないもの）もあれば、弱いもの（簡単に解読されてしまうもの）もあるがどんなアルゴリズムを使っても共通の問題点がある。それは共有鍵暗号が鍵を「共有」することから発生するものだ。
暗号化する側と復号する側で同じ鍵を使用するのはいいのだが、その鍵をどうやって配付すればいいのか？その鍵は暗号化を行うための鍵なのだから、その鍵自体の配付にその鍵を使うことはできない。平文で送ってしまえば、その後の暗号化文を盗聴してくれ、と言っているようなもんだ。となると鍵配付用の鍵が必要な気になり、ふと考えるとその鍵の配付はどうすればいいんだ、、、、と話は延々と続いてしまう。
交信するのが２人の間だけであれば話はまだ単純だが、交信するネットワークに参加する人間が増えれば増えるほど鍵の数も増える。（異なる相手には異なる鍵が必要であるから）これは単なる順列組み合わせの公式だがｎ人の人間が共有鍵暗号を使用して安全に交信しようとすると、n×(n-1)/2の鍵が必要となる。それだけの鍵をどうやって配付し、管理すればいいのだろうか。
この問題を解決する一つの方法が、鍵配付局の設置である。通信ネットワークに参加する人間は、誰かと話をしたいときに、鍵配付局に「私はだれだれと話がしたい」と連絡する。すると、鍵配付局はその会話用にサイコロをふって鍵を生成する。（その会話の間だけに使用される鍵なので、セッション鍵と呼ぶ）さて、このセッション鍵を平文で送ることはできないから、参加する人間はすべからく自分の鍵を鍵配付局に登録しておく必要がある。鍵配付局はそのセッション鍵配付用の鍵（ああ、ややこしい）を使用して暗号化された鍵を私と、通信をしたい相手に送付するわけだ。
さてこの方法だと鍵配付局はネットワークに参加する人間がｎ人だとすればｎ個のセッション鍵配付用の鍵、及びそのたび毎に生成されるセッション鍵を管理すればいいことになる。前述の方法に比べれば遙かに管理は簡単となる。
この方式の問題点は二つある。一つは鍵配付局自体がSecurity上の弱点となる点である。ここには通信ネットワークに参加する人間のすべての鍵が集まっているのだから、一度ここの情報が外に漏れればすべての通信は盗聴されてしまうことになる。情報の集中管理ということはそれ自体が攻撃する側にとってみれば格好の目標となりうるのだ。
もう一つの問題は、こうした方式は（仮に前述の鍵配付局の防御を向上したとしても）我々一般ユーザーにとってはとうてい利用することが困難と思われる点である。仮に我々が鍵配付局の設置を希望したとしても、誰がそれを設置してそのコストをまかなってくれるのだろう。そしてその鍵設置局が信用できる、ということは誰が保証するのだろう。かりにボランティア精神に富んだ人たちが民間鍵配付局を設置しれくれたとしても、そのボランティアの中に不心得者がまざっていない、とあなたは信用することができるだろうか。
さてこの二つの問題は共有鍵暗号が鍵を共有している限り（これは定義によって必然となる）避けることはできない。しかし１９７０年に「鍵を共有しない」暗号方式が開発された。この結果暗号は政府や大企業の独占できる道具ではなくなったのである。その方式が次に述べる公開鍵暗号である。
前述した共有鍵暗号の欠点は鍵を秘密裏に共有しなくてはならない、という点から来ている。鍵を公開してしまうことができ、なおかつ通信の秘密を保つ方法はないものだろうか？本書にはこの「公開鍵暗号」の開発の歴史が詳細に述べられていて大変Excitingだが、ここではふれない。公開鍵暗号の使われかた、というのは以下の通りである。
通信に参加する人間は数学的に関連した二つの鍵を保有している。一つは秘密鍵と呼ばれ、これはその名の通り秘密にしておく必要がある。また実際自分だけが知っていればいい。共有鍵のように通信相手や鍵配付局にこっそりと教える必要はない。
もう一つの鍵は公開鍵と呼ばれる。これまた読んで字のごとく、こちらの鍵はそこらじゅうに公開してかまわない。本に載せようが、自分の平文電子メールのフッタに記載しておこうが、自分の家の表札に書いておこうが自由である。
私がある人に通信を送りたいとする。そのためにはまず相手の公開鍵を手に入れる必要がある。これは簡単なことだ。相手に「公開鍵を送ってください」と平文で頼めばよい。もともと公開鍵は公開されるためのものだから、盗聴されようが、こちらが電子メールに公開鍵を書いているところを誰かにのぞきみされようがいっこうかまわない。
さて私はこうして手に入れた相手の公開鍵で、私が送りたい通信文を暗号化する。この暗号化された文章を復号化できるのは相手が秘密裏に隠し持っている秘密鍵だけである。相手の公開鍵をそのまま使おうが、逆さまにしてつっこもうが、（データの上でこれがどういう意味を持つか？などと考えないように）何をしようが、元の平文は復号できない。
暗号化された文章を受け取った相手は、自分の秘密鍵を取り出し、私が相手の公開鍵で暗号化した文章を復号化する。めでたしめでたし。
この公開鍵暗号は、先ほどの共有鍵暗号が「対称暗号」と呼ばれるのと反対に「非対称暗号」と呼ばれる。暗号化と復号化に異なる鍵が使用されるからだ。この方式にもいくつかの暗号化の方法が存在する。以下に簡単に説明する。
(1)Diffie-Hellman
このシステムに基づく会話は次のように行われる。会話に参加する両者がまずそれぞれ秘密鍵を作成する。次にこの秘密鍵に基づいた情報を交換することにより、２人はセッション鍵という第３の鍵を導出する。このセッション鍵を使用して両者はその後交換するメッセージを暗号化する。このメッセージの暗号化にはセッション鍵を共有鍵とした共有鍵方式-例えばDES-を用いればよい。とは言われてもなんのことかわからん、と思う人は以下の例を見て欲しい。彼らが目的としているのは、共有鍵暗号に使用する鍵を、どうやったら回線を盗聴している第３者に知られずに共用することができるか？という点にある。
(1)まずアリスとボブは事前に二つの数字、α＝５，ｑ＝５６３を決めておく。この数字は公開してもかまわない。
(2)次に各自が秘密の数を秘密裏に選定する。アリスはXa=9を秘密の数として選定する。次にYa=(α＾Xa)mod qという計算式で定義される値Ya=78をボブに送る。
(3)一方ボブは、Xb = 14を秘密の数として選定する。そしてYb = (α＾Xb)mod qで計算できる数Yb=534をアリスに送る。（回線を盗聴している第３者はこれで、α、ｑ、Ya,Ybを手に入れたことになる）
(4)さてアリスとボブは手に入った数Ya,Ybと公開されているｑ、それに自分が隠し持っているXa,Xbを使ってセッション用の鍵を計算する。アリスはセッション鍵Ｋ＝Yb＾Xa mod q＝１１７と計算し、ボブはＫ＝Ya＾Xb mod q＝１１７と計算する。これで同じ値K=117を得ることができた。以後はこの値をセッション用の「共有された」鍵として使い、メッセージを任意の共有鍵方式を使って暗号化すればよい。
さてここで律儀に回線を盗聴している盗聴者である。彼はα、ｑ、YaそれにYbの値を手に入れている。しかしXa,Xbは知らないので、アリスとボブと同じ関数を使ってセッション鍵Ｋを計算することはできない。先ほどの説明中にあったとおり、Ya,Ybはα、ｑ、Xa,Xbから計算される値であるから、がんばればYa,Yb,α、ｑからXa,Xbを逆に計算することができそうである。
たとえばXaを計算しようと思えば「５(=α）をXa乗して、563(=q)でわったときに、あまりが78(=Yb)になるようなXaを求める」とういう問題を解くことになる。しかしこれは大変難しい。従ってこの暗号は安全である。（ことになっている。私はただ本書に書いてある内容を信じるしかないのだが）
（２）RSA
RSAはいつでも取得できる公開鍵を利用して情報を暗号化する。この公開鍵で暗号化された情報を復号化することができるのは、この公開鍵に対応する秘密鍵だけである。この方法では、Diffie-Hellmanのように通信開始時にお互いが交信を行い、セッション鍵を生成するといった必要がない。
RSAが具体的にどう動くかについて、以下に例を示してみる。ひとつだけ説明の前に断っておくが、後述するようにRSAは「大きな数を素因数分解」するのが難しい、という事実に依存した暗号化方法だ。従って本来ならば「大きな数」を例に使うべきなのだろうが、そうするとタイプするほうも何度も長い数列を書かねばならんし、読む方だって数十桁の数を何度もみるだけでもうんざりするだろう。
従って以下の説明では「本当に暗号化するときは絶対こんな小さな数は使ってはいけない」とクレームがつきそうな小さな数を使って説明を行う。
先ほどの例と同じく、ボブがアリスに暗号文を送ることを考える。そのために、まずアリスは自分の秘密鍵と公開鍵を設定する必要がある。
その１ アリスの公開鍵、秘密鍵設定
（１）アリスは二つの素数を適当に選ぶ。ここではp=5,q=11を選んだとする。（この二つは自分と１以外に割り切れる数を持たないから、確かに素数だ）
（２）選んだ二つの数字をかけ算した結果、n=p×ｑ＝５５を計算する。これは公開鍵の一部になる。
（３）次に(p-1)×(q-1)＝４×１０＝４０とお互いに素になる（つまり１以外に公約数を持たない）数を適当に選定する。ここではe=7を選ぶ。
このe=7と(2)で計算したn=55がアリスの公開鍵となる。
（４）次に秘密鍵を計算する。ｄ×e= 1 mod(p-1)(q-1)となるｄ、つまり(p-1)(q-1)で、d×eを割ったときに余りが１となるようなｄを選ぶ。(p-1)(q-1)は４０であり、eは７だ。そこからうんうんうなって,d=23という数字をひねりだす。d×e=23×7=161であり、確かに４０で割れば余りは１だ。
ここで計算された、dと(2)で計算したnがアリスの秘密鍵となる。（nは公開されているから秘密でもなんでもないが、この値は後で復号化する際に必要となる）
その２ ボブの暗号化と、アリスの復号化
(1)さてボブがアリスに、Ｍ＝"2"という数字を暗号化して送信しようと決心する。（なんで2なんだ、と聞かないように。単に例としてあげただけだ）暗号化の式は以下の通りだ。以下の式で、eとnはアリスの公開鍵だから、値を得るのは簡単である。
Ｃ（暗号化メッセージ）＝M^e mod n = 2^7 mod 55 = 128 mod 55 = 18 (128を55で割れば、商が２，あまりが１８だ）
ということで、暗号化メッセージであるところの１８が得られたので、ボブはこれをアリスに送信する。
(2)ボブから１８，というメッセージを受け取ったアリスは以下の式で復号化を行う。下の式で、dとnはアリスが大切に隠し持っている秘密鍵だ。
Ｍ（メッセージ）＝Ｃ^d mod n = 18^23 mod 55 = 2
となりめでたくボブがもともと送りたかったメッセージ”２”を得ることができた。以上がRSAで使われている暗号化の方法である。
（３）Merkle-Hellman
Merkle-Hellmanはナップサック問題と呼ばれる数学のゲームに基づいている。ナップサック問題とは「重さの異なるいくつかの品物が与えられたとき、特定の重さになるようにナップサックに品物を詰め込むことができるか」という問題である。この暗号は長年にわたり解析が行われ致命的な結果がみつかり実際には使用されなくなってしまった。ここでは記述しないが本書にはその経緯が詳しく記載されておりこれまた大変Excitingだ。
さてこのように見てくると、これらの方式で公開される鍵（あるいはデータ）というのは、いずれも通信に参加する各自が持っている秘密鍵を含んだ計算式から導かれることが分かる。（当たり前の話だが、全く関係ない数を公開鍵と秘密鍵に選んだところで、なんともすることができない）従って公開鍵暗号が「強い暗号」であるためには、秘密鍵を利用して公開鍵を計算することは可能でもその逆が大変難しくなくてはならない。
Diffie-Hellmanでは,この「暗号の強さ」を達成するため、本書によれば「mod qの離散対数をとることが困難であること」という性質を利用しているそうだ。（これが何を意味するか？と私に聞かないように）
RSAでは二つの素数からその積を計算することは容易だが（これは私でもできる）その積から元の値を素因数分解することが困難である、という性質を利用している。もっともこの場合に「困難である」のは「大きな値」に対して、ということなのだが。具体的に先ほどのRSAによる暗号化の例をとって、正面から公開鍵暗号の解読を行うにはどうすればいいか。またそれがどの程度難しいかをみてみよう。
私が先ほどのアリスとボブの間の会話を盗聴しようとする。アリスは「あたしの公開鍵はn=55とe=7よ」と吹聴して歩き回っている。さてここからアリスの秘密鍵を類推しようとする。
公開鍵のうちnに関して言えば、二つの素数の積であることがわかっている。n=55を素因数分解するには、55=11×5のパターンしかあり得ない。こんなのは中学校の数学の問題だ。さて、e=7と分かっているから、アリスが秘密鍵を計算する公式にあてはめて、
ｄ×7 = 1 mod (11-1)(5-1)= 1 mod 40 、、と計算していくと、アリスと同じような過程を経て簡単にｄ＝23が得られてしまう。一旦d=23が得られれば私は自由にアリスとボブのやりとりと盗聴できるわけだ。
こう書いてくると、「なんだ、RSAは簡単に破れるじゃないか」と思えてしまう。しかしながら実際の世の中でRSAが広く使用されているのにはちゃんとわけがある。今私が簡単に秘密鍵を計算できたのは、公開鍵のn=55を素因数分解できたからだ。ところがこのｎが大きくなると話は変わってくる。桁数が大きくなるにつれて、素因数分解がどのように困難になるか、という問題は本書に詳しく書いてあるからふれない（だいたい理解ができない）その代わりに具体例として、RSAが１９７７年８月に「破るのに数百万年かかる新しい暗号」と題されてScientific American誌に発表されたときに使用された公開鍵を示しておこう。ちなみに公開鍵のかたわれは、e = 9007である。こちらは（たかだか）４桁だが、ｎのほうは１２９桁(429bits)もある。
n=114,381,625,757,888,867,669,235,779,976,146,612,020,218,296,721,242,362,562,561,842,935,706,935,245,733,897,830,597,123,563,958,705,058,989,075,147,599,290,026,879,543,541
この値は1993年に世界中の1,600台に及ぶコンピュータで８ヶ月の時間を費やした努力の後に素因数分解された。当初上記の問題が発表されたとき、問題の作成者は解読に必要な時間を「４京年」と見ていたのが、１７年後に解読されてしまったのである。これはコンピュータの処理速度と素因数分解のアルゴリズムの進歩が問題作成者の予想を上回っていたことを物語るものだ。従って429bitsの鍵長さでは既に安全ではない。（もっとも用途によるだろうが。誰が私が送ったメールをそんな労力をかけて解読しようとするだろう）実際本書ではRSAでは1,024bit の公開鍵を使用することが推奨されている。1,024bitのｎとは、WindowsNT4.0に付属してくる電卓プログラムで計算しようとすると「答えが大きすぎます。」というメッセージがでてくるくらい大きな値だ。しかしこの鍵長さがいつまで安全かは時間だけが（その本質がなんであれ）答えを出すことが出きる問題だ。
以上が公開鍵暗号に関する概略の説明である。次に公開鍵暗号の重要なアプリケーションの一つ、電子署名について書いてみよう。
注釈