MD5 на C++. Шаг за шагом.



До этого момента, кроме кода и комментариев к нему, я ничего творческого не писал. Даже школьные сочинения по русской литературе я списывал из Интернета. Но все когда-то надо начинать впервые … но не в этот раз =). Ниже я представлю реализацию хеш-функции MD5 на языке C++. Программу я писал в среде C++Builder, но код можно легко перегнать в любой C++-компилятор.
UPD: в последнее время мне пришло несколько писем на почту, что алгоритм работает неверное. Я глянул, и, действительно, не верно =(. В связи с этим я решил исправить эту несправедливость. Нижеследующий код написан в MSVS на чистом C++ без использования функций и типов фирмы Borland (Embarcadero), таких как IntToHex() и String. Вместо типа String будет использован тип стандартной библиотеки шаблонов C++ - std::string, а вместо функции IntToHex мы используем стандартную функцию _itoa_s с небольшими доработками результата.
Описание алгоритма остается таким же, а вот код слегка изменится.

Краткое описание:

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

Код:

Сначала в .h – файл нашего проекта подключим библиотеку string для работы с типом std::string. Затем добавим прототипы функций, требуемых для работы алгоритма. В итоге заголовочный файл будет выглядеть так:

/* Деректива препроцессора #pragma once следит за тем, чтобы конкретный исходный файл при компиляции подключался только один раз*/ #pragma once #include /*«определяем» тип unsigned int как uint. Теперь везде в коде, где будет встречаться слово uint, компилятор будет вставлять unsigned int*/ typedef unsigned int uint;

std::string to_hex(uint value);
uint F(uint X, uint Y, uint Z);
uint G(uint X, uint Y, uint Z);
uint H(uint X, uint Y, uint Z);
uint I(uint X, uint Y, uint Z);
uint rotate_left(uint value, int shift);
std::string get_md5(std::string in);

Теперь опишем функции, которые потребуются для работы алгоритма:

Функция to_hex перегоняет в hex, полученное на входе, значение. Принцип работы аналогичен элементарному переводу из dec в bin: число делим на 256. Почему на 256, а не на 16, ведь при перегонке в bin делим на 2, а не на 4? - Потому что нам надо получить dec-значение сразу 2ух символов. Получаем остаток от деления на 256 и приводим его (остаток) в hex. И так до тех пор, пока входное значение нельзя будет нацело поделить на 256.

std::string to_hex(uint value) { std::string out; unsigned char hex; char hex_res[3]; while(value) { hex = value%256; _itoa_s(hex, hex_res, 16); if(hex_res[1] == '\0') { hex_res[1] = hex_res[0]; hex_res[0] = '0'; hex_res[2] = '\0'; } out.append(hex_res); value /= 256; } return out; }

Надеюсь, что все понятно без комментариев. Единственный момент, который хотелось бы уточнить, это хитрый блок if после вызова функции itoa. Дело в том, результат числа, занимающего 1 байт, будет помещен в первый байт выходного буфера и в строку будет добавлен только один байт. Но, так как результат хеширования требует высокой точности, то один байт представляется двумя с нулевым первый байтом.
Далее определим 4 базовые функции, которые преобразуют блоки данных. По своей сути эти функции и являются функциями "шифрования". Почему функции выглядят именно следующим образом - я не могу сказать. Могу сказать лишь то, что это часть алгоритма, придуманного умным человеком. Эти функции используют битовые операции, о которых Вы, вполне подробно, можете прочесть на wikipedia: ]]>http://ru.wikipedia.org/wiki/Битовые_операции]]>

uint F(uint X, uint Y, uint Z) {return ((X & Y) | ((~X) & Z));} uint G(uint X, uint Y, uint Z) {return (X & Z) | (Y & (~Z));} uint H(uint X, uint Y, uint Z) {return X ^ Y ^ Z;} uint I(uint X, uint Y, uint Z) {return Y ^ (X | (~Z));}

Таким образом, получая на вход три 32-разрядных регистра(слова), функция возвращает нам, скажем там, "закодированное" 32-разрядное слово. Кстати, под словом я понимаю 32-разрядную величину.

