MD5 в Delphi / Pascal / FreePascal для коротких строк

Я пытаюсь реализовать простой MD5 для коротких строк (короче 64 байтов). Я использую алгоритм из Википедии. Все компилируется, но мой результат для строки:

"hello world" 

is:

BB3BB65ED0EE1EE0BB22CB93C3CD5A8F

при этом должно быть:

5EB63BBBE01EEED093CB22BB8F5ACDC3

Полный код здесь:

program Prog;

uses Classes, SysUtils;

function leftrotate(x, c: Cardinal): Cardinal;
begin
  leftrotate := (x shl c) or (x shr (32-c));
end;

const s: array[0..63] of Cardinal = (
    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 );
K: array[0..63] of Cardinal = (
    $d76aa478, $e8c7b756, $242070db, $c1bdceee,
    $f57c0faf, $4787c62a, $a8304613, $fd469501,
    $698098d8, $8b44f7af, $ffff5bb1, $895cd7be,
    $6b901122, $fd987193, $a679438e, $49b40821,
    $f61e2562, $c040b340, $265e5a51, $e9b6c7aa,
    $d62f105d, $02441453, $d8a1e681, $e7d3fbc8,
    $21e1cde6, $c33707d6, $f4d50d87, $455a14ed,
    $a9e3e905, $fcefa3f8, $676f02d9, $8d2a4c8a,
    $fffa3942, $8771f681, $6d9d6122, $fde5380c,
    $a4beea44, $4bdecfa9, $f6bb4b60, $bebfbc70,
    $289b7ec6, $eaa127fa, $d4ef3085, $04881d05,
    $d9d4d039, $e6db99e5, $1fa27cf8, $c4ac5665,
    $f4292244, $432aff97, $ab9423a7, $fc93a039,
    $655b59c3, $8f0ccc92, $ffeff47d, $85845dd1,
    $6fa87e4f, $fe2ce6e0, $a3014314, $4e0811a1,
    $f7537e82, $bd3af235, $2ad7d2bb, $eb86d391 );

var a0,b0,c0,d0, a,b,c,d, f,g,dTemp: Cardinal;
   Len: Integer;
   Msg: array[0..63] of Char;
   M: array[0..15] of Cardinal absolute Msg; //break chunk into sixteen 32-bit words M[j]
   Str: String;
   i: Integer;
   ff: TFileStream;
   wait: Char;
begin
  a0 := $67452301;
  b0 := $efcdab89;
  c0 := $98badcfe;
  d0 := $10325476;

  Str := 'hello world';
  Len := Length(Str);

  FillChar(Msg, 64, 0);

  for i:=1 to Len do Msg[i-1] := Str[i];

//append "1" bit to message
  Msg[Len] := chr(128);

//append original length in bits mod (2 pow 64) to message
  Msg[63-7] := chr(8*Len);  //Update thanks to @MBo

//Process each 512-bit chunk of message- 1 only have 1 chunk

//TEST dump
//  ff := TFileStream.create('test.txt', fmCreate);
//  ff.write(msg, 64);
//  ff.free;

//Initialize hash value for this chunk:
    A := a0;
    B := b0;
    C := c0;
    D := d0;

//Main loop:
    for i := 0 to 63 do begin

        if (i>=0) and (i<=15) then begin
            F := (B and C) or ((not B) and D);
            g := i;
        end
        else if (i>=16) and (i<=31) then begin
            F := (D and B) or ((not D) and C);
            g := (5*i + 1) mod 16;
        end
        else if (i>=32) and (i<=47) then begin
            F := B xor C xor D;
            g := (3*i + 5) mod 16;
        end
        else if (i>=48) and (i<=63) then begin
            F := C xor (B or (not D));
            g := (7*i) mod 16;
        end;

        dTemp := D;
        D := C;
        C := B;
        B := B + leftrotate((A + F + K[i] + M[g]), s[i]);
        A := dTemp;
    end;

