 |
|
Математическая модель шифра замены
Введение
Симметричные криптосистемы (также симметричное шифрование, симметричные шифры) — способ шифрования, в котором для шифрования и расшифровывания применяется один и тот же криптографический ключ. До изобретения схемы асимметричного шифрования единственным существовавшим способом являлось симметричное шифрование. Ключ алгоритма должен сохраняться в секрете обеими сторонами. Алгоритм шифрования выбирается сторонами до начала обмена сообщениями.
В настоящее время симметричные шифры — это:
· блочные шифры. Обрабатывают информацию блоками определённой длины (обычно 64, 128 бит), применяя к блоку ключ в установленном порядке, как правило, несколькими циклами перемешивания и подстановки, называемыми раундами. Результатом повторения раундов является лавинный эффект — нарастающая потеря соответствия битов между блоками открытых и зашифрованных данных.
· поточные шифры, в которых шифрование проводится над каждым битом либо байтом исходного (открытого) текста с использованием гаммирования.( Гаммирование — симметричный метод шифрования, основанный на «наложении» гамма-последовательности на открытый текст. Обычно это суммирование в каком-либо конечном поле).
Большинство симметричных шифров используют сложную комбинацию большого количества подстановок и перестановок. Многие такие шифры исполняются в несколько (иногда до 80) проходов, используя на каждом проходе «ключ прохода». Множество «ключей прохода» для всех проходов называется «расписанием ключей». Как правило, оно создается из ключа выполнением над ним неких операций, в том числе перестановок и подстановок.
Из всего многообразия симметричных шифров можно выделить три важных класса преобразования:
1. перестановки,
2. шифры замены,
3. Гаммирование.
Рассмотрим более подробно шифры замены и перестановки.
Шифры замены
Шифр замены является простейшим, наиболее популярным шифром. Типичными примерами являются шифр Цезаря, «цифирная азбука» Петра Великого и «пляшущие человечки» А. Конан Дойла. Как видно из самого названия, шифр замены осуществляет преобразование замены букв или других «частей» открытого текста на аналогичные «части» шифрованного текста. Легко дать математическое описание шифра замены. Пусть 
и 
– два алфавита (открытого и шифрованного текстов соответственно), состоящие из одинакового числа символов. Пусть также 
— взаимнооднозначное отображение в . Тогда шифр замены действует так: открытый текст 
преобразуется в шифрованный текст 
.
Математическая модель шифра замены
Определим модель 
произвольного шифра замены. Будем считать, что открытые и шифрованные тексты являются словами в алфавитах 
и 
соответственно: 
Здесь и далее 
обозначает множество слов конечной длины в алфавите 
.
Перед зашифрованием открытый текст предварительно представляется в виде последовательности подслов, называемых шифрвеличинами. При зашифровании шифрвеличины заменяются некоторыми их эквивалентами в шифртексте, которые назовем шифробозначениями. Как шифрвеличины, так и шифробозначения представляют собой слова из 
и 
соответственно.
Пусть 
— множество возможных шифрвеличин, 
— множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты 
можно было представить словами из 
и 
соответственно. Требование однозначности расшифрования влечет неравенства 
. Для определения правила зашифрования 
в общем случае нам понадобится ряд обозначений и понятие распределителя, который, по сути, и будет выбирать в каждом такте шифрования замену соответствующей шифрвеличине.
Поскольку 
, множество 
можно представить в виде объединения 
непересекающихся непустых подмножеств 
. Рассмотрим произвольное семейство, состоящее из 
таких разбиений множества :
,
и соответствующее семейство биекций
,
для которых
.
Рассмотрим также произвольное отображение
, где 
такое, что для любых 
.
.
Назовем последовательность 
распределителем, отвечающим данным значениям .
Теперь мы сможем определить правило зашифрования произвольного шифра замены. Пусть
и
.
Тогда
где 
.
В качестве 
можно выбрать любой элемент множества 
. Всякий раз при шифровании этот выбор можно производить случайно, например, с помощью некоторого рандомизатора.