Методы перестановки

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

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

П	л	к	з	ч	и
о	а	Г	р	а	#
с	ю	-	ы	т	#
ы	-	В	в	к	#

Рис.1.2.Шифр табличной перестановки

Открытый текст: Посылаю _ кг _ взрывчатки###.

Шифрсообщение:Плкзчиоагра#сю_ыт#ы_ввк#.

‘#’ - произвольные символы

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

Другой вариант - кодирование перестановкой по группам символов, используя некоторые зигзагообразные шаблоны, например, как показано на рисунке 1.3. Стоит записать

Рис.1.3. Зигзагообразный шифр перестановки

Открытый текст: Посылаю_кг_взрывчатки###

Шифрсообщение:Пюксл_ывгоа_ зтиыч#в##рак

‘#’- произвольные символы.

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

Использовались и более сложные (ручные) системы, также групповые. Например, в квадрате (рис.1.4), состоящем из 4 малых квадратов с определенной нумерацией клеток, вырезают 4 клетки под разными номерами. Квадрат кладется в начальное положение («1» - вверху) и в отверстия (слева направо/сверху вниз) вписываются буквы открытого сообщения. Затем квадрат поворачивается против часовой стрелки на 90 градусов («2» - вверху) и также вписываются следующие буквы, потом повторяем процесс для положения «3» и «4». Если остаются свободные клетки - они заполняются произвольными символами. Шифрсообщение получают, считав по столбцам или по строкам последовательность записанных в прямоугольнике букв.

Рис.1.4. Шифровальный квадрат

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

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

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

Перестановки получаются за счет разницы путей записи исходной информации и путей считывания зашифрованной информации в пределах геометрической фигуры. Примером простейшей перестановки является запись блока исходной информации в матрицу по строкам, а считывание - по столбцам. Последовательность заполнения строк матрицы и считывания зашифрованной информации по столбцам может задаваться ключом. Криптостойкость метода зависит от длины блока (размерности матрицы). Так для блока длиной 64 символа (размерность матрицы 8 x 8) возможны 1,6 х 10⁹ комбинаций ключа. Для блока длиной 256 символов (матрица размерностью 16 x 16) число возможных ключей достигает 1,4 x 10²⁶. Решение задачи перебора ключей в последнем случае даже для современных ЭВМ представляет существенную сложность.

Перестановки используются также в методе, основанном на применении маршрутов Гамильтона. Этот метод реализуется путем выполнения следующих шагов.

Шаг 1. Исходная информация разбивается на блоки. Если длина шифруемой информации не кратна длине блока, то на свободные места последнего блока помещаются специальные служебные символы-заполнители (например *).

Шаг 2. Символами блока заполняется таблица, в которой для каждого порядкового номера символа в блоке отводится вполне определенное место (рис. 5).

Шаг 3. Считывание символов из таблицы осуществляется по одному из маршрутов. Увеличение числа маршрутов повышает Криптостойкость шифра. Маршруты выбираются либо последовательно, либо их очередность задается ключом К.

Шаг 4. Зашифрованная последовательность символов разбивается на блоки фиксированной длины L. Величина L может отличаться от длины блоков, на которые разбивается исходная информация на шаге 1.

Расшифрование производится в обратном порядке. В соответствии с ключом выбирается маршрут и заполняется таблица согласно этому маршруту.


Таблица	Маршрут № 1	Маршрут № 2

Рис. 5. Вариант 8-элементной таблицы и маршрутов Гамильтона

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

Пусть требуется зашифровать исходный текст Т0 = <МЕТОДЫ_ПЕРЕСТАНОВКИ>. Ключ и длина зашифрованных блоков соответственно равны: К = <2, 1, 1>, L = 4. Для шифрования используются таблица и два маршрута, представленные на рис. 5. Для заданных условий


Маршрут №2	Маршрут № 1	Маршрут № 1

Рис. 6. Пример шифрования с помощью маршрутов Гамильтона

маршруты с заполненными матрицами имеют вид, показанный на рис. 6.

Шаг 1. Исходный текст разбивается на три блока:

Б1 = <МЕТОДЫ_П>;

Б2 = <ЕРЕСТАНО>;

Б3 = <ВКИ*****>.

Шаг 2. Заполняются три матрицы с маршрутами 2, 1, 1 (рис. 2.2.2).

Шаг 3. Получение шифртекста путем расстановки символов в соответствии с маршрутами.

Т1 = <ОП_ТМЕЫДЕСРЕТАОНИ*КВ****>.

Шаг 4. Разбиение на блоки шифртекста

Т1 = <ОП_Т МЕЫД ЕСРЕ ТАОН И*КВ ****>.

В практике большое значение имеет использование специальных аппаратных схем, реализующих метод перестановок (рис. 7).

Рис. 7. Схема перестановок

Современные блочные шифры.

Современные криптосистемы ориентированы на программно-аппаратные методы реализации. Блочные криптосистемы представляют собой блочные (групповые) шифрпреобразования. Блочная криптосистема разбивает открытый текст М на последовательные блоки M₁, M₂,... и зашифровывает каждый блок с помощью одного и того же обратимого преобразования E_k, выполне

