Перестановочные шифры

Подстановочные шифры.

Шифры.

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

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

2. Однозвучный подстановочный шифр похож на простую подстановочную криптосистему за исключением того, что один символ открытого текста отображается на несколько символов шифротекста. Например, "A" может соответствовать 5, 13, 25; "B" - 7, 19, 31.

3. Полигаммный подстановочный шифр - это шифр, который блоки символов шифрует по группам ("ABA" - соответствует "RTQ", "ABB" соответствует "SLL".

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

(Знаменитый шифр Цезаря - каждый символ открытого текста заменяется символом, находящегося тремя символами правее по модулю 26 ("A" заменяется на "D," "B" - на "E",... "W" - на " Z ", "X" - на "A", представляет собой простой подстановочный фильтр.

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

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

где i1 – номер места шифротекста, на которое попадает первая буква исходного сообщения при выбранном преобразовании, i2 – номер места для второй буквы.

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

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

1 2 3 4 5 6

5 2 3 1 4 6

и в соответствии с ней зашифровывается слово МОСКВА, то получится КОСВМА.

Существует n! вариантов заполнения нижней строки таблицы.

n
n!

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

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

10.4.3. Компьютерные алгоритмы шифрования

Существует множество алгоритмов шифрования, реализованных в виде компьютерных программ:

- DES (Data Encryption Standard), AES. Симметричный алгоритм шифрования(госстанд. в США).

- ГОСТ 28147-89. Симметричный алгоритм шифрования (госстандарт в России).

- RSA (Rivest, Shamir, Adleman,1978 г.). Асимметричный алгоритм шифрования.

Алгоритм DES (госстандарт в США, 1980г.) Параметры алгоритма: разрядность блока - 64 бита, размер ключа - 56 бит (с учетом контрольных разрядов - 64 бита). Алгоритм представляет собой классическую сеть Файстеля из 16 раундов с добавлением входной и выходной перестановки бит).

Образующая функция сети в алгоритме DES состоит из 4 операций:

1) перестановка бит/расширение блока с помощью повторов по определенной схеме;

2) наложение ключа раунда операцией XOR;

3) табличные подстановки;

4) перестановка бит.

Рис.12.6. Сеть Фейстеля

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

Недостаточная длина ключа DES, его ориентированность на аппаратную реализацию побудило правительство США к объявлению открытого конкурса на криптостандарт блочного шифрования США. Конкурс получил название AES (Advanced Encryption Standart) – "улучшенный стандарт шифрования" и был проведен в 1997 - 2000 годах (15 исследовательских групп). Выбраны 5–ть финалистов, прошедших во второй этап конкурса.

Преимущество	Алгоритмы
RIJNDAEL	SERPENT	TWOFISH	RC6	MARS
Быстродействие: аппаратная реализация	+	+
программная реализация: на слабых ВС на мощных ВС	+	+		+ +
Этап расширения ключа	+		+
Распараллели-ваемость	+
Этап дешифрирования			+	+	+
Запас криптостойкости	Оптимум	Завышен	Завышен	Оптимум	Завышен
Количество голосов

2 октября 2000 года алгоритм RIJNDAEL был официально признан победителем конкурса и получил название - AES. Структура: прямоугольные KASLT - сети. Шифруемый блок представляется в виде прямоугольника - 4´4 или 4´ 6 байт, а затем над ним построчно, по столбцам и побайтно производятся криптопреобразования. KASLT представляет собой аббревиатуру Key Addition (добавление ключа), Substitution (табличная подстановка) и Linear Transposition (линейное перемешивание).

Rijndael (бельгийцы Vincent Rijmen и Joan Daemen) - шифр с изменяемым размером блока и длиной ключа. Единственные налагаемые требования на эти два параметра - их кратность 32 битам. Размер блока далее определяется как Nb´32, длина ключа - Nk´32. Количество раундов сети, необходимое для стойкого шифрования зависит от двух параметров. Для конкурса AES в соответствии с требованиями авторы зафиксировали Nb = 4 (то есть шифруемый блок представляет собой квадрат 4 на 4 байта) и Nk = 4, 6, и 8. В этом случае количество раундов сети Nr соответственно равно 10, 12 и 14. Потенциально шифр может работать и с большими по размерам блоками.

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

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

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

ГОСТ 28147-89 - российский стандарт симметричного шифрования (1990г.) - блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма шифра - сеть Фейстеля. Базовым режимом шифрования является режим простой замены. Для зашифрования - открытый текст разбивается на две половины: младшие биты - A, старшие биты - B. На i-ом цикле используется подключ K_i:

( - двоичное «исключающее или» - XOR)

Оператор XOR имеет следующую таблицу истинности:

XOR

Результат операции XOR равен TRUE (истина) тогда и только тогда, когда один оператор равен TRUE, а второй - FALSE (ложь). Это дает XOR уникальные свойства: если выполнить операцию XOR над двумя байтами, один из которых называется ключом, а затем взять результат и ключ и снова применить к ним операцию XOR, то в результате получим исходный байт, как показано ниже.

	1101 1001	исходный текст
