Synthesis Optimization on Galois-Field Based Arithmetic Operators for Rijndael Cipher
DOI:
https://doi.org/10.5614/itbj.ict.2011.5.2.2Abstract
A series of experiments has been conducted to show that FPGA synthesis of Galois-Field (GF) based arithmetic operators can be optimized automatically to improve Rijndael Cipher throughput. Moreover, it has been demonstrated that efficiency improvement in GF operators does not directly correspond to the system performance at application level. The experiments were motivated by so many research works that focused on improving performance of GF operators. Each of the variants has the most efficient form in either time (fastest) or space (smallest occupied area) when implemented in FPGA chips. In fact, GF operators are not utilized individually, but rather integrated one to the others to implement algorithms. Contribution of this paper is to raise issue on GF-based application performance and suggest alternative aspects that potentially affect it. Instead of focusing on GF operator efficiency, system characteristics are worth considered in optimizing application performance.Downloads
References
van Tilborg, H., An Introduction to Cryptology, Kluwer Academic Publishers, 1988.
Schneier, B. Applied Chryptography, Wiley&Sons, 1993.
Wicker, S.B., Error Control Systems for Digital Communication and Storage, Prentice Hall, New Jersey 07458, 1995.
Sweeney, P., Error Control Coding from Theory to Practice, John Wiley & Sons, Inc., 2002.
Lin, S. & Costello, D.J. Error Control Coding, Prentice Hall, Englewood Cliffs, New Jersey, 1983.
Wang, C., Truong, T., Shao, H., Deutsch, L., Omura, J. & Reed, I., VLSI Architectures for Computing Multiplications and Inverses in GF(2m), IEEE Transactions on Computers, 34(8), pp. 709-717, August 1985.
Hasan, M., Wang, M. & Bhargava, V., Division and Bit-Serial Multiplication over GF(qm), IEEE Transactions on Computers, 41(8), 972-980, August 1992.
Zhou, T., Wu, X., Bai, G. & Chen, H., Fast GF(p) Modular Inversion Algorithm Suitable for VLSI Implementation, Electronics Letters, 38(14),pp. 706-707, 4 July 2002.
Bartee, T. & Schneider, D., Computation with Finite Fields, Information and Computers, 6, 79-98, March 1963.
Berlekamp, E., Bit-Serial Reed-Solomon Encoders, IEEE Transactions on Information Theory, 28, 869-874, November 1982.
Massey, J. & Omura, J., Computational Method and Apparatus for Finite Field Arithmetic, US Patent No.4, 587, 627, 1986.
Mastrovito, E.D., VLSI Designs for Computations Over Finite Field GF (2m), Master's Thesis No: 159, Linkping Studies in Science and Technology Linkping, Sweden, Dec 1988.
Mastrovito, E., VLSI Architectures for Computations in Galois Fields, PhD Thesis, Dept of Electrical Eng, Linkping Univ, Sweden, 1991.
Gollman, D., Algorithmenentwurf in der kryptographie Habil. University of Karlsruhe Preprint, 1990.
Wu, H., Hasan, M.A., Blake, I.F. & Gao, S., Finite Field Multiplier Using Redundant Representation, IEEE Transactions on Computers, pp. 1306-1316, Nov 2002.
Sunar, B., Savas, E. & Ko, C.K., Constructing Composite Field Representations for Efficient Conversion, IEEE Transactions on Computers, 52(11), 1391-1398, November 2003.
Afanasyev, V., Complexity of VLSI Implementation of Finite Field Arithmetic, In Proc of II Int'l Workshop on Algebraic and Combinatorial Coding Theory Leningrad, USSA., pp. 6-8, 1990.
Hasan, M., Wang, M. & Bhargava, V., A Modified Massey-Omura Parallel Multiplier for a Class of Finite Fields, IEEE Transactions on Computers, 42(10), pp. 1278-1280, October 1993.
Lee, C.-H. & Lim,J.-I., A New Aspect of Dual Basis for Efficient Field Arithmetic, Samsung Advanced Inst of Technology, 1998.
Fenn, T.S., Benaissa, M. & Taylor, D., GF(2m) Multiplication and Division Over the Dual Basis, IEEE Transactions on Computers, 45(3),pp. 319-327, March 1996.
Paar, C., Efficient VLSI Architectures for Bit-Parallel Computation in Galois Fields, PhD Thesis, Univ of Essen, Germany, June 1994.
Itoh, T. & Tsujii, A Fast Algorithm for Computing Multiplicative Inverses in GF(2m) using Normal Basis, Journal Information and Computation, 78(3), pp. 171-177, Sep. 1988.
Paar, C. & Rosner, M., Comparison of Arithmetic Architectures for ReedSolomon Decoders in Reconfigurable Hardware, IEEE Symposium on FPGA-Based Custom Computing Machines (FCCM), pp. 219-225, April 1997.
Mursanto, P., Comparison of Galois Field Mutlipliers in Standard and Composite Field Architectures, In National Conference on Computer Science & Information Technology, Depok Fasilkom UI, 29-30 January 2007.
Rudra, A., Dubey, P.K., Jutla, C.S., Kumar, V., Rao, J. & Rohatgi, P., Efficient Rijndael Encryption Implementation with Composite Field Arithmetic, Proc of 3rd Int'l Workshop on Cryptographic Hardware and Embedded Systems, Springer-Verlag, 2162, pp. 171-184, 2001.
Jutla, C., Kumar, V. & Rudra, A., On The Circuit Complexity of Isomorphic Galois Field Transformations, Technical Report RC22652 (W0211-243) IBM Research Division, Nov 2002.
Choi, Y., Chang, K.-Y., Hong, D. & Cho, H., Hybrid Multiplier for GF(2m) Defined by Some Irreducible Trinomials, Electronics Letters, 40(14), pp. 852-853, July 8, 2004.
Huang, C.-T. & Wu, C.W., High-Speed Easily Testable Galois-Field Inverter, IEEE Transactions on Circuit and Systems, 48(9), pp. 909-918, September 2000.
Li, H., A Parallel S-Box Architecture for AES Byte Substitution, International Conference on Communications, Circuits and Systems, 1(1), pp. 1-3, 27-29 June 2004.
Li, H., A New CAM Based S-Box Look Up Table in AES, IEEE International Symposium on Circuits and Systems, 5, pp. 4634-4636, 23-26 May 2005.
Rijmen, V., Efficient Implementation of the Rijndael S-box F.W.O. PostDoctoral report, Dept. ESAT, Belgium, 2001.
Daemen, J. & Rijmen, V., AES Proposal: Rijndael, March 9, 1999 Ver 2.
Mursanto, P., Manfaat Representasi Elemen Berbasis Normal dalam Meningkatkan Kinerja Operator Aritmetika Galois Field, In Proc 6th National Conf. Design and Application of Technology, Widya Mandala Univ., pp. 121-127, Jul 19, 2007.
Mursanto, P., Performance Evaluaton of Galois Field Arithmetic Operators for Optimizing Reed Solomon Codec, In Proceeding International Conference on Instrumentation, Communication, Information Technology & Biomedical Engineering (ICICI-BME) Bandung, Nov 23-25, 2009.
Daemen, J. & Rijmen,V. , Rijndael, The Advanced Encription Standard, Dr.Dobb's Journal, 26, pp. 137-139, Mar 2001.
Sklar, B., Digital Communications Fundamentals and Applications, Prentice Hall, Inc., New Jersey 2nd ed, 2003.
