16.3.1 RC4 Stream Cipher Algorithm

The RC4 algorithm is a remarkably simple cipher. A variable-length key K of size 1–256 bytes (8–2048 bits) is used to initialize a 256-byte state vector S = (S[0], S1, …, S[255]). At all times, S contains a permutation of all the 8-bit numbers from 0 through 255. For encryption and decryption, a byte is selected from S in a systematic fashion. The entries in S are then once again permuted.

Initially the entries in S are set equal to the values from 0 through 255 in the ascending order, that is, S = (0, 1, …, 255). A temporary vector, T, is also created. If the length of the key K is 256 bytes, then K is copied to T. Otherwise, for a key of length keylen bytes, K is copied to the first keylen elements of T and then K is repeated as many times as necessary to fill out T.

T is then used to produce the initial permutation of S. This involves starting with S[0] and going through to S[255], and, for each S[i], swapping S[i] with another byte S[j] in S where j is computed (j is initialized 0) as j ← (j + S[i] + T[i]) mod 256.

After the initialization of vector S, the key K is no longer used. Stream generation involves starting with S[0] and going through to S[255], and, for each S[i], swapping S[i] with another byte in S according to the following scheme dictated by the current configuration of S. First i and j are initialized to 0.

• i = (i + 1) mod 256

• j = (j + S[i]) mod 256

• Swap (S[i], S[j])

• t = (S[i] + S[j]) mod 256

• k = S[t]

The stream output is k, which is the key. After S[255] is reached, the process continues, starting over again at S[0]. Encryption is performed by XORing the stream output with the next byte of the plaintext. Decryption is carried out by XORing the same stream output with the next byte of the ciphertext. The stream generation by the RC4 cipher is illustrated in Figure 16.1.

16.3.2 RC4 Implementation

In Kitsos et al. [5], a hardware implementation of the RC4 stream cipher is presented. The implementation is parameterized to support variable key lengths (key length could be 8 up to 128 bits). This implementation requires three clock cycles per byte generation in the key setup phase, and three clock cycles per byte generation in the encryption phase. The total number of operations required is 768 + 3n clock cycles, where n is the number of bytes of the plaintext/ciphertext.

The proposed architecture in Kitsos et al. [5] consists of a control and a storage unit. The storage unit is responsible for the key setup and generation of the key-stream. There are two 256-byte arrays, S-box and K-box. The S-box is filled with the state array and the K-box consists of the key, repeating as necessary, to fill the array. The storage unit contains memory elements for the S-box and the K-box, along with 8-bit registers, adders, and one multiplexer.

The S-box RAM consists of three 256 bytes RAM blocks with same signals of clock and reset. Each RAM block has four inputs and one output. The two inputs are the read and write signals whereas the other two are the address and the data signals. When a reset signal occurs, the blocks are initialized linearly; when the write signal occurs, new data are stored in the address position; and when the read signal occurs, the data in the address position are available on the output of the block.

At the first clock cycle, the value of the counter i is used as address in the first RAM block. The value of the register S[i] is used for the computation of the new value of j. Two adders are used for the computation of the new value of j. The input to the adders is the values of T[i] and S[i]. At the second clock cycle, the new value j is used as the address for the second RAM block. The value stored in this address is temporarily stored in the S[j] register. At the third cycle, the contents of the S[i] register and S[j] register are written in the registers at the j-th and i-th address locations, respectively.

The operations in the key setup phase are as follows. First, the value of i is used as address in the first RAM block. Then the new value of j is computed. At the second step, the new value of j is used as address of the second RAM block and the value of S[j] is stored in the j-th register. Then the values of S[i] and S[j] are added and the result of the addition is stored in the S[t] register. At the third step, the contents of the S[i] register and S[j] register are swapped and the value of the t-th register S[t] is used as address for the third RAM block. The value of S[t] is produced in the third step and this value of S[t] becomes the stream-generated key byte.

The encryption (decryption) is achieved by the bitwise XORing of the keystream with the plaintext (ciphertext). The operation of the storage unit is synchronized by a control unit and the control unit is responsible for the generation of the clock and control signals.

16.4.1 Data Encryption Standard Block Cipher Algorithm

