Раздел 2. Организация и технология обеспечения информационной безопасности

Раздел 2. Организация и технология обеспечения информационной безопасности

Часть 2

 

Основы криптографии

2.5.1. Основные понятия и определения

Как и любая наука, криптография опирается на базовые понятия и определения. Рассмотрим основные из них.

Криптография  (от др.-греч. κρυπτός (криптос) – тайный, скрытый  и γράφω (графо) – пишу) – наука о методах обеспечения конфиденциальности (невозможности прочтения информации посторонним), целостности данных (невозможности незаметного изменения информации) и аутентификации (проверки подлинности авторства или иных свойств объекта), а также невозможности отказа от авторства.

Изначально криптография изучала методы шифрования информации – обратимого преобразования открытого (исходного) текста на основе секретного алгоритма и/или ключа в шифрованный текст (шифротекст). Традиционная криптография образует раздел симметричных криптосистем, в которых шифрование и расшифровывание проводится с использованием одного и того же секретного ключа. Помимо этого раздела современная криптография включает в себя асимметричные криптосистемы, использующие два ключа, системы электронной подписи (ЭП), хеш-функции, управление ключами, получение скрытой информации, квантовую криптографию.

Криптография не занимается: защитой от обмана, подкупа или шантажа законных абонентов, кражи ключей и других угроз информации, возникающих в защищенных системах передачи данных.

Шифр (от арабского sifr «ноль», откуда французское chiffre «цифра»; родственно слову «цифра») – это совокупность условных знаков (условная азбука из цифр или букв) для секретной переписки, для передачи текста секретных документов, в том числе  по техническим средствам связи. В общем случае понятие шифр идентично понятию криптосистема и означает семейство обратимых преобразований открытого текста в шифрованный. Шифр состоит, по меньшей мере, из четырех элементов:

· открытый текст X;

· функция шифрования f(X);

· ключ К;

· закрытый текст Y.

Открытый (исходный) текст – данные (текстовые или иного вида), представляемые и/или передаваемые без использования криптографии.

Шифротекст, шифрованный (закрытый) текст – данные, полученные после применения криптосистемы (обычно с некоторым указанным ключом).

Код – это алгоритм криптографических преобразований (шифрования) множества возможных открытых данных во множество возможных зашифрованных данных, и обратных им преобразований.

Ключ – это параметр криптографического алгоритма, обеспечивающий выбор одного преобразования из совокупности преобразований, возможных для этого алгоритма. В современной криптографии предполагается, что вся секретность криптографического алгоритма сосредоточена в ключе, но не деталях самого алгоритма (принцип Керкгоффса).

Шифры могут использовать один ключ для шифрования и дешифрования или два различных ключа. По этому признаку различают симметричный и асимметричный шифры.

Симметричный шифр – это шифр, который использует один ключ для шифрования и расшифровывания.

Асимметричный (несимметричный) шифр – это шифр, который для шифрования и расшифровывания использует два различных ключа, определенным образом связанных между собой.

Шифрование – процесс нормального применения криптографического преобразования открытого текста на основе алгоритма и ключа, в результате которого возникает шифрованный текст.

Расшифровывание(расшифровка) – процесс нормального применения криптографического преобразования шифрованного текста в открытый (то есть, на основе известного алгоритма и ключа).

Криптоанализ – наука, изучающая математические методы нарушения конфиденциальности и целостности информации. В то же время криптоанализ занимается  не только разработкой методов, позволяющих взламывать криптосистемы, но и  оценкой сильных и слабых сторон методов шифрования.

Криптоаналитик – человек, создающий и применяющий методы криптоанализа.

Криптография и криптоанализ составляюткриптологию как единую науку о создании и взломе шифров (такое деление привнесено с Запада, ранее в СССР и России не применялось специального деления).

Дешифрование (дешифровка) – процесс извлечения открытого текста без знания криптографического ключа на основе известного шифрованного текста. Термин «дешифрование» обычно применяют по отношению к процессу криптоанализа шифротекста. В некоторых источниках понятия дешифрования и расшифровывания объединяют вместе под термином дешифрование.

