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

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

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

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

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

;

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

;

Далее мы будем рассматривать однозначные замены, которые получили наибольшее практическое применение. Итак, далее

и .

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

В силу инъективности (по )отображения и того, что , введенные в общем случае отображения являются биекциями , определенными равенствами

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

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

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

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

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

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

В имеем следующие классы шифров замены:

1. шифры равнозначной замены,

2. шифры разнозначной замены,

3. поточные шифры,

4. блочные шифры,

5. одноалфавитные шифры,

6. многоалфавитные шифры.

В книге «Введение в криптографию» автора В.В.Ященко приведены условия задач олимпиад по математике и криптографии для школьников. Рассмотрим некоторые из них.

Задача 1.2.В адрес олимпиады пришло зашифрованное сообщение:

ФМЕЖТИВФЮ

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

Решение.

Легко видеть, что .Отсюда

где -- корни многочлена . Получаем

Буква ш.с.	Ф	В	М	Е	Ж	Т	И	В	Ф	Ю
Номер
Номер
Буква о.с.	Т	А	К	Д	Е	Р	Ж	А	Т	Ь

Ответ:ТАКДЕРЖАТЬ.

Опишем алгоритм расшифрования на языке C.

#include<stdio.h>

#include<string.h>

void main(){

int i,j,n;

/*Создаём массив содержащий 33 буквы русского алфавита*/

char а[]={'А','Б','В','Г','Д','Е','Ё','Ж','З','И','Й','К','Л','М','Н','О',

'П','Р','С','Т','У','Ф','Х','Ц','Ч','Ш','Щ','Ъ','Ы','Ь','Э','Ю', 'Я'};

/*Массив содержащий шифрованное послание*/

char b[]={'Ф','В','М','Е','Ж','Т','И','В','Ф','Ю'};

/*Расшифрование*/

for(j=0;j<10;j++){

for(i=0;i<32;i++)

if(b[i]==a[j]){ if(i==30)a[j]=b[0];

if(i==31)a[j]=b[1];

if(i!=30&i!=31)a[j]=b[i+2];

break;

}

/*Вывод исходного сообщения*/

puts(b);

}

Задача 4.6.Исходное сообщение из букв русского алфавита преобразуется в числовое сообщение заменой каждой его буквы числом по следующей таблице:

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

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

Решение. Заметим, что для всех натуральных . Складывая почленно эти равенства при , получим . По условию имеем .

Ясно, что при расшифровании так же, как и при зашифровании, вместо чисел можно воспользоваться их остатками от деления на 30. Так как для каждого целого неотрицательного

где -- некоторое целое число, то получаем следующие остатки при делении чисел на 30:

Заключительный этап представлен в талице:

Шифрованное сообщение	К	Е	Н	З	Э	Р	Е
Числовое шифрование
Шифрующий отрезок
Числовое исходное сообщение
Исходное сообщение	К	В	А	Д	Р	А	Т

Опишем алгоритм расшифрования на языке C.

#include<stdio.h>

void main(){

/*Создаём массив содержащий 30 букв русского алфавита*/

char b[]={'А','Б','В','Г','Д','Е','Ж','З','И','К','Л','М','Н','О',

'П','Р','С','Т','У','Ф','Х','Ц','Ч','Ш','Щ','Ъ','Ы','Э','Ю', 'Я'};

/*Массив содержащий шифрованное послание*/

char a[]={'К','Е','Н','З','Э','Р','Е'};

int j,i;

/*расшифрование*/

for(j=0;j<7;j++){

for(i=0;i<30;i++)

if(b[i]==a[j]){

a[j]=b[((i+30)-(j*j*j+2*j)%30)%30];

break; }

}

/*вывод исходного сообщения*/

for(j=0;j<7;j++)printf("%c",a[j]);

printf("\n");

}

Задача 6.4. На каждой из трёх осей установлено по одной вращающейся шестеренке и неподвижной стрелке. Шестеренки соединены последовательно. На первой шестеренке 33 зуба, на второй – 10, на третьей – 7. На каждом зубце первой шестеренки по часовой стрелке написано по одной букве русского языка в алфавитном порядке:

АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ

На зубцах второй и третьей шестеренки в порядке возрастания по часовой стрелке написаны цифры от 0 до 9 и от 0 до 6 соответственно. Когда стрелка первой оси указывает на букву, стрелки двух других осей указывают на цифры. Буквы сообщения шифруются последовательно. Зашифрование производится вращением первой шестеренки против часовой стрелки до первого попадания шифруемой буквы под стрелку. В этот момент последовательно выписываются цифры, на которые указывают вторая и третья стрелки. В начале шифрования стрелка первого колеса указывала на букву А, а стрелки второго и третьего колес на цифру 0.

a) зашифруйте слово ОЛИМПИАДА;

