Шифрование заменой (подстановками).docx

Шифрование заменой (подстановками)

Моно(одно)алфавитная замена — самый простой способ прямой замены. Составляется таблица прямой замены букв шифруемого текста другими буквами данного алфавита.

Таблица замены

Знаки в таблице шифрования не должны повторяться, т.е. таблица замены должна представлять полную перестановку алфавита (когда все буквы подверглись перестановке). После замены шифротекст для удобства работы с ним разбивается на равновеликие группы. В шифре Цезаря таблица замены есть алфавит сдвинутый в кольцо на 3 позиции.

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

Многотабличная замена. Буквенная ключевая последовательность.

Многоалфавитный шифр более стойкий. Например, таблица Вижинера. Это квадратная матрица N*N, где N — количество символов алфавита.

Первая строка матрицы — исходный алфавит. Следующие — кольцевой сдвиг алфавита на одну букву. Для шифрования задаётся слово из K букв (буквенный ключ). Из таблицы Вижинера выписывается рабочая подтаблица (K+1)*N. Первая строка — исходный алфавит. Следующие строки — алфавиты, начинающиеся с очередных букв ключа. Процедура шифрования:

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

·        Замена букв производится по подматрице и затем шифротекст разбивается на группы, например по 5 знаков.

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

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

Проблемы ключа.

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

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

алфавита и набором положительных целых чисел 0, 1, 2, …,

N - )

устанавливается

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

шифрование: расшифрование:

=      + zi    mod N

=      - zi    mod N

(1)

Если

i = cons

, то имеем одноалфавитную подстановку. Для неё общую формулу

можно расширить:

=     × x + z

mod N , при

i = cons

(2)

где:    yi xi

—                числовой               код                букв                шифра

—           числовой          код          букв           исходного          текста

N                                —                               размер                              алфавита

a                           —                          десятичный                          коэффициент

z — коэффициент сдвига

При a = 1 ,

z =(34) ,

N = 27

получаем код Цезаря с алфавитом, например:

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

z = 3 (формула 2), а вторая с

z = 5 , то получим результирующую одну замену с

z = 8 .

Числовая ключевая последовательность

Если      z      выбирается     из     последовательности

,,K    , zn ,                 то     имеем

многоалфавитную  подстановку с периодом ключа    =

z ,K , z K } равным K .

Если в многоалфавитной подстановке:

1.    Число знаков в ключе больше (или равно) числу шифруемых (исходных) знаков текста и знаки в ключе распределены случайно

2.    Ключ используется только один раз

3.    Исходный текст (или его часть) неизвестен злоумышленнику (криптоаналитику),

то зашифрованный текст будет нераскрываем и называется системой (схемой) Вернама.

Именно для этих условий Шеннон Э. и доказал нераскрываемость шифра.

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

=     - x  mod N

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

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

перестановок )(

= N!,

P 2 )

1.088 1028 . Однако, из этого множества не так много

подходящих, нужны только «полные» перестановки, т.е. такие которые затронули все буквы алфавита. Вот из этого множества и выбираем 10 (не считая первой) перестановок. Нумеруем их натуральными числами 0, 1, …, 9.

В качестве ключа берём случайный (практически псевдослучайный) ряд чисел бесконечной длины или длины не меньшей, чем количество букв исходном тексте. Например: n = 3.14159265358979323846..., e = 2.71828182845904523536...

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

Однако это всё таки всего 10-алфавитный ключ, правда алфавиты чередуются на всём протяжении текста в «случайном» порядке, а не повторяются группами по слову текстового ключа. Стойкость шифра несколько усиливается.

Формула (1) даст ещё лучшую стойкость, если в ней в качестве последовательности ключа взять «случайные» (например, по таблице случайных чисел 2-хразрядных

десятичных) из множества 0, 1, 2, …,

N - ) .

В этом случае получим 27-алфавитную подстановку со «случайным» чередованием алфавитов на всём протяжении исходного текста.