Пошаговый алгоритм симметричных криптографических преобразований

Алгоритм криптографических преобразований на базе биграммного шифра «двойная пирамида»

Основные положения и принципы реализации

Биграммный шифр «двойная пирамида» использует сразу две совмещенные по горизонтали пирамиды (рис. 2), одна из которых (левая) имеет основание в нижней (16-ой) строке, а другая (правая) в верхней (первой) строке (выделена серым фоном). Количество строк у параллелограмма, объединяющего эти две пирамиды – 16. Длина каждой объединенной строки включает в себя 32 ячейки. Таким образом, объединенная из двух пирамид фигура включает в себя 16 · 32 = 512 ячеек, следовательно, каждая пирамида состоит из 256 ячеек. Матричный эквивалент биграммного шифра «двойная пирамида» представлен на рис. 3.

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

Как видно из рисунка (рис.3), матричный эквивалент представляет собой двумерный массив, что существенно упрощает алгоритмы криптографических преобразований в рамках биграммного шифра «двойная пирамида». Для шифрования сообщение разбивают на биграммы. Первая буква биграммы берется из левой, а вторая из правой пирамиды. Приведем описание алгоритма использования шифра «двойная пирамида» для алфавита, представленного символами системы кодирования SCII.

Первая комбинация.Буквы биграммы шифруемого текста расположены на одной строке левой и правой пирамид (рис. 2 и 3, позиция 1). В этом случае буквы шифровки берутся из строки симметричной относительно горизонтального центра таблицы (например, первая строка, шифруемого текста заменяется последней, вторая – 15 и т.д.).

Вторая комбинация.Буквы биграммы расположены в разных строках и разных столбцах левой и правой пирамид. В этом случае возможны два варианта. Первый вариант – «вниз по лестнице», когда символ из левой пирамиды расположен выше символа из правой пирамиды (рис. 3.2). Мысленно строится прямоугольник таким образом, чтобы буквы биграммы лежали в его противоположных вершинах, симметрично диагонали матрицы. Тогда другие две вершины этого прямоугольника дают буквы шифровки.

Так, например, для шифровки биграммы, изображенной на рис. 3., имеем прямоугольник, у которого первый символ биграммного шифра расположен в левой пирамиде в ее 4 строке и отстоит от диагонали на 4 позиции, а второй символ расположен в правой пирамиде в ее 7 строке и отстоит от диагонали также на 4 позиции. Следовательно, символы шифра расположены, соответственно, в 4 и 7 строках и имеют удаление от диагонали 10 позиций.

Второй вариант – «вверх по лестнице» (рис. 4) включает в себя два самостоятельных алгоритма. Первый алгоритм обрабатывает ситуацию, когда, поднимаясь «вверх по лестнице», по правилам из первого варианта, оба зашифрованных символа попадают в разные пирамиды (рис. 4.). Этот случай обрабатывается алгоритмом из первого варианта.

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

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

Основные положения и принципы реализации

Биграммный шифр «четырехсегментный прямоугольник» является аналогом бинарного шифра Чарльза-Уитстона, в котором, однако каждый квадрат размерность 16 × 16 разбит на два сегмента размерностью 16 × 8. Матричный эквивалент биграммного шифра – «четырехсегментный прямоугольник», представляет собой две пары совмещенных по диагонали прямоугольников размерностью 16 × 8 (см. рис 5).

Первый сегмент первого квадрата расположен в верхнем левом углу матрицы, второй – в нижнем правом углу (на рис. 5 сегменты первого квадрата выделены темным фоном).

Первый сегмент второго квадрата расположен в нижнем левом углу матрицы, второй – в верхнем правом (на рис. 5 сегменты второго квадрата выделены светлым фоном).

Как видно из рисунка 5, матричный эквивалент представляет собой двумерный массив размерностью 16 × 32, и, следовательно, также как и в случае с «двойной пирамидой» состоит из 512 ячеек. Диагональное расположение сегментов первого и второго квадратов позволяет заметно упростить алгоритмы криптографических преобразований.

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

При этом возможны следующие варианты:

- первый символ находится в первом сегменте первого квадрата, второй символ в первом сегменте второго квадрата;

- первый символ – в первом сегменте первого, второй – во втором второго;

- первый – во втором первого, второй – в первом второго;

- первый – во втором первого, второй – во втором второго

Приведем описание алгоритма использования шифра «четырехсегментный прямоугольник» для символов алфавита соответствующего системе кодирования SCII. Алгоритм шифрации должен обрабатывать одну из четырех возможных комбинаций расположения бинарного кода в четырех сегментах нашей матрицы.

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

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

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

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

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

