Хэш-функция MD4

ГУАП

КАФЕДРА № 44

ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ

ПРЕПОДАВАТЕЛЬ

асп.
должность, уч. степень		подпись, дата		инициалы, фамилия

ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ

Хэш-функция MD4

по курсу:  Методы и средства защиты компьютерной информации

РАБОТУ ВЫПОЛНИЛ

СТУДЕНТ ГР.	4942
			подпись, дата		инициалы, фамилия

Санкт-Петербург

2012

Цель работы: Создать программу на языке ООП, для вычисления хэш-функции MD4

В основе работы алгоритма MD4 лежит преобразование блока данных с

использованием определенных формул.

На рисунке представлена внутренняя структура такого процессора.

Два регистра "УКАЗАТЕЛЬ ДАННЫХ" и "РАЗМЕР ДАННЫХ" содержат, соответственно,

указатель на буфер, где находится строка, подлежащая обработке и ее размер в

байтах. На рисунке приведена строка, состоящая из трех символов, поэтому регистр

"РАЗМЕР ДАННЫХ" содержит величину 3.

Регистры A, B, C и D содержат текущий дайджест обрабатываемого блока, а в конце

обработки – цифровой дайджест сообщения. Каждый регистр содержит 32-разрядную

беззнаковую величину, поэтому размер цифрового дайджеста будет равен 32*4=128

бит.

Регистр "РАЗМЕР СООБЩЕНИЯ" хранит размер обрабатываемого сообщения в битах.

Эта величина понадобиться нам на последнем этапе работы алгоритма. Регистр хранит

64-разрядную величину.

Регистровая группа "БЛОЧНЫЙ БУФЕР" предназначена для хранения очередного

блока, подлежащего обработке. Эта группа состоит из 16 регистров с номерами от 0 до

15.

Регистр "БАЙТ В БУФЕРЕ" хранит величину указывающую заполнение регистровой

группы "БЛОЧНЫЙ БУФЕР".

MD4 процессор реализует три базовых логических функции:

F(x, y,x) = (x AND y) OR (NOT x AND z)

G(x, y,z) = (x AND y) OR (x AND z) OR (y AND z)

H(x, y,z) = x XOR y XOR z

Каждая из функций получает на вход три 32-разрядные величины и формирует один

32-разрядный результат.

После первоначальной инициализации (заполнения данными по умолчанию) в регистрах будут содержаться следующие значения:

Процессор выполняет четыре базовые операции, которые преобразуют содержимое

регистров процессора: операция преобразование регистра A, операция

преобразование регистра B, операция преобразование регистра C, и операция

преобразование регистра D.

Операция

a = (a + F(b, c,d) + X[k]) <<< s

в применении к конкретным регистрам имеет следующий вид

A = (A + F(B, C,D) + X[0]) <<< 3

То есть процессор на основании содержимого регистров A, B, C и D, а также слова 0 из

"БЛОЧНОГО БУФЕРА" строит новое значение регистра A

Последовательность элементарных преобразований называется Раундом. MD4

Процессор выполняет три раунда: Раунд 1, Раунд 2 и Раунд 3. Раунд 1 использует

базовую функцию F. Раунд 2 использует базовую функцию G. Раунд 3 использует

базовую функцию H. Все раунды описаны в документе RFC 1320.

Мы рассмотрим Раунд 1 и его реализацию. Раунд 1 представляет собой

последовательность элементарных операций преобразования регистров процессора

MD4 на основании предыдущего содержимого регистров и данных из БЛОЧНОГО

БУФЕРА.

Пусть [abcd k s] обозначает базовую операцию a = (a + F(b, c,d) + X[k]) <<< s. Тогда

Раунд 1 представляет собой следующую последовательность элементарных

преобразований:

[ABCD 0 3] [DABC 1 7] [CDAB 2 11] [BCDA 3 19]

[ABCD 4 3] [DABC 5 7] [CDAB 6 11] [BCDA 7 19]

[ABCD 8 3] [DABC 9 7] [CDAB 10 11] [BCDA 11 19]