The DES algorithm in brief is as follows. Get a 64-bit block of data. Sixteen different round keys K[1], …, K[16] are first generated from the DES key K. An initial permutation is performed on the data block. The block is then divided into two halves. The first 32 bits are called the left half L[0], and the last 32 bits are called the right half R[0]. Sixteen subkeys are then applied to the data block in 16 successive rounds. Start with i = 1. The 32-bit R[i − 1] is expanded into 48 bits according to a bit-selection function E (.). E (R[i − 1]) is XORed with K[i]. E (R[i − 1]) ⊕ K[i] is then broken into eight 6-bit blocks and fed into eight S-boxes (substitution boxes). Each S-box has a 4-bit long output. Outputs from all the eight S-boxes concatenated and the bits in the resulting 32 bit string is permuted. The resulting string is XORed with L[i − 1] to get R[i − 1]. R[i − 1] is assigned as the new L[i]. The operation in the i-th round is illustrated in Figure 16.2. This process is repeated for the 16 rounds. After the 16th round, the left and right halves are swapped. Then inverse of the initial permutation is then performed on the result of left-right swap. The ciphertext is the output of the inverse permutation operation. To decrypt, use the same process, but just use the keys K[i] in the reverse order.

16.4.2 Triple Data Encryption Standard Implementation

Each DES begins with initial permutation IP and ends with the inverse of the initial permutation. These two permutations are inverse operations. When three DES are concatenated, the initial permutation of the previous DES follows the inverse initial permutation of the current DES and they cancel out. Hence, only the first IP and the last inverse IP need to be performed. As a result, the initial permutations of the second and third DES, and the final permutations of the first and the second DES, are not required to be included in the VLSI architecture. For all the following implementations of 3DES, the S-BOXes have been integrated by LUTs as well as by read-only memory (ROM) blocks.

We now describe a 48-stage VLSI architecture proposed in Kitsos et al. [7]. This architecture has the ability to process 48 independent data blocks. The subkeys for the 48 rounds are generated by three key scheduler units corresponding to the three DES components. Each key generator for a DES round produces 16 round keys. The 64-bit input key is initially permuted, and is then passed through a hardwired shifter and is finally passed through a second round permutation for each subkey. A memory of 3 × 64 bits is placed at the input to the key scheduling circuit. In this memory, the three 64 bits keys corresponding to the three DES rounds are stored to input the appropriate key in the appropriate time. On the first clock cycle, the first key is applied on the key scheduler and the DES runs in the encryption mode. On the 17th clock cycle the second key is supplied on the key scheduler and the DES runs in the decryption mode. Finally, on the 33rd cycle the third key is supplied and the DES runs in the encryption mode.

A second architecture proposed by Kitsos et al. [7] consists of 1 DES with 16 pipeline registers between the rounds. A multiplexer is used to determine between the new data and the output of the DES from the previous stage. This architecture can process 16 independent data blocks at a time. The generation of subkeys comprises 16 rounds. This architecture is suitable for high-speed applications that support ECB or automated teller machine (ATM) counter modes of operation of the block cipher where same message blocks encrypt to same ciphertext blocks.

A third architecture proposed by Kitsos et al. [7] uses consecutive iterations. Only one basic round each is implemented for the 3DES algorithm and the key scheduler to minimize the resources allocated for the 3DES. In this case, the required hardware resources are reduced by a factor of 40, 80, and 16, respectively, compared to the previous ones.

The output of the basic round is loaded to a register and another register is used for the input plaintext. The plaintext is loaded during the initialization step into the multiplexer. Feedback is used for loading new data blocks through the multiplexer for transforming the data during the 48 rounds of the 3DES. The key scheduler has one basic round and successive round subkeys are computed by simple rotations and permutations. The key scheduler provides one subkey at every clock cycle where 48 clock cycles are needed for the execution of the whole 3DES block cipher.

Because this architecture uses the minimum hardware with feedback mode, it is suitable for area-restricted devices and for the CBC or OFB modes of the block cipher operations.

16.5.1 Advanced Encryption Standard Algorithm

