mojalog

MD5のコードリーディングをしてみました。
MD5 メッセージダイジェストアルゴリズムに日本語訳されたRFCが載っていて非常に参考になりました。Cのソースも載っているんだけど、今回は高度なjavascript集から拾ってきて、読みながら書いてみながらいじくり回してみました。

firebugで１ステップずつ見ていきながら、この処理ではsin関数（ソースではあらかじめ値をsinTbl配列に書き出してあります）がでてきて、ここはパディング処理が出てきて、ここはMD5アルゴリズムとは関係ないjavascript的な言語仕様的な解決ね・・・・てのはわかるんだけど、だからどうして衝突しづらいハッシュ値が得られるのかはさっぱりわからん。プログラマの癖にわからないと駄目だろ的なところから読み始めたんだけどまぁわからん。
sin関数で得られる６４個の値は（視覚的に言うと「〜」←こんな値ね）（絶対値でつかってるからマイナスに振れたやつは正の値になってるけど）なんなの？とか。
メッセージダイジェストのバッファ初期値はなんでこういう並びなの？とか

01 23 45 67
89 ab cd ef
fe dc ba 98
76 54 32 10
※ソースではこういう風に使ってる。

        var state = [ 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476 ];

最近、日頃何となく使ってるアルゴリズムの仕組みを知りたくて色々と勉強してるんですけど、公開鍵の仕組みの方がわかりやすくて、この調子でメッセージダイジェストもわかるかなーと思ったんですけど、「このアルゴリズムはこうすると衝突しにくいダイジェストが得られるんです」がわからないです。ちっとも。ヤフー知恵袋にでも投稿してみようか。メッセージダイジェスト（笑）とかいわれるんだろうか（言いません）

