http://iet.metastore.ingenta.com
1887

Low-latency digit-serial dual basis multiplier for lightweight cryptosystems

Low-latency digit-serial dual basis multiplier for lightweight cryptosystems

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

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

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 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 Information Security — Recommend this title to your library

Thank you

Your recommendation has been sent to your librarian.

Various cryptosystems, such as elliptic curve and pairing-based cryptosystems, in resource-constrained security applications rely on finite field multiplication. For applications such as these, a digit-serial multiplier has the potential features to achieve a trade-off between space and time complexities. The authors propose an efficient decomposition of the multiplication into four independent sub-multiplication units to facilitate parallel processing, which is additionally facilitated by the systolic structures of the sub-multiplication units. The proposed architecture uses a four-bit scheme to construct a novel processing element, instead of using only one bit as is currently used in similar multipliers. The results of the synthesis show that the proposed digit-serial dual basis multiplier eliminates up to 96% of the critical path delay.

References

    1. 1)
      • R.L. Rivest , A. Shamir , L. Adleman .
        1. Rivest, R.L., Shamir, A., Adleman, L.: ‘A method for obtaining digital signatures and public-key cryptosystems’, Commun. ACM, 1978, 21, pp. 120126.
        . Commun. ACM , 120 - 126
    2. 2)
      • V.S. Miller .
        2. Miller, V.S.: ‘Use of elliptic curves in cryptography’. Proc. of Crypto 85, 1986 (LNCS, 218), pp. 417426.
        . Proc. of Crypto 85 , 417 - 426
    3. 3)
      • N. Koblitz .
        3. Koblitz, N.: ‘Elliptic curve cryptosystems’, Math. Comput., 1987, 48, pp. 203209.
        . Math. Comput. , 203 - 209
    4. 4)
      • (2000)
        4. FIPS 186-2: ‘Digital signature standard (DSS)’ (Federal Information Processing Standards Publication 186-2, Nat'l Inst. of Standards and Technology, 2000).
        .
    5. 5)
      • 5. IEEE Standard 1363-2000: ‘IEEE standard specifications for public-key cryptography’, January 2000.
        .
    6. 6)
      • 6. ISO/IEC 11770-3 : 2008: ‘Information technology – security techniques – key management – Part 3: mechanisms using asymmetric techniques’, 2008.
        .
    7. 7)
      • (2005)
        7. ANSI X9.62-2005: ‘Public key cryptography for the financial services industry: the elliptic curve digital signature algorithm (ECDSA)’ (American National Standards Institute (ANSI), 2005).
        .
    8. 8)
      • N. Koblitz .
        8. Koblitz, N.: ‘A family of Jacobians suitable for discrete log cryptosystems’. Advances in Cryptology, Proc. Crypto'88, 1988, pp. 9499.
        . Advances in Cryptology, Proc. Crypto'88 , 94 - 99
    9. 9)
      • R. Dutta , R. Barua , P. Sarkar .
        9. Dutta, R., Barua, R., Sarkar, P.: ‘Pairing-based cryptographic protocols: a survey’. Cryptology ePrint Archive, Report 064/2004, 2004.
        .
    10. 10)
      • T.C. Bartee , D.J. Schneider .
        10. Bartee, T.C., Schneider, D.J.: ‘Computation with finite fields’, Information and Computing, 1963, 6, pp. 7998.
        . Information and Computing , 79 - 98
    11. 11)
      • E.D. Mastrovito .
        11. Mastrovito, E.D.: ‘VLSI architectures for multiplication over finite field GF(2m)’. Proc. Sixth Int'l Conf. on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, (AAECC-6), Rome, 1988, pp. 297309.
        . Proc. Sixth Int'l Conf. on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes, (AAECC-6) , 297 - 309
    12. 12)
      • Ç.K. Koç , B. Sunar .
        12. Koç, Ç.K., Sunar, B.: ‘Low-complexity bit-parallel canonical and normal basis multipliers for a class of finite fields’, IEEE Trans. Comput., 1998, 47, (3), pp. 353356.
        . IEEE Trans. Comput. , 3 , 353 - 356
    13. 13)
      • T. Itoh , S. Tsujii .
        13. Itoh, T., Tsujii, S.: ‘Structure of parallel multipliers for a class of fields GF(2m)’, Inf. Comput., 1989, 83, pp. 2140.
        . Inf. Comput. , 21 - 40
    14. 14)
      • C.Y. Lee , E.H. Lu , J.Y. Lee .
        14. Lee, C.Y., Lu, E.H., Lee, J.Y.: ‘Bit-parallel systolic multipliers for GF(2m) fields defined by all-one and equally-spaced polynomials’, IEEE Trans. Comput., 2001, 50, (5), pp. 385393.
        . IEEE Trans. Comput. , 5 , 385 - 393
    15. 15)
      • C. Paar , P. Fleischmann , P. Roelse .
        15. Paar, C., Fleischmann, P., Roelse, P.: ‘Efficient multiplier architectures for Galois Fields GF(24n)’, IEEE Trans. Comput., 1998, 47, (2), pp. 162170.
        . IEEE Trans. Comput. , 2 , 162 - 170
    16. 16)
      • H. Wu .
        16. Wu, H.: ‘Bit-parallel finite field multiplier and squarer using polynomial basis’, IEEE Trans. Comput., 2002, 51, (7), pp. 750758.
        . IEEE Trans. Comput. , 7 , 750 - 758
    17. 17)
      • H. Fan , M.A. Hasan .
        17. Fan, H., Hasan, M.A.: ‘A new approach to subquadratic space complexity parallel multipliers for extended binary fields’, IEEE Trans. Comput., 2007, 56, (2), pp. 224233.
        . IEEE Trans. Comput. , 2 , 224 - 233
    18. 18)
      • J.-H. Guo , C.-L. Wang .
        18. Guo, J.-H., Wang, C.-L.: ‘Digit-serial systolic multiplier for finite fields GF(2m)’, IEE Proc. Comput. Digit.Tech., 1998, 145, (2), pp. 143148.
        . IEE Proc. Comput. Digit.Tech. , 2 , 143 - 148
    19. 19)
      • C.H. Kim , C.P. Hong , S. Kwon .
        19. Kim, C.H., Hong, C.P., Kwon, S.: ‘A digit-serial multiplier for finite field GF(2m)’, IEEE Trans. Very Large Scale Integr. Syst., 2005, 13, (4), pp. 476483.
        . IEEE Trans. Very Large Scale Integr. Syst. , 4 , 476 - 483
    20. 20)
      • S. Kumar , T. Wollinger , C. Paar .
        20. Kumar, S., Wollinger, T., Paar, C.: ‘Optimum digit-serial GF(2m) multipliers for curve-based cryptography’, IEEE Trans. Comput., 2006, 55, (10), pp. 13061311.
        . IEEE Trans. Comput. , 10 , 1306 - 1311
    21. 21)
      • S. Talapatra , H. Rahaman , J. Mathew .
        21. Talapatra, S., Rahaman, H., Mathew, J.: ‘Low complexity digit serial systolic Montgomery multipliers for special class of GF(2m)’, IEEE Trans. Very Large Scale Integr. Syst., 2010, 18, (5), pp. 847852.
        . IEEE Trans. Very Large Scale Integr. Syst. , 5 , 847 - 852
    22. 22)
      • W.-T. Huang , C.H. Chang , C.W. Chiou .
        22. Huang, W.-T., Chang, C.H., Chiou, C.W., et al: ‘Non-XOR approach for low-cost bit-parallel polynomial basis multiplier over GF(2m)’, IET Inf. Sec., 2011, 5, (3), pp. 152162.
        . IET Inf. Sec. , 3 , 152 - 162
    23. 23)
      • J. Xie , P.K. Meher , J. He .
        23. Xie, J., Meher, P.K., He, J.: ‘Low-latency area-delay-efficient systolic multiplier over GF(2m) for a wider class of trinomials using parallel register sharing’. IEEE Int. Symp. on Circuits and Systems, (ISCAS'12), Seoul, Korea, 2012, pp. 8992.
        . IEEE Int. Symp. on Circuits and Systems, (ISCAS'12) , 89 - 92
    24. 24)
      • J. Xie , J.J. He , P.K. Meher .
        24. Xie, J., He, J.J., Meher, P.K.: ‘Low latency systolic Montgomery multiplier for finite field GF(2m) based on pentanomials’, IEEE Trans. Very Large Scale Integr. Syst., 2013, 21, (2), pp. 385389.
        . IEEE Trans. Very Large Scale Integr. Syst. , 2 , 385 - 389
    25. 25)
      • C.Y. Lee , C.W. Chiou .
        25. Lee, C.Y., Chiou, C.W.: ‘Efficient design of low-complexity bit-parallel systolic Hankel multipliers to implement multiplication in normal and dual bases of GF(2m)’, IEICE Trans. Fund. Electron. Commun. Comput. Sci., 2005, E88-A, (11), pp. 31693179.
        . IEICE Trans. Fund. Electron. Commun. Comput. Sci. , 11 , 3169 - 3179
    26. 26)
      • J.L. Massey , J.K. Omura .
        26. Massey, J.L., Omura, J.K.: ‘Computational method and apparatus for finite field arithmetic’. U.S. Patent Number 4,587,627, May 1986.
        .
    27. 27)
      • C.C. Wang , T.K. Troung , H.M. Shao .
        27. Wang, C.C., Troung, T.K., Shao, H.M., et al: ‘VLSI architectures for computing multiplications and inverses in GF(2m)’, IEEE Trans. Comput., 1985, C-34, (8), pp. 709717.
        . IEEE Trans. Comput. , 8 , 709 - 717
    28. 28)
      • A. Reyhani-Masoleh .
        28. Reyhani-Masoleh, A.: ‘Efficient algorithms and architectures for field multiplication using Gaussian normal bases’, IEEE Trans. Comput., 2006, 55, (1), pp. 3447.
        . IEEE Trans. Comput. , 1 , 34 - 47
    29. 29)
      • G.B. Agnew , R.C. Mullin , I.M. Onyszchuk .
        29. Agnew, G.B., Mullin, R.C., Onyszchuk, I.M., et al: ‘An implementation for a fast public-key cryptosystem’, J. Cryptol., 1991, 3, pp. 6379.
        . J. Cryptol. , 63 - 79
    30. 30)
      • M.A. Hasan , M.Z. Wang , V.K. Bhargava .
        30. Hasan, M.A., Wang, M.Z., Bhargava, V.K.: ‘A modified Massey-Omura parallel multiplier for a class of finite fields’, IEEE Trans. Comput., 1993, 42, (10), pp. 12781280.
        . IEEE Trans. Comput. , 10 , 1278 - 1280
    31. 31)
      • S. Kwon .
        31. Kwon, S.: ‘A low complexity and a low latency bit parallel systolic multiplier over GF(2m) using an optimal normal basis of type II’. Proc. of the 16th IEEE Symp. on Computer Arithmetic, Santiago de Compostela, Spain, 2003, pp. 196202.
        . Proc. of the 16th IEEE Symp. on Computer Arithmetic , 196 - 202
    32. 32)
      • H. Fan , M.A. Hasan .
        32. Fan, H., Hasan, M.A.: ‘Subquadratic computational complexity schemes for extended binary field multiplication using optimal normal bases’, IEEE Trans. Comput., 2007, 56, (10), pp. 14351437.
        . IEEE Trans. Comput. , 10 , 1435 - 1437
    33. 33)
      • C.-Y. Lee , C.W. Chiou .
        33. Lee, C.-Y., Chiou, C.W.: ‘Scalable Gaussian normal basis multipliers over GF(2m) using Hankel matrix-vector representation’, J. Signal Process. Syst. Signal Image Video Technol., 2012, 69, (2), pp. 197211.
        . J. Signal Process. Syst. Signal Image Video Technol. , 2 , 197 - 211
    34. 34)
      • C.W. Chiou , T.-P. Chuang , S.-S. Lin .
        34. Chiou, C.W., Chuang, T.-P., Lin, S.-S., et al: ‘Palindromic-like representation for Gaussian normal basis multiplier over GF(2m) with odd type-t’, IET Inf. Sec., 2012, 6, (4), pp. 318323.
        . IET Inf. Sec. , 4 , 318 - 323
    35. 35)
      • C.W. Chiou , H.W. Chang , W.-Y. Liang .
        35. Chiou, C.W., Chang, H.W., Liang, W.-Y., et al: ‘Low-complexity Gaussian normal basis multiplier over GF(2m)’, IET Inf. Sec., 2012, 6, (4), pp. 310317.
        . IET Inf. Sec. , 4 , 310 - 317
    36. 36)
      • E.R. Berlekamp .
        36. Berlekamp, E.R.: ‘Bit-serial reed-solomon encoder’, IEEE Trans. Inf. Theory, 1982, IT-28, pp. 869874.
        . IEEE Trans. Inf. Theory , 869 - 874
    37. 37)
      • H. Wu , M.A. Hasan , I.F. Blake .
        37. Wu, H., Hasan, M.A., Blake, I.F.: ‘New low-complexity bit-parallel finite field multipliers using weakly dual bases’, IEEE Trans. Comput., 1998, 47, (11), pp. 12231234.
        . IEEE Trans. Comput. , 11 , 1223 - 1234
    38. 38)
      • S.T.J. Fenn , M. Benaissa , D. Taylor .
        38. Fenn, S.T.J., Benaissa, M., Taylor, D.: ‘GF(2m) multiplication and division over the dual basis’, IEEE Trans. Comput., 1996, 45, (3), pp. 319327.
        . IEEE Trans. Comput. , 3 , 319 - 327
    39. 39)
      • M. Wang , I.F. Blake .
        39. Wang, M., Blake, I.F.: ‘Bit serial multiplication in finite fields’, SIAM J. Disc. Math., 1990, 3, (1), pp. 140148.
        . SIAM J. Disc. Math. , 1 , 140 - 148
    40. 40)
      • J.-H. Wang , H.W. Chang , C.W. Chiou .
        40. Wang, J.-H., Chang, H.W., Chiou, C.W., et al: ‘Low-complexity design of bit-parallel dual basis multiplier over GF(2m)’, IET Inf. Sec., 2012, 6, (4), pp. 324328.
        . IET Inf. Sec. , 4 , 324 - 328
    41. 41)
      • M.K. Ibrahim , A. Aggoun .
        41. Ibrahim, M.K., Aggoun, A.: ‘Dual basis digit serial GF(2m) multiplier’, Int. J. Electron., 2002, 89, (7), pp. 517523.
        . Int. J. Electron. , 7 , 517 - 523
    42. 42)
      • P.-L. Chang , L.-H. Chen , C.-Y. Lee .
        42. Chang, P.-L., Chen, L.-H., Lee, C.-Y.: ‘Low-complexity dual basis digit serial GF(2m) multiplier’, ICIC Exp. Lett., 2009, 3, (4), pp. 11131118.
        . ICIC Exp. Lett. , 4 , 1113 - 1118
    43. 43)
      • P.-L. Chang , F.-H. Hsieh , L.-H. Chen .
        43. Chang, P.-L., Hsieh, F.-H., Chen, L.-H., et al: ‘Efficient digit serial dual basis GF(2m) multiplier’. Proc. of the 2010 5th IEEE Conf. on Industrial Electronics and Applications, (ICIEA 2010), Taichung, Taiwan, 2010, pp. 166170.
        . Proc. of the 2010 5th IEEE Conf. on Industrial Electronics and Applications, (ICIEA 2010) , 166 - 170
    44. 44)
      • L.-H. Chen , P.-L. Chang , C.-Y. Lee .
        44. Chen, L.-H., Chang, P.-L., Lee, C.-Y., et al: ‘Scalable and systolic dual basis multiplier over GF(2m)’, Int. J. Innovat. Comput. Inf. Control, 2011, 7, (3), pp. 11931208.
        . Int. J. Innovat. Comput. Inf. Control , 3 , 1193 - 1208
    45. 45)
      • Y.Y. Hua , J.-M. Lin , C.W. Chiou .
        45. Hua, Y.Y., Lin, J.-M., Chiou, C.W., et al: ‘A novel digit-serial dual basis Karatsuba multiplier over GF(2m)’, J. Comput., 2012, 23, (2), pp. 8094.
        . J. Comput. , 2 , 80 - 94
    46. 46)
      • Y.Y. Hua , J.-M. Lin , C.W. Chiou .
        46. Hua, Y.Y., Lin, J.-M., Chiou, C.W., et al: ‘Low space complexity digit serial dual basis systolic multiplier over Galois field GF(2m) using Hankel Matrix and Karatsuba algorithm’, IET Inf. Sec., 2013, 7, (2), pp. 7586.
        . IET Inf. Sec. , 2 , 75 - 86
    47. 47)
      • J.L. Imaña .
        47. Imaña, J.L.: ‘Low latency GF(2m) polynomial basis multiplier’, IEEE Trans. Circ. Syst. I Reg. Papers, 2011, 58, (5), pp. 935946.
        . IEEE Trans. Circ. Syst. I Reg. Papers , 5 , 935 - 946
    48. 48)
      • J.-S. Pan , C.-Y. Lee , P.K. Meher .
        48. Pan, J.-S., Lee, C.-Y., Meher, P.K.: ‘Low-latency digit-serial and digit-parallel systolic multipliers for large binary extension fields’, IEEE Trans. Circ. Syst. I Reg. Papers, 2013, 60, (12), pp. 31953204.
        . IEEE Trans. Circ. Syst. I Reg. Papers , 12 , 3195 - 3204
    49. 49)
      • W.-C. Lin , J.-H. Ye , M.-D. Shieh .
        49. Lin, W.-C., Ye, J.-H., Shieh, M.-D.: ‘Scalable Montgomery modular multiplication architecture with low-latency and low-memory bandwidth requirement’, IEEE Trans. Comput., 2014, 63, (2), pp. 475483.
        . IEEE Trans. Comput. , 2 , 475 - 483
    50. 50)
      • J.-S. Pan , R. Azarderakhsh , M.M. Kermani .
        50. Pan, J.-S., Azarderakhsh, R., Kermani, M.M., et al: ‘Low-latency digit-serial systolic double basis multiplier over GF(2m) using subquadratic Toeplitz matrix-vector product approach’, IEEE Trans. Comput., 2014, 63, (5), pp. 11691181.
        . IEEE Trans. Comput. , 5 , 1169 - 1181
    51. 51)
      • 51. NanGate Standard Cell Library. http://www.si2.org/openeda.si2.org/projects/nangatelib/, 2015/5/7.
        .
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-ifs.2015.0336
Loading

Related content

content/journals/10.1049/iet-ifs.2015.0336
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
This is a required field
Please enter a valid email address