5 : 25 JavaScriptで巨大整数演算

前 5‒24 p ｜ もくじ i ｜ 次 5‒26 n

JavaScriptで1000桁電卓

2002年 5月25日
記事ID d20525

2002年に、JavaScript上で任意精度整数演算を行うライブラリ bigint.js v0.2 - v0.4 を作ってみたときのメモです。 2004年に、はるかに効率化された bigint.js v0.5 に更新されましたが、記録のため、 この古い記事も残しておきます。 ちなみに、円周率計算のデモ（手元では2秒台で596桁）。

「[JS] 100行のプチ任意精度ライブラリ」も参照。

初めに

「JavaScriptでPGPもどき」では24ビットの鍵の長さのRSA暗号を実装した。暗号強度のこの制限は、JavaScriptで「ふつう」に扱える整数が 2⁵³ までなので生じた。JavaScriptでもっと大きな数の計算を ―― 浮動小数点でなく正確な整数計算として ―― 実行するには、足し算や掛け算を自分で実装する必要がある。このメモは、実際に試してみた第一夜の模様です。

100桁程度の整数3つを掛け算するデモの光景

2⁵³ は十進16桁にすぎないので100桁の素数をかけたりする現代暗号の世界をJavaScript上で楽しむには、多少の準備が要る。

整数を配列で表現する

例えば、7771234567890 という整数を、67890, 12345, 777 という3要素からなる配列で表現することにしよう。40桁の整数
12345 67890 22222 00000 33333 12345 44444 56789
は8要素の配列になる。各要素は絶対値において BIG_UNIT = 100000 より小さい。要素は昇順、すなわち整数の下5桁が配列の最初の要素、6桁め～10桁めが2番めの要素……となる。すべて10進数で考えている。負の数では全要素が負になる。

次の関数は、文字列として与えられた整数を上記の形式で格納した配列を返す。これはスケルトンである。より詳細な実装は、bigint.js参照。

function bset( canon ) {
    var Work = new Array();
    var size = Math.ceil( canon.length / 5 );

    // 最大要素の桁数
    var len0 = canon.length % 5;
    if(len0==0) len0=5;

    // とりあえず降順に格納。先頭には0がないので必ず十進法で評価される
    Work[0] = eval( canon.substr( 0, len0 ) );

    var pos = len0;
    var tmp;

    for( var i=1; i<size; i++ ) {
        tmp = canon.substr( pos , 5 );
        pos += 5;

        // 数値に変換。必ず十進法で評価されるよう0を消す
        Work[i] = eval( "1" + tmp ) - BIG_UNIT;
    }
    // 昇順にする
    return my_reverse( Work );
}

逆にこの形式の配列を文字列としての自然な整数表現に変換する bshow() を作っておく。

足し算

badd( A, B ) は上記形式の2整数を足し算する。要素ごとに足し算して、BIG_UNITを越えた場合は、「1くりあがる」ようにする。つまり、その要素から BIG_UNIT を引いて、ひとつ上の要素に1を足す。負数を含む足し算まで考えると、少し工夫が要る。

以下のサンプルで、bsign は正負の判定、babscmpは絶対値の大小の判定。

function badd( B1, B2 ) {
    var sign1 = bsign(B1), sign2 = bsign(B2);
    var ret_sign;

    // 結果の正負の判定
    if( sign1 * sign2 <0 ) {
        var abscmp = babscmp( B1, B2 );
        if( abscmp > 0 ) ret_sign = sign1;
        else if( abscmp < 0 ) ret_sign = sign2;
        else ret_sign = 1; // 符号だけ異なって絶対値が同じ、和はゼロ

    } else if( sign1 >= 0 ) {
        ret_sign = 1; // 正の数同士の足し算
    } else {
        ret_sign = -1; // 負の数同士の足し算
    }

    var sum = new Array();

    var max = Math.max( B1.length, B2.length );

    for( var i=0; i < max; i++ ) {
        sum[i] = 0;
        if( B1[i] ) sum[i] += B1[i];
        if( B2[i] ) sum[i] += B2[i];
    }

    // くりあがり等
    for( var i=0; i<sum.length; i++ ) {
        if( ret_sign >= 0 ) { // 結果は非負
            while( sum[i] >= BIG_UNIT ) {
                sum[i]-=BIG_UNIT;
                if(typeof sum[i+1] == "number" ) sum[i+1]++;
                else sum[i+1] = 1;
            }
            while( sum[i] < 0 ) { sum[i]+=BIG_UNIT; sum[i+1]--; }
        } else { // 結果は負
            while( sum[i] > 0 ) { sum[i]-=BIG_UNIT; sum[i+1]++; }
            while( sum[i] <= - BIG_UNIT ) {
                sum[i]+=BIG_UNIT;
                if(typeof sum[i+1] == "number" ) sum[i+1]--;
                else sum[i+1] = -1;
            }
        }
    }

    return bset( bshow( sum ) );
}

いったん bshow してから bset し直すことで格納形式を正規化する。数字の頭の0を消したり、近い数の引き算の結果、配列の長さが縮んだときに縮んだ部分を（0の入った配列でなく）未定義に戻して大きさと配列の長さが対応するようにするため。

