記事リバイバル④(公開キー暗号(神はサイコロ遊びをなさる))

※ リバイバル記事第４弾！！2006年５/４の量子エンタングルメント関係の記事の再掲載です。

先ほど「パズル・パレス(迷宮)(The Puzzle Palace)」という暗号の解読に関わる小説を読み終えたところです。

　これは「ダヴィンチ・コード(The Da Vinci Code)」というベストセラー小説を書いたダン・ブラウン(Dan Brown)の処女作です。

　確かに両方の著書はよく似ています。この著者は小説の中に自然科学とか数学とかを神秘的なテーマとして含ませるのが特徴のようです。

小説「パズル・パレス(迷宮)」の中では暗号特に公開鍵(キー)暗号の話がよく出てきます。

この暗号はアメリカの中央情報局(C.I.A)などが実際に使っているらしく,現状では事実上解読不可能なものですが,もしも後述するような量子コンピュータができたなら解読できるだろうと予測されるものです。

公開キー暗号,特にRSA式公開キー暗号について私が興味を持ったのは,シルヴァーマン(J.H.Silverman)著の「はじめての数論」という整数論の本を,一昨年だったか昨年だったかに読んで,その中に書かれていた内容からそれを知ったのがきっかけでした。

この本は,私がスタッフをやっている「ニフティ・物理フォーラム(@nifty Fphys)」の母胎の「ニフティ・サイエンスフォーラム(nifty-serve FSCI)」の数学会議室で長年の間,"議長＝世話役"をやっておられ,ホームページに移った後もスタッフとして残っておられる「プークさん＝鈴木治郎氏」が翻訳されたものです。

RSA式公開キー暗号は,いわゆる合同式に関する方程式を解くことで解読するものです。そこでまず,合同式というのはどういうものか？ということから説明しましょう。

ａ,ｂを整数の組として,ａ≡ｂ(mod 7)のように書かれた式を合同式といいます。この記号は,"７を法(modulo)としてａはｂと合同である。"と読みます。

そして,ａ≡ｂ(mod 7)は,"ａとｂをそれぞれ７で割ったとき,それらの余りが全く同じである"ことを意味します。例えば,6≡20(mod 7),6≡－1(mod 7),103≡68(mod 7)...ということになります。

言い換えると,ａ≡ｂ(mod 7)というのは,"ａとｂの差:(ａ－ｂ)が７で割り切れるとき,そのときに限ってａとｂは合同である。"という意味ですね。法(modulo)は７とは限らず,一般に,8≡41(mod 3),222≡57(mod 11)などと書けます。

RSA式暗号では,"複雑な合同式ｘ¹³¹≡758(mod 1073)を満たす最小の自然数ｘを求めよ。"というような合同式の方程式を解くことが暗号解読につながります。

この合同式の方程式ｘ¹³¹≡758(mod 1073)をどうやって解くのかについては,話が長くなるので省略しますが,要するに1073をすべて素数の積に素因数分解できればこれを解くことができます。

素因数分解というのは,例えば120＝2×2×2×3×5というように,左辺の120を全てが素数の積に因数分解することを言います。もちろん,素数(prime number)とは１以外で自分自身と１以外に約数を持たない自然数のことです。

1073の場合は,素因数分解が1073=29×37だということは容易にわかるので,その結果としてｘ＝905と計算できるわけです。つまり,905¹³¹≡ 758(mod 1073)という式が成立します。

例えば,ｘ^k ≡ｙ (mod ｍ)という合同式において,予めｋ＝79921,ｍ＝163276821という値を知っていて,右辺のｙとして５つの数のリスト:(145387828,47164891,152020614,27279275,353564912)が暗号として送られてきたとします。

これらの最初の数:ｙ＝145387828についての方程式ｘ⁷⁹⁹²¹ ≡145387828 (mod 163276821)の解ｘを求めるには,ｍがｍ＝163276821＝12553×13007と素因数分解できることがわかる必要があります。

　これがわかっていれば,解読結果として,ｘ＝30182523が得られます。

 そして５つの暗号数ｙについて全て解いて,その結果のｘの値を２桁毎に分けて順に並べます。ｘ＝30182523は,30 18 25 23と並べられます。

　５つの解ｘの全てについて並べたものは次のようになります。

 30 18 25 23 26 29 25 24 19 29 19 24 30 28 25 31 12 22 15

ですね。