//Add this chunk's hash to result so far:
  a0 := a0 + A;
  b0 := b0 + B;
  c0 := c0 + C;
  d0 := d0 + D;

  //This should give 5EB63BBBE01EEED093CB22BB8F5ACDC3
  Writeln( IntToHex(a0,8) + IntToHex(b0,8) + IntToHex(c0,8)  +IntToHex(d0,8) );

  Readln(wait);
end.

Вы можете попробовать код онлайн здесь: http://ideone.com/qdYQ6q

А вот дамп моего подготовленного фрагмента непосредственно перед основным циклом (test.txt):

введите описание изображения здесь


person Tom    schedule 08.12.2014    source источник
comment
Ну, конечно, вам следует поместить это в функцию для повторного использования. И действительно ли вы обрабатываете ввод как текст? Вы должны рассматривать ввод как двоичный.   -  person David Heffernan    schedule 08.12.2014
comment
@DavidHeffernan Я изложил это как программу, чтобы любой мог легко ее протестировать, и ее можно запустить на ideaone.com, но это будет функция. И да, он должен использовать текст (строки), поскольку я буду использовать его для хеширования электронных писем, логинов, паролей - только таких коротких строк.   -  person Tom    schedule 08.12.2014
comment
Вы ошиблись. Алгоритмы хеширования работают с двоичными файлами. Прежде всего выберите кодировку текста, а затем закодируйте текст как двоичный, используя эту кодировку. Например, вы можете выбрать UTF-8.   -  person David Heffernan    schedule 08.12.2014
comment
@DavidHeffernan есть двоичная кодировка: M: массив [0..15] кардинального абсолютного сообщения; а входные строки - ANSI.   -  person Tom    schedule 08.12.2014
comment
Теперь у вас есть код, который может работать только с текстом ANSI. Что довольно ограничивает. Вы не можете вычислить хэши для файлов, потоков и т. Д. Вы также изобретаете велосипед. Есть много хороших реализаций хеширования.   -  person David Heffernan    schedule 08.12.2014
comment
@DavidHeffernan: Я пробовал реализацию Indy. Он делает 100 000 хешей за 0,30 секунды. Моя реализация делает это за 0,20 секунды. В данном случае для меня важнее прирост скорости, чем эти ограничения. Итак, я заново изобрел довольно красивое колесо;)   -  person Tom    schedule 08.12.2014
comment
Это совсем не похоже на полезный прирост производительности. Я сомневаюсь, что хеширование когда-либо является узким местом. Можете ли вы действительно получить 100000 объектов для хеширования достаточно быстро, чтобы прирост производительности имел значение. И я уверен, что есть более быстрые хешеры, чем ваш код, если это действительно важно. Также вполне вероятно, что ваш тест ошибочен. Есть множество возможностей для улучшения вашего кода. Ваша rol реализация для начала оставляет желать лучшего.   -  person David Heffernan    schedule 08.12.2014
comment
@DavidHeffernan Я также хэширую строки, сгенерированные памятью, чтобы найти коллизию. Возможно, есть более быстрые реализации, но мне не понравилось.   -  person Tom    schedule 08.12.2014
comment
См. Также Хеширование MD5 в Delphi 2009.   -  person LU RD    schedule 09.12.2014


Ответы (3)


Последний шаг неверен:

  a0 := a0 + A;
  b0 := b0 + B;
  c0 := c0 + C;
  d0 := d0 + D;

он должен изменить порядок байтов:

  a0 := Swap32(a0 + A);
  b0 := Swap32(b0 + B);
  c0 := Swap32(c0 + C);
  d0 := Swap32(d0 + D);

function Swap32(ALong: Cardinal): Cardinal; Assembler; 
asm 
  BSWAP eax 
end;

и тогда это хорошо.

