Fast composite field S-box architectures for advanced encryption standard

ABSTRACT

Byte substitution (S-Box), which is essentially a combination of inversion and affine operations over a finite field GF(2⁸), limits the throughput of the Advanced Encryption Standard (AES) algorithm. Among existing S-Box architectures, the composite field S-Box algorithm is very attractive for its extremely low area cost, which is only 12%-20% of other implementation approaches [1]. However, the composite field S-Box suffers from extremely low throughput rate. In this paper, we propose a novel fast composite field S-Box architecture. By applying pre-computation techniques, some computation on the critical data path can be eliminated so as to reduce the critical path delay. The complexity of the precomputation units is minimized via sharing common structures. The proposed design is implemented using a 0.18-um CMOS technology library. The results show that the throughput rate is increased by 28.22% at the expense of a fairly modest increase in area. Based on the proposed design, we then present an approach to further reduce critical path delay. The gate-level analysis shows that the second proposed approach can increase the throughput rate by 56.25%. In addition, the proposed designs can reduce the pipelining latency by 40%-60% compared with the conventional design while keeping the same throughput rate.

REFERENCES

• 1: Sumio Morioka , Akashi Satoh, A 10-Gbps full-AES crypto design with a twisted BDD S-box architecture, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.7, p.686-691, July 2004 [doi>10.1109/TVLSI.2004.830936]
• 2: Advanced Encryption Standard (AES) FIPS Pub 197, Nov, 2001.
• 3: Data Encryption Standard (DES) FIPS Pub 46--3, Oct, 1999.
• 4: Alireza Hodjat , Ingrid Verbauwhede, Area-Throughput Trade-Offs for Fully Pipelined 30 to 70 Gbits/s AES Processors, IEEE Transactions on Computers, v.55 n.4, p.366-372, April 2006 [doi>10.1109/TC.2006.49]
• 5: A. J. Elbirt, W. Yip, B. Chetwynd, and C. Paar, "An FPGA Implementation and Performance Evaluation of the AES Block Cipher Candidate Algorithm Finalist," Proc. 3rd AES Conf. (AES3), New York, Apr. 2000.
• 6: Viktor Fischer , Milos Drutarovský, Two Methods of Rijndael Implementation in Reconfigurable Hardware, Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems, p.77-92, May 14-16, 2001
• 7: K. Gaj and P. Chodowiec, "Comparison of the Hardware Performance of the AES Candidates using Reconfigurable Hardware," in Proc. 3rd AES Conf. (AES3), New York, Apr. 2000.
• 8: Henry Kuo , Ingrid Verbauwhede, Architectural Optimization for a 1.82Gbits/sec VLSI Implementation of the AES Rijndael Algorithm, Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems, p.51-64, May 14-16, 2001
• 9: M. McLoone and J. V. McCanny, "Rijndael FPGA implementation utilizing Look-up tables," in IEEE Workshop on Signal Processing Systems, pp. 349--360, Sept. 2001.
• 10: V. Rijmen, "E±cient Implementation of the Rijndael S-Box," http://www.iaik.tugraz.ac.at/research/krypto/AES/old/rijmen/rijndael/SBox.pdf, 2006.
• 11: Atri Rudra , Pradeep K. Dubey , Charanjit S. Jutla , Vijay Kumar , Josyula R. Rao , Pankaj Rohatgi, Efficient Rijndael Encryption Implementation with Composite Field Arithmetic, Proceedings of the Third International Workshop on Cryptographic Hardware and Embedded Systems, p.171-184, May 14-16, 2001
• 12: Akashi Satoh , Sumio Morioka , Kohji Takano , Seiji Munetoh, A Compact Rijndael Hardware Architecture with S-Box Optimization, Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology, p.239-254, December 09-13, 2001
• 13: Jorge Guajardo , Christof Paar, Efficient Algorithms for Elliptic Curve Cryptosystems, Proceedings of the 17th Annual International Cryptology Conference on Advances in Cryptology, p.342-356, August 17-21, 1997
• 14: Xinmiao Zhang , Keshab K. Parhi, High-speed VLSI architectures for the AES algorithm, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.9, p.957-967, September 2004 [doi>10.1109/TVLSI.2004.832943]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Arithmetic and logic units

General Terms:
Design

Keywords:
advanced encryption standard (aes), composite finite field, precomputation, s-box