Функция rotate_left производит циклический сдвиг влево(о котором так же можно прочесть в вышеприведенной ссылке). Результат циклического сдвига отличается от результата логического сдвига. Представим ситуацию: утро, настроение у Вас не из лучших, т.к. пришлось встать рано, что бы успеть на учебу(работу или еще куда), но Вы все равно опаздываете. Еле-еле успев на автобус, Вы понимаете, что забыли дома проездной, и деньги на билетик. И тут, как назло, кондуктор-контроллер. Через все толпу контролер почти добрался до Вас...и что делаете Вы? Вы выходите из последней двери и заходите в первую(пока контроллер снова пробереться через всю толпу, Вы уже выйдите на своей остановке). Аналогично этому бытовому примеру работает и циклический сдвиг: бит который сдвинули с начала идет в конец, бит с конца - в начало. В функцию передаем два параметра: 1ый - 32-разярдное слово, над которым будем производить операцию, 2ой -количество бит для сдвига. Результат выполнения функции - 32-разярдное слово.

uint rotate_left(uint value, int shift) {return value << shift | value >> (32-shift);}

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

1)Расширение сообщения: сообщение расширяется таким образом, чтобы остаток деления его длины на 64(в байтах или 512 в битах) был равен 56(байтам или 448 битам). Почему 56 - поймете в шаге 2. Расширение происходит следующим образом: единичный бит добавляется в конец сообщения, а потом оно дополняется нулями.

2)Добавление длины сообщения: 64-разрядное представление входного сообщения (длины до того, как был выполнен шаг 1) добавляется в конец сообщения, полученного при выполнении шага 1 (для этого и нужен был остаток равный 56 байтам, что бы при добавлении 64-рязрядного сообщения, или, попросту, 8 байт, сообщение, которое далее будет зашифровываться, было кратно 64 байтам).

3)Инициализация MD буфера: для вычисления хеш-кода будем использовать 4 слова(32-разрядных) регистра A, B, C, D, таблицу констант T(она нужна для лучшей кодировки, по сравнению с MD4) и массив Х, в который записывается 32-разрядное представление выровненного сообщения.

4)Обработка сообщения в цикле: собственно это и есть сама кодировка. Шаг выполняется в 4 раунда, каждый раунд состоит из 16 операций(подробней о шаге 4 Вы узнаете из кода программы).

5)Вывод хеш-кода: по окончании 4ого шага хеш-код будет храниться в 4 регистрах (A, B, C, D). Все что нам надо - перегнать их в hex (с помощью вышеобъявленной функции to_hex).

Теперь описание функции get_md5:

