19-03-2014, 10:17 AM
HIGH SPEED VLSI IMPLEMENTATION OF THE RIJNDAEL ENCRYPTION ALGORITHM
[attachment=60220]
ABSTRACT
This thesis study presents a high speed VLSI implementation of the Rijndael
Encryption Algorithm, which is selected to be the new Advanced Encryption
Standard (AES) Algorithm. Both the encryption and the decryption algorithms of
Rijndael are implemented as a single ASIC. Although data size is fixed to 128 bits
in the AES, our implementation supports all the data sizes of the original Rijndael
Algorithm. The core is optimised for both area and speed. Using 149K gates in a
0.35-μm standard CMOS process, 132 MHz worst-case clock speed is achieved
yielding 2.41 Gbit/s non-pipelined throughput in both encryption and decryption.
INTRODUCTION
Cryptography is a Greek word that means to write secrets. Throughout history,
hiding secrets has played an important role in people’s lives.
Especially the
importance of encryption for military purposes has been a strong driving force for
cryptography. Cryptanalysis is the art of breaking into secure communications and
understanding their contents.
The combination of the cryptography and the
cryptanalysis is commonly referred to as cryptology. The ongoing competition
between code writers and code breakers has resulted in many advances in the field
of cryptology.
The growing of the Internet at the last decade has led to an increase in the
importance of cryptography. Internet applications such as electronic commerce and
electronic communication have made cryptography an essential tool.
In fact,
cryptography is used in a wide range of applications including digital signature,
authentication and commanding purposes.
In these applications, two forms of
cryptography are commonly used. These are symmetric key algorithms and public
key algorithms, also referred to as ciphers. In symmetric key ciphers, one secret key
is used for both encryption and decryption. In public key ciphers, two keys are
used. The first one, known as the public key, is not secret and openly available and
is used for encryption. The second key, known as the private key is secret and is
used for decryption.
Mathematical Preliminaries
In Rijndael Algorithm, most of the operations are done at byte level. These bytes
can be considered as elements of Galois Field (28), which is an extension field of
Galois field (2) having elements of {0,1}. A sequence of 8 bits from Galois Field
(2) forms an element in Galois Field (28). These 8 bit elements could be represented
in polynomial notation. A byte consisting of elements [ b7 b6 b5 b4 b3 b2 b1 b0 ] is
represented as b7 x7 + b6 x6 + b5 x5 + b4 x4 + b3 x3 + b2 x2 + b1 x1 + b0 x0 in
polynomial notation, where bi ∈ {0,1}. There are two operations in Galois Field
(28), namely addition and multiplication, which are different from conventional
addition and multiplication.
These operations are explained in the next two
sections.
The Rijndael Cipher
Rijndael is a symmetric key block cipher. The term symmetric key means that there
is only one secret key, which is used for both encryption and decryption. The term
block cipher means that the data to be ciphered is processed in blocks of constant
length. The output, named ciphered text, has same length as the input. The data
before ciphering is called plaintext. The encryption algorithm has constant key and
plaintext sizes that can be independently chosen as 128, 192 or 256 bits. These bits
can be considered as an array consisting of 8 bits. There are 4 rows in this array and
the number of columns, denoted by Nb, can be 4, 6 or 8 depending on the plaintext
and the key length. Figure 2.1 shows an example array corresponding to a key size
of 192 bits.
The ShiftRow Transformation
The ShiftRow Transformation is a cyclical shift operation that is applied to the rows
of the inner state and consists of the shifting of the rows by different offsets which
depend on the data block length Nb. The first row is not shifted; the second row is
shifted over 1 byte to the left. The third row is shifted over 2 bytes, if the block
length is 128 or 192 bits, and it is shifted over 3 bytes, if the block length is 256 bits.
The fourth row is shifted over 3 bytes if the block length is 128 or 192 bits, and it is
shifted over 4 bytes if the block length is 256 bits. Table 2.1 shows the offset values
as a function of the block length.
Key Schedule
The round keys are obtained from the initial cipher key, which can be 128, 192 or
256 bits long. The length of the plaintext determines how many bits are needed at
each round. For example, if Nk = 4, that is the cipher key is 128 bits long, and Nb =
6, that is the plaintext is 192 bits long, then there are 12 rounds specified by the
algorithm. In each round, a 192-bit key is needed, and another 192 bits are needed
for the initial key addition, so we need a total of 12 * 192 + 192 = 2496 bits to
complete the encryption.
DIFFERENT RIJNDAEL PROCESSOR IMPLEMENTATIONS
Both academia and industry have focused on the efficient implementation of the
new AES algorithm. There are many publications involving FPGA, ASIC, and
software implementations.
An ASIC implementation and its experimental results are presented by Henry Kuo,
Ingrid Verbauwhede and Patrick Shaumont in [5], [6] and [7]. In this study, a
Rijndael encryption core having a non-pipelined encryption data path is presented.
This chip has on-the-fly key schedule data path.
This means, the round keys
necessary for the encryption are calculated at every round. No pre calculation and
storage is needed for this case. However, for some data-key sizes, 2 round keys
must be prepared in the same clock period. This significantly increases the critical
length and decreases the overall speed of the chip.
The chip architecture of this Rijndael IC is shown in Figure 3.1 [5]. There is an
encryption module, a processor for controlling the operations, two 256-bit data
buffers for input and output data storage, two key scheduling modules to generate
the required keys necessary for each round and two Finite State Machines (FSM’s)
controlling the input and output data interface.
Key Generator Module
The Key Generator Module is responsible for generating the round keys and
supplying these keys to the Decryption and Encryption Modules.
The Key
Generator Module is composed of 3 sub-modules. They are the Key Expansion
Module, the Key Storage Module and the Key Selection Module. All the keys
needed for encryption and decryption are generated by Key Expansion Module and
they are stored in the Key Storage Module.
On the fly key generation is a method, which produces the keys needed for a round
at every clock and does not store all the keys in a register. This decreases the
number of the registers needed for the key generation. However, it is not practical
for implementations of encryption and decryption modules supporting all key and
data sizes of the Rijndael Algorithm. It may be good for implementations that make
encryption only.
[attachment=60220]
ABSTRACT
This thesis study presents a high speed VLSI implementation of the Rijndael
Encryption Algorithm, which is selected to be the new Advanced Encryption
Standard (AES) Algorithm. Both the encryption and the decryption algorithms of
Rijndael are implemented as a single ASIC. Although data size is fixed to 128 bits
in the AES, our implementation supports all the data sizes of the original Rijndael
Algorithm. The core is optimised for both area and speed. Using 149K gates in a
0.35-μm standard CMOS process, 132 MHz worst-case clock speed is achieved
yielding 2.41 Gbit/s non-pipelined throughput in both encryption and decryption.
INTRODUCTION
Cryptography is a Greek word that means to write secrets. Throughout history,
hiding secrets has played an important role in people’s lives.
Especially the
importance of encryption for military purposes has been a strong driving force for
cryptography. Cryptanalysis is the art of breaking into secure communications and
understanding their contents.
The combination of the cryptography and the
cryptanalysis is commonly referred to as cryptology. The ongoing competition
between code writers and code breakers has resulted in many advances in the field
of cryptology.
The growing of the Internet at the last decade has led to an increase in the
importance of cryptography. Internet applications such as electronic commerce and
electronic communication have made cryptography an essential tool.
In fact,
cryptography is used in a wide range of applications including digital signature,
authentication and commanding purposes.
In these applications, two forms of
cryptography are commonly used. These are symmetric key algorithms and public
key algorithms, also referred to as ciphers. In symmetric key ciphers, one secret key
is used for both encryption and decryption. In public key ciphers, two keys are
used. The first one, known as the public key, is not secret and openly available and
is used for encryption. The second key, known as the private key is secret and is
used for decryption.
Mathematical Preliminaries
In Rijndael Algorithm, most of the operations are done at byte level. These bytes
can be considered as elements of Galois Field (28), which is an extension field of
Galois field (2) having elements of {0,1}. A sequence of 8 bits from Galois Field
(2) forms an element in Galois Field (28). These 8 bit elements could be represented
in polynomial notation. A byte consisting of elements [ b7 b6 b5 b4 b3 b2 b1 b0 ] is
represented as b7 x7 + b6 x6 + b5 x5 + b4 x4 + b3 x3 + b2 x2 + b1 x1 + b0 x0 in
polynomial notation, where bi ∈ {0,1}. There are two operations in Galois Field
(28), namely addition and multiplication, which are different from conventional
addition and multiplication.
These operations are explained in the next two
sections.
The Rijndael Cipher
Rijndael is a symmetric key block cipher. The term symmetric key means that there
is only one secret key, which is used for both encryption and decryption. The term
block cipher means that the data to be ciphered is processed in blocks of constant
length. The output, named ciphered text, has same length as the input. The data
before ciphering is called plaintext. The encryption algorithm has constant key and
plaintext sizes that can be independently chosen as 128, 192 or 256 bits. These bits
can be considered as an array consisting of 8 bits. There are 4 rows in this array and
the number of columns, denoted by Nb, can be 4, 6 or 8 depending on the plaintext
and the key length. Figure 2.1 shows an example array corresponding to a key size
of 192 bits.
The ShiftRow Transformation
The ShiftRow Transformation is a cyclical shift operation that is applied to the rows
of the inner state and consists of the shifting of the rows by different offsets which
depend on the data block length Nb. The first row is not shifted; the second row is
shifted over 1 byte to the left. The third row is shifted over 2 bytes, if the block
length is 128 or 192 bits, and it is shifted over 3 bytes, if the block length is 256 bits.
The fourth row is shifted over 3 bytes if the block length is 128 or 192 bits, and it is
shifted over 4 bytes if the block length is 256 bits. Table 2.1 shows the offset values
as a function of the block length.
Key Schedule
The round keys are obtained from the initial cipher key, which can be 128, 192 or
256 bits long. The length of the plaintext determines how many bits are needed at
each round. For example, if Nk = 4, that is the cipher key is 128 bits long, and Nb =
6, that is the plaintext is 192 bits long, then there are 12 rounds specified by the
algorithm. In each round, a 192-bit key is needed, and another 192 bits are needed
for the initial key addition, so we need a total of 12 * 192 + 192 = 2496 bits to
complete the encryption.
DIFFERENT RIJNDAEL PROCESSOR IMPLEMENTATIONS
Both academia and industry have focused on the efficient implementation of the
new AES algorithm. There are many publications involving FPGA, ASIC, and
software implementations.
An ASIC implementation and its experimental results are presented by Henry Kuo,
Ingrid Verbauwhede and Patrick Shaumont in [5], [6] and [7]. In this study, a
Rijndael encryption core having a non-pipelined encryption data path is presented.
This chip has on-the-fly key schedule data path.
This means, the round keys
necessary for the encryption are calculated at every round. No pre calculation and
storage is needed for this case. However, for some data-key sizes, 2 round keys
must be prepared in the same clock period. This significantly increases the critical
length and decreases the overall speed of the chip.
The chip architecture of this Rijndael IC is shown in Figure 3.1 [5]. There is an
encryption module, a processor for controlling the operations, two 256-bit data
buffers for input and output data storage, two key scheduling modules to generate
the required keys necessary for each round and two Finite State Machines (FSM’s)
controlling the input and output data interface.
Key Generator Module
The Key Generator Module is responsible for generating the round keys and
supplying these keys to the Decryption and Encryption Modules.
The Key
Generator Module is composed of 3 sub-modules. They are the Key Expansion
Module, the Key Storage Module and the Key Selection Module. All the keys
needed for encryption and decryption are generated by Key Expansion Module and
they are stored in the Key Storage Module.
On the fly key generation is a method, which produces the keys needed for a round
at every clock and does not store all the keys in a register. This decreases the
number of the registers needed for the key generation. However, it is not practical
for implementations of encryption and decryption modules supporting all key and
data sizes of the Rijndael Algorithm. It may be good for implementations that make
encryption only.