KR20050092698A - A small hardware implementation of the subbyte function of rijndael - Google Patents

Abstract

A small hardware implementation is provided for the Advanced Encryption Standard SubByte function that implements the affine transform and inverse transform in a single Affine- All transform using a multiplicative inverse ROM. The logic is greatly reduced and the maximum path delay is reduced compared to a multiplexor implementation and is slightly greater than a ROM implementation.

Description

Apparatus and method for executing subbyte functions of linedal block ciphers and apparatuses for encrypting and decrypting data {A SMALL HARDWARE IMPLEMENTATION OF THE SUBBYTE FUNCTION OF RIJNDAEL}

The present invention relates to the field of data encryption. The present invention relates, in particular, to apparatus and methods for small hardware implementation of subbyte functions represented in AES (Advanced Encryption Standard) algorithms or Rijndael Cipher (hereinafter referred to as AES / Rijndael). This content can be redesigned to work with reverse and normal processing.

The state of the art in the art provides hardware in which reverse cryptography can only partially reuse circuits that implement cryptography. For high speed networking processor and smart card applications, a very small (gate size) and high data rate (accommodating a payload of 9.6 Gbps beyond the optical carrier rate of 9953.28 Mbps of OC-192) is desirable.

AES / Rijndael is an integrated block cipher and is described in a proposal by Joan Daemen and Vincent Rijmen, issued March 9, 1999. The National Institute of Standards and Technology (NIST) approved AES / Rijndael as a cryptographic algorithm and published AES / Rijndael on November 26, 2001 (see Federal Information Processing Standard 197 or publication 197, known as "FIPS 197"). , Which is incorporated herein by reference. According to many secret key encryption / decryption algorithms, including AES / Rijndael, encryption / decryption is generally performed in a plurality of steps, known as iterations or rounds. This algorithm applies to the architecture of a data processing pipeline or pipelines. In each round, AES / Rijndael uses affine transformation and vice versa, along with other transformations that decrypt and encrypt the information. Encryption converts data into an unintelligible form called cipher text, and decryption converts the data back to its original form called plaintext.

The inputs and outputs to the AES / Rijndael algorithm consist of a sequence of 128 bits (each with a value of 0 or 1, respectively). These sequences are generally referred to as blocks, and the number of bits they contain is also referred to as the length of these sequences (see "FIPS 197", NIST, page 7). The basic unit of processing in the AES / Rijndael algorithm is a byte, which is a sequence of 8 bits processed as a single entity with the most significant bit (MSB) on the left. Internally, the operation of the AES / Rijndael algorithm is performed on a two-dimensional byte array called a state. This state consists of four bytes of rows each containing Nb bytes, where Nb is a block length divided by 32 (see "FIPS 197", NIST, page 9).

At the beginning of the cipher and reverse cipher (cipher and decryption), an array of input in bytes in ₀ , in ₁ , ... in ₁₅ is copied into the state array shown in FIG. 1. A cryptographic or inverse cryptographic operation is then performed for each byte in this state array, and then copied into the byte array out ₀ , out ₁ , ... out _15, where the final value is the output.

The sum of two elements in the finite field is achieved by adding the coefficients for the corresponding power in the polynomial for the two elements. This addition is performed by a Boolean exclusive XOR operation ("FIPS 197", NIST, see page 10). The binary representation of the addition of two bytes is:

(1.0)

In the polynomial expression, the multiplication in GF (2 ⁸ ) is consistent with the multiplication of the polynomial modulo 8th order polynomial. A polynomial cannot be abbreviated only if the divisor is 1 and itself. For the AES / Rijndael algorithm, this shorthand polynomial is as follows (see "FIPS 197", NIST, page 10).

(1.1)

A diagonal matrix where each diagonal element is 1 is called an identity matrix. The n × n unit matrix is represented by In.

(1.2)

If A and B are n × n matrices, and the following holds, they are inverses for each.

(1.3)

The transformation that consists of multiplication by matrix and addition of vectors is called affine transformation.

The SubByte () function of AES / Rijndael is a non-linear byte substitution that operates independently for each byte of the state using an S-box. This S-box is reversible and is produced by constructing two transforms.

1. Take the inverse of the product in the finite field GF (2 ⁸ ) described above. Element {00} is mapped to itself.

2. Apply the following affine transformations (for GF (2)).

(1.4)

In matrix form, the affine transform elements of the S-box can be expressed as follows ("FIPS 197", NIST, p. 16).

(1.5)

