<?xml version="1.0" encoding="utf-8" ?>

<?xml-stylesheet type="text/xsl" href="../test.xsl"?>


<article  format="2002.0312">

<article_head>
	<article_id>d20524</article_id>
	<article_date><year>2002</year><month>05</month><day>24</day></article_date>
	<article_addr><sect>5</sect><subsect>24</subsect></article_addr>
	<article_subj>JavaScriptでPGPもどき</article_subj>
</article_head>

<article_body>
<p>
「<a href="/articles/5/24/#d20523">高校数学で遊ぶ公開鍵暗号RSA</a>」につづき、理解深めるために、JavaScript上でごく小さいRSAを実装してみる。
さらに大規模な実装例は次を参照:<br />
<a href="http://www.faireal.net/demo/PigPGP/">http://www.faireal.net/demo/PigPGP/</a>
</p>

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

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

<pre class="box">
function _debug( message ) {
    document.write( &quot;&lt;p&gt;Debug: &quot; + message + &quot;.&lt;\/p&gt;&quot; );
}

function isPrime( number ) {

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

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

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

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

var MAX_STEPS = 10000;
</pre>

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

<pre class="box">
var strength = 24;
if(strength&lt;24 || strength%2!=0 ) strength = 24;
_debug( strength + &quot;-bit RSA&quot;);

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 &lt; min ) seed += min;
if( seed % 2 == 0 ) seed += 1;
_debug( &quot;seed = &quot; + seed );

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

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

}

_debug(&quot;p = &quot; + p );
_debug(&quot;q = &quot; + q );
_debug(&quot;n = &quot; + n );

_debug( &quot;log&lt;sub&gt;2&lt;/sub&gt;n = &quot; + log2( n ) );

//isPrime( n );

</pre>

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

<pre class="box">
function gcd( a, b ) {

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

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

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

        r0 = r1, r1 = r;
    }

    _debug( &quot;gcd(&quot; + a + &quot;, &quot; + b + &quot;) = &quot; + r1 );

    return r1;
}

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

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

var alpha = v;
_debug(&quot;alpha = &quot; + alpha);

</pre>


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

<pre class="box">
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&gt;0 &amp;&amp; i&lt;MAX_STEPS; i++) {
    var tmp = t0 - q * t;

    if( tmp &gt;= 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(&quot;beta = &quot; + beta);
else _debug(&quot;[ERROR] beta not exists&quot;);

_debug(&quot;log2(alpha*beta) = &quot; + log2(alpha*beta) );
_debug(&quot;alpha*beta (mod u) = &quot; + alpha*beta%u);
</pre>

<h4>鍵生成完了</h4>

<pre class="box">

document.write(&quot;&lt;dl&gt;&quot;);
document.write(&quot;&lt;dt&gt;Public Key&lt;\/dt&gt;&quot;);
document.write(&quot;&lt;dd&gt;n = &quot; + n + &quot; , alpha = &quot; + alpha + &quot;&lt;\/dd&gt;&quot;);
document.write(&quot;&lt;dt&gt;Secret Key&lt;\/dt&gt;&quot;);
document.write(&quot;&lt;dd&gt;beta = &quot; + beta + &quot;&lt;\/dd&gt;&quot;);
document.write(&quot;&lt;\/dl&gt;&quot;);

</pre>


<h4>暗号化</h4>
<p>生成された公開鍵を使って3つのサンプルを暗号化する。</p>
<p>暗号化指数αは大きいから、累乗は分けて計算する必要がある。</p>

<pre class="box">
var sample1 = 123, sample2 = 7743, sample3 = n-5;
/*
n=17441,
alpha=7,
beta=14719;
sample1=4980;
sample2=1234;
*/

_debug(&quot;sample1 = &quot; + sample1 );
_debug(&quot;sample2 = &quot; + sample2 );
_debug(&quot;sample3 = &quot; + sample3 );

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

for(var i=0; i&lt;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&lt;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( &quot;sample1 encrypted: &quot; + e1 );

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

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

</pre>

<h4>暗号解除</h4>
<p>秘密指数βを使って暗号を解除する。</p>

<pre class="box">

var beta_bin = beta.toString(2);

var D_beta = new Array();

for(var i=0; i&lt;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&lt;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( &quot;sample1 decrypted: &quot; + d1 );

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


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

</pre>

<h4>demo</h4>
<p>以上のリストを実際に走らせた結果（<a href="/etc/rsa_0_1.js">rsa_0_1.js</a>を動的に実行）:</p>

<script type="text/javascript" src="/etc/rsa_0_1.js"></script>
<noscript>
<p>JavaScriptが有効であれば、この場でデモを実行できます。<a href="/etc/rsa.js">ソースを確認</a>することもできます。</p>
</noscript>

<!--
<h4>追記</h4>
<p>64ビットの鍵の長さをJavaScriptで実現することに成功した。詳細は「<a href="/articles/5/25/#d20528">64-bit RSA by JavaScript</a>」。</p>
-->
<h4>リンク</h4>


<ul class="book">

<li>
<a href="/articles/8/01/#d40204">JavaScript: 触って分かる公開鍵暗号RSA</a> <span class="date">(<strong>2004-02-04</strong>)</span>
</li>
</ul>

</article_body>
</article>
