![](https://habrastorage.org/files/6ba/a47/468/6baa474684cf46b9a5cdb8df9256d1ff.png)
Алгоритм RC5
В своём посте, я хотел бы рассказать о симметричном алгоритме шифрования RC5 и моей версии его реализации на python. Данный алгоритм разработан известнейшим криптологом Рональдом
Введение
При описании алгоритма будем использовать следующие обозначения:
- Размер слова
в битах. RC5 шифрует блоками по два слова; допустимыми значениями являются 16, 32 и 64. Данную величину рекомендуется брать равной машинному слову. Например для 32-битных машин
= 32 и следовательно размер блока будет равен 64 бита
- Количество раундов алгоритма
— целое число от 0 до 255 включительно. При значении 0 шифрование выполняться не будет
- Размер секретного ключа
в байтах — целое число от 0 до 255 включительно
Для уточнения параметров, используемых в конкретном случае применяется обозначение RC5-
![w/R/b](https://habrastorage.org/files/dd4/f15/5a0/dd4f155a07ab41e7897c736673315d4b.gif)
например, RC5-32/12/16 обозначает алгоритм RC5 c 64-битным блоком, 12 раундами шифрования и 16-байтным ключом(данная комбинация рекомендуется Ривестом в качестве основного варианта).
Работа алгоритма состоит из двух этапов:
- Процедура расширения ключа
- Само шифрование
Создадим класс и конструктор инициализирующий необходимые стартовые переменные
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 простеньких функции:
- Выравнивания ключа
- Инициализации массива расширенных ключей
- Перемешивания массивов ключей
Выравнивание ключа
Если размер ключа(в байтах) не кратен
![w/8](https://habrastorage.org/files/841/f89/820/841f898209ed4e65982fa3507c3d61b4.gif)
![w/8](https://habrastorage.org/files/841/f89/820/841f898209ed4e65982fa3507c3d61b4.gif)
![L[0]..L[c]](https://habrastorage.org/files/3d2/fae/eae/3d2faeeae4234504a669f0e335f87a0a.gif)
![c=w/8](https://habrastorage.org/files/297/0ce/6da/2970ce6daa7a46839defe962f142c1ee.gif)
![w/8](https://habrastorage.org/files/841/f89/820/841f898209ed4e65982fa3507c3d61b4.gif)
![w](https://habrastorage.org/files/7c1/26b/714/7c126b714976467f91143fd8cd0896e1.gif)
![L](https://habrastorage.org/files/95d/fc1/2ab/95dfc12ab992442d8e0baa9b59dbb76a.gif)
Например, при параметрах
![w=32, R=12, b=7](https://habrastorage.org/files/59a/ae5/40e/59aae540e7d14fb88a64e2ec6527e91e.gif)
![key=b'testkey'](https://habrastorage.org/files/977/272/06a/97727206a58c42b39aab7b1af18eb75b.gif)
![L[0]=b'test](https://habrastorage.org/files/45c/8f0/f76/45c8f0f7688347c0b903e4077dffa2a9.gif)
![L[1]=b'key\x00](https://habrastorage.org/files/62b/7c5/44c/62b7c544cee84108952cda1d41c449ef.gif)
Опишем необходимую функцию
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
Инициализация массива расширенных ключей
На этом шаге нам нужно сгенерировать псевдослучайные константы
![Pw](https://habrastorage.org/files/221/729/299/22172929927c44e78492510919530986.gif)
![Qw](https://habrastorage.org/files/87d/7bd/447/87d7bd4478a14e95b4018b58f8cbde70.gif)
![Pw=Odd((f-1)*2^w)](https://habrastorage.org/files/401/dff/ab7/401dffab738f4136ac0d7e8f754c5cb4.gif)
![Qw=Odd((e-2)*2^w](https://habrastorage.org/files/12e/daf/229/12edaf22966f4423934930647dab1197.gif)
где
![Odd](https://habrastorage.org/files/c59/d36/b94/c59d36b94cee44c6bee5d4cac3dc7bbf.gif)
![exp](https://habrastorage.org/files/ce9/9c0/021/ce99c0021628462caec8c946ede58d23.gif)
![f](https://habrastorage.org/files/2be/c16/22a/2bec1622a29549f7848bd142880bf544.gif)
Так же в спецификации алгоритма приведены уже вычисленные константы для всех возможных значений
![w](https://habrastorage.org/files/7c1/26b/714/7c126b714976467f91143fd8cd0896e1.gif)
![P16=B7E1](https://habrastorage.org/files/c8d/571/691/c8d5716915f243f2835f285b7d66e779.gif)
![](https://habrastorage.org/files/546/575/7ca/5465757ca0074b39b3c28c4e1b5fb4ce.gif)
![P32=B7E15163](https://habrastorage.org/files/18a/0ed/b20/18a0edb205c049dc981bdbed9504298d.gif)
![Q32=9E3779B9](https://habrastorage.org/files/c9c/5ac/713/c9c5ac7130734277b6d2b1b95d23b6b6.gif)
![P64=B7E151628AED2A6B](https://habrastorage.org/files/b7c/4d8/3ed/b7c4d83ed96049ba9bbbc4f260808593.gif)
![Q64=9E3779B97F4A7C15](https://habrastorage.org/files/4bf/d25/3c2/4bfd253c201047af81fc02579b8f360a.gif)
все константы представлены в шестнадцатеричном виде.
Получив всё необходимое мы инициализируем массив
![S[0]..S[2*r+1]](https://habrastorage.org/files/14c/031/840/14c0318409954c5299dfb5d47f23963f.gif)
![S[0]=Pw](https://habrastorage.org/files/412/214/c3b/412214c3bc3346a2a1a93a62eb4257ed.gif)
![S[i+1]=S[i]+Qw](https://habrastorage.org/files/8ba/b2a/76e/8bab2a76ef2c417f8f640af2c57e0180.gif)
Описание функций
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 выполнив следующий цикл:
![A=S[i]=(S[i]+A+A)<<<3](https://habrastorage.org/files/2c3/679/2ab/2c36792abd0643d0993a70bbbecba30c.gif)
![B=L[j]=(L[j]+A+B)<<<(A+B)](https://habrastorage.org/files/5eb/110/1f6/5eb1101f6b844bd689f89e7b59b6796d.gif)
![i=(i+1)mod(2*R+1)](https://habrastorage.org/files/d5c/802/7d5/d5c8027d5b354704b4ae8a96a409bfac.gif)
![j=(j+1)mod(c)](https://habrastorage.org/files/7c3/ee2/617/7c3ee2617e9d4618908d2b489af696f7.gif)
![i,j,A,B](https://habrastorage.org/files/ee8/f29/e84/ee8f29e843cf42afb91e4c5a56b5a497.gif)
![L,S](https://habrastorage.org/files/910/e20/582/910e20582dbf4209948fc6736599cb3c.gif)
Количество итераций
![N](https://habrastorage.org/files/06e/d7a/f42/06ed7af42295476eaa99fad335d5ed77.gif)
![N=3*max(c, 2*R+1)](https://habrastorage.org/files/a88/735/712/a8873571264b43b4b2626caca9b6dd5d.gif)
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(ссылка в конце)
Структура алгоритма
Шифрование
Алгоритм представляет собой сеть Фейстеля, в каждом раунде которой(за исключением нулевого) выполняются следующие операции:
![A=((A+B)<<<B)+S[2*r]mod2^w](https://habrastorage.org/files/062/12e/cda/06212ecda1674f018670146136481463.gif)
![B=((A+B)<<<A)+S[2*r+1]mod2^w](https://habrastorage.org/files/ae2/6e6/f33/ae26e6f3304b4f8dbe25893894c14473.gif)
где
![S[n]](https://habrastorage.org/files/8f9/c29/383/8f9c29383c5a48c58346a52f3f20b533.gif)
![<<<n](https://habrastorage.org/files/213/8f7/ed1/2138f7ed1bdd46eeb7393549f5661cd7.gif)
![n](https://habrastorage.org/files/805/dd5/53f/805dd553f8a541069d6eb5c511a49c25.gif)
В нулевом раунде выполняется операции наложения двух первых фрагментов расширенного ключа на шифруемые данные:
![A=(A+S[0])mod2^w](https://habrastorage.org/files/3ef/39f/3d0/3ef39f3d0e98473da28752fd8850aa44.gif)
![B=(B+S[1])mod2^w](https://habrastorage.org/files/57f/7b1/a8f/57f7b1a8f3e8495ea9de91b0467b94ff.gif)
Стоит отметить, что под раундом подразумевается преобразования, соответствующее двум раундам обычных алгоритмов, сконструированных на основе сетей Фейстеля. За раунд RC5 обрабатывает блок целиком, в отличии от раунда сети Фейстеля обрабатывающего один подблок — чаще всего половину блока.
Соответствующий код:
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)
Расшифровывание
Расшифровка данных выполняется применением обратных операций в обратной последовательности, т.е. сначала выполняем следующий цикл:
![B=(((B-S[2*r+1])mod2^w)>>>A)+A](https://habrastorage.org/files/255/df6/edb/255df6edbdd24c7ab507969c618719d2.gif)
![A=(((A-S[2*r])mod2^w)>>>B)+B](https://habrastorage.org/files/e50/a47/9e5/e50a479e53de4dffaaefaa941f9f629f.gif)
где
![>>>n](https://habrastorage.org/files/951/d3f/197/951d3f197a2f4ab993d02776d74edde6.gif)
![R](https://habrastorage.org/files/db6/2af/3df/db62af3df14d400d9a6fcb90aba772ec.gif)
После этого выполняются операции обратные для нулевого раунда, а именно:
![B=(B-S[1])mod2^w](https://habrastorage.org/files/b57/61d/ab0/b5761dab08b54b67b8e1cad5c2432b4c.gif)
![A=(A-S[0])mod2^w](https://habrastorage.org/files/2b2/755/9df/2b27559df7cf4e839ab3200800381b59.gif)
Код тут:
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 и по модулю
![2^w](https://habrastorage.org/files/788/48d/443/78848d443f704e81b1a2b1e2a402aec7.gif)
Код целиком можно посмотреть на github.
Немного криптоанализа
- Существует класс ключей при использовании которых алгоритм можно вскрыть линейным криптоанализом. В других случаях это почти невозможно.
- Дифференциальный криптоанализ более эффективен при атаке на данный алгоритм. Например, для алгорима RC5-32-12-16, в лучшем случае, требуется
выбранных открытых текстов для успешной атаки. При использовании 18-20(и больше) раундов вместо 12 вскрыть алгоритм с помощью дифференциального криптоанализа почти невозможно.
Таким образом, наиболее реальным методом взлома алгоритма RC5 (не считая варианты с небольшим количеством раундов и с коротким ключом) является полный перебор возможных вариантов ключа шифрования. Что означает, что у алгоритма RC5 практически отсутствуют недостатки с точки зрения его стойкости. На этом и хотелось бы закончить. Всем спасибо за внимание.
UPD: Изменены операции lshift, rshift. Добавленны константы в конструктор класса. Добавлены тесты.
Спасибо mas за советы и помощь.
Комментарии (8)
grossws
21.09.2015 22:07А что у него, кстати с патентной чистотой (был US patent в 1997 на RSA Data Security) и прочей копирастией (trade mark, другие ограничения)?
Также стоит информацию по патентну, лицензии на имплементацию и т. п. на github.
mas
22.09.2015 18:05+1В ...self.__lshift((self.S[i] + A + B),… или в самом __lshift (и __rshift), видимо, надо ограничить агрумент модулем 2**self.W, иначе значения S и L растут за пределы «слова». Ну и через строки работать, это конечно… эээ… попробуйте что-то вроде ((val<<n)|(val>>(self.W-n))) & self.MW для сдвига, где self.TW = 2**self.W # module и self.MW = self.TW-1 # mask. Лучше было, конечно, перевести прямо из С, который есть в people.csail.mit.edu/rivest/Rivest-rc5rev.pdf, Ну а так пока дальше будут вылезать ошибки для ключа из нулей, для файлов из нулей и т.д. И ещё, такие штуки надо обязательно проверять для стандартных тестовых наборов, если такие есть в описании алгоритмов. И лучше сделать encrypt и decrypt для одиночных блоков, а потом уже, используя их, для потоков (файлов) и байтовых строк.
Спасибо, однако, за статью. Хотя так и не понятно, рекомендуется ли RC5 и для каких применений, и насколько он распространён.tbb
22.09.2015 22:59Спасибо большое, отличная идея использовать & (теперь я чувствую себя неловко, потому что не догадался сам) и шифровать по блокам. Если честно, у меня мало опыта в разработке(особенно на Python), на днях дочитал «Изучаем Python» (Марк Лутц) и решил, что пора попробовать свои силы. Я думаю, в течении недели перепишу код и добавлю тесты, и сделаю апдейт статьи.
mas
23.09.2015 00:17Чем бы не заниматься, лишь бы не работой :) Довёл до какого-то рабочего состояния: С www.dropbox.com/s/52852xi7itrd6u0/RC5.c?dl=0 и Питон www.dropbox.com/s/krvs0iz4uf8x0ic/RC5.py?dl=0
hellman
08.10.2015 15:16+1> По количеству пользователей RC5 стоит в одном ряду с такими известными алгоритмами как IDEA и Blowfish.
Можно какие-нибудь ссылки, откуда инфа?
По поводу криптанализа — шифр взломан ещё в прошлом веке (с точки зрения академической криптографии), и с тех пор им почти никто не интересуется (опять же, среди криптоаналитиков). Поэтому утверждение
> у алгоритма RC5 практически отсутствуют недостатки с точки зрения его стойкости
слишком самоуверенно. Вы предлагаете 18-20 раундов для 32х битной версии (причем только как замечание в конце статьи), но вы не знаете какую стойкость эта версия гарантирует. 2^60? 2^70? Кроме того, «революционное решение» использовать переменные сдвиги очень сомнительное. Есть ли примеры не таких старых невзломанных шифров, использующих этот приём? А «поразительная простота» алгоритма, которая вас удивила, давно породила парадигму ARX шифров.
Я понимаю что статья про имплементацию чего попало на питоне, но почему бы не использовать для этого современные шифры?
grossws
tbb
Спасибо за замечание, исправил.