b) расшифруйте сообщение 24809283911211.

Решение.

a) Определим моменты остановок после начала шифрования. Для этого каждой букве русского алфавита припишем её порядковый номер: А – 0, Б – 1, и т. д. Тогда буквам из шифруемого слова будут соответствовать номера: О – 15, Л – 12, И – 9, М – 13, П – 16, А – 0, Д – 4. Моменты остановок будем указывать числом одношаговых (на один зубец) поворотов 1 колеса до соответствующей остановки.

Шифры перестановки

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

Рассмотрим преобразование из ШП, предназначенное для зашифрования сообщения длиной символов. Его можно представить с помощью таблицы

где - номер места шифртекста, на которое попадает первая буква исходного сообщения при выбранном преобразовании, - номер места для второй буквы и т.д. В верхней строке таблицы выписаны по порядку числа от 1 до , а в нижней - те же числа, но в произвольном порядке. Такая таблица называется подстановкой степени .

Зная подстановку, задающую преобразование, можно осуществить как зашифрование, так и расшифрование текста.

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

С увеличением числа значение растет очень быстро.

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

Широкое распространение получили шифры перестановки, использующие некоторую геометрическую фигуру. Преобразования из этого шифра состоят в том, что в фигуру исходный текст вписывается по ходу одного ``маршрута'', а затем по ходу другого выписывается с нее. Такой шифр называют маршрутной перестановкой. Например, можно вписывать исходное сообщение в прямоугольную таблицу, выбрав такой маршрут: по горизонтали, начиная с левого верхнего угла поочередно слева направо и справа налево. Выписывать же сообщение будем по другому маршруту: по вертикали, начиная с верхнего правого угла и двигаясь поочередно сверху вниз и снизу вверх.

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

К ШП относятся такие шифры как:

1. Шифр «Сцитала»,

2. Шифр «Поворотная решетка» или «решетка Кардано»,

3. шифром вертикальной перестановки'' и др.

Рассмотрим более подробно шифр «Поворотная решетка».

«Поворотная решетка»

В середине XVI века в Италии появляется книга математика, врача и философа Дж. Кардано «О тонкостях» с дополнением «О разных вещах», в котором имеются разделы, посвященные криптографии. В ней нашли отражение новые идеи криптографии: использование части самого передаваемого открытого текста в качестве ключа шифра и новый способ шифрования, который вошел в историю как «Поворотная решетка» («решетка Кардано»). Для ее изготовления брался лист из твердого материала (картон, пергамент, металл), представляющий собой квадрат, в котором вырезаны «окна». При шифровании решетка накладывалась на лист бумаги, и буквы открытого текста вписывались в «окна». При использовании всех «окон» решетка поворачивалась на 90 градусов, и вновь буквы открытого текста вписывались в «окна» повернутой решетки. Затем вновь производился поворот на 90 градусов и т. д. В один «заход» решетка работала 4 раза. Если текст зашифрован не полностью, то решетка ставилась в исходное положение и вся процедура повторялась. Это ни что иное, как шифр перестановки.

Главное требование к решетке Кардано - при всех поворотах «окна» не должны попадать на одно и то же место в квадрате, в котором образуется шифртекст.

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

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

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

Решетка Кардано позволяет осуществлять перестановку букв достаточно просто.

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

Обобщенный метод шифрования “решетка Кардано”

Недостатком классического метода является формирование шифртекста слева направо, сверху вниз. Очевидно, что он достаточно легко раскрывается -граммным криптоанализом (чтение в колонках).

Усилить алгоритм можно:

1. Избавлением от последовательного вписывания в «окна» решетки-ключа.

2. Избавлением от последовательного поворота решетки по или против часовой стрелке.

3. Использование алгоритма в -мерном пространстве.

4. Искусственным усложнением алгоритма в рамках языка программирования.

Очевидно, что при использовании произвольной последовательности маршрута перестановок увеличится размер ключа, причем в разы. Это усиление даёт увеличение всех возможных вариантов ключей в раз ( – сторона квадрата), что очень значительно.

⇐ Предыдущая 123 Следующая ⇒