Аффинная система подстановок Цезаря

В системе шифрования Цезаря использовались только ад­дитивные свойства множества целых Zm . Однако символы мно­жества Zm можно также умножать по модулю m. Применяя одно­временно операции сложения и умножения по модулю m над эле­ментами множества Zm, можно получить систему подстановок, которую называют аффинной системой подстановок Цезаря.

Определим преобразование в такой системе:

Ea,b : Zm®Zm

Ea,b : t®Ea,b(t)

Ea.b(t) = at + b (mod m), где a, b - целые числа, 0<a,b<m, НОД(а,m) = 1.

В данном преобразовании буква, соответствующая числу t, заменяется на букву, соответствующую числовому значению (at + b) по модулю m.

Следует заметить, что преобразование E_ab(t) является взаимно однозначным отображением на множестве Zm только в том случае, если наибольший общий делитель чисел а и m, обо­значаемый как НОД (а, m), равен единице, т.е. а и m должны быть взаимно простыми числами.

Например, пусть m = 26, а = 3, b = 5. Тогда, очевидно,
НОД (3,26) = 1, и мы получаем следующее соответствие между
числовыми кодами букв: .

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

Исходное сообщение НОРЕ преобразуется в шифртекст AVYR

Достоинством аффинной системы является удобное управление ключами - ключи шифрования и расшифрования представляются в компактной форме в виде пары чисел (а, Ь). Недостатки аффинной системы аналогичны недостаткам системы шифрования Цезаря.

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

Система Цезаря с ключевым словом

Система шифрования Цезаря с ключевым словом являет­ся одноалфавитной системой подстановки. Особенностью этой системы является использование ключевого слова для смещения и изменения порядка символов в алфавите подстановки .

Выберем некоторое число k, 0 < k < 25 , и слово или корот­кую фразу в качестве ключевого слова. Желательно, чтобы все буквы ключевого слова были различными. Пусть выбраны слово DIPLOMAT в качестве ключевого слова и число k = 5.

Ключевое слово записывается под буквами алфавита, на­чиная с буквы, числовой код которой совпадает с выбранным числом k:

0 1 2 3 4 5 10 15 20 25

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Оставшиеся буквы алфавита подстановки записываются после ключевого слова в алфавитном порядке:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

V W X Y Z D I P L O M A T B C E F G H J K N Q R S U

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

Исходное сообщение SEND MORE MONEY

шифруется как HZBY TCGZ TCBZS

Требование о различии всех букв ключевого слова не обязательно. Можно просто записать ключевое слово (или фразу) без повторения одинаковых букв. Напри­мер, ключевая фраза

КАК ДЫМ ОТЕЧЕСТВА НАМ СЛАДОК И ПРИЯТЕН и число k = 3 порождают следующую таблицу подстановок:

0 3

А Б ВГ Д ЕЖ З ИЙКЛ МНОПРСТУ ФХЦЧШЩЬЫЪЭЮЯ

ЪЭЮКА ДЫМОТЕ Ч СВНЛИП РЯ БГЖЗЙ У Ф X ЦШЩ Ь

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

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

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

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

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

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

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

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

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

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

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