引き算

引き算は全要素の符号を反転させる bneg を使って簡単に定義できる。

function bsub( B1, B2 ) {
    return ( badd( B1, bneg(B2) ) );
}

掛け算

例えば3要素の整数と4要素の整数をかけるには、要素を総当たり（12組み）全部かけて、積を足せば良い。JavaScript自身の加法や乗法を使うとオーバーフローで精度が失われてしまうので、上の badd を使って、bmul を構成する。

function bmul( B1, B2 ) {
    var zeros, _mul;
    var Work = bset("0");

    for( var idx1=0; idx1 < B1.length; idx1++ ) {
        for( var idx2=0; idx2 <B2.length; idx2++ ) {
            zeros = getZeros( ( idx1 + idx2 )*5 );
            _mul = ( B1[idx1] * B2[idx2] ).toString(10) + zeros;
            Work = badd( Work, bset(_mul) );
        }
    }
    return Work;
}

function getZeros( how_many ) {

    var _z = how_many % 10;
    var _z10 = (how_many - _z) / 10;

    var ret = "";

    for( var i = 0; i < _z10; i++ ) ret += "0000000000";
    for( var i = 0; i < _z; i++ ) ret += "0";

    return ret;
}

Demo

デモページのフォームにはA, B, C３つの入力欄がある。AとBの欄のそれぞれに大きな整数を書き込んでから実行ボタンをクリックしてみよう。次にA,B,C３つの欄すべてに巨大整数を入力してみよう。しょっぱなからあまりに大きなものを入れると計算時間が長くなりすぎるかもしれないので、10～20桁程度からいろいろ試してほしい。

AとBのみに入力した場合、それらの和と積を求める。Cも入れた場合、結合法則や分配法則のデモンストレーションを行い、計算間違いが生じていないか2通りに計算した結果を自動的に比較する。Windows 2000 上のIE6.0とNetscape4.79で動作確認した。以下は100桁程度の整数3つを入れた場合の出力例。これは53秒かかった。

この方法をさらに発展させれば、強度の高い「非自明な」RSAをJavaScript上で構築できるであろう。巨大剰余演算 bmod、巨大累乗計算 bpow などを実装する必要がある。詳しくは次回の予定。

この記事のURL

• https://yosei.fi/articles/5/25/#d20525

巨大整数計算の実装（づつき）

2002年 5月25日
記事ID d20525a

「JavaScriptで1000桁電卓」では足し算と掛け算まで書いた。今度は巨大整数の割り算、剰余演算、累乗計算などを考える。以下のリストは骨格だけだから、詳細についてはbigint_0_2.jsを参照。

累乗

累乗は掛け算の繰り返しで簡単に実装できる。ただしベタで繰り返すのは効率が悪い。例えば100乗を計算するとき100回かける（計算量100）かわりに平方計算を繰り返して2乗、4乗、8乗、16乗、32乗、64乗の6つを計算し（計算量6）、次に64乗したものと32乗したものと4乗したものをかければ、合計の計算量9で答がでるから効率が良い。要するに指数を2進展開する。

// PはBigInt形式でも通常の自然数でもかまわない。
function bpow( B, P ) {
    var power;
    if( typeof P == "number" ) power = P;
    else if( typeof P == "object") power = b2float( P );
    else return null;

    if( power != Math.floor(power) || power > 2048 || power < 0 ) {
        _debug("[ERROR] inadequate power at function bpow(): power=" + power );
        return null
    }

    // 3乗までは直接計算する
    if( power == 0 ) {
        if( babscmp( B, [0] ) == 0 ) return [ 0 ];
        else return [ 1 ];
    } else if( power == 1 ) return B;
    else if( power == 2 ) return bmul( B, B );
    else if( power == 3 ) return bmul( bmul( B, B ), B );

    // powerを2進展開する
    var bin_str = power.toString(2);
    var max = bin_str.length - 1;
    var bin_digit = new Array();
    for( var i=0; i<=max ; i++ ) {
        bin_digit[i] = bin_str.charAt( max - i );
    }

    // Bの2^n乗を計算する
    var _B = new Array(); // 配列の配列
    _B[0] = B; // 最初の要素はB自身
    for( var n = 1; n <= max; n++ ) {
        _B[n] = bmul( _B[ n-1 ] , _B[ n-1 ] );
    }

    var Ret = [ 1 ];
    for( var i = 0; i < bin_digit.length; i++ ) {
        if( bin_digit[i] == 1 ) Ret = bmul( Ret, _B[i] );
    }

    return Ret;
}

例題: 2, 4, 8, 16, 32, ... という2倍2倍で増えてく数列には誰しも興味を持つものだが、1000項めまでいくどどのくらい大きくなるだろうか?

2¹⁰⁰⁰を計算するには、bpow( [2], [1000] ) を実行する。結果は次の通り。

10 71508 60718 62673 20948 42504 90600 01810 56140 48117 05533 60744 37503 88370 35105 11249 36122 49319 83788 15695 85812 75946 72917 55314 68251 87145 28569 23140 43598 45775 74698 57480 39345 67774 82423 09854 21074 60506 23711 41877 95418 21530 46474 98358 19412 67398 76755 91655 43946 07706 29145 71196 47768 65421 67660 42983 16526 24386 83720 56680 69376.（302桁）

