Introduction
The RC5 family of algorithms was devised by Ronald L. Rivest, one of the cryptographers behind RSA.
In the 1994 paper 'The RC5 Encryption Algorithm' which describing its working, it is described as:
'A fast symmetric block cipher suitable for software and hardware implementations'
This basically means that it is an iterative 'word' based cipher, which uses the same variable length key for both encryption and decryption, allowing it to run on various architectures, with no problems. The length of this word, alongside several other parameters enables you to affect the behaviour of RC5 in many ways, making it a highly flexible cipher system.
The first user selected parameter to be used as an input into this cipher is the length of input plaintext and the output ciphertext, w. Information is read into the algorithm in 2w length blocks. Usual values of w are 32, or 64. but there is no real restriction.
The second user selected parameter of RC5 is the number of rotations, r. Generally with this number the more the merrier, as this increases security, but as a side effect, also impacts the processing time. A commonly accepted minimum value for r is 12, but theoretically 0<=r<=255
In addition to this RC5 also uses two other values to represent the secret key
K, and its length in bits denoted by
b.
The choice of these values also has the secondary effect of setting other values used by the algorithm, These 'variations' in parameterisation within the algorithm are denoted by writing the information down RC5-w/r/b. It is also suggested that a control block is included , containing the values of v,w,r,b and K whre v is the version number.
One of the more interesting features of this algorithm is that it was apparently one of the first to use a data dependent rotation, where one of word of the intermediate results is rotated by and amount dependent on another intermediate result.
The algorithm itself consists of three subsections:
- The key expansion algorithm
- The encryption algorithm
- The decryption algorithm
Each of these algorithms use just three operations and their inverses. These are:
- twos complement addition (+). The inverse operation is denoted by (-)
- Bitwise XOR (XOR)
- A left-rotation of a word, i.e. the cyclic rotation of word x left by y bits (<<<). The inverse rotation denoted by >>> is also used
The encryption algorithm
We assume that the key-expansion algorithm has already been been run.
A = A + S [0];
B = B + S [1];
for i=1 to r do
A = ((A XOR B) << B) + S [2*i];
B = ((B XOR A) <<< A) + S [2*i+1];
The output of this algorthm is register A and B.
The decryption algorithm
This is derived from the encryption algorithm.
For i=r downto 1 do
B = ((B - S [ 2*i+1 ] ) >>> A) XOR A ;
A = ((A - S [ 2*i ] ) >>> B) XOR B ;
B = B - S[0];
A = A - S[1];
The Key-expansion algorithm
This involves taking the users secret key K and expanding it to fill the expanded key array S in a seeming 'random' manner. An interesting thing to note is that t, the size of S, the key table is dependant upon r, the number of rounds of encryption used such that S contains t=2(r+1) words
The key-expansion algorithm depends on two w sized 'magic' constants, P and Q where
- Pw = Odd ((e - 2)2w) and
- Qw = Odd ((ø - 1)2w)
where
e is the base of the
natural logarithms, ø is the
golden ratio, and where Odd(
x) is the odd
integer closest to
x
The first step of this section of the cipher is to initialise the array Lof size c-1, where c= (b/(w/8)), by copying in the contents of K
Next L is then set to a pseudo-random bit pattern as follows:
S[0] = Pw;
for i = 1 to t-1 do
S[i] = S[i - 1] + Qw i
The next step is mixing in the users private key, by passing over the arry 3 times over the two arrays S and L in the following manner.
i = 0;
j = 0;
A = 0;
B = 0;
for 3 * max (t, c) times
A = S[i] = (S[i] + A + B) <<< 3;
A = L[i] = (L[i] + A + B) <<< (A + B);
i = (i +1) mod (t);
j = (j +1) mod (c);
Improvements have been made to this basic algorithm to counteract
avalanche effect and
avoid weak-keys. This variant of the algorithm is known as
RC6.
Sources include:
Rivest, Ronald L. - The RC5 Encyrption Algorithm (1994)