В этой главе мы рассмотрим вычислительно стойкие шифры с секретным ключом, которые, в принципе, могут быть вскрыты, но требуют для этого очень большого количества вычислений, скажем, 1020 лет для суперкомпьютера. Эти шифры обеспечивают шифрование и дешифрование данных со скоростями, значительно превышающими скорости шифров с открытыми ключами и стойких шифров, что и объясняет их широкое практическое использование. В последующих разделах мы опишем некоторые наиболее популярные шифры и режимы их функционирования, однако вначале, чтобы пояснить принципы построения этих шифров, продолжим пример с шифром Цезаря, начатый в первой главе.
Там мы рассмотрели атаку по шифротексту на шифр Цезаря. Было показано, что в случае избыточных сообщений шифр легко вскрывается путем перебора ключей. Поищем возможности повышeния стойкости шифра Цезаря. Пожалуй, самое простое, что приходит в голову — увеличить количество возможных значений ключа. В этом случае Еве придется перебирать больше ключей, прежде чем она найдет единственный правильный.
Естественный способ увеличить количество возможных значений ключа для шифра Цезаря — использовать разные ключи для разных букв сообщения. Например, мы можем шифровать каждую нечетную букву ключом k1, а четную ключом k2. Тогда секретный ключ k = (k1, k2) будет состоять из двух чисел, и количество возможных ключей будет 322 = 1024. Зашифруем наше прежнее сообщение из первой главы ключом k = (3,5):
(4.1)
Эта схема легко обобщается на произвольную длину секретного ключа k = (k1, k2, . . . , kt)32. При t порядка 10 и выше задача полного перебора ключей становится практически нерешаемой.
Тем не менее, данный шифр легко вскрывается путем так называемого частотного криптоанализа. Для этого используется статистика языка, на котором написано передаваемое сообщение. При использовании частотного криптоанализа перебор начинают с ключей, соответствующих наиболее часто встречающимся буквам и их сочетаниям. Например, известно, что в типичном тексте на русском языке буква О встречается чаще других. Смотрим на ТКУКПКРЕ в (4.1) и определяем, какие буквы встречаются чаще других на четных и нечетных местах. На четных местах это К. Предполагаем, что это код О, следовательно, k2 = К — О = 28 (mod 32). На нечетных местах все буквы различны, поэтому для поиска k1 знание частот букв языка не помогает (дело в том, что для нашего примера взято очень короткое сообщение). Пытаемся, как и прежде, найти k1 путем перебора, но убеждаемся, что приемлемых расшифровок не получается. Это означает, что наша гипотеза о том, что О заменяется в шифре на К, неверна. Берем вместо О другую часто встречающуюся букву — букву Е. Вычисляем k2 = К — Е = 5. Повторяем аналогичные действия для поиска k1 и на этот раз находим решение k1 = 3. В результате, чтобы расшифровать сообщение, из всех возможных 1024 ключей нам понадобилось проверить только 36 (мы проверяли (0,28),...,(31,28),(0,5),...,(3,5)).
Попробуем слегка усложнить шифр, чтобы затруднить частотный криптоанализ. Нам нужно каким-то образом перемешать символы сообщения, заставить их влиять друг на друга, чтобы скрыть ивдивидуальные частоты их появления. По-прежнему будем использовать ключ k = (k1, k2) и шифровать сообщение блоками по два символа mi, mi+1. Один из простейших вариантов шифра может выглядеть так:
(4.2)
(все суммы вычисляются по модулю 32). Здесь mi — нечетная буква исходного текста, mi+1 — четная буква, k1, k2 — символы ключа, а Ci, ci+1 — получаемые символы шифротекста. Например, пара символов ПЕ шифруется ключом k = (3, 5) следующим образом:
т.е. ПЕ превращается в ЧЮ.
Отметим, что этот шифр можно дешифровать. Алгоритм дешифрования, называемый обычно обратаым шифром, выглядит следующим образом:
(4.3)
Применяя к нашему сообщению шифр (4.2) с ключом (3, 5), получаем
(4.4)
Здесь для наглядности после первой стрелки показан промежуточный результат, получающийся после выполнения первых двух операций в (4.2) (это «перемешанный», но еще не зашифрованный текст сообщения). Мы видим, что данный шифр скрывает частоты появления отдельных символов, затрудняя частотный анализ. Конечно, он сохраняет частоты появления пар символов, но мы можем скрыть и их, если будем шифровать сообщения блоками по три символа и т.д.
Вообще, шифр (4.2) выглядит более сложным для Евы по сравнению с шифром (4.1), и он дает нам возможность рассмотреть еще одну ситуацию, связанную с ее действиями. До сих пор мы рассматривали атаки только по шифротексту. что произойдет, если Ева каким-то образом достала открытый текст, соответствующий ранее переданному зашифрованному сообщению? (Т.е. мы находимся в условиях атаки второго типа, см. главу 1, стр. 10.) Например, Ева имеет пару (ПЕРЕМЕНА, ТКУКПКРЕ) для шифра (4.1). Тогда она сразу вычисляет секретный ключ, k1 = Т — П = 3, k2 = К — Е = 5 ,и легко расшифровывает все последующие сообщения от Алисы к Бобу. При использовании шифра (4.2) пара (ПЕРЕМЕНА, ЧЮШЯФЫРТ) уже не дает такого очевидного решения, хотя и здесь оно довольно просто. Ева применяет две первые операции из (4.2) не требующие секретного ключа) к слову ПЕРЕМЕНА, получает промежуточный результат ФЩХЪСЦНН и уже по паре (ФЩХЪСЦНН, ЧЮШЯФЫРТ), как и в первом случае, находит ключ k = 3,5.
Как затруднить такие действия Евы? Идея проста. Будем при шифровании сообщения использовать шифр (4.2) два раза. Тогда получим:
(4.5)
Теперь, имея пару (ПЕРЕМЕНА, ШШЪЫТПЕЩ), Ева не может вычислить ключ, по крайней мере алгоритм ее действий не очевиден (она не может получить промежуточное значение ЧЮШЯФЫРТ, так как при его построении был использован секретный ключ, ей не известный).
В представленной схеме (4.5) отдельная реализация алгоритма (4.2) называется раундом или циклом шифра.
Мы проиллюстрировали влияние на стойкость шифра таких параметров, как длина ключа, размер блока, количество раундов, а также показали необходимость введения «перемешивающих» преобразований. В реальных шифрах используются, в принципе, те же преобразования, но над более длинными цепочками символов и обладающие целым рядом дополнительных свойств. Это связано с наличием развитых методов криптоанализа, таких, как дифференциальный и линейный криптоанализ, описание которых выходит за рамки нашей книги, но может быть найдено в [27].
Блоковый шифр можно определить как зависящее от ключа K обратимое преобразование слова X из n двоичных символов. Преобразованное с помощью шифра слово (или блок) будем обозначать через Y. Для всех рассматриваемых в этом разделе шифров длина слова Y равна длине слова X.
Таким образом, блоковый шифр — это обратимая функция E (другим словами, такая, для которой существует обратная функция). Конкретный вид EK этой функции определяется ключом K,
Здесь обозначает дешифрующее преобразование и называется обратным шифром.
Для криптографических приложений блоковый шифр должен удовлетворять ряду требований, зависящих от ситуации, в которой он используется. В большинстве случаев достаточно потребовать, чтобы шифр был стоек по отношению к атаке по выбранному тексту. Это автоматически подразумевает его стойкость по отношению к атакам по шифротексту и по известному тексту. Следует заметить, что при атаке по выбранному тексту шифр всегда может быть взломан путем перебора ключей. Поэтому требование стойкости шифра можно уточнить следующим образом.
Шифр стоек (при атаке по выбранному тексту), если для него не существуют алгоритмы взлома, существенно более быстрые, чем прямой перебор ключей.
Нам будет достаточно такого нестрогого определения стойкости. На самом деле, по состоянию на сегодняшний день, ни для одного используемого шифра не доказано соответствие этому определению стойкости. Реально можно говорить о следующем.
Шифр считается стойким (при атаке по выбранному тексту), если для него неизвестны алгоритмы взлома, существенно более эффективные, чем прямой перебор ключей.
Ниже мы приведем примеры некоторых практичеки используемых блоковых шифров. Наша задача будет состоять не только в том, чтобы дать достаточно подробное описание алгоритмов (их описание может быть найдено в литературе), но и в объяснении основных принципов построения блоковых шифров. Кроме того, наше описание может облегчить понимание материала, изложенного в официальных документах (ГОСТах и.т.п.). Далее, на протяжении всей главы, мы будем изучать технику использования блоковых шифров для решения различных задач криптографии.
До недавнего времени ни одна книга по криптографии не обходилась без описания шифра DES (Data Encryption Standard). Этот шифр был принят в качестве стандарта США в 1977 году. Его основные параметры: размер блока 64 бита, длина ключа 56 бит, 16 раундов. Этот шифр интенсивно использовался более двух десятков лет и еще сегодня встречается во многих работающих системах. Несмотря на многочисленные атаки против DES, он так и не был взломан. Однако высокий уровень развития вычислительных средств позволяет сегодня вскрывать DES путем перебора ключей. Напримeр, еще в 1993 году было опубликовано техническое описание системы стоимостью в один миллион долларов, позволяющей взламывать любой ключ DES за 7 часов. В результате DES нe рекомендуется использовать во вновь создаваемых криптографических системах, и поэтому мы нe описываем этот шифр. В 2001 году после специально объявленного конкурса в США был принят новый стандарт на блоковый шифр, названный AES (Advanced Encryption Standard), в основу которого был положeн шифр Rijndael, разработанный бельгийскими специалистами.
Большинство современных блоковых шифров строятся по схемам, значитeльно отличающимся от DES. Тем нe мeнee есть один действующий шифр, построенный на тех же принципах, что и DES, и представляющий для нас особый интерес. Это российский блоковый шифр ГОСТ 28147-89.
Шифр ГОСТ 28147-89
Шифр ГОСТ 28147-89 [5], как следует из его обозначeния, был принят в качестве стандарта в 1989 году. Основные параметры ГОСТ 28147-89: длина ключа 256 бит, размер блока 64 бита, 32 раунда. ГОСТ 28147-89 более удобeн для программной реализации, чем DES, имеются сведения о выигрыше по времени примерно в 1.5 раза. В отличие от DES, ГОСТ 28147-89, по-видимому, нe был предметом столь глубокого анализа со стороны мирового криптологического сообщества. Тем нe мeнee, как отмечают специалисты, консервативный дизайн и величина основных параметров (длина ключа, размер блока, количество раундов) позволяют утверждать, что шифр вряд ли может быть слабым. Никаких эффективных атак против шифра ГОСТ 28147-89 нe опубликовано.
В основе ГОСТ 28147-89, так же как и DES, лежит так называeмая структура Фейстела. Блок разбивается на две однаковые части, правую R и левую L. Правая часть объединяется с ключевым элементом и посредством некоторого алгоритма шифрует левую часть. Перед следующим раундом левая и правая части меняются местами. Такая структура позволяет использовать один и тот же алгоритм как для шифрования, так и для дешифрования блока. Это особенно важно при аппаратной реализации, так как прямой и обратный шифры формируются одним и тем же устройством (различается только порядок подачи элементов ключа).
Перейдем к непосредственному описанию шифра ГОСТ 28147-89. Введем необходимые определения и обозначения. Последовательность из 32 бит будем называть словом. Блок текста X (64 бита), также как блок шифротекста Y, состоит из двух слов — левого L и правого R, причем L — старшее слово, а R — младшее. Секретный ключ К (256 бит) рассматривается состоящим из восьми слов К = К0К1 . . . К7. На его основе строится так называемый раундовый ключ W = W0W1 . . . W31, состоящий из 32 слов (метод построения раундового ключа будет дан позже).
Для работы шифра нужны 8 таблиц S0, S1, ..., S7 Называемых также S-боксами). Каждая таблица содержит 16 четырехбитовых элементов, нумеруемых с 0 по 15. Будем обозначать через Si[j] j -й элемент i -й таблицы. ГОСТ рекомендует заполнять каждую таблицу различными числами из множества {0,1,..., 15}, переставленными случайным образом. Содержимое таблиц формирует дополнительный секретный параметр шифра, общий для большой группы пользователей. Заметим, что в DES аналогичные S-боксы фиксированы и несекретны.
В шифре используются следующие операции:
+ сложение слов по модулю 232;
циклический сдвиг слова влево на указанное число бит;
побитовое «исключающее или» двух слов, т.е. побитовое сложение по модулю 2.
Алгоритм 4.1. БАЗОВЫЙ ЦИКЛ ШИФРА ГОСТ 28147-89
ВХОД: Блок L, R, раундовый ключ W.
ВЫХОД: Преобразованный блок L, R.
(На шаге 4 алгоритма используются отдельные четырехбитовые элементы переменной k.)
С помощью базового цикла осуществляется шифрование и дешифрование блока. Чтобы зашифровать блок, строим раундовый ключ
(4.6)
подаем на вход X и на выходе получаем Y.
Чтобы дешифровать блок, строим раундовый ключ
(4.7)
подаем на вход Y и на выходе получаем X.
Программная реализация обычно требует переработки цикла 3 алгоритма 4.1, так как работа с полубайтами неэффективна. Ясно, что то же самое преобразование может быть выполнено с использованием четырех таблиц по 256 байт или двух таблиц по 65536 полуслов. Например, при работе с байтами имеем k = (k3 . . .k0 )256, и шаги 3—4 алгоритма 4.1 переписываются следующим образом:
Таблицы Tj, j = 0,1, 2, 3, вычисляются предварительно из S- боксов:
ГОСТ ничего не говорит о правилах формирования ключевой информации, кроме требования, чтобы каждый S-бокс содержал перестановку различных чисел. В то же время ясно, что, например, левой ключ или тривиально заданные S-боксы (отображающие k в себя) не обеспечивают секретности шифра.
Блоковые шифры применяются для решения многих задач криптографии. В этом разделе мы рассмотрим основные режимы их использования.
В предыдущем разделе были даны примеры реальных блоковых шифров. Теперь мы можем думать о (идеализированном) блоковом шифре, как о преобразовании входного блока X в выходной блок Y с участием секретного ключа K,
причем это преобразование должно иметь следующие свойства:
1) при известном Y, но неизвестном K практически невозможно узнать X;
2) при произвольных известных X и Y, но неизвестном K практически невозможно узнать K.
Вначале рассмотрим классическую задачу шифрования сообщений при помощи блоковых шифров.
Режим ECB
Название режима ECB (Electronic CodeBook) можно перевести как электронная кодовая книга.
Сообщение X разбивается на блоки X = X1,X2,... ,Xt. Каждый блок шифруется блоковым шифром
Получаем зашифрованное сообщение Y = Y1, Y2,..., Yt. Дешифрование выполняется по правилу
Нетрудно видеть, что дешифрование сообщения можно производить, выбирая блоки шифротекста в произвольном порядке. Такой режим удобен во многих реальных ситуациях. Например, можно работать с базой данных, хранящейся в зашифрованном виде. Однако при таком использовании одинаковые записи будут зашифрованы одинаково. Говорят, что в режиме ECB шифр сохраняет «образ данных», т.е. некий «рисунок» или шаблон, характерный для данных. Это может дать некоторую информацию противнику. Например, если количество различных записей в базе данных невелико (что нередко случается), то противник может составить словарь шифротекстов и вскрыть базу на основе частотного анализа. Заметим, что ему в этом случае не понадобится вскрывать сам шифр.
Некоторые авторы рекомендуют использовать режим ECB только в случаях, когда размер отдельного элемента данных в сообщении, к которому требуется осуществлять непосредственный (прямой) доступ, меньше размера блока. Остаток блока, свободный от данных, рекомендуется заполнять случайно выбираемыми битами. Тогда даже одинаковые элементы данных будут иметь разные шифротексты. При дешифровании биты заполнения просто отбрасываются.
Если размер элемента данных превышает размер блока, то часто рекомендуют использовать режим CBC.
Режим CBC
Название режима CBC (Cipher-Block Chaining) переводится как сцепление блоков шифра.
Зашифрованное сообщение получается по следующему правилу:
т.е. каждый последующий блок открытого текста предварительно закрывается предыдущим зашифрованным блоком. Слово Y0 должно быть определено заранее и известно при шифровании и дешифровании. Полученное зашифрованное сообщение можно дешифровать следующим образом:
Мы получаем шифротекст, в котором каждый следующий блок зависит от предыдущих. Данный режим разрушает «образ данных». Даже если все блоки X идентичны, шифротекст будет состоять из различных блоков Y. Этот режим предпочтителен при шифровании сообщений, размер которых превышает размер блока. Однако дешифровать сообщение можно только последовательно, начиная с первого блока.
В главе 3 мы рассмотрели шифр Вернама и установили, что он является совершенно секретным, т.е. при его использовании противник, перехвативший зашифрованное сообщение, не получает никакой информации об исходном сообщении. В шифре Вернама зашифрованное сообщение y
(4.8)
Мы видели, что данный шифр совершенен только в том случае, если ключ z1, z2,..., Zk образован из независимых и равновероятных символов и используется только один раз. Это приводит к необходимости генерировать случайные последовательности очень большого объема и передавать их по закрытым каналам связи, что весьма затруднительно. Поэтому давно была высказана идея использовать в качестве ключа последовательности не случайные, а порожденные при помощи генераторов псевдослучайных чисел. В этом случае в качестве секретного ключа используется начальное значение или состояние генератора. Однако надо четко осознавать, что в этом случае система уже не будет совершенно секретной. Максимум на что мы можем надеяться, это то, что для раскрытия этой системы потребуется очень много времени например, нужно будет выполнить перебор всех возможных начальных состояний генератора). В качестве возмещения за потерю совершенности мы получаем возможность использовать короткие (обычно несколько сотен бит) секретные ключи, которые значительно проще распределять и хранить (а при использовании систем с открытым ключом их можно и вычислять).
Определение 4.1. Шифр, построенный на основе (4.8), где в качестве z1, z2,..., zk используется псевдослучайная последовательность, называется потоковым шифром (stream cipher).
Как правило, исходное сообщение и ключевая последовательность представляют собой нeзависимыe потоки бит. Так как шифрующее (и дешифрующее) преобразование для всех потоковых шифров одно и то же, они различаются только способом построeния гeнeраторов псевдослучайных чисел. Действительно, чтобы из шифротекста y1, y2,..., yk, полученного по формуле (4.8), восстановить сообщение x1, x2,..., xk, нeобходимо сгeнeрировать точно такую же последовательность z1, z2,..., zk, что и при шифровании, и использовать для дешифрования формулу
(4.9)
П р и м е р 4.1. Один из самых простых гeнeраторов псевдослучайных чисел (линейный конгруэнтный гeнeратор) работает по схеме
(4.10)
где a, b, c — нeкоторыe константы, а zi+1 — очередное псевдослучайное число, вычисляемое по предыдущему zi. Обязательно задается начальноe значeниe z0. Возьмем в качестве примера a = 5, b = 12, c = 23, и пусть z0 = 4. Вычислим нeсколько элементов последовательности:
Полученная последовательность внeшнe выглядит как довольно случайная.
Для использования в криптографических целях гeнeратор должeн удовлетворять следующим основным трeбованиям:
1) период последовательности должен быть очень большой;
2) порождаемая последовательность должна быть «почти» неотличима от действительно случайной, в частности, вычисление числа zi+1 по известным предыдущим элементам последовательность без знания ключа должно быть трудной, практически нерешаемой задачей.
Рассмотренный выше линейный конгруэнтный генератор совершенно не годится для криптографических целей, так как известны простые алгоритмы, позволяющие полностью восстановить параметры генератора всего по нескольким элементам порождаемой им последовательности.
В качестве примеров криптостойких генераторов псевдослучайных чисел мы рассмотрим режимы OFB и CTR блоковых шифров и алгоритм RC4.
Режим OFB блокового шифра
Название режима OFB (Output FeedBack) переводится как обратная связь по выходу. В этом режиме блоковый шифр на основе секретного ключа К и некоторого инициализирующего вектора Y0 формирует псевдослучайную последовательность r-битовых чисел z1, z2,..., zk, которая может использоваться в (4.8) и (4.9) соответственно для шифрования и дешифрования сообщения. Будем считать, как и ранее, что размер блока шифра равен n бит.
Псевдослучайная последовательность получается по схеме
(здесь r, , — параметр метода).
При использовании стойкого блокового шифра можно получить криптостойкий генератор, отвечающий приведенным вьше требованиям. А именно, средняя длина периода псевдослучайной последовательности (при случайно выбранных K и Y0) составляет примерно r2n-1 бит [23]. Кроме того, псевдослучайная последовательность «непредсказуема» для противника, так как возможность предсказания (вычисления) zi+1 на основе z1,..., zi означала бы нестойкость шифра по отношению к атаке по известному тексту. Предсказание zi+1 становится даже более трудной задачей, чем взлом блокового шифра, если r < n [23].
Обратим внимание на одну особенность, характерную для всех потоковых шифров. Для шифрования каждого отдельного сообщения необходимо использовать разные K и/или Y0. В противном случае несколько сообщений будут шифроваться с помощью одних и тех же последовательностей z, и такой шифр может быть раскрыт. Поясним суть проблемы. Пусть два сообщения u1, u2,..., uk и v1, v2,..., vk зашифрованы с помощью одной и той же последовательности z. Тогда шифротексты будут иметь вид
Сложим оба шифротекста и, с учетом равенства = 0, получим последовательность
Мы получили аналог так называемого «шифра с бегущим ключом», когда один текст шифруется с помощью другого текста, взятого из определенного места определенной книги. Известао, что такой шифр не стоек, хотя использовался в эпоху «донаучной» криптографии [23]. Статистический анализ, основанный на избыточности текстов, позволяет в большинстве случаев достаточно точно восстановить оба сообщения.
Дешифрование сообщений для описанного режима блокового шифра может производиться только с начала, так как невозможно получить произвольный элемент последовательности z, не вычислив предыдущие. В этом смысле режим аналогичен режиму CBC. Преимущество режима OFB заключается в том, что последовательность z может быть сформирована заранее для того, чтобы быстро шифровать или дешифровать сообщения с помощью (4.8), (4.9) в момент их поступления. Это может быть актуально для систем, обрабатывающих данные в реальном масштабе времени.
Режим CTR блокового шифра
Название данного режима происходит от слова CounTeR — счетчик. Этот режим очень похож на OFB, но в нем шифруется не предыдущий выход шифра, а просто счетчик, увеличиваемый на каждом шаге на постоянное число (обычно 1). Точнее, схема выглядит следующим образом:
где r — параметр.
При использовании «идеального» блокового шифра режим CTR обеспечивает те же параметры стойкости, что и OFB. Преимущество режима CTR состоит в том, что любой элемент последовательности z может быть вычислен непосредственно. Это дает возможность шифровать и дешифровать любые фрагменты сообщения независимо друг от друга.
Алгоритм RC4
Алгоритм RC4, предложенный Ривестом в 1994 году, относится к классу алгоритмов, разработанных специально для потоковых шифров. Генераторы псевдослучайных чисел, построенные с помощью таких алгоритмов, как правило, значительно быстрее генераторов, основанных на блоковых шифрах.
Алгоритм RC4 работает с n-битовыми словами (обычно n = 8). Все вычисления проводятся по модулю 2n (остаток x mod 2n вычисляется очень быстро путем выделения n младших бит в x с помощью логической операции «и»). RC4 использует L -словный ключ K = K0K1... KL-1 и генерирует последовательность слов Z = z1z2z3 ... , конкретный вид которой определяется ключом K. Состояние генератора задается таблицей S из 2n слов и двух переменных i и j .В каждый момент времени таблица S содержит все возможные n-битовые числа в перемешанном виде. Так как каждый элемент таблицы принимает значения в промежутке [0, 2n — 1], то его можно трактовать двояко: либо как число, либо как номер другого элемента в таблице. Секретный ключ задает только начальное перемешивание чисел в таблице, которое формируется с помощью следующего алгоритма:
После этого генератор готов к работе. Генерация очередного псевдосдучанноно слова zi осуществляется следующим образом:
П р и м е р 4.2. Пусть n = 3, K = 25 (L = 2).
Сформируем начальную перестановку чисел в таблице S (все вычисления проводим по модулю 8):
Теперь вычислим несколько первых элементов псевдослучайной последовательности z:
и т.д. Чтобы воспользоваться формулой (4.8) для получения шифра, числа zi записываем в двоичном виде. В рассмотренном примере каждое число zi представляется тремя битами, и мы получаем последовательность
Хеш-функции (hash functions) находят широкое применение в криптографии, особенно при построении систем цифровой подписи и различных криптографических протоколов, которые будут рассматриваться в последующих главах. В этом разделе мы сформулируем основные требования к криптографически стойким хеш-функциям и рассмотрим один из способов их вычисления.
Определение 4.2. Хеш-функцией называется любая функция
которая строке (сообщению) xix2 ... хn произвольной длины n ставит в соответствие целое число фиксированной длины.
Примером хеш-функции может служить контрольная сумма для сообщения. В этом случае
где размер машинного слова. Длина слова, получаемого как значение этой хеш-функции, составляет
бит независимо от длины сообщения. Контрольные суммы очень часто используются для обнаружения непреднамеренных ошибок в сообщении (при изменении одного символа контрольная сумма изменится). Однако очень легко внести преднамеренную ошибку в сообщение и сохранить при этом значение контрольной суммы. Если бы такая хеш-функция использовалась, например, при генерации электронной подписи, то было бы очень легко изменить содержание подписанного сообщения. Поэтому рассмотренная хеш-функция не годится для криптографических применений.
Сформулируем основные требования, предъявляемые к криптографическим хеш-функциям. Пусть х некоторая строка (сообщение). Тогда
1) для любого заданного х вычисление h(х) должно выполняться относительно быстро;
2) при известном y должно быть трудно (практически невозможно) найти х, для которого y=h(х);
3) при известном сообщении х должно быть трудно найти другое сообщение , такое, что
4) должно быть трудно найти какую-либо пару различны сообщений х и х', для которых
Отметим, что первое требование должно выполняться всегда, в противном случае хеш-функция теряет какое-либо практическое значение. Остальные требования важны для тех или иных приложений. Например, если пароли для входа в систему хранятся в виде значений соответствующих им хеш-функций, то хеш-функция должна удовлетворять второму требованию. В схеме электронной подписи актуально третье требование. Четвертое требование важно в некоторых криптографических протоколах. Заметим, что четвертое требование более сильное, чем третье (т.е. при выполнении четвертого автоматически выполняется и третье).
Разработка хеш-функции, удовлетворяющей всем четырем требованиям задача непростая. В настоящее время предложены и практически используются хеш-функции (например, MD5, SHA-1, RIPEMD-160 и др., см., например, [19, 23]), которые считаются отвечающими перечисленным выше требованиям (хотя это строго не доказано). Описание этих и подобных им функций усложнено в деталях и громоздко. Мы рассмотрим универсальный способ построения хеш-функций на базе блоковых шифров, который представляет практический интерес, хотя получаемые хеш-функции и не являются очень быстро вычислимыми. Именно такой подход использован в российском стандарте на криптографическую хеш-функцию (ГОСТ Р34.11-94 [7]).
Пусть дан блоковый шифр Е, который для заданного блока Х и ключа К формирует шифротекст Y,
Мы представим два алгоритма, для которых длина слова, получаемого как значение хеш-функции, равна размеру блока в шифре, но отметим, что известны конструкции, позволяющие получать хеш-функции с длинами слов, кратными размеру блока.
В первом алгоритме сообщение вначале представляется в виде последовательности блоков Х1, Х2, ... , Хn. Последний блок при необходимости дополняется нулями, иногда в последний блок приписывают длину сообщения в виде двоичного числа. Значение хеш-функции h получается как результат выполнения следующего итерационного процесса:
В качестве начального значения h можно использовать не нуль, а какое-либо «магическое» число, но это не имеет большого значения. В данном алгоритме значение h, полученное на предыдущей итерации, используется в качестве ключа шифра в следующей итерации. Поэтому неявно полагается, что длина ключа в шифре равна длине блока. Однако, как мы видели при изучении шифра RC6, длина ключа может значительно превышать размер блока (в RC6 при максимальной длине блока 256 бит длина ключа может достигать 255 байт, или 2040 бит). В таких случаях более эффективен другой алгоритм.
В этом алгоритме сообщение вначале представляется в виде последовательности Х1, Х2, ... , Хm в которой размер каждого элемента равен длине ключа в шифре. Последний элемент заполняется так же, как и в первом алгоритме. Значение хеш-функции h вычисляется следующим образом:
Здесь уже элементы сообщения выполняют роль ключей в шифре.
Представленные алгоритмы вычисления хеш-функций удовлетворяют всем четырем требованиям, предъявляемым к криптографическим хеш-функциям, в предположении стойкости используемых блоковых шифров (см. [22, 23]).