нного с помощью ключа К. E_k(М)=E_k(M₁), E_k(M₂),.… Любое из них можно рассматривать как последовательность операций, проводимых с элементами ключа и открытого текста, а так же производными от них величинами. Произвол в выборе элементов алгоритма шифрования достаточно велик, однако "элементарные" операции должны обладать хорошим криптографическими свойствами и допускать удобную техническую или программную реализацию /1-6/. Обычно используются операции:

- побитового сложения по модулю 2 (обозначение операции Å) двоичных векторов (XOR):

return false">ссылка скрыта

0Е0=0

0Е1=1

1Е1=0

- сложение целых чисел по определенному модулю:

например, по модулю 2³², обозначение операции - +

a + b= a+b, если a+b<2³²,

а + b= a+b-2³², если a+bі2³²,

где + - сложение целых чисел;

- умножение целых чисел по определенному модулю:

ab(mod n) = res(ab/n) – остаток от деления произведения целых чисел ab на n;

- перестановка битов двоичных векторов;

- табличная замена элементов двоичных векторов.

Практическая стойкость алгоритмов шифрования зависит и от особенностей соединения операций в последовательности. Примерами блочных систем являются алгоритмы блочного шифрования, принятые в качестве стандартов шифрования данных в США и России – DES–алгоритм и ГОСТ-28147-89 соответственно.

DES - алгоритм

В 1973 году Национальное Бюро Стандартов США начало работы по созданию стандарта шифрования данных на ЭВМ. Был объявлен конкурс, который выиграла фирма IBM, представившая алгоритм шифрования, сейчас

известный как DES-алгоритм (Data Encryption Standard) [1].

Рассмотрим работу DES-алгоритма в простейшем (базовом) режиме ЕСВ - электронной кодовой книги. Алгоритм работы показан на рисунке 1.5.

Входные 64-битовые векторы, называемые блоками открытого текста, преобразуются в выходные 64-битовые векторы, называемые блоками шифртекста, с помощью 56-битового ключа К (число различных ключей равно 2⁵⁶=7_*10⁶)

Алгоритм реализуется в 16 аналогичных циклах шифрования, где в i-ом цикле используется цикловой ключ Ki, предоставляющий собой выборку 48 битов из 56 битов ключа К. Реализация алгоритма функции f показана на рисунке 1.6. Здесь операция Е - расширение 32-битового вектора до 48-битового, операция S_j(S-боксы) - замена 6-битовых векторов на 4 - битовые.

Рис. 1.5. Блок-схема DES-алгоритма

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

В ходе открытого обсуждения алгоритма в прессе, рассматривались пути усиления его криптографических свойств. Наиболее простой вариант предполагал использовать независимые 48-битовые векторы в качестве цифровых ключей, что позволит увеличить общее число ключей до 2⁷⁶⁸.

Режим электронной кодовой книги (ЕСВ) используется в основном для шифрования коротких сообщений служебного содержания - паролей, ключей и т.п. Наиболее общий режим - режим сцепления блоков (СВС), (Cifer Block Chaining) схема которого показана на рисунке 1.7. Здесь каждый входной блок зависит от всех предыдущих. Начальный вектор b_o (случайный начальный вектор) вырабатывается для каждого сообщения и может передаваться в линию связи, как в открытом, так и в шифрованном виде, что препятствует атакам на шифротекст, основанным на наличии стандартов в начале сообщения (вспомните "Семнадцать мгновений весны": Центр - Юстасу... ).

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

Рис.1.6. Блок-схема функции f DES -алгогитма

Достигнута высокая скорость шифрования. По некоторым сообщениям, в одном из устройств на основе специализированной микросхемы она составляет около 45 Мбит/сек.

Рис. 1.7. Реализация DES-алгоритма в режиме сцепления блоков

Основные области применения DES-алгоритма:

- хранение данных в ЭВМ (шифрование файлов, паролей);

- электронная система платежей (между клиентом и банком);

- электронный обмен коммерческой информацией (между покупателем и продавцом).

Российский стандарт шифрования

В 1989 году был разработан блочный шифр для использования в качестве государственного стандарта шифрования (зарегистрирован как ГОСТ 28147-89)/7/. В основном алгоритм применяется в банковской системе, судя по публикациям – несколько медлителен, но обладает весьма высокой стойкостью.

Его общая схема близка к схеме DES-алгоритма, лишь отсутствует начальная перестановка и число циклов шифрования равно 32 (вместо 16 в DES-алгоритме). Ключом считается набор из 8 элементарных 32-битовых ключей X₁, X₂,...,X₈(общее число ключей 2²⁵⁶). В циклах шифрования трижды используется прямая последовательность элементарных ключей и один раз - обратная: X₈, X₇,...,X₁.

Основное отличие – в реализации функции f стандарта шифрования (приведена на рисунке 1.8). Элементы S₁, S₂, ..., S₈ - представляют собой таблицы замены 4-битовых векторов и могут рассматриваться как долговременные ключи

ГОСТ 28147-89, как DES-алгоритм, предусматривает различные режимы использования и только базовый (режим простой замены) совпадает, по сути, с базовым режимом DES-алгоритма, остальные - в той или иной мере отличаются.

Известна специальная реализация алгоритма шифрования ГОСТ 28147-89 аппаратная плата шифрования данных «Криптон-3» для IBM PC, ее производительность - 50 Кбит/сек.

Рис.1.8 Блок-схема функции fалгоритма ГОСТ 28147-89 .