MD5のハッシュ値計算を関数md5()を使わずに、phpで１から実装してみた。phpでビット演算なんてするもんじゃないな…。

この頃、パスワードとかでハッシュ値を使う事が多かったので、ハッシュ値の原理を理解するためにも自力で実装してみたくなった。
データを大きな素数で割るって説明はよく見るけど、それだとハッシュ値が固定(128ビット=16バイト)なのもよく分からんし…。

参考URL
https://ja.wikipedia.org/wiki/MD5
http://bkclass.web.fc2.com/doc_md5.html

を見ながら、模擬コードをPHPに落とし込む。
最初は大変だから、空文字(“”)固定で算出してみた。
マジカルナンバー(ビットシフトする数)が出てきて、何故この数字を使うんだ！？
※雪崩効果(入力が1bitでも変わったら、ハッシュが平均で半分以上変わる)を最大にするためのビットシフト数らしい。どうやって求めたんだ？
この処理をすると、なぜハッシュ値が偏らない(クラスタ化しない)のかは不明のままだけど、とりあえずPHPで実装出来たので満足！

<?php

// abs(sin(1radから64rad)) * 0xffffffffで、0から2^32の間の4byteワードを64個も生成する
$k_table = [
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
];
// ビットシフトする数。どこから求めているのか謎！
// こちらも64個ある
$s_table = [
    //雪崩効果(入力が1bitでも変わったら、ハッシュが平均で半分以上変わる)を最大にするためのビットシフト数らしい。どうやって求めたんだ？
    // 以下のように1の繰り返し(1bit左シフトするだけ)でも、それなりに雪崩効果はある。
    // 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
   7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,  7, 12, 17, 22,
   5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,  5,  9, 14, 20,
   4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,  4, 11, 16, 23,
   6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21,  6, 10, 15, 21
];

// 長さ0の文字列(パッティングにより512ビット=64byte化されている)
// 各ワードをリトルエンディアン化する必要があるので、0x80000000 → 0x00000080 となっている
$input_data = [
    0x00000080, //1ワード目(パッティングの一番最初には1を入れる。0x80=b1000-0000)
    0x00000000, //2ワード目(それ以降は0詰め)
    0x00000000, //3ワード目
    0x00000000, //4ワード目
    0x00000000, //5ワード目
    0x00000000, //6ワード目
    0x00000000, //7ワード目
    0x00000000, //8ワード目
    0x00000000, //9ワード目
    0x00000000, //10ワード目
    0x00000000, //11ワード目
    0x00000000, //12ワード目
    0x00000000, //13ワード目
    0x00000000, //14ワード目
    0x00000000, //15ワード目(ここから先16byteは、元のメッセージのサイズ領域)
    0x00000000, //16ワード目(今回は空文字なので0)
];
// ハッシュ値の元になる4WORD(リトルエンディアンだと逆になる)
/* 
$a0 = 0x01234567;   //A
$b0 = 0x89abcdef;   //B
$c0 = 0xfedcba98;   //C
$d0 = 0x76543210;   //D
*/
$a0 = 0x67452301;   //A
$b0 = 0xefcdab89;   //B
$c0 = 0x98badcfe;   //C
$d0 = 0x10325476;   //D

$A = $a0;   //A
$B = $b0;   //B
$C = $c0;   //C
$D = $d0;   //D

// 1block = 64byte
for($i=0; $i<64; $i++){
    if( 0 <= $i && $i < 16){
        $F = ($B & $C) | ((~$B) & $D);
        $index = $i;
    
    }else if( 16 <= $i && $i < 32){
        $F = ($D & $B) | ((~$D) & $C);
        $index = (5 * $i + 1) % 16; // 0-15をシャッフルっぽい感じに並び替える

    }else if(32 <= $i && $i < 48){
        $F = ($B ^ $C) ^ $D;
        $index = (3 * $i + 5) % 16; // 0-15をシャッフルっぽい感じに並び替える

    }else if(48 <= $i && $i < 64){
        $F = $C ^ ($B | (~$D));
        $index = (7 * $i) % 16; // 0-15をシャッフルっぽい感じに並び替える
    }
    $dTemp = $D;
    $D = $C;
    $C = $B;
    // 1巡目は、各ワードは順番(0-15)
    // 2巡目以降は、各ワードは飛び飛びに見えるが、ちゃんと0-15をすべて持ってきている！
    $B = $B + leftrotate(($A + $F + $k_table[$i] + $input_data[$index]), $s_table[$i]);
    $A = $dTemp;
}

//今までの結果に、このブロックの結果を足す
$a0 = $a0 + $A;
$b0 = $b0 + $B;
$c0 = $c0 + $C;
$d0 = $d0 + $D;


echo big2little($a0) ."<br>";
echo big2little($b0) ."<br>";
echo big2little($c0) ."<br>";
echo big2little($d0) ."<br>";
echo big2little($a0) .big2little($b0) .big2little($c0) .big2little($d0)."<br>";
echo "d41d8cd98f00b204e9800998ecf8427e(空文字のMD5ハッシュ)<br>";


