phpでsha1ハッシュ値を自力計算できた！やっている事はmd5と基本的に同じだったので、九割方コピペで行けるな…。

admin

5年前

いいものじゃないわよ。md5ハッシュ値の自力演算なんて…。phpは論理シフトも出来ないし、unsigned intも使えないし、大変だよ。(今回は、任意の文字列)　まさかメッセージの長さだけビッグエンディアンだったとは…。日本語サイトも英語サイトも分かったふうな解説ばかりで、キモの部分の説明がない！

md5とsha1の違い
1, ハッシュ値のサイズが違う
MD5: 128bit(16byte)=32文字
SHA1: 160bit(20byte)=40文字
※初期値となるWORDも、1WORD増えている

2, 1block = 64byteなのは同じ

3, メッセージの長さ(ビット数)を、最後の８バイトに入れるのは同じ
MD5: 下位WORD(4byte)+上位WORD(4byte)
SHA1: 上位WORD(4byte)+下位WORD(4byte) 通常のビッグエンディアン

4, bit演算の回数が違う
MD5: 1ブロックにつき64回(16*4種類のビット演算)
SHA1: 1ブロックにつき80回(20*4種類のビット演算)

5, kテーブル(ビット演算に使うkeyを格納するテーブル)が違う
MD5: abs(sin(1radから64rad)) * 0xffffffffで、0から2^32の間の4byteワードを64個も生成する
SHA1: 以下の４種類だけ
0x5A827999, /* 0～19回目の演算で使用 */
0x6ED9EBA1, /* 20～39回目の演算で使用 */
0x8F1BBCDC, /* 40～59回目の演算で使用 */
0xCA62C1D6 /* 60～79回目の演算で使用 */

6, バイトオーダーが違う
MD5: リトルエンディアン(メッセージのビット数だけビッグエンディアン)
SHA1: ビッグエンディアン(ハッシュの初期値となる5WORDだけは、リトルエンディアン)

7, ビット演算が、それなりに違う。
最初に各ブロックの64byteを配列に格納して、ひたすらビット演算を繰り返す感じ。
後から作られただけあって、それなりにシンプルに仕上がっている気がする！(表などの数列が少なくなっている)

<?php

// 英数字記号(ダブルクオーテーションと￥はややこしいから抜き)
// 文字列をバイナリ化表記にして、最後に1を付与
$message = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 !#$%&'()-^@[;:],./\=~|`{+*}<>?_";
$message = "";
$hex_str = bin2hex($message) . "80";

// メッセージサイズを取得(メッセージ最後を表す１byte(80)の分はマイナスしておく)
$message_size = (strlen($hex_str)/2)-1;

// 末尾８バイトに付与するメッセージの長さは、ビット数で表現する
// なぜか、ここだけビッグエンディアンで表現する…。数値だからか？
// MD5とは違って、下位ビットを先にしない
$message_bit_size_dword = sprintf("%016x", $message_size * 8);


// 64byte単位でブロック化する。足らない部分は0詰め
// 1byteが2文字なので、割る2してバイト数を算出。
for($i=0; $i < ((strlen($hex_str)/2) % 64); $i++){
    $hex_str .= "00";
}

// 最後の8byteに、メッセージのサイズ(ビット数)を格納
$hex_str = substr($hex_str, 0, strlen($hex_str)-16) . $message_bit_size_dword; 

// メッセージ文字列をバイナリに変換
$input_data = str_hex2word($hex_str);

// 画面にバイト列を表示
for($iBlock=0; $iBlock<count($input_data); $iBlock++){
    for($i=0; $i<16; $i++){
        printf("0x%08x<br>\n", $input_data[$iBlock][$i]);
    }
}

// ハッシュ値の元になる5WORD(リトルエンディアンだと逆になる)=20byte
$a0 = 0x67452301;   //A
$b0 = 0xefcdab89;   //B
$c0 = 0x98badcfe;   //C
$d0 = 0x10325476;   //D
$e0 = 0xC3D2E1F0;   //E MD5には無かった第5WORD

