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

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


<article  format="2002.0312">

<article_head>
	<article_id>d31206</article_id>
	<article_date><year>2003</year><month>12</month><day>06</day></article_date>
	<article_addr><sect>8</sect><subsect>23</subsect></article_addr>
	<article_subj>楕円曲線暗号と攻撃のデモ (2)</article_subj>
</article_head>

<article_body>
<p>
JavaScript で小さな楕円曲線暗号を実装する遊びを続けよう。
</p>

<p>
以下では 10進5桁の法 10007 と 位数 10091 （素数）を持つ楕円曲線暗号系を構成する。
Mozilla の上で<em class="pale">（注: Mozilla の JavaScript は遅い）</em>正規のユーザは、この暗号系を10ミリ秒オーダーの処理時間で利用できるが、
brute attack を行う攻撃者は10000ミリ秒オーダーのコストを要求される。</p>

<p>
さらに、構成過程は明示しないが、
10進6桁の法 100493 と位数 100673 （素数）を持つ系でも実演を行う。
正規ユーザの計算量はほとんど変わらないのに対して、
brute attack で攻撃すると、1分近くかかる。
</p>

<p>
<a href="/articles/8/23/#d31204">2桁、3桁、4桁の鍵長についての前回の実験</a>と合わせると、
おおざっぱに10進10桁でクラックは困難になり、20桁程度で一応の実用強度に達すると予想される。
うわさどおり、RSAより短い鍵長で同等の暗号強度を実現できそうだ、という実感がわく。
もちろんJavaScriptではもともと遅いということもあるが、
比較の対象とするRSAもJavaScript上で構築したのだから、
この比較は合理的だ。
</p>

<h4>どのようにして素数位数の群を見つけるか</h4>

<p>
10進5桁のオーダーでは、以下の方法が効果的だった。
</p>
<p>
まず、その上に楕円曲線をはわせる有限体の法を決めてしまう。ここでは素数10007を選んだ。
10進5桁の最小の素数である。あとは、楕円曲線の定義式を少しずつ変化させて、位数が素数になるようにすればよい。
具体的には、次のようにした。
</p>

<p>
<var>C</var> : y<sup>2</sup> = x<sup>3</sup> + 9973x + B (mod 10007)<br />
とおいて、1次の係数 9973 （勝手に選んだ）も固定してしまう。この楕円曲線 <var>C</var> の点の数は、
<a href="http://en2.wikipedia.org/wiki/Elliptic_curve" title="Wikipedia::Elliptic curve">Hasse(-Weil)の定理</a>によって、<br />
(10007 + 1) ± 2(10007)<sup>1/2</sup><br />
の範囲にある。9807.93以上、10208.07以下である。
</p>

<p>
位数が素数になるとしたら、<var>C</var>上の無限遠点以外の任意の点をその素数倍したとき、結果は無限遠点となるわけだが、
この素数は上記の範囲になければならないから、具体的には次のいずれかだ:
</p>

<pre>
var MyPrimes = [
    9811, 9817, 9829, 9833, 9839, 9851, 9857, 9859, 9871, 9883,
    9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973,
    10007, 10009, 10037, 10039, 10061, 10067, 10069, 10079, 10091, 10093,
    10099, 10103, 10111, 10133, 10139, 10141, 10151, 10159, 10163, 10169,
    10177, 10181, 10193
];
</pre>

<p>
ゆえに、無限遠点以外の <var>C</var> の勝手な元を一つ選んで、
どれかの i について MyPrimes[i] 倍して無限遠点が得られたなら、
それが、望む位数である。
逆に、そのような結果を生じさせる素数が MyPrimes リストにないなら、
その群の位数は、素数ではない。
なぜなら、位数は9807.93以上、10208.07以下であることが保証されているが、
その範囲の素数についてすべての可能性が潰れたなら、結局、（有限体の）位数はその範囲にあるどれかの非素数ということになるからだ（選んだ元自身の位数は、それと等しいか、またはその約数）。
「ある元の位数は群の位数の約数」というLagrangeの定理──または、同じことだが「素数位数の群では、すべての元の位数が群の位数と同じ素数」という性質──に注意する。
</p>
<p>
例えば、 <var>C</var> の定数項を8000から8100へと変化させて、位数が素数になる場所がないか捜索するには、次のリストを使えばよい。
</p>

<p>
findPoint を使って点を一つ見つけて <var>test</var> と名づける。
 <var>C</var> の右辺が平方剰余か非剰余かは恐らく確率50%ずつなので、
xを1以上100未満まで変化させるときの失敗確率は2<sup>-99</sup>であって、事実上、必ず点が見つかる。
次に、 <var>test</var> を MyPrimes[i] 倍して、どれかの i について無限遠点になったら成功であり、
それが望む位数である。どの i についても駄目だったら望むような曲線ではないから、<var>C</var> の定数項を変えて再試行する。
</p>

<pre>
function ECC( a, b, modulus ) {
    this.a = a;
    this.b = b;
    this.modulus = modulus;
}

ECC.prototype.findPoint = function( _x ) {
    if( _x === void 0 ) {
        for( var x = 1; x &lt; 100 &amp;&amp; x &lt; this.modulus; x++ ) {
            var oPoint = this.findPointAt( x );
            if( oPoint !== void 0 ) return oPoint;
        }
    } else {
        return this.findPointAt( _x );
    }
}

ECC.prototype.findPointAt = function( _x ) {
    var x = reduce( _x , this.modulus );
    var X3 = ( x * x % this.modulus ) * x % this.modulus;
    var AX = this.a * x % this.modulus;
    var R = reduce( ( X3 + AX + this.b ), this.modulus );
    for( var y=0; y &lt; this.modulus / 2; y++ ) {
        var L = reduce( y * y,  this.modulus );
        if( L === R ) {
            return new ECCPoint( x , y );
        }
    }
    return void 0;
}

ECC.prototype.getPrimeOrder = function() {
    var test = this.findPoint();
    for( var i=0; i&lt;MyPrimes.length; i++ ) {
        var Result = this.multiply( test, MyPrimes[i] );
        if( Result.isO() ) {
            return MyPrimes[i];
        }
    }
    return void 0;
}

for(var B=8000; B&lt;8100; B++ ) {
    var objECC = new ECC( 9973, B, modulus );
    var order = objECC.getPrimeOrder();
    if( order === void 0 ) {
        _debug( objECC + &quot; is bad.&quot; );
    } else {
        _debug( objECC + &quot; is good: order = &quot; + order + &quot; (prime)&quot; );
        break;
    }
}
</pre>

<p>
このオーダーの数だと、だいたい50試行に1回は、素数位数をもたらす曲線が見つかる。
1分もかからずに簡単に曲線が見つかるのである。
定数項を8000から8200に変化させるだけで次のようにいっぱい見つかり、よりどりみどりだ。
</p>

<pre>
y^2 = x^3 + 9973 * x + 8044 (mod 10007) is good: order = 10141 (prime)
y^2 = x^3 + 9973 * x + 8070 (mod 10007) is good: order = 10169 (prime)
y^2 = x^3 + 9973 * x + 8100 (mod 10007) is good: order = 9887 (prime)
y^2 = x^3 + 9973 * x + 8108 (mod 10007) is good: order = 10091 (prime)
y^2 = x^3 + 9973 * x + 8142 (mod 10007) is good: order = 10111 (prime)
y^2 = x^3 + 9973 * x + 8148 (mod 10007) is good: order = 9941 (prime)
y^2 = x^3 + 9973 * x + 8179 (mod 10007) is good: order = 10093 (prime)
y^2 = x^3 + 9973 * x + 8180 (mod 10007) is good: order = 9887 (prime)
y^2 = x^3 + 9973 * x + 8191 (mod 10007) is good: order = 9941 (prime)
</pre>

<p>
この例では、<br />
y<sup>2</sup> = x<sup>3</sup> + 9973x + 8108 (mod 10007)<br />
を選択した。
</p>

<h4>暗号系の完成</h4>
<p>
鍵交換を行う楕円曲線暗号系をこれで作るには、あとは曲線上の勝手な点を一つ選んで「合意の点」とすればよい。
使う曲線さえ決まれば、あとはたいした計算量ではない。
このデモでは、
(5755, 4233) を選択した。
</p>

<h4>ソースと実演</h4>

<p>
注意: 正規利用者のシミュレーションは一瞬ですが、
暗号をクラックしようとする攻撃者のシミュレーションに数秒から数十秒かかる場合があります。
</p>
<p>
<a href="/demo/libecc_0.1.js">http://www.faireal.net/demo/libecc_0.1.js</a>
</p>
<p>
<a href="/demo/ecc3">http://www.faireal.net/demo/ecc3</a> （鍵 ～10000）
</p>
<p>
<a href="/demo/ecc3a">http://www.faireal.net/demo/ecc3a</a> （鍵 ～50000）
</p>
<p>
<a href="/demo/ecc3b_users">http://www.faireal.net/demo/ecc3b_users</a> （鍵 ～100000）正規ユーザのデモ（一瞬）
</p>

<p>
<a href="/demo/ecc3b">http://www.faireal.net/demo/ecc3b</a> （鍵 ～100000）攻撃を行うデモ（時間がかかります）
</p>
<h4>
展望
</h4>
<p>
10進3桁までの場合と異なり、実際に点を数え上げる方法では、10進4桁では時間がかかりすぎる。
例えば法が1万なら、もしかしたら曲線上にあるかもしれない、
という点の候補は1万×1万で1億もあり、仮に平均4分の1調べればよいとしても数千万の点を実際に調べることになって、
コストが大変だ。今回使った特定の元の位数を利用する方法だと、10進7桁くらいまではいけそうだ。
また、決まった点に、ある特定範囲のスカラーを繰り返しかけるのだから、そのたびごとに繰り返し二乗法を実行するのでなく、
1度だけ繰り返し二乗法で Work[i] を決めてしまったら、その曲線を調べ終わるまで、それを固定して使いまわすことでも、
少し計算量が節約できるはずだ。
</p>

<p>
いずれにしても、このオーダーでは、実際の楕円曲線暗号の運用自体はきわめて容易であり、
問題になるのは運用すべき楕円曲線のパラメータを決定する準備の部分なのである。
</p>

</article_body>
</article>
