Реферат: Цифровая подпись

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() для битовых преобразований.