Криптографическая стойкость – способность криптографического алгоритма противостоять криптоанализу, то есть к дешифрованию без знания ключа.

Алфавит – конечное множество используемых для кодирования информации знаков. В качестве примеров алфавитов можно привести следующие:

- алфавит Z₃₃ - 32 буквы русского алфавита и пробел;

- алфавит Z₂₇ - 26 букв латинского алфавита и пробел;

- алфавит Z₂₅₆ - символы, входящие в стандартные коды ASCII и КОИ-8;

- бинарный алфавит – Z₂ = {0,1};

- восьмеричный или шестнадцатеричный алфавит.

Если указанные алфавиты используют расположение символов в соответствии с установленными правилами или стандартами для естественных языков, то их можно рассматривать как естественные алфавиты открытых текстов. Изменение порядка расположения символов может преобразовать их в специальные алфавиты шифротекстов, которые используются в некоторых алгоритмах криптографических преобразований (например, в шифрах замены).

 

Немного истории

 

История криптографии насчитывает около 4 тысяч лет. В качестве основного критерия периодизации криптографии можно использовать технологические характеристики используемых методов шифрования. В связи с этим историю криптографии можно условно разделить на четыре периода.

Первый период (приблизительно с 3-го тысячелетия до н.э. до IX в. на Ближнем Востоке и до XV в. в Европе) характеризуется господством моноалфавитных шифров (основной принцип – замена алфавита исходного текста другим алфавитом через замену букв другими буквами или символами). Хорошо известен, в частности, моноалфавитный шифр, вошедший в историю как Шифр Цезаря, получивший свое развитие в более поздние времена. В шифре Цезаря каждая буква алфавита циклически сдвигается на определенное число позиций. Величину сдвига можно рассматривать как ключ шифрования. Сам Цезарь использовал сдвиг на три позиции. Буквы исходного алфавита заменялись затем на буквы «сдвинутого» алфавита.

Интересно отметить, что уже к первому периоду относится применение простейших криптографических устройств. Первым из них считают сциталу, которую еще называют шифром Древней Спарты (рис. 2.15). Известно, что сцитала использовалась в войне Спарты против Афин в конце V в. до н.э. Сцитала представляла собой длинный стержень, на который наматывалась лента из пергамента. На ленту вдоль оси сциталы наносился текст так, что после разматывания он становился нечитаемым. Для его восстановления требовалась сцитала такого же диаметра. Считается, что автором способа взлома шифра сциталы является Аристотель, который наматывал ленту на конусообразную палку до тех пор, пока не появлялись читаемые куски текста.

 

 

 

Рис. 2.15. Внешний вид сциталы

 

С именем полководца Энея Тактика (IVв. до н.э.) связывают несколько техник шифрования и тайнописи. Диск Энея представлял собой диск диаметром 10 – 15 см с отверстиями по числу букв алфавита. Для записи сообщения нитка протягивалась через отверстия в диске, соответствующие буквам сообщения. При чтении получатель вытягивал нитку и получал буквы, правда, в обратном порядке. Хотя недоброжелатель мог прочитать сообщение, если перехватит диск, Эней предусмотрел способ быстрого уничтожения сообщения – для этого было достаточно выдернуть нить, закрепленную на катушке в центре диска.

Первым действительно криптографическим инструментом можно назвать линейку Энея, реализующую шифр замены. Вместо диска использовалась линейка с отверстиями по числу букв алфавита, катушкой и прорезью. Для шифрования нить протягивалась через прорезь и отверстие, после чего на нити завязывался очередной узел. Для расшифровывания необходимо было иметь саму нить и линейку с аналогичным расположением отверстий. Таким образом, даже зная алгоритм шифрования, но, не имея ключа (линейки), прочитать сообщение было невозможно.

