You get a bonus - 1 coin for daily activity. Now you have 1 coin

Cipher RC6, Algorithm Examples

Lecture



RC6
  Cipher RC6, Algorithm  Examples
Feistel network RC6 algorithm
Creator:

Ronald Raivest, M. Robshaw, R. Sydney (RSA Laboratories)

Created by:

1998

Published:

1998

Key size:

128, 192 or 256 bits (0 to 2040 bits)

Block size:

128 bits (for 32-bit platforms)

Number of rounds:

20 (default)

Type of:

Feistel Network

RC6 is a symmetric block cryptographic algorithm derived from the RC5 algorithm. It was created by Ron Rivest, Matt Robschaw and Ray Sydney to meet the requirements of the Advanced Encryption Standard Competition (AES). The algorithm was one of the five finalists of the competition, was also presented by NESSIE and CRYPTREC. It is a proprietary (proprietary) algorithm, and patented by RSA Security.

The RC6 cipher variant announced for the AES tender supports 128-bit blocks and 128, 192, and 256-bit keys, but the algorithm itself, like RC5, can be configured to support a wider range of lengths of both blocks and keys (from 0 up to 2040 bits) [1]. RC6 is very similar to RC5 in its structure and is also quite simple to implement.

It is an AES finalist, but one of the primitive operations is a multiplication operation that is slowly performed on some hardware and makes it difficult to implement the cipher on a number of hardware platforms and, which turned out to be a surprise for the authors, on systems with Intel IA-64 architecture is also rather poorly implemented. In this case, the algorithm loses one of its key advantages - high speed of execution, which was the reason for criticism and one of the barriers to being elected as a new standard. However, on systems with a Pentium II, Pentium Pro, Pentium III, PowerPC and ARM processor, the RC6 algorithm is ahead of the winner - Rijndael [2].

Content

  • 1Details RC6
  • 2 Key Expansion
  • 3 Encryption and decryption
    • 3.1 Encryption / Decryption with RC6-w / r / b
  • 4 Implementation of the RC6 algorithm in C #
  • 5Security
  • 6Evaluation of hardware
  • 7 Execution
  • 8Fibility and development directions
  • 9Licensing
  • 10Sources
  • 11Notes
  • 12 External links

RC6 Details

Like RC5, RC6 is a fully parameterized family of encryption algorithms. For the specification of the algorithm with specific parameters, the designation is RC6-w / r / b , where

  • w is the length of the machine word in bits.
  • r is the number of rounds.
  • b - key length in bytes. Possible values ​​are 0..255 bytes.

In order to comply with AES requirements, a block cipher must handle 128-bit blocks. Since RC5 is an exceptionally fast block cipher, expanding it to work with 128-bit blocks would result in using two 64-bit working registers. But the architecture and programming languages ​​do not yet support operations, so I had to change the project to use four 32-bit registers instead of two 64-bit ones.

Key extension

Constant generation:

As in RC5, two pseudo-random variables are generated in RC6 using two mathematical constants: exponent (e) and golden section (f).

{}   Cipher RC6, Algorithm  Examples

  Cipher RC6, Algorithm  Examples ,

where   Cipher RC6, Algorithm  Examples Is rounding to the nearest odd integer. When w = 32 bits (in hexadecimal):

  Cipher RC6, Algorithm  Examples

  Cipher RC6, Algorithm  Examples

Key expansion procedure for RC6-w / r / b:

The key table for the RC6 cipher is also identical to the RC5 cipher table. The difference is that a larger number of words from the array L is obtained from a user-provided key for use during encryption and decryption.

Entrance:

  • b-byte key specified by the user, previously converted into an array of   Cipher RC6, Algorithm  Examples words   Cipher RC6, Algorithm  Examples .
  • r is the number of rounds.

Output:

  • w-bit key table   Cipher RC6, Algorithm  Examples .
	 S [0] = Pw
	 for i = 1 to 2r + 3 do
    		 S [i] = S [i-1] + Qw

	 A = B = i = j = 0

	 v = 3 * max {c, 2r + 4}
	 for s = 1 to v do
    	 {
        	 A = S [i] = (S [i] + A + B) <<< 3
        	 B = L [j] = (L [j] + A + B) <<< (A + B)
        	 i = (i + 1) mod (2r + 4)
        	 j = (j + 1) mod c
    	 }

