« 記事リバイバル③(一筆書き(トポロジー)入門) | トップページ | 記事リバイバル⑤(量子通信(続::神はサイコロ遊びをなさる)) »

2018年10月29日 (月)

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

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

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

 

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

 

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

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

 

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

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

 

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

 

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

 

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

 

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

 

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

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

 

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

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

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

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

 

これらの最初の数:y=145387828についての方程式79921 ≡145387828 (mod 163276821)の解xを求めるには,mがm=163276821=12553×13007と素因数分解できることがわかる必要があります。

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

 

 そして5つの暗号数yについて全て解いて,その結果のxの値を2桁毎に分けて順に並べます。x=30182523は,30 18 25 23と並べられます。

 

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

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

ですね。

 

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

 一般に,11=A,12=B,13=C,....36=Zというように2桁の数にアルファベットを対応させるのが普通です。

 

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

  T H O M P S O N I S I N T R O U B L E

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

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

 

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

 

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

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

 

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

 

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

 

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

 

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

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

 

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

 

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

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

 

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

 

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

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

 

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

 

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

 

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

 

そもそも,コンピュータといのは,数でいえば全ての数を2進法で表わす,つまり1と 0 だけで表わすことが基本になっています。0 は 0 ,1は1,2は10,3は11,4は100,5は101,6は110,という感じです。

 

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

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

 

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

 

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

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

 

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

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

 

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

 

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

 

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

 

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

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

 

そして2ビットなら4回,3ビットなら8回というように計算回数はネズミ算的に増加していきます。

 

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

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

 

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

 

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

 

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

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

 

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

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

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

 

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

 

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

 

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

|

« 記事リバイバル③(一筆書き(トポロジー)入門) | トップページ | 記事リバイバル⑤(量子通信(続::神はサイコロ遊びをなさる)) »

118. 観測問題・量子もつれ」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/71281/74496458

この記事へのトラックバック一覧です: 記事リバイバル④(公開キー暗号(神はサイコロ遊びをなさる)):

« 記事リバイバル③(一筆書き(トポロジー)入門) | トップページ | 記事リバイバル⑤(量子通信(続::神はサイコロ遊びをなさる)) »