Второй период (хронологические рамки – с IX в. на Ближнем Востоке и с XV в. в Европе – до начала XX в.) ознаменовался введением в обиход полиалфавитных шифров. Назовем наиболее известных криптологов, с именем которых связана разработка новых шифров. Отцом западной криптографии называют ученого эпохи Возрождения Леона Баттиста Альберти. Изучив методы вскрытия использовавшихся в Европе моноалфавитных шифров, он попытался создать шифр, который был бы устойчив к частотному криптоанализу. Трактат о новом шифре был представлен им в папскую канцелярию в 1466 г. Альберти предложил вместо единственного секретного алфавита, как в моноалфавитных шифрах, использовать два или более, переключаясь между ними по какому-либо правилу. Однако флорентийский ученый так и не смог оформить свое открытие в полную работающую систему, что было сделано уже его последователями.

Очередной известный результат принадлежит перу германского аббата Иоганна Тритемия (по некоторым источникам Иоганн Трисемус), которого многие историки считают вторым отцом современной криптологии. В пятой книге серии Polygraphia, изданной в 1518 г., он описал шифр, в котором каждая следующая буква шифруется своим собственным шифром сдвига. Однако самым известным криптографом XVI в. можно назвать Блеза де Виженера (фр. Blaise de Vigenere). В своем трактате 1585 г. он описал шифр, подобный шифру Тритемия, однако изменил систему выбора конкретного шифра замены для каждой буквы. Одной из предложенных техник было использование букв другого открытого текста для выбора ключа каждой буквы исходного текста.

Описанный шифр известен как шифр Виженера и при длине случайного ключа, равной длине открытого текста, является абсолютно стойким шифром, что было математически доказано много позже (в XX в. в работах К.Э. Шеннона). Другая техника использовала результат шифрования для выбора следующего ключа – то, что впоследствии использует Фейстель и компания IBM при разработке шифра DES в 1970-х гг.

Для рассматриваемого периода характерно развитие криптологической деятельности под эгидой государства. В России датой учреждения первой государственной шифровальной службы можно считать 1549 г. – образование «посольского приказа» с «циферным отделением». А как минимум с 1702 г. Петра I сопровождала походная посольская канцелярия под руководством первого министра Ф.А. Головина, которая с 1710 г. приобрела статус постоянного учреждения. В нем сосредоточилась криптографическая работа, связанная  с перепиской между Петром, его приближенными и различными получателями, а также по созданию новых шифров. К началу XVIII в. подобные шифровальные кабинеты были по всей Европе, в том числе Die Geheime Kabinettskanzlei в Вене, первое дешифровальное отделение в Германии под начальством графа Гронсфельда, группа Джона Валлиса в Англии и т.д.

Получила развития работа по механизации процесса шифрования-расшифровывания.

В 1790-х гг. будущий президент США Томас Джефферсон построил одну из первых механических роторных машин, упрощавшую использование полиалфавитных шифров. Среди других авторов-изобретателей стоит отметить полковника Десиуса Вадсворта, изобре­тателя машины с вращательными шифровальными дисками с различным количеством букв. Хотя он изобрел ее в 1817 г., вся слава досталась Чарлзу Уитстону за аналогичную машину, представленную на Всемирной выставке 1867 г. в Париже. Однако распространение роторные машины получили лишь в начале XX в.

Значительный толчок криптографии дало изобретение телеграфа. Необходимость закрытия передаваемых по телеграфу военных сообщений стимулировала развитие полевых шифров.

Третий период (с начала XX в. и до конца 70-х гг. XX в.) характеризуется внедрением электромеханических устройств в работу шифровальщиков. При этом продолжалось использование полиалфавитных шифров. В начале этого периода правительства разных стран вновь бросили значительные силы на шифрование и криптоанализ. В 1914 г. Британия открыла «Комнату 40», в 1917 г. США – MI-8, ставшую предшественницей совре­менного АНБ.

Во время Первой мировой войны криптография и, в особенности, криптоанализ становится одним из инструментов ведения войны. Известны факты расшифровки русских сообщений австрийцами, русскими же был расшифровыван немецкий шифр (благодаря найденной водолазами копии кодовой книги), после чего результаты были переданы союзникам. Для перехвата радиосообщений были построены специальные подслушивающие станции, в результате работы которых (вместе с умением дешифровать немецкий шифр, использовавшийся в том числе турками) русский флот был осведомлен о составе и действиях противника. В британском адмиралтействе «Комнатой 40» за время войны расшифровало около 15 тысяч сообщений. Этот результат сыграл важную роль в сражении при Доггер-банке и в Ютландском сражении.