Encryption and decryption

RC6 works with four w-bit registers A, B, C and D, which contain input source text and output cipher text at the end of encryption.

Encryption / Decryption with RC6-w / r / b

Encryption procedure:

Entrance:

  • r number of rounds
  • w-bit keys for each round S [0, ..., 2r + 3]

Output:

  • the cipher text is saved in A, B, C and D

	 B = B + S [0]
	 D = D + S [1]
	 for i = 1 to r do
	 {
		 t = (B (2B + 1)) <<< lg w
		 u = (D (2D + 1)) <<< lg w
		 A = ((A ⊕ t) <<< u) + S [2i]
		 C = ((C ⊕ u) <<< t) + S [2i + 1] 
                 (A, B, C, D) = (B, C, D, A)

	 }
	 A = A + S [2r + 2]
	 C = C + S [2r + 3]

Decryption procedure:

Entrance:

  • cipher text stored in A, B, C and D
  • r number of rounds
  • w-bit keys for each round S [0, ..., 2r + 3]

Output:

  • source code is saved in A, B, C and D

	 C = C - S [2r + 3]
	 A = A - S [2r + 2]

	 for i = r downto 1 do
	 {
	    (A, B, C, D) = (D, A, B, C)
	     u = (D (2D + 1)) <<< lg w
	     t = (B (2B + 1)) <<< lg w
	     C = ((C - S [2i + 1]) >>> t) ⊕ u
	     A = ((A - S [2i]) >>> u) ⊕ t
	 }
	 D = D - S [1]
	 B = B - S [0]

Implementation of the RC6 algorithm in C #

