Учебное пособие: Криптоанализ классических шифров

Шифр перестановки, как видно из названия, осуществляет преобразование перестановки букв в открытом тексте. Типичным примером шифра перестановки является шифр «Сцитала». Обычно открытый текст разбивается на отрезки равной длины и каждый отрезок шифруется независимо. Пусть, например, длина отрезков равна п и σ — взаимнооднозначное отображение множества {1,2,..., п} в себя. Тогда шифр перестановки действует так: отрезок открытого текста х₁ ...х_п преобразуется в отрезок шифрованного текста

Математическая модель шифра замены

Определим модель _А =(X,K,Y,E,D) произвольного шифра замены. Будем считать, что открытые и шифрованные тексты являются словами в алфавитах А и В соответственно: XA*, YВ*, |А|=п, |В| = т . Здесь и далее С* обозначает множество слов конечной длины в алфавите С.

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

Пусть U = {u₁ ,..,и_N } — множество возможных шифрвеличин, V = {v₁ ,...,v_M } — множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты хX, yY можно было представить словами из 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 можно выбрать любой элемент множества т . Всякий раз при шифровании этот выбор можно производить случайно, например, с помощью некоторого рандомизатора типа игровой рулетки. Подчеркнем, что такая многозначность при зашифровании не препятствует расшифрованию, так как при ij.

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

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

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

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

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

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

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