Synthesis Optimization on Galois-Field Based Arithmetic Operators for Rijndael Cipher

Petrus Mursanto

Abstract


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.

Full Text:

PDF

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.




DOI: http://dx.doi.org/10.5614%2Fitbj.ict.2011.5.2.2

Refbacks

  • There are currently no refbacks.


Contact Information:

ITB Journal Publisher, LPPM – ITB, 

Center for Research and Community Services (CRCS) Building Floor 7th, 
Jl. Ganesha No. 10 Bandung 40132, Indonesia,

Tel. +62-22-86010080,

Fax.: +62-22-86010051;

e-mail: jictra@lppm.itb.ac.id.