Through the data storage of Rijndael encryption algorithm and the analysis of the characteristics of column mixing and wheel transformation, the author put forward some suggestions for the optimization of Rijndael. Meanwhile, the author design and realize the optimized Rijndael encryption through the SOPC (System on Program Chip). Based on the SOPC of Altera FPGA (Field Programmable Gata Array), the algorithm design is put forward and the center is the embedded soft core NiosII. It is also realized the encryption and decryption verification by using the ModelSim software. Compared with the traditional design, Rijndael encryption algorithm undergoes a great breakthrough. The author also evaluated the Rijndael encryption algorithm performance and logic resources occupation.
PDF Abstract XML References Citation
How to cite this article
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 doesnt 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(28) take inverse, zero 00 at inverse provisions for 00;
Second, the inverse again after the definition (at GF (2) affine transformation role:
|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:
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 (28) four dimensional vector α(x) = A3,jx3+A2,jx2+A1,jx+A0,j and GF (28) on a fixed polynomial c(x) = 03'x3+01'x2+01'x+02' do multiplication again to take mold x4+1, can use matrix representation is as follows:
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) = 0bx3+0dx2+09x+0e and d(x)c(x) = 01', the related matrix:
The above carry on the corresponding deformation:
Visible in parentheses is the column transformation, so use the existing column transformation code.
Simplify the rest of the part:
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:
|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 T0 to T3 as follows:
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 T01 [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:
|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):
The round key 'i' can be expressed as Eq. 13:
With 4x4 matrix that is Eq. 14:
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.
RESULTS AND DISCUSSION
According to the initial key (w (0), w (1), w (2) and w (3)), the key generator generates w (4)~w (43) automatically and stores them in the memory (complete the memory initialization).
|Fig. 3:||Module of key expansion circuit|
|Fig. 4:||Simulation of the Encryption algorithm|
In the period of round transformation, the quadruple frequency of the round clock is conducted by the frequency multiplier and the counting value is taken as the Look-up Table circuit address. Four Look-up tables are implemented in a round clock period and w4i+0 ~ w4i+3 are sent out. At the same time, the 128 bits round key is exported through the serial-in parallel-out shift register. The function description for the key generation circuit is conducted by VHDL and the generated module symbols are shown in Fig. 3.
In which, W0[31..0], W1[31..0] , W2[31..0] and W3[31..0]is the initial key, Key_load is loading the initial key, start is the beginning of the round key generation, key_data_out[127..0] is the output of Sub-key, key_over is the completion of round key generation. When the initial key is W0 = 173c4615, W1 = 29bd08a1, W2 = 123f4c55 and W3 = 9167ce16, the simulation result is presented in Fig. 4.
The design based on Altera EP2C35 chips is synthesized under the integrated environment of QUARTUSII9.0. The testing results are shown in Table 4. As can be seen, research the working frequency is 141 MHZ; the data flow is 1805 Mbps after improved. Compared with the results in literature (Table 4), the speed of data flow has been increased by 131% at least.
|Table 4:||The results of experiment|
The design has a clear superiority in speed and performance under the relatively low resource request. The study based on the on the optimization of the algorithm combined with the previous research about Amplify-and-Forward Cooperative Systems, can greatly improve the system performance (Tang and Wang, 2013).
According to the traditional Rijndael algorithm, this study proposes a realization of Rijndael algorithm more optimized solutions, this scheme will wheel transformation, key expansion algorithm with matrix said out, again to table query, using SOPC rich look-up table and storage resources to achieve the algorithm, the proposed algorithm reduced the complexity of the calculation. The testing results show that the design of the Rijndael algorithm based on "FPGA+NiosII" can achieve a higher data processing speed while it occupies relatively low resources. The design has a big breakthrough compared to the traditional realization based on FPGA.
The study is supported by the Natural Science Foundation of China (No. 61261036) and Natural Science Foundation of Xinjiang Province (No. 2013211A012).
- Babu, G.D., N.N. Anandakumar and D. Muralidharan, 2012. Countermeasures against DPA attacks on FPGA implementation of AES. J. Artif. Intell., 5: 186-192.
- Tang, J. and L. Wang, 2013. Non-combining incremental relaying protocol for amplify-and-forward cooperative systems. Inf. Technol. J., 12: 239-242.