Рис. №3

 

2. Многоалфавитные подстановки

 

    Полиалфавитные  подстановочные шифры были изобретены Лином Баттистой (Lean Battista) в 1568 году. Основная идея многоалфавитных систем состоит в том, что на протяжении всего текста одна и та же буква может быть зашифрована по-разному. Т.е. замены для буквы выбираются из многих алфавитов в зависимости от положения в тексте. Это является хорошей защитой от простого подсчета частот, так как не существует единой маскировки для каждой буквы в криптотексте. В данных шифрах используются множественные однобуквенные ключи, каждый из которых используется для шифрования одного символа открытого текста. Первым ключом шифруется первый символ открытого текста, вторым – второй, и т.д. После использования всех ключей они повторяются циклически. 

Шифр  Вернама

    Шифр  Вернама, или одноразовый блокнот, был изобретен в 1917 году Мейджором  Джозефом Моборном (Major Joseph Mauborn) и Гильбертом Вернамом (Gilbert Vernam) из AT&T (American Telephone & Telegraph). В классическом понимании одноразовый блокнот является большой неповторяющейся последовательностью символов ключа, распределенных случайным образом. Первоначально это была одноразовая лента для телетайпов. Отправитель использовал каждый символ ключа для шифрования только одного символа открытого текста. Шифрование представляет собой сложение по модулю n (мощность алфавита) символа открытого текста и символа ключа из одноразового блокнота.

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

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

Рис. №4

    Главным недостатком данной системы является то, что для каждого бита переданной информации должен быть заранее подготовлен  бит ключевой информации, причем эти биты должны быть случайными. При шифровании большого объема данных это является серьезным ограничением. Поэтому данная система используется только для передачи сообщений наивысшей секретности. По слухам "горячая линия" между США и СССР шифровалась с помощью одноразового блокнота. Многие сообщения советских шпионов были зашифрованы с использованием одноразовых блокнотов. Эти сообщения нераскрыты сегодня, и не будут раскрыты никогда (если не найдется способа вернуться в прошлое и достать эти блокноты):

Рис. №5

Чтобы обойти проблему предварительной передачи секретного ключа большого объема, инженеры и изобретатели придумали  много остроумных схем генерации  очень длинных потоков псевдослучайных  цифр из нескольких коротких потоков  в соответствии с некоторым алгоритмом. Получателя шифрованного сообщения при этом необходимо снабдить точно таким же генератором, как и у отправителя. Но такие алгоритмы добавляющих регулярности в шифротекст, обнаружение которых может помочь аналитику дешифровать сообщение. Один из основных методов построения подобных генераторов заключается в использовании двух или более битовых лент, считанные с которых данные побитно складываются для получения "смешанного" потока. Например, простая одноразовая лента может быть заменена двумя циклическими лентами, длины которых являются простыми или взаимно простыми числами. Так как в этом случае длины лент не имеют общих множителей, полученный из них поток имеет период повторения, равный произведению их длин: две ленты, имеющие длину 1000 и 1001 соответственно, дают в результате составной поток с периодом 1000x1001=1001000 цифр. Ленты циркулируют через сумматор, который складывает по модулю два считанные с них цифры. Выход сумматора служит ключом, используемым для зашифрования сообщения. Поэтому важно, чтобы составной поток превышал по длине все вместе взятые сообщения, которые могут быть переданы за разумный период времени.

Поскольку побитовый сумматор является линейным устройством, он изначально криптографически слаб, но может быть усилен большим количеством различных способов. Другой способ - указание местонахождения ключа как места в книге, например, Дональд Э. Кнут Искусство Программирования Том 2. Получисленные алгоритмы. Третье издание. стр. 83, 3-й абзац. Все символы, входящие в алфавит, начиная с этого места, используются как одноразовый ключ для какого-либо сообщения. Но в данном случае ключ не будет случайным и может быть использована информация о частотах распределения букв.

    Как не удивительно, но класс шифров Вернама - единственный класс шифров, для которого может быть доказана (и была доказана Шенноном) невскрываемость в абсолютном смысле этого термина.

Шифр  Виженера

    Одной из старейших и наиболее известных  многоалфавитных криптосистем является система Виженера, названная в честь французского криптографа Блейза Виженера(Vigenere), в М.Н.Аршинов, Л.Е.Садовский Коды и математика данный шифр назван шифром Тритемиуса. Этот метод был впервые опубликован в 1586 году. В данном шифре ключ задается набором из d букв. Такие наборы подписываются с повторением под сообщением, а, затем, полученную последовательность складывают с открытым текстом по модулю n(мощность алфавита). Т.е. получается следующая формула:

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

    Таблица №3

    В частном случае, при d=1, получаем шифр Цезаря.

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

      

    Таблица №4

    Формулой  преобразования будет:

 

     В обоих случаях обратная подстановка  легко определяется из квадрата, или  по формулам