Первый вариант. Символы биграммы отстоят друг от друга не более чем 16 позиций (m≤16) (рис. 6.3). В этом случае биграммный шифр располагается в этих же сегментах в строке симметричной обратному счету строк (например, первая и последняя, вторая и предпоследняя и т.д.). Ячейки биграммного шифра располагаются симметрично относительно линии сопряжения «крест на крест» (например, первый символ бинарного шифра заносится в столбец с отступом от линии сопряжения на 4, а второй – на 3 позиции, в то время как биграммнные символы текста имеют отступы соответственно 3 и 4 позиции).

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

Пошаговый алгоритм симметричных криптографических преобразований

Инициализация. Инициализация производится путем выполнения целого ряда последовательно выполняемых операций.

Формирование «исходников». «Исходником» называется одномерный массив размерностью в 256 неповторяющихся элементов, с диапазоном значений [0..255]. Заполнение исходников конкретными числами осуществляется по специальному алгоритму.

Шаг 1. Создаются пустые множества с идентификаторами {Mn₁},…,{Mn_N}, где N – количество «исходников» (определяется пользователем).

Шаг 2. Выполняется процедура генерации случайного числа «S» в диапазоне [0..255].

Шаг 3. Если сгенерированное случайное число [S] принадлежит каждому из множеств {Mn₁},…,{Mn_N}, переходим к выполнению пункта 2, в противном случае – пункта 4.

Шаг 4. Первое множество {Mn_х}, которому не принадлежит случайное число [S] дополняется новым членом: {Mn_х}:= {Mn_х} + [S], здесь {Mn_х}; в текущую позицию соответствующего «исходника», также записывается значение элемента [S] .

Шаг 5. Если множество {Mn_х} уже состоит из 256 элементов, то оно исключается из списка формируемых.

Шаг 6. Если список заполняемых множеств пустой, переходим к пункту 7, в противном случае – к пункту 2.

Шаг 7. Выход.

Количество «исходников» определяется пользователем на этапе инициализации, их количество не должно быть больше 256.

Выбор текущих «исходников» пользователем. Выбор текущих «исходников» (в количестве двух) производится в автоматическом режиме после ввода пользователем ключевой секретной комбинации по формуле:

,

где Х_i – элемент секретной ключевой комбинации (ключа) формулы гаммирования;

М_т.д – такназываемый маркант, который не является ключом и определяется как функция текущей даты;

N – количество сгенерированных на этапе инициализации «исходников» (N ≤ 256);

n – число элементов ключа.

Формирование рабочих таблиц. Рабочая таблица это списковый эквивалент шифровальной матрицы (у нас их две), состоящий из нескольких столбцов. Первый столбец это последовательность кодов элементов шифровальной таблицы, последующие столбцы – рабочие реквизиты шифровальной матрицы, используемые алгоритмами криптографических преобразований (например, для алгоритма «двойная пирамида» это номер столбца, номер строки, длина строки и т.д. ).

Формирование элементов первого столбца производится с использованием алгоритма гаммирования по ключевой комбинации:

,

где π – подстановка по первому столбцу рабочей таблицы.

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

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

Шаг первый – шифруемый текст разбивается на сегменты по 255 символов в каждом. Далее каждый сегмент дополняется одним дополнительным служебным символом, который становится первым элементом сегмента и рамен фактическому количеству символов в сегменте. Последний сегмент дополняется до 256 случайными символами.

Шаг второй. Первые y символов каждого сегмента меняются местами с последующими. Значение параметра y определяется на этапе инициализации программы и зависит от конкретных значений ключа.

Шаг третий. Реализация элементарных операций подстановки внутри каждого сегмента, осуществляется по правилам, вытекающим из анализа ключа.

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

Основной этап. В рамках основного этапа реализуются последовательно и многократно алгоритмы подстановки и перемешивания внутри блока размерностью 256 байт.

Алгоритм перемешивания внутри блока. Элементы внутри блока перемешиваются в соответствии со значениями элементов первого столбца рабочей таблицы (для каждого блока другой). Например, если первый элемент первого столбца рабочей таблицы имеет значение 54, то на первое место в блоке ставится 54 элемент блока и т. д.

Алгоритм подстановки внутри блока. Метод подстановки внутри блока это алгоритм криптографических преобразований по методу «двойная пирамида» или «четырехсегментный квадрат».

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

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: