Размещено на http://www.allbest.ru/

УО «Белорусский государственный технологический университет»

Кафедра Информационных систем и технологий

Курс «Защита информации и надежность информационных систем»

Отчёт по лабораторной работе №1:

MD5

Выполнила: Панченко О.Л.

3 курс 2 группа

Проверил: Шиман Д. В

Минск 2016

Теоретическая часть

хеширование данные массив алгоритм

Хеширование (иной вариант написания - хэширование; англ. hashing) - преобразование по определённому алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хэш-функциями или «функциями свёртки», а их результаты называют хэшем, хэш-кодом, хэш-суммой или «сводкой сообщения».

Хэширование применяется для построения ассоциативных массивов, поиска дубликатов в сериях наборов данных, построения достаточно уникальных идентификаторов для наборов данных, контрольного суммирования с целью обнаружения случайных или намеренных ошибок при хранении или передаче, для хранения паролей в системах защиты (в этом случае доступ к области памяти, где находятся пароли, не позволяет восстановить сам пароль), при выработке электронной подписи (на практике часто подписывается не само сообщение, а его хэш-образ).

Хорошая хэш-функция должна удовлетворять двум свойствам:

· быстро вычисляться;

· минимизировать количество коллизий

Идеальной хэш-функцией (англ. Perfect hash function) называется такая функция, которая отображает каждый ключ из набора в множество целых чисел без коллизий. В математических терминах это инъективное отображение.

1. Функция называется идеальной хэш-функцией для , если она инъективна на ;

2. Функция называется минимальной идеальной хэш-функцией для , если она является ИХФ и ;

3. Для целого , функция называется -идеальной хэш-функцией (k-PHF) для если для каждого имеем .

Идеальное хэширование применяется в тех случаях, когда мы хотим присвоить уникальный идентификатор ключу, без сохранения какой-либо информации о ключе.

MD5 (англ. Message Digest 5) - 128-битный алгоритм хеширования, разработанный профессором Рональдом Л. Ривестом из Массачусетского технологического института (Massachusetts Institute of Technology, MIT) в 1991 году. Предназначен для создания «отпечатков» или дайджестов сообщения произвольной длины и последующей проверки их подлинности. Широко применялся для проверки целостности информации и хранения паролей в закрытом виде.

Алгоритм MD5

На вход алгоритма поступает входной поток данных, хеш которого необходимо найти. Длина сообщения может быть любой (в том числе нулевой). Запишем длину сообщения в L. Это число целое и неотрицательное. Кратность каким-либо числам необязательна. После поступления данных идёт процесс подготовки потока к вычислениям.

Шаг 1. Выравнивание потока. Сначала дописывают единичный бит в конец потока (байт 80h), затем необходимое число нулевых бит. Входные данные выравниваются так, чтобы их новый размер был сравним с 448 по модулю 512 (). Выравнивание происходит, даже если длина уже сравнима с 448.

Шаг 2. Добавление длины сообщения. В конец сообщения дописывают 64-битное представление длины данных (количество бит в сообщении) до выравнивания. Сначала записывают младшие 4 байта, затем старшие. Если длина превосходит , то дописывают только младшие биты (эквивалентно взятию по модулю ). После этого длина потока станет кратной 512. Вычисления будут основываться на представлении этого потока данных в виде массива слов по 512 бит.

Шаг 3. Инициализация буфера. Для вычислений инициализируются 4 переменных размером по 32 бита и задаются начальные значения шестнадцатеричными числами (порядок байтов little-endian, сначала младший байт):

А = 01 23 45 67; // 67452301h

В = 89 AB CD EF; // EFCDAB89h

С = FE DC BA 98; // 98BADCFEh

D = 76 54 32 10. // 10325476h

В этих переменных будут храниться результаты промежуточных вычислений. Начальное состояние ABCD называется инициализирующим вектором.

Определим ещё функции и константы, которые нам понадобятся для вычислений.

· Потребуются 4 функции для четырёх раундов. Введём функции от трёх параметров - слов, результатом также будет слово:

1-й раунд: ,

2-й раунд: ,

3-й раунд: ,

4-й раунд: ,

где побитовые логические операции XOR, AND, OR и NOT соответственно.

· Определим таблицу констант  - 64-элементная таблица данных, построенная следующим образом: .[11]

· Каждый 512-битный блок проходит 4 этапа вычислений по 16 раундов. Для этого блок представляется в виде массива X из 16 слов по 32 бита. Все раунды однотипны и имеют вид: [abcd k s i], определяемый как , где k - номер 32-битного слова из текущего 512-битного блока сообщения, и  - циклический сдвиг влево на s бит полученного 32-битного аргумента. Число s задается отдельно для каждого раунда.

Шаг 4. Вычисление в цикле. Заносим в блок данных элемент n из массива 512-битных блоков. Сохраняются значения A, B, C и D, оставшиеся после операций над предыдущими блоками (или их начальные значения, если блок первый).

AA = A

BB = B

CC = C

DD = D

Этап 1

/* [abcd k s i] a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */

[ABCD 0 7 1][DABC 1 12 2][CDAB 2 17 3][BCDA 3 22 4]

[ABCD 4 7 5][DABC 5 12 6][CDAB 6 17 7][BCDA 7 22 8]

[ABCD 8 7 9][DABC 9 12 10][CDAB 10 17 11][BCDA 11 22 12]

[ABCD 12 7 13][DABC 13 12 14][CDAB 14 17 15][BCDA 15 22 16]

