Шифрующие таблицы Трисемуса

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

Поскольку ключевое слово или фразу легко хранить в памяти, то такой подход упрощал процессы шифрования и расшифрования. Поясним этот метод шифрования на примере. Для русского алфавита шифрующая таблица может иметь размер 4х8. Выберем в качестве ключа слово БАНДЕРОЛЬ. Шифрующая таблица с таким ключом показана на рис. 8.

Рис. 1.Шифрующая таблица с ключевым словом БАНДЕРОЛЬ

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

Например, при шифровании с помощью этой таблицы сообщения

ВЫЛЕТАЕМПЯТОГО

получаем шифртекст

ПДКЗЫВЗЧШЛЫЙСЙ

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

Квадрат Полибия

В криптографии квадрат Полибия (англ. Polybius square), также известный как шахматная доска Полибия — оригинальный код простой замены, одна из древнейших систем кодирования, предложенная Полибием (греческий историк, полководец, государственный деятель, III век до н. э.). Данный вид кодирования изначально применялся для греческого алфавита[1], но затем был распространен на другие языки.

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

Шаг 1: Формирование таблицы шифрования

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

Латинский алфавит

В современном латинском алфавите 26 букв, следовательно таблица должна состоять из 5 строк и 5 столбцов, так как 25=5*5 наиболее близкое к 26 число. При этом буквы I, J не различаются (J отождествляется с буквой I), так как не хватает 1 ячейки:

Русский алфавит

Идею формирования таблицы шифрования проиллюстрируем для русского языка. Число букв в русском алфавите отличается от числа букв в греческом алфавите, поэтому размер таблицы выбран другой (квадрат 6*6=36, поскольку 36 наиболее близкое число к 33):

Возможен также другой вариант составления, предусматривающий объединение букв Е и Ё, И и Й, Ъ и Ь. В данном случае получаем следующий результат:

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

Или есть такой вариант: Шифр «Квадрат Полибия».

«Квадрат Полибия» представляет собой квадрат 5x5, столбцы и строки которого нумеруются цифрами от 1 до 5. В каждую клетку этого квадрата записывается одна буква (в нашем алфавите 31 буква, Ъ и Ё исключены, кроме того в одну клетку поместите буквы е-э, и-й, ж-з, р-с, ф-х, ш-щ). Буквы расположены в алфавитном порядке. В результате каждой букве соответствует пара чисел, и шифрованное сообщение превращается в последовательность пар чисел. Расшифровывается путем нахождения буквы, стоящей на пересечении строки и столбца.

1 2 3 4 5
1 А Б В Г Д
2 Е/Э Ж З И/Й К
3 Л М Н О П
4 Р/С Т У Ф/Х Ц
5 Ч Ш/Щ Ы Ю Я

Шаг 2: Принцип шифрования

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

Метод 1

Зашифруем слово «SOMETEXT»:

Для шифрования на квадрате находили букву текста и вставляли в шифровку нижнюю от неё в том же столбце. Если буква была в нижней строке, то брали верхнюю из того же столбца.

Таким образом после шифрования получаем:

Метод 2

Сообщение преобразуется в координаты по квадрату Полибия, координаты записываются вертикально:

Затем координаты считывают по строкам:

34 25 45 34 43 31 41 54                                                                                                              (*)

Далее координаты преобразуются в буквы по этому же квадрату:

Таким образом после шифрования получаем:

Метод 3

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

3425453443314154  

Полученная последовательность цифр сдвигается циклически влево на один шаг(нечетное количество шагов):

4254534433141543

Эта последовательность вновь разбивается в группы по два:

42 54 53 44 33 14 15 43

и по таблице заменяется на окончательный шифротекст:

Таким образом после шифрования получаем:

Добавление ключа

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

1. возможность заполнить квадрат Полибия буквами произвольно, а не только строго по алфавиту;

2. возможность периодически заменять квадраты.

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

Буквы могут вписываться в таблицу в произвольном порядке — заполнение таблицы в этом случае и является ключом. Для латинского алфавита в первую клетку можно вписать одну из 25 букв, во вторую — одну из 24, в третью — одну из 23 и т. д. Получаем максимальное количество ключей для шифра на таблице латинского алфавита:

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

Пример

Зашифруем слово «SOMETEXT», используя ключ «DRAFT». Составим предварительно таблицу шифрования с данным ключом, записывая символы ключа по порядку в таблицу, после них остальной алфавит:

Преобразуем сообщение в координаты по квадрату Полибия:

Считаем координаты по строкам:

41 43 53 35 44 32 12 51

Преобразуем координаты в буквы по этому же квадрату:

Таким образом после шифрования получаем:

Историческая справка.

Ещё в далекой древности у человека возникла необходимость передачи сигналов на расстояние. Для усиления голоса при подаче сигналов на охоте стали применять простейшие рупоры в виде рогов, раковин и др. Целями подачи служили тамтамы, барабаны и подобные им устройства, а чуть позже световые средства — факелы, костры. Даже эти примитивные предметы световой сигнализации позволили резко увеличить расстояние, на котором людям удавалось поддерживать связь.[6]

С развитием общества возникла необходимость в передаче более разнообразных сигналов, в том числе сигналов, смысл которых не был обусловлен заранее. В книге Полибия описан способ[7] применения водяных часов, так называемых клепсидр, в устройстве для дальней сигнализации. Клепсидры представляли собой сосуды с водой, на поверхности которой находились поплавки с вертикальными стойками на них. Вода из сосудов вытекала с постоянной скоростью, и длина видимой части стоек была обратно пропорциональна времени. Суть использования клепсидр для сигнализации состояла в том, что их вертикальные стойки имели однотипную разметку: вместо часовых делений на них были написаны в одинаковой последовательности различные слова, команды и т. п. По условному сигналу с передающего пункта обе клепсидры одновременно запускались, а по другому сигналу останавливались в тот момент, когда на стойках была видна надпись, которую нужно было передать. Так как клепсидры были довольно точными часами, то на передающем и на приемном пунктах они показывали один и тот же сигнал. В этом способе связи дальность определялась условиями видимости сигналов, которые могли подаваться любыми другими известными тогда сигнальными средствами.

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

Полибий описывает также и второй способ сигнализации, основанный на ином принципе, изобретение которого он связывает с именами Клеоксена и Демоклита из Александрии. По этому способу для сигнализации использовали факелы, которые выставляли на сигнальной стене. При этом существовал определенный код, составленный следующим образом. Греческий алфавит (24 буквы) разделяли на 5 групп таким образом, что каждая буква определялась номером группы и порядковым номером её в группе. Число факелов в левой части сигнальной стены означало номер группы, а число факелов в правой части стены — номер места в группе. Такой способ, хотя и требовал много времени на передачу каждого сигнала, однако давал возможность передавать буквенным текстом любое сообщение. Полибий, описывая этот способ, как раз приводил таблицу такого кода (таблица Полибия), которая рассматривается в статье, в дальнейшем нашедшую применение во многих системах сигнализации. Это, по-видимому, была одна из первых попыток использовать код (пятеричный двухразрядный) для передачи информации.

Интересно заметить, что в несколько измененном виде код Полибия дошёл до наших дней и получил интересное название «тюремный шифр». Для его применения необходимо знать лишь естественный порядок расположения букв в алфавите (как в указанных выше примерах для латинского и русского алфавитов). Число 3, например, передавалось путем трехкратного стука. При передаче буквы сперва отстукивалось число, соответствующее строке, в которой располагалась буква, а затем номер столбца. Например, буква «H» передавалась двукратным стуком (вторая строка) и затем трехкратным (третий столбец). Доподлинно известно, что декабристы, посаженные в тюрьму после неудачного восстания 1825 года, не могли установить связь с находившимся в одиночной камере Петропавловской крепости князем Одоевским. Оказалось, что он не помнил естественный порядок расположения букв в русском и французском алфавитах (другими языками он не владел). Декабристы для русского алфавита использовали прямоугольник размера 5x6 и сжатый до 30 букв алфавит. Поэтому «Тюремный шифр», строго говоря, не шифр, а способ модификации сообщения с целью его приведения к виду, удобному для передачи по каналу связи (через стенку).