[ABCD 12 3] [DABC 13 7] [CDAB 14 11] [BCDA 15 19]

Текст Программы на Delhi

Основная программа:

unit lab2;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, md4Hash, StdCtrls;

type

TForm1 = class(TForm)

Edit1: TEdit;

Button1: TButton;

Memo1: TMemo;

Label1: TLabel;

procedure Button1Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

begin

edit1.Text:=md4(Memo1.Text);

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

memo1.Text:='test';

end;

end.

Модуль md4hash:

unit md4Hash;

interface

uses Windows, SysUtils;

function md4 (S: string): string;

implementation

var a: array[0..15] of Byte;

i: Integer;

LenHi, LenLo: LongWord;

Index: DWord;

HashBuffer: array[0..63] of Byte;

CurrentHash: array[0..3] of DWord;

procedure Burn;

begin

LenHi := 0;

LenLo := 0;

Index := 0;

FillChar (HashBuffer, Sizeof (HashBuffer), 0);

FillChar (CurrentHash, Sizeof (CurrentHash), 0);

end; {proc Burn}

procedure Init;

begin

Burn;

CurrentHash[0] := $;

CurrentHash[1] := $efcdab89;

CurrentHash[2] := $98badcfe;

CurrentHash[3] := $;

end; {proc Init}

function R0 (a, b: LongWord): LongWord;

begin

Result:= (a shl b) or (a shr (32 - b));

end; {func LRot32}

procedure Compress;

var Data: array[0..15] of DWord;

A, B, C, D: DWord;

begin

Move (HashBuffer, Data, Sizeof (Data));

A := CurrentHash[0];

B := CurrentHash[1];

C := CurrentHash[2];

D := CurrentHash[3];

A := R0 (A + ((B and C) or (not(B)and D)) + Data[ 0] , 3);

D := R0 (D + ((A and B) or (not(A)and C)) + Data[ 1] , 7);

C := R0 (C + ((D and A) or (not(D)and B)) + Data[ 2] , 11);

B := R0 (B + ((C and D) or (not(C)and A)) + Data[ 3] , 19);

A := R0 (A + ((B and C) or (not(B)and D)) + Data[ 4] , 3);

D := R0 (D + ((A and B) or (not(A)and C)) + Data[ 5] , 7);

C := R0 (C + ((D and A) or (not(D)and B)) + Data[ 6] , 11);

B := R0 (B + ((C and D) or (not(C)and A)) + Data[ 7] , 19);

A := R0 (A + ((B and C) or (not(B)and D)) + Data[ 8] , 3);

D := R0 (D + ((A and B) or (not(A)and C)) + Data[ 9] , 7);

C := R0 (C + ((D and A) or (not(D)and B)) + Data[10] , 11);

B := R0 (B + ((C and D) or (not(C)and A)) + Data[11] , 19);

A := R0 (A + ((B and C) or (not(B)and D)) + Data[12] , 3);

D := R0 (D + ((A and B) or (not(A)and C)) + Data[13] , 7);

C := R0 (C + ((D and A) or (not(D)and B)) + Data[14] , 11);

B := R0 (B + ((C and D) or (not(C)and A)) + Data[15] , 19);

A := R0 (A + ((B and C) or (B and D) or (C and D)) + Data[ 0] + $5A 3);

D := R0 (D + ((A and B) or (A and C) or (B and C)) + Data[ 4] + $5A 5);

C := R0 (C + ((D and A) or (D and B) or (A and B)) + Data[ 8] + $5A 9);

B := R0 (B + ((C and D) or (C and A) or (D and A)) + Data[12] + $5A 13);

A := R0 (A + ((B and C) or (B and D) or (C and D)) + Data[ 1] + $5A 3);

D := R0 (D + ((A and B) or (A and C) or (B and C)) + Data[ 5] + $5A 5);

C := R0 (C + ((D and A) or (D and B) or (A and B)) + Data[ 9] + $5A 9);

B := R0 (B + ((C and D) or (C and A) or (D and A)) + Data[13] + $5A 13);

