<< Предыдущая

стр. 40
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

ДА/НЕТ.
Эта схема называется схемой подписи с прилоэюением., так как под­
пись добавляется в конец сообщения перед его передачей. Получен­
ное сообщение подается на вход процедуры проверки подписи. Дру­
гой вариант — схема подписи с восстановлением сообщения^ когда
сообщение восстанавливается на выходе процедуры проверки под­
писи:
СООБЩЕНИЕ + секретный ключ Алисы = ПОДПИСЬ,
ПОДПИСЬ + ОТКРЫТЫЙ КЛЮЧ АЛИСЫ = ДА/НЕТ +
СООБЩЕНИЕ.
Важным моментом здесь является то, что только Алиса может под­
писать свое сообщение, поскольку только она имеет доступ к сво­
ему секретному ключу. С другой стороны, ее подпись может быть
Глава 10. Распределение ключей, схемы подписей и хэш-функции

проверена любым желающим, поскольку р^ля этого нужен лишь от­
крытый ключ Алисы.
Главная проблема состоит в том, каким открытым ключам мож­
но доверять. Как удостовериться, что тот или иной открытый ключ
принадлежит конкретному лицу? Вы можете считать, что данный
ключ использует Алиса, в то время как он имеет отношение к Еве.
Поэтому Ева может подписывать чеки или нечто подобное, а Вы
будете считать, что все это исходит от Алисы. Кажется мы столк­
нулись с той же проблемой управления ключами, что имела место в
симметричных системах, хотя акцент теперь падает не на сохране­
ние ключей в тайне, а на проверку их подлинности. Мы вернемся к
этой проблеме позже.
Более формально, схема цифровой подписи состоит из таких
двух преобразований:
- секретное преобразование подписи 5,
- открытое преобразование проверки V.
Далее будем предполагать, что используется схема подписи с вос­
становлением сообщения, поскольку схема подписи с приложением
несильно от нее отличается.
Алиса, посылая сообщение М, вычисляет S = s{M) и передает
результат 5, где S — цифровая подпись на сообщении М. Заме­
тим, что мы сейчас не заботимся о секретности сообщения, т. к. для
нас сейчас важно лишь то, кто его отправил. Если существенна и
конфиденциальность сообщения, то подпись S можно зашифровать,
используя, например, открытый ключ адресата.
Получатель подписи S применяет открытое преобразование про­
верки V к S и получает на выходе процедуры сообщение М и не­
который бит ^, который отвечает за результат проверки подписи.
Если результат проверки положителен, то адресат получает уверен­
ность в следующем:
- в целостности сообщения, т. е. в том, что оно не было изменено
при передаче;
- в его оригинальности, т. е. в том, что сообщение было послано
именно Алисой;
- в отсутствии ренегатства: Алиса не сможет утверждать, что
не посылала сообщения.
Заметим, что первые два момента из упомянутых присущи также
кодам аутентификации сообщений MAC. Однако последнего свой­
ства, уверенности в отсутствии ренегатства, в схемах MAC нет.
10,2. Схемы цифровой подписи

А оно имеет важное значение в электронной коммерции. Чтобы убе­
диться в этом, представьте себе, что случится, если Вы начнете
отрицать факт подписания чека, в действительности подписанного
Вами.
Алгоритм шифрования RSA представляет особый интерес, по­
скольку его можно непосредственно использовать в качестве алго­
ритма подписи с восстановлением сообш;ения.
- Отправитель применяет расшифровываюш;ее преобразование
RSA^ чтобы поставить подпись, беря сообщение и возводя его
в секретную степень d: S = т^ (modiV).
- Получатель использует шифрующую функцию RSA и восста­
навливает оригинальное сообщение: М = S^ (modTV).
При этом встает вопрос о проверке законности подписи. Если исход­
ное сообщение было написано на естественном языке, то мы можем
проверить, что восстановленное сообщение написано на том же язы­
ке. Но это не очень удачное решение. Лучшим выходом из ситуации
служит добавление к сообщению некоторой избыточной информации.
Один из способов сделать это заключается в следующем. Пред­
положим, сообщение D состоит из t битов, а модуль N алгоритма
RSA насчитывает к битов, причем t < к — 32. Тогда мы дополняем
сообщение D справа нулями до длины, кратной 8. Затем мы приба­
вляем к D {к —1)/8 байтов слева и получаем строку байтов вида
М = 00||01||FF||FF •.. ||FF||00||L),
после чего подпись вычисляется посредством формулы:
М^ (modN),
При проверке подписи правильность восстановления сообщения М
подтверждается корректностью дополнения.
К сожалению, далеко не все сообщения имеют малую длину, по­
зволяющую применить вышеупомянутый метод. Следовательно, с
наивной точки зрения для применения алгоритма подписи RSA к
длинному сообщению нам нужно разбить его на блоки и подписы­
вать каждый из них. Такой способ съедает слишком много времени,
если сообщение действительно длинное. Более того, при разбиении
сообщения на блоки нам необходимо добавлять еще некоторые из­
быточные данные, страхуясь от атак, при которых можно было бы
удалить часть блоков незаметно для получателя, как это было отме­
чено при рассмотрении режима шифрования ЕСВ. Такая проблема
возникает в связи с тем, что наша схема подписи основана на вое-
Глава 10. Распределение ключей, схемы подписей и хэш-функции

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