AES, like DES, is an iterative algorithm. Each iteration is called a round. AES block cipher algorithm deals with data blocks of 128 bits using keys with three standard lengths of 128, 192, and 256 bits. The 128-bit data block is divided into 16 bytes. These bytes are mapped to a 4 × 4 array called the state, and all the internal operations of the AES algorithm are performed on the state matrix. The internal operations consist of mainly four primitive transformations: Sub-Bytes, ShiftRows, MixColumns, and AddRoundKey. AES encryption/decryption process involves these four primitive transformations executed iteratively in several rounds. The number of rounds is 10, 12, or 14, corresponding to the key sizes 128, 192, and 256, respectively.

In the encryption procedure, the input data is bitwise XORed with an initial key, and then four transformations are executed in the following order: Sub-Bytes, ShiftRows, MixColumns, and AddRoundKey for all rounds except the last one. All four transformations except the MixColumns transformation are performed in the last round (in the same order). The execution sequence is reversed in the decryption process, with the inverses of transformations such as InvSubBytes, InvShiftRows, InvMixColumns, respectively as well as the AddRoundKey operation. Because each round needs a round key, an initial key is used to generate all the round keys before the encryption/decryption operation. The block diagram of the AES encryption and the decryption algorithms is given in Figure 16.3.

16.5.2 Advanced Encryption Standard Implementation

Three architectural optimization approaches are usually employed to speed up the hardware implementations of AES. They are pipelining, subpipelining, and loop-unrolling. Among these three approaches, the subpipelined architecture can achieve maximum speedup and optimum speed–area ratio in non-feedback modes of the block cipher. The advantage of subpipelining can be enhanced further by dividing each round unit into more substages with equal delay. However, the SubBytes and the InvSubBytes operations in the AES algorithm are traditionally implemented by LUTs.

In Zhang et al. [9], the authors avoid the use of LUTs and propose the use of composite field data paths for the SubBytes and InvSubBytes transformations. They achieved high-speed subpipelined AES architectures through such data paths. Composite field arithmetic has been employed by Satoh et al. [10] to design efficient data paths. In the architecture proposed in Zhang et al. [9], the inversion in GF (2⁴) is implemented by a novel approach, which leads to a more efficient architecture with shorter critical path and smaller area. The composite field arithmetic used in Rudra et al. [11] is not efficient in all the transformations used in the AES algorithm. In Zhang et al. [9], a key expansion architecture is presented, which is well suited for subpipelined designs. Further, this architecture can operate in an on-the-fly manner.

16.6.1 RSA Encryption and Decryption Algorithms

RSA is a public-key cryptographic algorithm. It uses two keys: a public key and a private key. The public key is known to everyone and is used for encrypting messages. Messages encrypted with the public key can be decrypted only using the private key. The keys for the RSA algorithm are generated in the following way:

• Choose randomly two distinct prime numbers p and q of approximately equal bit length.

• Compute n = pq.

• Compute φ(n) = (p − 1)(q − 1), where φ is the Euler’s totient function.

• Choose an integer e having a short bit length and small Hamming weight such that 1 < e < φ (n) and the greatest common divisor (e,φ(n)) = 1; that is, e and φ(n) are relatively prime. e is published as the public key exponent.

• Determine d as ed ≡ 1(mod φ(n)). d is securely kept as the private key exponent.

The encryption is performed as follows. Alice sends her public key (n,e) to Bob and keeps the private key d secret. To send a message M to Alice, Bob firsts converts M into an integer m, such that 0 ≤ m < n. He then computes the ciphertext c corresponding to m as

This can be done quickly using the method of exponentiation by repeated squaring. Bob then transmits c to Alice.

On receiving the ciphertext c, Alice can recover m from c by using her private key exponent d by performing the decryption operation as

After getting m, Alice can recover the original message M by reversing the conversion operation.

16.6.2 RSA Implementation

LFSR can be used to generate random numbers p and q. Simultaneously, each number will be checked to see whether it is a prime number or not. The modular multiplication can be implemented using shift-add multiplication algorithm. The modular exponentiation can be implemented using a 16-bit modular exponentiation using LR binary method, where LR stands for the left-to-right scanning direction of the exponent.