{ int length = in.length();; //получаем длину входного сообщения. int rest = length%64; //остаток от деления на 64байта. int size = 0; //тут будет храниться размер сообщения после первых 2ух шагов.

//Шаг 1.
if(rest < 56) //если остаток от деления на 64 меньше 56
size = length - rest + 56 + 8; //подгоняем размер так, что бы он был кратен 64(+8 байт для 2ого шага).
else //иначе (если остаток больше 56)
size = length + 64 - rest + 56 + 8; //подгоняем размер так, что бы он был кратен 64(+8 байт для 2ого шага).

unsigned char *msg_for_decode = new unsigned char[size]; //создаем динамический массив для хранения сообщения, которое далее будет кодироваться

for(int i=0; i < length; i++) //первые length элементов сIn
msg_for_decode[i] = in[i]; //заполняем символами входного сообщения

msg_for_decode[length] = 0x80; //ставим в конец сообщения единичный бит.

for(int i = length + 1; i < size; i++) //а все остальное
msg_for_decode[i] = 0; //заполняем нулями

//Шаг 2.
__int64 bit_length = (uint)(length)*8; //длина сообщения в битах.

for(int i = 0; i < 8; i++) //последние 8 байт
msg_for_decode[size - 8 + i] = (unsigned char)(bit_length >> i * 8); //заполняем 64-битным представлением длины данных до выравнивания

//Шаг 3.
uint A=0x67452301, B=0xefcdab89, C=0x98badcfe, D=0x10325476; //Инициализируем начальные значения регистров.
uint T[64]; //64-элементная таблица данных (констант).

for(int i=0;i<64;i++) //всю таблицу констант
T[i]= uint(pow(2,32)*fabs(sin(i + 1)));; //заполняем в соответствии с алгоритмом.

//объявляем массив Х, в котором будет 32-разрядное представление сообщения.
uint *X=(uint*)(msg_for_decode); //загоняем в массив Х сообщение msg_for_decode.

//Шаг 4.
uint AA, BB, CC, DD;

for(int i=0;i {
AA = A;BB = B; CC = C; DD = D;

//раунд 1
A = B + rotate_left((A + F(B,C,D) + X[i+ 0] + T[ 0]), 7);
D = A + rotate_left((D + F(A,B,C) + X[i+ 1] + T[ 1]), 12);
C = D + rotate_left((C + F(D,A,B) + X[i+ 2] + T[ 2]), 17);
B = C + rotate_left((B + F(C,D,A) + X[i+ 3] + T[ 3]), 22);

A = B + rotate_left((A + F(B,C,D) + X[i+ 4] + T[ 4]), 7);
D = A + rotate_left((D + F(A,B,C) + X[i+ 5] + T[ 5]), 12);
C = D + rotate_left((C + F(D,A,B) + X[i+ 6] + T[ 6]), 17);
B = C + rotate_left((B + F(C,D,A) + X[i+ 7] + T[ 7]), 22);

A = B + rotate_left((A + F(B,C,D) + X[i+ 8] + T[ 8]), 7);
D = A + rotate_left((D + F(A,B,C) + X[i+ 9] + T[ 9]), 12);
C = D + rotate_left((C + F(D,A,B) + X[i+10] + T[10]), 17);
B = C + rotate_left((B + F(C,D,A) + X[i+11] + T[11]), 22);

A = B + rotate_left((A + F(B,C,D) + X[i+12] + T[12]), 7);
D = A + rotate_left((D + F(A,B,C) + X[i+13] + T[13]), 12);
C = D + rotate_left((C + F(D,A,B) + X[i+14] + T[14]), 17);
B = C + rotate_left((B + F(C,D,A) + X[i+15] + T[15]), 22);

//раунд 2
A = B + rotate_left((A + G(B,C,D) + X[i+ 1] + T[16]), 5);
D = A + rotate_left((D + G(A,B,C) + X[i+ 6] + T[17]), 9);
C = D + rotate_left((C + G(D,A,B) + X[i+11] + T[18]), 14);
B = C + rotate_left((B + G(C,D,A) + X[i+ 0] + T[19]), 20);

A = B + rotate_left((A + G(B,C,D) + X[i+ 5] + T[20]), 5);
D = A + rotate_left((D + G(A,B,C) + X[i+10] + T[21]), 9);
C = D + rotate_left((C + G(D,A,B) + X[i+15] + T[22]), 14);
B = C + rotate_left((B + G(C,D,A) + X[i+ 4] + T[23]), 20);

A = B + rotate_left((A + G(B,C,D) + X[i+ 9] + T[24]), 5);
D = A + rotate_left((D + G(A,B,C) + X[i+14] + T[25]), 9);
C = D + rotate_left((C + G(D,A,B) + X[i+ 3] + T[26]), 14);
B = C + rotate_left((B + G(C,D,A) + X[i+ 8] + T[27]), 20);

A = B + rotate_left((A + G(B,C,D) + X[i+13] + T[28]), 5);
D = A + rotate_left((D + G(A,B,C) + X[i+ 2] + T[29]), 9);
C = D + rotate_left((C + G(D,A,B) + X[i+ 7] + T[30]), 14);
B = C + rotate_left((B + G(C,D,A) + X[i+12] + T[31]), 20);

//раунд 3
A = B + rotate_left((A + H(B,C,D) + X[i+ 5] + T[32]), 4);
D = A + rotate_left((D + H(A,B,C) + X[i+ 8] + T[33]), 11);
C = D + rotate_left((C + H(D,A,B) + X[i+11] + T[34]), 16);
B = C + rotate_left((B + H(C,D,A) + X[i+14] + T[35]), 23);

A = B + rotate_left((A + H(B,C,D) + X[i+ 1] + T[36]), 4);
D = A + rotate_left((D + H(A,B,C) + X[i+ 4] + T[37]), 11);
C = D + rotate_left((C + H(D,A,B) + X[i+ 7] + T[38]), 16);
B = C + rotate_left((B + H(C,D,A) + X[i+10] + T[39]), 23);

A = B + rotate_left((A + H(B,C,D) + X[i+13] + T[40]), 4);
D = A + rotate_left((D + H(A,B,C) + X[i+ 0] + T[41]), 11);
C = D + rotate_left((C + H(D,A,B) + X[i+ 3] + T[42]), 16);
B = C + rotate_left((B + H(C,D,A) + X[i+ 6] + T[43]), 23);

A = B + rotate_left((A + H(B,C,D) + X[i+ 9] + T[44]), 4);
D = A + rotate_left((D + H(A,B,C) + X[i+12] + T[45]), 11);
C = D + rotate_left((C + H(D,A,B) + X[i+15] + T[46]), 16);
B = C + rotate_left((B + H(C,D,A) + X[i+ 2] + T[47]), 23);

//раунд 4
A = B + rotate_left((A + I(B,C,D) + X[i+ 0] + T[48]), 6);
D = A + rotate_left((D + I(A,B,C) + X[i+ 7] + T[49]), 10);
C = D + rotate_left((C + I(D,A,B) + X[i+14] + T[50]), 15);
B = C + rotate_left((B + I(C,D,A) + X[i+ 5] + T[51]), 21);

A = B + rotate_left((A + I(B,C,D) + X[i+12] + T[52]), 6);
D = A + rotate_left((D + I(A,B,C) + X[i+ 3] + T[53]), 10);
C = D + rotate_left((C + I(D,A,B) + X[i+10] + T[54]), 15);
B = C + rotate_left((B + I(C,D,A) + X[i+ 1] + T[55]), 21);

A = B + rotate_left((A + I(B,C,D) + X[i+ 8] + T[56]), 6);
D = A + rotate_left((D + I(A,B,C) + X[i+15] + T[57]), 10);
C = D + rotate_left((C + I(D,A,B) + X[i+ 6] + T[58]), 15);
B = C + rotate_left((B + I(C,D,A) + X[i+13] + T[59]), 21);

A = B + rotate_left((A + I(B,C,D) + X[i+ 4] + T[60]), 6);
D = A + rotate_left((D + I(A,B,C) + X[i+11] + T[61]), 10);
C = D + rotate_left((C + I(D,A,B) + X[i+ 2] + T[62]), 15);
B = C + rotate_left((B + I(C,D,A) + X[i+ 9] + T[63]), 21);

A += AA;
B += BB;
C += CC;
D += DD;
}

delete []msg_for_decode; //не забываем освободить память =)
//Шаг 5.
std::string res = to_hex(A) + to_hex(B) + to_hex(C) + to_hex(D); //заполняем выходную строку hex-//представлением, полученных в шаге 4, регистров.

return res; //возвращаем строку с хеш-кодом.
}

Пример использования:

int _tmain(int argc, _TCHAR* argv[])
{
std::cout << get_md5("grape") << std::endl;
return 0;
}

Я думаю, что с прокомментированный код не вызвал никаких вопросов. Но про шаг 4 я все же скажу. Шаг 4 придуман не мной и почему он реализован именно так как реализован, знает только автор алгоритма (ну не только он, может еще кто, но точно не я). Кодирование выполняется в цикле, т.к. длина входного сообщения может быть больше 55 байт, и в этом случаи, при отсутствии цикла, хеш-код получится неправильный.
Вот и все. Думаю эта статья будет полезна. В Интернете не трудно найти реализацию MD5, но пошаговую реализацию найти очень тяжело.

Отдельно поблагодарить Романа Костенко (Lord_of_fear) и Игоря Антонова (Spider_NET) за их помощь в написании этого алгоритма.
Так же, спасибо тем, кто все таки пользуется этим алгоритмом и указывает на ошибки.
Прикладываю два файла с реализацией алгоритма.

Written by: Сергей Дубовик aka sd
e-mail: eval(unescape('%64%6f%63%75%6d%65%6e%74%2e%77%72%69%74%65%28%27%3c%61%20%68%72%65%66%3d%22%6d%61%69%6c%74%6f%3a%73%64%62%6f%78%40%74%75%74%2e%62%79%22%3e%73%64%62%6f%78%40%74%75%74%2e%62%79%3c%2f%61%3e%27%29%3b'))

ВложениеРазмер
hashmd5.rar1.68 КБ

Комментарии

9 комментария(ев)
аватар: fenix_777
fenix_777
Дата: Пнд, 16/05/2011 - 05:35
Звание: Наблюдатель
Сообщений: 1

А в какой библиотеке прописан тип String и функция IntToHex?

аватар: sd
sd
Дата: Пнд, 16/05/2011 - 17:35
Звание: Энтузиаст
Сообщений: 158

Тип String - встроенный тип borland'а. Общий для языка C++ является тип string. Что бы его использовать - достаточно в начало кода добавить

#include
using namespace std;

Функция ToHex - пользовательская функция (т.е. функция, определенная самим программистом). Ее прототип объявляется в заголовочном файле (.h файле самого проекта), а ее тело описывается в .cpp файле проекта. В данной статье эта функция описана с подробными комментариями во второй кодовой вставке.

аватар: serj
serj
Дата: Втр, 05/07/2011 - 23:25
Звание: Наблюдатель
Сообщений: 2

на первый взгляд грамотно, но честно говоря пришлось отлаживать) косяки есть)
и есть пару вопросов =)
1)почему везде фигурирует 64, а не 512 ?
и 2) мне вот например нужно ещё получить полностью дополненное сообщение длиной по модулю 512, как это можно сделать ? =) хочу посмотреть лавинный эффект =)
а так впринципе удалось довести до рабочего состояния)