Netscape4.79上での計算時間 43.542 秒であった。

ちなみに JavaScriptの組み込み関数 Math.pow( 2 , 1000 ) を用いると結果は
1.0715086071862673e+301
であって最初の十数桁しか分からない。したがって正確な値が必要なときは、独自の「BigInt」を使う必要がある。

商と余り

巨大整数B1をB2で割ったときの商と余り。JavaScript組み込みの浮動小数点演算で商を計算し、その商が正確かどうか、すでに構成してある bmul で逆算検証する。誤差があった場合、残差がゼロになるまで同様に逐次近似をつづける。

function bdivmod( B1, B2 ) {

    var sign2 = bsign( B2 );

    // 第0近似
    var _Q = _b2fdiv2b( B1, B2 );

    var _R = new Array();

    var step;

    for( step=1; step<100; step++ ) {

        // 剰余を求める
        _R = bsub( B1, bmul( B2, _Q ) );

        // 剰余が非負で割る数B2より絶対値が小さければ計算終了
        if( bsign( _R ) >=0 && babscmp( _R, B2 ) < 0 ) return [ _Q, _R ];

        // しからざれば ...
        if( sign2 >= 0 || step%2==0 ) {
            // 残差をB2で割った商を足して_Qを補正
            _Q = badd( _Q, _b2fdiv2b( _R, B2 ) );
        } else {
            // 負数で割る場合、商+1も試さねばならない
            _Q = badd( _Q , [1] );
        }
    }
    _debug("[Error] Too many steps at function bdivmod: _R=" + bshow(_R));
    return null;
}

B2が負の場合の上の実装はアドホックで効率が悪い。けれど負の数で割ることは、あまりないので、とりあえず次へ進む。

下請け関数 _b2fdiv2b は、BigInt形式の巨大整数2つを引数にとって、floatで割り算した整数商をふたたびBigInt形式で返す。

function _b2fdiv2b( B1, B2 ) {
    return bset(   Math.floor( b2float(B1)/b2float(B2) ).toString()   );
}

ところでJavaScriptで浮動小数点演算を行うと、2.2220000222222167e+53のような形式で返ることがあるから、bset() は、この形式の文字列を解釈できるように拡張されなければならない。

    var part = str.match(/^(\-?)(\d+)\.(\d+)e([\+|\-]\d+)/i);
    if(part) {
        var power = eval( part[4] );
        if( power < 0 ) return "0";

        // part[3] の右端に必要なだけ文字0をつなげる
        // もしpart[3]がe10をかけても小数部分があるなら、小数部分は捨てる
        var c;
        var ret = "";
        for( var i=0; i < power; i++ ) {
            c = part[3].charAt(i) || "0" ;
            ret += c;
        }

        ret = part[2].toString() + ret;
        // マイナス符号
        if( part[1] ) ret = part[1] + ret;

        return ret;
    }

上記はさしあたって必要なロジックであり、すべての科学記法形式の数値をパースできるわけではないので注意。この拡張によって下請け関数は正常に仕事をすることができるから、結局、巨大整数の割り算が実装された。

function bdiv( B1, B2 ) {
    var result = bdivmod( B1, B2 );
    return result[0];
}

function bmod( B1, B2 ) {
    var result = bdivmod( B1, B2 );
    return result[1];
}

bdiv と bmod は同じ関数 bdivmod のラッパーだから、商と余りの両方が必要なときには、個別に呼ばず、直接 bdivmod を呼べば同じ計算を2回しないですむ。bdivmod は配列を返す。第0要素が整数商、第1要素が剰余。負の数の除法でも剰余は0以上になるようにしてある。戻り値もBigInt形式だから、通常の形式で表示するには、bshow を使う。

例題 2⁵⁹-1 は素数か?

本来のJavaScriptでは2⁵³までの数しか扱えないので、2⁵⁹-1を扱うにはBigIntが必要である。ただし、
2⁵⁹-1 = 576 46075 23034 23487
は10進18桁もあるので、かたっぱしから割ってみる方法では、運が良くないと途方もなく時間がかかる。10万以下には因数がない（この検証には約4分かかった）。あきらめずに10万～20万の範囲を検証してみる:

var A=bset("2"), B=bset("59"), C=bset("1");
var N = bsub( bpow( A, B ), C );
var I;

document.write("<p>Checking whether it is divisible by:<br>");
for(var i=100001; i<200000; i+=2 ) {
    if(i%1000==1) document.write( "" + (i-1) + " ...<br>");

    if(i%3==0||i%5==0||i%7==0||i%11==0||i%13==0||i%17==0||i%19==0||
    i%23==0||i%29==0||i%31==0||i%37==0||i%41==0||i%43==0||i%47==0||
    i%53==0||i%59==0||i%61==0||i%67==0||i%71==0||i%73==0||i%79==0||
    i%83==0||i%89==0||i%93==0||i%97==0||i%101==0||i%103==0||i%107==0||
    i%109==0||i%113==0||i%127==0||i%131==0||i%137==0||i%139==0||i%149==0)continue;

    var I = bset( i.toString() );

    if( bmod( N, I ) == 0 ) {
        document.write( " <strong>" + i + "</strong> found!</p>" );
        break;
    }
}

