5 : 24 JavaScriptでPGPもどき

JavaScriptでPGPもどき

2002年 5月24日
記事ID d20524

JavaScriptで「ふつう」に扱える整数は 2⁵³ までである。単純に考えると52ビットまでの鍵を使える。しかし途中計算で積をとったりするので、その半分以下にしたほうが簡単だ。ここでは大きな数の計算を独自に実装することが目的でなく、あくまでRSAをJavaScript上で構築してみるのが目的だからだ（巨大整数の計算については別記事「JavaScriptで1000桁電卓」を参照）。以下では暗号強度を24ビットとする。

最初にいくつかの一般的な関数などを定義しとく。

function _debug( message ) {
    document.write( "<p>Debug: " + message + ".<\/p>" );
}

function isPrime( number ) {

    if( number < 2 || number != Math.floor(number) ) {
        _debug("[ERROR] Unexpected input " + number + " at function isPrime");
        return false;
    }

    for( var i=3; i <= Math.sqrt(number); i+=2 ) {
        if( number % i ==0 ) {
            _debug( number + " divisible by " + i );
            return false;
        }
    }

    _debug( "* " + number + " is prime" );
    return true;
}

function log2( x ) {
    return Math.log( x ) / Math.log( 2 );
}

var MAX_STEPS = 10000;

素数を見つける

鍵を生成するために、2つの素数 p, q を見つける。ミリ秒単位のUnix秒から種を得る。種は一定の値の範囲の奇数になるようにする。素数が見つかるまで2ずつ増やしながら検索をつづける。この方法だと p, q は必ず隣同士の素数になり、n = pq の因数分解が容易になってしまう。しかし24ビットではどっちにせよもともと容易なので、気にしないことにしよう。

var strength = 24;
if(strength<24 || strength%2!=0 ) strength = 24;
_debug( strength + "-bit RSA");

var max = Math.pow( 2, (strength/2) ), min = Math.pow( 2, (strength/2 - 1) );

var objDate = new Date();
var seed = ( objDate.getTime() ) % max;
if( seed < min ) seed += min;
if( seed % 2 == 0 ) seed += 1;
_debug( "seed = " + seed );

var number, p = 0, q = 0, n;
for( var i=0; i<MAX_STEPS; i++ ) {
    number = seed + i*2;

    if( isPrime(number) ) {
        if( p==0 ) p = number;
        else {
            q = number;
            n = p * q;
            break;
        }
    }

}

_debug("p = " + p );
_debug("q = " + q );
_debug("n = " + n );

_debug( "log<sub>2</sub>n = " + log2( n ) );

//isPrime( n );

公開指数を決定する

次に公開指数αを決定する。αは u = (p-1)(q-1) と互いに素でなければならない。そのことを保証するためにあらかじめ (p-1)(q-1) の素因数を調べあげても良いが、ユークリッドの互除法を使ってαとuの最大公約数が1であることを確認したほうが手っ取り早い。

function gcd( a, b ) {

    if( a<1 || b<1 || a!=Math.floor(a) || b!=Math.floor(b) ) {
        _debug("[Error] a=" + a + ", b=" + b + " at function gcd(a, b)");
        return 2;
    }

    var r0=a, r1=b, r=1;

    for( var i=0; i<MAX_STEPS; i++) {
        r = r0 % r1;
        if(r==0) break;

        r0 = r1, r1 = r;
    }

    _debug( "gcd(" + a + ", " + b + ") = " + r1 );

    return r1;
}

var u = (p-1)*(q-1);
_debug("u = " + u );
var v = ( objDate.getTime() ) % max;
if( v < min*1.5 ) v += min*1.5;
if(v%2==0) v+=1;
_debug("v = " + v );

for( var i=0; i<MAX_STEPS; i++ ) {
    if( gcd(u, v) == 1) break;
    else v += 2;
}

var alpha = v;
_debug("alpha = " + alpha);

秘密鍵βを決定する

法 n と公開指数α が求まったので、秘密鍵βを決定することができる。

u=(p-1)*(q-1);
var u0 = u;
var a0 = alpha;

var t0 = 0, t = 1;
var r = u0 % a0;
var q = (u0-r)/a0;

for(var i=0; r>0 && i<MAX_STEPS; i++) {
    var tmp = t0 - q * t;

    if( tmp >= 0 ) tmp = tmp % u;
    else tmp = u - ( (-tmp) % u );

    t0 = t, t = tmp, u0 = a0, a0 = r;
    r = u0 % a0;
    q = (u0-r)/a0;
}

var beta = t % u;

if( a0 == 1 ) _debug("beta = " + beta);
else _debug("[ERROR] beta not exists");

_debug("log2(alpha*beta) = " + log2(alpha*beta) );
_debug("alpha*beta (mod u) = " + alpha*beta%u);

鍵生成完了

document.write("<dl>");
document.write("<dt>Public Key<\/dt>");
document.write("<dd>n = " + n + " , alpha = " + alpha + "<\/dd>");
document.write("<dt>Secret Key<\/dt>");
document.write("<dd>beta = " + beta + "<\/dd>");
document.write("<\/dl>");

暗号化

生成された公開鍵を使って3つのサンプルを暗号化する。

暗号化指数αは大きいから、累乗は分けて計算する必要がある。

var sample1 = 123, sample2 = 7743, sample3 = n-5;
/*
n=17441,
alpha=7,
beta=14719;
sample1=4980;
sample2=1234;
*/

_debug("sample1 = " + sample1 );
_debug("sample2 = " + sample2 );
_debug("sample3 = " + sample3 );

var alpha_bin = alpha.toString(2);
var D_alpha = new Array();

for(var i=0; i<alpha_bin.length; i++) {
    D_alpha[i] = alpha_bin.substr( alpha_bin.length-1 - i , 1 );

}

function encrypt( the_plain ) {

    var Work = new Array();
    var result = 1;
    for(var i=0; i<alpha_bin.length; i++ ) {

        if(i==0) Work[i] = the_plain;
        else Work[i] = Work[i-1]*Work[i-1]%n;

        if( D_alpha[i] == 1 ) {
            result *= Work[i];
            result %= n;
        }
    }

    return result;
}

var e1 = encrypt( sample1 );
_debug( "sample1 encrypted: " + e1 );

var e2 = encrypt( sample2 );
_debug( "sample2 encrypted: " + e2 );

var e3 = encrypt( sample3 );
_debug( "sample3 encrypted: " + e3 );

暗号解除

秘密指数βを使って暗号を解除する。

var beta_bin = beta.toString(2);

var D_beta = new Array();

for(var i=0; i<beta_bin.length; i++) {
    D_beta[i] = beta_bin.substr( beta_bin.length-1 - i , 1 );

}

function decrypt( the_encrypted ) {
    var Work = new Array();
    var result = 1;
    for(var i=0; i<beta_bin.length; i++ ) {
        if(i==0) Work[i] = the_encrypted;
        else Work[i] = Work[i-1] * Work[i-1]%n;

        if( D_beta[i] == 1 ) {
            result *= Work[i];
            result %= n;
        }
    }

    return result;
}

var d1 = decrypt( e1 );
_debug( "sample1 decrypted: " + d1 );

var d2 = decrypt( e2 );
_debug( "sample2 decrypted: " + d2 );


var d3 = decrypt( e3 );
_debug( "sample2 decrypted: " + d3 );

demo

以上のリストを実際に走らせた結果（rsa.jsを動的に実行）: