1 introduction
Along with the cryptanalysis level, chip handling ability and computation technology’s unceasing progress, the DES working strength already with difficulty met the new safety requirement, it realizes the speed, the code size and the cross platform with difficulty continues to meet the application need. Therefore, NIST (US national standards and Technical research institute) prepare AES (high-level des) the algorithm, is for the purpose of substituting for DES, protects in the 21st century the sensitive government information new encryption standard. The Rijndael algorithm take its succinct, highly effective, the security and the principled design by the admission as AES, and in November 26, 2001 official announcement, in FIPS (Federal Information ProcessingStandards) publishes FIPS-PUB in 197. As the DES successor, AES since is admitted date of for the standard already by the industrial world, the banking industry and the Administrative department takes the password standard in fact.
Along with the network transmission speed promotion is the gigabits magnitude, the field carries out the speed request to the algorithm to be also getting higher and higher, then appears based on software’s crypto-algorithm the performance is insufficient, needs to use the hardware encryption the way, he uses some special optimization techniques (for example assembly line and search table and so on), but enhances the data enormously the current capacity and reduces key’s generated time. Moreover, realizes the encryption algorithm and with it related key production process with the hardware, and seals in the chip, because they are read not easily by the exterior aggressor or the change, will have the high physical security. Therefore, receives the field based on hardware’s crypto-algorithm the universal attention. As representative may restructure the hardware take FPGA - - both to have hardware’s security and high speed by its own inherent characteristic and has software’s flexibility and the easy maintenance, already became the hot spot research direction which the block cipher algorithm hardware realizes.
This article introduced AES encryption algorithm one kind of FPGA realizes method as well as to its encryption speed optimized processing skill.
2 AES encryption algorithm synopsis
AES is one kind of iterative block cipher, what uses replaces/permutation network (SPN). He the definite orders block length fixed is 128 b, moreover only supports 128,196 or 256 b key lengths, this article is only 128 b situations carries on the discussion to the key length.
AES encryption algorithm realization including key expansion process and encryption process. The encryption process includes an achievement initial wheel initial key addition (AddRoundKey), then carries on 9 wheels to transform (Round), finally uses a wheel to transform (FinalRound) again, as shown in Figure 1.
 |
Each Round by SubBytes, ShiftRows, MixColumns and the AddRoundKey altogether 4 step constitutions, FinalRound contains besides MixColumns this step other 3 steps, Round structure as shown in Figure 2.
 |
A round transformation and each step affects in the intermediate result, is called the condition this intermediate result, may the expression be a 4*4 B matrix vividly.
3 AES encryption algorithm optimization
3.1 bytes substitute (SubBytes)
Step SubBytes is in the Rijndael password the only non-linear transformation. He is a bricklayer replaces, this replacement contains an function in the status byte S- box, indicated with SRD, he is asks its multiplication by the byte in GF(28) territory counter and the sur- affine transformation (affine transformation function is complication S- box algebraic expression) realizes, supposition this step input is a, the output is b, namely b=SRD(a). Because this step is one kind non-linear face the byte transformation, is a 8 binary system data conversion for another different 8 binary data, here requests 11 correspondences, and the replace result cannot surpass 8, may realize through the structure reversible S- box.
According to the byte substitution’s request and the characteristic, when realizes specifically, may the S- box with a 16*16 B replacement table indicate that then realizes this step through the table look-up the transformation, has avoided the complex multiply operation.
3.2 lines move transform (ShiftRows)
ShiftRows is the linear transformation, he and row hybrid operation mutual influence, after the multiwheel transforms, enables the cryptographic information to achieve the full confusion, enhances non-linear.
A line of transformation is carries on condition each between the lines, is in the condition line carries on the rotate left operation according to the different displacement quantity, when the definite orders block length is 128 b, the key length is 128 b, ShiftRows shows to the condition each line of function like following expression:
 |
Obviously, may through realize this step simply to each byte shifting the transformation.
3.3 rows mixes transform (MixColumns)
MixColumns is the linear transformation, is by the condition the operation which lists as the unit to carry on. A supposition this step row input is a, the output is b, MixColumns to the condition each row function like following expression:
 |
The above matrix multiplication is in GF(28) galois field multiply operation, and has a factor is a constant. Because in GF(28) galois field’s each element could write 02 different powers time and (e.g.: 15=01○ 022 ○ 024), therefore, is multiplied by any constant multiplication to be possible through repeated to be multiplied by 02 and the “or else” realizes. May the matrix multiplication in constant factor decomposition be 02 different powers and, the matrix multiplication transforms into and 02 multiplications and the “or else”. GF(28) territory’s in each element with 02 product accumulations in 16*16 in the B search table, records makes xtime (?)(e.g.: 02*a=xtime(a)). Therefore, this step may realizes through the table look-up and the “or else”, the expression as follows (a supposition this step row input is a, output is b):
 |
3.4 key addition (AddRoundKey)
AddRoundKey is turns in the key each byte and in condition each byte by the position different or, realizes the password and key’s mix. Turns the key is obtains by the initial key through the key expansion.
3.5 keys expand (ExpandedKey)
Take the definite orders block length as 128 b, the key length is 128 b is the example, ExpandedKey (initial key may an image arrangement 4*4 B matrix) take the initial password key the initial key addition the key, the later each round wheel key is passes through (K[i][j which the following expression the key spread function obtains] to express that the initial key condition’s ith line of jth row, W[i][j] indicated after expanding, the key condition’s ith line of jth row, Nk expressed the key groups the enumeration, Nr expresses the round the number, Nb expresses the definite orders grouping enumeration, here Nk=4, Nr=10, Nb=4):
When Nk≤6:
 |
And, SRD (?)Is the S- box replacement table, RC(j/Nk) is a wheel constant, uses in eliminating the symmetry, may through look up a round constant the table to obtain.
Key’s selection: The ith round wheel key is gives from matrix W in the Nb*i row to the Nb*(i 1)-1 row.
3.6 running water line structures
The running water line structure is realizes in the flow to join the register and the corresponding logic circuit, divides the entire process into the around connected multistage entity, each first-level only completes data processing one step, a clock cycle completes the first-level data processing, then after the next clock arrives will process the data transfer gives first-level; After the first group of data enters the assembly line, passes through a clock cycle to transmit the second level, simultaneously the second group of data enters the bamboo bed mat first-level, the data formation advances in proper order. Enables in a clock to have at the same time many block data to process in all levels. Although after each group of data must pass through the entire assembly line, can obtain the final computed result, but takes the entire assembly line, each clock cycle can calculate group of results, therefore an average group of data nearly only need a clock cycle the time, raised the data processing speed greatly, has guaranteed the overall system by the high frequency work.
The assembly line technology enhances the volume of goods handled through the simultaneous working many block data’s methods, its price is hardware source increase. The running water line structure can only use in the non-feedback encryption pattern.
4 realize and the simulation
Overall system structure as shown in Figure 3. In the chart the heavy line represents the data line, the fine lace represents the pilot wire. The control signal enters from the input connection, the data and the key enter through the data bus, carries on the data transmission according to the control module, replaces the key and the encryption operation.
 |
May see from the 3rd analysis, the AES algorithm may through to the SRD table, the xtime table and the RC table inquiry and shifting which and the “or else” realizes through the combinatory logic realizes. These realized the method to replace the tedious multiply operation, raised the encryption speed.
Used the running water line structure to come simultaneous working many block data, enhanced the volume of goods handled.
The use wheel box number launches completely the split-ring structure, divides the wheel box number 4 levels of assembly lines, in wheel box number each step is first-level, and joins the register interim compound state between the level and the level the data to eliminate the competition, thus realized the wheel box to teach the internal complete running water, as shown in Figure 4.
 |
And, control signal sel1, sel2.sel3 does sel4 respectively is each first-level (each step data) processes whether to complete symbol.
In wheel box number’s exterior, takes each wheel box number in the exterior running water first-level, thus has realized outside the algorithm interior complete running water structure, as shown in Figure 5.
 |
And, control signal sel0~sel10 respectively is each round data processing whether to complete symbol.
Because uses the running water line structure only to be able to use in the non-feedback encryption pattern, what therefore the AES algorithm realizes the use is the telegraphic code book pattern (ECB) working.
Before the key expands this step places all encryption step, carries on. Inputs the initial key first again, then through realizes through the combinatory logic completes key’s expansion to the SRD table and the RC table’s inquiry and shifting which and the “or else”, and will save finally in a 176 B register. After the key expands completes carries on the later data encryption again, when carries on each round key law, will choose the round directly in this register the key.
In view of the AFS algorithm and the FPGA characteristic, uses to each step processing take the byte carries on the operation as the unit to the register the way. Toward QuartusII5.0, has realized this algorithm with the VHDL hardware description language, passes through the simulation, the result is as follows:
 |
5 expansions and application
Welcomes FPGA to realize the AES decipher algorithm (only to discuss block length in this is 128 b, key length is time 128 b situations), similarly may use the search table and the simple combinatory logic realizes. Considers use equal decipher algorithm not how many advantage, therefore selects the direct decipher algorithm, may use outside as before the wheel box number interior the complete running water assembly line technology to raise the decipher speed.
Attention:
in (1) decipher algorithm’s counter byte substitutes this step to be possible through to look up the counter SRD table to realize.
in (2) decipher algorithm goes against the flow moves transforms this step to be possible to realize directly the condition each line of shift right circular, if the following expression shows:
 |
Also after may the condition second line and the fourth line of exchange, carries on the encryption algorithm the line to move to the transformation, after will then transform again the condition second line and the fourth line of exchange realizes in the decipher algorithm to go against the flow moves transforms this step. This used in the encryption algorithm line to move to the transformation the module (this method only to be suitable in block length is 128 b situations).
in (3) decipher algorithm’s counter row mix transforms in this step, because the matrix multiplication’s coefficient is 09,0E,0B,0D, if the following expression shows (a supposition this step row input is a, output is b):
 |
May realizes through a pretreatment step and a row mix transformation step, processes the step like following expression to show (a is thick a row):
 |
This has used in the encryption algorithm row mix transformation module.
In simultaneously supports adds the decipher in the module, the key expansion and the key addition’s part may simultaneously use in these two kind of patterns, after the key expands the part only need input corresponding the muscle dense initial key, does with the encryption same key expansion, then arranges according to the wheel key’s order which the decipher needs to use, stores the register waiting use then, like this may the nurse resources.
From this, may unify the AES Canadian decipher algorithm, realizes in a FPGA module. Through processor’s and so on AVR or ARM controls choose FPGA are carry out the encryption process to decipher the process as well as whether to replace the new initial key, forms the complete Canadian decipher module, may take the independent cipher machine use or through each kind of connection and the computer, the labor controls machine and so on other master control device attachment to complete to the data Canadian decipher.
AES adds the decipher algorithm to be possible to apply in hypothesized domains and so on private network, SONET, remote access server, high speed ATM, ether router, mobile communication, satellite communication, electronic finance service, provides safely, reliable, the fast solution for it.