In this implementation, the word size W = 32 bits is used, which corresponds to a block size of 128 bits. The number of rounds is R = 16. The key K is determined by the user independently. This implementation does not work.

 using System;
 using System.IO;
 using System.Collections.Generic;

 namespace RC6
 {
     class RC6
     {
         // Constants for swig operations
         public const int W = 32;
         public const int R = 16;

         // Variables for working with files
         public Byte [] fileData;
         public uint fileLength;

         // List of decrypted / decrypted data
         public List resultData = new List ();

         // Crypto key
         public UInt32 [] key = new UInt32 [2 * R + 4];

         // The function of writing data to a file
         public void WriteByteArrayToFile (Byte [] buffer, string fileName)
         {
             try
             {
                 FileStream fs = new FileStream (fileName, FileMode.Create, FileAccess.ReadWrite);
                 BinaryWriter bw = new BinaryWriter (fs);

                 for (int i = 0; i 

                 bw.Close ();
                 fs.Close ();
             }
             catch (Exception ex)
             {
                 // Omitted for implementation under different types of projects
             }
         }

         // Function of reading data from file
         public Byte [] ReadByteArrayFromFile (string fileName)
         {   
             Byte [] buffer = null;

             try
             {
                 FileStream fs = new FileStream (fileName, FileMode.Open, FileAccess.Read);
                 BinaryReader br = new BinaryReader (fs);

                 long numBytes = new FileInfo (fileName) .Length;
                 buffer = br.ReadBytes ((int) numBytes);

                 br.Close ();
                 fs.Close ();
             }
             catch (Exception ex)
             {
                 // Omitted for implementation under different types of projects
             }

             return buffer;
         }

         // right shift function
         public UInt32 RightShift (UInt32 z_value, int z_shift)
         {
             return ((z_value >> z_shift) | (z_value << (W - z_shift)));
         }

         // left shift function
         public UInt32 LeftShift (UInt32 z_value, int z_shift)
         {
             return ((z_value << z_shift) | (z_value >> (W - z_shift)));
         }

         // The function of determining the number of shifts
         public int OffsetAmount (int dwVar)
         {
             int nLgw = (int) (Math.Log ((double) W) / Math.Log (2.0));

             dwVar = dwVar << (W - nLgw);
             dwVar = dwVar >> (W - nLgw);

             return dwVar;
         }

         // Key generation function
         public void KeyGen (UInt32 dwKey)
         {
             UInt32 P32 = 0xB7E15163;
             UInt32 Q32 = 0x9E3779B9;
             UInt32 i, A, B;
             UInt32 dwByteOne, dwByteTwo, dwByteThree, dwByteFour;

             dwByteOne = dwKey >> 24;
             dwByteTwo = dwKey >> 8;
             dwByteTwo = dwByteTwo & 0x0010;
             dwByteThree = dwKey << 8;
             dwByteThree = dwByteThree & 0x0100;
             dwByteFour = dwKey << 24;

             dwKey = dwByteOne |  dwByteTwo |  dwByteThree |  dwByteFour;

             key [0] = P32;

             for (i = 1; i <2 * R + 4; i ++)
                 key [i] = key [i - 1] + Q32;

             i = A = B = 0;

             int v = 3 * Math.Max ​​(1, 2 * R + 4);

             for (int s = 1; s <= v; s ++)
             {
                 A = key [i] = LeftShift (key [i] + A + B, OffsetAmount (3));
                 B = dwKey = LeftShift (dwKey + A + B, OffsetAmount ((int) (A + B)));

                 i = (i + 1)% (2 * R + 4);
             }
         }

         // The function of converting the array UInt32 to the list of bytes
         public void ConvertFromUInt32ToByteArray (UInt32 [] array)
         {
             List results = new List ();

             foreach (UInt32 value in array)
             {
                 byte [] converted = BitConverter.GetBytes (value);
                 results.AddRange (converted);
             }

             // Formation of a list of encrypted / decrypted data bytes
             resultData.AddRange (results);
         }

         // The function of converting an array of bytes into an array of UInt32 (fitted to the current task)
         public UInt32 [] ConvertFromByteArrayToUIn32 (byte [] array, int position)
         {
             List results = new List ();
             // Size of the block of convertible data.  We read 16 bytes.
             int length = position + 16;                 

             for (int i = position; i 

                 for (int j = 0; j <4; ++ j)
                 {
                     if (i + j 

                 results.Add (BitConverter.ToUInt32 (temp, 0));
             }

             return results.ToArray ();
         }

         // File decryption function
         public void DecodeFile ()
         {
             UInt32 [] pdwTemp;

             for (int i = 0; i 

                 pdwTemp [1] = (pdwTemp [1] + key [0]);
                 pdwTemp [3] = (pdwTemp [3] + key [1]);

                 for (int j = 1; j <= R; j ++)
                 {
                     UInt32 t = LeftShift ((pdwTemp [1] * (2 * pdwTemp [1] + 1)),
                                         OffsetAmount ((int) (Math.Log ((double) W) / Math.Log (2.0))));
                     UInt32 u = LeftShift ((pdwTemp [3] * (2 * pdwTemp [3] + 1)),
                                         OffsetAmount ((int) (Math.Log ((double) W) / Math.Log (2.0))));

                     pdwTemp [0] = (LeftShift (pdwTemp [0] ^ t, OffsetAmount ((int) u)) + key [2 * j]);
                     pdwTemp [2] = (LeftShift (pdwTemp [2] ^ u, OffsetAmount ((int) t)) + key [2 * j + 1]);

                     UInt32 temp = pdwTemp [0];
                     pdwTemp [0] = pdwTemp [1];
                     pdwTemp [1] = pdwTemp [2];
                     pdwTemp [2] = pdwTemp [3];
                     pdwTemp [3] = temp;
                 }

                 pdwTemp [0] = (pdwTemp [0] + key [2 * R + 2]);
                 pdwTemp [2] = (pdwTemp [2] + key [2 * R + 3]);

                 // Convert to the output array of decrypted data
                 ConvertFromUInt32ToByteArray (pdwTemp);
             }

             pdwTemp = null;
         }

         // file encryption function
         public void EncodeFile ()
         {
             UInt32 [] pdwTemp;

             for (int i = 0; i 

                 pdwTemp [0] = (pdwTemp [0] - key [2 * R + 2]);
                 pdwTemp [2] = (pdwTemp [2] - key [2 * R + 3]);

                 for (int j = r; j> = 1; j--)
                 {
                     UInt32 temp = pdwTemp [3];
                     pdwTemp [3] = pdwTemp [2];
                     pdwTemp [2] = pdwTemp [1];
                     pdwTemp [1] = pdwTemp [0];
                     pdwTemp [0] = temp;

                     UInt32 t = LeftShift ((pdwTemp [1] * (2 * pdwTemp [1] + 1)),
                                         OffsetAmount ((int) (Math.Log ((double) W) / Math.Log (2.0))));
                     UInt32 u = LeftShift ((pdwTemp [3] * (2 * pdwTemp [3] + 1)),
                                         OffsetAmount ((int) (Math.Log ((double) W) / Math.Log (2.0))));

                     pdwTemp [0] = (RightShift ((pdwTemp [0] - key [2 * j]), OffsetAmount ((int) u))) ^ t;
                     pdwTemp [2] = (RightShift ((pdwTemp [2] - key [2 * j + 1]), OffsetAmount ((int) t))) ^ u;
                 }

                 pdwTemp [1] = (pdwTemp [1] - key [0]);
                 pdwTemp [3] = (pdwTemp [3] - key [1]);

                 // Convert Encrypted Data To Output Array
                 ConvertFromUInt32ToByteArray (pdwTemp);
             }

             pdwTemp = null;
         }
     }
 }

Security

The variant of the RC6 algorithm, which was declared on AES, as already mentioned, supports blocks of 128 bits in length and keys of 128, 192, and 256 bits in length, and also contains 20 rounds. That is, RC6-128 / 20 / b, where b = 128,192 or 256 bits. In relation to this algorithm, no attacks were detected. Only attacks against simplified versions of the algorithm, that is, an algorithm with a reduced number of rounds, were discovered.

It is believed that the best attack option on the RC6 available to the cryptanalyst is a complete brute-force search of the b-byte encryption key (or the extended key array S [0, ..., 43], when the user-provided encryption key is particularly long). The full search requires   Cipher RC6, Algorithm  Examples operations. Don Coppersmith remarked that due to the significant memory and preliminary calculations, it is possible to organize a “meet-in-the-middle” attack in order to restore the extended key array S [0, ..., 43]. This would require   Cipher RC6, Algorithm  Examples calculations and thus the required number of operations was equal to   Cipher RC6, Algorithm  Examples . More advanced attacks, such as differential and linear cryptanalysis, executable on cipher versions with a small number of rounds, are difficult to attack on the full RC6 cipher with 20 rounds. The difficulty is that it is difficult to find good repetitive features or linear approximations with which an attack could be carried out.

An interesting challenge is to set appropriate security targets against these more advanced attacks. To succeed, these attacks typically require large amounts of data, and obtaining {\ displaystyle 2 ^ {a}}   Cipher RC6, Algorithm  Examples blocks of known or selected encrypted / plaintext pairs - a task different from trying to return one key from {\ displaystyle 2 ^ {a}}   Cipher RC6, Algorithm  Examples possible. It is worth noting that with a cipher operating at a speed of one terabit per second (that is, encrypting data at a speed of {\ displaystyle 10 ^ {12}}   Cipher RC6, Algorithm  Examples bps), the time required for 50 computers running in parallel to encrypt {\ displaystyle 2 ^ {64}}   Cipher RC6, Algorithm  Examples data blocks, is over a year; encrypt {\ displaystyle 2 ^ {80}}   Cipher RC6, Algorithm  Examples data blocks are more than 98,000 years old; and encrypt {\ displaystyle 2 ^ {128}}   Cipher RC6, Algorithm  Examples data blocks is greater than {\ displaystyle 10 ^ {19}}   Cipher RC6, Algorithm  Examples years old.

Although data requirements for   Cipher RC6, Algorithm  Examples blocks for a successful attack could be considered as sufficient in practical terms, the developers sought to provide a much greater level of security.

RC5 research did not show weakness in key installation. This led to the use of the same key installation process in RC6. The process of converting a user-provided key to the key table seems to be well modeled by a pseudo-random process. Thus, while there is no proof that no two keys lead to the same key table, this seems very unlikely. This can be estimated as the probability that there are two 256-bit keys, resulting in the same table 44, 32-bit keys, there are approximately {\ displaystyle 2 ^ {2 * 256-44 * 32} = 2 ^ {- 896} = 10 ^ {- 270}}   Cipher RC6, Algorithm  Examples .

We can summarize our safety requirements for RC6 as follows:

- The best attack on RC6 is a complete brute-force encryption key provided by the user.

- Data requirements to organize more complex attacks on RC6, such as differential and linear cryptanalysis, exceed the available data.

An important criterion for the safety reserve is the maximum number of rounds at which an attack is possible. This is possible for 12, 14 and 15 round variants of the RC6.

Cipher Number of rounds (b) Attack type Text Memory bytes Operations
RC6-128 / 20 / b 12 Statistical differences   Cipher RC6, Algorithm  Examples   Cipher RC6, Algorithm  Examples   Cipher RC6, Algorithm  Examples
14 Statistical differences   Cipher RC6, Algorithm  Examples   Cipher RC6, Algorithm  Examples   Cipher RC6, Algorithm  Examples
15 (256) Statistical differences   Cipher RC6, Algorithm  Examples   Cipher RC6, Algorithm  Examples   Cipher RC6, Algorithm  Examples

The fourth column “Text” contains information on the number of unencrypted blocks and the corresponding ciphertext blocks corresponding to these keys. The fifth column, "Bytes of memory", contains the maximum number of bytes of memory that are needed at an arbitrary point of attack. The sixth column “Operations” indicates the expected number of operations that must be performed to launch an attack.

Hardware evaluation

For most applications, embedding RC6 in software is probably the best choice. The RC6 primitive operations (addition, subtraction, multiplication, excluding or offset) are very well supported by modern microprocessors and therefore it is advantageous to take this into account when developing these processors.

However, in some cases it is useful to have RC6 in the form of an embedded circuit. Then one could reach maximum speed or combine other functions around the RC6. Since RC6 uses the primitive operations described above, it is possible to take advantage of the existing verification when developing circuit modules for implementing these primitive operations. For example, if you implement RC6 using technologies based on matrices of logic elements, this will not bring the desired benefits because of the tremendous efforts that will need to be made to develop a multiplication circuit. The implementation based on this technology is significantly inferior to the implementation based on the processor. But this is not a typical situation and you can easily design a multiplication scheme that will be used as a submodule.

With 20 rounds per block, the encryption time is approximately 100 nanoseconds for each block, providing an estimated data transfer rate of approximately 1.3 Gbit / s.

Performance

As follows from the description of the algorithm, the RC6 is very compact. Indeed, the implementation of the RC6 algorithm in Assembler for the Intel Pentium Pro microprocessor can be implemented in less than 256 bytes of code for each of the tasks:

  1. key installation
  2. block encryption
  3. decryption unit.

Unlike many other encryption algorithms, the RC6 does not use reference tables during encryption. This means RC6 code and data can be placed in modern cache memory and thereby save memory space.

Given that RC6 is fully parameterized, and that it can be efficiently and compactly implemented, the cipher seems to be especially versatile.

Flexibility and development directions

As we have already noted, RC6 provides the user with greater flexibility regarding the size of the encryption key, the number of rounds and the word size of the main computing module.

While RC6, presented for review at AES, is based on the use of 32-bit words (128-bit block size), the future need of the market needs RC6 expansion for other block sizes. The most important are block sizes of 256 bits, which would use the word size of 64 bits and the performance offered by the next generation of system architecture. Also note that the RC6 structure allows exploiting a certain degree of parallelism in the decryption and encryption routines. For example, calculating t and u in each round can be computed in parallel, as are updates A and C. As processors evolve towards increasing the amount of internal parallelism (for example, moving to a superscalar architecture), RC6 implementations must demonstrate greater performance.

Licensing

Since RC6 was not chosen as AES, there is no guarantee that its use is free. Since January 2007, the webpage of the official RC6 developer RSA Laboratories website contains the following:

"We emphasize that if the RC6 is selected for the AES, we’ll emphasize that if RC6 is selected as AES, then RSA Security will not require any licensing or royalties for products using the algorithm ").

The highlighted word “if” means RSA Security Inc. can now require license and copyright payments for any product that uses the RC6 algorithm. RC6 is a patented encryption algorithm (US Patent 5,724,428 and US Patent 5,835,600).

Примеры

Block diagram RC6

  Cipher RC6, Algorithm  Examples

Encryption block diagram

  Cipher RC6, Algorithm  Examples

Decryption block diagram

  Cipher RC6, Algorithm  Examples

Flowchart for Encryption Блок-схема шифрования RC6 алгоритма

  Cipher RC6, Algorithm  Examples

Flowchart for Dencryption Блок-схема дешифрования RC6 алгоритма

  Cipher RC6, Algorithm  Examples


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Cryptographic ciphers

Terms: Cryptographic ciphers