Хэш данные. Хеш-функции в криптографии

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

Цель лекции: познакомиться с понятием "хеш-функция", а также с принципами работы таких функций.

Понятие хеш-функции

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

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

Смысл хеш-функции состоит в определении характерного признака прообраза – значения хеш-функции. Это значение обычно имеет определенный фиксированный размер, например, 64 или 128 бит. Хеш-код может быть в дальнейшем проанализирован для решения какой-либо задачи. Так, например, хеширование может применяться для сравнения данных: если у двух массивов данных хеш-коды разные, массивы гарантированно различаются; если одинаковые - массивы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет из-за того, что количество значений хеш-функций всегда меньше, чем вариантов входных данных. Следовательно, существует множество входных сообщений, дающих одинаковые хеш-коды (такие ситуации называются коллизиями ). Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

Хеш-функции широко применяются в современной криптографии.

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

Например, пусть исходное сообщение, переведенное в цифровой вид, было следующим (в шестнадцатеричном формате):

Переведем сообщение в двоичный вид, запишем байты друг под другом и сложим биты в каждом столбике по модулю 2:

0011 1110 0101 0100 1010 0000 0001 1111 1101 0100 ---------- 0110 0101

Результат (0110 0101 (2) или 65 (16) ) и будет значением хеш-функции.

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

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

Сформулируем основные требования, предъявляемые к криптографическим хеш-функциям:

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

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

В настоящее время на практике в качестве хеш-функций применяются функции, обрабатывающие входное сообщение блок за блоком и вычисляющие хеш-значение h i для каждого блока M i входного сообщения по зависимостям вида

h i =H(M i ,h i-1),

где h i-1 – результат, полученный при вычислении хеш-функции для предыдущего блока входных данных.

В результате выход хеш-функции h n является функцией от всех n блоков входного сообщения.

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

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

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

• практически невозможно без знания ключа шифрования вычисление хеш-значения для заданного открытого массива информации;
• практически невозможен без знания ключа шифрования подбор открытых данных под заданное значение хеш-функции.

Сформированное таким образом хеш-значение обычно называют имитовставкой или аутентификатором и используется для проверки целостности сообщения. Таким образом, имитовставка – это контрольная комбинация, зависящая от открытых данных и секретной ключевой информации. Целью использования имитовставки является обнаружение всех случайных или преднамеренных изменений в массиве информации. Значение, полученное хеш-функцией при обработке входного сообщения, присоединяется к сообщению в тот момент, когда известно, что сообщение корректно. Получатель проверяет целостность сообщения путем вычисления имитовставки полученного сообщения и сравнения его с полученным хеш-кодом, который должен быть передан безопасным способом. Одним из таких безопасных способов может быть шифрование имитовставки закрытым ключом отправителя, т.е. создание подписи. Возможно также шифрование полученного хеш-кода алгоритмом симметричного шифрования, если отправитель и получатель имеют общий ключ симметричного шифрования.

Указанный процесс получения и использования имитовставки описан в отечественном стандарте ГОСТ 28147-89. Стандарт предлагает использовать младшие 32 бита блока, полученного на выходе операции шифрования всего сообщения в режиме сцепления блоков шифра для контроля целостности передаваемого сообщения. Таким же образом для формирования имитовставки можно использовать любой блочный алгоритм симметричного шифрования .

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

На самом деле возможны еще несколько схем использования блочного шифра для формирования хеш-функции. Пусть М i – блок исходного сообщения, h i – значение хеш-функции на i-том этапе, f – блочный алгоритм шифрования, используемый в режиме простой замены, – операция сложения по модулю 2. Тогда возможны, например, следующие схемы формирования хеш-функции:

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

Основным недостатком хеш-функций, спроектированных на основе блочных алгоритмов, является относительно низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хеширования, спроектированных самостоятельно, с нуля, исходя из требований криптостойкости (наиболее распространенные из них – MD5, SHA-1, SHA-2 и ГОСТ Р 34.11-94).

Лекция

доцента кафедры ИВТ Гродненского госуниверситета

канд. техн. наук Ливак Елены Николаевны

Функции хэширования.

Механизм хэш-функций

Функции хэширования играют главную роль в современной криптографии.

В настоящее время механизм хэш-функций используется на практике очень широко.

С помощью хэш-функций реализуют

1.Проверку целостности данных (обнаружение изменений)

Идея заключается в сохранении хэш-кода и последующем сравнении с эталоном повторно вычисленного для тех же данных хэш-значения.

Очевидно, что неравенство сравниваемых величин означает нарушение целостности.

2.Системы аутентификации

Используют хэширование паролей.

3.Создание и проверку ЭЦП

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

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

1)по заданному y = h ( x ) определить x (односторонняя функция h );

2)для заданного x найти другое x´ , такое, что h(x)= h(x´) (свободная от коллизий функция h );

3)найти пару x, x´ (x ≠ x´) , такую, что h(x)= h(x´) (строго свободная от коллизий функция h ).

Обратим внимание, значение хэш-функции также называют

Хэш-код

Функция (значение) свертки

Профиль сообщения

Дайджест сообщения

Криптографическая контрольная сумма

Цифровой отпечаток

Код аутентичности сообщения

Код обнаружения манипуляций

Функции хэширования (Алгоритмы создания дайджестов сообщений)

Перечислим и кратко охарактеризуем наиболее часто используемые функции хэширования, применяемые для ЭЦП.

SHA - Secure Hash Algorithm (1992)

160-разрядный хэш-код (дайджест). НЕ устойчив к коллизиям.

512- битовые блоки .

SHA-1 - Secure Hash Algorithm 1 (1995)

Модификация SHA . Исправлены недостатки. Решает проблему коллизий.

· MAC - Message Authentication Code - код аутентификации (проверки подлинности) сообщения.

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

· HMAC

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

Алгоритм HMAC [представлен в документе RFC 2104] принят как обязательный в протоколе IPSec и используется в ряде других протоколов Internet (TLS , SET и другие)

Широко используются на практике также функции, разработанные Роном Ривестом:

· MD2 - Message Digest #2

Низкоскоростной, но очень надежный алгоритм, создающий 128-разрядные дайджесты данных любого объема.

MD4 - Message Digest #4 (1990)

Более скоростной, но менее надежный алгоритм, создающий 128-разрядные дайджесты данных любого объема. 512-битовые блоки. Есть дефекты.

· MD5 - Message Digest #5 (1992)

Версия MD 4 с повышенной надежностью, преимущества также и в скорости. 128-разрядные дайджесты данных любого объема.

Неустойчив к коллизиям! Не используется для долговременных ЭЦП.

Обратим внимание, что алгоритмы SHA надежнее алгоритмов MDx , так как вырабатывают более длинный хэш-код (160 бит против 128 бит), что снижает вероятность того, что разные входные последовательности будут преобразованы в одно значение хэш-кода.

Современные технологии распределенных вычислений и многопроцессорные компьютеры демонстрируют недостаточную защищенность 128-битовых хэш-кодов. «Кроме того, были разработаны сценарии целого ряда атак, демонстрирующих уязвимость MD 5 в отношении современных методов криптоанализа» [Шнайер].

Однако, до сих пор не разработаны атаки, демонстрирующие уязвимость SHA в отношении современных методов криптоанализа; «сведения об успешных криптографических атаках на алгоритм SHA отсутствуют» [Шнайер].

Заметим также, что в российском стандарте ГОСТ Р 34.11-94 (в основе схемы Эль-Гамаля и Шнорра) длина хэш-кода равна 256 битам.

Защищенная функция хэширования SHA –1 (Secure Hash Algorithm )

Алгоритм SHA был разработан Национальным институтом стандартов и технологии США (NIST ) и опубликован в виде федерального стандарта обработки информации в 1993 г. Пересмотренная версия вышла в 1995 г.

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