аватар: sd
sd
Дата: СБ, 09/07/2011 - 09:42
Звание: Энтузиаст
Сообщений: 158

1) Согласно алгоритму операции выполняются с битами, следовательно по алгоритму и идет значение в 512 бит. Если перевести в байты, то получится 64, что никак не влияет на работу алгоритма. Не важно в каких единицах мы работаем со словом, главное что мы с ним работает.
2) Ну это уже выходит за рамки алгоритма. Т.е. по алгоритму получается сообщение длиной по модулю 448. Если у Вас по ходу выполнения второго шага алгоритма получится слово, длиной по модулю 512, то Вы не получите MD5 хэш.

Все мы люди и все мы можем ошибаться. Не буду спорить, что статья написана не очень хорошо и что в ней отсутствуют ошибки и недочеты.
А в чем конкретно косяки? Не могли бы написать? Что бы те, кто будет использовать эту статью для себя знали что исправлять.

аватар: serj
serj
Дата: Пнд, 11/07/2011 - 03:54
Звание: Наблюдатель
Сообщений: 2

ну из того что помню:
1) откуда ваще берётся сообщение ? момента этого нет =)
2) напутанно с переменными, то они value и shift то A и B
uint RotateLeft(uint value, int shift)
{
return A << B | A >> (32-B);
}
3) второй блок md5 хеша считается неверно =) как вы думаете почему ?
uint T[64]; //64-элементная таблица данных (констатнт).
for(int i=1;i<=64;i++) //всю таблицу констант
T[i]= pow(2,32)*fabs(sin(i)); //заполняем в соответствии с алгоритмом.
Создаётся массив от 0 до 63 (64 элемента), а заполняется он начиная с первого.
В итоге 64 константа пишется в некуда и вот тут B = C + RotateLeft((B + I(C,D,A) + X[i+ 9] + T[64]), 21); берётся не полученное значение, а непонятно что =)
4) ещё было что-то по мелочи, но щас уже не помню =)
есть ощущение что код вообще не отлаживали)

