YU Wei, WANG Kunpeng, LI Bao, TIAN Song. Montgomery Algorithm over a Prime Field[J]. Chinese Journal of Electronics, 2019, 28(1): 39-44. doi: 10.1049/cje.2018.11.006
Citation: YU Wei, WANG Kunpeng, LI Bao, TIAN Song. Montgomery Algorithm over a Prime Field[J]. Chinese Journal of Electronics, 2019, 28(1): 39-44. doi: 10.1049/cje.2018.11.006

Montgomery Algorithm over a Prime Field

doi: 10.1049/cje.2018.11.006
Funds:  This work is supported by the National Natural Science Foundation of China (No.61872442, No.61502487) and the National Cryptography Development Fund (No.MMJJ20180216).
  • Received Date: 2017-02-20
  • Rev Recd Date: 2017-06-14
  • Publish Date: 2019-01-10
  • New formulae for point addition and point doubling on elliptic curves over prime fields are presented. Based on these formulae, an improved Montgomery algorithm is proposed. The theoretical analysis indicates that it is about 13.4% faster than Brier and Joye's Montgomery algorithm. Experiments on the elliptic curve over a 256-bit prime field recommended by the National Institute of Standards and Technology and over a 256-bit prime field in Chinese elliptic curve standard SM2 support the theoretical analysis.
  • loading
  • A. Capuñay and N. Thériault, "Computing optimal 2-3 chains for pairings", LATINCRYPT 2015, LNCS 9230, Springer Berlin Heidelberg, pp.225-244, 2015.
    C. Doche and D. Sutantyo, "New and improved methods to analyze and compute double-scalar multiplications", IEEE Transactions on Computers, Vol.63, No.1, pp.230-242, 2014.
    V. Dimitrov, L. Imbert and P.K. Mishra, "The doublebase number system and its application to elliptic curve cryptography", Mathematics of Computation, Vol.77, No.262, pp.1075-1104, 2008.
    N. Méloni and M. Anwar Hasan, "Elliptic curve scalar multiplication combining Yao's algorithm and double bases", CHES 2009, LNCS 5747, Springer Berlin Heidelberg, pp.304-316, 2009.
    W. Yu, K. Wang and B. Li, "Joint triple base number system for multi-scalar multiplications", ISPEC 2013, LNCS 7863, Springer Berlin Heidelberg, pp.160-173, 2013.
    W. Yu, K. Wang, B. Li, et al., "On the expansion length of triple-base number systems", AFRICACRYPT 2013, Cairo, Egypt, pp.424-432, 2013.
    C. Doche, "On the enumeration of double-base chains with applications to elliptic curve cryptography", ASIACRYPT 2014, LNCS 8874, Springer Berlin Heidelberg, pp.297-316, 2014.
    W. Yu, K. Wang, B. Li, et al., "Triple-base number system for scalar multiplications", AFRICACRYPT 2013, LNCS 7918, Springer Berlin Heidelberg, pp.433-451, 2013.
    N. Méloni, "New point addition formulae for ECC applications", WAIFI 2007, LNCS 4547, Springer Berlin Heidelberg, pp.189-201, 2007.
    R.R. Goundar, M. Joye and A. Miyaji, "Co-Z addition formulae and binary ladders on elliptic curves", CHES 2010, LNCS 6225, Springer Berlin Heidelberg, pp.65-79,2010.
    W. Li, W. Yu and K. Wang, "Improved tripling on elliptic curves", INSCRYPT 2015, LNCS 9589, Springer Berlin Heidelberg, pp.193-205, 2016.
    H. Cohen, A. Miyaji and T. Ono, "Efficient elliptic curve exponentiation using mixed coordinates", ASIACRYPT 1998, LNCS 1514, Springer Berlin Heidelberg, pp.51-65, 1998.
    R. Gallant, R. Lambert and S. Vanstone, "Faster point multiplication on elliptic curves with efficient endomorphisms", CRYPTO 2001, LNCS 2139, Springer Berlin Heidelberg, pp.190-200, 2001.
    S. Galbraith, X. Lin and M. Scott, "Endomorphisms for faster elliptic curve cryptography on a large class of curves", EUROCRYPT 2009, Cologne, Germany, pp.518-535, 2009.
    W. Trost and G. Xu, "On the optimal pre-computation of window τNAF for Koblitz curves", IEEE Transactions on Computers, Vol.65, No.9, pp.2918-2924, 2016.
    Z. Zhou, Z. Hu, M. Xu, et al., "Efficient 3-dimensional GLV method for faster point multiplication on some GLS elliptic curves", Information Processing Letters, Vol.110, No.22, pp.1003-1006, 2010.
    P. Longa and F. Sica, "Four-dimensional Gallant-LambertVanstone scalar multiplication", ASIACRYPT 2012, LNCS 7658, Springer Berlin Heidelberg, pp.718-739, 2012.
    Z. Hu, P. Longa and M. Xu, "Implementing the 4-dimensional GLV method on GLS elliptic curves with j-invariant 0", Design Codes and Cryptography, Vol.63, No.3, pp.331-343, 2012.
    X. Xu, W. Yu, K. Wang, et al., "Constructing isogenies on extended Jacobi quartic curves", INSCRYPT 2016, LNCS 10143, Springer Berlin Heidelberg, pp.416-427, 2016.
    L. Elmegaard-Fessel, "Efficient scalar multiplication and security against power analysis in cryptosystems based on the NIST elliptic curves over prime fields", https://eprint.iacr.org/2006/313,2006-9-9.
    P. Montgomery, "Speeding the Pollard and elliptic curve methods of factorization", Mathematics of Computation, Vol.48, No.177, pp.243-264, 1987.
    J. Lopez and R. Dahab, "Fast multiplication on elliptic curves over GF(2n) without precomputation", CHES 1999, LNCS 1717, Springer Berlin Heidelberg, pp.316-327, 1999.
    K. Okeya and K. Sakurai, "Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery-form elliptic curve", CHES 2001, LNCS 2162, Springer Berlin Heidelberg, pp.126-141, 2001.
    E. Brier and M. Joye, "Weierstrass elliptic curves and sidechannel attacks", PKC 2002, LNCS 2274, Springer Berlin Heidelberg, pp.335-345, 2002.
    H. Wang, B. Li and W. Yu, "Montgomery algorithm on elliptic curves over finite fields of character three", Journal on Communications, Vol.29, No.10, pp.25-29, 2008.
    "Public key cryptographic algorithm SM2 based on elliptic curves", http://www.sca.gov.cn/sca/xwdt/2010-12/17/content_1002386.shtml,2010-12-17.
    FIPS PUB 186-4, 2013, National institute of standards and technology(NIST), Digital Signature Standard(DSS).
    L. Zhang, K. Wang and H. Wang, "Unified and complete point addition formula for elliptic curves", Chinese Journal of Electronics, Vol.21, No.2, pp.345-349, 2012.
    M. Joye and C. Tymen, "Protections against differential analysis for elliptic curve cryptography-An algebraic approach", CHES 2001, LNCS 2162, Springer Berlin Heidelberg, pp.377-390, 2001.
    D. Bernstein and T. Lange, "Explicit-formulas database", http://www.hyperelliptic.org/EFD/,2017-1-1.
    T. St Denis, "Libtom", http://math.libtomcrypt.com,2017-1-11.
  • 加载中


    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (151) PDF downloads(423) Cited by()
    Proportional views


    DownLoad:  Full-Size Img  PowerPoint