uzluga.ru
добавить свой файл
Математическая модель шифра


Используя терминологию, принятую в [Алф01], под шифром мы понимаем любой симметричный шифр однозначной замены, алфавитом которого служит множество шифрвеличин. Это множество адаптировано к способу шифрования. Им может быть, например, множество отдельных знаков исходного алфавита, -грамм, или другое конечное множество слов.

Шифрвеличины, составляющие открытый текст, поочередно шифруются одной из “простых замен”, составляющих данный шифр замены. Выбор той или иной “простой замены” осуществляется с помощью ключевого потока (или, в терминологии [Алф01], распределителя), представляющего собой последовательность номеров “простых замен”. Ключевой поток может получаться случайным образом, например, с помощью рандомизатора типа игровой рулетки. Такой шифр мы будем называть шифром с неограниченным ключом. Ключами шифра служат всевозможные ключевые потоки. Шифр с неограниченным ключом полностью определяется своим действием на множестве шифрвеличин и рандомизатором. Ключевой поток может также функционально зависеть от ключа шифра и вычисляться детерминированно (по некоторому алгоритму или программе). Число возможных ключевых потоков фиксированной длины не превосходит в этом случае числа ключей шифра. Такой шифр мы будем называть шифром с ограниченным ключом. Подавляющее большинство шифров, используемых на практике, являются именно шифрами с ограниченным ключом. Ключевым потоком для них служит, как правило, выходная последовательность некоторого автономного автомата, множество внутренних состояний которого совпадает с множеством ключей шифра.

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

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





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




Пусть





Через обозначим отображение такое что для любого По определению





Определение 2.1.1. Опорным шифром шифра замены назовем совокупность


(2.1.1)


объектов, в которой и множества шифрвеличин и шифробозначений, множество ключей, и множество правил зашифрования, множество правил расшифрования.


Определение 2.1.2. -й степенью опорного шифра назовем совокупность объектов


(2.1.2)


в которой декартовы степени множеств соответственно; множество состоит из отображений





таких что для и





множество состоит из отображений





таких что для и





При шифр совпадает с шифром

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

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

Если нужно случайно выбрать один из двух вариантов, то достаточно подбросить монету. Исход бросания (“орел” или “решка”) укажет случайный выбор. Аналогично можно поступить для случайного выбора одного из вариантов достаточно подбросить монету раз подряд. Заметим, что при этом исходы бросаний образуют последовательность испытаний случайной величины принимающей значения и с вероятностями и соответственно (). Нулем мы обозначили “орел”, единицей “решку”. Обычно хотя это и не обязательно. Вместо монеты можно было использовать другой рандомизатор.

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

Заметим, что аналогичная ситуация имеет место и при выборе шифрвеличин из множества Этот выбор производится в соответствии с частотными характеристиками открытых текстов. Хорошо известно (см. [Алф01]), что такие характеристики для обычных (“читаемых”) открытых текстов далеко не равномерны. Пусть


(2.1.3)

и

(2.1.4)


выбранные априорные распределения вероятностей. Обозначим через случайные величины, принимающие значения из и в соответствии с распределениями (2.1.3) и (2.1.4). По определению случайные величины мы полагаем независимыми.

Далее нам понадобится понятие -го опорного шифра, под которым мы будем понимать совокупность





где введенные выше случайные величины, случайная величина с множеством исходов и распределением вероятностей





множества правил зашифрования и правил расшифрования, введенных определением 2.1.2. Распределение индуцируется и и вычисляется по формуле


(2.1.5)


В связи с введением понятия -го опорного шифра сделаем одно замечание.

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




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

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


(2.1.6)


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

В той же связи вместо мы рассматриваем При этом (как и для опорного шифра) полагаем


(2.1.7)


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


Определение 2.1.3. Пусть


(2.1.8)


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


(2.1.9)


при любых

Тогда шифром замены с неограниченным ключом назовем семейство

(2.1.10)


При этом совокупность (2.1.8) будем называть -м опорным шифром шифра


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

Сделаем ряд пояснений в связи с определением 2.1.3.

Может возникнуть вопрос: почему вместо семейства моделей в этом определении не рассматривать одну модель с множеством открытых текстов




множеством ключей





и множеством шифрованных текстов





Такой подход обладает, на наш взгляд, одним существенным недостатком. Дело в том, что при этом не всякий открытый текст можно зашифровать на любом ключе. В самом деле, ключ можно применять лишь к открытому тексту Поэтому мы не можем рассматривать правила зашифрования как отображения для любого Отметим, что указанная возможность предусматривается в модели шифра, предлагаемой в [Бра99]. Там в качестве правил зашифрования рассматриваются отображения


(2.1.11)


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




правила зашифрования являются отображениями типа (2.1.11) для любого

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

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

Исходными предпосылками в этом построении служат опорный шифр введенный определением 2.1.1, конечное множество ключей шифра и множество правил зашифрования





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




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

Обозначим через множество слов конечной длины в алфавите


Определение 2.1.4. Пусть


(2.1.12)


произвольное отображение, такое, что для любых и некоторых




причем




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


Подчеркнем, что в определении 2.1.4 ключевой поток однозначно определяется выбором ключа и числом

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




Пусть для





Введем распределение вероятностей так, что


(2.1.13)


Определение 2.1.5. Пусть


(2.1.14)


совокупность случайных величин правил зашифрования и расшифрования для которой распределение определяется формулой (2.1.13) и выполняется условие


(2.1.15)

при любых

Тогда шифром замены с ограниченным ключом назовем семейство


(2.1.16)

При этом совокупность (2.1.14) будем называть -м опорным шифром шифра


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

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





для любого и подходящего то получаем “слабый” шифр простой замены. Если





представляет собой периодическую последовательность (в которой

),


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

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

Пример 2.1.6. Шифр Цезаря (сдвиговый шифр).

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



таких что

(2.1.17)


и соответственно правил расшифрования




таких что

(2.1.18)


Таким образом, опорный шифр шифра Цезаря имеет вид


(2.1.19)

где





определяется формулой (2.1.17), а формулой (2.1.18).

Шифр Цезаря это шифр замены с ограниченным ключом, для которого Генератором ключевого потока для него служит отображение





такое что




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

Заметим, что для любого





и что для любого





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


Пример 2.1.7. Шифр модульного гаммирования с л.р.с. в качестве генератора.

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


Выход k1 k2 … km


Рис. 1. Линейный регистр сдвига


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

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


Пример 2.1.8. Шифр модульного гаммирования со случайной гаммой.

Опорный шифр рассматриваемого шифра тот же, что и в предыдущих примерах. Генератор ключевого потока (гаммы шифра) позаимствуем из [Неч99], это “вертушка со стрелкой” (рис. 2).

i-1

i

i+1




n-1

Рис. 2. Вертушка со стрелкой


Обод вертушки разделен на равных частей (дуг). Каждая из них помечена числами от до Запуская вертушку, получим какое-нибудь число из Для того чтобы получить ключевой поток длины нужно раз воспользоваться вертушкой. Если она “правильная”, то





для любого

Мы построили пример случайного шифра.


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


99) Отметим, что блочный шифр простой замены, например, DES не так уж и слаб.

110) См., например, [Алф01].