Основные характеристики алгоритма SHA приведены в таблице.

Основные характеристики SHA

Вычисление значения хеш-функции в соответствии с алгоритмом SHA –1 происходит следующим образом (схему алгоритма в рисунках см . в презентации к лекции).

1.На вход поступает k -бит ов ый блок данных, где k < 2 64 .

2. k -битовый блок дополняется так, чтобы его длина стала кратной 512 разрядам (данные обрабатываются 512-битовыми блоками). Структура дополнения следующая: 100...0 (от 1 до 512 бит).

3.К полученному результату добавляется 64-битовое представление длины исходного блока данных.

4.Инициализируются пять 32-разрядных переменных:

A = 0x67452301

B = 0xefcdab89

C = 0x98badcfe

D = 0x10325476

E = 0 xc 3 d 2 e 1 f 0

5.Производится обработка 512-битовых блоков данных в 4 раунда по 20 операций каждый.

На рисунке (см . в презентации к лекции) представлена схема одной операции SHA . Циклический сдвиг влево на s разрядов обозначен « s ; W t – подблок дополненного сообщения такой, что:

W t = M t (0 ≤ t ≤ 15), где M t – 32-битовый блок данных

W t = (W t-3 ⊕ W t-8 ⊕ W t-14 ⊕ W t-16) « 1 (16 ≤ t ≤ 79).

Соответствие аддитивных констант K t и нелинейных функций F t номеру операции представлено в таблице (см . презентацию к лекции).

6.Значения переменных a , b , c , d , e складываются, соответственно, с A , B , C , D , E .

7.Обрабатывается следующий блок данных.

8.Окончательный результат получается конкатенацией значений A , B , C , D , E .

На выходе получается 160-битовый хэш-код.

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

1. на вход хэш-функции подается сообщение произвольной длины;
2. на выходе хэш-функции формируется блок данных фиксированной длины;
3. значения на выходе хэш-функции распределены по равномерному закону;
4. при изменении одного бита на входе хэш-функции существенно изменяется выход.

Кроме того, для обеспечения устойчивости хэш-функции к атакам она должна удовлетворять следующим требованиям:

1. если мы знаем значение хэш-функции h , то задача нахождения сообщения M такого, что Н(М) = h , должна быть вычислительно трудной;
2. при заданном сообщении M задача нахождения другого сообщения M’, такого, что Н(М) = H(M’), должна быть вычислительно трудной.

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

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

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

Если вспомнить, насколько рандомизируют входное сообщение блочные шифры, можно в качестве функции хэш-преобразования использовать какой-нибудь блочный шифр. То, что блочные шифры являются обратимыми преобразованиями, не противоречит свойствам хэш-функции, поскольку блочный шифр необратим по ключу шифрования, и, если в качестве ключа шифрования использовать выход предыдущего шага хэш-преобразования, а в качестве шифруемого сообщения очередной блок сообщения (или наоборот), то можно получить хэш-функцию с хорошими криптографическими характеристиками. Такой подход использован, например, в российском стандарте хэширования – ГОСТ Р 34.11-94. Эта хэш-функция формирует 256-битное выходное значение, используя в качестве преобразующей операции блочный шифр ГОСТ 28147-89 (рис.2.17). Функция хэширования H получает на вход хэш, полученный на предыдущем шаге (значение h 0 произвольное начальное число), а также очередной блок сообщения m i . Ее внутренняя структура представлена на рис.2.18. Здесь в блоке шифрующего преобразования для модификации h i в s i используется блочный шифр ГОСТ 28147-89. Перемешивающее преобразование представляет собой модифицированную перестановку Фейштеля. Для последнего блока m N (N – общее количество блоков сообщения) выполняется набивка до размера 256 бит с добавлением истинной длины сообщения.Параллельно подсчитывается контрольная суммасообщения ∑ и суммарная длина L, которые участвуют в финальной функции сжатия.

Основным недостатком хэш-функций на основе блочных шифров является невысокая скорость их работы. Поэтому были спроектированы ряд специализированных алгоритмов, которые, обеспечивая аналогичную стойкость к атакам, выполняют гораздо меньшее количество операций над входными данными и обеспечивают большую скорость работы. Примерами подобного рода алгоритмов являются: MD2, MD4, MD5, RIPEMD – 160, SHA. Рассмотрим подробнее структуру алгоритма хэширования SHA (Secure Hash Algorithm), который описан в стандарте SHS и обеспечивает безопасность электронной цифровой подписи DSA, формируя 160-битный дайджест сообщения.

Сначала сообщение разбивается на блоки длиной 512 бит. Если длина сообщения не кратна 512, к последнему блоку приписывается справа 1, после чего он дополняется нулями до 512 бит. В конец последнего блока записывается код длины сообщения. В результате сообщение приобретает вид n 512-разрядных блоков M 1 , M 2 , …, M n .

Алгоритм SHA использует 80 логических функций f 0 , f 1 , …, f 79 , которые производят операции над тремя 32-разрядными словами (B,C,D):

В алгоритме используются также специальным образом инициализированные 4 константы K i и 5 начальных значений H i .

Делим массив M на группы из 16 слов W 0 , W 1 ,…,W 15 (W 0 самое левое слово).
Для t = 16 - 79 W t = S 1 (W t-3 ⊕ W t-8 ⊕ W t-14 ⊕ W t-16)
S k означает операцию циклического сдвига влево на k разрядов.
Пусть теперь A = H 0 , B = H 1 , C = H 2 , D = H 3 , E = H 4 .
for t = 0 to 79 do
TEMP = S 5 (A) + f t (B, C, D) + E + W t + K i .
E = D; D = C; C = S 30 (B); B = A; A = TEMP;
Пусть H 0 = H 0 + A; H 1 = H 1 + B; H 2 = H 2 + C; H 3 = H 3 + D; H 4 = H 4 + E.

Графически один цикл SHA представлен на рис.2.19.

В результате обработки массива М будет получено 5 слов H 0 , H 1 , H 2 , H 3 , H 4 с общей длиной 160 бит, которые и образуют дайджест сообщения.

Из приведенных данных ясно, что сложность американского стандарта хэширования ниже, чем у российского. Российский стандарт предполагает выполнение четырех шифрований за один цикл выработки хэша, или в общей сложности 128 раундов. Каждый раунд шифрования требует примерно полтора десятка элементарных машинных операций, что существенно увеличивает затраты машинного времени на выполнение линейных перемешивающих операций. Один раунд выработки хэша SHA гораздо проще: он весь может быть реализован примерно за 15-20 команд, общее количество раундов всего 80, и за один цикл выработки хэша обрабатывается вдвое больше исходных данных - 512 против 256 в ГОСТ P34.ll - 94. Таким образом, можно предположить, что быстродействие программных реализаций SHA будет примерно в 3-6 раз быстрее, чем у отечественного стандарта.

Основная задача хэш-функций – генерация дайджестов, уникальных для конкретного документа. Если для двух различных входных блоков хэш-функция дает одинаковый дайджест, такая ситуация называется хэш-коллизией . Из теоремы, носящей название «парадокс дней рождения», следует, что для n-битного хэш-значения необходимо в среднем 2 n/2 различных входных сообщений, чтобы возникла коллизия. Это делает практически невозможным изменение документа при его подписи с помощью, например, алгоритма SHА путем простого подбора, поскольку при таком подходе потребуется сгенерировать около 2 80 различных сообщений, чтобы получить аналогичное подменяемому по получаемому дайджесту. Эта цифра недостижима для современного уровня технологий.

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

Целью аутентификации электронных документов является их защита от возможных видов злоумышленных действий, к которым относятся:

• активный перехват - нарушитель, подключившийся к сети, перехватывает документы (файлы) и изменяет их;
• маскарад - абонент С посылает документ абоненту В от имени абонента А;
• ренегатство - абонент А заявляет, что не посылал сообщения абоненту В, хотя на самом деле послал;
• подмена - абонент В изменяет или формирует новый документ и заявляет, что получил его от абонента А;
• повтор - абонент С повторяет ранее переданный документ, который абонент А посылал абоненту В.

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

При обработке документов в электронной форме совершенно непригодны традиционные способы установления подлинности по рукописной подписи и оттиску печати на бумажном документе. Принципиально новым решением является электронная цифровая подпись (ЭЦП ).

Электронная цифровая подпись используется для аутентификации текстов, передаваемых по телекоммуникационным каналам. Функционально она аналогична обычной рукописной подписи и обладает ее основными достоинствами:

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

Цифровая подпись представляет собой относительно небольшое количество дополнительной цифровой информации, передаваемой вместе с подписываемым текстом.

Система ЭЦП включает две процедуры: 1) процедуру постановки подписи; 2) процедуру проверки подписи. В процедуре постановки подписи используется секретный ключ отправителя сообщения, в процедуре проверки подписи - открытый ключ отправителя.

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

При проверке ЭЦП получатель сообщения снова вычисляет хэш-функцию m = h(М) принятого по каналу текста М, после чего при помощи открытого ключа отправителя проверяет, соответствует ли полученная подпись вычисленному значению m хэш-функции.

Принципиальным моментом в системе ЭЦП является невозможность подделки ЭЦП пользователя без знания его секретного ключа подписывания.

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

Каждая подпись содержит следующую информацию:

• дату подписи;
• срок окончания действия ключа данной подписи;
• информацию о лице, подписавшем файл (Ф.И.0., должность, краткое наименование фирмы);
• идентификатор подписавшего (имя открытого ключа);
• собственно цифровую подпись.

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

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

1. хэш-функция должна быть чувствительна к всевозможным изменениям в тексте М, таким как вставки, выбросы, перестановки и т.п.;
2. хэш-функция должна обладать свойством необратимости, то есть задача подбора документа М" , который обладал бы требуемым значением хэш-функции, должна быть вычислительно неразрешима;
3. вероятность того, что значения хэш-функций двух различных документов (вне зависимости от их длин) совпадут, должна быть ничтожно мала.

Большинство хэш-функций строится на основе однонаправленной функции f(·) , которая образует выходное значение длиной n при задании двух входных значений длиной n . Этими входами являются блок исходного текста М, и хэш-значение Н i-1 предыдущего блока текста (рис.1).

Рис.1. Построение однонаправленной хэш-функции

Н i = f(М i , Н i-1) .

Хэш-значение, вычисляемое при вводе последнего блока текста, становится хэш-значением всего сообщения М.

В результате однонаправленная хэш-функция всегда формирует выход фиксированной длины n (независимо от длины входного текста).

Основы построения хэш-функций

Общепринятым принципом построения хэш-функций является итеративная последовательная схема . По этой методики ядром алгоритма является преобразование k бит в n бит. Величина n - разрядность результата хэш-функции, а k - произвольное число, большее n . Базовое преобразование должно обладать всеми свойствами хэш-функции т.е. необратимостью и невозможностью инвариантного изменения входных данных.

Хэширование производится с помощью промежуточной вспомогательной переменной разрядностью в n бит. В качестве ее начального значения выбирается произвольное известное всем сторонам значение, например, 0.

Входные данные разбиваются на блоки по (k-n) бит. На каждой итерации хэширования со значением промежуточной величины, полученной на предыдущей итерации, объединяется очередная (k-n) -битная порция входных данных, и над получившимся k -битным блоком производится базовое преобразование. В результате весь входной текст оказывается "перемешанным" с начальным значением вспомогательной величины. Из-за характера преобразования базовую функцию часто называют сжимающей . Значение вспомогательной величины после финальной итерации поступает на выход хэш-функции (рис.2). Иногда над получившимся значением производят дополнительные преобразования. Но в том случае, если сжимающая функция спроектирована с достаточной степенью стойкости, эти преобразования излишни.

При проектировании хэш-функции по итеративной схеме возникают два взаимосвязанных вопроса: как поступать с данными, не кратными числу (k-n) , и как добавлять в хэш-сумму длину документа, если это требуется. Есть два варианта решения этих вопросов. В первом варианте в начало документа перед хэшированием добавляется поле фиксированной длины (например, 32 бита), в котором в двоичном виде записывается исходная длина текста. Затем объединенный блок данных дополняется нулями до ближайшего кратного (k-n) бит размера. Во втором варианте документ дополняется справа одним битом "1", а затем до кратного (k-n) бит размера битами "0". В этом варианте необходимость в поле длины отпадает - никакие два разных документа после выравнивания по границе порций не станут одинаковыми.

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

Рис.2. Итерактивная хэш-функция

Однонаправленные хэш-функции на основе симметричных блочных алгоритмов

Однонаправленную хэш-функцию можно построить, используя симметричный блочный алгоритм. Наиболее очевидный подход состоит в том, чтобы шифровать сообщение М посредством блочного алгоритма в режиме СВС или СFВ с помощью фиксированного ключа и некоторого вектора инициализации IV. Последний блок шифртекста можно рассматривать в качестве хэш-значения сообщения М. При таком подходе не всегда возможно построить безопасную однонаправленную хэш-функцию, но всегда можно получить код аутентификации сообщения МАС (Message Authentication Code).

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

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

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

Н 0 = I н, Н i = Е A (В) Å С, где Å - сложение по модулю 2 (исключающее ИЛИ); I н - некоторое случайное начальное значение; А, В, С могут принимать значения М i , Н i-1 , (М i Å Н i-1) или быть константами.

Рис.3. Обобщенная схема формирования хэш-функции

Сообщение М разбивается на блоки М i принятой длины, которые обрабатываются поочередно.

Три различные переменные А, В, С могут принимать одно из четырех возможных значений, поэтому в принципе можно получить 64 варианта общей схемы этого типа. Из них 52 варианта являются либо тривиально слабыми, либо небезопасными. Остальные 12 схем безопасного хэширования, у которых длина хэш-значения равна длине блока перечислены в табл.1.

Первые четыре схемы хэширования, являющиеся безопасными при всех атаках, приведены на рис.4.

Рис.4. Четыре схемы безопасного хэширования

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

Алгоритм MD5

Алгоритм MD5 (Message Digest №5) разработан Роналдом Риверсом. MD5 использует 4 многократно повторяющиеся преобразования над тремя 32-битными величинами U, V и W:

F(U,V,W)=(U AND V) OR ((NOT U) AND W) g(U,V,W)=(U AND W) OR (V AND (NOT W)) h(U,V,W)=U XOR V XOR W k(U,V,W)=V XOR (U OR (NOT W)).

В алгоритме используются следующие константы:

• начальные константы промежуточных величин - H=67452301 16 , H=EFCDAB89 16 , H=98BADCFE 16 , H=10325476 16 ;
• константы сложения в раундах - y[j]=HIGHEST_32_BITS(ABS(SIN(j+1))) j=0...63 , где функция HIGHEST_32_BITS(X) отделяет 32 самых старших бита из двоичной записи дробного числа X , а операнд SIN(j+1) считается взятым в радианах;
• массив порядка выбора ячеек в раундах - z = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12, 5, 8, 11, 4, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2, 0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9);
• массив величины битовых циклических сдвигов влево - s = (7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21).

На первоначальном этапе входной блок данных дополняется одним битом "1". Затем к нему добавляется такое количество битов "0", чтобы остаток от деления блока на 512 составлял 448. Наконец, к блоку добавляется 64-битная величина, хранящая первоначальную длину документа. Получившийся входной поток имеет длину кратную 512 битам.