соответственно.

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

Оно имеет уравнение

,

где ki + li + ... + si вообще говоря, имеют различные  периоды dk, dl, ..., ds соответственно. Период их суммы ki + li + ... + si будет наименьшим общим кратным отдельных периодов.

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

Шифр  Виженера с перемешанным один раз алфавитом

    Такой шифр представляет собой простую  подстановку с последующим применением  шифра Виженера:

 

Шифр c автоключом

    Дальнейшей  модификацией системы Виженера является система шифров с автоключом (auto-key), приписываемая математику XVI в. Дж. Кардано, AUTOCLAVE. Шифрование начинается с помощью "первичного ключа" (который является настоящим ключом в нашем смысле) и продолжается с помощью сообщения или криптограммы, смещенной на длину первичного ключа, затем производится сложение по модулю, равному мощности алфавита. Например:

 

Рис. №6

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

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

Методы  анализа многоалфавитных  систем

    Если  ключ повторяется периодически и  период известен, то криптоанализ данных систем может быть сведен к криптоанализу  одноалфавитных систем. Пусть период равен 5. Буквы упорядочиваются по столбцам следующим образом:

    Два появления одной буквы в одном  столбце представляют одну букву  сообщения. Поэтому можно расшифровать каждый столбец простым подсчетом  частот. 

Метод Казиски

    Примерно  в 1860г. немецким криптоаналитиком Ф.У.Казиски (Kasisky) был изобретен метод вскрытия систем с неизвестным периодом с помощью обнаружения одинаковых слов в криптотексте. Допустим, слово ЫВАП появляется дважды с 13 буквами между двумя появлениями. Это может быть случайно, а может означать тот факт, что одинаковая часть сообщения зашифрована начиная с той же позиции ключа. Тогда расстояние между двумя Ы равно 16 и кратно длине ключа. поэтому возможная длина ключа равна 2, 4, 8, 16. Когда получается несколько таких предположений о длине ключа, некоторые из которых могут оказаться неправильными, то можно будет сделать верное предположение о длине ключа. Более длинные повторяющиеся слова предпочтительнее. Также преимуществом для криптоаналитика является повторение слов более одного раза.

 

Криптоанализ  систем с автоключом

    Криптоанализ  измененной системы AUTOCLAVE проще, чем  для первоначальной. Аналитику достаточно только угадать или найти длину  ключа d. Тогда он может взять первую и d+1 буквы из криптотекста. Тогда, по построению, для d+1 буквы ключом является первая, следовательно, из квадрата Виженера можно определить букву, стоящую на d+1 месте в открытом тексте. Подобным образом может быть раскрыт весь текст сообщения, кроме первых d букв. Первая версия данной системы, где ключом служит сдвиг исходного сообщения, неуязвима против такой простой криптоатаки.

    Для раскрытия первой версии AUTOCLAVE может  быть использован метод Казиски. Пусть слово ИЛИ появляется дважды в исходном сообщении и расстояние между этими появлениями равно  удвоенному смещению. Тогда найдется последовательность из трех букв, например КАН, расположенная посредине между появлениями ИЛИ. Таким образом, имеется следующая часть исходного сообщения: ... ИЛИ ... КАН ... ИЛИ ...

    В процессе шифрования получаем:

Рис. №7

    Таким образом, ЬЛЩ появляется дважды в криптотексте и расстояние между ними в точности равно периоду, в то время как для системы Виженера данный метод давал числа лишь кратные периоду. После того, как смещение известно, ключевое слово находится с помощью исчерпывающего поиска, основанного на подсчете частот индивидуальных букв. При получении ключевого слова все становится очевидным. Имеется n возможных набором для первой буквы ключевого слова. Когда этот выбор произведен, из него определяется первая буква сообщения, которая в свою очередь, определяет d+1, и так далее. Поэтому выбор первой буквы дает 1, d+1, 2d+1, ... буквы сообщения. Варианты, приводящие к последовательностям невозможных распределений, могут быть отброшены. Таки способом находится первая буква. Остальные d-1 букв определяются аналогично.

 

Глава 2. Программная реализация многоалфавитной подстановки

 

Текст программы

#include <iostream>

#include <conio>

#include <windows.h> //для возможности работы с  русским текстом

#include <string>

#include <cstdlib>

#include <math>