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

Профиль сообщения также может применяться для гарантии сохранности сообщения при передаче его по сети в системах шифрования с открытым ключом, как показано на рис. 8.17. Здесь Алиса сначала вычисляет профиль сообщения для своего открытого текста. Затем она подписывает профиль сообщения и посылает зашифрованный профиль сообщения и открытый текст Бобу. Если злоумышленник попытается подменить по дороге открытый текст P, Боб обнаружит это, сосчитав значение профиля сообщения MD(P).

Рис. 8.17. Цифровая подпись с использованием профиля сообщения

SHA-1

Было предложено несколько вариантов функций, вычисляющих профиль сообщения. Самое широкое распространение получила функция SHA-1 (Secure Hash Algorithm 1 — надежный алгоритм хэширования) (NIST, 1993). Как и все профили сообщения, он перемешивает входные биты достаточно сложным образом, так что каждый выходной бит зависит от каждого входного бита. SHA-1 был разработан Агентством национальной безопасности США и получил благословение NIST (выразившееся в федеральном стандарте FIPS 180-1). Алгоритм SHA-1 обрабатывает входные данные блоками по 512 бит и формирует профиль сообщения длиной 160 бит. Типичный случай отправки Алисой несекретного, но подписанного сообщения Бобу показан на рис. 8.18. Открытый текст обрабатывается алгоритмом SHA-1, на выходе получается 160-битный хэш SHA-1. Он подписывается Алисой (закрытым ключом RSA) и отправляется вместе с открытым текстом Бобу.

Рис. 8.18. Применение SHA-1 и RSA для создания подписей несекретных сообщений

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

Давайте теперь вкратце рассмотрим, как работает SHA-1. Для начала алгоритм SHA-1 также дополняет сообщение единичным битом в конце, за которым следует такое количество нулевых бит (равное как минимум 64), чтобы в итоге получилось общее число бит, кратное 512. Затем 64-разрядное число, содержащее длину сообщения (до битового дополнения), логически складывается (операция ИЛИ) с 64 младшими битами. На рис. 8.19, а показано сообщение с дополнением, расположенным справа, потому что английский текст и рисунки читаются слева направо (то есть правая граница рисунка воспринимается как его конец, а левая — как начало). Применительно к вычислительной технике такое расположение соответствует обратному порядку хранения байтов (сначала передается самый значимый, старший бит). Такая реализация присуща, например, SPARC или IBM 360 и его последователям. Однако, вне зависимости от используемой техники, SHA-1 вставляет битовое дополнение в конец сообщения.

Во время выполнения вычислений SHA-1 работает с пятью 32-битными переменными (H₀ ... H₄), в которых накапливается значение хэш-функции. Они показаны на рис. 8.19, б. Их начальные значения — это постоянные величины, определенные стандартом.

Рис. 8.19. Сообщение, дополненное до размера, кратного 512 битам (а); выходные переменные (б); массив слов (в)

После 80 итераций цикла значения переменных A ... E добавляются к H₀ ... H₄ соответственно.

После обработки первого 512-битного блока начинается обработка следующего. Массив W инициализируется заново с помощью нового блока, однако H сохраняется неизменным. По окончании этого блока обрабатывается следующий, и т. д., пока все 512-разрядные блоки сообщения не попадут в эту кастрюлю. После обработки последнего блока пять 32-разрядных слов в массиве H выводятся в качестве 160-битного значения криптографической хэш-функции. Полный код SHA-1 приведен в RFC 3174.

В настоящее время идет работа над новыми версиями SHA-1 с 224, 256-, 384-и 512-разрядными значениями хэш-функций. Эти версии вместе называются SHA-2. Не только их хэши длиннее, чем хэши SHA-1, профиль был изменен еще и для того, чтобы избавиться от некоторых потенциально слабых сторон SHA-1. SHA-2 пока еще широко не используется, но это вероятно случится в будущем.

MD5

Для полноты картины мы отметим еще один популярный профиль. Алгоритм MD5 (Message Digest 5 — профиль сообщения 5) представляет собой пятую версию хэш-функций, разработанных Рональдом Ривестом (Ronald Rivest). Сначала сообщение дополняется до длины 448 бит по модулю 512. Затем к нему добавляется исходная длина сообщения, рассматриваемая как 64-разрядное число, в результате чего получается блок битов длиной кратной 512. Последний шаг подготовки к вычислениям инициализирует 128-разрядный буфер, задавая его содержимое равным некоему фиксированному значению.

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

После более десяти лет использования и изучения MD5 были обнаружены совпадения, то есть разные сообщения с одинаковым хэшем (Sotirov et al., 2008). Это страшное предзнаменование для функции профилей, так как оно означает, что функция не может безопасно использоваться для представления сообщения. Таким образом, сообщество по безопасности считает MD5 сломанным; его нужно заменить там, где это возможно, и новые системы не должны использовать его как часть своей конструкции. Несмотря на это, на момент написания книги этот алгоритм еще держится на плаву.

8.4.4. Задача о днях рождения

В мире шифров многое оказывается совсем не таким, каким кажется на первый взгляд. Можно, например, предполагать, что для ниспровержения профиля сообщения, состоящего из m разрядов, потребуется порядка 2^m операций. На самом деле, часто оказывается достаточно 2^m/2 операций, если использовать метод, основанный на задаче о днях рождения (birthday attack), опубликованный в ставшей классической книге (Yuval, 1979).

В основе идеи этого метода лежит задача, часто приводимая в качестве примера профессорами математики на курсах по теории вероятности. Вопрос: сколько студентов должно находиться в классе, чтобы вероятность появления двух человек с совпадающими днями рождения превысила 1/2? Большинство студентов обычно ожидают, что ответ будет значительно больше 100. На самом же деле, теория вероятности утверждает, что это число равно 23. Не вдаваясь в тонкости анализа этой проблемы, дадим интуитивно понятное объяснение: из 23 человек мы можем сформировать (23 х 22)/2 = 253 различных пары, у каждой из которой дни рождения могут совпасть с вероятностью 1/365. Теперь этот ответ уже не кажется таким удивительным.