Пусть U = {u1,..,иN} — множество возможных шифрвеличин, V = {v1,...,vM} — множество возможных шифробозначений. Эти множества должны быть такими, чтобы любые тексты х
Поскольку М
и соответствующее семейство биекций
для которых
Рассмотрим также произвольное отображение
Назовем последовательность
Теперь мы сможем определить правило зашифрования произвольного шифра замены. Пусть
x
и
В качестве уj можно выбрать любой элемент множества т
Классификация шифров замены
Если ключ зашифрования совпадает с ключом расшифрования: k3 = kp, то такие шифры называют симметричными, если же k3
В связи с указанным различием в использовании ключей сделаем еще один шаг в классификации:
Отметим также, что в приведенном определении правило зашифрования Еk(х) является, вообще говоря, многозначной функцией. Выбор ее значений представляет собой некоторую проблему, которая делает многозначные функции Еk(х) не слишком удобными для использования. Избавиться от этой проблемы позволяет использование однозначных функций, что приводит к естественному разделению всех шифров замены на однозначные и многозначные замены (называемых также в литературе омофонами).
Для однозначных шифров замены справедливо свойство:
для многозначных шифров замены:
Исторически известный шифр — пропорциональной замены представляет собой пример шифра многозначной замены, шифр гаммирования - пример шифра однозначной замены. Далее мы будем заниматься в основном изучением однозначных замен, получивших наибольшее практическое применение. Итак, далее М = N и
Заметим, что правило зашифрования Еkестественным образом индуцирует отображение
В силу инъективности (по k)отображения Еk и того, что |U| = |V|, введенные в общем случае отображения
Число таких биекций не превосходит N!.
Для шифра однозначной замены определение правила зашифрования можно уточнить: в формуле включение следует заменить равенством
Введем еще ряд определений.
Если для некоторого числа q
В подавляющем большинстве случаев используются шифры замены, для которых U
Следующее определение. В случае r= 1 шифр замены называют одноалфавитным шифром замены или шифром простой замены. В противном случае – многоалфавитным шифром замены:
Ограничиваясь наиболее важными классами шифров замены и исторически известными классами шифров перестановки, сведем результаты классификации в схему, изображенную на рисунке.
Следует подчеркнуть, что стрелки, выходящие из любого прямоугольника схемы, указывают лишь на наиболее значимые частные подклассы шифров. Пунктирные стрелки, ведущие из подклассов шифров перестановки, означают, что эти шифры можно рассматривать и как блочные шифры замены в соответствии с тем, что открытый текст делится при шифровании на блоки фиксированной длины, в каждом из которых производится некоторая перестановка букв. Одноалфавитные и многоалфавитные шифры могут быть как поточными, так и блочными. В то же время шифры гаммирования, образующие подкласс многоалфавитных шифров, относятся к поточным, а не к блочным шифрам. Кроме того, они являются симметричными, а не асимметричными шифрами.
Шифр Виженера
Наиболее известными являются шифры замены, или подстановки, особенностью которых является замена символов (или слов, или других частей сообщения) открытого текста соответствующими символами, принадлежащими алфавиту шифротекста. Различают одноалфавитную и многоалфавитнуюзамену. Вскрытие одноалфавитных шифров основано на учете частоты появления отдельных букв или их сочетаний (биграмм, триграмм и т. п.) в данном языке. Классические примеры вскрытия таких шифров содержатся в рассказах Э. По "Золотой жук" и А.Конан Дойля "Пляшущие человечки".
Примером многоалфавитного шифра замены является так называемая система Виженера. Шифрование осуществляется по таблице, представляющей собой квадратную матрицу размерностью п X n, где п - число символов используемого алфавита. На рис.4 показана таблица Виженера для русского языка (алфавит Z32- 32 буквы и пробел). Первая строка содержит все символы алфавита. Каждая следующая строка получается из предыдущей циклическим сдвигом последней на символ влево.