RC2

• Block length = 8 bytes
• Key length = from one byte up to 128 bytes

RC2 is a block symmetric cipher which was popular in the first half of the 90s of the last century. It was greatly promoted by the US government agencies.

Usage

RC2 was designed by Ron Rivest of RSA Security in 1987, who created also a few other ciphers. RC2 algorithm had been kept secret until 1996, when it was anonymously posted on sci.crypt group.

RC2 is also known as ARC2. The acronym RC is understood as "Rivest Cipher" or "Ron's Code".

Algorithm

RC2 is a block cipher, and the block size is 8 bytes (64 bits). This means that the input data is first divided into blocks of 8 bytes and then each of them is processed separately.

Each data block is treated as four words, each word has 16 bits (2 bytes). The array of four words is presented as R[0] R[1] R[2] R[3]. Both encryption and decryption take this array as input and modify the four words. The output is returned in the same array.

Key Expansion

Apart from the data, the RC2 cipher takes as input a secret user key. The key provided by the user may be of size from one byte up to 128 bytes. Let us denote the key size (in bytes) as Key_size. The first operation which RC2 then performs is to expand the key, to receive new 128 key bytes which will be used for encryption or decryption of all data bytes.

The user provides also a second value, denoted Key_bit-limit, which determines the maximum effective key size, provided in bits. This means, that no matter how many bytes of the secret key has been provided by the user, the cipher will operate on the key which effective size is Key_byte-limit, where:
Key_byte-limit = (Key_bit-limit + 7) / 8

Of course, the real strength of the key will be even smaller, if the user provided less key bytes than Key_byte-limit.

In order to assure that only that many bits will be used to secure the data, the following bit mask is defined:
Key_mask = 255 mod 2^(8 + Key_bit-limit - 8·Key_byte-limit)

The 8 - (8·Key_byte-limit - Key_bit-limit) least significant bits of Key_mask are set, the rest are zeros.

Key Words and Bytes

The mathematical operations that are performed on the key operate on both single bytes and whole words. So, for convenience, the numbers in the key may be presented as either 64 words:
K[0], K[1], ..., K[63]

or 128 separate bytes:
L[0], L[1], ..., L[127].

Note, that each part of the key array may be addressed by using either bytes or words. The following equation can be defined:
K[i] = L[2·i] + 256·L[2·i+1]

The low-order eight bits of each word is located before the high-order byte.

Key Expansion Algorithm

The first step of the key expansion algorithm is to fill the first Key_size bytes of key array with the bytes received from the user:
L[0], L[1], ..., L[Key_size-1].

Then, the following steps are performed on the key data. T_PI mentioned below is a fixed array of size 256, filled randomly with values from 0 to 255:

1. For i = Key_size, Key_size+1, and up until 127:
   L[i] = T_PI[(L[i-1] + L[i-Key_size]) mod 256]
2. L[128-Key_byte-limit] = T_PI[L[128-Key_byte-limit] & Key_mask]
3. For i = 127-Key_byte-limit, down until 0:
   L[i] = T_PI[L[i+1] XOR L[i+Key_byte-limit]]

The effective encryption key is determined by the bytes:
L[128-Key_byte-limit], L[128-Key_byte-limit+1]..., L[127]

The operation & performed in the second step above limits the effective size of the key down to just Key_bit-limit bits.

Encryption

The encryption procedure takes as input four words: R[0] R[1] R[2] R[3], which form one block of data. Every block of data will be encrypted by using the same 64 words of expanded secret key: K[0] K[1] ... K[63].

The following encryption steps are performed on every data block:

1. Initialize the counter j to 0.
2. Perform five Mixing Rounds.
3. Perform one Mashing Round.
4. Perform six Mixing Rounds.
5. Perform one Mashing Round.
6. Perform five Mixing Rounds.

Because every Mixing Round uses 4 key bytes, all 128 key bytes are used during encryption of one data block. The Mashing Rounds use key bytes in a more unpredicted manner.

Each Mixing Round consists of four Mixing operations, performed on four words of the data block:

1. Mixing R[0]
2. Mixing R[1]
3. Mixing R[2]
4. Mixing R[3]

Each Mashing Round consists of four Mashing operations, performed on four words of the data block:

1. Mashing R[0]
2. Mashing R[1]
3. Mashing R[2]
4. Mashing R[3]

Decryption

The decryption procedure takes as input four ciphertext words: R[0] R[1] R[2] R[3], which form one block of encrypted data. Every block of data will be decrypted by using the same 64 words of expanded secret key: K[0] K[1] ... K[63].

The following decryption steps are performed on every ciphertext block:

1. Initialize the counter j to 63.
2. Perform five R-Mixing Rounds.
3. Perform one R-Mashing Round.
4. Perform six R-Mixing Rounds.
5. Perform one R-Mashing Round.
6. Perform five R-Mixing Rounds.

Each R-Mixing Round consists of four R-Mixing operations, performed on four words of the encrypted data block:

1. R-Mixing R[3]
2. R-Mixing R[2]
3. R-Mixing R[1]
4. R-Mixing R[0]

Each R-Mashing Round consists of four R-Mashing operations, performed on four words of the encrypted data block:

1. R-Mashing R[3]
2. R-Mashing R[2]
3. R-Mashing R[1]
4. R-Mashing R[0]

Block Diagram of RC2 Encryption

Block Diagram of RC2 Decryption

Maths

The operations for RC2 algorithm are presented in the order from the low-level functions, to the more complex operations, that use the functions described above them.

Table PI (T_PI)

Table PI is a fixed array that contains 256 elements, used during key expansion operations.

Table PI is filled with numbers, which are a random permutation of all possible byte values from 0 to 255. The order of numbers is based on the digits of PI: 3.1415...

Binary Left Rotation: <<<

The a-bit left rotation of a 2-byte word w is denoted in the algorithm as w <<< a. The leftmost a bits move to the rightmost positions.

Binary Right Rotation: >>>

The a-bit right rotation of a 2-byte word w is denoted in the algorithm as w >>> a. The rightmost a bits move to the leftmost positions.

Mixing Operation

Mixing Operation modifies one data word and increments the counter j during encryption process.

The following three operations are performed during Mixing:
R[i] = R[i] + K[j] +
+ (R[(i+4-1) mod 4] & R[(i+4-2) mod 4])
+ ((~R[(i+4-1) mod 4]) & R[(i+4-3) mod 4])
j = j + 1
R[i] = R[i] <<< s[i]

where j is the counter variable and the vector s contains the following values: s[0] = 1, s[1] = 2, s[2] = 3, s[3] = 5.

Mashing Operation

Mashing Operation modifies one data word during encryption process.

The following operation is performed during Mashing:
R[i] = R[i] + K[R[(i+4-1) mod 4] & 63]

R-Mixing Operation

R-Mixing Operation modifies one ciphertext word and decrements the counter j during decryption process.

The following three operations are performed during R-Mixing:
R[i] = R[i] >>> s[i]
R[i] = R[i] - K[j]
- (R[(i+4-1) mod 4] & R[(i+4-2) mod 4])
- ((~R[(i+4-1) mod 4]) & R[(i+4-3) mod 4])
j = j - 1

where j is the counter variable and the vector s contains the following values: s[0] = 1, s[1] = 2, s[2] = 3, s[3] = 5.

R-Mashing Operation

R-Mashing Operation modifies one data word during decryption process.

The following operation is performed during R-Mashing:
R[i] = R[i] - K[R[(i+4-1) mod 4] & 63]