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

access icon free Efficient digit-serial modular multiplication algorithm on FPGA

For cryptographic applications, such as DSA, RSA and ECC systems, the crypto-processors are required to perform modular multiplication (MM) on large integers over Galois field. A new digit-serial MM method is presented by using a variable size lookup table. The proposed modular multiplier can be designed for any digit-size d and modulus M which only requires simple operations such as addition and shifting. Based on theoretical analysis, the efficient digit-serial MM architecture requires the latency of clock cycles. As a result, the developed architecture can achieve less area–delay product on hardware when compared with previous designs.

References

    1. 1)
      • 13. Shieh, M.D., Chen, J.H., Lin, W.C., et al: ‘A new algorithm for high-speed modular multiplication design’, IEEE Trans. Circuits Syst. I. Regul. Pap., 2009, 56, pp. 20092019.
    2. 2)
      • 2. IEEE Std 1363-2000: ‘IEEE standard specifications for public-key cryptography’, 2000.
    3. 3)
      • 23. Erdem, S.S., Yank, T., Çelebi, A.: ‘A general digit-serial architecture for Montgomery modular multiplication’, IEEE Trans. Very Large Scale Integr. Syst., 2017, 25, pp. 16581668.
    4. 4)
      • 9. Blum, T., Paar, C.: ‘High-radix Montgomery modular exponentiation on reconfigurable hardware’, IEEE Trans. Comput., 2001, 50, pp. 759764.
    5. 5)
      • 6. Kornerup, P.: ‘High-radix modular multiplication for cryptosystems’. Proc. 11th IEEE Symp. Computer Arithmetic (ARITH-11), Windsor, Ont., Canada, 1993, pp. 277283.
    6. 6)
      • 14. Tenca, A.F., Koç, Ç.K.: ‘A scalable architecture for modular multiplication based on Montgomery's algorithm’, IEEE Trans. Comput., 1993, 52, pp. 12151221.
    7. 7)
      • 17. Kuang, S.R., Wu, K.Y., Lu, R.Y.: ‘Low-cost high-performance VLSI architecture for Montgomery modular multiplication’, IEEE Trans. Very Large Scale Integr. Syst., 2016, 24, pp. 434443.
    8. 8)
      • 3. Diffie, W., Hellman, M.: ‘New directions in cryptography’, IEEE Trans. Inf. Theory, 1976, 22, pp. 644654.
    9. 9)
      • 16. Kuang, S.R., Wang, J.P., Chang, K.C., et al: ‘Energy-efficient high-throughput Montgomery modular multipliers for RSA cryptosystems’, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2013, 21, pp. 19992009.
    10. 10)
      • 10. Hong, J.H., Wu, C.W.: ‘Cellular-array modular multiplier for fast RSA public-key cryptosystem based on modified Booth's algorithm’, IEEE Trans. Very Large Scale Integr. Syst., 2003, 11, pp. 474484.
    11. 11)
      • 5. Takagi, N.: ‘A radix-4 modular multiplication hardware algorithm for modular exponentiation’, IEEE Trans. Comput., 1992, 41, pp. 949956.
    12. 12)
      • 7. Walter, C.D.: ‘Systolic modular multiplication’, IEEE Trans. Comput., 1993, 42, pp. 376378.
    13. 13)
      • 11. Miyamoto, A., Homma, N., Aoki, T., et al: ‘Systematic design of RSA processors based on high-radix Montgomery multipliers’, IEEE Trans. Very Large Scale Integr. Syst., 2011, 19, pp. 11361146.
    14. 14)
      • 15. Shieh, M.D., Chen, J.H., Wu, H.H., et al: ‘A new modular exponentiation architecture for efficient design of RSA cryptosystem’, IEEE Trans. Very Large Scale Integr. (VLSI) Syst., 2008, 16, pp. 11511161.
    15. 15)
      • 8. Koç, Ç.K., Acar, T., Kaliski, B.S.: ‘Analyzing and comparing Montgomery multiplication algorithms’, IEEE Micro, 1992, 16, pp. 2633.
    16. 16)
      • 18. Shieh, M.D., Lin, W.C.: ‘Word-based Montgomery modular multiplication algorithm for low-latency scalable architectures’, IEEE Trans. Comput., 2010, 59, pp. 11451151.
    17. 17)
      • 20. Barrett, P.D.: ‘Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor’. Proc. Int. Cryptology Conf. Advances in Cryptology (CRYPTO ’86), 1987, pp. 311–323.
    18. 18)
      • 12. Huang, M., Gaj, K., El-Ghazawi, T.: ‘New hardware architectures for Montgomery modular multiplication algorithm’, IEEE Trans. Comput., 2011, 60, pp. 923936.
    19. 19)
      • 1. Rivest, R.L., Shamir, A., Adleman, L.: ‘A method for obtaining digital signatures and public-key cryptosystems’, Commun. ACM, 1978, 21, pp. 120126.
    20. 20)
      • 19. Kaihara, M.E., Takagi, N.: ‘A hardware algorithm for modular multiplication/division’, IEEE Trans. Comput., 2005, 54, pp. 1221.
    21. 21)
      • 22. Pai, Y.T., Chen, Y.K.: ‘The fastest carry lookahead adder’. Proc. Second IEEE Int. Workshop on Electronic Design, Test and Applications (DELTA'04), 2004, pp. 434436.
    22. 22)
      • 4. Blakely, G.R.: ‘A computer algorithm for calculating the product AB modulo M’, IEEE Trans. Comput., 1978, 32, pp. 497500.
    23. 23)
      • 21. Montgomery, P.L.: ‘Modular multiplication without trial division’, Math. Comput., 1985, 44, pp. 519521.
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cds.2017.0300
Loading

Related content

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