このスクリプトは試行範囲を刻々とフィードバックしながら計算をつづけ、やがて因数 179951 を発見する。2⁵⁹-1 は合成数であり、
2⁵⁹-1 = 179951×320 34317 80337
と分解される（これは bdiv, bmod を使って一瞬で確認できる）。

累乗（るいじょう）の剰余

「高校数学で遊ぶ公開鍵暗号RSA」でみたように「6943¹⁴⁷¹⁹を17441で割った余り」とか、そんな感じでもっと巨大な指数計算の余りを計算したいことがよくある。bpow で巨大な累乗を作ってから bmod をとるのでは効率が悪くて使い物にならないので、専用の関数 bpowmod を準備しておく。

// BのP乗をmodで割ったときの余りを求める
// P, mod はBigInt形式でも数値でもかまわない。
function bpowmod( B, P, mod ) {
    if( !isBigInt(B) ) return null;

    var power;
    if( typeof P == "number" ) power = P;
    else if( typeof P == "object") power = b2float( P );
    else return null;

    if( power != Math.floor(power) || power < 0 ) {
        _debug("[ERROR] inadequate power at function bpowmod(): power=" + power );
        return null
    } else if( power > Math.pow(2, 52) ) {
        _debug("[NOT IMPLEMENTED YET] a big power at function bpowmod(): power=" + power );
        return null
    }

    var M = new Array();
    if( typeof mod == "number" ) M = bset( mod.toString(10) );
    else if( isBigInt( mod ) ) M = bcopy( mod );
    else return null;

    var fmod = b2float( M );
    // modは2以上でなければならない
    if( fmod <= 1 ) {
        _debug("[ERROR] inadequate mod at function bpowmod(): mod=" + bshow(M) );
        return null
    }

    // 0乗と1乗は直接計算
    if( power == 0 ) {
        if( babscmp( B, [0] ) == 0 ) return [ 0 ];
        else return [ 1 ];
    } else if( power == 1 ) return bmod( B, M );

    // powerを2進展開する
    var bin_str = power.toString(2);
    var max = bin_str.length - 1;
    var bin_digit = new Array();
    for( var i=0; i<=max ; i++ ) {
        bin_digit[i] = bin_str.charAt( max - i );
    }

    // Bの2^n乗をMで割った剰余計算する
    var _B = new Array(); // 配列の配列
    _B[0] = bmod( B, M );
    for( var n = 1; n <= max; n++ ) {
        _B[n] = bmod( bmul( _B[ n-1 ] , _B[ n-1 ] ) , M );
    }

    var Ret = [ 1 ];
    for( var i = 0; i < bin_digit.length; i++ ) {
        if( bin_digit[i] == 1 ) Ret = bmod( bmul( Ret, _B[i] ), M );
    }

    return Ret;
}

例題: 6943¹⁴⁷¹⁹を17441で割った余りを求めよ。

「高校数学で遊ぶ公開鍵暗号RSA」では手動で計算したが、ここまでの準備があれば、たった一行のスクリプト
var answer = bpowmod( [6943], [14719], [17441] );
を実行するだけでいい。答は4980。

結び

JavaScriptでも、こんな感じで実験数学（とくに初等整数論関係の実験）のためのべんりな「道具箱」を用意してゆくことができる。ざっと走り書きしたライブラリ関数のうち主なものを一覧表にしておく。これを使えば通常のJavaScriptでは不可能な大きな数の加減乗除などを自由に行える。巨大整数は自動的に必要なだけの幅を確保してそこに格納される（内部的な格納形式について知っている必要はない）。

問題

これらのライブラリ関数を使って、32ビット、64ビット……等々の比較的強いRSA暗号をJavaScriptで実装する。

この記事のURL

• https://yosei.fi/articles/5/25/#d20525a

bigint_0_4.js 概要

2002年 5月30日
記事ID d20530

BigIntライブラリは、JavaScriptで2⁵³を越える巨大整数とそうでない整数とを一括して扱えるようにする。

document.write( Math.pow( 7, 20 ) ); //  79792266297612000
document.write( Math.bpow( 7, 20 ) ); // 79792266297612001

上の例では 7²⁰ を計算している。JavaScript の組み込み関数 Math.pow では精度が失われる。BigIntライブラリをインクルードすることによって使用可能になる Math.bpow メソッドは、正確な答を返す。

以下は古い記事（bigint.js v0.4）です。 はるかに高速化された bigint.js v0.5 をごらんください。

簡易リファレンス (ver.0.4)

Bigintオブジェクト o が表す整数のことを、簡単のため、その整数と同一視して「整数o」とか言うことがある。これは正確には、オブジェクト o が表現している整数のことです。

objBigint = new Bigint( arg )