10,3. Хэш-функции
Криптографическая хэш-функция h — это функция, определенная
на битовых строках произвольной длины со значениями в стро­
ках битов фиксированной длины. Ее значение часто называют хэги-
кодом или хэш-значением, В информатике тоже используются свое­
го рода хэш-функции, но важное отличие криптографических хэш-
функций от стандартных состоит в том, что первые должны быть
односторонними. Другими словами, должно быть невозможно в вы­
числительном отношении по элементу Y из множества значений
хэш-функции подобрать такой х из области определения, при ко­
тором h{x) = Y. Другая характеризация односторонних хэш-функ­
ций — сказать о них, что они защищены от восстановления прообра­
зов. Применение криптографических хэш-функций позволяет создать
схему подписи RSA без восстановления сообщения, что намного эф­
фективней для длинных сообщений.
Предположим, нам дано длинное сообщение М д^ля визирования.
Сначала вычисляется h{M) и потом применяется преобразование
подписи RSA к хэш-значению h{M)^ т.е. подпись получается как
S = h{M)^ (modTV).
Наконец, подпись и само сообщение передаются вместе в виде пары
(М, S). Проверка пары (М, S) состоит из трех этапов:
- «Шифрование» S с помощью шифрующей экспоненты RSA р^ля
получения Н':
Н' = S^ (modiV).
- Вычисление h{M) по М.
- Проверка равенства Н' — h{M), Если оно верно, то подпись
законна. В противном случае — незаконна.
На самом деле при практическом использовании тут тоже нужно
пополнение, но его можно делать например так, как в схеме подписи
с восстановлением сообщения.
10.3. Хэш-функции

Итак, почему нам нужна хэш-функция со свойством односторон­
ности? Ответ заключается в том, что свойство односторонности
препятствует криптоаналитику фабриковать сообш;ение с данной
подписью. Предположите, например, что мы используем только что
описанную схему подписи RSA с приложением, но хэш-функцию бе­
рем стандартную, а не одностороннюю. Тогда возможна следуюш;ая
атака.
- Ева вычисляет Н' — R^ (mod N) с некоторым выбранным на­
угад целом числом R.
- Кроме того, она находит прообраз значения Н^ при отобра­
жении h (напомним, что h сейчас стандартная хэш-функция и
вычисление прообраза вполне возможно), т.е. Ева определяет
М= h-^H').
Теперь Ева обладает Вашей подписью (М, R) сообш;ения М. Такая
подделка называется экзистенциальной. В ней нападающий не име­
ет контроля над содержанием сообщения, на которое он поставил
Вашу подпись.
На практике требуется нечто большее, чем свойство односторон­
ности. Хэш-функцию h называют защищенной от повторений^ если
вычислительно невозможно найти два таких различных значения х
и х\ при которых h{x) = h{x').
Это требование помогает избежать следующих атак со стороны
подписывающего лица.
- Отправитель выбирает два сообщения М и М', удовлетворя­
ющие соотношению h{M) = h{M').
- Он подписывает М и получает подпись (М, S).
- Потом он отказывается от своего сообщения, утверждая, что
посылал сообщение М'.
Например, можно предположить, что М — электронный чек на сум­
му в 1000 евро, в то время как М' — чек на сумму в 10 евро. Ясно,
что получится неприятность.
Ввиду парадокса дней рождений залщщенные от повторений хэш-
функции строятся сложнее, чем односторонние. Чтобы найти по­
вторы в значениях хэш-функции / , нам необходимо запоминать ре­
зультаты вычисления / ( ^ i ) , /(^2)? /(^з)? и т. д., пока не встретится
повторение. Если значения этой функции имеют длину п битов, то
ожидаемое совпадение появится через 0(2^/^) итераций. Эту оцен­
ку стоит сравнить с числом шагов, необходимых для вычисления
прообраза, которое имеет порядок 0(2^) для корректно заданной
Глава 10. Распределение ключей, схемы подписей и хэш-функции

хэш-функции. Следовательно, для достижения необходимого уровня
стойкости устойчивая от повторений функция, определенная на 80-
битовых строках должна принимать значения в 160-битовых стро­
ках.
Но и этого еще недостаточно. Криптографическая хэш-функция
должна обладать свойством защищенности от вторых прообразов^
т. е. по данному М должно быть практически невозможно отыскать
такой М' ф М, ]\^1я которого h{M) = h{M'), Это требование обес­
печивает стойкость против следующих атак:
- нападающий получает Вашу подпись (М, S) на сообщении М;
- находит другое сообщение М'^ р^ля которого h{M) = h{M')\
- ставит Вашу подпись [M'^S) на своем сообщении М'.
В итоге криптографические хэш-функции должны обладать сле­
дующими тремя свойствами:
1) защищенностью от восстановления прообразов: должно
быть невозможно в вычислительном отношении найти сообще­
ние с данным значением хэш-функции;
2) защищенностью от повторений: вычислительно невозмож­
но найти два сообщения с одним и тем же значением хэш-
функции;
3) защищенностью от вторых прообразов: по данному сооб­
щению нереально найти другое сообщение с тем же значением
хэш-функции.
Как же соотносятся эти свойства? Как и в случае анализа кри­
птосистем с открытым ключом, мы можем проследить связи свойств,
сводя одно из них к другому.