If this is implemented as a lookup table proposed by the AES / Rijndael proposal, a 256 entry ROM or multiplexer will be required. In order to implement the AES / Rijndael algorithm, 12 instances of this table will be required. The inverse of this matrix can be

(1.6)

If this is implemented as a lookup table proposed by the AES / Rijndael proposal, then a 128 entry, 16 bit word ROM or multiplexer will be required. In order to implement the AES / Rijndael algorithm, 12 instances of this table will be required.

1 illustrates a state array input and output ("FIPS 197", see NIST page 9).

2 shows a comparison of a look-up table (multiplexer) implementation of a prior art ROM and a subbyte function implemented with affine all of the present invention.

3 illustrates a lookup table or ROM used in the affine all transformation of the present invention.

4 shows a netlist of affine all combinatorial logic.

Thus, there is a need for a system and method that shares nearly all circuitry for affine conversion to reduce the number of gates. To achieve high data rates and small gate sizes, the maximum path must be designed not to be too long, and the gate size must be designed so that the design can be replicated to facilitate parallel processing without significantly increasing die size. As dies grow in size, cost and power consumption increase, resulting in a lower market value of the product. The present invention is directed to an apparatus and method for reducing gate size while slightly increasing maximum path delay. This reduces the size of the circuit, making it attractive for high data rate designs.

The affine and inverse affine transformation pairs of AES / Rijndael are reduced by one invention to one transformation, the Affine-All transform. In a preferred embodiment, the circuit performs both normal and inverse affine transformations with very little double logic. In this preferred embodiment, by implementing the affine all transformation with inverse ROM on the product, the logic is greatly reduced, and the maximum path delay is reduced compared to the implementation with multiplexers, although slightly larger than with ROM.

Thus, a preferred embodiment of the present invention employs read only memory (ROM) for the inverse of the product and employs reduced combinatorial logic for affine transformation. This implementation has a very small number of gates with similar maximum delay paths.

The present invention is based in part on the fact that from the last row each row of determinants (1.5) and (1.6) is shifted left by one bit from the previous row. In the present invention, the first row of each matrix is referred to as a "load pattern". Thus, the "load pattern" of the affine transformation matrix is {10001111} and the "load pattern" for the inverse affine transformation is {00100101}. Note that the number of zeros in each "load pattern is odd, and it is an important feature that the two transformations can be merged into one circuit in the system and method of the present invention.

If the two affine transformations are implemented as suggested by Daemen and Rijmen (see "FIPS 197") using an exclusive OR gate, the circuit equation becomes as follows.

Affine conversion

(1.7)

Note that each equation has an odd number of terms and five equal numbers of terms. The addition of the vector determines the negation of some equations. Thus, the number of terms in each equation is determined by the "rod pattern". The number of negations is determined by the addition of a vector called a "load vector".

Inverse Affine Conversion

(1.8)

Each equation has an odd number of terms and three identical terms. Addition of vectors determines the negation of some expressions. Thus, the number of terms in each equation is determined by the "rod pattern". The number of negations is determined by the addition of the vector.

This addition vector can also be used as a "load vector." Looking at the two sets of expressions, we can see that there is no common logic to merge. If these expressions are represented again with the included "load pattern" and use vector addition to determine negation, a common circuit will appear. The properties of exclusive OR are used to achieve this, and these properties are as follows.

(1.9)

(2.0)

(2.1)

(2.2)

In a preferred embodiment, the circuitry that implements both the affine transformation and the inverse affine transformation comprises an inverse ROM with respect to the product, and logic representing both transformations is defined as p as a "load pattern" and v as a "load vector" as follows. Have For example, the seven equations in the affine matrix are:

(2.3)

The number of instantiations was cut in half. Because of the zero generated by the addition of p and b, this equation applies to both affine and inverse affine transformations. Since b xed with 1 is always the inverse of b, using v ₇ each time negates this equation where appropriate.

compare:

Using the design proposed by the AES / Rijndael proposal (see FIPS 197) is implemented in two ways:

(1) 128-entry, 16-bit word ROM

(2) 16-bit word lookup table implemented as a 128-entry, multiplexer

ROM, multiplexer and affine all circuit embodiments of the present invention were synthesized and adjusted using maximum path analysis. Figure 2 compares the micron size with the ROM implementation for results and comparison given the size of the gate. The net area is not taken into account because the wiring rod model is technology dependent.

A preferred embodiment of a ROM or lookup table includes the value shown in FIG. 3 represented in hexadecimal.

The net list of affine all combinatorial logic of the preferred embodiment is shown in FIG. Code for implementation is included as Appendix A.

