RC5 encryption algorithm and its implementation in python
RC5 Algorithm
In my post, I would like to talk about the symmetric RC5 encryption algorithm and my version of its implementation in python. This algorithm was developed by the famous cryptologist Ronald
Introduction
When describing the algorithm, we will use the following notation:
- The word size in bits . RC5 encrypts in blocks of two words; valid values are 16, 32, and 64. It is recommended that this value be taken equal to the machine word. For example, for 32-bit machines = 32, and therefore the block size will be 64 bits
- The number of rounds of the algorithm is an integer from 0 to 255 inclusive. If set to 0, encryption will not be performed.
- The size of the private key in bytes is an integer from 0 to 255 inclusive
To clarify the parameters used in a particular case, the designation RC5- is used ;
for example, RC5-32 / 12/16 denotes the RC5 algorithm with a 64-bit block, 12 rounds of encryption and a 16-byte key (this combination is recommended by Rivest as the main option).
The operation of the algorithm consists of two stages:
- Key Extension Procedure
- Encryption itself
Create a class and constructor initializing the necessary start variables
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()
Key Extension Procedure
I suggest starting with a step that is a bit more complicated, namely, with the key expansion procedure. To do this, we need to write 3 simple functions:
- Key alignment
- Initializing an Extended Key Array
- Key Array Shuffling
Key alignment
If the size of the key (in bytes) is not a multiple , add it with zero bytes to the nearest multiple size . After that, the key is copied to the array , where . Simply put, we copy the key in blocks of bytes (2, 4, 8 for values 16, 32, 64, respectively) into an array .
For example, with the parameters and value of the key, we get and (by 0 we mean zero byte).
We describe the necessary function
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
Initializing an Extended Key Array
In this step, we need to generate a pseudo-random constants , and using the following formula:
,
where
- rounding to the nearest nechentnogo function
- Euler's number
- the golden section
Also in the algorithm specification already given constants calculated for all possible values :
,
all constants are represented in hexadecimal.
Having received everything we need, we initialize the array , where the
Description of functions
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)]
Stirring
Now, before proceeding with encryption, we only need to mix the elements of the arrays L and S by executing the following cycle:
where
- temporary variables, the initial values are 0
- arrays obtained in the previous steps The
number of iterations is determined as
Python listing
lshift and rshift (which we will see below) are logical left and right shift operations, respectively.
I think their comments will be redundant, and the code can be viewed on github (link at the end)
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 and rshift (which we will see below) are logical left and right shift operations, respectively.
I think their comments will be redundant, and the code can be viewed on github (link at the end)
Algorithm structure
Encryption
The algorithm is a Feistel network, each round which (except for zero) perform the following operations:
,
where
- the current round number from 1
- a fragment of the extended key
- the operation of cyclic shift on the bits to the left
in the zero round performed blending operation the first two fragments extended key for encrypted data:
It is worth noting that a round is understood as a conversion corresponding to two rounds of conventional algorithms constructed on the basis of Feistel networks. For a round, RC5 processes the entire block, in contrast to the Feistel network round processing one sub-block - most often half the block.
Relevant Code:
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)
Decryption
Data decryption is performed using reverse operations in the reverse order, i.e. first perform the following cycle
,
wherein
- the cyclic shift operation to the right
- the round number in reverse order, i.e. starting with and ending with a unit.
After that, the operations are performed inverse for the zero round, namely:
Code here:
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)
The algorithm is amazingly simple - it uses only addition operations modulo 2 and modulo , as well as shifts by a variable number of bits. The last of the operations is presented by the author of the algorithm as a revolutionary solution that was not used in earlier encryption algorithms (before the RC5 algorithm, these were used only in the Madryga algorithm, which was not widely used), shifting by a variable number of bits is a very simple operation, which, however, significantly complicates the differential and linear cryptanalysis of the algorithm. The simplicity of the algorithm can be considered as its important advantage - a simple algorithm is easier to implement and easier to analyze for possible vulnerabilities.
The whole code can be viewed on github .
A bit of cryptanalysis
- Существует класс ключей при использовании которых алгоритм можно вскрыть линейным криптоанализом. В других случаях это почти невозможно.
- Дифференциальный криптоанализ более эффективен при атаке на данный алгоритм. Например, для алгорима RC5-32-12-16, в лучшем случае, требуется выбранных открытых текстов для успешной атаки. При использовании 18-20(и больше) раундов вместо 12 вскрыть алгоритм с помощью дифференциального криптоанализа почти невозможно.
Thus, the most realistic method of hacking the RC5 algorithm (not counting the options with a small number of rounds and with a short key) is a exhaustive search of the possible encryption key options. Which means that the RC5 algorithm has practically no drawbacks in terms of its durability. On this and I would like to finish. Thank you all for your attention.
UPD: Changed operations lshift, rshift. Constants added to the constructor of the class. Added tests.
Thanks mas for the advice and help.