Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

Concurrent error detection and correction in dual basis multiplier over GF(2m)

Concurrent error detection and correction in dual basis multiplier over GF(2m)

For access to this article, please select a purchase option:

Buy article PDF
£12.50
(plus tax if applicable)
Add to cart
Buy Knowledge Pack
10 articles for £75.00
(plus taxes if applicable)
Add to cart

IET members benefit from discounts to all IET publications and free access to E&T Magazine. If you are an IET member, log in to your account and the discounts will automatically be applied.

Learn more about IET membership 

Recommend Title Publication to library

You must fill out fields marked with: *

Librarian details
Name:*
Email:*
Your details
Name:*
Email:*
Department:*
Why are you recommending this title?
Select reason:
 
 
 
 
 
IET Circuits, Devices & Systems — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

  • Author(s): C.W. Chiou 1 ; C.-Y. Lee 2 ; J.-M. Lin 3 ; T.-W. Hou 4 ; C.-C. Chang 3
    • View affiliations
    • Affiliations: 1: Department of Computer Science and Information Engineering, Ching Yun University, Chung-Li, Taiwan, Republic of China
      2: Department of Computer Information and Network Engineering, Lunghwa University of Science and Technology, Taiwan, Republic of China
      3: Department of Information Engineering and Computer Science, Feng Chia University, Taiwan, Republic of China
      4: Department of Engineering Science, National Cheng Kung University, Taiwan, Republic of China
  • Source: Volume 3, Issue 1, February 2009, p. 22 – 40
    DOI:  10.1049/iet-cds:20080122 , Print ISSN 1751-858X, Online ISSN 1751-8598
© The Institution of Engineering and Technology
Published

Fault-based side-channel cryptanalysis is a useful technique against symmetrical and asymmetrical encryption/decryption algorithms. Thus, eliminating cryptographic computation errors become critical in preventing such kind of attacks. A simple way to eliminating cryptographic computation errors is to output correct or corrected ciphers. Multiplication is the most important finite field arithmetic operation in the cryptographic computations. By using time redundancy technique, a novel dual basis (DB) multiplier over Galois fields (2m) will be presented with lower space complexity and feedback-free property. Based on the proposed feedback-free DB multiplier, the DB multiplier with a concurrent error detection (CED) capability is also easily developed. Compared with the existing DB multiplier with CED capability, the proposed one saves about 90% of time-area complexity. No existing DB multiplier in the literature has concurrent error correction (CEC) capability. Based on the proposed DB multiplier, a novel DB multiplier with CEC capability is easily designed. The proposed DB multiplier with CEC capability requires only about 3% of extra space complexity and 15% of time complexity when compared with the proposed DB multiplier without CEC.

Inspec keywords: cryptography; error correction codes; computational complexity; fault diagnosis; algebra; Galois fields

Other keywords: decryption algorithms; concurrent error detection; feedback-free property; cryptographic computation errors; dual basis multiplier; time complexity; GF; fault-based side-channel cryptanalysis; asymmetrical encryption; Galois fields; finite field arithmetic operation

Subjects: Algebra; Cryptography; Codes

