Алгоритм генерации подключей для шифрования

АлгоритмSPN

Рассмотрим алгоритм шифрования, построенный на основе сети SPN, структура которого показана на рис. 1. Здесь  - 16-ти битовый блок открытого (исходного) сообщения,  - 16-ти битовый блок закрытого (зашифрованного) сообщения.

Рисунок 1 – Структура алгоритма шифрования, построенного на основе сети SPN[1, 2, 3]

В основе алгоритма – последовательное применение двух основных преобразований: замены

и перестановки

,

где  - размер блока. В алгоритме, представленном на рис. 1, =4, =4.

Замена бит в блоке

Преобразование  можно задать в виде таблицы, где первая строка задает вход ( ), а вторая строка – выход ( ). Табл.1 задает используемое в данном алгоритме преобразование .

Таблица 1 - Замена

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

Рисунок 2 – Графическое обозначение замены

В частности, в схеме алгоритма на рис. 1 операции замены обозначены именно таким образом – в виде S-блоков замены. На вход блока замены поступает 4-х битовое значение, на выходе блока замены – измененное в соответствии с табл.1 4-х битовое значение. Табл.1 можно описать в виде массива (рис.3).

Рисунок 3 – Реализация блока замены

Для выполнения замены  необходимо выполнить следующие шаги:

1. -битовый блок разбить на -битовых подблоков. Такое разбиение для -битового блока можно записать таким образом

,

где

2. Применить преобразование  над каждым подблоком:

3. Объединить подблоки в один -битовый вход

.

Пример выполнения замены для 16-битового блока приведен на рис.4.

Путь . Тогда 16-ти битовый блок  разбивается на 4 подблока , где , , , . Для блока  получим 4 подблока: . , , . После применения преобразования  (табл.1) над каждым из подблоков получим , , , . Таким образом, результатом применения преобразования замены над блоком будет блок .

Рисунок 4 – Пример выполнения операции замены

Перестановка бит в блоке

Преобразование задает перестановку бит внутри блока. Данное преобразование удобно задать в виде таблицы, в которой в первой строке (вход z)заданы порядковые номера бит блока (самый младший бит в блоке имеет номер 0), а во второй строке - выход ( )–результат перестановки бит внутри блока, т.е. на -ю позицию ставится  бит блока (табл.2).

Таблица 2 - Перестановка

вход	15	14	13	12	11	10	9	8	7	6	5	4	3	2	1	0
Выход	15	11	7	3	14	10	6	2	13	9	5	1	12	8	4	0

Указанный способ перестановки реализован с помощью метода pbox() (рис.5).

Рисунок 5

Например, для блока  результатом применения преобразования (табл.2) будет блок (рис.6).

Рисунок 6

На рис.6 пустая ячейка в таблице означает нуль. Имеет смысл переставлять только единицы, как это реализовано в методе pbox() (рис.5). Закрашенные одинаковым цветом ячейки таблицы показывают перемещение соответствующих единиц в результате перестановки.

Перестановку (табл.2) удобно задать в виде массива:

P = [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15].

В схеме на рис.1 перестановка показана традиционным графическим способом как в примере на рис.7.

Рисунок 7

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

Алгоритм генерации подключей для шифрования

Составной частью алгоритма является описание процедуры получения раундовых ключей – так называемой процедуры генерации подключей. Для рассматриваемого алгоритма шифрования процедура генерации подключей заключается в следующем: все пять подключей получаются последовательным выбором 16 бит из 32 битного ключа по следующему правилу. Ключ ( ) состоит из 16 последовательных бит ключа , начиная с . Например, для ключа =982832703 (00111010100101001101011000111111) в результате применения процедуры генерации подключей (расширения ключа) получены следующие раундовые ключи (рис.8).

=0011101010010100 =1010100101001101 =1001010011010110 =0100110101100011 =1101011000111111

Рисунок 8 – Раундовые ключи (подключи)

Алгоритм реализован с помощью метода round_keys() (рис.9).

Рисунок 9

Алгоритм шифрования

Псевдокод алгоритма шифрования приведен на рис.10.  - количество раундов шифрования.

Рисунок 10 – Псевдокод алгоритма шифрования

Для открытого 16-ти битового блока  и ключа последовательное применение алгоритма (рис.10) дает результаты, приведенные на рис.11.

Раунд 1 Раунд 2 Раунд 3 Раунд 4 =0110101011101001

Рисунок 11

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

Задание 1

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

Вход: Скворцов Антон.

S->01010011

A->01000001

Результат:

y=1010101110000110

Задание 2

В файле spn1.py содержится реализация алгоритма шифрования.

а) Пояснить, что делает функция demux():

Функция demux() разбивает входную битовую строку на 4 блока и переводит из двоичной системы в десятичную поблочно, но в полученном списке они храняться в обратном порядке.

б) Пояснить, что делает функция mux():

Функция mux()является функцией, обратной demux().

в) Зашифровать блок данных из задания 1 (рис.12), представленный индивидуальным 16-ти битовым числом . Ключ шифрования =982832703. Проверьте, совпадает ли результат с результатом из задания 1.

Рисунок 12

Да, ответ совпал.

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

Раундовые ключи.

[14996, 43341, 38102, 19811, 54847]

Значения блока.

x=0101001101000001

w = 1111000111011011

w = 1011100011111101

w = 1011111100001110

y=1010101110000110

Задание 3

Написать функцию encrypt_data(self, data, key, rounds), где data – список чисел (данные, прочитанные из файла),key – ключ шифра, rounds – количество раундов.

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

Рисунок 13

defencrypt_data(self, data, key, rounds):

res=[]

print(data)

rk = self.round_keys(key)

for d in data:

res.append(self.encrypt(d,rk,rounds))

returnres

Задание 4

а) Добавить в класс SPN1 метод asbox(), который выполняет обратную замену:

Можно использовать метод списка index().

def asbox(self,sx):

returnself.s.index(sx)

б) Обратная перестановка  реализована с помощью метода apbox() (рис.14).

Рисунок 14 – Обратная перестановка

Проверьте корректность выполнения обратной перестановки для      p = [2, 5, 6, 8, 4, 14, 0, 7, 11, 10, 12, 1, 15, 9, 3, 13]

в) Проверьте выполнение равенства , например, для  и .

import spn1       

x=15324

y=24681

e=spn1.SPN1()

x=15324

y=24681

s1=e.apbox(e.mix(x,y))

s2=e.mix(e.apbox(x),e.apbox(y))

if s1==s2: print('да')

else:print('нет')

Алгоритм расшифрования

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

Рисунок 15

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

Рисунок 16 – Расшифрование по схеме на рис.1

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