Каждый 512-битный блок, представленный в виде 16 32-битных значений X...X , проходит через сжимающую функцию, которая перемешивает его со вспомогательным блоком (H,H,H,H) :

(A,B,C,D) = (H,H,H,H) цикл по j от 0 до 15 T = (A + f(B,C,D) + x] + y[j]) ROL s[j] (A,B,C,D) = (D,B+T,B,C) конец_цикла цикл по j от 16 до 31 T = (A + g(B,C,D) + x] + y[j]) ROL s[j] (A,B,C,D) = (D,B+T,B,C) конец_цикла цикл по j от 32 до 47 T = (A + h(B,C,D) + x] + y[j]) ROL s[j] (A,B,C,D) = (D,B+T,B,C) конец_цикла цикл по j от 48 до 63 T = (A + k(B,C,D) + x] + y[j]) ROL s[j] (A,B,C,D) = (D,B+T,B,C) конец_цикла (H,H,H,H) = (H+A,H+B,H+C,H+D)

После того, как все 512-битные блоки прошли через процедуру перемешивания, временные переменные H,H,H,H , а 128-битное значение подается на выход хэш-функции.

Алгоритм MD5, основанный на предыдущей разработке Роналда Риверса MD4, был призван дать еще больший запас прочности к криптоатакам. MD5 очень похож на MD4. Отличие состоит в простейших изменениях в алгоритмах наложения и в том, что в MD4 48 проходов основного преобразования, а в MD5 - 64. Несмотря на большую популярность, MD4 "медленно, но верно" был взломан. Сначала появились публикации об атаках на упрощенный алгоритм. Затем было заявлено о возможности найти два входных блока сжимающей функции MD4, которые порождают одинаковый выход. Наконец, в 1995 году было показано, что найти коллизию, т.е. "хэш-двойник" к произвольному документу, можно менее чем за минуту, а добиться "осмысленности" фальшивого документа (т.е. наличия в нем только ASCII-символов с определенными "разумными" законами расположения) - всего лишь за несколько дней.

Алгоритм безопасного хэширования SНА

Алгоритм безопасного хэширования SНА (Secure Hash Algorithm ) разработан НИСТ и АНБ США в рамках стандарта безопасного хэширования SHS (Secure Hash Standard) в 1992 г. Алгоритм хэширования SНА предназначен для использования совместно с алгоритмом цифровой подписи DSА.

При вводе сообщения М произвольной длины менее 2 64 бит алгоритм SНА вырабатывает 160-битовое выходное сообщение, называемое дайджестом сообщения МD (Message Digest). Затем этот дайджест сообщения используется в качестве входа алгоритма DSА, который вычисляет цифровую подпись сообщения М. Формирование цифровой подписи для дайджеста сообщения, а не для самого сообщения повышает эффективность процесса подписания, поскольку дайджест сообщения обычно намного короче самого сообщения.

Такой же дайджест сообщения должен вычисляться пользователем, проверяющим полученную подпись, при этом в качестве входа в алгоритм SНА используется полученное сообщение М.

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

Рассмотрим подробнее работу алгоритма хэширования SНА. Прежде всего исходное сообщение М дополняют так, чтобы оно стало кратным 512 битам. Дополнительная набивка сообщения выполняется следующим образом: сначала добавляется единица, затем следуют столько нулей, сколько необходимо для получения сообщения, которое на 64 бита короче, чем кратное 512, и наконец добавляют 64-битовое представление длины исходного сообщения.

Инициализируется пять 32-битовых переменных в виде:

А = 0х67452301 В = 0хЕFСDАВ89 С = 0х98ВАDСFЕ D = 0x10325476 Е = 0хС3D2Е1F0

Затем начинается главный цикл алгоритма. В нем обрабатывается по 512 бит сообщения поочередно для всех 512-битовых блоков, имеющихся в сообщении. Первые пять переменных А, В, С, D, Е копируются в другие переменные a, b, с, d, е:

А = А, b = В, с = С, d = D, е = Е

Главный цикл содержит четыре цикла по 20 операций каждый. Каждая операция реализует нелинейную функцию от трех из пяти переменных а, b, с, d, е, а затем производит сдвиг и сложение.

Алгоритм SНА имеет следующий набор нелинейных функций:

F t (Х, Y, Z) = (X Ù Y) Ú ((Ø X) Ù Z) для t = 0...19, f t (Х, Y, Z) =Х Å Y Å Z для t = 20...39, f t (Х, Y, Z) = (X Ù Y) Ú (X Ù Z) Ú (Y Ù Z) для t = 40...59, f t (Х, Y, Z) = Х Å Y Å Z для t = 60...79, где t - номер операции.

В алгоритме используются также четыре константы:

К t = 0х5А827999 для t = 0...19, К t = 0х6ЕD9ЕВА1 для t = 20...39, К t = 0х8F1ВВСDС для t = 40...59, К t = 0хСА62С1D6 для t = 60...79.

Блок сообщения преобразуется из шестнадцати 32-битовых слов (М 0 ...М 15) в восемьдесят 32-битовых слов (W 0 ...W 79) с помощью следующего алгоритма:

W t = М t для t = 0...15, W t = (W t-3 Å W t-8 Å W t-14 Å W t-16) <<< 1 для t = 16...79,
где t - номер операции, W t - t -й субблок расширенного сообщения, <<< S - циклический сдвиг влево на S бит.

С учетом введенных обозначений главный цикл из восьмидесяти операций можно описать так:

Цикл по t от 0 до 79 ТЕМР = (а <<< 5) + f t (b, c, d) + е + W t + К t е = d d = с с = (b <<< 30) b = а а = ТЕМР конец_цикла

Схема выполнения одной операции показана на рис.5.

Рис.5. Схема выполнения одной операции алгоритма SHA

После окончания главного цикла значения а, b, с, d, е складываются с А, В, С, D, Е соответственно, и алгоритм приступает к обработке следующего 512-битового блока данных. Окончательный выход формируется в виде конкатенации значений А, В, С, D, Е.

Отличия SHA от MD5 состоят в следующем:

• SНА выдает 160-битовое хэш-значение, поэтому он более устойчив к атакам полного перебора и атакам "дня рождения", чем MD5, формирующий 128-битовые хэш-значения.
• Сжимающая функция SHA состоит из 80 шагов, а не из 64 как в MD5.
• Расширение входных данных производится не простым их повторение в другом порядке, а рекуррентной формулой.
• Усложнен процесс перемешивания

Отечественный стандарт хэш-функции

Российский стандарт ГОСТ Р 34.11-94 определяет алгоритм и процедуру вычисления хэш-функции для любых последовательностей двоичных символов, применяемых в криптографических методах обработки и защиты информации. Этот стандарт базируется на блочном алгоритме шифрования ГОСТ 28147-89, хотя в принципе можно было бы использовать и другои блочный алгоритм шифрования с 64-битовым блоком и 256-битовым ключом.

Данная хэш-функция формирует 256-битовое хэш-значение.

Функция сжатия Н i = f(М i , Н i-1) (оба операнда М i и Н i-1 являются 256-битовыми величинами) определяется следующим образом:

1. Генерируются 4 ключа шифрования К j , j = 1...4 , путем линейного смешивания М i , Н i-1 и некоторых констант С j .
2. Каждый ключ К j используют для шифрования 64-битовых подслов h j слова Н i-1 в режиме простой замены:
   S i = E Kj (h j) . Результирующая последовательность S 4 , S 3 , S 2 , S 1 длиной 256 бит запоминается во временной переменной S .