Что касается применения для шифрования электромеханических устройств, то здесь можно назвать электрическую роторную шифровальную машину «Энигма», используемую в Германией в период 1920 – 1940 гг., главным образом, в военных целях (см. рис. 2.16), и  американскую машину М-209 на дисках. В СССР производились оба типа машин.

 

 

Рис. 2.16. Внешний вид шифровальной машины «Энигма»

 

Германские военные постоянно совершенствовали «Энигму». Без учета настройки положения колец (нем. Ringstellung) количество различных ключей составляло 10¹⁶. В конце 1920-х – начале 1930-х гг. британские разведчики считали шифр «Энигмы» невзламываемым. Только усилиями польских математиков-энтузиастов, сотрудничавших с британской разведкой, а также на основе анализа множества перехваченных сообщений, кодовых книг, донесений разведки, результатов усилий военных и даже террористических атак удалось «вскрыть» шифр «Энигмы».

Однако  с 1940 г. высшее германское командование начало использовать новый метод шифрования, названный британцами Fish. Для шифрования использовалось новое устройство Lorenz SZ 40, разработанное по заказу военных (см. рис. 2.17).

 

 

Рис. 2.17. Внешний вид шифровальной машины Lorenz SZ 40

 

Шифрование основывалось на принципе одноразового блокнота (шифр Вернама, одна из модификаций шифра Виженера, описанная в 1917 г.) и при правильном использовании гарантировало абсолютную криптостойкость (что было доказано позже в работах Шеннона). Однако для работы шифра требовался «надежный» генератор случайной последовательности, который бы синхронизировался на передающей и принимающей стороне. Если криптоаналитик сумеет предсказать следующее число, выдаваемое генератором, он сможет расшифровать текст. Дешифровать сообщения Lorenz SZ 40 американцам удалось в 1943 г. на основе использования одной из первых программируемых вычислительных машин Colossus, созданной Максом Ньюменом и Томми Флауэрсом при участии Алана Тьюринга. Colossus осуществил криптоанализ на основе переборавсех возможные вариантов исходного сообщения.

Четвертый период (с конца 70-х гг. XX в. по настоящее время) характеризуется переходом к математической криптографии. В работе К.Э. Шеннона появляются строгие математические определения количества информации, передачи данных, энтропии, функ­ций шифрования. Обязательным этапом создания шифра считается изучение его уязвимости к различным известным атакам – линейному и дифференциальному криптоанализу. Однако до 1975 г. криптография оставалась «классической», или же, более корректно, криптографией с секретным ключом.

Современный период развития криптографии отличается появлением и развитием нового направления – криптографии с открытым ключом. Ее появление знаменуется не только новыми техническими возможностями, но и сравнительно широким распространением криптографии для использования частными лицами (в предыдущие эпохи использование криптографии было исключительной прерогативой государства). Правовое регулирование использования криптографии частными лицами в разных странах сильно различается – от разрешения до полного запрета. В нашей стране деятельность в данной области является лицензируемой.

Современная криптография образует отдельное научное направление на стыке математики, информатики, физики – работы в этой области публикуются в научных журналах, организуются регулярные конференции. Практическое применение криптографии стало неотъемлемой частью жизни современного общества – ее используют в таких отраслях, как электронная коммерция, электронный документооборот (включая электронные подписи), телекоммуникации и др. Кроме очевидных применений – собственно, для передачи информации, она используется в сотовой связи, платном цифровом телевидении при подключении к Wi - Fi и на транспорте для защиты билетов от подделок, и в банковских операциях, и даже для защиты электронной почты от спама.

Технологической основой современной криптографии и криптоанализа является программно-аппаратный комплекс информационно-технологической инфраструктуры.

Еще одна особенность современного периода – открытое формирование государственных стандартов на криптографические протоколы и криптографические алгоритмы.

 

