Zur Übung und zum Verständnis über die Programmierung mit Bits und Bytes (bitweise Operationen, Bitverschiebung, Bitwertigkeit, Bytereihenfolge, etc) möchte ich mir meine eigene Implementierung eines MD5-Algorithmus zusammenbauen. Leider kommt am Ende nicht das selbe Ergebnis wie bei der Originalfunktion raus.
Ich habe mich der Erklärung des RFC 1321 bedient.
Ich bin mir auch bewusst, dass es im Internet schon teilweise richtige Implementierungen gibt. Doch ich würde gern wissen, wo bei meinem Code der Fehler liegt, da ich afaik alles berücksichtigt habe was im RFC steht
Vielen Dank im Voraus
LG
Ich habe mich der Erklärung des RFC 1321 bedient.
Ich bin mir auch bewusst, dass es im Internet schon teilweise richtige Implementierungen gibt. Doch ich würde gern wissen, wo bei meinem Code der Fehler liegt, da ich afaik alles berücksichtigt habe was im RFC steht
PHP-Code:
<?php //https://tools.ietf.org/html/rfc1321
$little_endian = true; //Bytereihenfolge
$a0 = hexdec("67452301"); //Buffer variables (big endian)
$b0 = hexdec("efcdab89");
$c0 = hexdec("98badcfe");
$d0 = hexdec("10325476");
/*$a0 = hexdec("01234567"); //Buffer variables (little endian)
$b0 = hexdec("89abcdef");
$c0 = hexdec("fedcba98");
$d0 = hexdec("76543210");*/
function F($x, $y, $z){return (($x & $y) | ((~$x) & $z));} //Compression functions
function G($x, $y, $z){return (($x & $z) | ($y & (~$z)));}
function H($x, $y, $z){return ($x ^ $y ^ $z);}
function I($x, $y, $z){return ($y ^ ($x | (~$z)));}
$T = array();
for($i = 1; $i <= 64; $i++){
$T[$i] = floor(abs(sin($i)) * 4294967296);
}
$in = "Hallo, Welt!";
//echo "Input: <strong>".$in."</strong><br>";
$b = ""; //Binary string of input
for($i = 0; $i < strlen($in); $i++){
$byte = decbin(ord(substr($in, $i, 1)));
while(strlen($byte) < 8){ //pad 0's before the byte string while it's length isn't 8
$byte = "0".$byte;
}
$b .= $byte;
}
$b_original = $b; //original binary string
/*
MD5
*/
//1.1 append "1"
$b .= "1";
//1.2 pad with "0" until length is 64 bit smaller than a multiple of 512
while(strlen($b) % 512 != 448){
$b .= "0";
}
//2.1 Append the bit length of input stream in 64 bits
$len_bin = decbin(strlen($b_original));
if(strlen($len_bin) < 64){
while(strlen($len_bin) < 64){
$len_bin = "0" . $len_bin;
}
}else if(strlen($len_bin) > 64){
while(strlen($len_bin) > 64){
$len_bin = substr($len_bin, 1);
}
}
$b_len_low_order_word = substr($len_bin, 32);
$b_len_high_order_word = substr($len_bin, 0, 32);
$b .= $little_endian ?
implode("", array_reverse(splitIntoBytes($b_len_low_order_word))).implode("", array_reverse(splitIntoBytes($b_len_high_order_word))) :
$b_len_low_order_word.$b_len_high_order_word;
//echo $b . "<br>";
$N = strlen($b) / 32; //Number of 32-bit-words, a multiple of 16
//4.3 divide input stream into 512 bit blocks
for($i = 0; $i < ($N/16); $i++){
$block = substr($b, $i * 512, 512); //current 512 bit block
$M = array();
for($j = 0; $j < 16; $j++){ //divide block into 32 bit words
$word = substr($block, $j * 32, 32); //current 32 bit word
$M[$j] = $little_endian ? bindec(implode("", array_reverse(splitIntoBytes($word)))) : bindec($word);
//echo $word . "<br>";
}
$AA = $a0;
$BB = $b0;
$CC = $c0;
$DD = $d0;
echo "Block " . $i+1 . ", before Round 1:<br>A: ".dechex($a0)."<br>B: ".dechex($b0)."<br>C: ".dechex($c0)."<br>D: ".dechex($d0)."<br><br>";
//Round 1 (all values are decimal)
R1($a0, $b0, $c0, $d0, 0, 7, 1);
R1($d0, $a0, $b0, $c0, 1, 12, 2);
R1($c0, $d0, $a0, $b0, 2, 17, 3);
R1($b0, $c0, $d0, $a0, 3, 22, 4);
R1($a0, $b0, $c0, $d0, 4, 7, 5);
R1($d0, $a0, $b0, $c0, 5, 12, 6);
R1($c0, $d0, $a0, $b0, 6, 17, 7);
R1($b0, $c0, $d0, $a0, 7, 22, 8);
R1($a0, $b0, $c0, $d0, 8, 7, 9);
R1($d0, $a0, $b0, $c0, 9, 12, 10);
R1($c0, $d0, $a0, $b0, 10, 17, 11);
R1($b0, $c0, $d0, $a0, 11, 22, 12);
R1($a0, $b0, $c0, $d0, 12, 7, 13);
R1($d0, $a0, $b0, $c0, 13, 12, 14);
R1($c0, $d0, $a0, $b0, 14, 17, 15);
R1($b0, $c0, $d0, $a0, 15, 22, 16);
echo "Block " . $i+1 . ", before Round 2:<br>A: ".dechex($a0)."<br>B: ".dechex($b0)."<br>C: ".dechex($c0)."<br>D: ".dechex($d0)."<br><br>";
//Round 2
R2($a0, $b0, $c0, $d0, 1, 5, 17);
R2($d0, $a0, $b0, $c0, 6, 9, 18);
R2($c0, $d0, $a0, $b0, 11, 14, 19);
R2($b0, $c0, $d0, $a0, 0, 20, 20);
R2($a0, $b0, $c0, $d0, 5, 5, 21);
R2($d0, $a0, $b0, $c0, 10, 9, 22);
R2($c0, $d0, $a0, $b0, 15, 14, 23);
R2($b0, $c0, $d0, $a0, 4, 20, 24);
R2($a0, $b0, $c0, $d0, 9, 5, 25);
R2($d0, $a0, $b0, $c0, 14, 9, 26);
R2($c0, $d0, $a0, $b0, 3, 14, 27);
R2($b0, $c0, $d0, $a0, 8, 20, 28);
R2($a0, $b0, $c0, $d0, 13, 5, 29);
R2($d0, $a0, $b0, $c0, 2, 9, 30);
R2($c0, $d0, $a0, $b0, 7, 14, 31);
R2($b0, $c0, $d0, $a0, 12, 20, 32);
echo "Block " . $i+1 . ", before Round 3:<br>A: ".dechex($a0)."<br>B: ".dechex($b0)."<br>C: ".dechex($c0)."<br>D: ".dechex($d0)."<br><br>";
//Round 3
R3($a0, $b0, $c0, $d0, 5, 4, 33);
R3($d0, $a0, $b0, $c0, 8, 11, 34);
R3($c0, $d0, $a0, $b0, 11, 16, 35);
R3($b0, $c0, $d0, $a0, 14, 23, 36);
R3($a0, $b0, $c0, $d0, 1, 4, 37);
R3($d0, $a0, $b0, $c0, 4, 11, 38);
R3($c0, $d0, $a0, $b0, 7, 16, 39);
R3($b0, $c0, $d0, $a0, 10, 23, 40);
R3($a0, $b0, $c0, $d0, 13, 4, 41);
R3($d0, $a0, $b0, $c0, 0, 11, 42);
R3($c0, $d0, $a0, $b0, 3, 16, 43);
R3($b0, $c0, $d0, $a0, 6, 23, 44);
R3($a0, $b0, $c0, $d0, 9, 4, 45);
R3($d0, $a0, $b0, $c0, 12, 11, 46);
R3($c0, $d0, $a0, $b0, 15, 16, 47);
R3($b0, $c0, $d0, $a0, 2, 23, 48);
echo "Block " . $i+1 . ", before Round 4:<br>A: ".dechex($a0)."<br>B: ".dechex($b0)."<br>C: ".dechex($c0)."<br>D: ".dechex($d0)."<br><br>";
//Round 4
R4($a0, $b0, $c0, $d0, 0, 6, 49);
R4($d0, $a0, $b0, $c0, 7, 10, 50);
R4($c0, $d0, $a0, $b0, 14, 15, 51);
R4($b0, $c0, $d0, $a0, 5, 21, 52);
R4($a0, $b0, $c0, $d0, 12, 6, 53);
R4($d0, $a0, $b0, $c0, 3, 10, 54);
R4($c0, $d0, $a0, $b0, 10, 15, 55);
R4($b0, $c0, $d0, $a0, 1, 21, 56);
R4($a0, $b0, $c0, $d0, 8, 6, 57);
R4($d0, $a0, $b0, $c0, 15, 10, 58);
R4($c0, $d0, $a0, $b0, 6, 15, 59);
R4($b0, $c0, $d0, $a0, 13, 21, 60);
R4($a0, $b0, $c0, $d0, 4, 6, 61);
R4($d0, $a0, $b0, $c0, 11, 10, 62);
R4($c0, $d0, $a0, $b0, 2, 15, 63);
R4($b0, $c0, $d0, $a0, 9, 21, 64);
$a0 = $a0 + $AA;
$b0 = $b0 + $BB;
$c0 = $c0 + $CC;
$d0 = $d0 + $DD;
}
//decimal variables to binary
$a0 = appendZeroAtBegin(decbin($a0), 32);
$b0 = appendZeroAtBegin(decbin($b0), 32);
$c0 = appendZeroAtBegin(decbin($c0), 32);
$d0 = appendZeroAtBegin(decbin($d0), 32);
echo "End:<br>A: ".binhex($a0)."<br>";
echo "B: ".binhex($b0)."<br>";
echo "C: ".binhex($c0)."<br>";
echo "D: ".binhex($d0)."<br>";
/*$a_b = array_reverse(splitIntoBytes($a));
$b_b = array_reverse(splitIntoBytes($b));
$c_b = array_reverse(splitIntoBytes($c));
$d_b = array_reverse(splitIntoBytes($d));*/
//$hash = implode("", $a_b).implode("", $b_b).implode("", $c_b).implode("", $d_b);
$hash = $a0.$b0.$c0.$d0;
//echo "Hash value: <strong>" . binhex($hash) . "</strong><br>Original MD5: <strong>" . md5($in) . "</strong><br>";
echo binhex($hash) . "<br>" . md5($in);
function hexbin($str){
$hexbinmap = array(
"0" => "0000",
"1" => "0001",
"2" => "0010",
"3" => "0011",
"4" => "0100",
"5" => "0101",
"6" => "0110",
"7" => "0111",
"8" => "1000",
"9" => "1001",
"a" => "1010",
"b" => "1011",
"c" => "1100",
"d" => "1101",
"e" => "1110",
"f" => "1111");
$bin = "";
for ($i = 0; $i < strlen($str); $i++)
{
$bin .= $hexbinmap[strtolower($str[$i])];
}
return $bin;
}
function binhex($str){
$binhexmap = array(
"0000" => "0",
"0001" => "1",
"0010" => "2",
"0011" => "3",
"0100" => "4",
"0101" => "5",
"0110" => "6",
"0111" => "7",
"1000" => "8",
"1001" => "9",
"1010" => "a",
"1011" => "b",
"1100" => "c",
"1101" => "d",
"1110" => "e",
"1111" => "f");
$hex = "";
foreach(explode("\r\n", chunk_split($str, 4)) as $ch){
if(empty($ch)) continue;
$hex .= $binhexmap[$ch];
}
return $hex;
}
function rotateLeft($exp, $s, $binary = false){
$new_exp = $binary ? $exp : decbin($exp);
//append first bit behind the last s times
for($i = 0; $i < $s; $i++){
$new_exp = substr($new_exp, 1) . substr($new_exp, 0, 1);
}
return $binary ? $new_exp : bindec($new_exp);
}
function appendZeroAtBegin($bin, $len){
$new_bin = $bin;
while(strlen($new_bin) < $len){
$new_bin = "0" . $new_bin;
}
return $new_bin;
}
function splitIntoBytes($bin){
//returns high order bits first
$arr = array();
if(strlen($bin) % 8 != 0) return null;
for($i = 0; $i < strlen($bin) / 8; $i++){
$arr[] = substr($bin, $i * 8, 8);
}
return $arr;
}
function R1(&$a, $b, $c, $d, $k, $s, $i){
global $M, $T;
$a = rotateLeft(($a + F($b, $c, $d) + $M[$k] + $T[$i]), $s) + $b;
/*$a = F($b, $c, $d) + $M[$k] + $T[$i];
$a = rotateLeft($a, $s);
$a += $b;*/
}
function R2(&$a, $b, $c, $d, $k, $s, $i){
global $M, $T;
$a = rotateLeft(($a + G($b, $c, $d) + $M[$k] + $T[$i]), $s) + $b;
/*$a = G($b, $c, $d) + $M[$k] + $T[$i];
$a = rotateLeft($a, $s);
$a += $b;*/
}
function R3(&$a, $b, $c, $d, $k, $s, $i){
global $M, $T;
$a = rotateLeft(($a + H($b, $c, $d) + $M[$k] + $T[$i]), $s) + $b;
/*$a = H($b, $c, $d) + $M[$k] + $T[$i];
$a = rotateLeft($a, $s);
$a += $b;*/
}
function R4(&$a, $b, $c, $d, $k, $s, $i){
global $M, $T;
$a = rotateLeft(($a + I($b, $c, $d) + $M[$k] + $T[$i]), $s) + $b;
/*$a = I($b, $c, $d) + $M[$k] + $T[$i];
$a = rotateLeft($a, $s);
$a += $b;*/
}
LG
Kommentar