var MD5 = {
    utf16to8 : function( str ){
        var retStr = "";
        var len = str.length;
        for( var idx = 0; idx < len; idx++ ){
            var chara = str.charCodeAt( idx );
            if( ( chara >= 0x0001 ) && ( chara <= 0x007F ) ){
                retStr += str.charAt( idx );
            }
            else if ( chara > 0x07FF ){
                retStr += String.fromCharCode( 0xE0 | ( ( chara >> 12 ) & 0x0F ) );
                retStr += String.fromCharCode( 0x80 | ( ( chara >>  6 ) & 0x3F ) );
                retStr += String.fromCharCode( 0x80 | ( ( chara >>  0 ) & 0x3F ) );
            }
            else {
                retStr += String.fromCharCode( 0xC0 | ( ( chara >> 6 ) & 0x1F ) );
                retStr += String.fromCharCode( 0x80 | ( ( chara >> 0 ) & 0x3F ) );
            }
        }
        return retStr;
    },

    sinTbl : [
        0x00000000, 0xd76aa478, 0xe8c7b756, 0x242070db,
        0xc1bdceee, 0xf57c0faf, 0x4787c62a, 0xa8304613,
        0xfd469501, 0x698098d8, 0x8b44f7af, 0xffff5bb1,
        0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e,
        0x49b40821, 0xf61e2562, 0xc040b340, 0x265e5a51,
        0xe9b6c7aa, 0xd62f105d, 0x02441453, 0xd8a1e681,
        0xe7d3fbc8, 0x21e1cde6, 0xc33707d6, 0xf4d50d87,
        0x455a14ed, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9,
        0x8d2a4c8a, 0xfffa3942, 0x8771f681, 0x6d9d6122,
        0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60,
        0xbebfbc70, 0x289b7ec6, 0xeaa127fa, 0xd4ef3085,
        0x04881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8,
        0xc4ac5665, 0xf4292244, 0x432aff97, 0xab9423a7,
        0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d,
        0x85845dd1, 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314,
        0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb,
        0xeb86d391 
    ],

    tblIdx : [
        [ 
            function( x, y, z ){ return ( x & y ) | ( ~x & z ); },
            [
                [ 0, 7, 1],[ 1,12, 2],[ 2,17, 3],[ 3,22, 4],
                [ 4, 7, 5],[ 5,12, 6],[ 6,17, 7],[ 7,22, 8],
                [ 8, 7, 9],[ 9,12,10],[10,17,11],[11,22,12],
                [12, 7,13],[13,12,14],[14,17,15],[15,22,16]
            ]
        ],[
            function( x, y, z ){ return ( x & z ) | ( y & ~z ); },
            [
                [ 1,5,17],[ 6, 9,18],[11,14,19],[ 0,20,20],
                [ 5,5,21],[10, 9,22],[15,14,23],[ 4,20,24],
                [ 9,5,25],[14, 9,26],[ 3,14,27],[ 8,20,28],
                [13,5,29],[ 2, 9,30],[ 7,14,31],[12,20,32]
            ]
        ],[
            function( x, y, z ){ return x ^ y ^ z; },
            [
                [ 5,4,33],[ 8,11,34],[11,16,35],[14,23,36],
                [ 1,4,37],[ 4,11,38],[ 7,16,39],[10,23,40],
                [13,4,41],[ 0,11,42],[ 3,16,43],[ 6,23,44],
                [ 9,4,45],[12,11,46],[15,16,47],[ 2,23,48]
            ]
        ],[
            function( x, y, z ) { return y ^ (x | ~z); },
            [
                [ 0,6,49],[ 7,10,50],[14,15,51],[ 5,21,52],
                [12,6,53],[ 3,10,54],[10,15,55],[ 1,21,56],
                [ 8,6,57],[15,10,58],[ 6,15,59],[13,21,60],
                [ 4,6,61],[11,10,62],[ 2,15,63],[ 9,21,64]
            ]
        ]
    ],

    shift : function( code ){
        return String.fromCharCode( code & 0xff ) +
            String.fromCharCode( ( code >>> 8 ) & 0xff ) +
            String.fromCharCode( ( code >>> 16) & 0xff ) +
            String.fromCharCode( ( code >>> 24) & 0xff );
    },

    rollNum : function( num ){
        while( num < 0 ) num += 4294967296;
        while( num > 4294967295 ) num -= 4294967296;
        return num;
    },

    setRound : function( codeLst, state, func, rndRbn, pos ){

        var _0 = rndRbn[ 0 ];
        var _1 = rndRbn[ 1 ];
        var _2 = rndRbn[ 2 ];
        var _3 = rndRbn[ 3 ];

        var codePos    = pos[ 0 ];
        var shiftValue = pos[ 1 ];
        var curTblIdx  = pos[ 2 ];

        var result = state[ _0 ] + func( state[ _1 ], state[ _2 ], state[ _3 ] ) + codeLst[ codePos ] + MD5.sinTbl[ curTblIdx ];
        result = MD5.rollNum( result );
        result = ( ( result << shiftValue ) | ( result >>> ( 32 - shiftValue ) ) );
        result += state[ _1 ];
        state[ _0 ] = MD5.rollNum( result );
    },

    get128BitDigest : function( data ){

        var state = [ 0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476 ];
        var len = data.length;
        var idx = len & 0x3f;
        var padLen = ( idx < 56 ) ?( 56 - idx ) :( 120 - idx );
        if( padLen > 0 ) {
            data += "\x80";
            for( idx = 0; idx < padLen - 1; idx++ )
                data += "\x00";
        }

        data += MD5.shift( len * 8 );
        data += MD5.shift( 0 );
        len  += padLen + 8;
        var rndRbn = [ 0, 1, 2, 3 ];
        var codeLst = new Array( 16 );
        var tmpStat = new Array( 4 );

        for( var rndCnt = 0; rndCnt < len; rndCnt += 64) {

            for( idx = 0, shiftIdx = rndCnt; idx < 16; idx++, shiftIdx += 4 ) {
                codeLst[ idx ] = data.charCodeAt( shiftIdx ) |
                ( data.charCodeAt( shiftIdx + 1 ) <<  8 ) |
                ( data.charCodeAt( shiftIdx + 2 ) << 16 ) |
                ( data.charCodeAt( shiftIdx + 3 ) << 24 );
            }

            for( idx = 0; idx < 4; idx++ )
                tmpStat[ idx ] = state[ idx ];

            for( idx = 0; idx < 4; idx++ ){
                var func  = MD5.tblIdx[ idx ][ 0 ];
                var block = MD5.tblIdx[ idx ][ 1 ];

                for( shiftIdx = 0; shiftIdx < 16; shiftIdx++ ) {
                    MD5.setRound( codeLst, tmpStat, func, rndRbn, block[ shiftIdx ]);
                    var tmp = rndRbn[ 0 ];
                    rndRbn[ 0 ] = rndRbn[ 3 ];
                    rndRbn[ 3 ] = rndRbn[ 2 ];
                    rndRbn[ 2 ] = rndRbn[ 1 ];
                    rndRbn[ 1 ] = tmp;
                }
            }

            for( idx = 0; idx < 4; idx++ ){
                state[ idx ] += tmpStat[ idx ];
                state[ idx ] = MD5.rollNum( state[ idx ] );
            }
        }
        return MD5.shift( state[ 0 ] ) +
            MD5.shift( state[ 1 ] ) +
            MD5.shift( state[ 2 ] ) +
            MD5.shift( state[ 3 ] );
    },

    getDigest : function( data ) {
        var str = "";
        var bit128 = MD5.get128BitDigest( MD5.utf16to8( data ) );
        for( var idx = 0; idx < 16; idx++ ){
            var chara = bit128.charCodeAt( idx );
            str += "0123456789abcdef".charAt( ( chara >> 4 ) & 0xf );
            str += "0123456789abcdef".charAt( chara & 0xf );
        }
        return str;
    }
}
(function(){
    alert( MD5.getDigest( "test" ) );
    //098f6bcd4621d373cade4e832627b4f6
})();