Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
40
Часть I. Введение
числа а; и не может от него отказаться. На этом жеребьевка с помощью монеты завершается.
Во-вторых, благодаря свойству I, Боб не может определить, является прообраз, известный Алисе, четным или нечетным при заданном значении f(x). Следовательно, предположение Боба, сделанное им на втором шаге протокола, является настоящей догадкой (т.е. догадкой, сделанной при полном отсутствии информации). На этом этапе Алиса может убедить Боба, верна ли его догадка, назвав число ж(шаг 3). Боб может проверить это, самостоятельно вычислив функцию f(x) (шаг 4) и сравнив ее с числом, полученным от Алисы на первом шаге, предполагая, что функция f(x) обладает заявленными свойствами. Кроме того, жеребьевка является корректной, если число х извлекается из достаточно большого множества, чтобы вероятность угадать четность числа х не превышала 50%.
Следует подчеркнуть, что, проводя наш "анализ стойкости", мы многое упростили и о многом умолчали. В результате текущая версия протокола далека от совершенства. Некоторые упрощения и умолчания мы обсудим в следующей главе. Криптографические средства, необходимые для правильной и точной реализации данного протокола, а также методы анализа его стойкости будут рассмотрены в дальнейших главах. Мы отложим конкретную реализацию протокола 1.1, основанную на свойствах волшебной функции f(x), до заключительной части книги, содержащей техническую информацию (глава 19) Для того чтобы провести формальный анализ стойкости конкретной реализации протокола, нам необходимо овладеть соответствующими методами.
1.1.2 Первые сведения об основах криптографии
Хотя наш первый протокол весьма прост, его можно назвать полноценным криптографическим протоколом, поскольку волшебная функция, положенная в его основу, представляет собой основной ингредиент современной криптографии: однонаправленную функцию (one-way function). Два волшебных свойства этой функции ставят две трудноразрешимые вычислительные задачи (computationally intractable): одну — перед Алисой, а вторую — перед Бобом.
Элементарный анализ стойкости протокола 1.1 показывает, что однонаправленная функция предоставляет надежное средство выбора места отдыха. Обобщим это утверждение.
Существование однонаправленной функции гарантирует существование стойкой криптографической системы.
В настоящее время хорошо известно, что справедливо и обратное утверждение.
Существование стойкой криптографической системы предполагает существование однонаправленной функции.
Глава 1. Защита информации в игре "орел или решка"
41
Широко распространено мнение, что однонаправленные функции действительно существуют. Это внушает уверенность в том, что мы можем защитить информацию. Наш оптимизм часто подкрепляется повседневным опытом: многие процессы, протекающие в реальном мире, носят однонаправленный характер. Рассмотрим следующее физическое явление (хотя у него нет точного математического аналога): уронить стакан на пол и разбить его на мелкие осколки довольно легко, поскольку при этом происходит рассеивание определенного объема энергии (т.е. тепла, акустических волн и даже слабого света) в окружающей среде. Обратный процесс, заключающийся в собирании рассеянной энергии и воссоединении разбросанных осколков, чтобы получился целый стакан, представляет собой весьма трудную, скорее, даже неразрешимую проблему. (Если бы это было возможно, восстановленная энергия вернула бы стакан на ту высоту, с которой он упал!)
Класс математических функций, обладающих свойствами однонаправленности, необходимыми для современной криптографии, будет рассмотрен в главе 4.
1.1.3 Основы информационной безопасности: не только трудноразрешимые вычислительные задачи
Итак, мы утверждаем, что для защиты информации необходимы определенные математические свойства. Более того, мы оптимистично заявили, что верно и обратное: математические свойства предполагают (т.е. гарантируют) защиту информации.
Однако в реальности последнее утверждение не всегда справедливо! Безопасность информации в реальных приложениях зависит от многих аспектов. Для подтверждения своих слов рассмотрим наш первый протокол.
Следует заметить, что в ходе анализа стойкости протокола 1.1 мы проигнорировали многие важные аспекты. Фактически сам по себе протокол 1.1 представляет собой значительно упрощенную спецификацию. В нем не учтены некоторые детали, влияющие на степень надежности. Это позволило нам не задавать некоторые неудобные вопросы.
Например, мы могли бы спросить: действительно ли Алиса вынуждена фиксировать свой выбор числа х1 И наоборот, действительно ли Боб вынужден фиксировать свою догадку о четности или нечетности числа xl Под словом "вынужден" мы имеем в виду следующее: может ли голос по телефону гарантировать строгие математические свойства, обеспечивающие защиту информации? Можно было бы поинтересоваться, достаточно ли хороший генератор случайных чисел использует Алиса при выборе случайного числа xl Качество этого генератора крайне важно для многих серьезных приложений, в которых необходимо принимать правильное