巨大整数オブジェクトを生成するコンストラクタ。arg は文字列でも数値でも良い。文字列では、数字以外の文字は無視されるので、適当にスペースを入れて書いてもかまわない。小数点以下も無視される。頭のマイナス符号は認識される。数値の場合、JavaScriptの数値として評価される。20桁の整数を表す objBigを生成する例:
objBig = new Bigint("1234567890 55555 00000")

Bigint.n( arg )

new演算子を使わないで書きたい場合に使う。例えば、Bigint.n( 1 ) は、整数値1と等価な無名オブジェクトを返す。objBig に 1 を足したいとき、1 を表す名前のあるオブジェクトをわざわざ作らずに、
Bigint.add( objBig, Bigint.n( 1 ) )
とするとができる。実際には、Bigintメソッドの強力な型変換機能により、
Bigint.add( objBig, 1 )
と書いてかまわない。

objBigint.toString(radix)

オブジェクトを文字列に変換する。radix を省略した場合、適当に桁ごとに区切った10進数が返る。これは、そのまま最終的な出力をするのに適した形である。戻り値を eval で10進数の数値に変換できることが保証されるためには、radix = 10 を明示することが必要であり、かつ戻り値が数値としてJavaScriptで扱える範囲であることで必要充分となる。radix = 2 で2進展開される。JavaScript自身の toString(2) と違って、大きな数でも最後の桁まで正確に展開する。.toString() メソッドは JavaScript の同名メソッドを上書きしない。Bigintオブジェクトに対してこのメソッドが呼ばれたときに限って、ここに書いたようになる。BigIntライブラリをインクルードしただけで、すべての toString が巨大整数対応版になるわけではない。2 または 10 以外の radix を指定した場合の動作は未定義。用例は下記デモページにあります。

objBigint.negative()

符号が反対の整数に対応したオブジェクトを返す。objBigintは、Bigintオブジェクトでなければならない。

objBigint.sign()

オブジェクトが表す整数の符号を調べる。正なら1、負なら-1、ゼロなら0を返す。objBigintは、Bigintオブジェクトでなければならない。

objBigint.abs()

オブジェクトが表す整数と絶対値が等しく符号が正の整数に対応するオブジェクトを返す。objBigintは、Bigintオブジェクトでなければならない。

objBigint.getDigits()

オブジェクトが表す整数が10進表記で何桁か？の整数を返す。objBigintは、Bigintオブジェクトでなければならない。

Bigint.cmp(o1, o2)

o1, o2が表す整数を符号も含めて大小比較。前者が大きければ1、後者が大きければ-1、等しければ0を返す。o1, o2は、Bigintオブジェクトであってもなくてもかまわない。数値でも文字列でも勝手に解釈してBigintに変換される。そして戻り値は必ずBigintオブジェクトだ。以下の関数で、Bigintオブジェクトを入れるべきところは、全部、数値や数値を表す文字列を入れても正しく動作することが保証される。

Bigint.equal(o1, o2)

2つのオブジェクトが表す整数が等しければ true、さもなければ false を返す。用例は下記デモページに。

Bigint.add(o1, o2), Bigint.sub(o1, o2), Bigint.mul(o1, o2)

2オブジェクトが表す整数の和、差、積に対応する新しいオブジェクトを返す。

Bigint.div(o1, o2), Bigint.mod(o1, o2)

2オブジェクトの整数商と剰余のオブジェクト。ここで剰余は0以上o2になるように整数商ともども選ばれる。負の数の割り算のときには注意。

Bigint.divmod(o1, o2)

2オブジェクトの整数商と剰余のオブジェクトを長さ2の配列でいっぺんに返す。商と剰余が両方必要なときは、この関数を呼んだ方が効率がよい。

Bigint.pow(o1, o2)

o1のo2乗を返す。

Bigint.powmod(o1, o2, o3)

o1のo2乗をo3で割った余りを返す。指数が巨大のとき、Bigint.pow(o1, o2)を実際に計算させてから、modをとるのは、非現実的に効率が悪い。必ず専用関数 powmod を使う。

Math.badd, Math.bsub, Math.bmul, Math.bdiv, Math.bmod, Math.bpow, etc.

JavaScript組み込みのMathオブジェクトに、これらのメソッドが追加される。これらのメソッドの引数は、数値、数値を表す文字列、Bigintオブジェクトのいずれでもかまわない。Mathオブジェクトに追加されるこれらのメソッドは数値を表記した文字列を返す。その文字列がJavaScriptの数値として評価できる範囲内であれば、そのままJavaScriptの数値として用いることもできるが、とりあえず文字列なので、例えば +1 と書くと、末尾に文字としての1がくっつく。一見ふべんなようだが、そもそも JavaScript では表現できない整数値を文字列で書くという発想なのだから、文字列なのは当然。どうしても数値でほしければ、b2float を使えるが、精度は保証されない。Mathオブジェクトへのメソッド追加は、あくまで余興というか、ちょっと試す用。Bigintオブジェクトのメソッド（戻り値もBigintオブジェクト）のほうが、連続して使い倒せる。

履歴

これまでの履歴については、「JavaScriptで巨大整数演算」参照。