　これらの数に,アルファベット(Alphabet)を対応させて当てはめれば,暗号は解読されます。

　一般に,11＝Ａ,12＝Ｂ,13＝Ｃ,．．．．36＝Ｚというように２桁の数にアルファベットを対応させるのが普通です。

　これを行うと,上記暗号は,

　　Ｔ Ｈ Ｏ Ｍ Ｐ Ｓ Ｏ Ｎ Ｉ Ｓ Ｉ Ｎ Ｔ Ｒ Ｏ Ｕ Ｂ Ｌ Ｅ

つまり,"Thompson　is　in　trouble."(トンプソンがトラブルにあっている)と解読されるわけです。

  しかし,暗号というのは他人に解かれては困りますが,本人には解けないと困ります。

　そこで,暗号を解いて欲しい人だけに,ｍ＝163276821については鍵(key:キー)として,"163276821が12553と13007の積に素因数分解できる。"ことを教えておくわけですね。

　具体的には,暗号は解くプロセスをコンピュータにプログラムしておき,キーとｙのリストを入力すると直ちにｘのリストが計算されて文章に変換された解読結果が得られるようにしておくわけです。

　ｍ＝163276821の素因数分解程度なら,大した労力もなくできるので,これは暗号としての意味を持ちません。

　しかし,ｍの桁を200桁とか400桁とかにしておくと,現在のコンピュータでは因数分解に何年か何十年かがかかるはずなので,それで解けたとしてももはや暗号としての価値はなくなっていることになります。

　そこでキーを持っている人だけに通じる秘密となります。これが公開(キー)暗号の一つRSA暗号の仕組みです。

 では,具体的にコンピュータでｍの素因数を見つけるというのはどうすればいいのでしょうか？ それは,もちろん単純には２から順にｍを割っていって１つ１つ割り切れるかどうかを調べればいいのですが。。

　でも例えば 613という整数が何かの整数で割り切れるかどうか,を調べるのに２から 612まで600回程度も割り算をする必要はありません。

613は25×25＝625よりも小さいので,仮に613が何かの整数で割り切れるとすると,それはまず２つの整数の積に表わせるはずですが,その２つの整数のうち,一方は必ず25以上で他方は25以下です。

そこで,２から25までの間の数で割り切れないなら,これの素因数はない,つまり613は素数であるということになります。

実際にはこれより効率のいい素因数探しのアルゴリズム(algorithm)もあるとは思いますが,基本的には８桁まで,つまり１億までの数が素数かどうかを調べるとか,その素因数を全て探すとかが目的なら,"せいぜい４桁の試行回数＝1万回の割り算"をするだけでいいことになります。

しかし,もしｍが200桁ならどうでしょうか。基本的には１から100桁までの全ての数で試行錯誤して割り算をやって余りがでるかどうかを検算する必要があります。

これは現在のコンピュータでも莫大な計算量なので,工夫しても何年かはかかるでしょう。というわけで,事実上解けない暗号ということになるわけです。

もっともパスワード(password)である"素因数＝鍵(キー)そのもの"を盗まれたら意味はないわけですけどね。

ところが,いまの工学(technology)の世界では,現在のコンピュータの計算時間をはるかに縮めることができる"量子コンピュータ"という可能性があります。例の小説の中では既にこれが完成して実用化されていて世界中の暗号が無力化されたことになっています。

しかし,実際には,まだ量子コンピュータは,せいぜい数桁の因数分解に成功したというレベル(level)にしか到達してないらしいです。

もしも,量子コンピュータが完成すれば,それは現在のコンピュータが何年,何十年とかかる計算を,因数分解などの計算の種類によっては数秒,数分で解いてしまうということになります。

今の暗号は役に立たないことになり,新しいものを考え出す必要にせまられるでしょう。

そもそも,コンピュータといのは,数でいえば全ての数を２進法で表わす,つまり１と 0 だけで表わすことが基本になっています。0 は 0 ,１は１,２は10,３は11,４は100,５は101,６は110,という感じです。

このときの１と 0 で表わされた各桁をビット(bit)といいます。また,面倒なので,ビットが８桁集まったものをまとめてバイト(Byte)と呼びます。

これを利用すると,片手の指だけで 0 から 31まで32個の数をカウントすることができます。手を開いた状態が 0 ,親指を折ると１,人差し指を折って親指を元に戻して立てると２,人差し指と親指を折ると３,中指まで使うと７まで数えられます。