The present invention is applicable to all systems and devices capable of securely communicating, including secure networking processors, secure keyboard devices, magnetic card readers, smart card readers, and wireless 802.11 devices.

The above-described embodiments are merely exemplary and modifications and variations thereof will be apparent to those skilled in the art. Various modifications of the above-described embodiments can be made without departing from the scope of the invention as embodied in the appended claims.

Appendix A

Hereinafter, the RTL for implementing the affine all circuit is shown.

Claims (18)

In the apparatus that executes the SubByte function of the Rijndael Block Cipher, An S-box fabricated by configuring the first and second transforms, The first transform is a lookup table 300 and the second transform is an affine-all transformation that performs both affine and inverse affine transformations. Device that executes the subbyte function of the linedal block cipher. The method of claim 1, The lookup table 300 is the inverse of the product in the finite field GF 2 ⁸ with {00} mapped to it, The affine all transformation is implemented using combinational logic circuit 400. Device that executes the subbyte function of the linedal block cipher. The method of claim 2, The lookup table 300 is implemented by a read only memory (ROM), The combinational logic circuit 400 executes the following equation, Here, as a load pattern consisting of {10001111} for the affine transformation and {00100101} for the inverse affine transformation, p = p ₀ p ₁ p ₂ p ₃ p ₄ p ₅ p ₆ p ₇ , and the affine A load vector consisting of {11000110} for the transform and {10100000} for the inverse affine transform, with v = v ₀ v ₁ v ₂ v ₃ v ₄ v ₅ v ₆ v ₇ Device that executes the subbyte function of the linedal block cipher. In the data encryption and decryption apparatus, A data processing module configured to perform byte substitution, At least part of the data processing module Lookup table 300, A storage device for storing the lookup table; A circuit 400 having shared logic that performs a single transformation that performs either an affine transformation or an inverse affine transformation. Data encryption and decryption device. The method of claim 4, wherein The lookup table 300 is the inverse of the product of the finite field GF (2 ⁸ ). Data encryption and decryption device. The method of claim 5, The lookup table 300 is implemented by read only memory (ROM). Data encryption and decryption device. The method of claim 4, wherein The lookup table 300 is implemented by read only memory (ROM). Data encryption and decryption device. The method of claim 4, wherein The apparatus includes a plurality of instances of a data processing module disposed in the data processing pipeline. Data encryption and decryption device. The method of claim 4, wherein The apparatus is configured to perform encryption or decryption in accordance with a linedal block cipher, and the data processing module is configured to execute a Rijndael round. Data encryption and decryption device. The method of claim 9, The data processing module is configured to execute the subbyte conversion of a linedal round using the lookup table consisting of an affine transformation for encryption and an inverse affine transformation for decryption. Data encryption and decryption device. The method of claim 10, The lookup table 300 is implemented by read only memory (ROM). Data encryption and decryption device. A device for executing a subbyte function of a round of linedal block ciphers, Means for obtaining the inverse of the product in the finite field GF (2 ⁸ ), S-box fabricated by constructing means for performing affine transformations consisting of affine transformations and inverse affine transformations as a single affine transformation. Device that executes the subbyte function of the round of linedal block ciphers. The method of claim 12, The means for obtaining the inverse for the product is a lookup table 300 and the means for performing the affine all transformation is a combinational logic circuit 400. Device that executes the subbyte function of the round of linedal block ciphers. A method of executing a line-byte round subbyte function of a line-dal block cipher. Generating a lookup table 300 for the inverse for the product in the finite field GF (2 ⁸ ), Providing affine transformations consisting of affine transformations and inverse affine transformations into a single affine transformation, Manufacturing an S-box including the lookup table 300 and the affine all transformations; Performing non-linear byte substitution using the manufactured S-box. How to execute a subbyte function of the linedal round of a linedal block cipher. The method of claim 14, Providing the affine all transformations further comprises providing a shared logic circuit 400 for performing the single affine transformation. How to execute a subbyte function of the linedal round of a linedal block cipher. The method of claim 14, Storing the lookup table 300 in the read only memory (ROM). How to execute a subbyte function of the linedal round of a linedal block cipher. The method of claim 16, Providing the affine all transformations further comprises implementing a shared logic circuit 400 that performs the single affine transformation. How to execute a subbyte function of the linedal round of a linedal block cipher. The method of claim 14, The lookup table 300 is the inverse of the product in the finite field GF 2 ⁸ with {00} mapped to it, Providing the affine all transformations further comprises implementing a combinational logic circuit 400 that performs the single affine transformation. How to execute a subbyte function of the linedal round of a linedal block cipher.