8 : 23 楕円曲線暗号（ECC）

(1, 3)

(1, 4)

(2, 2)

(2, 5)

(3, 2)

(3, 5)

(4, 1)

(4, 6)

(5, 1)

(5, 6)

(1, 3) あるる

(1, 4) あれれ

(2, 2) きりり

(2, 5) きろろ

(3, 2) さりり

(3, 5) さろろ

(4, 1) たらら

(4, 6) たわわ

(5, 1) ならら

(5, 6) なわわ

(∞, ∞) 無限遠点

あるる×1 = あるる
あるる×2 = あるる + あるる = きりり
あるる×3 = きりり + あるる = ならら
あるる×4 = ならら + あるる = さろろ
あるる×5 = さろろ + あるる = たらら
あるる×6 = たらら + あるる = たわわ
あるる×7 = たわわ + あるる = さりり
...
あるる×11 = あれれ + あるる = 無限遠点

var mod = 307;
var a = 19;
var b = 77;
var Point = new Array();
var index = 0;
Point[ index ] = "(0, 0)";


for(var x = 0; x < mod; x++ ) {
    for(var y = 0; y < mod/2; y++ ) {
        var L = ( y*y ) % mod;
        var R = ( x*x*x + a*x + b ) % mod;
        if( L === R ) {
            var sPoint = "(" + x + ", " + y + ")";
            Point[ ++index ] = sPoint;
            if( y !== 0 ) {
                sPoint = "(" + x + ", " + (mod-y) + ")";
                Point[ ++index ] = sPoint;
            }
            break;
        }
    }
}

_debug("Point.lenght = " + Point.length);

document.write( "<p>" );
for(var i=0; i<Point.length; i++) {
    document.write( "<strong>P<sub>" + i + "<\/sub><\/strong> = " + Point[i] );
    if(i < Point.length-1 ) document.write( ", " );
}
document.write( "<\/p>" );

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

var Order = 331;
var Point = [ "(0, 0)", "(0, 153)", "(0, 154)", "(1, 149)", "(1, 158)", "(6, 10)", "(6, 297)", 
 ... , "(302, 85)", "(302, 222)" ];

var ECCPoint = new Object();
for(var i=0; i<Order; i++ ) {
    ECCPoint[ Point[i] ] = i;

    ECCPoint[i] = new Object();
    ECCPoint[i].index = i;
    ECCPoint[i].coord = Point[i];
    if( Point[i].match(/^\((\d+), (\d+)\)$/) ) {
        ECCPoint[i].x = parseInt( RegExp.$1 );
        ECCPoint[i].y = parseInt( RegExp.$2 );
    } else {
        _debug("ECCPoint: Init Error: " + Point[i] );
        break;
    }
}

function fairy_add( index1, index2 ) {
    index1 = reduce( index1, Order );
    index2 = reduce( index2, Order );

    if(index1 === 0 ) return index2;
    else if(index2 === 0 ) return index1;

    var x1 = ECCPoint[index1].x;
    var y1 = ECCPoint[index1].y;
    var x2 = ECCPoint[index2].x;
    var y2 = ECCPoint[index2].y;
    if( x1 === x2 && y1 !== y2 ) {
        if( (y1+y2) % mod === 0 ) return 0;
        _debug("fairy_add: Something is wrong:"
         + ECCPoint[index1].coord + " : " + ECCPoint[index2].coord );
        return void 0;
    }
    
    var lambda;
    if( x1 === x2 && y1 === y2 ) {
        if( ( 2 * y1 ) % mod === 0 ) return 0;
         else lambda = ( 3*x1*x1 + a ) * rev( 2 * y1 );
    } else {
        lambda = ( y2 - y1 ) * rev( x2 - x1 );
    }
    
    lambda %= mod;

    var x3 = lambda*lambda - x1 - x2;
    var y3 = lambda * (x1-x3) - y1;
    x3 = reduce( x3, mod );
    y3 = reduce( y3, mod );
    var sPoint = "(" + x3 + ", " + y3 + ")";
    
    if( ECCPoint[ sPoint ] === void 0 ) {
        _debug( "fairy_add failed. Dump:"
         + x1 + "," + y1 + "; " + x2 + "," + y2 + "; " +x3 + ", " + y3 + " : lambda=" + lambda );
    }
    return ECCPoint[ sPoint ];
}

function reduce( N , Mod ) {
    if( typeof N !== "number" ) {
        _debug("reduce: " + N + " is " + typeof N );
        return void 0;
    }
    if( N >= 0 ) return N % Mod;
    var k = Math.floor( Math.abs(N) / Mod );
    return ( N + Mod*(k+1) ) % Mod;
}

function rev(N) {
    if( typeof N !== "number" ) {
        _debug("rev: " + N + " is " + typeof N );
        return void 0;
    }

    if( N % mod === 0 ) {
        _debug("rev: Bad input:" + N );
        return void 0;
    }
    
    N = reduce( N, mod );
    
    for( var i = 1; i < mod; i++ ) {
        if( N * i % mod === 1 ) return i;
    }

    _debug( "rev: failed for: " + N );
    return void 0;
}

function fairy_mul( index, N ) {
    if( N === 0 ) return 0;
    else if( N === 1 ) return index;
    var result = index;
    for( var i=2; i<=N; i++ ) {
        result = fairy_add( result, index );
    }
    return result;
}

var PubPointIndex = 8;

_debug("PubPoint: P" + PubPointIndex + " = " + Point[PubPointIndex]);

var SecKeyAlice = 75;
var MaskedKeyAlice = fairy_mul( PubPointIndex, SecKeyAlice );

var SecKeyBob = 234;
var MaskedKeyBob = fairy_mul( PubPointIndex, SecKeyBob );

_debug("MaskedKeyAlice: P" + MaskedKeyAlice + " = " + Point[MaskedKeyAlice]);
_debug("MaskedKeyBob: P" + MaskedKeyBob + " = " + Point[MaskedKeyBob]);

var KeyByAlice = fairy_mul( MaskedKeyBob, SecKeyAlice );
var KeyByBob = fairy_mul( MaskedKeyAlice, SecKeyBob );

_debug("KeyByAlice: P" + KeyByAlice + " = " + Point[KeyByAlice]);
_debug("KeyByBob: P" + KeyByBob + " = " + Point[KeyByBob]);

/*
Debug: PubPoint: P8 = (7, 218)
Debug: MaskedKeyAlice: P26 = (20, 274)
Debug: MaskedKeyBob: P178 = (162, 225)
Debug: KeyByAlice: P217 = (199, 151)
Debug: KeyByBob: P217 = (199, 151)
*/

var test = 8;
for( var i=2; i<Order; i++ ) {
    test = fairy_add( test , 8 );
    if( 26 === test ) {
        _debug("Cracked: SecKeyAlice = " + i );
        break;
    }
}

// Debug: Cracked: SecKeyAlice = 75