// ブロック単位で処理
for($iBlock=0; $iBlock<count($input_data); $iBlock++){

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

    // 1block = 64byte
    for($i=0; $i<80; $i++){
        if( 0 <= $i && $i < 20){
            $F = ($B & $C) | ((~$B) & $D);
            $k_table_data = 0x5A827999;    /*  0～19回目の演算で使用 */       
        }else if( 20 <= $i && $i < 40){
            $F = $B ^ $C ^ $D;
            $k_table_data = 0x6ED9EBA1;    /*  20～39回目の演算で使用 */

        }else if(40 <= $i && $i < 60){
            $F = ($B & $C) | ($B & $D) | ($C & $D) ;
            $k_table_data = 0x8F1BBCDC;    /*  40～59回目の演算で使用 */

        }else if(60 <= $i && $i < 80){
            $F = $B ^ $C ^ $D;
            $k_table_data = 0xCA62C1D6;    /*  60～79回目の演算で使用 */
        }

        // 各回で演算に使う値を算出
        if( 0 <= $i && $i < 16){
            // 各ブロックの全ワード(4byte*16)
            $w[$i] = $input_data[$iBlock][$i]; 
        }else if( 16 <= $i && $i < 80){
            // それ以降は、ビット演算を繰り返す
            $w[$i] = leftrotate( ($w[$i-3] ^ $w[$i-8] ^ $w[$i-14] ^ $w[$i-16]) , 1);
        }

        // 各ワードを演算しながら、スライドする
        $dTemp = leftrotate($A, 5) + $F + $E + $w[$i] + $k_table_data;
        $E = $D;
        $D = $C;
        $C = leftrotate($B, 30);
        $B = $A;
        $A = $dTemp;

    }

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

// 最終結果を表示。sha1()関数と比較してみる。
echo sprintf("%08x", $a0). 
     sprintf("%08x", $b0). 
     sprintf("%08x", $c0). 
     sprintf("%08x", $d0). 
     sprintf("%08x", $e0).  "<br>";

echo sha1($message)."<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);
}