person Tom    schedule 08.12.2014
comment
Одно маленькое примечание ... В псевдокоде вики //Note: All variables are unsigned 32 bit and wrap modulo 2^32 when calculating есть строка, так что не следует ли менять эти Longint на DWord? - person Rik; 08.12.2014
comment
@Rik У нас здесь в основном бинарные операции, и это прекрасно работает с Longints. Но спасибо за заметку - я изменю свой код, чтобы использовать Cardinals, просто чтобы убедиться, что он в порядке. - person Tom; 08.12.2014
comment
Кардинал - это DWord на 32 бит, но гарантировано ли, что он останется DWord (32-битное целое число без знака) на других платформах / битности? Я думаю, DWord всегда будет 32-битным. (Я также не уверен, когда на самом деле будет 32-битная упаковка, но на всякий случай это всегда должно быть 32-битное целое число без знака, независимо от системы, что, я думаю, Cardinal не гарантирует) - person Rik; 08.12.2014
comment
@Rik DWord не является типом данных Delphi. Это Winapi. Uint32 в Delphi - это либо Cardinal, либо Longword. И я где-то читал, что это псевдонимы и никогда не меняются на других платформах. - person Tom; 08.12.2014
comment
Можно с уверенностью предположить, что Cardinal всегда будет 32-битным везде. Однако, если вы нервничаете по этому поводу, используйте LongWord. - person David Heffernan; 08.12.2014
comment
Аааа. Хорошо. Я только что где-то читал, что Cardinal не гарантированно всегда будет 32-битным в будущее, но теперь я вижу на сайте Delphi, что должно быть. Но LongWord - тоже хорошая альтернатива. - person Rik; 08.12.2014
comment
Что ж, вместо DWord, Longword или Cardinal используйте явный UInt32. Я ожидаю, что это будет сопоставлено с подходящим типом, независимо от того, на какой платформе. Я не уверен, что Cardinal всегда будет 32-битным. В конце концов, в былые времена это было 16 бит. - person Rudy Velthuis; 09.12.2014
comment
@RudyVelthuis Я исключал возможность переноса обратно на 16-битный Delphi - person David Heffernan; 09.12.2014
comment
Конечно, но не уверен, что Cardinal останется 32-битным. Были разговоры о том, чтобы сделать его 64-битным на некоторых платформах, но это было отклонено из-за протестов пользователей. Не уверен, всегда ли он будет отклонен. Конечно, UInt32 останется 32-битным. - person Rudy Velthuis; 09.12.2014

Возможно, вы захотите использовать стороннюю реализацию вместо создания своей собственной. Например, класс Indy TIdHashMessageDigest5 выдает правильное значение, например:

uses
  ..., IdHashMessageDigest;

var
  S: string;
begin
  with TIdHashMessageDigest5.Create do
  try
    S := HashStringAsHex('hello world'); // returns '5EB63BBBE01EEED093CB22BB8F5ACDC3'
  finally
    Free;
  end;
end;
person Remy Lebeau    schedule 08.12.2014
comment
И аналогично ... FPC имеет модуль MD5, который вы можете использовать. (к этому вопросу был прикреплен тег freepascal) - person Rik; 08.12.2014
comment
А еще есть модуль MessageDigest_5 в Delphi. - person LU RD; 09.12.2014

А как насчет этих шагов:

append "0" bit until message length in bits ≡ 448 (mod 512)

(56 байт, 64 + 56 и т. Д.) И

append original length в битах mod (2 pow 64) to message

но вы добавили Len в байтах

P.S. Я проверил последний вариант с Delphi. Я изменил типы символов на AnsiChar, и результат соответствует ожидаемому. Обратите внимание, что для правильного двоичного результата перестановка байтов не требуется. Это может помочь только для построения шестнадцатеричной строки из значений Int32

Int32 уже является прямым порядком байтов на оборудовании Intel, поэтому BB3BB65E (шестнадцатеричное строковое представление) соответствует байтовой последовательности 5E B6 3B BB и так далее.

person MBo    schedule 08.12.2014
comment
BitsLen должен быть в 56-м байте - person MBo; 08.12.2014