Шифр Цезаря.

Историческим примером шифра замены является шифр Цезаря (I век до н.э.), описанный историком Древнего Рима Светонием. Гай Юлий Цезарь использовал в своей переписке шифр собственного изобретения. Применительно к современному русскому языку он состоял в следующем. Выписывался алфавит: А, Б, В, Г, Д, Е,...; затем под ним выписывался тот же алфавит, но со сдвигом на 3 буквы влево (табл. 2.5). Можно сказать, что осуществился переход к специальному алфавиту, на котором будет записываться шифротекст.

 

Таблица 2.5

 

Подстановки по шифру Цезаря для алфавита русского языка

Обратите внимание на то, что алфавит считается “циклическим”, поэтому после Я идет А. При шифровке буква А заменялась буквой Г, Б заменялась на Д, В – на Е и т.д. Так, например, слово “РИМ” превращалось в слово “УЛП”. Получатель сообщения “УЛП” искал эти буквы в нижней строке и по буквам над ними восстанавливал исходное слово “РИМ”. Ключом в шифре Цезаря является величина сдвига 3 алфавита открытого текста. Преемник Юлия Цезаря – цезарь Август – использовал тот же шифр, но с ключом-сдвигом 4. Слово “РИМ” он в этом случае зашифровал бы в буквосочетание “ФМР”.

Итак, смещение K=3 или K=4 можно рассматривать как ключ шифра.

В таблице 2.6 показаны подстановки, соответствующие шифру Цезаря для латинского алфавита. Английская фраза (открытый текст) meet me after the toga party после шифрования примет следующий вид (шифрованный текст): PHHW PH DIWHU WKH WRJD SDUMB.

Послание Цезаря «VENI VIDI VICI» в переводе на русский язык означающее «Пришел. Увидел. Победил», направленное его другу Аминтию после победы над понтийским царем Фернаком, сыном Митридата, выглядело бы в зашифрованном виде так: YHQL YLGL YLFL.

 

Таблица 2.6

 

Подстановки по шифру Цезаря для латинского алфавита

 

A—> D	J—> M	S—> V
В —> Е	К —> N	Т —> W
С —> F	L—> O	U—> X
D —> G	M—> P	V—> Y
E —> H	N—> O	W—> Z
F —> I	O—> R	X —> А
G —> J	P—> S	Y—> B
H —> K	Q —> Т	Z—> C
I —> L	R—> U

 

Если каждой букве назначить числовой эквивалент (а = 1, b = 2 и т.д.), то алгоритм шифрования по Цезарю применительно к латинскому алфавиту можно выразить следующей формулой, которая показывает, каким образом каждая буква открытого текста p заменяется буквой шифрованного текста C:

С = Е(p) = (p + 3) mod(26).

Введем понятие обобщенного алгоритма (шифра) Цезаря, сдвиг K исходного алфавита в котором возможен на любую величину, но не больше, чем количество букв в применяемом алфавите минус 1. Для латинского алфавита обобщенный алгоритм Цезаря записывается формулой:

 

С = Е(р) = (р + K) mod(26),

 

где K принимает значения в диапазоне от 1 до 25. Алгоритм расшифровывания также прост:

p = D(С) = (С – K)mod(26)

Достоинством системы шифрования Цезаря является простота шифрования и расшифровывания. К недостаткам системы Цезаря следует отнести:

—   подстановки, выполняемые в соответствии с системой Цезаря, не маскируют частот появления различных букв исходного открытого текста;

— сохраняется алфавитный порядок в последовательности заменяющих букв; при изменении значения К изменяются только начальные позиции такой последовательности;

— число возможных ключей К мало;

— шифр Цезаря легко вскрывается на основе анализа частот появления букв в шифротексте и даже на основе простого перебора вариантов.

Две практические задачи криптоанализа: доказательство слабой криптографической стойкости алгоритма Цезаря и шифров моноалфавитной подстановки.

Если известно, что определенный текст был шифрован с помощью шифра Цезаря, то с помощью простого перебора всех вариантов раскрыть шифр очень просто – для этого достаточно проверить 25 возможных вариантов ключей. На рис. 2.19 показаны результаты применения этой стратегии к указанному выше первому сообщению. В данном случае открытый текст распознается в третьей строке.