Modular multiplication is a slightly complicated arithmetic operation because of the inherent multiplication and division operations. Modular multiplication can be carried out by performing the modulo operation after multiplication or during the multiplication. The modulo operation is accomplished by integer division, in which only the remainder after division is taken for further computation. The first approach requires an n × n bit multiplier with a 2n-bit register followed by a 2n × n bit divider. In the second approach, the modulo operation occurs in each step of integer multiplication. Therefore the first approach requires more hardware while the second requires more addition/subtraction computations. Different number representations such as redundant number systems and higher radix carry-save form have been used for this purpose. A carry prediction mechanism has also been used for fast calculation of modular multiplication.

Various authors [13,14,15,16] have proposed different array structures suited for VLSI implementation of modular multiplication. Vandemeulebroecke et al. [15] used a modulo after a multiplication approach using a signed digit number representation. Two arrays were used: one for multiplication and the other for integer division. Koc et al. [14] applied Blakelys algorithm [17] and use a sign estimation method by looking at the five most significant bits (MSBs) in each iteration stage. Although they obtain a bit-level systolic array structure, the latency and clock cycle are relatively long due to the control node that estimates the sign of the intermediate result in each stage [18].

Jeong et al. [18] have developed two new VLSI array architectures for modular multiplication. The idea is similar to Montgomerys algorithm [19] in which each partial product is made as a multiple of the radix to simplify the multiplication by the radix by only looking at the least significant bits. This approach requires only a post-processing step to get the final answer. In Jeong et al. [18], the MSBs are considered to remove higher bit positions while keeping the correct answer in each partial product, keeping it within a certain range. By a simple translation of a modulo operation into an addition of a precalculated complement of the modulus, the modulo during multiplication approach is used with a carry-save adder structure. Multiple XORs are used to choose the precalculated integer depending on the control that is generated in the leftmost node in each stage. Compared to other algorithms, they obtain a higher clock frequency because of the simplified modulo reduction operation.

16.7.1 Elliptic Curve Cryptography

The security of elliptic curve cryptographic systems is based on the hardness of the elliptic curve discrete logarithm problem (ECDLP). The ECDLP is as follows: given an elliptic curve E defined over GF (pⁿ), and two points P,Q ∈ E, find an integer x such that Q = xP.

Given a set of domain parameters that include a choice of base prime field GF (p), an elliptic curve E, and a base point G of order n on E, an elliptic curve key pair (d,Q) consists of a private key d, which is a randomly chosen nonzero integer modulo the group order n, and a public key Q = dG. Thus, the point Q becomes a randomly selected point in the group generated by G.

There are several different standardizations extending the basic elliptic curve Diffie–Hellman key exchange protocol. The basic Diffie–Hellman key exchange protocol is as follows. To agree on a shared key, Alice and Bob individually generate key pairs (d_A,Q_A) and (d_B,Q_B). They then exchange the public keys Q_A and Q_B over a public channel. In this case, both Alice and Bob will be able to compute the point P = d_AQ_B = d_BQ_A using their respective private keys. The shared secret key is derived from P by a key derivation function, usually being applied to its x-coordinate.

The ElGamal elliptic curve cryptosystem is as follows. Suppose that E is an elliptic curve defined over a finite field GF (pⁿ). Suppose that E,pⁿ, and a point G ∈ E and the embedding m → P_m (from message to point on the elliptic curve) are publicly known. When Alice wants to communicate secretly with Bob, they proceed as follows:

• Bob chooses a random integer b, and publishes the point bG, keeping b secret.

• Alice chooses another random integer a and sends the pair of points (aG,P_m + a (bG)) to Bob, keeping a secret.

• To decrypt the message, Bob calculates b (aG) from the first part of the pair, then subtracts it from the second part to obtain P_m + a (bG) − b (aG) = P_m + abG − abG = P_m, and then reverses the embedding (P_m → m) to get back the message m.

An attacker, Eve, who can only see bG, aG, and P_m + a (bG), must find a from aG or b from bG to get P_m. Thus the security of the system is reduced to the ECDLP.