Этап 2

/* [abcd k s i] a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */

[ABCD 1 5 17][DABC 6 9 18][CDAB 11 14 19][BCDA 0 20 20]

[ABCD 5 5 21][DABC 10 9 22][CDAB 15 14 23][BCDA 4 20 24]

[ABCD 9 5 25][DABC 14 9 26][CDAB 3 14 27][BCDA 8 20 28]

[ABCD 13 5 29][DABC 2 9 30][CDAB 7 14 31][BCDA 12 20 32]

Этап 3

/* [abcd k s i] a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */

[ABCD 5 4 33][DABC 8 11 34][CDAB 11 16 35][BCDA 14 23 36]

[ABCD 1 4 37][DABC 4 11 38][CDAB 7 16 39][BCDA 10 23 40]

[ABCD 13 4 41][DABC 0 11 42][CDAB 3 16 43][BCDA 6 23 44]

[ABCD 9 4 45][DABC 12 11 46][CDAB 15 16 47][BCDA 2 23 48]

Этап 4

/* [abcd k s i] a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */

[ABCD 0 6 49][DABC 7 10 50][CDAB 14 15 51][BCDA 5 21 52]

[ABCD 12 6 53][DABC 3 10 54][CDAB 10 15 55][BCDA 1 21 56]

[ABCD 8 6 57][DABC 15 10 58][CDAB 6 15 59][BCDA 13 21 60]

[ABCD 4 6 61][DABC 11 10 62][CDAB 2 15 63][BCDA 9 21 64]

Суммируем с результатом предыдущего цикла:

A = AA + A

B = BB + B

C = CC + C

D = DD + D

После окончания цикла необходимо проверить, есть ли ещё блоки для вычислений. Если да, то переходим к следующему элементу массива (n + 1) и повторяем цикл.

Шаг 5. Результат вычислений. Результат вычислений находится в буфере ABCD, это и есть хеш. Если выводить побайтово, начиная с младшего байта A и закончив старшим байтом D, то мы получим MD5-хеш. 1, 0, 15, 34, 17, 18…



Реализация

Входные данные выравниваются так, чтобы их новый размер был сравним с 448 по модулю 512 (). В конец сообщения дописывают 64-битное представление длины данных (количество бит в сообщении) до выравнивания.

StringBuilder PaddedMessage=new StringBuilder(GetBinary(msg));

//выравнивание данных к 448 по модулю 512

PaddedMessage.Append("1");

uint BeginMessageLength = (uint)PaddedMessage.Length;

while(PaddedMessage.Length % 512!=448)

{

PaddedMessage.Append("0");

}

//дописывание 64 бит длинны сообщения

word MessageLength=new word(BeginMessageLength-1,-1);

short [] LengthBit = new short[64];

int iter = 0;

for (int i = 7; i >= 0; i--)

{

for (int j = 0; j < 8; j++)

{

LengthBit[iter] = MessageLength[i * 8 + j];

iter++;

}

}

for (int i = 0; i < LengthBit.Length; i++)

{

if (LengthBit[i] == 1) PaddedMessage.Append("1");

else PaddedMessage.Append("0");

}

таблицу констант  

T = new uint[64];

for (int i = 0; i < 64; i++)

{

T[i] = (uint)(Math.Pow(2, 32) * Math.Abs(Math.Sin(i + 1)));

}

Массив из 16 слов

string[] Registers = new string[]{"ABCD","DABC","CDAB","BCDA",

"ABCD","DABC","CDAB","BCDA",

"ABCD","DABC","CDAB","BCDA",

"ABCD","DABC","CDAB","BCDA"};

//этап 1

int[] S = new int[] { 7, 12, 17, 22,

7, 12, 17, 22,

7, 12, 17, 22,

7, 12, 17, 22 };

for(int step=0;step<16;step++)

{

Step(Registers[step][0], Registers[step][1], Registers[step][2], Registers[step][3], F, step, S[step], step);

}

//этап 2

S = new int[] { 5, 9, 14, 20,

5, 9, 14, 20,

5, 9, 14, 20,

5, 9, 14, 20 };

int[] K = new int[] { 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12 };

for (int step = 0; step < 16; step++)

{

Step(Registers[step][0], Registers[step][1], Registers[step][2], Registers[step][3], G, K[step], S[step], step + 16);

}

//этап 3

K = new int[] { 5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2 };

S = new int[] { 4, 11, 16, 23,

4, 11, 16, 23,

4, 11, 16, 23,

4, 11, 16, 23 };

for (int step = 0; step < 16; step++)

{

Step(Registers[step][0], Registers[step][1], Registers[step][2], Registers[step][3], H, K[step], S[step], step + 32);

}

K = new int[] { 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9 };

S = new int[] { 6, 10, 15, 21,

6, 10, 15, 21,

6, 10, 15, 21,

6, 10, 15, 21 };

for (int step = 0; step < 16; step++)

{

Step(Registers[step][0], Registers[step][1], Registers[step][2], Registers[step][3], I, K[step], S[step], step + 48);

}

Суммируем с результатом предыдущего цикла:

A = AA + A;

B = BB + B;

C = CC + C;

D = DD + D;

Данные берем из текстового файла

using (StreamReader rfile = new StreamReader("text.txt"))

{

v_txt = new string(rfile.ReadToEnd().ToCharArray());

}

Результат выполнения программы

Размещено на Allbest.ru

...