nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Three Dimensional Montgomery Ladder, Differential Point Tripling on Montgomery Curves and Point Quintupling on Weierstrass’ and Edwards Curves

verfasst von : Srinivasa Rao Subramanya Rao

Erschienen in: Progress in Cryptology – AFRICACRYPT 2016

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Elliptic Curve Cryptography is an important alternative to traditional public key schemes such as RSA. This paper presents

(i)

a simultaneous triple scalar multiplication algorithm to compute the x-coordinate of \(kP+lQ+uR\) on a Montgomery Curve \(E_{m}\) defined over \(\mathbb {F}_p\) which is about 15 to 22 % faster than the straight forward method of doing the same. The algorithm, motivated by Bernstein’s paper on Differential Addition Chains, where the author proposes various 2-dimensional differential addition chains and asks for 3-dimensional versions to be constructed, can be generalized to other elliptic curve forms with differential addition formula,

(ii)

a formula for Differential point tripling on Montgomery Curves which is slightly better than computing 3P as \(2P+P\) and relevant in the implementation of Montgomery’s PRAC and

(iii)

an improvement in Mishra and Dimitrov’s point Quintupling algorithm for Weierstrass’ curves and an efficient Quintupling algorithm for Edwards Curves.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A Fast and Compact FPGA Implementation of Elliptic Curve Cryptography Using Lambda Coordinates

Nächstes Kapitel Cryptanalysis of PRINCE with Minimal Data

Nur mit Berechtigung zugänglich

Stinson, D.: Cryptography: Theory and Practice, 3rd edn. CRC Press, Boca Raton (2005)MATH

Bellman, R., Straus, E.G.: Addition chains of vectors (problem 5125). Am. Math. Mon. 71, 806–808 (1964)MathSciNetCrossRef

ElGamal, T.: A public key cryptosystem and a signature scheme base on discrete logarithms. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1985)CrossRef

Cohen, H., Frey, G.: Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, Boca Raton (2006)MATH

Solinas, J.A.: Low-weight binary representations for pairs of integers. Combinatorics and Optimization Research Report CORR 2001-41. University of Waterloo (2001)

Montgomery, P.L.: Speeding the pollard and elliptic curve methods of factorization. Math. Comput. 48(177), 243–264 (1987)MathSciNetCrossRefMATH

Akishita, T.: Fast simultaneous scalar multiplication on elliptic curve with montgomery form. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, pp. 255–267. Springer, Heidelberg (2001)CrossRef

Stam, M.: Speeding up subgroup cryptosystems. Ph.D. thesis, Technische Universiteit Eindhoven (2003)

Knuth, D.E.: The Art of Computer Programming. Seminumerical algorithms, vol. 2, 3rd edn. Pearson, London (1998)

10.

Bernstein, D.J.: Differential Addition Chains (2006). http://cr.yp.to/ecdh/diffchain-20060219.pdf. Accessed 25 January 2015

11.

Brown, D.R.L.: Multi-dimensional Montgomery ladders for elliptic curves (2006). http://eprint.iacr.org/2006/220. Accessed 25 January 2015

12.

Brown, D.R.L.: Multi-dimensional Montgomery ladders for elliptic curves. Patent No. US8750500 B2 (2014). http://www.google.com/patents/US8750500

13.

Montgomery, P.L.: Evaluating recurrences of form \(X_{m+n} = f(x_{m}, X_{n}, X_{m-n})\) via Lucas chains (1992). https://cr.yp.to/bib/1992/montgomery-lucas.ps. Accessed 2 February 2016

14.

Azarderakhsh, R., Karabina, K.: A New Double Point Multiplication Method and its Implementation on Binary Elliptic Curves with Endomorphisms. http://cacr.uwaterloo.ca/techreports/2012/cacr2012-24.pdf

15.

Okeya, K., Sakurai, K.: Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a montgomery form elliptic curve. In: Ko, K., Naccache, D., Paar, C. (eds.) CHES 2001. LNCS, vol. 2162, pp. 126–141. Springer, Heidelberg (2001)CrossRef

16.

Brent, R., Zimmermann, P.: Modern Computer Arithmetic. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge (2010)CrossRefMATH

17.

Subramanya Rao, S.R.: A note on Schoenmakers’ algorithm for multi-exponentiation. In: Obaidat, M.S., Lorenz, P., Samarati, P. (eds.) Proceedings of International Conference on Security and Cryptography, SECRYPT 2015, pp. 384–391. SciTePress, Setúbal (2015)

18.

Menezes, A., van Oorschot, P., Vanstone, S.: Handbook of Applied Cryptography. Taylor and Francis, London (1997)MATH

19.

Antipa, A., Brown, D., Gallant, R., Lambert, R., Struik, R., Vanstone, S.: Accelerated verification of ECDSA signatures. http://cacr.uwaterloo.ca/techreports/2005/cacr2005-28.pdf. Accessed 2 February 2016

20.

Cheon, J.H., Yi, J.H.: Fast batch verification of multiple signatures. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 442–457. Springer, Heidelberg (2007)