以前のバージョンであった手続き的な関数（説明はリンク先参照）もいちおう使えるはずだが、よく確かめていない。上のメソッドにもバグがありうるし、たぶんあるだろう。

機能実演

bigint_0_4。このページを開くと、2つの巨大整数の積を計算します。次に得られた積を2番目の数で割って、1番目の数に戻るか検算します。同じことをオブジェクト指向的な方法と手続き的な方法の2通りに実行します。コードはデモページに掲載。（所要時間: 1秒未満）

この開発テスト版ライブラリを、お手元のローカル環境から使うには、次の例のようにするか、または、bigint_0_4.jsをダウンロードしてください。

<!-- ライブラリを呼び出す -->
<script type="text/javascript"
 src="http://m17n.cool.ne.jp/demo/bigint/bigint_0_4.js"></script>
<script type="text/javascript">
// 試したいコードを書く

var a = Math.pow( 2, 100 );
var b = Math.bpow( 2, 100 );
_debug( "2の100乗は、JavaScript自身によると、" + a );
_debug( "でも、正確な値は、" + b );

</script>

この記事のURL

• https://yosei.fi/articles/5/25/#d20530

64-bit RSA by JavaScript

2002年 5月28日
記事ID d20528

2002年に、64ビットのミニミニRSAを作ってみたときのメモです。 しだいに発展して、2004年には1024ビットに達しましたが、 そこまで行くために解決しなかったいろいろな問題を記録しておくために、 この古い記事も残しておきます。 「JavaScript: 触って分かる公開鍵暗号RSA」（2004年2月）を先に読まれたほうが、 全体が分かりやすいかもしれません。

初めに

「高校数学で遊ぶ公開鍵暗号RSA」ではRSA暗号のロジックを紹介した。「JavaScriptでPGPもどき」では実際に24-bitのRSAを実装してみせた。24-bitでは弱すぎて実用にならないが、ロジックを理解するには役立った。今回は64-bitの鍵を構築してみせる。この実験によって、実装上の現実的問題のいくつかが実感できるだろう。

64ビットのRSAは絶対的には強くないのだが、JavaScriptでこれを実装した場合、JavaScript自身ではクラックできないほどの強さになる。自分で作ったものであるけれど自分でも壊しかたが分からないほど頑丈になる、ということだ。以下の説明を読むとなんとなく意味が実感できると思われる。24ビットの場合は、JavaSciript自身で因数の全数検索をすれば、たちまち鍵が割れてしまったので、この違いは重要である。

RSAの基礎的なことは、「高校数学で遊ぶ公開鍵暗号RSA」で説明してある。以下では、基礎的な部分の説明は繰り返さない。

2⁵³の壁

JavaScriptの組み込み変数では扱える整数の最大値が 2⁵³ であるから、より強い暗号強度を使うには、まず巨大整数の四則演算等を自前で実装しなければならない。この問題については「JavaScriptで巨大整数演算」で扱った。そこで作っておいた badd, bsub, bmul, bdiv, bpow 等を使って実装を進める。これらのライブラリ関数は必ずしも最適化されておらず、かなり遅いが、とりあえず動くことは動く。

ところで、2⁵³ というのは、
9 00719 92547 40992
であって、10進数で16桁である。64ビットの鍵を使うときには、例えば
15864 09681 24704 19570^{17023 51553 19066 68755} ( mod 24552 16349 47175 97467 )
のように20桁の数を「20桁の数」乗して、それを20桁の数で割る……といった計算が必要なので、JavaScript自身の整数型では、まったくまにあわない。なお「20桁の数」乗、というのは20乗ではない。上の例でいえば、
15864 09681 24704 19570 を 17023 51553 19066 68755回、かけあわせる
のである。

このような計算では、指数を2進数展開したものを使うと効率が良いことは、すでに示した。ところで手元の Netscape 4.79 では、2進数表示に変換するメソッド .toString(2) の壁が 2⁵³ でなく 2³² あたりにある（メモ1）。いずれにせよ、10進20桁の数を2進数表示に変換するのは .toString(2) ではまにあわないので、自力でやる必要がある。

function radix2( arg ) {
    var N = new Array();
    if( isBigInt( arg ) ) N = bcopy( arg );
    else N = bset( arg.toString() );

    var f = b2float( N );
    var digit = Math.ceil( Math.log( f ) / Math.log( 2 ) );

    while(1) {
        var P = bset(digit-1);
        var test = b2float(      bdiv( N, bpow([2],P) )      );
        if( test >= 2 ) digit++;
        else if( test < 1 ) digit--;
        else break;
    }

    var Power = new Array(digit);

    for( var i=0; i<=digit-1; i++ ) {
        if( i==0 ) Power[i] = [1];
        else Power[i] = bmul( Power[i-1] , [2] );
    }

    var R = bcopy( N );
    var ret = "";
    for( var power = digit-1; power >= 0; power-- ) {
        var X = Power[ power ];
        var Q = bdiv( R , X );

        if(b2float(Q)==1) {
            ret += "1";
            R = bsub( R, X );
        } else {
            ret += "0";
        }
    }
    return ret;
}

