| Last Modified On : | May 7, 2008 12:33 AM PDT |
Rate |
|
Challenge
Optimize performance of the Advanced Encryption Standard (AES) algorithm for the Pentium® 4 processor. The Data Encryption Standard (DES) had served as an important cryptographic algorithm for over two decades. However, the growth of computing power during that time had compromised the security of that algorithm. There was considerable evidence that it was time to replace DES with a new standard. In October 2000, the National Institute of Standards and Technology (NIST) selected the Rijndael algorithm as the new encryption standard to replace the current DES algorithm. For further information on the selection process and AES itself see: CSRC - Cryptographic Toolkit*.
Antoon Bosselaers and Vincent Rijmen, who proposed Rijndael as the AES, wrote the following implementation of the Rijndael algorithm in the C programming language:
Antoon Bosselaers and Vincent Rijmen, who proposed Rijndael as the AES, wrote the following implementation of the Rijndael algorithm in the C programming language:
|
The array a contains 16 bytes of input text, the array b will contain the output and the array rk contains 16 bytes of key for each round of encryption. For 128-bit Rijndael encryption, the value of MAXROUNDS and ROUNDS will be 14 and 10, respectively. The array temp is the state table containing indexes into four fixed-sized, constant tables T1, T2, T3 and T4. Lines 7-10 calculate the initial value of the state table. Lines 12-26 perform the table lookups and the XOR operations to calculate the encrypted text for the first iteration, which also becomes the input to the next iteration. The state table for the next iteration is calculated in lines 29-32, which is used in lines 34-49 to calculate the encrypted text for that round.
Solution
Rearrange the code and hide dependencies. We will start optimizing the original C code shown in the Challenge section by rearranging the code. We will move lines 12-15 inside the for loop as shown below. This reduces the number of assignment statements, avoiding assignment to the temp array through the b array. Instead, we use the temp array to communicate between iterations of the loop.
Since the Pentium 4 processor can execute several instructions in parallel and out of the order they appear in the code, it is often useful to rearrange the code to let the processor start a long computation so that the result will be ready for later calculations that depend on it. This is often referred to as 'hiding the latency' of an instruction. The first four bytes of the encrypted text are available after the calculation in line 12. In order to hide the latency of instructions, we can start the operations of line 29 at line 12. In this way, we can avoid building a dependency chain that can interfere with the out-of-order and parallel execution in the processor. The modified code below includes changes to start computing the state table as soon as possible. It also partially unrolls the for loop:
Since the Pentium 4 processor can execute several instructions in parallel and out of the order they appear in the code, it is often useful to rearrange the code to let the processor start a long computation so that the result will be ready for later calculations that depend on it. This is often referred to as 'hiding the latency' of an instruction. The first four bytes of the encrypted text are available after the calculation in line 12. In order to hide the latency of instructions, we can start the operations of line 29 at line 12. In this way, we can avoid building a dependency chain that can interfere with the out-of-order and parallel execution in the processor. The modified code below includes changes to start computing the state table as soon as possible. It also partially unrolls the for loop:
|
Source
Comments (0)
Leave a comment
Name (required)
Email (required; will not be displayed on this page)
Your URL (optional)
Comment*
Email (required; will not be displayed on this page)
Your URL (optional)
Comment*
Search
- Entire Site
- Knowledgebase
- Forums
- Videos
- Blogs