21.

Karati, S., Das, A., Roychoudhury, D.: Randomized batch verification of standard ECDSA signatures. In: Chakraborty, R.S., Matyas, V., Schaumont, P. (eds.) SPACE 2014. LNCS, vol. 8804, pp. 237–255. Springer, Heidelberg (2014)

22.

Bernstein, D.J., Birkner, P., Lange, T., Peters, C.: Optimizing Double-Base Elliptic-Curve Single-Scalar Multiplication. https://cr.yp.to/antiforgery/doublebase-20071028.pdf. Accessed 2 February 2016

23.

Dimitrov, V.S., Imbert, L., Mishra, P.K.: Efficient and Secure Elliptic Curve Point Multiplicaton Using Double-Base Chains. https://www.iacr.org/archive/asiacrypt2005/059/059.pdf. Accessed 2 February 2016

24.

Dimitrov, V.S., Cooklev, T.: Hybrid algorithm for the computation of the matrix polynomial \(I+A+ \dots +A^{n-1}\). IEEE Trans. Circ. Syst. 42(7), 377–380 (1995)MathSciNetCrossRefMATH

25.

Mishra, P.K., Dimitrov, V.S.: Efficient Quintuple Formuals for Elliptic Curves and Efficeint Scalar Multiplication Using Multibase Number Representation. https://eprint.iacr.org/2007/040.pdf. Accessed 2 February 2016

26.

Giorgi, P., Imbert, L., Izard, T.: Optimizing elliptic curve scalar multiplications for small scalars. In: Mathematics for Signal and Information Processing, San Diego, CA, United States, p. 74440N (2009)

27.

Longa, P., Miri, A.: New Multibase Non-Adjacent Form Scalar Multiplication and its applications to Elliptic Curve Cryptosystems. https://eprint.iacr.org/2008/052.pdf. Accessed 2 February 2016

28.

Lopez, J., Dahab, R.: Fast multiplication on elliptic curves over \(GF(2^m)\) without precomputation. In: Ko, K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 316–327. Springer, Heidelberg (1999)CrossRef

29.

Fischer, W., Giraud, C., Knudsen, E.W., Seifert, J.-P.: Parallel scalar multiplication on general elliptic curves over \(\mathbb{F}_p\) hedged against Non-Differential Side-Channel Attacks. http://eprint.iacr.org/2002/007.pdf. Accessed 2 February 2016

30.

Brier, E., Joye, M.: Weierstrass elliptic curves and side-channel attacks. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 335–345. Springer, Heidelberg (2002)

31.

Bernstein, D.J., Lange, T., Rezaeian Farashahi, R.: Binary edwards curves. In: Oswald, E., Rohatgi, P. (eds.) CHES 2008. LNCS, vol. 5154, pp. 244–265. Springer, Heidelberg (2008)CrossRef

32.

Justus, B., Loebenberger, D.: Differential addition in generalized edwards coordinates. In: Echizen, I., Kunihiro, N., Sasaki, R. (eds.) IWSEC 2010. LNCS, vol. 6434, pp. 316–325. Springer, Heidelberg (2010)CrossRef

33.

Devigne, J., Joye, M.: Binary huff curves. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol. 6558, pp. 340–355. Springer, Heidelberg (2011)CrossRef

34.

Hutter, M., Joye, M., Sierra, Y.: Memory-constrained implementations of elliptic curve cryptography in co-Z coordinate representation. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol. 6737, pp. 170–187. Springer, Heidelberg (2011)CrossRef

35.

Wu, H., Tang, C., Feng, R.: A new model of binary elliptic curves. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 399–411. Springer, Heidelberg (2012)CrossRef

36.

Farashahi, R.R., Joye, M.: Efficient arithmetic on hessian curves. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 243–260. Springer, Heidelberg (2010)CrossRef

37.

Abarzúa, R., Thériault, N.: Complete atomic blocks for elliptic curves in jacobian coordinates over prime fields. In: Hevia, A., Neven, G. (eds.) LatinCrypt 2012. LNCS, vol. 7533, pp. 37–55. Springer, Heidelberg (2012)CrossRef

38.

Longa, P., Miri, A.: Fast and flexible elliptic curves point arithmetic over prime fields. IEEE Trans. Comput. 57(3), 289–302 (2008)MathSciNetCrossRefMATH

39.

Bernstein, D.J.: Curve25519: New Diffie Hellman Speed Records. https://cr.yp.to/ecdh/curve25519-20060209.pdf. Accessed 2 February 2016

Titel: Three Dimensional Montgomery Ladder, Differential Point Tripling on Montgomery Curves and Point Quintupling on Weierstrass’ and Edwards Curves
verfasst von: Srinivasa Rao Subramanya Rao
Verlag: Springer International Publishing
Buch: Progress in Cryptology – AFRICACRYPT 2016
Print ISBN: 978-3-319-31516-4

Electronic ISBN: 978-3-319-31517-1

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-319-31517-1_5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner