PDA

Просмотр полной версии : md5 (реализация в Delphi)


Flenov
17.12.2009, 15:39
Доброго всем времени суток.
Это моя первая статья, где я что-то рассказываю, а не спрашиваю.
А рассказать я хочу немного об алгоритме md5.

Немного истории:
MD5 (англ. Message Digest 5) — 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института (Massachusetts Institute of Technology, MIT) в 1991 году. Предназначен для создания «отпечатков» или «дайджестов» сообщений произвольной длины.
Является улучшенной в плане безопасности версией MD4.[1] Зная MD5, невозможно восстановить входное сообщение, так как одному MD5 могут соответствовать разные сообщения. Используется для проверки подлинности опубликованных сообщений путём сравнения дайджеста сообщения с опубликованным.
Эту операцию называют «проверка хеша» (hashcheck). Описан в RFC 1321.[2]

Приведу сразу исходный код:
unit md5Unit;

interface

uses
Windows, SysUtils;


function md5(S: String): String;
implementation
type
THash = Array[0..3] of DWORD;
TBuff = Array[0..15] of DWORD;


function LRot32(A: DWORD; B: Byte): DWORD;
begin
Result:= (A shl B) or (A shr (32-B));
end;

procedure Compressor(var CurrentHash: THash; HashBuffer: TBuff);
var
A, B, C, D: DWORD;
begin
A:=CurrentHash[0];
B:=CurrentHash[1];
C:=CurrentHash[2];
D:=CurrentHash[3];
//
A:= B + LRot32(A + (D xor (B and (C xor D))) + HashBuffer[ 0] + $D76AA478, 7);
D:= A + LRot32(D + (C xor (A and (B xor C))) + HashBuffer[ 1] + $E8C7B756, 12);
C:= D + LRot32(C + (B xor (D and (A xor B))) + HashBuffer[ 2] + $242070DB, 17);
B:= C + LRot32(B + (A xor (C and (D xor A))) + HashBuffer[ 3] + $C1BDCEEE, 22);
A:= B + LRot32(A + (D xor (B and (C xor D))) + HashBuffer[ 4] + $F57C0FAF, 7);
D:= A + LRot32(D + (C xor (A and (B xor C))) + HashBuffer[ 5] + $4787C62A, 12);
C:= D + LRot32(C + (B xor (D and (A xor B))) + HashBuffer[ 6] + $A8304613, 17);
B:= C + LRot32(B + (A xor (C and (D xor A))) + HashBuffer[ 7] + $FD469501, 22);
A:= B + LRot32(A + (D xor (B and (C xor D))) + HashBuffer[ 8] + $698098D8, 7);
D:= A + LRot32(D + (C xor (A and (B xor C))) + HashBuffer[ 9] + $8B44F7AF, 12);
C:= D + LRot32(C + (B xor (D and (A xor B))) + HashBuffer[10] + $FFFF5BB1, 17);
B:= C + LRot32(B + (A xor (C and (D xor A))) + HashBuffer[11] + $895CD7BE, 22);
A:= B + LRot32(A + (D xor (B and (C xor D))) + HashBuffer[12] + $6B901122, 7);
D:= A + LRot32(D + (C xor (A and (B xor C))) + HashBuffer[13] + $FD987193, 12);
C:= D + LRot32(C + (B xor (D and (A xor B))) + HashBuffer[14] + $A679438E, 17);
B:= C + LRot32(B + (A xor (C and (D xor A))) + HashBuffer[15] + $49B40821, 22);

A:= B + LRot32(A + (C xor (D and (B xor C))) + HashBuffer[ 1] + $F61E2562, 5);
D:= A + LRot32(D + (B xor (C and (A xor B))) + HashBuffer[ 6] + $C040B340, 9);
C:= D + LRot32(C + (A xor (B and (D xor A))) + HashBuffer[11] + $265E5A51, 14);
B:= C + LRot32(B + (D xor (A and (C xor D))) + HashBuffer[ 0] + $E9B6C7AA, 20);
A:= B + LRot32(A + (C xor (D and (B xor C))) + HashBuffer[ 5] + $D62F105D, 5);
D:= A + LRot32(D + (B xor (C and (A xor B))) + HashBuffer[10] + $02441453, 9);
C:= D + LRot32(C + (A xor (B and (D xor A))) + HashBuffer[15] + $D8A1E681, 14);
B:= C + LRot32(B + (D xor (A and (C xor D))) + HashBuffer[ 4] + $E7D3FBC8, 20);
A:= B + LRot32(A + (C xor (D and (B xor C))) + HashBuffer[ 9] + $21E1CDE6, 5);
D:= A + LRot32(D + (B xor (C and (A xor B))) + HashBuffer[14] + $C33707D6, 9);
C:= D + LRot32(C + (A xor (B and (D xor A))) + HashBuffer[ 3] + $F4D50D87, 14);
B:= C + LRot32(B + (D xor (A and (C xor D))) + HashBuffer[ 8] + $455A14ED, 20);
A:= B + LRot32(A + (C xor (D and (B xor C))) + HashBuffer[13] + $A9E3E905, 5);
D:= A + LRot32(D + (B xor (C and (A xor B))) + HashBuffer[ 2] + $FCEFA3F8, 9);
C:= D + LRot32(C + (A xor (B and (D xor A))) + HashBuffer[ 7] + $676F02D9, 14);
B:= C + LRot32(B + (D xor (A and (C xor D))) + HashBuffer[12] + $8D2A4C8A, 20);

A:= B + LRot32(A + (B xor C xor D) + HashBuffer[ 5] + $FFFA3942, 4);
D:= A + LRot32(D + (A xor B xor C) + HashBuffer[ 8] + $8771f681, 11);
C:= D + LRot32(C + (D xor A xor B) + HashBuffer[11] + $6D9D6122, 16);
B:= C + LRot32(B + (C xor D xor A) + HashBuffer[14] + $FDE5380C, 23);
A:= B + LRot32(A + (B xor C xor D) + HashBuffer[ 1] + $A4BEEA44, 4);
D:= A + LRot32(D + (A xor B xor C) + HashBuffer[ 4] + $4BDECFA9, 11);
C:= D + LRot32(C + (D xor A xor B) + HashBuffer[ 7] + $F6BB4B60, 16);
B:= C + LRot32(B + (C xor D xor A) + HashBuffer[10] + $BEBFBC70, 23);
A:= B + LRot32(A + (B xor C xor D) + HashBuffer[13] + $289B7EC6, 4);
D:= A + LRot32(D + (A xor B xor C) + HashBuffer[ 0] + $EAA127FA, 11);
C:= D + LRot32(C + (D xor A xor B) + HashBuffer[ 3] + $D4EF3085, 16);
B:= C + LRot32(B + (C xor D xor A) + HashBuffer[ 6] + $04881D05, 23);
A:= B + LRot32(A + (B xor C xor D) + HashBuffer[ 9] + $D9D4D039, 4);
D:= A + LRot32(D + (A xor B xor C) + HashBuffer[12] + $E6DB99E5, 11);
C:= D + LRot32(C + (D xor A xor B) + HashBuffer[15] + $1FA27CF8, 16);
B:= C + LRot32(B + (C xor D xor A) + HashBuffer[ 2] + $C4AC5665, 23);

A:= B + LRot32(A + (C xor (B or (not D))) + HashBuffer[ 0] + $F4292244, 6);
D:= A + LRot32(D + (B xor (A or (not C))) + HashBuffer[ 7] + $432AFF97, 10);
C:= D + LRot32(C + (A xor (D or (not B))) + HashBuffer[14] + $AB9423A7, 15);
B:= C + LRot32(B + (D xor (C or (not A))) + HashBuffer[ 5] + $FC93A039, 21);
A:= B + LRot32(A + (C xor (B or (not D))) + HashBuffer[12] + $655B59C3, 6);
D:= A + LRot32(D + (B xor (A or (not C))) + HashBuffer[ 3] + $8F0CCC92, 10);
C:= D + LRot32(C + (A xor (D or (not B))) + HashBuffer[10] + $FFEFF47D, 15);
B:= C + LRot32(B + (D xor (C or (not A))) + HashBuffer[ 1] + $85845DD1, 21);
A:= B + LRot32(A + (C xor (B or (not D))) + HashBuffer[ 8] + $6FA87E4F, 6);
D:= A + LRot32(D + (B xor (A or (not C))) + HashBuffer[15] + $FE2CE6E0, 10);
C:= D + LRot32(C + (A xor (D or (not B))) + HashBuffer[ 6] + $A3014314, 15);
B:= C + LRot32(B + (D xor (C or (not A))) + HashBuffer[13] + $4E0811A1, 21);
A:= B + LRot32(A + (C xor (B or (not D))) + HashBuffer[ 4] + $F7537E82, 6);
D:= A + LRot32(D + (B xor (A or (not C))) + HashBuffer[11] + $BD3AF235, 10);
C:= D + LRot32(C + (A xor (D or (not B))) + HashBuffer[ 2] + $2AD7D2BB, 15);
B:= C + LRot32(B + (D xor (C or (not A))) + HashBuffer[ 9] + $EB86D391, 21);
//
Inc(CurrentHash[0], A);
Inc(CurrentHash[1], B);
Inc(CurrentHash[2], C);
Inc(CurrentHash[3], D);
end;

function HashToStr(Hash: THash): String;
var
MainBuff: Array[0..3] of Byte;
i: Byte;
begin
Result:='';
for i:=0 to 3 do
begin
FillChar(MainBuff, 4, 0);
CopyMemory(@MainBuff, @Hash[i], 4);
Result:=Result+IntToHex(MainBuff[0], 2)+IntToHex(MainBuff[1], 2)+IntToHex(MainBuff[2], 2)+IntToHex(MainBuff[3], 2);
end;
end;

function md5(S: String): String;
const
BuffSize=64;
var
PBuff: PChar;
CurrentHash: THash;
HashBuff: TBuff;
Size: LongWord;
LenLO, LenHI: LongWord;
begin
Size:=Length(S);
LenLO:=Size*8;
LenHI:=Size shr 29;
//
S:=S+#$80;
PBuff:=PChar(S);
//
FillChar(HashBuff, BuffSize, 0);
CurrentHash[0]:= $67452301;
CurrentHash[1]:= $EFCDAB89;
CurrentHash[2]:= $98BADCFE;
CurrentHash[3]:= $10325476;
//
Inc(Size);
While (Size>=BuffSize) do
begin
CopyMemory(@HashBuff, PBuff, BuffSize);
Compressor(CurrentHash, HashBuff);
FillChar(HashBuff, BuffSize, 0);
Inc(PBuff, BuffSize);
Dec(Size, BuffSize);
end;
if (Size>0) then
begin
CopyMemory(@HashBuff, PBuff, Size);
Inc(PBuff, Size);
end;
//
if (Size>56) then
begin
Compressor(CurrentHash, HashBuff);
FillChar(HashBuff, BuffSize, 0);
end;
HashBuff[14]:=LenLO;
HashBuff[15]:=LenHI;
Compressor(CurrentHash, HashBuff);
FillChar(HashBuff, BuffSize, 0);
//
Result:=LowerCase(HashToStr(CurrentHash));
end;
end.

А теперь я попробую объяснить, как это работает.
Изначально у нас есть два буфера.
CurrentHash - это буфер текущего хеша.
Занимает 16 байт.
HashBuff - это буфер для рассчёта хеша.
Занимает 64 байта.
В него копируются байты сообщения, хеш которого нужно рассчитать.
Кстати, если мы рассчитываем хеш строки, то в HashBuff копируются коды символов строки, если мы рассчитываем для какого-либо файла,
то в HashBuff должны копироваться байты файла.


Теперь подробно о функции md5:

Сначала мы вычисляем длину сообщения.
Size:=Length(S);
LenLO:=Size*8;
LenHI:=Size shr 29;

Затем дописываем закрывающий код и ставим указатель в начало.
S:=S+#$80;
PBuff:=PChar(S);

Далее инициализируем буффер текущего хеша (CurrentHash) и чистим HashBuff.
FillChar(HashBuff, BuffSize, 0);
CurrentHash[0]:= $67452301;
CurrentHash[1]:= $EFCDAB89;
CurrentHash[2]:= $98BADCFE;
CurrentHash[3]:= $10325476;

Увеличиваю переменную, отвечающую за фактическую длину сообщения.
И если длина сообщения больше 64 байт - выполняю рассчёт хеша до тех пор, пока длина оставшегося сообщения будет меньше 64 байт.
Inc(Size);
While (Size>=BuffSize) do
begin
CopyMemory(@HashBuff, PBuff, BuffSize);
Compressor(CurrentHash, HashBuff);
FillChar(HashBuff, BuffSize, 0);
Inc(PBuff, BuffSize);
Dec(Size, BuffSize);
end;

Если длина оставшегося сообщения больше нуля, то загоняю оставшееся в буффер.
if (Size>0) then
begin
CopyMemory(@HashBuff, PBuff, Size);
Inc(PBuff, Size);
end;

Проверяю длину оставшегося сообщения.
Если она больше 56 байт (тоесть последние 6 байт не свободны) то вызываю компрессор.
if (Size>56) then
begin
Compressor(CurrentHash, HashBuff);
FillChar(HashBuff, BuffSize, 0);
end;

Далее в последние 8 байт дописываю длину исходного сообщения и вызываю компрессор.
HashBuff[14]:=LenLO;
HashBuff[15]:=LenHI;
Compressor(CurrentHash, HashBuff);
FillChar(HashBuff, BuffSize, 0);

Ну собственно и результат:
Result:=LowerCase(HashToStr(CurrentHash));

Flenov
17.12.2009, 16:04
Особого внимания заслуживает функция LRot32.
На первый взгляд может показаться, что она просто смещает биты A на величину B,
но это не так.
Эта функция именно поворачивает A: то что ушло влево выйдет справа.
Как бы такой своеобразный барабанчик.

Приглядитесь:
function LRot32(A: DWORD; B: Byte): DWORD;
begin
Result:= (A shl B) or (A shr (32-B));
end;

Flenov
17.12.2009, 16:08
Некоторым может показаться, что тут можно устроить побитовый перебор.
К сожалению это не так.
Даже, если вы знаете длину исхожного сообщения, знаете пусть даже часть сообщения.
Всёравно каждый бит зависит от другого бита.
Эту зависимость как раз и делают вышеописанный ротор и сложение результата текущего с результатом предыдущим.
A:= B + LRot32(A + (D xor (B and (C xor D))) + HashBuffer[ 0] + $D76AA478, 7);
D:= A + LRot32(D + (C xor (A and (B xor C))) + HashBuffer[ 1] + $E8C7B756, 12);

Так называемый "Лавинный эффект"

Flenov
17.12.2009, 16:18
Кстати, все вопросы пишем в этой теме.
Постараюсь ответить.

Исходник:
Ссылка 1 (http://smitt89.narod.ru/md5.zip)
Ссылка 2 (http://rapidshare.com/files/322067601/md5.zip.html)