The Elliptic Curve Digital Signature Algorithm that was standardized in the FIPS 186-4 is as follows. A signer generates a key pair (d,Q) consisting of a private signing key d and a public verification key Q = dG. To sign a message m, the signer first chooses a random integer k such that 1 ≤ k ≤ n, computes the point kG = (x,y), transforms x to an integer, and computes r = x mod n. The message m is hashed to a bitstring and then transformed to an integer e. The signature of m is a pair (r,s) of integers modulo n, where s = k⁻¹(e + dr) mod n.

16.7.2 Elliptic Curve Cryptosystem Implementation

The most basic finite field algorithms are addition and subtraction. In Wenger et al. [21], algorithms for modular addition in GF (p) and GF (2^m) are given. Operand-scanning or product-scanning multiplication approaches are used for realizing modular multiprecision multiplications. A multiply-accumulate unit has been used to increase the efficiency of the product-scanning method. Such multiply-accumulate units can be designed for the finite fields GF (p) and GF (2ⁿ). Carry-less multipliers for GF (2ⁿ) have shorter critical paths and smaller area requirements because in this case, logical XOR cells are used instead of full-adder standard cells. The power consumption for a multiplier designed out of XORs is lower compared to full adders.

16.8.1 SHA-3 Standard

Keccak Hash Function was finally selected as the SHA-3 standard. Keccak is a family of sponge functions Keccak[r,c] characterized by two parameters, the bitrate r and the capacity c. The sum r + c determines the width of the Keccak − f permutation used in the sponge construction and can take values only in the set {25,50,100,200,400,800,1600}. For the SHA-3 standard, the designers of Keccak proposed the Keccak[1600] with different values for r and c for each desired length of the hash output. The Keccak[1600] has a 1600-bit state, which consists of 5 × 5 matrix of 64-bit words. For the 256-bit hash Keccak 256, the parameters are r = 1088 and c = 512. For the 512-bit hash Keccak-512, the parameters are r = 576 and c = 1024.

The compression function of Keccak consists of the following five primitive steps consisting of XOR, AND, NOT, and permutation operations:

• theta (θ)

• rho (ρ)

• pi (π)

• chi (ξ)

• iota (ι)

Each compression step of Keccak consists of 24 rounds. The hash function operation consists of three phases, which are initialization, absorbing phase, and squeezing-bit phase. In the initialization phase, all the entries of the state matrix are set to zero. In the absorbing phase, each message is XORed with the current state and 24 rounds of Keccak permutation are performed. After absorbing all blocks of the input message, the squeezing phase is performed. In the squeezing phase, the state matrix is truncated to the desired output length of the hash. If a longer hash value is required, then more Keccak permutations are performed and their results are concatenated until the length of the hash values reaches the desired output length. The function is illustrated in Figure 16.4.

16.8.2 SHA-3 Implementation

Hardware implementation of SHA-3 is analyzed based on the operation speed, the circuit area, and the power consumption. The cost of an application-specific integrated circuit (ASIC) implementation of SHA-3 directly depends on the area required to realize the algorithm. The maximum available silicon area, the total number of I/O pins, and the capabilities of the test infrastructure can all limit the implementations. Further, the throughput of a hash function, which is defined as the amount of message in bits for which a hash value can be computed per second, needs to be measured. Power and energy requirements are also used in evaluations in these days. Power density can limit the circuits to comply for sub 100-nm technologies, and limit the applications in systems with scarce energy resources such as handheld devices, smartcards, RFID devices, and so on. In evaluations, the energy per bit of input information processed by the hash function may be calculated to determine the energy consumption.

In Henzen et al. [26], an ASIC hardware implementation of SHA-3 hash standard is given. The authors first developed a golden model and then used it to generate the stimuli vectors and expected responses to verify the register-transfer level (RTL) description of the algorithm written in Very high speed integrated circuit Hardware Description Language. They then used Synopsys Design Vision-2009.06 to map the RTL description to the UMC 90-nm technology using the fsd0a_a_2009Q2v2.0 RVT standard cell library from the Faraday Technology Corporation. All outputs are assumed to have a capacitive loading of 50 fF, and the input drive strength is assumed to be that of a medium strength buffer.

Postlayout performances of SHA-3 (Keccak-256) algorithms for a target throughput of 20 Gbps in the UMC 90-nm process as reported by Henzen et al. [26] are given in Table 16.1.