指が１本増えるごとに折った状態と立てた状態の２通りがあるので数えられる数の個数は２倍に増える,というわけです。片手を握った状態は31ですね。

このことから,両手を使うと 0 から1023まで数えられる,ことになります。足の指を折るのは大変ですが,もしも可能なら手足の指は全部で20本あるので 0 から(1024×1024－1)まで,実に100万以上まで数えることができます。

手足の指:20ビットだけでもそこまで数えられるのですが,現在のパソコンの最先端には64ビットのマシンというのもあって,それだと整数だけでも莫大な数(2⁶⁴－1)まで数えられるということがわかります。

コンピュータの具体的な計算には,媒体(メディア)としてメモリーとか,時には大容量のディスクなども利用しますが,基本的に一度にバサッと足し算や掛け算などの演算をするものは,32ビットマシンなら２進法で32桁,64ビットマシンなら２進法で64桁くらいのレジスターと呼ばれるものです。

電気回路的には,"通電＝(電流が流れている状態)がon＝１"で,"(電流が流れていない状態)がoff＝0 "であり,これによって電流で数:1,0 を表現することができます。

これをうまく組合わせれば,全ての数を表わすこともできるのです。

さらには論理回路といって,いわゆるブール代数の論理を表現する電気回路もコンピュータの中に構成されています。

だいたい,"NOT＝(否定)"という回路があればほとんどの論理を表現できます。"NOT＝(否定)"というのは１がくれば 0 を, 0 がくれば１を返す論理回路です。

例えば"YES＝(肯定)"なら,"NOT＝(否定)"を２つ直列に並べればいいわけです。逆に"YES＝(肯定)"だけの回路からはどうしても"NOT＝(否定)"をつくることはできません。

ですから,例えばコンピュータの内部で割り算の試行錯誤を行なう場合,１ビットなら 0 の場合と１の場合の２通りを行うのですから最低２回の計算をする必要があるわけです。

そして２ビットなら４回,３ビットなら８回というように計算回数はネズミ算的に増加していきます。

そこで,単純に考えても200桁の数 ～ 10²⁰⁰なら,10¹⁰⁰回,つまり約3300ビット＝2³³⁰⁰回くらいの計算回数が必要ということになり,コンピュータの能力をもってしても莫大な計算回数となって事実上不可能になるわけです。

ところが,量子コンピュータのアイデアはブール代数の単純な論理では表現できない量子力学に従う論理回路を利用することで,計算のスピードが飛躍的に上昇して,こうした時間的限界を突破できるというものです。

かつて,アインシュタイン(A.Einstein)は,"神はサイコロ遊びをなさらない。"とか,"神はサイコロを振らない。"(英語では"God does not play dice.")とか述べたと言われています。

これこそは"アインシュタイン生涯最大のあやまち"です。実際は"神はサイコロ遊びをなさる。(God does play dice.)"というのが正しいのです。

これについては後で量子通信について述べるときに詳しく説明しますが,"神がサイコロ遊びをする。"というのは量子力学の１つの真髄を示す言葉です。

現在のコンピュータというのは 0 の場合と１の場合で"２通り＝２回の計算"が必要なわけですが,これが１回で済めば結局,"何桁＝何ビット"であろうと１回の計算で済むわけですから,計算時間は飛躍的に短くなることは自明です。

これを実現しようというのが量子コンピュータという概念ですね。

量子論というのは全ての事象(event)は確率的にしか存在できない,つまり"粒子といえども実は存在する確率というものの波＝確率波 or 量子(quantum)"でしかない,というものです。

ですから,確実に 0 である,とか確実に１であるとかいう確率として100％の状態ももちろんあるのですが,0 と１が半分ずつの確率で存在しているような中途半端な重ね合わせ状態も存在可能なわけです。

したがって,最初から確実に 0 であるとか１であるとかではなく,0 と１の両方の可能性を持つ状態を入力信号として入力すれば,0 に対する結果と１に対する結果が重ね合わされたものとして出力されるはずというのが,量子コンピュータの基本的なアイデアです。

つまり,入力信号の 0 である状態と１である状態のそれぞれの確率を示す係数さえ知っていれば,結果もその割合の重ね合わせで出力されるので,その結果, 0 の場合と１の場合の計算結果を並列して同時に得ることが可能になるのです。

しかしながら,技術的には,まだ色々な問題点があるので実用化には到っていないらしい,という話です。