Сергей Дориченко - 25 этюдов о шифрах
Например, если роль сциталя выполняет карандаш с шестью гранями, то открытый текст КРИПТОГРАФИЯ может быть преобразован в шифртекст РПОРФЯКИТГАИ. Шифртекст может быть и другим, так как он зависит не только от диаметра карандаша. Поэкспериментируйте!
Отметим, что в этом шифре преобразование открытого текста в шифрованный заключается в определенной перестановке букв открытого текста. Поэтому класс шифров, к которым относится и шифр «Сциталь», называется шифрами перестановки. Математическому описанию таких шифров посвящен этюд 2.4.
Шифр Цезаря. Этот шифр реализует следующее преобразование открытого текста: каждая буква открытого текста заменяется третьей после нее буквой в алфавите, который считается написанным по кругу, т.е. после буквы «я» следует буква «а». Поэтому класс шифров, к которым относится и шифр Цезаря, называется шифрами замены. Математическому описанию таких шифров посвящен этюд 2.4.
Например, открытый текст КРИПТОГРАФИЯ при таком способе шифрования преобразуется в шифртекст НУЛТХСЁУГЧЛВ. Отметим, что Цезарь заменял букву третьей после нее буквой, но можно заменять и пятой, и какой-нибудь другой. Главное, чтобы тот, кому посылается шифрованное сообщение, знал эту величину сдвига.
Шифр Виженера. Этот шифр удобнее всего представлять себе как шифр Цезаря с переменной величиной сдвига. Чтобы знать, на сколько сдвигать очередную букву открытого текста, заранее договариваются о способе запоминания сдвигов. Сам Виженер предлагал запоминать ключевое слово, каждая буква которого своим номером в алфавите указывает величину сдвига. Ключевое слово повторяется столько раз, сколько нужно для замены всех букв открытого текста. Например, ключевое слово ВАЗА означает следующую последовательность сдвигов букв открытого текста: 3191319131913191... Например, открытый текст КРИПТОГРАФИЯ при таком способе шифрования преобразуется в шифртекст НССРХПЛСГХСА.
Дальнейшее развитие идеи ключевого слова, а именно, идея запоминать способ преобразования открытого текста с помощью какой-либо книги, привело к возникновению различных видов так называемых книжных шифров. Они хорошо известны любителям детективной и приключенческой литературы.
Подумайте сами:
1. Поэкспериментируйте с шифрами Цезаря и Виженера.
2. Попробуйте найти способ вскрытия шифра «Сциталь» (не зная диаметра сциталя).
1.5. Что такое ключ?
Под ключом в криптографии понимают сменный элемент шифра, который применен для шифрования конкретного сообщения.
В древнейшем шифре «Сциталь», описанном в этюде 1.4, ключом является диаметр сциталя. При этом не меняя принцип построения шифра, можно для шифрования разных сообщений пользоваться сциталями разных диаметров.
В шифрах типа шифра Цезаря ключом является величина сдвига букв шифртекста относительно букв открытого текста.
Зачем же нужен ключ? Из предыдущего изложения понятно, что придумывание хорошего шифра — дело трудоемкое. Поэтому желательно увеличить «время жизни» хорошего шифра и использовать его для шифрования как можно большего количества сообщений. Но при этом возникает опасность, что противник уже разгадал (вскрыл) шифр и читает защищаемую информацию. Если же в шифре есть сменный ключ, то, заменив ключ, можно сделать так, что разработанные противником методы уже не дают эффекта. Этот принцип особенно полезен и важен в тех случаях, когда применимы дорогостоящие шифрующие машины (шифрмашины) в больших сетях связи.
Описанные соображения привели к тому, что безопасность защищаемой информации стала определяться в первую очередь ключом. Сам шифр, шифрмашина или принцип шифрования стали считать известными противнику и доступными для предварительного изучения. Но применяемые в шифрах преобразования информации стали сильно зависеть от ключа. А для противника появились новая задача — определить ключ, после чего можно легко прочитать зашифрованные на этом ключе сообщения. Законные пользователи, прежде чем обмениваться шифрованными сообщениями, должны тайно от противника обменяться ключами или установить одинаковый ключ на обоих концах канала связи.
Вернёмся к формальному описанию основного объекта криптографии (этюд 1.3). Теперь в него необходимо внести существенное изменение — добавить недоступный для противника секретный канал связи для обмена ключами:
Практическое построение таких сетей связи для большого обмена шифрованными сообщениями стало ещё более дорогостоящим мероприятием.
Подумайте сами:
1. Что является ключом в шифре Виженера.
1.6. Атака на шифр. Стойкость шифра
Под атакой на шифр понимают попытку вскрытия этого шифра.
Под стойкостью шифра понимают способность шифра противостоять всевозможным атакам на него.
Понятие стойкости шифра является центральным для криптографии. Хотя качественно понять его довольно легко, но получение строгих доказуемых оценок стойкости для каждого конкретного шифра — проблема нерешённая. Это объясняется тем, что до сих пор нет необходимых для решения такой проблемы математических результатов. (Мы вернемся к обсуждению этого вопроса в этюде 2.6.) Поэтому стойкость конкретного шифра оценивается только путем всевозможных попыток его вскрытия и зависит от квалификации криптоаналитиков, атакующих шифр. Последнюю процедуру иногда называют проверкой стойкости.
Важным подготовительным этапом для проверки стойкости шифра является продумывание различных предполагаемых возможностей, с помощью которых противник может атаковать шифр. Появление таких возможностей у противника обычно не зависит от криптографии, это является некоторой внешней подсказкой и существенно влияет на стойкость шифра. Поэтому оценки стойкости шифра всегда содержат те предположения о противнике, в условиях которых эти оценки получены.
Прежде всего, как это уже отмечалось в этюде 1.5, обычно считается, что противник знает сам шифр и имеет возможности для его предварительного изучения. Противник также знает некоторые характеристики открытых текстов (защищаемой информации), например, общую тематику сообщений, их стиль, некоторые стандарты, форматы и т.д.
Из более специфических приведем еще три примера возможностей противника:
▪ противник может перехватывать все шифрованные сообщения, но не имеет соответствующих им открытых текстов;
▪ противник может перехватывать все шифрованные сообщения и добывать соответствующие им открытые тексты;
▪ противник имеет доступ к шифру (но не к ключам!) и поэтому может зашифровывать и дешифровывать любую информацию.
Рекомендуем самостоятельно придумать еще несколько возможностей противника. Подскажем, например, использование так называемого «вероятного слова» в открытом тексте: противнику из каких-либо соображений известно, что в открытом тексте встречается конкретное слово. Иногда такая информация облегчает процесс вскрытия шифра.
На протяжении многих веков среди специалистов не утихали споры о стойкости шифров и о возможности построения абсолютно стойкого шифра. Приведем два характерных высказывания на этот счет.
Английский математик Чарльз Беббидж (XIX в): «Всякий человек, даже если он не знаком с техникой вскрытия шифров, твердо считает, что сможет изобрести абсолютно стойкий шифр, и чем более умен и образован этот человек, тем более твердо это убеждение. Я сам разделял эту уверенность в течение многих лет».
«Отец кибернетики» Норберт Винер (XX в): «Любой шифр может быть вскрыт, если только в этом есть настоятельная необходимость и информация, которую предполагается получить, стоит затраченных средств, усилий и времени...»
Мы вернемся к этому вопросу в этюде 2.5 после рассказа о работах Клода Шеннона.
1.7. Криптография и криптология
Криптпология — наука, состоящая из двух ветвей: криптографии и криптоанализа.
Криптография — наука о способах преобразования (шифрования) информации с целью ее защиты от незаконных пользователей.
Криптоанализ — наука (и практика ее применения) о методах и способах вскрытия шифров.
В последнее время наряду со словом «криптография» часто встречается и слово «криптология», но соотношение между ними не всегда понимается правильно. Сейчас происходит окончательное формирование этих научных дисциплин, уточняются их предмет и задачи.
Соотношение криптографии и криптоанализа очевидно: криптография — защита, т.е. разработка шифров, а криптоанализ — нападение, т.е. атака на шифры. Однако эти две дисциплины связаны друг с другом, и не бывает хороших криптографов, не владеющих методами криптоанализа. Дело в том, что стойкость разработанного шифра можно доказать только с помощью проведения различных атак на шифр, становясь мысленно в положение противника (см. этюды 1.6, 2.6).