これ以外については、24ビットの場合のコードの＋－×÷％等の演算を、badd, bsub, bmul, bdiv, bmod といった巨大整数対応版で置き換えるだけで良い。

このスクリプトは、IE、Mozilla、Netscapeのどれでも動作する。

64ビット鍵の生成

これは数秒で実行できる。

64ビットの鍵の長さということは、だいたい32ビットの素数を2つ見つけて掛け算をすることになる。そのために、まず2つの乱数を発生させなければならない。鍵生成においてどこから「いきのいい」乱数を持ってくるか？というのは重要なポイントだが、ここでは単純に組み込み関数 Math.random() を使っている。

乱数をタネにして、その周辺の奇数のなかに素数がないか、あさる。このロジックは24ビット版と同じだ。 64ビットの場合、鍵を構成する素数は32ビット、つまり10進10桁であるが、このくらいの大きさなら、総当たりで素数判定するのが簡単だし、いちばん高速でもある。しかし、もっと桁数が大きくなると、実際に割ってみる方法で素数性を確認するのでは、破綻する。「確率的」な素数検定が必要になる。また、53ビットの壁を越えた割り算の場合、現バージョンの bdiv はとても遅いことに注意する。

ともかく、今のコンピュータ（2002年）だと、10桁程度の数は単純な総当たりでさくっと素因数分解できる。

そういうわけだから、64ビット鍵を構成するための32ビット程度の素数について、それが本当に素数かどうか確認するのは、総当たり割り算で良い。

しかし、いったん２素数をかけて64ビット鍵（10進20桁）を得ると、今度は、総当たりでもとに戻すのはコスト的に非現実になる。これはRSAの核心をミニチュア版ながら、かいまみせてくれる。例えば、
第一の素数 P = 52682 42677
第二の素数 Q = 60009 18397
が素数であることは1秒程度で確認できるが、それらをかけた合成数
PQ = 31614 29440 02698 28769
をもとに戻すのは、桁違いなコストを要する。実際、i=3 から始めて i=50億以上までループしなければ、分解できない。やってみれば分かるが、1億どころか10万程度でもけっこう大変だ。50億といったら一晩かかっても、たぶん一週間かかってもJavaScriptでは、分解できないかもしれない。しかし、bmul( P, Q ) は1秒未満のコストで計算できる。素因数分解が計算量的に一方通行である、という観念は、こういうことを表している ―― もっとも「どんな方法を使っても素因数分解は難しい」ということが証明されているわけでは、ない。

暗号化と暗号解除

例えば64ビットのRSA公開鍵 N = 20978 37388 62382 78843 , α = 48408 91627 を使って文章 p を暗号化するには、まず p をα乗して、次にそれを N で割った余りを求める。この演算の逆算は、素因数分解のアルゴリズムと計算量的に同値であると信じられている。つまり、これも一方通行であろう、ということだ。p^α mod N は10秒オーダーの時間で計算できるけれど、「逆算」は桁違いに難しい。強引に総当たり的に逆算するには、N=1から始めてその20桁の数まで順々に入れて、α乗してNで割った余りがその数と同じになるまで調べるわけだが、あまりにコストが高い。しかし、もし N が素因数分解できれば、次に示す秘密鍵βを簡単に決定できるので、「素因数分解がどのくらい素早くできるか？」と「RSA暗号をどのくらいの手間で破れるか？」は密接に関連している。

秘密鍵βを作るアルゴリズムは、すでに前の記事で説明した。上の例では
β = 17231 12278 06360 67683
であり、暗号化されている数値をβ乗してNで割れば、最初の p に戻る。

より強い鍵について

鍵の長さを64ビットより大きくすると、鍵を作るために素数を見つけることが困難になる。128ビットなどだと、素数の値もJavaScriptの限界である2⁵³を越える。64ビットよりさらに強い暗号をJavaScript上で構成するには、そうした問題を克服しなければならない。鍵自体は、がんばれば128ビットでも256ビットでも、作れるかもしれないが、その鍵を使って暗号化したり暗号を解除する計算はコストが高い。

ただ、今回の64ビット版は、とりあえず動くことは動く、という段階なので、まだまだ高速化の可能性はある。

「一方通行」の特徴づけ

「掛け算は易しいが、素因数分解は難しい」つまり「2素数PとQをかえて積Nを得るのは易しいが、Nだけ与えられてPとQに分解するのは難しい」ということは、次のように特徴づけることができる。

ふつうに素因数分解をしようとしたら、i=2, 3, 5, 7,... と小さい数で次々と割ってゆく。Nが分解されるまでには、最悪 √N まで割り算を続けなければならない。つまり、Nの素因数候補は、おおざっぱに √N 個ある。したがって、鍵の長さが10進数表示で2桁長くなるごとに、素因数の候補は10倍になる（総当たりで検索しなければならないときの検索範囲が10倍になる）。10進の鍵の長さが10のときと12のときでは、12のほうが10倍強い。14ならさらに10倍、16ならさらに10倍……。だから、10桁の鍵と20桁の鍵というのは、長さの違いは2倍でも、とんでもなく ―― 具体的には1万倍も ―― 強度が違う。前者が1日でクラックできるとしても後者は数十年かかるのだ。