3. Значение Н i является сложной, хотя и линейной функцией смешивания S, М i , Н i-1 .

При вычислении окончательного хэш-значения сообщения М учитываются значения трех связанных между собой переменных:

Н n - хэш-значение последнего блока сообщения;
Z - значение контрольной суммы, получаемой при сложении по модулю 2 всех блоков сообщения;
L - длина сообщения.

Эти три переменные и дополненный последний блок М " сообщения объединяются в окончательное хэш-значение следующим образом:

Н = f (Z Å М", f (L, f(М", Н n))).

Данная хэш-функция определена стандартом ГОСТ Р 34.11-94 для использования совместно с российским стандартом электронной цифровой подписи.

3. Алгоритмы электронной цифровой подписи

Технология применения системы ЭЦП предполагает наличие сети абонентов, посылающих друг другу подписанные электронные документы. Для каждого абонента генерируется пара ключей: секретный и открытый. Секретный ключ хранится абонентом в тайне и используется им для формирования ЭЦП. Открытый ключ известен всем другим пользователям и предназначен для проверки ЭЦП получателем подписанного электронного документа. Иначе говоря, открытый ключ является необходимым инструментом, позволяющим проверить подлинность электронного документа и автора подписи. Открытый ключ не позволяет вычислить секретный ключ.

Для генерации пары ключей (секретного и открытого) в алгоритмах ЭЦП, как и в асимметричных системах шифрования, используются разные математические схемы, основанные на применении однонаправленных функции. Эти схемы разделяются на две группы. В основе такого разделения лежат известные сложные вычислительные задачи:

• задача факторизации (разложения на множители) больших целых чисел;
• задача дискретного логарифмирования.

Алгоритм цифровой подписи RSА

Первой и наиболее известной во всем мире конкретной системой ЭЦП стала система RSА , математическая схема которой была разработана в 1977 г. в Массачуссетском технологическом институте США.

Сначала необходимо вычислить пару ключей (секретный ключ и открытый ключ). Для этого отправитель (автор) электронных документов вычисляет два больших простых числа Р и Q, затем находит их произведение

N = Р * Q и значение функции j (N) = (Р-1)(Q-1).
Далее отправитель вычисляет число Е из условий: Е £ j (N), НОД (Е, j (N)) = 1
и число D из условий: D < N, Е*D º 1 (mod j (N)).

Пара чисел (Е, N) является открытым ключом. Эту пару чисел автор передает партнерам по переписке для проверки его цифровых подписей. Число D сохраняется автором как секретный ключ для подписывания.

Обобщенная схема формирования и проверки цифровой подписи RSА показана на рис.6.

Рис.6. Обобщённая схема цифровой подписи RSA

Допустим, что отправитель хочет подписать сообщение М перед его отправкой. Сначала сообщение М (блок информации, файл, таблица) сжимают с помощью хэш-функции h(·) в целое число m:

M = h(М).

Затем вычисляют цифровую подпись S под электронным документом М, используя хэш-значение m и секретный ключ D:

S = m D (mod N).

Пара (М,S) передается партнеру-получателю как электронный документ М, подписанный цифровой подписью S , причем подпись S сформирована обладателем секретного ключа D .

После приема пары (М,S) получатель вычисляет хэш-значение сообидения М двумя разными способами. Прежде всего он восстанавливает хэш-значение m" , применяя криптографическое преобразование подписи S с использованием открытого ключа Е:

M" = S E (mod N).

Кроме того, он находит результат хэширования принятого сообщения М с помощью такой же хэш-функции h(·) :

M = h(М).

Если соблюдается равенство вычисленных значений, т.е.

S E (mod N) = h (М),
то получатель признает пару (М,S) подлинной. Доказано, что только обладатель секретного ключа D может сформировать цифровую подпись S по документу М, а определить секретное число D по открытому числу Е не легче, чем разложить модуль N на множители.

Кроме того, можно строго математически доказать, что результат проверки цифровой подписи S будет положительным только в том случае, если при вычислении S был использован секретный ключ D , соответствующий открытому ключу Е. Поэтому открытый ключ Е иногда называют "идентификатором" подписавшего.

Недостатки алгоритма цифровой подписи RSА.

1. При вычислении модуля N , ключей Е и D для системы цифровой подписи RSА необходимо проверять большое количество дополнительных условий, что сделать практически трудно. Невыполнение любого из этих условий делает возможным фальсификацию цифровой подписи со стороны того, кто обнаружит такое невыполнение. При подписании важных документов нельзя допускать такую возможность даже теоретически.
2. Для обеспечения криптостойкости цифровой подписи RSА по отношению к попыткам фальсификации на уровне, например, национального стандарта США на шифрование информации (алгоритм DES), т.е. 10 18 , необходимо использовать при вычислениях N , D и Е целые числа не менее 2 512 (или около 10 154) каждое, что требует больших вычислительных затрат, превышающих на 20...30% вычислительные затраты других алгоритмов цифровой подписи при сохранении того же уровня криптостойкости.
3. Цифровая подпись RSА уязвима к так называемой мультипликативной атаке. Иначе говоря, алгоритм цифровой подписи RSА позволяет злоумышленнику без знания секретного кпюча D сформировать подписи под теми документами, у которых результат хэширования можно вычислить как произведение результатов хэширования уже подписанных документов.

Пример. Допустим, что злоумышленник может сконструировать три сообщения М 1 , М 2 , М 3 , у которых хэш-значения

M 1 = h (М 1), m 2 = h (М 2), m 3 = h (М 3) ,

M 3 = m 1 * m 2 (mod N) .

Допустим также, что для двух сообщений М 1 и М 2 получены законные подписи

S 1 = m 1 D (mod N) S 2 = m 2 D (mod N) .

Тогда злоумышленник может легко вычислить подпись S 3 для документа М 3 , даже не зная секретного ключа D:

S 3 = S 1 * S 2 (mod N).

Действительно,

S 1 * S 2 (mod N) = m 1 D * m 2 D (mod N) = (m 1 m 2) D (mod N) = m 3 D (mod N) = S 3 .

Более надежный и удобный для реализации на персональных компьютерах алгоритм цифровой подписи был разработан в 1984 г. американцем арабского происхождения Тахером Эль Гамалем. В 1991 г. НИСТ США обосновал перед комиссией Конгресса США выбор алгоритма в качестве основы для национального стандарта.

Алгоритм цифровой подписи Эль Гамаля (ЕGSА)

Название ЕGSА происходит от слов Е_ Gаmа_ Signaturе Аlgorithm (алгоритм цифровой подписи Эль Гамаля). Идея ЕGSА основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа,- задача дискретного логарифмирования. Кроме того, Эль Гамалю удалось избежать явной слабости алгоритма цифровой подписи RSА, связанной с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа.

Рассмотрим подробнее алгоритм цифровой подписи Эль-Гамаля . Для того чтобы генерировать пару ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое целое число Р и большое целое число G , причем G < Р. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа Р (~10 308 или ~2 1024) и G (~10 154 или ~2 512), которые не являются секретными.

Отправитель выбирает случайное целое число X, 1 < Х £ (Р-1) , и вычисляет

Y =G X mod Р.

Число Y является открытым ключом, используемым для проверки подписи отправителя. Число Y открыто передается всем потенциальным получателям документов.

Число Х является секретным ключом отправителя для подписывания документов и должно храниться в секрете.

Для того чтобы подписать сообщение М, сначала отправитель хэширует его с помощью хэш-функции h(·) в целое число m:

M = h(М), 1 < m < (Р-1) , и генерирует случайное целое число К, 1 < К < (Р-1) , такое, что К и (Р-1) являются взаимно простыми. Затем отправитель вычисляет целое число а: а = G K mod Р и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число b из уравнения m = Х * а + К * b (mod (Р-1)) .

