Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Стремление гарантировать соблюдение правил игры побуждает нас защитить игроков от мошенничества. Способ, которым достигается эта цель, широко применяется для защиты связи в открытых сетях — это сокрытие информации с помощью криптографии.
Средства прикладной криптографии позволяют получить качественное решение нашей первой задачи, связанной с защитой информации. Это позволит нам в дальнейшем перейти к обсуждению критериев качества криптографических систем (раздел 1.2). Кроме того, мы рассмотрим подоплеку и культурные аспекты тех областей, в которых необходимо применять технологии защиты конфиденциальной информации.
38
Часть I. Введение
1.1 Орел или решка
Сформулируем простую задачу. Алиса и Боб1 хотят провести вечер вместе, но не могут решить, куда идти: в кино или в театр. Чтобы разрешить возникший спор, они договорились подбросить монету: этот способ жеребьевки известен всем.
Алиса берет монету и говорит Бобу: "Ты выбираешь сторону, а я подбрасываю монету". Боб соглашается, и Алиса подбрасывает монету в воздух. Затем они вместе смотрят, какой стороной вверх упала монета. Если выпал результат, выбранный Бобом, то Боб решает, куда идти, в противном случае Боб подчиняется Алисе.
В работах, посвященных процедурам обмена информацией, многосторонняя игра, подобная описанной выше, носит специальное название — протокол. Строго говоря, протоколом называется точно определенная последовательность действий, выполняемых несколькими участниками. Следует подчеркнуть, что протокол всегда предполагает существование нескольких участников; если вся процедура полностью выполняется одним участником, ее нельзя называть протоколом.
1.1.1 Первое знакомство с криптографией
Теперь представьте, что Алиса и Боб выполняют описанный выше протокол, разговаривая по телефону. Алиса предлагает Бобу: "Выбери сторону монеты, а я ее подброшу и скажу, выиграл ты или нет". Разумеется, Боб не согласится, поскольку не может проверить результат жеребьевки.
Добавим в этот протокол немного криптографии и вернемся к варианту жеребьевки по телефону. В результате мы получим криптографический протокол — первый в нашей книге! Давайте рассматривать нашу "криптографию" как математическую функцию f{x), определенную на множестве целых чисел и обладающую следующими волшебными свойствами.
Свойство 1.1. Волшебная функция / /. Для каждого целого числа х мы можем легко вычислить значение f{x), однако по заданному значению f(x) невозможно восстановить его прообраз х, например, определить, каким числом является х — четным или нечетным.
II. Невозможно найти пару чисел (ж, у), таких что хфу и f{x) — f(y).
В свойстве 1.1 употребляются наречия "легко" и "невозможно". Их смысл необходимо разъяснить. Поскольку оба слова определяют степень трудности какого-то действия, их взаимное соотношение вполне понятно. Однако, поскольку
'Алиса и Боб являются широко известными персонажами в области криптографии, криптографических протоколов и защиты информации; они будут участниками большинства криптографических протоколов, обсуждаемых в книге.
Глава 1. Защита информации в игре "орел или решка"
39
Протокол 1.1. Подбрасывание монеты по телефону
ИСХОДНЫЕ УСЛОВИЯ:
Алиса и Боб договорились о следующем:
а) волшебная функция / обладает свойствами 1.1;
б) если х — четное число, то f(x) означает ОРЕЛ, в противном случае f(x) означает РЕШКА.
( * Внимание. Условие б является слабым местом протокола, см. упражнение 1.2. * )
1. Алиса выбирает большое случайное целое число х, вычисляет значение f(x) и сообщает его Бобу по телефону.
2. Боб сообщает Алисе свою догадку о числе х: четное оно или нечетное.
3. Алиса называет Бобу число х.
4. Боб проверяет значение /(ж) и убеждается в правоте или неправоте своей догадки.
мы считаем, что функция f(x) обладает волшебными свойствами, можно использовать эти слова в их общеупотребительном значении. В главе 4 будет сформулировано математическое определение понятий "легко" и "невозможно". Одна из основных целей книги — установить различные количественные значения слов "легко", "трудно" и даже "невозможно". Фактически, как мы убедимся после изучения главы 19, содержащей окончательную реализацию протокола жеребьевки с помощью монеты, слово "невозможно" в формулировке свойств 1.1 имеет два совершенно разных количественных значения.
Предположим, что Алиса и Боб согласились применить волшебную функцию f{x). Допустим также, что они договорились четное число считать эквивалентом ОРЛА, а нечетное — РЕШКИ. Теперь они готовы выполнить наш первый криптографический протокол 1.1.
Очевидно, что протокол "Подбрасывание монеты по телефону" вполне работоспособен. Проведем элементарный "анализ стойкости" этого протокола. (Предупреждение: мы заключили слова "анализ стойкости" в кавычки, поскольку этот анализ далеко не полон.)
1.1.1.1 Элементарный "анализ стойкости"
Во-первых, свойство II функции f(x) означает, что Алиса не может найти два разных числа х и у, одно из которых было бы четным, а другое — нечетным (этот факт можно выразить формулой х Ф y(mod2)), таких что f(x) = /(у). Следовательно, сообщив значение f(x) Бобу (шаг 1), Алиса фиксирует свой выбор
