「公開鍵暗号」とくにRSAと呼ばれるシステムは、有名な暗号ソフトPGPの理論的基礎となっている。 一方、JavaScript はHTMLページでちょっと動的なことをやったりするのによく用いられる簡易スクリプト言語だが、 Windows のインターネットエクスプローラーとメモ帳などで、だれでも手軽に使える。 Cのソースが公開されているPGPのまねごとを、Cよりはるかに貧弱で低速なJavaScript上でエミュレートすることに何の意味があるのか？ という疑問は決して不自然ではないが、 「JavaScript上でRSA」とかそもそも「素数」と聞くだけでうっとりしてしまう脳が存在することも事実である。
RSAの核心部分については「高校数学で遊ぶ公開鍵暗号RSA」でいちおう説明した。 「JavaScriptでPGPもどき」では、JavaScript自身の整数型（253という限界）を使って、 つまり約53ビットの鍵の小さなRSAを構築した。 より大きな鍵を使うために配列を使って任意精度を実現する最初のテストが「JavaScriptで1000桁電卓」 「巨大整数計算の実装（つづき）」で、 これを用いて「64-bit RSA by JavaScript」が実装された。 むだが多くて遅かったが、「bigint_0_4.js 概要」で多少、改善、 「100-bit RSA by JavaScript」で100ビットの鍵、 完全なインターフェイスをもったデモ「Pig PGP: なんちゃって暗号」まで書いた。
この段階で実感されることは、RSAの「現実的」な実装では、巨大な素数を手に入れるための計算時間がとても大きいということだ。
もう少し一般的にいえば、 2002〜3年現在のPCでは、 おおざっぱに16桁の数（つまり1000兆）くらいまでは、 「3, 5, 7, ... で順々に割ってみて、どれで割っても割り切れないから素数だと確認する」 という単純な方法だけで、素数か素数でないか判定できるか、 それより大きいと時間がかかりすぎる。 逆にいえば、一億だの一兆だの、そんな小さな素数は、 原理的に、簡単な JavaScript 数行であっさり処理できる。
ちなみに、
log2 1016 = 53.15...
なので、16桁オーダーの素数は約53ビットであり、
そのオーダーの素数２つをかけ算してできる公開鍵の長さは100ビット程度ということになる。
以上のデモを行ったとき、これより大きな素数を使うには「確率的」な素数判定が必要になる、とコメントした。
そのために必要な数学は「フェルマーの小定理」――
ある数 a がもし素数なら、勝手に選んだ自然数 b の a 乗を a で割ると、余りは b に戻る
という法則だ。
さらっと、このへんの復習から始めましょう……。
ピタゴラスの定理というのはご存じと思いますが、ことばでいうと、
直角三角形のいちばん長い辺の長さの二乗は、残りの２辺の長さそれぞれ二乗して足したものと等しい、
ということです。
言い換えれば二乗和の平方根をとるといちばん長い辺（斜辺）の長さが出るわけです。
また、話は変わりますが、
(a + b)2 = a2 + 2ab + b2
といった展開の公式もご存じと思います。
こうした定理は考えてみるとけっこう難しいですが、使い慣れているので、何となく当たり前のように思ってると思います。
フェルマーの定理（小定理）も最初は分かりにくいと思うかもしれませんが、
実際には少しも難しいことはなく、
「自然数を素数乗してその素数で割ると、割り切れなくて余りが出て、その余りは最初の数と同じになる」
という一種の数字の遊びです。
例えば「自然数」として４、「素数」として５を選ぶと、４の５乗を５で割ると余りは４といったことです。実際、４の５乗は 1024 だから、
5で割ると４余るはず。
で、ふだんピタゴラスの定理がなぜ成り立つか？などとあまり意識しない、意識しなくてもべつにピタゴラスの定理を使ううえで、 なんの支障もない、というのと同じように、 フェルマーの定理がなぜ成り立つのか以下の議論とはあまり関係ないです。 証明済みの法則として受け入れてください。 いちおうの説明は、別記事「フェルマーの小定理」にあります。 公理論的というか大学数学的というかエレガントというか抽象的な立場では、 これはオイラーの定理の特殊例にすぎませんが、そのこともここでは全然関係ないです。
式を使って書けば次のような感じです。
あるいは両辺を n で割って――
この場合は、n が素数 p の倍数じゃないという条件がつきます。
素数5 → 5-1=4 → 24 = 16 → 5で割ると1余る
素数7 → 7-1=6 → 26 = 64 → 7で割ると1余る
このように「素数-1」乗を素数で割ると必ず1余ります。 この法則は、素数でないときは、一般には成り立ちません。 次の例では余りが1以外になってます。
合成数6 → 6-1=5 → 25 = 128 → 6で割ると2余る
ご存じとは思いますが、話の順序としていちおう書くと、 「逆、必ずしも真ならず」というように、あることが成り立つからとてその逆も成り立つとは限りません。 例えば「４の倍数はすべて偶数だ」という命題は当たり前すぎですが、 逆に「偶数はすべて４の倍数だ」はどう考えても間違ってます。 もちろん、逆が言えることもあります。 「６の倍数は２でも３でも割り切れる」というのは事実です。 そして逆に「２でも３でも割り切れる数は６の倍数だ」ということも言えます。 これは逆も成り立つ例です。
つまりあることが正しいとして、その逆が成り立つかどうかは別問題。 成り立つ場合もあるけれど成り立たないこともある。 逆というのは必ず成り立つわけではない。 一般には成り立たない。
で、フェルマーの定理の逆が成り立つかどうか。
フェルマーの定理は「x が素数なら、nx-1 を x で割った余りは 1 」という内容で、 これは数学的に証明されてます（ n は x の倍数以外の任意の数）。 ですので、その逆が成り立つか？というのは、 「ある数 x が与えられたとして、もし nx-1 を x で割った余りが 1 だったら x は素数だ、と断定できるか？」 ということ。
もしそう断定できるなら、RSAで素数探しをするとき、 3, 5, 7, ... でかたっぱしから割り切れるかどうか試すかわりに、 たった一つ式を検証して余りが1かどうか？を調べれば、素数か素数でないか、ラクに判定できることになります。 最初に書いたように16桁くらいまでの小さい数であれば、あれこれ悩むより、 かたっぱしから割ってみたほうが速いですが、 それより大きい数では、かたっぱしから割るのでは時間がかかりすぎるので、何とか効率良い抜け道を探したいわけです。 そしてRSA暗号では50桁や100桁や150桁の素数を扱いたいわけです。
ところで、逆は必ずしも成り立たないけれど、「逆の裏」すなわち
このことを分かりやすく説明するため、話を単純化して、いま仮に、接続速度というものには、 ダイヤルアップ56K、ADSL8M、光ファイバー20Mの3通りだけあるとします。 でもって、実効速度1Mbps以上の接続の人だけが参加できる「ブロードバンドの会」という閉鎖的なやらしい会員制クラブがあるとします（笑）。 ただの仮定ですが。ていうか、何をするためのクラブか知りませんが。 この場合、ADSL以上であることは入会の必要条件です。 ダイヤルアップ56Kなんてのは書類審査の段階で跳ねられます。門前払い。問題外です。 一方、光ファイバーの人はとっても速いので1Mbps以上なんて基準は余裕でクリアします。 基準に比べて、充分すぎるくらい充分に速いです。すなわち光ファイバーの人は入会のための充分条件を持っています。 問題はADSLの人で、これは理論値8Mといっても1Mbps出るかどうかは場合によりけりなので、 個々に調べるしかないですが、まぁすべてではないにせよ多くの場合、1Mbpsは出るでしょう。
なんか話がわけ分からなくなってきましたが、 フェルマーの定理の対偶をとると、 「nx-1 を x で割った余りが 1 にならなければ x は素数ではありえない 」と断言できます。 x が素数なら必ずこの余りが1になることが分かってるからです。 これはフェルマーの定理によって保証されることです。 ですので、素数だけが入会できる素数の会という場所があるとして、 上記の余りが1になるかをチェックする「フェルマーテスト」に合格できないような数は門前払いです。 それは絶対に素数でないので入会は認められません。 フェルマーテストを通過できるということは素数性の必要条件です。 また、素数であれば、もちろんフェルマーテストに合格します。 素数性はフェルマーテスト合格の充分条件です。 問題は、フェルマーテストにパスするからといって、まだ素数だとは断言できないということ。 素数であれば必ずフェルマーテストを通るが、逆は言えない、フェルマーテストを通るものがすべて素数だけとは限らない。
しかし、フェルマーテストで弾かれるものは100%素数でない（合成数）です。
このことを実際に確かめるために、次のようなスクリプトを走らせてみましょう。
<script type="text/javascript">
function _is_prime( n ) {
if( typeof n === "number") {
if( n % 2 === 0 ) return false;
var max = Math.floor( Math.sqrt( n ) );
for( var i=3; i<=max; i++ ) {
if( n % i === 0 ) {
return false;
}
}
return true;
}
}
for( var n=3; n<1000; n+=2 ) {
var oAmari = Bigint.powmod( 2, n-1, n );
if( oAmari.toString() === "1" ) {
_debug( n + " はフェルマーテストに合格しました" );
if( _is_prime( n ) ) {
_debug( "しかも素数です" );
} else {
_debug( "<em>しかし素数ではありません<\/em>" );
}
}
}
いま仮にフェルマーの小定理の式の累乗の下にくる数（ベース）を２に固定して、
３から1000までの奇数 n に対して、 2n-1 を n で割った余りを調べます。
最高で 2999 という大きな数になるので、
JavaScript 自身の関数（整数値 253 まで）では対応できないので、
Bigint オブジェクトを使います。
そのため、ライブラリ bigint_0_4b.js をインクルードしています。
Bigint.powmod( b, c, d )
は、
b の c 乗を d で割った余りを（Bigintオブジェクトとして）返します。
詳しくは「bigint_0_4.js 概要」。
余りが1になった場合（フェルマーテストに合格した場合）、直接3, 5, 7,... で割って、本当に素数かどうか確認します。
フェルマーテストを通らないものは絶対に素数でないのでこの確認はするまでもありません。
これを実際に走らせると、 3から999がテストされ、 全素数について、「フェルマーテストに合格しました. しかも素数です.」というデバッグメッセージが出ますが、 たまーに「フェルマーテストに合格しました. しかし素数ではありません.」という出力が混ざっているのが観察できます。 素数でないくせにフェルマーテストをすり抜けてしまう連中がいるのです。
結局、フェルマーの小定理の逆は、つねに成り立つわけではないことが分かりました。 げんに成り立たない例（反例）が見つかったので議論の余地ありません。 とはいえ、フェルマーテストはほとんどの合成数をフィルタリングしてくれます。 そして素数は必ず通します。 素数でないのにフェルマーテストを通ってしまう数もありますが、 ごくまれです。 この範囲でも1%くらいですが、PGPが実際に機能する50桁、100桁のような巨大整数においては、 適切に設定されたフェルマーテストをパスした数は、素数と断定してまず間違いありません。 数学的に「絶対」という保証はないのですが、実用上は問題ありません。「実用上」の意味については後でもう少しつっこんで検討します。
フェルマーテストを通過できない数は素数でありません。こっちは絶対的に断言できます。
フェルマーテストを通過した数のみが素数でありえます。
フェルマーテストを通過する数、言い換えれば（非自明な底に対して）フェルマーの小定理を成り立たせるような数のことを、
「素数候補」 Probable Prime
と名づけます。
すべての素数候補が本当に素数であるわけではありません。
「素数候補」のなかには真の素数と、実際には合成数である数（まれ）が混ざっています。
実際には合成数であるのに素数候補となる数を
var ps = 341; var oBig = Bigint.pow( 2 , ps - 1 ); _debug( "2<sup>" + ps + "-1<\/sup> = " + oBig ); var Result = Bigint.divmod( oBig, ps ); _debug( ps + "で割ると商" + Result[0] + ". 余り" + Result[1] ); var oCheck = Bigint.mul( Result[0] , ps ); oCheck = Bigint.add( oCheck, Result[1] ); _debug( Result[0] + "×" + ps + " + " + Result[1] + " = " + oCheck ); _debug( Bigint.cmp( oBig, oCheck ) === 0 ? "一致しました" : "検算が合いません" );
クラシックPGP（Ver. 2.x, etc.)で暗号鍵の生成に使う巨大素数は、
暗号のような、デリケートなセキュリティにかかわることが、そんなあいまいな話でいいのでしょうか。 数学的に間違いがありうると分かっているような方法で良いのでしょうか。
それに対する答は、「これは純粋数学ではないから、数学的に厳密でなくても実用上かまわない」です。 動画処理ソフトのノイズフィルターが100%すべてのノイズを除去できなくても実用上、有用なのと同じこと。 暗号ソフトもあくまでソフトウェア製品であり、数学を応用したアプリケーションです。 具体的に「もしかすると鍵生成につかった素数は本当は素数ではなかったかもしれない」ということを考え、 それがまじ素数でなかったなら何が起きるでしょうか。
数学的にいうと、その場合、公開鍵は２つの巨大素数の積ではなく、そのどちらかが実は合成数だった、つまり、 全体として３つまたはそれ以上の数の積になっている、という状態です。 PGPの安全性は公開鍵の素因数分解が難しい、という事実にもとづいています。 例えば公開鍵が100桁の素数２つの積だと思っていたら、そのうち1つは実は合成数で30桁の整数と70桁の整数にさらに分解できるとしたら……。 その場合「素因数分解が思ったよりは少し簡単にできる」ということになります。
いうなれば「ゾウが踏んでも壊れません。超頑丈金庫」という製品を買ってきて、 子どもがちょっとけとばしたら、壊れてしまった、という状態です。 この場合、客は当然、文句を言うでしょう。 欠陥商品と。 このような欠陥商品が例えば1%の割合で混ざっていたら、あそこの製品は品質に問題がある、ということになるでしょう。 1%は実用上、問題になるレベルです。 ですが、部品に欠陥のある製品が100万に1とか一億に1の割合で混入していても、 そう問題にならないでしょう。 それどころか、99.999999%の圧倒的な成績を誇る高品質の製品と威張れるかもしれません。 暗号ソフトの場合、内部的に素数と思って使っている数が0.00000001%の確率でじつは素数でないとしても、 そもそもまず発覚しないでしょう。（内部パラメータが理論と違えば、最悪、暗号化や暗号解除がおかしくなるが、 そのときはそのときで、何かうまく解読できないんだけど？とかなって、 遅かれ早かれ「あれ、おかしいな、再インストールして鍵を作り直してみるね」 となって、それで解決。） しかも100桁×100桁のうち一方が素数でなかったとしても、 暗号をクラックしたい人からみて最もラッキーな場合ですら、 100桁×50桁×50桁のひとつの50桁の数が分かるだけで、素因数分解を完成するには、まだまだたいへんな計算量が必要。 つまり欠陥商品で非素数が混入していてさえ、それでただちにすべてがぶっこわれるほどヤワじゃない、ってなことです。 だいたいのイメージとしては。 ていうか、1億ぶんの1とか、そんなの宝くじに当たる確率よりもっと難しいでしょう……欠陥商品を手に入れるのは。
直接3, 5, 7, ... で割って確かめなくても、 フェルマーテストを使って素数でないものを除外できる、ということを説明しました。 実際のPGPでは、「どうみても素数でないもの」をとりあえず捨てて（fast test）、 「素数かもしれない」と思ったものがあるとフェルマーテストでじっくり調べています（slow test）。
フェルマーテストは素数でないものを合格させることがありますが、 素数を間違えて失格させることはありません。 ですので、フェルマーテストではねられた数は、実際に割り算しなくても合成数だと断定できます。 何十桁もある巨大な数が素数か素数でないか簡単には分からないような場合でも、 フェルマーテストにかけて否定されれば、それは絶対に素数でない、と断言できます。 この場合「この数は素数でないこと（つまり合成数であること）は分かっているのだが、 どういうふうに素因数分解できるのかは分からない」というある意味「おもしろい」状態になります。 素因数分解が完成している数とそうでない数というのは、じつは観測者すなわち人間のこころの状態とのあいだの相対的な問題にすぎず、 Probable といっても「絶対的」な見地からは素数であるかないかのどっちかひとつです。 どっちつかずの状態こそが人のこころを引きつけるのでしょうが……。
RSAにおけるフェルマーテストを JavaScript上で敢行するということは、
つまり50桁や100桁の指数計算
89715021234567890123456789012345678901234567890123456789077777
のような、とんでもない累乗計算を意味します。
こんなすごい指数計算をするくらいなら、むしろ割り算してみるほうが速いのでは？という感じもするかもしれませんが、
一般にはフェルマーテストのほうがずっと速いです。
（つづく）