Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Классические шифры, даже простые подстановочные шифры, могут оказаться очень стойкими, если криптографические ключи подчиняются определенным условиям. По этой причине простые подстановочные шифры широко применяются в криптографических системах и протоколах.
7.5.1 Полезность классических шифров
Рассмотрим пример сдвигового шифра (простейший пример подстановочного шифра), который применяется в криптографическом протоколе. Это позволит нам сформулировать два важных условия, обеспечивающих стойкость классических шифров.
Допустим, что над группой Zn задана функция f(x), обладающая следующими двумя свойствами.
Однонаправленность. При заданном элементе х € Zn функция f(x) допускает эффективное вычисление (это понятие рассматривается в разделе 4.4.6). В то же время для почти всех элементов у G Zn и для любого эффективного] алгоритма А вероятность Р[х *— А(у) А /(ж) = у] пренебрежимо мала по! сравнению с величиной у (понятие пренебрежимо малой величины описано] в разделе 4.6).
Гомоморфизм. Для всех xi,x2E Zn выполняется условие f(x\ + х2) = f{xi) ¦
Существует много функций, удовлетворяющих такому условию. Используя их, можно построить протокол "доказательства с нулевым разглашением", позволяющий доказывающей стороне (например, Алисе) доказать верификатору (например, Бобу), что Алиса знает прообраз элемента f(z) (где z < тг), не сообщая
Глава 7. Шифрование — симметричные методы
259
самого прообраза. Этого можно достичь с помощью простого протокола, использующего сдвиговый шифр.
Протокол 7.1. Протокол доказательства с нулевым разглашением на основе сдвигового шифра
ОБЩИЕ ВХОДНЫЕ ДАННЫЕ:
1. /(): однонаправленная и гомоморфная функция над группой Ъп;
2. X = f(z) для некоторого z Е Ъп. ВХОДНЫЕ ДАННЫЕ АЛИСЫ:
z < п (* Закрытые входные данные доказывающей стороны *) ЗАКЛЮЧЕНИЕ БОБА:
Алиса знает элемент z € Ъп, удовлетворяющий условию X =¦ f(z).
Следующие шаги выполняются т раз.
1. Алиса извлекает число кЕцЪп, вычисляет число Commit *— /(fc) и посылает его Бобу.
2. Боб извлекает число Challenge € с/{0,1} и посылает его Алисе.
3. Алиса вычисляет число
Response
[к
\к +
если Challenge = О, z(modn), если Challenge = 1
и посылает его Бобу.
(* Если Challenge = 1, число Response является результатом шифрования числа z с помощью сдвигового шифра и одноразового ключа к (см. раздел 7.3.1). *)
4. Боб проверяет условие
_ . 7 [Commit, если Challenge = О,
/(Response) = \ у
[Commit • X, если Challenge = 1.
Если на каком-либо шаге возникает ошибка, Боб отвергает доказательство и прекращает выполнение протокола. Боб принимает доказательство.
Протокол 7.1 весьма полезен. В приложениях величина X = f(z) может выступать в роли криптографического удостоверения Алисы, позволяющего ее идентифицировать. Это удостоверение может использовать только Алиса, поскольку лишь она знает, как с ним обращаться, учитывая прообраз z. Этот протокол демон-
260
Часть III. Основные методы криптографии
стрирует, как Алиса должна применять свое удостоверение без предоставление Бобу какой-либо информации о прообразе z.
В главе 18 мы будем интенсивно применять этот протокол и его модификации при описании протокола доказательства с нулевым разглашением.
7.5.2 Стойкость классических шифров
Какой уровень конфиденциальности, позволяющий Алисе скрывать секретную) информацию о прообразе z, обеспечивает протокол 7.1? Мы утверждаем, что этот! протокол обеспечивает высший уровень секретности. Иначе говоря, после запуска^ протокола Боб не получает абсолютно никакой новой информации об элемента z б Zn, кроме той, которую он мог получить, анализируя величину f(z) (общия входные данные предоставляют только априорную информацию).
Следует заметить, что шифрование с помощью сдвигового шифра
Response = z + fc(mod тг)
образует перестановку над группой Zn. Если к G и%п = К = М, перестановка переводит это число в элемент Response е c/Zn, поскольку она отображает равно-' мерное распределение в равномерное распределение. Это означает, что заданный] зашифрованный текст Response мог быть создан с помощью любого ключа из группы Zn (вероятностное пространство состоит из пространства ключей и про-] странства сообщений). Иначе говоря, в сообщении Response с одинаковой веро-| ятностью мог быть зашифрован любой элемент х е Zn. Итак, исходный текст z на зависит от зашифрованного текста Response, т.е. зашифрованный текст не предо-J ставляет никакой информации об исходном тексте.
Если шифр обеспечивает независимость между распределениями исходных! и зашифрованных текстов, говорят, что шифр является стойким в информационно-теоретическом смысле (information-theoretically secure sense). В отличие си стойкости в смысле вычислительной сложности (complex-theoretic sence), устаЛ новленной в главе 4, стойкость в теоретико-информационном смысле является безусловной и не поддается ни одному из методов криптоанализа. Относителыш протокола 7.1 это означает, что запуск протокола не предоставляет Бобу никакой информации о закрытых входных данных Алисы z, кроме того, что этот bboJ является секретным.
