Криптоанализ классических шифров (стр. 4 из 27)

Пусть U = {u₁,..,и_N} — множество возможных шифрвеличин, V = {v₁,...,v_M} — множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты х

X, y

Y можно было представить словами из U*, V * соответственно. Требование однозначности расшифрования влечет неравенства N

п, М

т, М

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

Поскольку М

N, множество V можно представить в виде объединения

непересекающихся непустых подмножеств V⁽ⁱ⁾. Рассмотрим произвольное семейство, состоящее из r таких разбиений множества V :

,

и соответствующее семейство биекций

для которых

.

Рассмотрим также произвольное отображение

где , такое, что для любых

Назовем последовательность

(к,1) распределителем, отвечающим данным значениям к K, l N.

Теперь мы сможем определить правило зашифрования произвольного шифра замены. Пусть

x

X, x = x₁...x_l, x_i U, i = 1,l; k K

и

(к,I) = а₁^(k)...а₁^(k). Тогда Е_к(х) = у, где у = у₁...у_l,

В качестве у_j можно выбрать любой элемент множества т

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

j.

Классификация шифров замены

Если ключ зашифрования совпадает с ключом расшифрования: k₃ = k_p, то такие шифры называют симметричными, если же k₃

k_р— асимметричными.

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

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

Для однозначных шифров замены справедливо свойство:

для многозначных шифров замены:

Исторически известный шифр — пропорциональной замены представляет собой пример шифра многозначной замены, шифр гаммирования - пример шифра однозначной замены. Далее мы будем заниматься в основном изучением однозначных замен, получивших наибольшее практическое применение. Итак, далее М = N и

.

Заметим, что правило зашифрования Е_kестественным образом индуцирует отображение

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

В силу инъективности (по k)отображения Е_k и того, что |U| = |V|, введенные в общем случае отображения

являются биекциями

, определенными равенствами

.

Число таких биекций не превосходит N!.

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

Введем еще ряд определений.

Если для некоторого числа q

N выполняются включения v_i

В^q, i=1,N, то соответствующий шифр замены будем называть шифром равнозначной замены. В противном случае — шифром разнозначной замены:

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

А^р, для некоторого р

N . При р = 1 говорят о поточных шифрах замены, при р > 1 — о блочных шифрах замены:

Следующее определение. В случае r= 1 шифр замены называют одноалфавитным шифром замены или шифром простой замены. В противном случае – многоалфавитным шифром замены:

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

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

Шифр Виженера

Наиболее известными являются шифры замены, или подстановки, особенностью которых является замена символов (или слов, или других частей сообщения) открытого текста соответствующими символами, принадлежащими алфавиту шифротекста. Различают одноалфавитную и многоалфавитнуюзамену. Вскрытие одноалфавитных шифров основано на учете частоты появления отдельных букв или их сочетаний (биграмм, триграмм и т. п.) в данном языке. Классические примеры вскрытия таких шифров содержатся в рассказах Э. По "Золотой жук" и А.Конан Дойля "Пляшущие человечки".

Примером многоалфавитного шифра замены является так называемая система Виженера. Шифрование осуществляется по таблице, представляющей собой квадратную матрицу размерностью п X n, где п - число символов используемого алфавита. На рис.4 показана таблица Виженера для русского языка (алфавит Z₃₂- 32 буквы и пробел). Первая строка содержит все символы алфавита. Каждая следующая строка получается из предыдущей циклическим сдвигом последней на символ влево.