Пара чисел (а,b) образует цифровую подпись S:

S=(а,b) , проставляемую под документом М.

Тройка чисел (М,а,b) передается получателю, в то время как пара чисел (Х,К) держится в секрете.

После приема подписанного сообщения (М,а,b) получатель должен проверить, соответствует ли подпись S=(а,b) сообщению М. Для этого получатель сначала вычисляет по принятому сообщению М число

M = h(М) , т.е. хэширует принятое сообщение М.

Затем получатель вычисляет значение

А = Y a a b (mod Р) и признает сообщение М подлинным, только если А = G m (mod Р) .

Иначе говоря, получатель проверяет справедливость соотношения

Y a a b (mod Р) = G m (mod Р) .

Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S=(а,b) под документом М получена с помощью именно того секретного ключа X , из которого был получен открытый ключ Y . Таким образом, можно надежно удостовериться, что отправителем сообщения М был обладатель именно данного секретного ключа X , не раскрывая при этом сам ключ, и что отправитель подписал именно этот конкретный документ М.

Следует отметить, что выполнение каждой подписи по методу Эль Гамаля требует нового значения К, причем это значение должно выбираться случайным образом. Если нарушитель раскроет когда-либо значение К, повторно используемое отправителем, то он сможет раскрыть секретный ключ Х отправителя.

Пример. Выберем: числа Р = 11, G = 2 и секретный ключ Х = 8 . Вычисляем значение открытого ключа:

Y = G X mod Р = 2 8 mod 11 = 3 .

Предположим, что исходное сообщение М характеризуется хэш-значением m = 5 .

Для того чтобы вычислить цифровую подпись для сообщения М, имеющего хэш-значение m = 5 , сначала выберем случайное целое число К = 9 . Убедимся, что числа К и (Р-1) являются взаимно простыми. Действительно, НОД (9,10) = 1 . Далее вычисляем элементы а и b подписи:

А = G K mod Р = 2 9 mod 11 = 6 , элемент b определяем, используя расширенный алгоритм Евклида: m = Х * а + К * b (mod(Р-1)).

При m = 5, а = 6, Х = 8, К = 9, Р = 11 получаем

5 = 8 * 6 + 9 * b (mod 10) или 9 * b = -43 (mod 10) .

Решение: b = 3 . Цифровая подпись представляет собой пару: а = 6, b = 3 . Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ Y = 3 , получатель вычисляет хэш-значение для сообщения М: m = 5 , а затем вычисляет два числа:

Y a a b (mod Р) = 3 6 * 6 3 (mod 11) = 10 (mod 11); G m (mod Р) = 2 5 (mod 11) = 10 (mod 11).

Так как эти два целых числа равны, принятое получателем сообщение признается подлинным.

Следует отметить, что схема Эль Гамаля является характерным примером подхода, который допускает пересылку сообщения М в открытой форме вместе с присоединенным аутентификатором (а,b) . В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщению.

Схема цифровой подписи Эль Гамаля имеет ряд преимуществ по сравнению со схемой цифровой подписи RSА:

1. При заданном уровне стойкости алгоритма цифровой подписи целые числа, участвующие в вычислениях, имеют запись на 25% короче, что уменьшает сложность вычислений почти в два раза и позволяет заметно сократить объем используемой памяти.
2. При выборе модуля Р достаточно проверить, что это число является простым и что у числа (Р-1) имеется большой простой множитель (т.е. всего два достаточно просто проверяемых условия).
3. Процедура формирования подписи по схеме Эль Гамаля не позволяет вычислять цифровые подписи под новыми сообщениями без знания секретного ключа (как в RSА).

Однако алгоритм цифровой подписи Эль Гамаля имеет и некоторые недостатки по сравнению со схемой подписи RSА. В частности, длина цифровой подписи получается в 1,5 раза больше, что, в свою очередь, увеличивает время ее вычисления.

Алгоритм цифровой подписи DSА

Алгоритм цифровой подписи DSА (Digital Signature Algorithm ) предложен в 1991 г. в НИСТ США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSА является развитием алгоритмов цифровой подписи Эль Гамаля и К.Шнорра.

Отправитель и получатель электронного документа используют при вычислении большие целые числа: G и Р - простые числа, L бит каждое (512 £ L £ 1024); q - простое число длиной 160 бит (делитель числа (Р-1)). Числа G, Р, q являются открытыми и могут быть общими для всех пользователей сети.

Отправитель выбирает случайное целое число X, 1 < Х < q . Число Х является секретным ключом отправителя для формирования электронной цифровой подписи.

Затем отправитель вычисляет значение

Y = G X mod Р.

Число Y является открытым ключом для проверки подписи отправителя и передается всем получателям документов.

Этот алгоритм также предусматривает использование односторонней функции хэширования h(·) . В стандарте DSS определен алгоритм безопасного хэширования SНА (Secure Hash Algorithm).

Для того чтобы подписать документ М, отправитель хэширует его в целое хэш-значение m:

M = h(М), 1

Пара чисел (r,s) образует цифровую подпись

S = (r,s) под документом М.

Таким образом, подписанное сообщение представляет собой тройку чисел (М,r,s) .

Получатель подписанного сообщения (М,r,s) проверяет выполнение условий

0 < r < q, 0 < s < q и отвергает подпись, если хотя бы одно из этих условий не выполнено. Затем получатель вычисляет значение w = (1/s) mod q , хэш-значение m = h(М) и числа u 1 = (m * w) mod q , u 2 = (r * w) mod q .

V = ((G u 1 * Y u 2) mod Р) mod q и проверяет выполнение условия v = r .

Если условие v = r выполняется, тогда подпись S=(r,s) под документом М признается получателем подлинной.

Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S=(r,s) под документом М получена с помощью именно того секретного ключа X , из которого был получен открытый ключ Y . Таким образом, можно надежно удостовериться, что отправитель сообщения владеет именно данным секретным ключом Х (не раскрывая при этом значения ключа X) и что отправитель подписал именно данный документ М.

По сравнению с алгоритмом цифровой подписи Эль Гамаля алгоритм DSА имеет следующие основные преимущества:

1. При любом допустимом уровне стойкости, т.е. при любой паре чисел G и Р (от 512 до 1024 бит), числа q, X, r, s имеют длину по 160 бит, сокращая длину подписи до 320 бит.
2. Большинство операций с числами К, r, s, Х при вычислении подписи производится по модулю числа q длиной 160 бит, что сокращает время вычисления подписи.
3. При проверке подписи большинство операций с числами u 1 , u 2 , v, w также производится по модулю числа q длиной 160 бит, что сокращает объем памяти и время вычисления.

Недостатком алгоритма DSА является то, что при подписывании и при проверке подписи приходится выполнять сложные операции деления по модулю q:

S = ((m + rX)/K) (mod q), w = (1/s) (mod q) ,

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

Следует отметить, что реальное исполнение алгоритма DSА может быть ускорено с помощью выполнения предварительных вычислений. Заметим, что значение r не зависит от сообщения М и его хэш-значения m . Можно заранее создать строку случайных значений К и затем для каждого из этих значений вычислить значения r . Можно также заранее вычислить обратные значения К -1 для каждого из значений К. Затем, при поступлении сообщения М, можно вычислить значение s для данных значений r и К -1 . Эти предварительные вычисления значительно ускоряют работу алгоритма DSА.

Отечественный стандарт цифровой подписи

Отечественный стандарт цифровой подписи обозначается как ГОСТ Р 34.10-94. Алгоритм цифровой подписи, определяемый этим стандартом, концептуально близок к алгоритму DSА. В нем используются следующие параметры:

