An Improved Rijndael Encryption Algorithm Based on NiosII

INTRODUCTION

As the new generation AES (Advanced Encryption Standard) cipher algorithm, the Rijndael algorithm has the advantages of high efficiency in implementation, low demand for storage and high speed of encryption and decryption (Liu et al., 2011; Zhang, 2007).The algorithm can be implemented through software as well as hardware. The software implementation is too slow although it is flexible. It is even more so with the block encryption algorithms getting more and more complex (Liang et al., 2011; Spillman, 2005). Besides, the security system is difficult to avoid the appearance of the key plaintext in the computer during the implementation through software, which may result in the plaintext being stolen or modified. On the contrary, the hardware implementation has the advantages of high speed, high reliability and much higher security, so that an increasing number of applications require the implementation through hardware (Zhang, 2008; Babu et al., 2012). The key of hardware implementation operates in the interior of module and the algorithm solidifies in the hardware, which can guarantee that the key of plaintext doesn’t flow outside and can achieve the true sense of confidentiality. The design based on "FPGA+NiosII" project, on the one hand, can configure CPU flexibly according to the application, on the other hand, it can realize the configuration of hardware logic directly in the FPGA interior (Liao and Chao, 2008; Cao, 2006). The software realization can be used for the peripheral device that has not so high demand for data transmission speed. While for the configuration that requires high speed, it can use the hardware interface to realize directly and then use the software to control it. In this study, the Rijndael algorithm is optimized comprehensively using Look-up Table and then the algorithm is designed systematically using "FPGA+NiosII" project (Lv, 2005; Wang, 2008).

OPTIMIZED DESIGN OF RIJNDAEL ALGORITHM

The discussion of data storage condition: The statement of Rijndael algorithm can be done as 4 bytes matrix. It is stored with the order of the priority list. As shown in Table 1a, A0~A15 represents the bytes stored in the matrix.

And in the most advanced languages, usually in the order of priority do store a two-dimensional array, so if in Table 1a to the order of the data storage, the access state of a list of the corresponding four times to visit. But if the matrix transpose store data form, as shown in Table 1b, the access state line (original one column) so only visit only once, so efficiency is greatly improved (Shen, 2006).

Optimization to realize S-box: Instead of table (or S-box) is reversible and is made up of two reversible transformation compound.

First, the finite field GF(2⁸) take inverse, zero 00 at inverse provisions for 00;

Second, the inverse again after the definition (at GF (2) affine transformation role:

(1)

Table 1(a-b):	Status data storage

Realize the affine transformation, to realize the require relatively large amount of computation, through the observation, finding that can carry on the transformation:

(2)

This can be done by cyclic shift to achieve.

Optimization to realize column hybrid: Column hybrid transformation is the state of the column as a finite field GF (2⁸) four dimensional vector α(x) = A_3,jx³+A_2,jx²+A_1,jx+A_0,j and GF (2⁸) on a fixed polynomial c(x) = ‘03'x³+‘01'x²+01'x+’02' do multiplication again to take mold x⁴+1, can use matrix representation is as follows:

(3)

Then:

(4)

Will be listed in the four bytes as 32 bytes α, the rest of the word on the level of byte cyclic shift and word multiplier operation (3α = 2α+α, namely 3α is multiplier and a plus combination) to achieve. Word of the multiplier is each byte elements by x (Muda et al., 2010).

Optimization to realize column hybrid inverse operation: The polynomial which need to modular multiplication among the column transformation of the inverse operation is d(x) = ‘0b’x³+‘0d’x²+‘09x’+0e and d(x)c(x) = ‘01', the related matrix:

(5)

The above carry on the corresponding deformation:

(6)

Visible in parentheses is the column transformation, so use the existing column transformation code.

Simplify the rest of the part:

(7)

So this part can be through the use of xor and multiply (the column left 1 byte) to achieve the efficiency and to realize the relative gets greatly improved.

Optimization wheel transformation: According to the literature, the whole wheel transformation on four column operation, each column operation involves bytes instead, line shift, column transformation and wheel key added:

(8)

Table 2(a-b):	Intermediate result state

Through the production of look-up table in the S-box search α_{i, j} for the above four vector S [α_{i, j}], defining table T₀ to T₃ as follows:

Then:

(9)

For Eq. 8 application addition (xor) exchange rates (Wang, 2008):

(10)

Equation 8, 10 corresponding as shown in Table 2a and (b) line shift after the state, (b) is (a) second, four lines transposition results.

Wrap in the state, there are three groups of continuous double byte (16 bits), i.e., A3 and A4, A7 and A8, A11 and A12, so each byte can all one-time access to, in the above Eq. (10) calculation, construct a table T₀₁ [ab] (a and b are 8 bits of bytes), corresponding to the above Eq. (10) of the first paragraph may also structure the table below:

(11)

Table 3:	The key of wheel change

The key is divided into groups according to the column of matrix and 40 new columns are added to expand. If the former four columns (i.e., the initial key) is w (0), w (1), w (2) and w (3), then the new column will produce in a recursive way. The column 'i' is determined by Eq. 12 (Babu et al.,2012):

(12)

The round key 'i' can be expressed as Eq. 13:

(13)

With 4x4 matrix that is Eq. 14:

(14)

If the initial key is w(0), w(1), w(2) and w(3), it can obtain w(4)~w(43) by Eq. 12. So the 10 round keys are composed of w(4)~w(43), as is shown in Table 3.

As can be seen from Table 3, if the initial key (w(0), w(1), w(2) and w(3)) is known, then the round key can be taken as a constant table and it can be implemented through Look-up Table circuit.

Although, need to use additional memory space to store structure form, but because the calculation of the process can be directly look-up table, the calculation efficiency has been greatly improved.

Rijndael algorithm based on niosII: The Rijndael algorithm based on the SOPC system is shown in Fig. 1. The standard Altera 32 bits NiosII embedded CPU provides guarantee for the large and systematic data processing. The system is composed of FPGA, memory and the external interface three parts.

Fig. 1:	Scheme of SOPC system based on FPGA

Fig. 2:	Design of optimized algorithm

In the system, the peripheral circuit and NiosII CPU Soft-Core are integrated to realize the control functions. As the control core of the system, the NiosII CPU Soft-Core needs a balance between its resource occupation and function when it is created. The demand of system resources is greatly reduced by the SOPC Builder customization for NiosII CPU. The FPGA part is built in the FPGA chip, the core is NiosII processor core. A lot of data need to be processed in algorithm, so the algorithm round transformation is completed by using NiosII processor core and the key generation is conducted by the key generator in FPGA. The external interface of FPGA is a part including some interface devices and circuit modules, which is used for data input / output and display and so on.

The design of optimized algorithm is shown in Fig. 2.