Применение метода последовательного перебора всех возможных вариантов оправдано следующими тремя важными характеристиками данного шифра.

1. Известны алгоритмы шифрования и дешифрования.

2. Необходимо перебрать всего 25 вариантов.

3. Язык открытого текста известен и легко узнаваем.

В большинстве случаев, когда речь идет о защите сетей, можно предполагать, что алгоритм известен. Единственное, что делает криптоанализ на основе метода последовательного перебора практически бесполезным – это применение алгоритма, для которого требуется перебрать слишком много ключей. Например, алгоритм DES, использующий 56-битовые ключи, требует при последовательном переборе рассмотреть пространство из 2⁵⁶, или более чем 7х10¹⁶ ключей.

Третья характеристика также важна. Если язык, на котором написан открытый текст, неизвестен, то расшифровыванный текст можно не распознать. Более того, исходный текст может состоять из сокращений или быть каким-либо образом сжат – это также затрудняет распознавание.

Рассмотрим теперь более простую возможность повысить криптостойкость шифров моноалфавитной подстановки. Если в латинском алфавите шифротекста допустить использование любой из перестановок 26 символов алфавита, то мы получим 26!, или более чем 4х10²⁶ возможных ключей (ключ в данном случае – применяемый для записи шифротекста алфавит, полученный на основе перестановок символов обычного алфавита, а данный подход можно охарактеризовать как наивысший уровень развития идеи «шифра Цезаря»). Это на 10 порядков больше, чем размер пространства ключей DES, и это кажется достаточным для того, чтобы сделать невозможным успешное применение криптоанализа на основе метода последовательного перебора.

 

Рис. 2.19. Криптоанализ шифра Цезаря методом перебора всех вариантов ключей

Однако для криптоаналитика существует и другая линия атаки. Если криптоаналитик имеет представление о природе открытого текста (например, о том, что это несжатый текст на английском языке), можно использовать известную информацию о характерных признаках, присущих текстам на соответствующем языке. Чтобы показать, как этот подход применяется на практике, рассмотрим небольшой пример. Допустим, нам требуется расшифровать следующий шифрованный текст:

UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ

VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX

EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ

На первом этапе можно определить относительную частоту появления в тексте различных букв и сравнить их со среднестатистическими данными для букв английского языка (рис. 2.20).

Рис. 2.20. Относительная частота появления букв в английском тексте

Если сообщение достаточно длинное, этой методики уже может быть достаточно для распознавания текста, но в нашем случае, когда сообщение небольшое, точного соответствия ожидать не приходится. В нашем случае относительная частота вхождения букв в шифрованном тексте (в процентах) оказывается следующей:

 

Сравнивая эти результаты с данными, показанными на рис. 2.20, можно заключить, что, скорее всего, буквы Р и Z шифрованного текста являются эквивалентами букв е и t открытого текста, хотя трудно сказать, какой именно букве – Р или Z – соответствует е, а какой – t. Буквы S, U, О, М и Н, обладающие относительно высокой частотой появления в тексте, скорее всего, соответствуют буквам из множества {г, n, i, о, а, s}. Буквы с низкой частотой появления (а именно А, В, G, Y, I, J), по-видимому, соответствуют буквам множества {w, v, b, k, x, q, j, z}.

Дальше можно пойти несколькими путями. Можно, например, принять какие-то предположения о соответствиях и на их основе попытаться восстановить открытый текст, чтобы увидеть, выглядит ли такой текст похожим на что-либо осмысленное. Более систематизированный подход заключается в продолжении поиска в тексте новых характерных закономерностей. Например, может быть известно, что в рассматриваемом тексте обязательно должны присутствовать некоторые слова. Или же можно искать повторяющиеся последовательности букв шифрованного текста и пытаться определить их эквиваленты в открытом тексте.