Р - большое простое число длиной от 509 до 512 бит либо от 1020 до 1024 бит;
q - простой сомножитель числа (р-1) , имеющий длину 254...256 бит;
а - любое число, меньшее (р-1) , причем такое, что а q mod p = 1 ;
х - некоторое число, меньшее q ;
у = а x mod р.

Кроме того, этот алгоритм использует однонаправленную хэш-функцию Н(х) . Стандарт ГОСТ Р 34.11-94 определяет хэш-функцию, основанную на использовании стандартного симметричного алгоритма ГОСТ 28147-89.

Первые три параметра р, q, а являются открытыми и могут быть общими для всех пользователей сети. Число х является секретным ключом. Число у является открытым ключом. Чтобы подписать некоторое сообщение m , а затем проверить подпись, выполняются следующие шаги.

1. Пользователь А генерирует случайное число k , причем k
2. Пользователь А вычисляет значения r = (а k mod p) mod p , s = (х * r + k (Н(m))) mod p . Если Н(m) mod q = 0 , то значение Н(m) mod q принимают равным единице. Если r=0 , то выбирают другое значение k и начинают снова.
   Цифровая подпись представляет собой два числа: r mod 2 256 и s mod 2 256 . Пользователь А отправляет эти числа пользователю В.
3. Пользователь В проверяет полученную подпись, вычисляя v = Н(m) q-2 mod q , z 1 = (s * v) mod q , z 2 = ((q-r) * v) mod q , u = ((а z 1 * у z 2) mod р) mod p . Если u = r , то подпись считается верной.

Различие между этим алгоритмом и алгоритмом DSА заключается в том, что в DSА

S = (k -1 (х * r + (Н(m)))) mod q ,

что приводит к другому уравнению верификации.

Следует также отметить, что в отечественном стандарте ЭЦП параметр q имеет длину 256 бит. Западных криптографов вполне устраивает q длиной примерно 160 бит. Различие в значениях параметра q является отражением стремления разработчиков отечественного стандарта к получению более безопасной подписи.

Этот стандарт вступил в действие c начала 1995 г.

Литература

1. Романец Ю.В., Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. Под ред. В.Ф. Шаньгина. - 2-е изд., перераб. и доп. - М.: Радио и связь, 2001. - 376 с.: ил.
2. Конеев И.Р., Беляев А.В. Информационная безопасность предприятия. - СПб.: БХВ-Петербург, 2003.

Вопросы:

1. Понятие хеш-функции.

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

3. Обзор алгоритмов формирования хеш-функций.

1. Понятие хеш-функции

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

h = H(M) ,

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

Смысл хеш-функции состоит в определении характерного признака прообраза – значения хеш-функции. Это значение обычно имеет определенный фиксированный размер, например, 64 или 128 бит. Хеш-код может быть в дальнейшем проанализирован для решения какой-либо задачи. Так, например, хеширование может применяться для сравнения данных: если у двух массивов данных хеш-коды разные, массивы гарантированно различаются; если одинаковые - массивы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет из-за того, что количество значений хеш-функций всегда меньше, чем вариантов входных данных. Следовательно, существует множество входных сообщений, дающих одинаковые хеш-коды (такие ситуации называются коллизиями ). Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

Хеш-функции широко применяются в современной криптографии.

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

Например, пусть исходное сообщение, переведенное в цифровой вид, было следующим (в шестнадцатеричном формате):

2 B 1 4 A 9 5 F E 4

Переведем сообщение в двоичный вид, запишем байты друг под другом и сложим биты в каждом столбике по модулю 2:

0010 1011

0001 0100

1010 1001

0101 1111

1110 0100

——————-

0010 1101

Результат: 0010 1101 или 2 D и будет значением хеш-функции.

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

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

Сформулируем основные требования, предъявляемые к криптографическим хеш-функциям:

· хеш-функция должна быть применима к сообщению любого размера;

· вычисление значения функции должно выполняться достаточно быстро;

· при известном значении хеш-функции должно быть трудно (практически невозможно) найти подходящий прообраз М ;

· при известном сообщении М должно быть трудно найти другое сообщение М’ с таким же значением хеш-функции, как у исходного сообщения;

· должно быть трудно найти какую-либо пару случайных различных сообщений с одинаковым значением хеш-функции.

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

В настоящее время на практике в качестве хеш-функций применяются функции, обрабатывающие входное сообщение блок за блоком и вычисляющие хеш- значение h i для каждого блока M i входного сообщения по зависимостям вида

h i = H(M i ,h i-1),

где h i-1 – результат, полученный при вычислении хеш-функции для предыдущего блока входных данных.

В результате выход хеш-функции h n является функцией от всех n блоков входного сообщения.

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

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

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

· практически невозможно без знания ключа шифрования вычисление хеш-значения для заданного открытого массива информации;

· практически невозможен без знания ключа шифрования подбор открытых данных под заданное значение хеш-функции.

Сформированное таким образом хеш- значение обычно называют имитовставкой или аутентификатором и используется для проверки целостности сообщения. Таким образом, имитовставка – это контрольная комбинация, зависящая от открытых данных и секретной ключевой информации. Целью использования имитовставки является обнаружение всех случайных или преднамеренных изменений в массиве информации. Значение, полученное хеш-функцией при обработке входного сообщения, присоединяется к сообщению в тот момент, когда известно, что сообщение корректно. Получатель проверяет целостность сообщения путем вычисления имитовставки полученного сообщения и сравнения его с полученным хеш-кодом, который должен быть передан безопасным способом. Одним из таких безопасных способов может быть шифрование имитовставки закрытым ключом отправителя, т.е. создание подписи. Возможно также шифрование полученного хеш-кода алгоритмом симметричного шифрования, если отправитель и получатель имеют общий ключ симметричного шифрования.

Указанный процесс получения и использования имитовставки описан в отечественном стандарте ГОСТ 28147-89. Стандарт предлагает использовать младшие 32 бита блока, полученного на выходе операции шифрования всего сообщения в режиме сцепления блоков шифра для контроля целостности передаваемого сообщения. Таким же образом для формирования имитовставки можно использовать любой блочный алгоритм симметричного шифрования.

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

Таким образом, если обычную схему шифрования сообщения М с помощью блочного шифра f на ключе К мы записывали как E= f(M,K) , то схему получения хеш-кода h по описанному выше алгоритму можно представить как

h i = f ( h i -1 , M )

В качестве начального хеш-кода h 0 берут некоторую константу. Шифрование производится в режиме простой замены. При использовании указанного способа размер блока совпадает с длиной ключа и размером хеш-значения будет длина блока.

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

h i = f ( M , h i -1 ,)

На самом деле возможны еще несколько схем использования блочного шифра для формирования хеш-функции. Пусть М i – блок исходного сообщения, h i – значение хеш-функции на i -том этапе, f – блочный алгоритм шифрования, используемый в режиме простой замены, – операция сложения по модулю 2. Тогда возможны, например, следующие схемы формирования хеш-функции:

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

Основным недостатком хеш-функций, спроектированных на основе блочных алгоритмов, является относительно низкая скорость работы. Необходимую криптостойкость можно обеспечить и за меньшее количество операций над входными данными. Существуют более быстрые алгоритмы хеширования (наиболее распространенные из них – MD5, SHA-1, SHA-2 и ГОСТ Р 34.11-94).

3. Обзор алгоритмов формирования хеш-функций.

В настоящее время предложены и практически используются различные специальные алгоритмы для вычисления хеш-функции. Наиболее известными алгоритмами являются MD5, SHA-1, SHA-2 и другие версии SHA, а также отечественный алгоритм, изложенный в ГОСТ Р 34.11-94.

