Алгоритм RC5
В своём посте, я хотел бы рассказать о симметричном алгоритме шифрования RC5 и моей версии его реализации на python. Данный алгоритм разработан известнейшим криптологом Рональдом
Введение
При описании алгоритма будем использовать следующие обозначения:
- Размер слова
в битах. RC5 шифрует блоками по два слова; допустимыми значениями являются 16, 32 и 64. Данную величину рекомендуется брать равной машинному слову. Например для 32-битных машин = 32 и следовательно размер блока будет равен 64 бита - Количество раундов алгоритма
— целое число от 0 до 255 включительно. При значении 0 шифрование выполняться не будет - Размер секретного ключа
в байтах — целое число от 0 до 255 включительно
Для уточнения параметров, используемых в конкретном случае применяется обозначение RC5-
;например, RC5-32/12/16 обозначает алгоритм RC5 c 64-битным блоком, 12 раундами шифрования и 16-байтным ключом(данная комбинация рекомендуется Ривестом в качестве основного варианта).
Работа алгоритма состоит из двух этапов:
- Процедура расширения ключа
- Само шифрование
Создадим класс и конструктор инициализирующий необходимые стартовые переменные
Python listing
def __init__(self, w, R, key):
self.w = w
self.R = R
self.key = key
self.T = 2 * (R + 1)
self.w4 = w // 4
self.w8 = w // 8
self.mod = 2 ** self.w
self.mask = self.mod - 1
self.b = len(key)
self.__keyAlign()
self.__keyExtend()
self.__shuffle()
Процедура расширения ключа
Предлагаю начать с этапа, который немного сложней, а именно, с процедуры расширения ключа. Для этого нам понадобится написать 3 простеньких функции:
- Выравнивания ключа
- Инициализации массива расширенных ключей
- Перемешивания массивов ключей
Выравнивание ключа
Если размер ключа(в байтах) не кратен
, дополняем его нулевыми байтами до ближайшего размера кратного . После этого ключ копируется в массив 
, где 
. Проще говоря, мы копируем ключ блоками по байт (2, 4, 8 для значений 16, 32, 64 соответственно) в массив 
.Например, при параметрах
и значении ключа 
мы получим 
и 
(под 0 подразумевается нулевой байт).Опишем необходимую функцию
Python listing
def __keyAlign(self):
if self.b == 0: # пустой ключ
self.c = 1
elif self.b % self.w8: # ключ не кратен w / 8
self.key += b'\x00' * (self.w8 - self.b % self.w8) # дополняем ключ байтами \x00
self.b = len(self.key)
self.c = self.b // self.w8
else:
self.c = self.b // self.w8
L = [0] * self.c
for i in range(self.b - 1, -1, -1): # Заполняем массив L
L[i // self.w8] = (L[i // self.w8] << 8) + self.key[i]
self.L = L
Инициализация массива расширенных ключей
На этом шаге нам нужно сгенерировать псевдослучайные константы
и 
по следующим формулам:
,где
— функция округления до ближайшего нечентного
— число Эйлера
— золотое сечениеТак же в спецификации алгоритма приведены уже вычисленные константы для всех возможных значений
:
,все константы представлены в шестнадцатеричном виде.
Получив всё необходимое мы инициализируем массив
, где
Описание функций
Python listing
def __const(self): # функция генерации констант
if self.W == 16:
return (0xB7E1, 0x9E37) # Возвращает значения P и Q соответсвенно
elif self.W == 32:
return (0xB7E15163, 0x9E3779B9)
elif self.W == 64:
return (0xB7E151628AED2A6B, 0x9E3779B97F4A7C15)
def __keyExtend(self): # Заполняем массив S
P, Q = self.__const()
self.S = [(P + i * Q) % self.mod for i in range(self.T)]
Перемешивание
Теперь, перед тем как приступить к шифрованию, нам осталось лишь перемешать элементы массивов L и S выполнив следующий цикл:
, где
— временные переменные, начальные значения равны 0
— массивы полученные на предыдущих шагахКоличество итераций
определяется как 
Python listing
lshift и rshift(который встретится нам чуть ниже) это операции логического сдвига влево и вправо соответственно.
Я думаю, что их комментарии будут излишними, а код можно посмотреть на github(ссылка в конце)
def __shuffle(self):
i, j, A, B = 0, 0, 0, 0
for k in range(3 * max(self.c, self.T)):
A = self.S[i] = self.__lshift((self.S[i] + A + B), 3)
B = self.L[j] = self.__lshift((self.L[j] + A + B), A + B)
i = (i + 1) % self.T
j = (j + 1) % self.c
lshift и rshift(который встретится нам чуть ниже) это операции логического сдвига влево и вправо соответственно.
Я думаю, что их комментарии будут излишними, а код можно посмотреть на github(ссылка в конце)
Структура алгоритма
Шифрование
Алгоритм представляет собой сеть Фейстеля, в каждом раунде которой(за исключением нулевого) выполняются следующие операции:
,где
— фрагмент расширенного ключа
— операция циклического сдвига на 
битов влевоВ нулевом раунде выполняется операции наложения двух первых фрагментов расширенного ключа на шифруемые данные:
Стоит отметить, что под раундом подразумевается преобразования, соответствующее двум раундам обычных алгоритмов, сконструированных на основе сетей Фейстеля. За раунд RC5 обрабатывает блок целиком, в отличии от раунда сети Фейстеля обрабатывающего один подблок — чаще всего половину блока.
Соответствующий код:
Python listing
def encryptBlock(self, data):
A = int.from_bytes(data[:self.w8], byteorder='little')
B = int.from_bytes(data[self.w8:], byteorder='little')
A = (A + self.S[0]) % self.mod
B = (B + self.S[1]) % self.mod
for i in range(1, self.R + 1):
A = (self.__lshift((A ^ B), B) + self.S[2 * i]) % self.mod
B = (self.__lshift((A ^ B), A) + self.S[2 * i + 1]) % self.mod
return (A.to_bytes(self.w8, byteorder='little')
def encryptFile(self, inpFileName, outFileName): # в качестве параметров передаётся имя файла и открытым текстом и имя выходного файла
with open(inpFileName, 'rb') as inp, open(outFileName, 'wb') as out:
run = True
while run:
text = inp.read(self.w4)
if not text:
break
if len(text) != self.w4:
text = text.ljust(self.w4, b'\x00') # последняя считанная строка может быть меньше необходимого размера, что критичного для блочного шифра, поэтому мы дополняем её нулевыми байтами
run = False
text = self.encryptBlock(text)
out.write(text)
Расшифровывание
Расшифровка данных выполняется применением обратных операций в обратной последовательности, т.е. сначала выполняем следующий цикл:
,где
— операция циклического сдвига вправо и заканчивая единицей.После этого выполняются операции обратные для нулевого раунда, а именно:
Код тут:
Python listing
def decryptBlock(self, data):
A = int.from_bytes(data[:self.w8], byteorder='little')
B = int.from_bytes(data[self.w8:], byteorder='little')
for i in range(self.R, 0, -1):
B = self.__rshift(B - self.S[2 * i + 1], A) ^ A
A = self.__rshift(A - self.S[2 * i], B) ^ B
B = (B - self.S[1]) % self.mod
A = (A - self.S[0]) % self.mod
return (A.to_bytes(self.w8, byteorder='little')
+ B.to_bytes(self.w8, byteorder='little'))
def decryptFile(self, inpFileName, outFileName):
with open(inpFileName, 'rb') as inp, open(outFileName, 'wb') as out:
run = True
while run:
text = inp.read(self.w4)
if not text:
break
if len(text) != self.w4:
run = False
text = self.decryptBlock(text)
if not run:
text = text.rstrip(b'\x00') # удаляем добавленные на этапе шифрования b'\x00'
out.write(text)
Алгоритм поразительно прост — в нем используются только операции сложения по модулю 2 и по модулю
, а также сдвиги на переменное число битов. Последняя из операций представляется автором алгоритма как революционное решение, не использованное в более ранних алгоритмах шифрования (до алгоритма RC5 такие использовались только в алгоритме Madryga, не получившем широкого распространения), — сдвиг на переменное число битов является весьма просто реализуемой операцией, которая, однако, существенно усложняет дифференциальный и линейный криптоанализ алгоритма. Простота алгоритма может рассматриваться как его важное достоинство — простой алгоритм легче реализовать и легче анализировать на предмет возможных уязвимостей.Код целиком можно посмотреть на github.
Немного криптоанализа
- Существует класс ключей при использовании которых алгоритм можно вскрыть линейным криптоанализом. В других случаях это почти невозможно.
- Дифференциальный криптоанализ более эффективен при атаке на данный алгоритм. Например, для алгорима RC5-32-12-16, в лучшем случае, требуется
выбранных открытых текстов для успешной атаки. При использовании 18-20(и больше) раундов вместо 12 вскрыть алгоритм с помощью дифференциального криптоанализа почти невозможно.
Таким образом, наиболее реальным методом взлома алгоритма RC5 (не считая варианты с небольшим количеством раундов и с коротким ключом) является полный перебор возможных вариантов ключа шифрования. Что означает, что у алгоритма RC5 практически отсутствуют недостатки с точки зрения его стойкости. На этом и хотелось бы закончить. Всем спасибо за внимание.
UPD: Изменены операции lshift, rshift. Добавленны константы в конструктор класса. Добавлены тесты.
Спасибо mas за советы и помощь.