Среди односторонних алгоритмов хэширования наибольшей известностью пользуются два из них: алгоритм MD5 (message digest), разработанный профессором Массачусетского технологического института Роном Ривестом (Ron Rivest) (один из авторов популярной криптосистемы с ключом общего пользования RSA), и алгоритм Secure Hash Algorithm (SHA), созданный совместными усилиями Национального института по стандартизации и технологическим разработкам (NIST) и Управления национальной безопасности США (NSA). Результат анализа последовательности входных данных с помощью алгоритма MD5 - 128-разрядный цифровой идентификатор, а при использовании алгоритма SHA - 160-разрядное значение. Учитывая, что пока никому не удалось подобрать ключ ни к одному из названных алгоритмов, можно считать, что восстановление исходных данных по некоторому хэшированному значению, являющемуся результатом работы алгоритма SNA либо по некоторому коэффициенту алгоритма MD5 нереально. Таким образом, если вам отправили какой-то файл и идентификатор, полученный в результате применения к нему алгоритма MD5 или SHA, и если вы выполнили с ним тот же алгоритм хэширования и ваш результат совпал с исходным значением, определенно можно быть уверенным, что принятый вами файл не подвергся искажениям.
Алгоритм MD5
Терминология
В данном случае "word" является 32-х битной величиной, "byte" - 8-ми битная величина. Последовательность бит должна интерпретироваться таким же способом что и последовательность байт, где каждая последовательная группа из восьми бит интерпретируется как байт с старшим (наиболее значащим) битом каждого байта следующим в последовательности первым. Подобно последовательности байт должна интерпретироваться и последовательность 32-битных слов.
Запись x_i означает "x sub i" (т. е. х с индексом i). Если некоторое выражение используется как индекс, то оно берется в фигурные скобки, например x_{i+1}. Символ " ^ " используется для операций возведения в степень, т. е. x^i следует понимать как х в степени i.
Символ "+" обозначает операцию сложения слов (т. е. сложение по модулю 2^32). Далее x << s будет означать вычисление нового 32-х битного значения х путем циклического сдвига (вращения) предыдущего значения х на s бит влево. not(x) - поразрядная операция отрицания , x v y - поразрядное ИЛИ(OR) операндов x и y , x xor y – поразрядное исключающее ИЛИ(XOR) операндов x и y , и xy - поразрядное И(AND) операндов x и y.
Краткое описание алгоритма MD5
Вначале допускаем, что имеем на входе сообщение из b-бит, и что мы желаем найти Message Digest этой последовательности бит. Число b является произвольным неотрицательным целым; b может быть равным нулю, оно не обязательно должно быть множителем 8, и оно может быть произвольно большим. Представим последовательность бит сообщения как:
m0 m1 m2 . . . . . . m{b-1}
Следующие пять этапов выполняются для подсчета Message Digest сообщения.
Этап 1. Присоединение заполняющих (дополнительных) битов.
Сообщение расширяется так, чтобы его длина (в битах) совпадала с 448, по модулю 512. Дополнение всегда выполняется, даже если длина сообщения - уже совпадает с 448 по модулю 512. Дополнение выполняется следующим образом: одиночный "1" бит добавляется к сообщению, и далее "0" биты добавляются так что длина в битах заполняемого сообщения соответствует 448 по модулю 512. В общем случае, минимум один бит и максимум 512 бит добавляется.
Этап 2. Добавление длины
64-битное представление входной последовательности b (длина сообщения перед расширением дополнительными битами) присоединяется к результату предыдущего этапа. Маловероятно, что длина b будет больше, чем 264 поэтому и используется 64-х разрядная величина для хранения длины b. (Эти биты добавляются как два 32-х разрядных слова, младшее заносится первым).
В этом месте окончательное сообщение(после выполнения первого и второго этапов) имеет длину, кратную 512 битам, т. е. сообщение имеет длину, которая точно кратна 16-ти словам. Последовательность М[0 . . . . N-1] является словами окончательного сообщения, где N кратно 16.
Этап 3. Инициализация MD буфера.
Буфер на 4-е слова (A, B, C, D) используется для подсчета Message Digest. Каждое из A, B, C, D является 32-х битным регистром. Эти регистры инициализируются следующими шестнадцатиричными значениями, где первым следует самый младший байт:
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Программисты из RSA Data Security, Inc. , дабы не утруждать себя и остальных людей по поводу происхождения этих чисел, просто назвали их магическими константами.
Этап 4. Обработка сообщения в блоках по 16 слов.
Сначала определяются четыре вспомагательных функции каждая из которых имеет на входе три 32-битных слова и производит одно 32-битное слово на выходе.
F(X, Y, Z) = XY v not(X) Z
G(X, Y, Z) = XZ v Y not(Z)
H(X, Y, Z) = X xor Y xor Z
I(X, Y, Z) = Y xor (X v not(Z))
В каждой битовой позиции функция F действует как условный опреатор : если X то Y иначе Z. Функция F могла бы определяться с использованием операцию + вместо v, так как выражение XY and not(X)Z никогда не будет иметь 1 в одинаковых битовых позициях.
Если биты X, Y и Z независимы и несмещены(??), то каждый бит после выполнения F(X, Y, Z) будет независим и несмещен.
Функции G, H и I подобны функции F, они действуют в "побитовом соответствии" для нахождения выходного значения от входных битов X, Y и Z, тем же способом, что если биты X, Y и Z независимы и несмещены, то каждый бит после выполнения вышеуказанных функций будет независим и несмещен. Обратите внимание, что функция H(X, Y, Z) является поразрядной операцией исключающего ИЛИ (т. е. функцией контроля четности входных значений). Далее на этом этапе происходит четыре цикла, в которых происходит трансформация битов сообщения при помощи вышеуказанных
функций, функций циклического сдвига, и таблицы константных значений.
Этап 5. Вывод
В результате выполнения предыдущих этапов Message Digest производит на выходе числа A, B, C, D, общая длина которых 128 бит.
Резюме
Алгоритм получает на входе сообщение произвольной длины и после обработки на выходе получаем 128-битный "отпечаток" или "Message Digest". Предполагается, что вычислительная трудоемкость нахождения двух сообщений, имеющих одинаковые Message Digest очень велика. MD5 алгоритм предназначен для приложений, формирующих цифровые сигнатуры, в которых большой файл должен быть "сжат" безопасным способом перед зашифровкой открытым (или секретным)ключом в некоторой криптосистеме с открытым ключом, такой как RSA.
MD5 алгоритм является расширением алгоритма MD4.
MD5 алгоритм полностью разработан для быстрой работы на 32-х разрядных машинах. К тому же алгоритм не требует каких-либо больших подстановочных таблиц; обеспечивается компактная кодировка.
MD5 Message Digest алгоритм прост в использовании, и обеспечивает получение 128-ми битного "отпечатка" или Message Digest сообщения произвольной длины.
Предполагается, что сложность нахождения двух сообщений, которые произведут одинаковые Message Digest является порядка 2 в 64 степени операций, и сложность построения сообщения по некоторому известному Message Digest является порядка 2 в 128 степени операций.
Примеры исходного кода для реализации MD5.
Макросы
F, G, H, I
Данные макросы определяют четыре вспомогательных функции, каждая из которых имеет на входе три 32-битных слова и производит одно 32-битное слово на выходе.
#define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) | (~z)))
В каждой битовой позиции функция F действует как условный оператор : если X то Y иначе Z. Если биты X, Y и Z независимы и несмещены (??), то каждый бит после выполнения F(X, Y, Z) будет независим и несмещен.
Функции G, H и I подобны функции F, они действуют в "побитовом соответствии" для нахождения выходного значения от входных битов X, Y и Z, тем же способом, что если
биты X, Y и Z независимы и несмещены, то каждый бит после выполнения вышеуказанных функций будет независим и несмещен. Следует обратить внимание, что функция H(X, Y, Z) является поразрядной операцией исключающего ИЛИ (т. е. функцией контроля четности входных значений).
FF, GG, HH, II
Данные макросы определяют четыре вспомагательных функции, которые на входе получают семь 32-х разрядных параметров, а на выходе получаем одну 32-х разрядную величину.
Эти фунции используются в функции Transform() для битовых преобразований.
Функции работают следующим образом:
1. В выходной параметр записывается сумма соответствующей функции (для FF() это F(), для GG() это G(), для HH() это H(), для II() это I()) от 2-го, 3-го и 4-го параметров с 5-м и 7-м параметрами.
2. Производится циклический сдвиг влево выходного параметра на количество бит, указанное в 6-м входном параметре.
3. Производится приращение выходного параметра на величину, указанную во 2-м входном параметре.
#define FF(a, b, c, d, x, s, ac) /
{(a) += F ((b), (c), (d)) + (x) + (UINT4)(ac); /
(a) = ROTATE_LEFT ((a), (s)); /
(a) += (b); /
}
#define GG(a, b, c, d, x, s, ac) /
{(a) += G ((b), (c), (d)) + (x) + (UINT4)(ac); /
(a) = ROTATE_LEFT ((a), (s)); /
(a) += (b); /
}
#define HH(a, b, c, d, x, s, ac) /
{(a) += H ((b), (c), (d)) + (x) + (UINT4)(ac); /
(a) = ROTATE_LEFT ((a), (s)); /
(a) += (b); /
}
#define II(a, b, c, d, x, s, ac) /