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 MacDonald Rivest - one of the developers of the RSA system and the founders of the same company. By the number of users, RC5 is on a par with such well-known algorithms as IDEA and Blowfish. The abbreviation RC means, according to various sources, either Rivest Cipher or Ron's Code, which together gives us the “Ron Rivest code”. Interested, I ask for cat.

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
    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.

Also popular now: