RC5 encryption algorithm and its implementation in python

RC5 algorithm

In my post, I would like to talk about the RC5 symmetric encryption algorithm and my version of its implementation in python. This algorithm was developed by the most famous cryptologist Ronald Macdonald Rivest - one of the developers of the RSA system and the founders of the eponymous company. By the number of users, RC5 ranks with such well-known algorithms as IDEA and Blowfish. RC stands for, according to various sources, either Rivest Cipher or Ron's Code, which together gives us the “Ron Rivest cipher”. Interested please under the cat.

Introduction

In the description of the algorithm we will use the following notation:

• Word size in bits . RC5 encrypts in two word blocks; valid values ​​are 16, 32, and 64. This value is recommended to 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 - integer from 0 to 255 inclusive. If set to 0, encryption will not be performed.
• Secret key size in bytes - an integer from 0 to 255 inclusive

To clarify the parameters used in a particular case, the notation 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 work of the algorithm consists of two stages:

• Key Expansion Procedure
• Encryption itself

Create a class and constructor initializing the necessary starting variables.

Key Expansion Procedure

I propose to start with a stage that is a little more complicated, namely, with the key expansion procedure. For this we need to write 3 simple functions:

• Key alignment
• Extended key array initialization
• Shuffle arrays of keys

Key alignment

If the key size (in bytes) is not a multiple , we supplement it with zero bytes to the nearest multiple . 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 parameters and key value we'll get and (0 means zero byte).

We describe the necessary function

Initialization of the extended key array

In this step, we need to generate pseudo-random constants. and according to the following formulas:

,
Where
- rounding function to the nearest inappropriate
- Euler number
- golden ratio
')
Also in the specification of the algorithm are already calculated constants for all possible values. :





,
all constants are represented in hexadecimal.

Having got everything we need, we initialize the array. where



Feature Description

Stirring

Now, before proceeding to encryption, we need only mix the elements of the arrays L and S by executing the following cycle:



where
- temporary variables, initial values ​​are 0
- arrays obtained in the previous steps
Number of iterations defined as

Algorithm structure

Encryption

The algorithm is a network of its Feistel, in each round of which (with the exception of zero) the following operations are performed:

,
Where
- number of the current round, starting with 1
- extended key fragment
- cyclic shift operation on bits left

In the zero round, the operations of imposing the first two fragments of the extended key on the encrypted data are performed:



It is worth noting that a round means transformations, corresponding to two rounds of conventional algorithms designed on the basis of Feistel networks. For a round, RC5 processes the block as a whole, in contrast to the round of the Feistel network processing one sub-block - most often half of the block.

Corresponding code:

Decryption

Data decryption is performed by applying the inverse operation in reverse order We first perform the following cycle:

,
Where
- cyclic right shift operation
- the round number in the reverse order, i.e. beginning with and ending with a unit.

After this, the operations are reverse for the zero round, namely:



Code here:

The algorithm is strikingly simple - it uses only modulo 2 and modulo addition operations. 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 (prior to the RC5 algorithm, these were used only in the Madryga algorithm, which was not widely used) - a shift by a variable number of bits is a very simple operation, but 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 .

Bit of cryptanalysis

• There is a class of keys using which the algorithm can be opened by linear cryptanalysis. In other cases it is almost impossible.
• Differential cryptanalysis is more effective when attacking this algorithm. For example, for the algorithm RC5-32-12-16, at best, it is required selected clear texts for a successful attack. When using 18-20 (and more) rounds instead of 12, it is almost impossible to open the algorithm using differential cryptanalysis.

Thus, the most realistic method of cracking the RC5 algorithm (not counting the options with a small number of rounds and with a short key) is a complete search through the possible options for the encryption key. Which means that the RC5 algorithm has practically no flaws in terms of its durability. On this and I would like to finish. Thank you all for your attention.

UPD: Changed operation lshift, rshift. Added constants to the class constructor. Added tests.
Thank you mas for advice and help.