Например, А заменяется на Г, Б на Д и т. Три последние буквы русского алфавита — Э, Ю, Я — шифруются буквами А, Б, В соответственно. Например, слово ПЕРЕМЕНА после применения к нему шифра Цезаря превращается в ТИУИПИРГ . Последующие римские цезари модифицировали шифр, используя смещение в алфавите на четыре, пять и более букв. Мы можем описать их шифр в общем виде, если пронумеруем . Для этого Алиса каким. Замену ключа можно проводить, например, перед каждым сеансом связи или после передачи фиксированного числа букв . В таком случае говорят, что ключ порождается источником ключа. Схема рассмотренной криптосистемы с секретным ключом приведена на рис. Классическая система секретной связи . Введение Обратимся теперь к анализу действий противника, пытающегося расшифровать сообщение и узнать секретный ключ, иными словами, вскрыть, или взломать шифр. Каждая попытка вскрытия шифра называется атакой на шифр . В криптографии принято считать, что противник может знать использованный алгоритм шифрования, характер передаваемых сообщений и перехваченный шифротекст, но не знает секретный ключ. Иногда это правило кажется . В нашем примере Ева знает, что шифр был построен в соответствии с . Наиболее очевидная попытка расшифровки — последовательный перебор всех возможных ключей . Итак, Ева перебирает последовательно все возможные ключи к . , подставляя их в алгоритм дешифрования и оценивая получающиеся результаты. Попробуем и мы использовать этот метод. В большинстве случаев нам достаточно было расшифровать две. расшифровка слова тиуипирг путем перебора ключей к га к . Причем для того, чтобы про Глава . Из этого примера мы видим, что рассмотренный шифр совершенно нестоек, для его вскрытия достаточно проанализировать несколько первых букв сообщения и после этого ключ к однозначно определяется . В чем же причины нестойкости рассмотренного шифра и как можно было бы увеличить его стойкость. Алиса спрятала важные документы в ячейке камеры хранения, снабженной пяти декадным кодовым замком. Теперь она хотела бы сообщить Бобу комбинацию цифр, открывающую ячейку. Она решила использовать аналог шифра Цезаря, адаптированный к алфавиту, состоящему из десятичных цифр. Ева пытается расшифровать его, последовательно перебирая все возможные ключи. Результаты ее попыток сведены в табл. Анализируя шифротекст, она не может найти значения секретного ключа. Конечно, до перехвата сообщения у Евы было . Однако важно отметить то, что в данном случае всего . Поэтому при таком ключе . В первом примере сообщение — текст на русском языке, поэтому оно подчиняется многочисленным правилам, различные буквы и их сочетания имеют различные вероятности и, в частности, многие наборы букв вообще запрещены. В противоположность этому, во втором примере все комбинации цифр допустимы. Поэтому даже простой шифр, примененный к сообщениям этого языка, становится невскрываемым. В классической работе К. Мы кратко коснемся этих вопросов в главе . Описанная в приведенных примерах атака называется атакой по шифротексту. Но часто на шифр может быть проведена атака по известному тексту. Это происходит, если Ева получает в свое распоряжение какие. Можно представить себе и более . Например, во время Второй мировой войны американцы, подкупив охрану, выкрали шифровальную машину в японском посольстве на два дня и имели возможность подавать ей на вход различные тексты и получать соответствующие шифровки. Но разработчики современных криптосистем стремятся сделать их неуязвимыми даже и по отношению к атакам по выбранному тексту, и Задачи и упражнения . Иногда считается, что более надежно использовать шифр, противостоящий атаке по выбранному тексту, чем организационно. Итак, мы познакомились с основными героями криптографии — Алисой, Бобом и Евой и с важными понятиями этой науки — шифром, ключом, атакой, открытым и защищенным каналом. Заметим, что с последним понятием связан один интригующий факт — возможно построение надежных криптосистем без защищенного канала. Это открытие было сделано в основополагающих работах Диффи, Хеллмана и Меркля . Большая часть этой книги будет связана именно с такими системами, называемыми схемами с открытым, или несимметричным ключом. Задачи и упражнения . Определить ключи шифра Цезаря, если известны следующие пары открытый текст шифротекст. Расшифровать следующие сообщения, зашифрованные шифром Цезаря с неизвестным ключом к, О к . КРИПТОСИСТЕМЫ С ОТКРЫТЫМ КЛЮЧОМ . Предыстория и основные идеи Рассмотрим три задачи, решение которых поможет нам лучше понять идеи и методы криптографии с открытым ключом. Все эти задачи имеют важное практическое значение. Первая задача — хранение паролей в компьютере. Мы знаем, что каждый пользователь в сети имеет свой секретный пароль. При входе в сеть пользователь указывает свое имя . Проблема состоит в следующем. Поэтому необходимо организовать хранение паролей в компьютере так, чтобы такой . Вторая задача возникла с появлением радиолокаторов и системы ПВО. При пересечении самолетом границы радиолокатор спрашивает пароль. Если пароль верный, то самолет . Здесь возникает такая проблема. Третья задача похожа на предыдущую и возникает в компьютерных сетях с удаленным доступом, например, при взаимодействии банка и клиента. Обычно в начале сеанса банк запрашивает у клиента имя, а затем секретный пароль, но Ева может узнать пароль, так как линия связи открытая. Сегодня все эти проблемы решаются с использованием криптографических методов. Решение всех этих задач основано на важном понятии односторонней функции . Предыстория и основные идеи . Пусть дана функция У . Данное определение, безусловно, неформально. Строгое определение односторонней функции может быть найдено в . В качестве примера односторонней функции рассмотрим следующую. такое, которое делится без остатка только на себя и на единицу. Обратная функция обозначается и называется дискретным логарифмом. Для того чтобы обеспечить трудность вычисления по .