References

    1. 1)
      • D. Boneh , R.A. DeMillo , R.J. Lipton . On the importance of eliminating errors in cryptographic computations. J. Cryptol. , 101 - 119
    2. 2)
      • R. Lidl , H. Niederreiter . (1994) Introduction to finite fields and their applications.
    3. 3)
      • M74HC174: ‘Hex D-type flip flop with clear, 2001 STMicroelectronics’, http://www.st.com/stonline/products/literature/ds/1914/M74HC174.pdf.
    4. 4)
      • H. Wu , M.A. Hasan . Low complexity bit-parallel multipliers for a class of finite fields. IEEE Trans. Comput. , 8 , 883 - 887
    5. 5)
      • I.S. Hsu , T.K. Truong , L.J. Deutsch , I.S. Reed . A comparison of VLSI architecture of finite field multipliers using dual, normal, or standard bases. IEEE Trans. Comput. , 6 , 735 - 739
    6. 6)
      • M74HC86: ‘Quad exclusive OR gate, 2001 STMicroelectronics’, http://www.st.com/stonline/books/pdf/docs/2006.pdf.
    7. 7)
      • C.W. Chiou , C.Y. Lee . Multiplexer-based double-exponentiation for normal basis of GF (2m). Comput. Secur. , 1 , 83 - 86
    8. 8)
      • Mastrovito, E.D., Mora, T.: `VLSI architectures for multiplication over finite field GF(2', Proc. 6th Int. Conf., AAECC-6, July 1988, Rome, p. 297–309.
    9. 9)
      • M. Diab , A. Poli . New bit-serial systolic multiplier for GF(2m) using irreducible trinomials. Electron. Lett. , 13 , 1183 - 1184
    10. 10)
      • Massey, J.L., Omura, J.K.: `Computational method and apparatus for finite field arithmetic', U.S., 4,587,627, 1986.
    11. 11)
      • Ç.K. Koç , B. Sunar . Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields. IEEE Trans. Comput. , 3 , 353 - 356
    12. 12)
      • C.K. Koc , B. Sunar . An efficient optimal normal basis type II multiplier. IEEE Trans. Comput. , 1 , 83 - 87
    13. 13)
      • Coron, J.S.: `Resistance against differential power analysis attacks for elliptic curve cryptosystems', Proc. Cryptographic Hardware and Embedded Systems (CHES'99), LNCS 1717, 1999, p. 292–302.
    14. 14)
      • Messerges, T.S., Dabbish, E.A., Sloan, R.H.: `Power analysis attacks on modular exponentiation in smartcards', Proc. Cryptographic Hardware and Embedded Systems (CHES'99), LNCS 1717, 1999.
    15. 15)
      • Reyhani-Masoleh, A., Hasan, M.A.: `Error detection in polynomial basis multipliers over binary extension fields', Proc. Cryptographic Hardware and Embedded Systems-CHES 2002, LNCS 2523, 2003, p. 515–528.
    16. 16)
      • Minero, R.H., Anello, A.J., Furey, R.G., Palounek, L.R.: `Checking by pseuduplication', U.S., 3660646, May 1972.
    17. 17)
      • S.T.J. Fenn , M. Benaissa , D. Taylor . GF(2m) multiplication and division over the dual basis. IEEE Trans. Comput. , 3 , 319 - 327
    18. 18)
      • E.R. Berlekamp . Bit-serial Reed-Solomon encoder. IEEE Trans. Inf. Theory , 869 - 874
    19. 19)
      • B. Benjauthrit , I.S. Reed . Galois switching functions and their applications. IEEE Trans. Comput. , 78 - 86
    20. 20)
      • A. Reyhani-Masoleh , M.A. Hasan . A new construction of Massey-Omura parallel multiplier over GF(2m). IEEE Trans. Comput. , 5 , 511 - 520
    21. 21)
      • Anderson, R.J., Kuhn, M.: `Low cost attack on tamper resistant devices', Proc. 5th Int. Workshop on Security Protocols, 1997, Lecture Notes in Computer Sciences, Springer-Verlag, LNCS 1361.
    22. 22)
      • Karri, R., Kuznetsov, G., Goessel, M.: `Parity-based concurrent error detection of substitution-permutation network block ciphers', Proc. CHES 2003, 2003, Springer LNCS 2779, p. 113–124.
    23. 23)
      • C.-Y. Lee , Y.-H. Chen , C.W. Chiou , J-M. Lin . Unified parallel systolic multipliers over GF(2m). J. Comput. Sci. Technol. , 1 , 28 - 38
    24. 24)
      • F.J. MacWilliams , N.J.A. Sloane . (1977) The theory of error-correcting codes.
    25. 25)
      • Kelsey, J., Schneier, B., Wagner, D., Hall, C.: `Side-channel cryptanalysis of product ciphers', Proc. ESORICS, September 1998, Springer, p. 97–110.
    26. 26)
      • C.-Y. Lee , C.W. Chiou , A.-W. Deng , J.-M. Lin . Low-complexity bit-parallel systolic architectures for computing A(x)B2(x) over GF(2m). IEE Proc. Circuits Devices Syst. , 4 , 399 - 406
    27. 27)
      • H. Wu , M.A. Hasan , I.F. Blake . New low-complexity bit-parallel finite field multipliers using weakly dual bases. IEEE Trans. Comput. , 11 , 1223 - 1234
    28. 28)
      • C.Y. Lee , E.H. Lu , J.Y. Lee . Bit-parallel systolic multipliers for GF(2m) fields defined by all-one and equally-spaced polynomials. IEEE Trans. Comput. , 5 , 385 - 393
    29. 29)
      • C.C. Wang . An algorithm to design finite field multipliers using a self-dual normal basis. IEEE Trans. Comput. , 10 , 1457 - 1459
    30. 30)
      • H. Wu . Bit-parallel finite field multiplier and squarer using polynomial basis. IEEE Trans. Comput. , 7 , 750 - 758
    31. 31)
      • C.C. Wang , T.K. Truong , H.M. Shao , L.J. Deutsch , J.K. Omura , I.S. Reed . VLSI architectures for computing multiplications and inverses in GF(2m). IEEE Trans. Comput. , 8 , 709 - 717
    32. 32)
      • M74HC32: ‘Quad 2-input OR gate, 2001 STMicroelectronics’, http://www.st.com/stonline/books/pdf/docs/1944.pdf.
    33. 33)
      • S.T.J. Fenn , M. Benaissa , D. Taylor . Dual basis systolic multipliers for GF(2m). IEE Proc. Comput. Digit. Tech. , 1 , 43 - 46
    34. 34)
      • N. Weste , K. Eshraghian . (1985) Principles of CMOS VLSI design: a system perspective.
    35. 35)
      • A. Reyhani-Masoleh , M.A. Hasan . Fault detection architectures for field multiplication using polynomial bases. IEEE Trans. Comput. , 9 , 1089 - 1103
    36. 36)
      • J.H. Patel , L.Y. Fung . Concurrent error detection in ALU's by recomputing with shifted operands. IEEE Trans. Comput. , 7 , 589 - 595
    37. 37)
      • M. Joye , A.K. Lenstra , J.-J. Quisquater . Chinese remaindering based cryptosystems in the presence of faults. J. Cryptol. , 241 - 245
    38. 38)
      • C.-Y. Lee , J.-M. Lin , C.W. Chiou . Scalable and systolic architecture for computing double exponentiation over GF(2m). Acta Appl. Math. , 161 - 178
    39. 39)
      • S. Oh , C.H. Kim , J. Lim , D.H. Cheon . Efficient normal basis multipliers in composite fields. IEEE Trans. Comput. , 10 , 1133 - 1138
    40. 40)
      • T. Itoh , S. Tsujii . Structure of parallel multipliers for a class of fields GF(2m). Inf. Comput. , 21 - 40
    41. 41)
      • Mastrovito, E.D.: `VLSI architectures for computations in Galois fields', 1991, PhD, Linköping University, Department of Electrical Engineering, Linköping, Sweden, 1991.
    42. 42)
      • C.Y. Lee , C.W. Chiou , J.M. Lin . Concurrent error detection in a polynomial basis multiplier over GF(2m). J. Electron. Test. Theory Appl. , 2 , 143 - 150
    43. 43)
      • G. Bertoni , L. Breveglieri , I. Koren , P. Maistri , V. Piuri . Error analysis and detection procedures for a hardware implementation of the advanced encryption standard. IEEE Trans. Comput. , 4 , 492 - 505
    44. 44)
      • N. Takagi , J.-I. Yoshiki , K. Takagi . A fast algorithm for multiplicative inversion in GF(2m) using normal basis. IEEE Trans. Comput. , 5 , 394 - 398
    45. 45)
      • C.Y. Lee , C.W. Chiou , J.M. Lin . Concurrent error detection in a bit-parallel systolic multiplier for dual basis of GF(2m). J. Electron. Test. Theory Appl. , 5 , 539 - 549
    46. 46)
      • M74HC08: ‘Quad 2-input AND gate, 2001 STMicroelectronics’, http://www.st.com/stonline/books/pdf/docs/1885.pdf.
    47. 47)
      • T.C. Bartee , D.J. Schneider . Computation with finite fields. Inf. Comput. , 79 - 98
    48. 48)
      • S. Fenn , M. Gossel , M. Benaissa , D. Taylor . On-line error detection for bit-serial multipliers in GF(2m). J. Electron. Test. Theory Appl. , 29 - 40
    49. 49)
      • C.Y. Lee , C.W. Chiou . Efficient design of low-complexity bit-parallel systolic Hankel multipliers to implement multiplication in normal and dual bases of GF(2m). IEICE Trans. Fundam. Electron. Commun. Comput. Sci. , 11 , 3169 - 3179
    50. 50)
      • C.C. Wang , D. Pei . A VLSI design for computing exponentiation in GF(2m) and its application to generate pseudorandom number sequences. IEEE Trans. Comput. , 2 , 258 - 262
    51. 51)
      • Boneh, D., DeMillo, R., Lipton, R.: `On the importance of checking cryptographic protocols for faults', Proc. Eurocrypt, 1999, p. 37–51, Springer LNCS 1233.
    52. 52)
      • M. Wang , I.F. Blake . Bit serial multiplication in finite fields. SIAM J. Discret. Math. , 1 , 140 - 148
    53. 53)
      • J.H. Patel , L.Y. Fung . Concurrent error detection in multiply and divide arrays. IEEE Trans. Comput. , 4 , 417 - 422
    54. 54)
      • Biham, E., Shamir, A.: `Differential fault analysis of secret key cryptosystems', Proc. Crypto, 1997, p. 513–525, Springer LNCS 1294.
    55. 55)
      • R.E. Blahut . (1985) Fast algorithms for digital signal processing.
    56. 56)
      • Hewlett Packard: ‘Table of low-weight binary irreducible polynomials’, HPL-98-135, 1998.
    57. 57)
      • M. Morii , M. Kasahara , D.L. Whiting . Efficient bit-serial multiplication and the discrete-time Wiener-Hopf equation over finite fields. IEEE Trans. Inf. Theory , 6 , 1177 - 1183
    58. 58)
      • C.W. Chiou , C.-Y. Lee , J.-M. Lin . Efficient systolic arrays for power-sum, inversion, and division in GF(2m). Int. J. Comput. Sci. Eng. Syst. , 1 , 27 - 41
    59. 59)
      • C.W. Chiou . Concurrent error detection in array multipliers for GF(2m) fields. IEE Electron. Lett. , 14 , 688 - 689
    60. 60)
      • National Institute for Standards and Technology, ‘Digital Signature Standard’, FIPS publication 186-2, January 2000.
    61. 61)
      • I.S. Reed , T.K. Truong . The use of finite fields to compute convolutions. IEEE Trans. Inf. Theory , 2 , 208 - 213
    62. 62)
      • C.W. Chiou , C.Y. Lee , A.W. Deng , J.M. Lin . Concurrent error detection in montgomery multiplication over GF(2m). IEICE Trans. Fundam. Electron. Commun. Comput. Sci. , 2 , 566 - 574
    63. 63)
      • J. Wakerly . (1980) Error detecting codes, self-checking circuits and applications.
    64. 64)
      • M.A. Hasan , M. Wang , V.K. Bhargava . Modular construction of low complexity parallel multipliers for a class of finite fields GF(2m). IEEE Trans. Comput. , 8 , 962 - 971
    65. 65)
      • S.W. Wei . VLSl architectures for computing exponentiations, multiplicative inverses, and divisions in GF(2m). IEEE Trans. Circuits Syst. , 10 , 847 - 855
    66. 66)
      • M74HC4075: ‘Triple 3-input OR gate, 2001 STMicroelectronics’, http://www.st.com/stonline/books/pdf/docs/1970.pdf.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds_20080122
Loading

Related content

content/journals/10.1049/iet-cds_20080122
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address