XOR	0101 0011	ключ
	1000 1010	шифр
	1000 1010	шифр
XOR	0101 0011	ключ
	1101 1001	исходный текст

Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: K₁…K₈.

Ключи K₉…K₂₄ являются циклическим повторением ключей K₁…K₈ (нумеруются от младших битов к старшим). Ключи K₂₅…K₃₂ являются ключами K₁…K₈, идущими в обратном порядке.

После выполнения всех 32 раундов алгоритма, блоки A₃₃ и B₃₃ склеиваются (старшим битом становится A₃₃, а младшим - B₃₃) - результат работы алгоритма.

Расшифрование выполняется так же, как и зашифрование, но инвертируется порядок подключей K_i.

Функция f (A_i, K_i) вычисляется следующим образом:

A_i и K_i складываются по модулю 2³².

Результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания старшинства битов), называемого S-блоком. Общее количество S-блоков - восемь, сколько и подпоследовательностей. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Первая 4-битная подпоследовательность попадает на вход первого S-блока, вторая — на вход второго.

Если S-блок выглядит так:

1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12

и на входе S-блока 0, то на выходе будет 1, если 4, то на выходе будет 5, если на входе 12, то на выходе 6. Выходы всех восьми S-блоков объединяются в 32-битное слово, затем всё слово циклически сдвигается влево (к старшим разрядам) на 11 битов.

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

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

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

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

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

Алгоритм RSA стал первым алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи. Надежность алгоритма основывается на трудности факторизации больших чисел и трудности вычисления дискретных логарифмов. (Факторизацией натурального числа называется его разложение в произведение простых множителей. Дискретное логарифмирование - задача обращения функции g^x. Наиболее часто задачу дискретного логарифмирования рассматривают в мультипликативной группе кольца вычетов или конечного поля, а также в группе точек эллиптической кривой над конечным полем. Эффективные алгоритмы для решения задачи дискретного логарифмирования в общем случае неизвестны. Для заданных g и a решение x уравнения g^x = a называется дискретным логарифмом элемента a по основанию g).

Первый этап любого асимметричного алгоритма - создание пары ключей:

1. Выбираются два больших простых числа р и q (простым называется число, делящееся на

единицу и на само себя).

2. Вычисляется n= (p ´ q).

3. Выбирается произвольное число e (e < n) такое, что наибольший общий делитель НОД (e,

(p-1) ´ (q-1)) = 1, т. е. должно быть взаимно простым с числом (p-1) ´ (q-1).

4. Методом Евклида решается в целых числах уравнение e ´ d + (p-1) ´ (q-1) ´ y = 1. Здесь

неизвестными являются переменные d и y - метод Евклида как раз и находит множество

пар (d, y), каждая из которых является решением уравнения в целых числах.

5. Пара чисел (e, n) - публикуется как открытый ключ. Число d хранится в строжайшем

секрете - это и есть закрытый ключ, который позволит читать все послания, зашифрованные с помощью пары ключей (e, n).

Второй этап - собственно шифрование с помощью открытого ключа.

1. Отправитель разбивает свое сообщение на блоки, равные k = [log₂ (n)], где квадратные

скобки - взятие целой части от дробного числа. Подобный блок может быть интерпретирован как число из диапазона (0: 2^k – 1).

2. Для каждого такого числа (назовем его m_i) вычисляется выражение c_i = ((m_i)^e) mod n. Блоки c_i и есть зашифрованное сообщение. Их можно без опасения передавать по открытому каналу, поскольку операция возведения в степень по модулю простого числа является трудноразрешимой математической задачей.

Третий этап - дешифрование послания с помощью секретного ключа. Частный случай теоремы Эйлера утверждает, что если число n может быть представлено в виде произведения двух простых чисел p и q, то для любого х имеет место равенство:

(х^{(р-1) ´ (q-1)}) mod n = 1.

Возведем обе ее части в степень (-y): ((х^{(-y) ´ (р-1) ´ (q-1)}) mod n = 1^(-y) = x. После умножения обеих частей равенства на х получим:

(х^{(-y) ´ (р-1) ´ (q-1)}) mod n = 1 ´ = х

Алгоритм: Взять открытый ключ стороны Взять открытый текст Передать шифрованное сообщение:

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

Пример1. Пусть р = 5, а q = 11, тогда значение n = 55. В качестве открытого ключа е выберем число 7, таким образом, весь открытый ключ имеет вид (е=7, n=55).

Вычислим закрытый ключ d: уравнение e ´ d + (p-1) ´ (q-1) ´ y = 1 приобретает вид

7 ´ d + 40 ´ y = 1 и имеет в целых числах решение d = 23, y = - 4. Таким образом, закрытым ключом являются числа (23, 55).

Пусть произвольный отправитель хочет передать абоненту комбинацию бит 100111₂, ее числовой эквивалент 39₁₀. Возводим 39 в степень открытого ключа е = 7 по модулю n = 55: (39⁷ mod 55) = 19. Число 19 является шифрограммой и передается по каналу связи. Получатель по приходу сообщения возводит его в степень d = 23: (19²³ mod 55) = 39.

Дата добавления: 2014-01-20