2.2. Свойства элементарных шифров

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

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

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

Напомним, что число различных перестановок целых чисел равно.

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

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

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

Например, открытое сообщение КИЕВ после применения перестановки преобразуется в шифрованный текст ЕВИК. Восстановление открытого текста (расшифрование) из шифрованных сообщений осуществляется аналогичным порядком с использованием обратного преобразования : {ЕВИК}{КИЕВ}.

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

Если длина текста не кратна длине перестановки, то последний блок дополняется некоторым набором символов алфавита для получения длины кратной.

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

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

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

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

.

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

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

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

При анализе усложнений шифра перестановки используются свойства подстановок.

Подстановкой порядкана множествеизэлементов называется взаимно однозначное отображение множествана себя.

Подстановку записывают в виде двухстрочной таблицы:

.

Подстановки можно умножать по правилу: .

Множество всех подстановок порядка является группой по умноже-нию.

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

Множество всех подстановок над , будем в дальнейшем обозначать через.

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

1. Замкнутость: произведение двух постановок иявляется подстановкой:. Данное свойство в терминах шифра замены означает, что двукратное применение простой замены эквивалентно некоторой третьей замене. Т.е. стойкость шифрования от этого не увеличивается.

2. Ассоциативность: результат произведения не зависит от порядка расстановки скобок.

3. Существование единицы: постановка, определяемая как ,

является единицей относительно операции умножения:.

4. Существование обратного элемента: для любой подстановки существует единственная обратная подстановка, удовлетворяющая условию.

Взаимно обратными подстановками являются:

и .

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

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

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

1. Свойство сохранения структуры: поскольку исходный текст шифруется посимвольно, то при шифровании -граммы, у которой символы на местахравны, т.е. совпадают, будет получена-грамма, у которой символы на местахтакже равны.

2. Пусть – подстановочная матрица, соответствующая подстановке:

, где , если, иначе,.

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

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

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

Отметим один важный частный случай многоалфавитной подстановки.

Подножество подстановок сдвига

, называетсясемейством шифров Цезаря.

Упражнение: Доказать, что – коммутативная подгруппа симметрической группы. Указание: Обратной подстановкой кявляется.

Упражнение: Пусть дана подстановка Цезаря с верхней строкой (алфавитом) вида V=(АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ_).

Зашифровать сообщение (КОНТРАКТ_НА_ПОСТАВКУ) с помощью подстановки .

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

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

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

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

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

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

Гамма шифрования называется периодической, если существует некоторое такое, что.

В этом случае периодическим называется и сам шифр.

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

Весьма распространенным способом получения таких гаммовых последовательностей является применение датчиков псевдослучайных чисел.

В дальнейшем эти методы будут рассмотрены достаточно подробно.

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

Если длина гаммы шифрования равна длине открытого текста, а сама гамма – равновероятна и используется только один раз, то имеет место случай системы одноразового использования или шифра Вернама, названого по имени инженера американской компании AT&T, предложившего в 1917 году соответствующий метод шифрования.

В то время ключ записывался на бумажной ленте. Каждая буква исходного текста в латинском алфавите, расширенном некоторыми дополнительными знаками, сначала переводилась с использованием кода Бодо в пятибитовый символ. К исходному тексту в коде Бодо ключ добавлялся по модулю 2. Телетайп фирмы AT&T со считывающим устройством Вернама и оборудованием для шифрования, использовался в корпусе связи армии США.

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

Пример шифра гаммирования с ключом (ОДНОРАЗОВАЯ_ГАММА_).

Зашифруем текст (ВЫПОЛНИ_ТРАНЗАКЦИЮ) с помощью этого ключа. Шифрование удобнее производить путем сложения по модулю 33 целых чисел – номеров букв в алфавите V, пронумерованном с единицы.

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

ВЫПОЛНИ_ТРАНЗАКЦИЮ	03	28	16	15	12	14	09	33	19	17	01	14	08	01	…
ОДНОРАЗОВАЯ_ГАММА_	15	05	14	15	17	01	08	15	03	01	32	33	04	01	…
С_ЭЭЬОРОХС_НЛБЧВЙЮ	18	33	30	30	29	15	17	15	22	18	33	14	12	02	…

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

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

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

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

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

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

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