Шифр Цезаря

В 1 в. н. э. Ю. Цезарь во время войны с галлами, в своей переписке заменял в сообщении первую букву латинского алфавита (А) на четвертую (D), вторую (В) – на пятую (Е), наконец, последнюю – на третью:

при зашифровании ⇓ 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

при расшифровании ⇑ 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

Пример 39. Донесение Ю. Цезаря Сенату об одержанной им победе над Понтийским царем выглядело так:

YHQL YLGL YLFL(" Veni, vidi, vici" – лат. " Пришел, увидел, победил"). ▲

Подмножество C_n = {C_k: 0 ≤ k < n} симметрической группы S(Z_n), содержащее n подстановок C_k: j→ (j + k)(mod n), 0 ≤ k < n, называется подстановкой Цезаря.

Свойства подстановки Цезаря:

· умножение коммутативно, то есть C_k ∙ C_j = C_j ∙ C_k = C_j+k;

· C₀ – единичная подстановка;

· обратной к C_к является C_k^-1 = C_n-k, где 0 < k < n.

Подстановка определяется по таблице замещения, содержащей пары соответствующих букв “исходный текст – шифрованный текст”. Для русского алфавита подстановка C₃ приведена в таблице. Стрелка (↓) означает, что буква исходного текста (в верхней строке таблицы) шифруется при помощи C₃ в букву шифрованного текста (в нижней строке).

Таблица замещения символов по системе Цезаря

Пример 40. ВЫШЛИТЕ_НОВЫЕ_УКАЗАНИЯ посpедством подстановки C₃ пpеобpазуется в ЕЮЫОЛХИВРСЕЮИВЦНГКГРЛБ. ▲

Шифр моноалфавитной замены действует как набор подстановок на множестве букв открытого текста. Поэтому такие шифры, как и подстановки, образуют группу по композиции. Это значит, что зашифрование текста сначала одним, а затем другим шифром моноалфлвитной замены эквивалентно зашифрованию этого же текста каким – то третьим шифром моноалфавитной замены. Композиция таких шифров ассоциативна, единичным элементом группы является шифр, оставляющий все буквы неподвижными. Число шифров моноалфавитной замены равно m!, где m – число букв в алфавите.

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

Аббат Тритемеус – автор первой печатной книги о тайнописи (1518г.) – предложил несколько шифров и среди них шифр, который можно считать усовершенствованием шифра Цезаря. Этот шифр устроен так. Все буквы алфавита нумеруются по порядку (от 1 до 33 в русском варианте). Затем выбирают ключевое слово и записывают его под символами исходного сообщения с повторением. Чтобы получить шифрованный текст, складывают номер очередной буквы с номером соответствующей буквы ключа. Если полученная сумма больше 33, то из нее вычитают 33. В результате получают последовательность чисел от 1 до 33. Вновь заменяя числа этой последовательности соответствующими буквами, получают шифрованный текст. Если под ключом шифра понимать однобуквенное слово “В” (в русском варианте), то мы получим шифр Цезаря.

Более эффективны обобщения подстановки Цезаря - шифр Хилла и шифр Плэйфера. Они основаны на подстановке не отдельных символов, а 2-грамм (шифр Плэйфера) или n -грамм (шифр Хилла). При более высокой криптостойкости они значительно сложнее для реализации и требуют достаточно большого количества ключевой информации.

Слабая криптостойкость моноалфавитных подстановок преодолевается с применением многоалфавитных подстановок, которые определяются ключом π = (π ₁, π ₂,...), содержащим не менее двух различных подстановок. В начале рассмотрим многоалфавитные системы подстановок с нулевым начальным смещением.

Пусть {K_i: 0 ≤ i < n} - независимые случайные переменные с одинаковым распределением вероятностей, принимающие значения на множестве Z_m:

P{(K₀, K₁,..., K_n-1) = (k₀, k₁,..., k_n-1)} = (1/m)ⁿ.

Система одноразового использования преобразует исходный текст:

X = (x₀, x₁,..., x_n-1) в шифрованный текст: Y = (y₀, y₁,..., y_n-1) при помощи подстановки Цезаря:

y_i = C_Ki(x_i) = (K_i + x_i) (mod m) i = 0, 1, …, n-1.

Для такой системы подстановки используют также термин " одноразовая лента" и " одноразовый блокнот". Пространство ключей К системы одноразовой подстановки является вектором ранга (K₀, K₁,..., K_n-1) и содержит m∙ n точек.

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