このように、素因数分解の計算量は、鍵の長さがちょっと長くなるごとに、「指数関数的」に増大する。よく「計算量が多項式時間で抑えられない」などと言い表すのは、この現象を思い浮かべると、とりあえずイメージがわくであろう。

多項式時間ということを、ものすごくくだいて言うなら、「鍵を作るのと同じくらい、鍵をやぶるのも難しい」といことだ。現実的に言うと、「そんな複雑な暗号を構成できるプログラムが作れるなら、当然、その暗号を解読するプログラムも作れる」というような計算だ。これは「双方向的」な話である。

すでに見たように、公開鍵暗号では、等しい知識量（秘密鍵を知らない状態）において、暗号化と暗号解除の計算量は双方向的ではなく、一方通行的である。暗号化の計算は、確かに桁数がのびると大変になるが、それをクラックする計算は、さらに急激な勢いで大変になる。最初に24ビットRSAを構成して、今回64ビットRSAを構成してみせた。24に比べると64は、かなりややこしいし、計算量も多くなる。が、24→64で暗号化がややこしくなったのと、24→64でクラックが困難になったのとは、比例していない。24→64で、暗号化コストが10倍くらいになったかもしれないけれど、クラックのコストは数万倍、ひょっとして数億倍、JavaScript自身の範囲では事実上、不可能なほどに困難になった。

コンピュータが発達して性能が10倍、100倍になったとしても、鍵をちょっと長くするだけで、RSAは「逃げる」ことができる。もし計算量が「多項式的」だったなら、コンピュータの性能があがると逃げ切れずに一発でクラックされてしまう。

鍵の長さと難しさは、比例でも2乗に比例でも3乗に比例でも……なく、指数関数の関係にある、と考えられている。例えば、強度を10倍にするのにコストは2倍、ふんぱつして10倍のコストを負担すれば、いっきょに100億倍の強さが得られる……といったぐあいで、第三者による暗号解読を妨害する、という意味では「安上がりで意地悪ができる」わけだ。敵が予算を100倍に増やして総攻撃をしかけてきても、こっちは予算を2倍にふやすだけで、対応できる。

（ただし、素因数分解が桁数の増加に対して絶対に指数関数的に難しくなるのか？というと、数学的には、そうだとも、そうでないとも証明されてない。ひょっとすると、奇跡的に素因数分解ができるアルゴリズムが存在するかもしれないのだ。）

多項式時間でおさまるかどうか？というのは、計算量の絶対的な指標でなく、相対的な指標である。攻撃者が攻撃力を100倍に増強していどんできたときに、こっちは2倍の増強で対応できる ―― 敵が一万倍になっても、こっちは数倍の増強で対応できる ―― と、このような相対的力関係になっているなら、その暗号系は頑強だろう。敵が一万倍に戦力増強してくるときというのは、それなりにコンピュータのハードも発達しているわけだろうから、防衛力強化のためのリソース配備は、実際には経済的な負担にならない。これは、Windows 95 の32MBマシンと、Windows 2000 の数百倍高性能なマシンが、ほとんど同じ経済的な値段で手に入った、という事実からも、納得ができるだろう。関係ないけどLinuxならタダだしね。

世界最高のコンピュータと、ふつうのPCの能力差は、単に多項式的である。100倍のお金を払えば100倍程度のリソースは得られるだろうが、リソースは払ったお金と比例（ないし多項式関係）にある。充分に強い暗号は、世界最速のコンピュータと実在する限りの無制限のリソースを使っても、解読できない。

以上の説明は必ずしも厳密でないのだが、参考になる面もあると思われる。

メモ1

2002-05-28 Netscape 4のJavaScriptの奇妙な動作。JavaScript で n.toString(2) は数値 n を2進数表記した文字列を返す。しかし、Netscape 4 では 2³² 以上、言い換えれば2進32桁以上の文字列が生ずべき場合に、正しく変換できないばかりか、
/0/0/0/0//000000/00000//000/0/0
のような奇妙な文字列を返すことがある。'1' (0x31) と '0' (0x30) からなる列を返すべきときに '/' (0x2F) が返るのは、「繰り上がりすぎて」オーバーランしているものと思われる。オーバーフロー時のエラー処理ルーティンがちゃんとなってないようだ。IEおよびMozillaでは、この問題は生じない。ただし 2⁵³ を越えると変換で精度が失われるが、これは JavaScript の一般的な制限である。

リンク

• JavaScript: 触って分かる公開鍵暗号RSA (2004-02-04)

この記事のURL

• https://yosei.fi/articles/5/25/#d20528

前 5‒24 p ｜ もくじ i ｜ 次 5‒26 n

• このページに関するご連絡は、下記メールアドレスへお願いします。
• このウェブサイトは、都合により、まもなく終了します。書いてあった情報は、特に断り書きがない限り、自由に使ってください。そのまま転載しても、書き換えたりして再利用してもかまいません。
• 記事の中には情報が古くて現状と合っていないものや、不正確な点を含むものが あるかもしれません。修正が必要と思われる点がありましたら、お気軽にお知らせください。