//左ローテート関数
function leftrotate ($x, $c){
    $left_shift = $x << $c;
    $right_shift = $x >> (32-$c);
    // PHPは算術シフトしかないので、シフトした分だけビットマスクする用のビット列を生成
    $bit_mask = pow(2, $c)-1;

    // 左シフトビット列と、32(ワードのビット数)-シフトビット数だけ右シフトしたビット列をor演算すれば、左ローテートになる
    return $left_shift | ($right_shift & $bit_mask);
}
//printf("0x%08X<br>\n", leftrotate(0xff00ff00, 1));

// 4btye専用のビッグエンディアン→リトルエンディアン
function big2little ($dec){
    $hex = sprintf("%08x", $dec);
    $ret =  substr($hex, 6, 2) .
            substr($hex, 4, 2) .
            substr($hex, 2, 2) .
            substr($hex, 0, 2) ;         
    return $ret;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

<?php

// abs(sin(1radから64rad)) * 0xffffffffで、0から2^32の間の4byteワードを64個も生成する

$k_table = [

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

];

// ビットシフトする数。どこから求めているのか謎！

// こちらも64個ある

$s_table = [

//雪崩効果(入力が1bitでも変わったら、ハッシュが平均で半分以上変わる)を最大にするためのビットシフト数らしい。どうやって求めたんだ？

// 以下のように1の繰り返し(1bit左シフトするだけ)でも、それなりに雪崩効果はある。

// 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,

5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,

4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,

6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21

];

// 長さ0の文字列(パッティングにより512ビット=64byte化されている)

// 各ワードをリトルエンディアン化する必要があるので、0x80000000 → 0x00000080 となっている

$input_data = [

0x00000080, //1ワード目(パッティングの一番最初には1を入れる。0x80=b1000-0000)

0x00000000, //2ワード目(それ以降は0詰め)

0x00000000, //3ワード目

0x00000000, //4ワード目

0x00000000, //5ワード目

0x00000000, //6ワード目

0x00000000, //7ワード目

0x00000000, //8ワード目

0x00000000, //9ワード目

0x00000000, //10ワード目

0x00000000, //11ワード目

0x00000000, //12ワード目

0x00000000, //13ワード目

0x00000000, //14ワード目

0x00000000, //15ワード目(ここから先16byteは、元のメッセージのサイズ領域)

0x00000000, //16ワード目(今回は空文字なので0)

];

// ハッシュ値の元になる4WORD(リトルエンディアンだと逆になる)

$a0 = 0x01234567; //A

$b0 = 0x89abcdef; //B

$c0 = 0xfedcba98; //C

$d0 = 0x76543210; //D

$a0 = 0x67452301; //A

$b0 = 0xefcdab89; //B

$c0 = 0x98badcfe; //C

$d0 = 0x10325476; //D

$A = $a0; //A

$B = $b0; //B

$C = $c0; //C

$D = $d0; //D

// 1block = 64byte

for($i=0; $i<64; $i++){

if( 0 <= $i && $i < 16){

$F = ($B & $C) | ((~$B) & $D);

$index = $i;

}else if( 16 <= $i && $i < 32){

$F = ($D & $B) | ((~$D) & $C);

$index = (5 * $i + 1) % 16; // 0-15をシャッフルっぽい感じに並び替える

}else if(32 <= $i && $i < 48){

$F = ($B ^ $C) ^ $D;

$index = (3 * $i + 5) % 16; // 0-15をシャッフルっぽい感じに並び替える

}else if(48 <= $i && $i < 64){

$F = $C ^ ($B | (~$D));

$index = (7 * $i) % 16; // 0-15をシャッフルっぽい感じに並び替える

}

$dTemp = $D;

$D = $C;

$C = $B;

// 1巡目は、各ワードは順番(0-15)

// 2巡目以降は、各ワードは飛び飛びに見えるが、ちゃんと0-15をすべて持ってきている！

$B = $B + leftrotate(($A + $F + $k_table[$i] + $input_data[$index]), $s_table[$i]);

$A = $dTemp;

}

//今までの結果に、このブロックの結果を足す

$a0 = $a0 + $A;

$b0 = $b0 + $B;

$c0 = $c0 + $C;

$d0 = $d0 + $D;

echo big2little($a0) ." ";

echo big2little($b0) ." ";

echo big2little($c0) ." ";

echo big2little($d0) ." ";

echo big2little($a0) .big2little($b0) .big2little($c0) .big2little($d0)." ";

echo "d41d8cd98f00b204e9800998ecf8427e(空文字のMD5ハッシュ) ";

//左ローテート関数

function leftrotate ($x, $c){

$left_shift = $x << $c;

$right_shift = $x >> (32-$c);

// PHPは算術シフトしかないので、シフトした分だけビットマスクする用のビット列を生成

$bit_mask = pow(2, $c)-1;

// 左シフトビット列と、32(ワードのビット数)-シフトビット数だけ右シフトしたビット列をor演算すれば、左ローテートになる

return $left_shift | ($right_shift & $bit_mask);

}

//printf("0x%08X \n", leftrotate(0xff00ff00, 1));

// 4btye専用のビッグエンディアン→リトルエンディアン

function big2little ($dec){

$hex = sprintf("%08x", $dec);

$ret = substr($hex, 6, 2) .

substr($hex, 4, 2) .

substr($hex, 2, 2) .

substr($hex, 0, 2) ;

return $ret;

}

関連記事