Алгоритм MD5 появился в начале 90-х годов ХХ века в результате усовершенствования алгоритма формирования хеш-функции MD4. Символы в названии " MD" означают Message Digest – краткое изложение сообщения. Автор алгоритмов MD4 и MD5 – Р. Ривест (R.Rivest). В результате использования MD5 для произвольного сообщения формируется 128-битное хеш- значение. Входные данные обрабатываются блоками по 512 бит. В алгоритме используются элементарные логические операции ( инверсия, конъюнкция, сложение по модулю 2, циклические сдвиги и др.), а также обыкновенное арифметическое сложение. Комплексное повторение этих элементарных функций алгоритма обеспечивает то, что результат после обработки хорошо перемешан. Поэтому маловероятно, чтобы два сообщения, выбранные случайно, имели одинаковый хеш-код. Алгоритм MD5 имеет следующее свойство: каждый бит полученного хеш-значения является функцией от каждого бита входа. Считается, что MD5 является наиболее сильной хеш-функцией для 128-битного хеш-значения.

Алгоритм SHA ( Secure Hash Algorithm – Безопасный хеш- алгоритм) был разработан национальным институтом стандартов и технологии ( NIST) США и опубликован в качестве американского федерального информационного стандарта в 1993 году. SHA-1, как и MD5, основан на алгоритме MD4. SHA-1 формирует 160-битное хеш- значение на основе обработки исходного сообщения блоками по 512 бит. В алгоритме SHA-1 также используются простые логические и арифметические операции. Наиболее важным отличием SHA-1 от MD5 является то, что хеш-код SHA-1 на 32 бита длиннее, чем хеш-код MD5. Если предположить, что оба алгоритма одинаковы по сложности для криптоанализа, то SHA-1 является более стойким алгоритмом. Используя атаку методом грубой силы (лобовую атаку), труднее создать произвольное сообщение, имеющее данный хеш-код, а также труднее создать два сообщения, имеющие одинаковый хеш-код.

В 2001 году национальный институт стандартов и технологии США принял в качестве стандарта три хеш-функции с большей длиной хеш-кода, чем у SHA-1. Часто эти хеш-функции называют SHA-2 или SHA-256, SHA-384 и SHA-512 (в названии указывается длина создаваемого алгоритмами хеш-кода). Эти алгоритмы отличаются не только длиной создаваемого хеш-кода, но и используемыми внутренними функциями и длиной обрабатываемого блока (у SHA-256 длина блока – 512, а у SHA-384 и SHA-512 длина блока – 1024 бита). Постепенные усовершенствования алгоритма SHA ведут к увеличению его криптостойкости. Несмотря на отличия рассматриваемых алгоритмов друг от друга, все они являются дальнейшим развитием SHA-1 и MD4 и имеют похожую структуру.

В России принят ГОСТ Р34.11-94, который является отечественным стандартом для хеш-функций. Его структура довольно сильно отличается от структуры алгоритмов SHA-1,2 или MD5, в основе которых лежит алгоритм MD4. Длина хеш-кода, создаваемого алгоритмом ГОСТ Р 34.11-94, равна 256 битам. Алгоритм последовательно обрабатывает исходное сообщение блоками по 256 бит справа налево. Параметром алгоритма является стартовый вектор хеширования – произвольное фиксированное значение длиной также 256 бит. В алгоритме ГОСТ Р 34.11-94 используются операции перестановки, сдвига, арифметического сложения, сложения по модулю 2. В качестве вспомогательной функции в ГОСТ 34.11-94 используется алгоритм по ГОСТ 28147-89 в режиме простой замены.

4. Требования к хэш-функциям

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

Хэш-код создается функцией Н :

h = H (M)

Где М является сообщением произвольной длины и h является хэш-кодом фиксированной длины.

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

Хэш-функция Н , которая используется для аутентификации сообщений, должна обладать следующими свойствами:

1. Хэш-функция Н должна применяться к блоку данных любой длины.

2. Хэш-функция Н создает выход фиксированной длины.

3. Н (М) относительно легко (за полиномиальное время) вычисляется для любого значения М .

4. Для любого данного значения хэш-кода h вычислительно невозможно найти M такое, что Н (M) = h .

5. Для любого данного х вычислительно невозможно найти , что

H (y) = H (x).

6. Вычислительно невозможно найти произвольную пару (х , y ) такую, что H (y) = H (x) .

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

Четвертое свойство определяет требование односторонности хэш-функции: легко создать хэш-код по данному сообщению, но невозможно восстановить сообщение по данному хэш-коду. Это свойство важно, если аутентификация с использованием хэш-функции включает секретное значение. Само секретное значение может не посылаться, тем не менее, если хэш-функция не является односторонней, противник может легко раскрыть секретное значение следующим образом. При перехвате передачи атакующий получает сообщение М и хэш-код С = Н (SAB || M) . Если атакующий может инвертировать хэш-функцию, то, следовательно, он может получить SAB || M = H-1 (C) . Так как атакующий теперь знает и М и SAB || M , получить SAB совсем просто.

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

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

5. Простые хэш-функции

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

Одним из простейших примеров хэш-функции является побитовый XOR каждого блока:

На каждом из четырех циклов алгоритма используется одна из четырех элементарных логических функций. Каждая элементарная функция получает три 32-битных слова на входе и на выходе создает одно 32-битное слово. Каждая функция является множеством побитовых логических операций, т.е. n-ый бит выхода является функцией от n-ого бита трех входов. Элементарные функции следующие:

Массив из 32-битных слов X содержит значение текущего 512-битного входного блока, который обрабатывается в настоящий момент. Каждый цикл выполняется 16 раз, а так как каждый блок входного сообщения обрабатывается в четырех циклах, то каждый блок входного сообщения обрабатывается по схеме, показанной на Рис. 4 , 64 раза. Если представить входной 512-битный блок в виде шестнадцати 32-битных слов, то каждое входное 32-битное слово используется четыре раза, по одному разу в каждом цикле, и каждый элемент таблицы Т, состоящей из 64 32-битных слов, используется только один раз. После каждого шага цикла происходит циклический сдвиг влево четырех слов A, B, C и D. На каждом шаге изменяется только одно из четырех слов буфера ABCD. Следовательно, каждое слово буфера изменяется 16 раз, и затем 17-ый раз в конце для получения окончательного выхода данного блока.

2. Скорость: программная реализация алгоритма должна выполняться достаточно быстро. В частности, алгоритм должен быть достаточно быстрым на 32-битной архитектуре. Поэтому алгоритм основан на простом множестве элементарных операций над 32-битными словами.

3. Простота и компактность: алгоритм должен быть простым в описании и простым в программировании, без больших программ или подстановочных таблиц. Эти характеристики не только имеют очевидные программные преимущества, но и желательны с точки зрения безопасности, потому что для анализа возможных слабых мест лучше иметь простой алгоритм.

4. Желательна little- endian архитектура: некоторые архитектуры процессоров (такие как линия Intel 80xxx) хранят левые байты слова в позиции младших адресов байта (little- endian). Другие (такие как SUN Sparcstation) хранят правые байты слова в позиции младших адресов байта (big MD4 дополнительная константа в первом цикле не применяется. Аналогичная дополнительная константа используется для каждого из шагов во втором цикле. Другая дополнительная константа используется для каждого из шагов в третьем цикле. В хэш-кода является функцией от каждого бита входа. Комплексное повторение элементарных функций f F , f G , f H и f I обеспечивает то, что результат хорошо перемешан; то есть маловероятно, чтобы два сообщения, выбранные случайно, даже если они имеют явно похожие закономерности, имели одинаковый дайджеста, которые создают одно и то же выходное значение. Это означает, что выполнение MD5 над единственным блоком из 512 бит приведет к одинаковому выходу для двух различных входных значений в буфере ABCD. Пока способа расширения данного подхода для успешной атаки на MD5 не существует.