p.s. а вообще большое спасибо =) щас дописываю к этому коду кое-что под свои нужды =)

аватар: sd
sd
Дата: СР, 13/07/2011 - 02:09
Звание: Энтузиаст
Сообщений: 158

По поводу (2) согласен. Сразу после прочтения Вашего комментария, я перечитал статью и нашел этот косяк. Только что добрался до выхода в Интернет и исправил.
Пункт №3 так же согласен, сейчас исправлю.

"есть ощущение что код вообще не отлаживали)" << Это была моя первая статья, а код писался вообще как часть курсового проекта. И я его не успевал написать вовремя, поэтому как только я получил верный хеш 10 случайных слов - я понес его сдавать.

P.S. Спасибо за замечания.

аватар: Наим Резаиан
Наим Резаиан
Дата: ВС, 23/12/2012 - 03:44
Звание: Наблюдатель
Сообщений: 1

где IntToHex?

аватар: wyvie
wyvie
Дата: Втр, 17/09/2013 - 18:08
Звание: Наблюдатель
Сообщений: 1

Я понимаю, что дофига времени прошло, но вдруг еще кто полезет.

Здесь утечка памяти. Теряется выделенная под X память, потому что происходит не копирование массива, а копирование указателя.

uint *X=new uint[size/4]; //создаем массив Х, в котором будет 32-разрядное представление сообщения.
X=(uint*)(cIn);

Надо так:
uint *X = 0;
X=(uint*)(cIn);

аватар: sd
sd
Дата: СБ, 31/05/2014 - 05:54
Звание: Энтузиаст
Сообщений: 158

Ребят, алгоритм был не совсем рабочий и по поводу утечки верное замечание. Исправил алгоритм, теперь все работает как надо и без утечек. Всем спасибо.