Один из очень эффективных методов заключается в подсчете частоты использования комбинаций, состоящих из двух букв. Такие комбинации называют биграммами. Для значений относительной частоты появления в тексте биграмм тоже можно построить гистограмму, подобную показанной на рис. 2.20. Известно, что в английском языке самой распространенной является биграмма th. В нашем шифрованном тексте чаще всего (три раза) встречается комбинация ZW. Поэтому можно предположить, что Z соответствует t а W – h. Тогда из ранее сформулированной гипотезы вытекает, что Р соответствует е. Заметим, что в шифрованном тексте буквосочетание ZWP имеется, и теперь мы можем представить его как the. В английском языке the является самой распространенной триграммой (т.е. комбинацией из трех букв), поэтому можно надеяться, что мы движемся в правильном направлении.

Теперь обратите внимание на комбинацию ZWSZ в первой строке. Конечно, мы не можем сказать с полной уверенностью, что эти буквы принадлежат одному и тому же слову, но, если предположить, что это так, они соответствуют слову thSt. Отсюда заключаем, что букве S соответствует а.

Теперь мы имеем следующий результат:

Выяснив значение всего лишь четырех букв, мы расшифровали уже значительную часть сообщения. Продолжая анализ частоты появления букв, а также применяя метод проб и ошибок, остается проделать совсем немного работы, чтобы получить окончательный ответ. Расшифровыванный исходный текст (с добавленными в него пробелами) имеет следующий вид:

it was disclosed yesterday that several informal but direct contacts have been made with political representatives of the viet cong in Moscow /вчера стало известно, что в Москве состоялся ряд неофициальных, но прямых контактов с политическими представителями вьетконга/

 

 

Применение перестановок

Все рассмотренные выше методы основывались на замещении по определенным правилам символов открытого текста на естественном языке различными символами специального алфавита (алфавитов), предназначенных для записи шифрованного текста. Принципиально иной класс преобразований строится на использовании перестановок букв открытого текста. Шифры, созданные с помощью перестановок, называют перестановочными шифрами.

Шифр «Лесенка». Простейший из перестановочных шифров использует преобразование “лесенки”, заключающееся в том, что открытый текст записывается вдоль наклонных строк определенной длины («ступенек»), а затем считывается построчно по горизонтали. Например, чтобы шифровать сообщение «meet me after the toga party» /встретьте меня после вечеринки в тогах/ по методу лесенки со ступеньками длиной 2 символа, запишем это сообщение в виде:

Шифрованное сообщение будет иметь следующий вид:

MEMATRHTGPRYETEFETEOAAT

Количество ступенек в «лесенке» рассматривается как ключ шифра. Такой шифр особой сложности для криптоанализа не представляет. Дешифровка может быть осуществлена на основе перебора вариантов количества ступенек в «лесенке».

При расшифровке необходимо определить количество символов в зашифрованной строке и разделить шифрованный текст на равные части в соответствии со значением ключа (количества ступенек в «лесенке»). Первая часть образует первую строку лесенки, вторая часть – вторую и т.д. Дальнейшая расшифровка не представляет труда. При делении с остатком необходимо иметь в виду, что последняя «лесенка» будет «не достроена» за счет нижних ступенек, что характерно для приведенного простого примера.

Шифр вертикальной перестановки. Более сложная схема предполагает запись текста сообщения в горизонтальные строки одинаковой длины и последующее считывание текста столбец за столбцом, но не по порядку, а в соответствии с некоторой перестановкой столбцов. Порядок считывания столбцов при этом становится ключом алгоритма. Рассмотрим пример шифрования следующей фразы: attack postponed until two am /атака отложена до двух ночи/. Первоначально фраза записывается построчно с помощью матрицы размером 4×7, затем с использованием ключа преобразуется в шифротекст:

Буквы x, y, z используются в данном случае как буквы-заполнители.

Простой перестановочный шрифт очень легко распознать, так как буквы в нем встречаются с той же частотой, что и в открытом тексте. Например, для только что рассмотренного способа шифрования с перестановкой столбцов анализ шифра выполнить достаточно просто – необходимо записать шифрованный текст в виде матрицы и перебрать возможные варианты перестановок для столбцов. Можно использовать также таблицы значений частоты биграмм и триграмм.

