「4つの4で遊ぼうよ」から発展して、任意の4つの数に対してパズルを解く JavaScript です。Netscape, Mozilla, IE で動作します。
「4つの4」の初期バージョンは、かなり計算時間がかかりましたが、そのごの高速化で、きわめて軽くなっています。手元の環境では、平均して1秒~10秒程度でパズルを解くことができます。また、初期バージョンはIE専用の「意味論関数」execScript
を使っていましたが、書き直してネスケやモジラでも動作するようになりました。
この記事は、すぐ次の「ラムダ関数――夢みつつ目覚めるもの」につづきます。
このメモは直前の「任意の4つの数を与えてパズルを解く「思考」スクリプト」から参照によって話を渡されました。
「4つの4」の最初のバージョンでは、コードを文字列として生成し、次にそれを「解釈」する、という二段構えを使っていました。これは本質的には、Lispでいうラムダ関数のようなもので、値が関数である変数(関数が代入された変数)、言い換えれば、本質的には、関数(メソッド)を返す関数(つまり超関数)にあたります。JavaScript では関数を文字通りリテラルとして使うこともできますが、さらに関数コンストラクタによって、実行時に動的に何度も何度も自分で自分(の一部)をリコンパイルする、という離れ業が使えます。JavaScriptというと、ブラウザでかんたんな処理を行う簡易言語というイメージがあるかもしれませんが、その深層は意外にも C や Java より柔軟です(まぁ、Cプログラマにとっては、それが厳密でなくて気持ち悪い、という面がありうるのも事実ですが)。
その場で動的にコンパイルされる、というスクリプト言語の本質が、一方においては(実行時間における)弱点であると同時に、他方において、以下で述べるような超柔軟な構造を形成します。Perl における eval
も同じことです。実行時にコンパイルされるからこそ、自分で自分を見つめる「コンパイル層」と「記述層」のふたつのレイヤが生じて、それらのあいだでいろいろな「階層のもつれ」をもてあそぶことができ、このような「もつれ」のなかにこそ「意味」や「思考」や「知能」のようなものがひそんでいるのであろう、ということは、広く認識されてます。
// 変数に「解釈すると計算式」になるような文字列を形式的に格納して…… expression = getExpressionEx( op_code, param, param2, n1, n2, n3, n4 ); // それを内容的に解釈して実際に計算する関数を作って…… var lambda = new Function( "return " + expression + ";" ); // 幻想世界と回線をつなぎ、戻り値を現実世界でいただく evaluated = lambda( );
最初の代入では、expression は単なる冷たい文字列です。例えば、1+2+3+4 という7つの記号がならんだ模様です――ここでの説明を理解するには、これを「足し算の式だ」と解釈せず、ただの模様だ、と思わなければなりません。実際、これは、JavaScript の文字列として例えばae9gyj#と同じ透明でランダムな存在です。次の lambda には、この模様を戻り値にせよ、という関数が入ります。ラムダは、ふたつの世界を結ぶ役目の
ラムダは、1+2+3+4 をまず単なる文字列としてたんたんと読み込み、次の瞬間、それをコンパイルして「10」を「意味」していることを理解します。
3番めの文で、evaluated はラムダ関数が息を吹き込んで作った戻り値をもらいます。
ラムダ関数にとって、このプロセスは、無数に流れるループのなかの一瞬のひとこまにすぎません。
ラムダ関数はプロシージャであると同時に、単なる揮発する一時的な変数であって、ループがまわるたびに違うものが入ります。Function
コンストラクタが一時的に生成するプロシージャへの参照です。参照の入り口はlambdaという決まっためじるし(なまえ)を持っていますが、それが参照する実体は、めまぐるしく変化します。つまり、lambdaは、あるレベルでは、ひとつの変数ですが、lambda というのは誰ですか、何ですか?と尋ねても、lambdaというなまえが指し示している「モノ(世界、関数)」は、1秒に何万回となく変化します。あくまで変数 lambda なのです。関数 getExpressionEx
が返す「だれか」(名無しさん)の考え方を一時的に「自分」だと思って、それを忠実に実行し――実際、その時点では、 lambda はその名無しさんと同一なのですが――、実行が終わると、すぐに「自分」を解放して次の名無しさんに「なる」わけです。
言うまでもなく、これは自閉症者のロジックです、が、あなたは、この文を呼んでもこれが何を指しているのかコンパイルできないでしょう。
以上が、Cのようなコンパイル言語よりもダイナミックにコンパイルされるスクリプト言語が柔軟でありうることの説明ですが、これは他方において、巨大ループの1ステップごとにコンパイラが起動され自分で自分を再コンパイルする、という大きな計算コストを意味しています。
2つの世界の通信に特有の問題については、別記事「execScript()が解釈する変数のスコープ」も参考にしてください。
} else if( g_sqrts == 1 ) { if( flag[0] ) N[ g_sqrt_idx[0] ] = "Math.sqrt(" + N[ g_sqrt_idx[0] ] + ")"; } var base = g_sqrts; if( g_sigmas == 4 ) { if( flag[ base+0 ] ) N[ g_sorted_idx[0] ] = "Sigma(" + N[ g_sorted_idx[0] ] + ")"; if( flag[ base+1 ] ) N[ g_sorted_idx[1] ] = "Sigma(" + N[ g_sorted_idx[1] ] + ")"; if( flag[ base+2 ] ) N[ g_sorted_idx[2] ] = "Sigma(" + N[ g_sorted_idx[2] ] + ")"; if( flag[ base+3 ] ) N[ g_sorted_idx[3] ] = "Sigma(" + N[ g_sorted_idx[3] ] + ")"; } else
これとはまた別のレベルですが、自分で自分を持ち上げる、という意味では、次のような考えともイメージが近いです。
document.write('<script type="text/javascript">'); document.write('document.write("I know you like the function " + '); document.write('"<code>document.write()<\/code>, do you?");'); document.write('<\/script>');
PigPGP は、JavaScript で RSA暗号系を実装する試みです。
おもしろいといえばおもしろいですし、クレイジーといえばクレイジーです。
2004年になって、とうとう本物のPGPと同等の1024ビット強度も実現、
乱数ジェネレーターも Mersenne Twister を搭載するなど、「なんちゃって暗号」と呼ぶにはちょっと本格的になりすぎたかもしれません。
以下はいちばん最初、たった64ビットでも苦労していた時期のメモです。最新版のデモは下記URLにあります。
http://www.faireal.net/demo/PigPGP/
Mozillaユーザのボブは デモページ を開いて、「鍵生成」をクリックした。1秒程度で64-bit鍵が生成された。
/H/b+9-D+u-e+P+o2=*=-8s+rW2がボブの公開鍵、
/H/b+9-D+u-e+P+o2=*=/n/X-a/r/2-Q/g$がボブの秘密鍵だ。
ボブは公開鍵をホームページで公開する一方、秘密鍵は秘密の場所に保存した。
アリスはボブに秘密のメッセージを送ることにした。ボブが公開している公開鍵/H/b+9-D+u-e+P+o2=*=-8s+rW2を「公開鍵」欄にペーストしてから、テキスト欄にメッセージをタイプする。
「暗号化」をクリックすると、アリスのメッセージは、ボブにだけ解読可能な形で暗号化された。
以下が出力例である。(注: この暗号系はセッション鍵を使っているため、同じ文章を同じ鍵で暗号化しても、そのつど異なる出力になる。)
-----BEGIN PigPGP MESSAGE----- Version: PigPGP 0.1.0 by JavaScript 7/y+t/3-r-eO/5j-S+C-T+gB7J+t-v-r-J/I+2/g-l+C/U+gd77J+4+HG/IP/g-V +C-S+g+67i+t/4-rs/Iqc+x+C/m+gC74+t-s+HJ-Y/wC/W+C-T+gr7/L+t-b-r-P E/0/g+N+C/i+g17H+t-A+HJ-Y/w9+R-f-2+g07I+t+W-r-a/I+F/g-k+C/5+g@7e J+4+HG/Io/g-c+C/3+gH76+t-2-r+T/Iq/g-R+C-N+gC+f+U-9/Y-r-O/Is/g-e+ C-J+gd7/$+t-A+HJ-Y/w/g-k+C/J+g-Y7y+t+Y-r+A/I+q/g-d+C-L+g+171J+4+ HG/IP/g+P+C/3+gy7/y+t-l-r+T/I+6/L-3-5B+gGA+q/3/0-r-Ogf/g-l+C/e+g r78+t-d-r-D/Is-wWS+R+gB7/C+t-d-r-7/Io/g-c+C/3+gD7f-d/a-r+A/Iy/g- K+C-X+gv77+t-0-r-a/Iq/g-r+C/i+gj7D+t+Y+HJ-Y/wl+c+C-U+gy7/A+t/2-V /q/IZ0-G+C/3+gX7a+t-A-r+ID$/g+N+C/h+g17H+t/6+HJ-Y/w/g/$+CZ+g-e/m -JJ+1-r+y/IR/g-5+C/m+gA74+t-n-r-zT/D/g+N+C-$+gA71+t-8-r-0-Y/z-wT -a+U+O07f-i-f-r+E/I+1/g+N+C-S+g+67-w-7+t-VEl2/g-R = +z-Z-V-7/f+x+c+o -----END PigPGP MESSAGE-----
Pig PGPというだけあって、いかにもPGPっぽいが、もちろん互換性はない。
アリスは、この秘密のメッセージを、ボブにメールで送った。メールは盗聴されていたが、だれにも解読できなかった。
さて、ボブはアリスからのメッセージをテキスト欄にペーストし、「秘密鍵」の欄には、自分の公開している公開鍵に対応する秘密鍵
/H/b+9-D+u-e+P+o2=*=/n/X-a/r/2-Q/g$
をペーストした。
「暗号解除」をクリックすると、アリスからのメッセージがあらわれた。
ボブはアリスに返事を書いた。アリスへの返事を暗号化するときには、今度はアリスが公開しているアリスの公開鍵を使う。ボブ自身の鍵では、ない。そして、ボブはアリスの秘密鍵を知らない。このように、やりとりする方向によって異なる鍵を使い、しかも暗号化するときの鍵(受信者の公開鍵)と暗号解除するときの鍵(受信者の秘密鍵)が異なる。「公開鍵暗号は非対称鍵だ、というのは、こういうことなんだなぁ」アリスとボブは、しみじみ実感するのであった。
現在は512ビット版を公開していますが、参考までに古い記事も残しておきます。
oKey = new RSA( strength )
oKey.modulus
oKey.publicKey
oKey.secretKey
oKey.setKeys( mod, pub, sec )
oKey.encrypt( message )
oKey.decrypt( encrypted )
上記のように64ビット鍵は充分に高速に扱えるようになったので、80ビットと100ビットに挑戦してみます。
var oKey = new RSA(80); _debug( "80ビットの鍵を生成しました: " + oKey );
以下の公開鍵を使って「12345678905555」を暗号化します。
法 1 59451 04683 81864 79200 58494 01711
指数 1 86714 37520 24315
var test = "12345678905555"; var oPubkey = new RSA(); oPubkey.setKeys("1 59451 04683 81864 79200 58494 01711" , "1 86714 37520 24315"); _debug( test + "を暗号化。使用する鍵: " + oPubkey); _debug("結果: " + oPubkey.encrypt( test ));
38875 64474 95279 32099 48253 16740 が得られるはずです。
上記に対応する秘密鍵
1 05034 82749 44284 05749 84137 22755
を使って、上で得られた暗号を解除します。
var encrypted = "38875 64474 95279 32099 48253 16740"; var oSeckey = new RSA(); oSeckey.setKeys("1 59451 04683 81864 79200 58494 01711" , "1 86714 37520 24315" , "1 05034 82749 44284 05749 84137 22755" ); _debug( encrypted + "を暗号解除。使用する鍵: " + oSeckey ); _debug( "結果: " + oSeckey.decrypt( encrypted ) );
1234 56789 05555に戻るはず。
暗号化と暗号解除は、計算量が多いです。そのためPGPでも、メッセージ全文を公開鍵で暗号化することはせず、メッセージを共有鍵暗号で暗号化して、その共有鍵を公開鍵で暗号化して送る、という方法が採用されました。
鍵が長くなった場合に時間がかかるのは鍵の生成です。その時間の大部分が素数の検索です。さらに言えば、候補の数が素数かどうかの確認に時間がかかります。手元の環境で、上の100ビット鍵を使うと、暗号化や暗号解除の処理は数秒~数十秒程度にすぎませんが、この100ビット鍵の生成には3分かかっています。また、試しに104ビット鍵を作ると7分かかりました。かたっぱしから割ってみて素数性を確認する方法では100ビットくらいが限界で(1つの素数あたり50ビット=10進16桁)、さらに上に行くには、確率的な方法を使う必要があります。
24ビットから始めて、この遊びもとうとう100ビットに到達しました。あくまで「遊び」ですが、やってみると、いろいろと実感が深まり、なにかと勉強になるもんです。