// 64byte単位でブロック分けして配列で返す。
function str_hex2word ($dec){

    // 64byte単位でブロック分けする
    for($iBlock=0; $iBlock<(strlen($dec)/128); $iBlock++){
        // 64byte * 2文字(FF) = 128文字
        $block = sprintf("%s", substr($dec, $iBlock*128, 128));

        unset($arr_block); //NULL

        // 1block毎に4byte単位で、文字列から数値に変換(ffffffff→約43億)
        for($i=0; $i<(strlen($block)/8); $i++){
            // phpでは、unsigned intが扱えないのでintval()だと負数になる(計算で算出)
            $hex = sprintf("%s", substr($block, $i*8, 8));
            $word = intval(substr($hex, 6, 2),16) * pow(256, 0) +
                    intval(substr($hex, 4, 2),16) * pow(256, 1) +
                    intval(substr($hex, 2, 2),16) * pow(256, 2) +
                    intval(substr($hex, 0, 2),16) * pow(256, 3);
            $arr_block[] = $word;
        }
        $ret[] = $arr_block;
    }
    return $ret;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

<?php

// 英数字記号(ダブルクオーテーションと￥はややこしいから抜き)

// 文字列をバイナリ化表記にして、最後に1を付与

$message = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 !#$%&'()-^@[;:],./\=~|`{+*}<>?_";

$message = "";

$hex_str = bin2hex($message) . "80";

// メッセージサイズを取得(メッセージ最後を表す１byte(80)の分はマイナスしておく)

$message_size = (strlen($hex_str)/2)-1;

// 末尾８バイトに付与するメッセージの長さは、ビット数で表現する

// なぜか、ここだけビッグエンディアンで表現する…。数値だからか？

// MD5とは違って、下位ビットを先にしない

$message_bit_size_dword = sprintf("%016x", $message_size * 8);

// 64byte単位でブロック化する。足らない部分は0詰め

// 1byteが2文字なので、割る2してバイト数を算出。

for($i=0; $i < ((strlen($hex_str)/2) % 64); $i++){

$hex_str .= "00";

}

// 最後の8byteに、メッセージのサイズ(ビット数)を格納

$hex_str = substr($hex_str, 0, strlen($hex_str)-16) . $message_bit_size_dword;

// メッセージ文字列をバイナリに変換

$input_data = str_hex2word($hex_str);

// 画面にバイト列を表示

for($iBlock=0; $iBlock<count($input_data); $iBlock++){

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

printf("0x%08x<br>\n", $input_data[$iBlock][$i]);

}

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

$a0 = 0x67452301; //A

$b0 = 0xefcdab89; //B

$c0 = 0x98badcfe; //C

$d0 = 0x10325476; //D

$e0 = 0xC3D2E1F0; //E MD5には無かった第5WORD

// ブロック単位で処理

for($iBlock=0; $iBlock<count($input_data); $iBlock++){

$A = $a0; //A

$B = $b0; //B

$C = $c0; //C

$D = $d0; //D

$E = $e0; //E

// 1block = 64byte

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

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

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

$k_table_data = 0x5A827999; /* 0～19回目の演算で使用 */

}else if( 20 <= $i && $i < 40){

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

$k_table_data = 0x6ED9EBA1; /* 20～39回目の演算で使用 */

}else if(40 <= $i && $i < 60){

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

$k_table_data = 0x8F1BBCDC; /* 40～59回目の演算で使用 */

}else if(60 <= $i && $i < 80){

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

$k_table_data = 0xCA62C1D6; /* 60～79回目の演算で使用 */

}

// 各回で演算に使う値を算出

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

// 各ブロックの全ワード(4byte*16)

$w[$i] = $input_data[$iBlock][$i];

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

// それ以降は、ビット演算を繰り返す

$w[$i] = leftrotate( ($w[$i-3] ^ $w[$i-8] ^ $w[$i-14] ^ $w[$i-16]) , 1);

}

// 各ワードを演算しながら、スライドする

$dTemp = leftrotate($A, 5) + $F + $E + $w[$i] + $k_table_data;

$E = $D;

$D = $C;

$C = leftrotate($B, 30);

$B = $A;

$A = $dTemp;

}

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

$a0 = $a0 + $A;

$b0 = $b0 + $B;

$c0 = $c0 + $C;

$d0 = $d0 + $D;

$e0 = $e0 + $E;

}

// 最終結果を表示。sha1()関数と比較してみる。

echo sprintf("%08x", $a0).

sprintf("%08x", $b0).

sprintf("%08x", $c0).

sprintf("%08x", $d0).

sprintf("%08x", $e0). "<br>";

echo sha1($message)."<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);

}

// 64byte単位でブロック分けして配列で返す。

function str_hex2word ($dec){

// 64byte単位でブロック分けする

for($iBlock=0; $iBlock<(strlen($dec)/128); $iBlock++){

// 64byte * 2文字(FF) = 128文字

$block = sprintf("%s", substr($dec, $iBlock*128, 128));

unset($arr_block); //NULL

// 1block毎に4byte単位で、文字列から数値に変換(ffffffff→約43億)

for($i=0; $i<(strlen($block)/8); $i++){

// phpでは、unsigned intが扱えないのでintval()だと負数になる(計算で算出)

$hex = sprintf("%s", substr($block, $i*8, 8));

$word = intval(substr($hex, 6, 2),16) * pow(256, 0) +

intval(substr($hex, 4, 2),16) * pow(256, 1) +

intval(substr($hex, 2, 2),16) * pow(256, 2) +

intval(substr($hex, 0, 2),16) * pow(256, 3);

$arr_block[] = $word;

}

$ret[] = $arr_block;

}

return $ret;

}

関連記事