Перестановочный шифр можно сделать существенно более защищенным, выполнив шифрование с использованием перестановок несколько раз. Оказывается, что в этом случае примененную для шифрования перестановку воссоздать уже не так просто. Например, если предыдущее сообщение шифровать еще раз с помощью того же самого алгоритма, то результат будет следующим:

Чтобы нагляднее представить то, что мы получим в итоге повторного применения перестановки, сопоставим каждую букву исходного открытого текста с номером соответствующей ей позиции. Наше сообщение состоит из 28 букв, и исходной последовательностью будет последовательность:

После первой перестановки получим последовательность, которая все еще сохраняет некоторую регулярность структуры.

После второй перестановки получается следующая последовательность.

Регулярность этой последовательности уже совсем не просматривается, поэтому ее криптоанализ потребует значительно больше усилий.

Если известен ключ, расшифровка весьма проста и не требует пояснений.

Применение магических квадратов. В средние века для шифрования перестановкой применялись и магические квадраты. Магическими квадратами называют квадратные таблицы с вписанными в их клетки последовательными натуральными числами, начиная от 1, которые дают в сумме по каждому столбцу, каждой строке и каждой диагонали одно и то же число.

Шифруемый текст вписывали в магические квадраты в соответствии с нумерацией их клеток (первая буква записывалась в клетку под номером 1, вторая – в клетку под номером 2 и т.д.). Если затем выписать содержимое такой таблицы по строкам, то получится шифротекст, сформированный благодаря перестановке букв исходного сообщения. В те времена считалось, что созданные с помощью магических квадратов шифротексты охраняет не только ключ, но и магическая сила.

Пример магического квадрата и его заполнения сообщением ПРИЛЕТАЮ ВОСЬМОГО показан на рис. 2.24.

Рис. 2.24. Пример магического квадрата 4x4 и его заполнения сообщением ПРИЛЕТАЮ ВОСЬМОГО

Шифротекст, получаемый при считывании содержимого правой таблицы по строкам, имеет вполне загадочный вид:

ОИРМ ЕОСЮ ВТАЬ ЛГОП

Число магических квадратов быстро возрастает с увеличением размера квадрата. Существует только один магический квадрат размером 3x3 (если не учитывать его повороты). Количество возможных магических квадратов 4x4 составляет уже 880, а количество магических квадратов 5x5 – около 250 000. В связи с этим магические квадраты средних и больших размеров могли служить хорошей базой для обеспечения нужд шифрования того времени, поскольку практически нереально выполнить вручную перебор всех вариантов для такого шифра в целях его дешифровки.

Что касается расшифровки, то она при наличии ключа (то есть магического квадрата) чрезвычайно проста.

Метод  гаммирования

Современный метод гаммирования базируется на методе одноразового блокнота Джозефа Моборна, который нами уже рассматривался. В годы Второй мировой войны этот метод был действительно труднореализуем, однако в условиях применения современных информационных технологий метод гаммирования стал одним из самых распространенных. Данный метод относится к категории методов замены (подстановки), но обычно его рассматривают отдельно.

Процесс шифрования заключается в данном случае в генерации гаммы шифра и наложении этой гаммы на исходный открытый текст. Наиболее часто на практике применяется двоичное гаммирование. В этом случае символы текста и гаммы представляются в двоичных кодах, а затем каждая пара двоичных разрядов складывается по модулю 2[7]. При необходимости двоичные коды можно преобразовать в обычный текст.

Процедура гаммирования на передаче и приеме представлена на рис. 2.25. При расшифровывании операция проводится повторно, в результате получается открытый текст. Символы текста и гаммы здесь также представляются первоначально в двоичных кодах.

Соответствие между буквенно-цифровыми символами и их двоичными кодами регулируется различными стандартами. В таблице 2.10 представлены коды буквенных символов русского языка в стандарте Windows 1251 и их двоичное представление. Этот стандарт представляет собой расширение стандарта ASCII для символов русского языка. В таблице 2.11 представлено кодирование латинских букв и некоторых других символ