Л е м м а 10.1. Свойство защищенности от восстановления прообра­
зов сильнее защищенности от повторений и вторых прообразов.
Доказательство. Пусть h — функция, а О обозначает оракул,
который по данному у находит такой ж, что h{x) = у^ т.е. О — ора­
кул, взламывающий защищецность от восстановления прообразов
функции h.
Используя О, мы можем найти повторения в значениях /i, выбрав
X наугад и вычислив у = h{x). Подставив найденное значение у в
=
оракул, мы найдем ж', удовлетворяющий равенству у = h{x'). Пос­
кольку область определения функции h бесконечна, вероятность со­
впадения X = х' крайне мала. Следовательно, мы нашли повторение
значений функции h.
10.3. Хэш-функции

Аналогичным рассуждением можно показать, как используя ал­
горитм, взламывающий защищенность от восстановления прообра­
зов, можно найти второй прообраз. •

Лемма 10.2. Защищенность от вторых прообразов сильнее защи­
щенности от повторений.
Доказательство. Пусть существует оракул (!?, который по данно­
му X может отыскать х' ф х^ для которого h{x^) = h{x). Ясно, что
с его помощью мы легко найдем повторения, взяв произвольное х и
применив оракул. •
Хотелось бы основывать криптографические схемы на самых
сильных свойствах. Но в этой главе мы будем считать, что все ис­
пользуемые хэш-функции защищены от повторений, т.е. выберем
самое слабое свойство. В следующих главах мы познакомимся с кри­
птографическими схемами, в которых требуются функции, защи­
щенные от вторых прообразов.
Заметим, что криптостойкость любой схемы цифровой подпи­
си, использующей криптографические хэш-функции, зависит как от
сложности подлежащей математической задачи, такой, например,
как задачи факторизации или дискретного логарифмирования, так
и от стойкости хэш-функции.
Криптографические хэш-функции без повторений можно при­
менять как основу MAC. Одна из возможностей построения кода
МЛ С, опирающегося на хэш-функции, состоит в присоединении к
сообщению ключа и применении к такой связке хэш-функции, т. е.
MAC = h{M\\k),
хотя этот способ не считают особенно удачным. Во многих рабо­
тах коды аутентификации сообщений, работающие по этому же, но
чуть более сложному (в целях повышения стойкости) принципу, на­
зывают НМАС:
НМАС = h{k\\Pi\\h{k\\P2\\M)),
где Fi и Р2 — последовательности символов, используемые для по­
полнения входных данных до полных блоков.
Хэш-функции можно также рассматривать как специальный тип
кодов обнаружения вмешательства, MDC (от англ. manipulation de­
tection code). Например, хэш-функцию можно использовать для за­
щиты целостности больших файлов так, как это делается в неко­
торых программах защиты от вирусов. Вычисляется значение хэш-
Глава 10. Распределение ключей, схемы подписей и хэш-функции

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

<< Предыдущая

стр. 40
(из 82 стр.)

ОГЛАВЛЕНИЕ

Следующая >>