A := R0 (A + ((B and C) or (B and D) or (C and D)) + Data[ 2] + $5A 3);

D := R0 (D + ((A and B) or (A and C) or (B and C)) + Data[ 6] + $5A 5);

C := R0 (C + ((D and A) or (D and B) or (A and B)) + Data[10] + $5A 9);

B := R0 (B + ((C and D) or (C and A) or (D and A)) + Data[14] + $5A 13);

A := R0 (A + ((B and C) or (B and D) or (C and D)) + Data[ 3] + $5A 3);

D := R0 (D + ((A and B) or (A and C) or (B and C)) + Data[ 7] + $5A 5);

C := R0 (C + ((D and A) or (D and B) or (A and B)) + Data[11] + $5A 9);

B := R0 (B + ((C and D) or (C and A) or (D and A)) + Data[15] + $5A 13);

A := R0 (A + (B xor C xor D) + Data[ 0] + $6ED9EBA1, 3);

D := R0 (D + (A xor B xor C) + Data[ 8] + $6ED9EBA1, 9);

C := R0 (C + (D xor A xor B) + Data[ 4] + $6ED9EBA1, 11);

B := R0 (B + (C xor D xor A) + Data[12] + $6ED9EBA1, 15);

A := R0 (A + (B xor C xor D) + Data[ 2] + $6ED9EBA1, 3);

D := R0 (D + (A xor B xor C) + Data[10] + $6ED9EBA1, 9);

C := R0 (C + (D xor A xor B) + Data[ 6] + $6ED9EBA1, 11);

B := R0 (B + (C xor D xor A) + Data[14] + $6ED9EBA1, 15);

A := R0 (A + (B xor C xor D) + Data[ 1] + $6ED9EBA1, 3);

D := R0 (D + (A xor B xor C) + Data[ 9] + $6ED9EBA1, 9);

C := R0 (C + (D xor A xor B) + Data[ 5] + $6ED9EBA1, 11);

B := R0 (B + (C xor D xor A) + Data[13] + $6ED9EBA1, 15);

A := R0 (A + (B xor C xor D) + Data[ 3] + $6ED9EBA1, 3);

D := R0 (D + (A xor B xor C) + Data[11] + $6ED9EBA1, 9);

C := R0 (C + (D xor A xor B) + Data[ 7] + $6ED9EBA1, 11);

B := R0 (B + (C xor D xor A) + Data[15] + $6ED9EBA1, 15);

Inc (CurrentHash[0], A);

Inc (CurrentHash[1], B);

Inc (CurrentHash[2], C);

Inc (CurrentHash[3], D);

Index := 0;

FillChar (HashBuffer, Sizeof (HashBuffer), 0);

end; {proc Compress}

procedure Update (const Buffer; Size: LongWord);

var PBuf: ^Byte;

begin

Inc (LenHi, Size shr 29);

Inc (LenLo, Size * 8);

if LenLo < (Size * 8) then Inc (LenHi);

PBuf := @Buffer;

while Size > 0 do

begin

if (Sizeof (HashBuffer) - Index) <= DWord (Size) then

begin

Move (PBuf^, HashBuffer[Index], Sizeof (HashBuffer) - Index);

Dec (Size, Sizeof (HashBuffer) - Index);

Inc (PBuf, Sizeof (HashBuffer) - Index);

Compress;

end

else

begin

Move (PBuf^, HashBuffer[Index], Size);

Inc (Index, Size);

Size := 0;

end; {if}

end; {while}

end; {proc Update}

procedure Final (var Digest);

begin

HashBuffer[Index] := $80;

if Index >= 56 then Compress;

PDWord (@HashBuffer[56])^ := LenLo;

PDWord (@HashBuffer[60])^ := LenHi;

Compress;

Move (CurrentHash, Digest, Sizeof (CurrentHash));

Burn;

end; {proc Final}

function md4 (S: string): string;

begin

Init;

Update (s[1], Length (s));

Final (a);

Result := '';

for i := 0 to 15 do

Result := Concat (Result, IntToHex (a[i], 2));

Burn;

Result := Result;

end; {func md4}

end.