Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Arithmetic of \(\tau \)-adic expansions for lightweight Koblitz curve cryptography

  • Regular Paper
  • Published:
Journal of Cryptographic Engineering Aims and scope Submit manuscript

Abstract

Koblitz curves allow very efficient elliptic curve cryptography. The reason is that one can trade expensive point doublings to cheap Frobenius endomorphisms by representing the scalar as a \(\tau \)-adic expansion. Typically elliptic curve cryptosystems, such as ECDSA, also require the scalar as an integer. This results in a need for conversions between integers and the \(\tau \)-adic domain, which are costly and hinder the use of Koblitz curves on very constrained devices, such as RFID tags, wireless sensors, or certain applications of the Internet of things. We provide solutions to this problem by showing how complete cryptographic processes, such as ECDSA signing, can be completed in the \(\tau \)-adic domain with very few resources. This allows outsourcing conversions to a more powerful party. We provide several algorithms for performing arithmetic operations in the \(\tau \)-adic domain. In particular, we introduce a new representation allowing more efficient and secure computations compared to the algorithms available in the preliminary version of this work from CARDIS 2014. We also provide datapath extensions with different speed and side-channel resistance properties that require areas from less than one hundred to a few hundred gate equivalents on 0.13-\(\upmu \)m CMOS. These extensions are applicable for all Koblitz curves.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. Obtained by synthesizing 16-bit adder/subtractor and 16-bit binary multiplier codes for 130-nm CMOS using the same setup as above.

References

  1. Adikari, J., Dimitrov, V., Järvinen, K.: A fast hardware architecture for integer to \(\tau \)NAF conversion for Koblitz curves. IEEE Trans. Comput. 61(5), 732–737 (2012)

    Article  MathSciNet  Google Scholar 

  2. Ahmadi, O., Hankerson, D., Rodríguez-Henríquez, F.: Parallel formulations of scalar multiplication on Koblitz curves. J. Univ. Comput. Sci. 14(3), 481–504 (2008)

    MathSciNet  MATH  Google Scholar 

  3. Aranha, D.F., Faz-Hernández, A., López, J., Rodríguez-Henríquez, F.: Faster implementation of scalar multiplication on Koblitz curves. In: Progress in Cryptology (LATINCRYPT 2012), LNCS, vol. 7533, pp. 177–193. Springer, Berlin (2012)

    Chapter  Google Scholar 

  4. Azarderakhsh, R., Järvinen, K.U., Mozaffari-Kermani, M.: Efficient algorithm and architecture for elliptic curve cryptography for extremely constrained secure applications. IEEE Trans. Circuits Syst. I Reg. Pap. 61(4), 1144–1155 (2014)

    Article  Google Scholar 

  5. Azarderakhsh, R., Reyhani-Masoleh, A.: High-performance implementation of point multiplication on Koblitz curves. IEEE Trans. Circuits Syst. II 60(1), 41–45 (2013)

    Article  Google Scholar 

  6. Batina, L., Mentens, N., Sakiyama, K., Preneel, B., Verbauwhede, I.: Low-cost elliptic curve cryptography for wireless sensor networks. In: Proceedings of 3rd European Workshop on Security and Privacy in Ad-Hoc and Sensor Networks (ESAS 2006). LNCS, vol. 4357, pp. 6–17 (2006)

    Google Scholar 

  7. Bauer, A., Jaulmes, E., Prouff, E., Reinhard, J.R., Wild, J.: Horizontal collision correlation attack on elliptic curves. Cryptogr. Commun. 7(1), 91–119 (2015)

    Article  MathSciNet  Google Scholar 

  8. Benits, Jr., W.D., Galbraith, S.D.: The GPS identification scheme using Frobenius expansions. In: Western European Workshop Research in Cryptology (WEWoRC’07). LNCS, vol. 4945, pp. 13–27 (2008)

  9. Brumley, B.B., Järvinen, K.: Koblitz curves and integer equivalents of Frobenius expansions. In: Selected Areas in Cryptography (SAC 2007). LNCS, vol. 4876, pp. 126–137 (2007)

  10. Brumley, B.B., Järvinen, K.U.: Conversion algorithms and implementations for Koblitz curve cryptography. IEEE Trans. Comput. 59(1), 81–92 (2010)

    Article  MathSciNet  Google Scholar 

  11. Cinnati Loi, K.C., An, S., Ko, S.B.: FPGA implementation of low latency scalable elliptic curve cryptosystem processor in \(GF(2^m)\). In: IEEE International Symposium on Circuits and Systems (ISCAS 2014), pp. 822–825. IEEE (2014)

  12. Cinnati Loi, K.C., Ko, S.B.: High performance scalable elliptic curve cryptosystem processor for Koblitz curves. Microproc. Microsyst. 37(4), 394–406 (2013)

    Google Scholar 

  13. De Clercq, R., Uhsadel, L., Van Herrewege, A., Verbauwhede, I.: Ultra low-power implementation of ECC on the ARM Cortex-M0+. In: Design Automation Conference (DAC 2014), pp. 1–6. ACM, New York (2014)

  14. Hankerson, D., Hernandez, J.L., Menezes, A.: Software implementation of elliptic curve cryptography over binary fields. In: Cryptographic Hardware and Embedded Systems (CHES 2000). LNCS, vol. 1965, pp. 1–24. Springer (2000)

  15. Hanley, N., Kim, H., Tunstall, M.: Exploiting collisions in addition chain-based exponentiation algorithms using a single trace. In: Topics in Cryptology—CT-RSA 2015. Lecture Notes in Computer Science, vol. 9048, pp. 431–448. Springer, Berlin (2015)

    MATH  Google Scholar 

  16. Hanser, C., Wagner, C.: Speeding up the fixed-base comb method for faster scalar multiplication on Koblitz curves. In: Modern Cryptography and Security Engineering (MoCrySEn 2013), LNCS, vol. 8128, pp. 168–179. Springer, Berlin (2013)

    Chapter  Google Scholar 

  17. Hein, D.M., Wolkerstorfer, J., Felber, N.: ECC is ready for RFID: a proof in silicon. In: Selected Areas in Cryptography (SAC 2008). LNCS, vol. 5381, pp. 401–413 (2009)

    Chapter  Google Scholar 

  18. Järvinen, K.: Optimized FPGA-based elliptic curve cryptography processor for high-speed applications. Integration 44(4), 270–279 (2011)

    Article  Google Scholar 

  19. Järvinen, K., Forsten, J., Skyttä, J.: Efficient circuitry for computing \(\tau \)-adic non-adjacent form. In: Proceedings of 13th IEEE International Conference on Electronics, Circuits and Systems (ICECS 2006), pp. 232–235 (2006)

  20. Järvinen, K., Verbauwhede, I.: How to use Koblitz curves on small devices? In: Smart Card Research and Advanced Application Conference (CARDIS 2014). LNCS, vol. 8968, pp. 154–170 (2015)

    Google Scholar 

  21. Joye, M., Tymen, C.: Compact encoding of non-adjacent forms with applications to elliptic curve cryptography. In: Public Key Cryptography (PKC 2001). LNCS, vol. 1992, pp. 353–364 (2001)

    Chapter  Google Scholar 

  22. Koblitz, N.: Elliptic curve cryptosystems. Math. Comput. 48(177), 203–209 (1987)

    Article  MathSciNet  Google Scholar 

  23. Koblitz, N.: CM-curves with good cryptographic properties. In: CRYPTO ’91. LNCS, vol. 576, pp. 279–287 (1991)

  24. Koçabas, Ü., Fan, J., Verbauwhede, I.: Implementation of binary Edwards curves for very-constrained devices. In: Proceedings of 21st IEEE International Conference on Application-Specific Systems Architectures and Processors (ASAP 2010), pp. 185–191 (2010)

  25. Lange, T.: Koblitz curve cryptosystems. Finite Fields Appl. 11, 200–229 (2005)

    Article  MathSciNet  Google Scholar 

  26. Lee, Y.K., Sakiyama, K., Batina, L., Verbauwhede, I.: Elliptic-curve-based security processor for RFID. IEEE Trans. Comput. 57(11), 1514–1527 (2008)

    Article  MathSciNet  Google Scholar 

  27. Lutz, J., Hasan, A.: High performance FPGA based elliptic curve cryptographic co-processor. In: International Conference on Information Technology: Coding and Computing (ITCC 2004), vol. 2, pp. 486–492. IEEE (2004)

  28. Meier, W., Staffelbach, O.: Efficient multiplication on certain nonsupersingular elliptic curves. In: CRYPTO ’92. LNCS, vol. 740, pp. 333–344 (1993)

  29. Miller, V.S.: Use of elliptic curves in cryptography. In: CRYPTO ’85. LNCS, vol. 218, pp. 417–426 (1986)

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

    Article  MathSciNet  Google Scholar 

  31. Naccache, D., M’Raïhi, D., Vaudenay, S., Raphaeli, D.: Can D.S.A. be improved? Complexity trade-offs with the digital signature algorithm. In: EUROCRYPT ’94. LNCS, vol. 950, pp. 77–85 (1994)

  32. National Institute of Standards and Technology (NIST): Digital signature standard (DSS). FIPS PUB 186-4 (2013)

  33. Okada, S., Torii, N., Itoh, K., Takenaka, M.: Implementation of elliptic curve cryptographic coprocessor over \(GF(2^m)\) on an FPGA. In: Cryptographic Hardware and Embedded Systems (CHES 2000), LNCS, vol. 1965, pp. 25–40. Springer, Berlin (2000)

  34. Okeya, K., Takagi, T., Vuillaume, C.: Efficient representations on Koblitz curves with resistance to side channel attacks. In: Proceedings of 10th Australasian Conference on Information Security and Privacy (ACISP 2005). LNCS, vol. 3574, pp. 218–229 (2005)

    Chapter  Google Scholar 

  35. Oren, Y., Feldhofer, M.: A low-resource public-key identification scheme for RFID tags and sensor nodes. In: ACM Conference on Wireless Network Security (WiSec’09), pp. 59–68. ACM (2009)

  36. Secunet Security Networks AG: Elliptic curve cryptography “Made in Germany”. Press release (2014). https://www.secunet.com/fileadmin/user_upload/Presse/Pressemitteilungen/Pressemitteilungen_EN/Pressemitteilungen_2014_EN/140625_PI_ECC_EN.pdf. Retrieved 21 Feb 2017

  37. Sinha Roy, S., Fan, J., Verbauwhede, I.: Accelerating scalar conversion for Koblitz curve cryptoprocessors on hardware platforms. IEEE Trans. VLSI Syst. 23(5), 810–818 (2015)

    Article  Google Scholar 

  38. Sinha Roy, S., Järvinen, K., Verbauwhede, I.: Lightweight coprocessor for Koblitz curves: 283-bit ECC including scalar conversion with only 4.3 kGE. In: Cryptographic Hardware and Embedded Systems (CHES 2015). LNCS, vol. 9293, pp. 102–122 (2015)

  39. Solinas, J.A.: Efficient arithmetic on Koblitz curves. Des. Code Cryptogr. 19(2–3), 195–249 (2000)

    Article  MathSciNet  Google Scholar 

  40. Taverne, J., Faz-Hernández, A., Aranha, D.F., Rodríguez-Henríquez, F., Hankerson, D., López, J.: Speeding scalar multiplication over binary elliptic curves using the new carry-less multiplication instruction. J. Cryptogr. Eng. 1(3), 187–199 (2011)

    Article  Google Scholar 

  41. Vuillaume, C., Okeya, K., Takagi, T.: Defeating simple power analysis on Koblitz curves. IEICE Trans. Fund. Elect. E89–A(5), 1362–1369 (2006)

    Article  Google Scholar 

  42. Weimerskirch, A., Stebila, D., Shantz, S.C.: Generic \(GF(2^m)\) arithmetic in software and its application to ECC. In: Australasian Conference on Information Security and Privacy (ACISP 2003). LNCS, vol. 2727, pp. 79–92. Springer, Berlin (2003)

    Chapter  Google Scholar 

Download references

Acknowledgements

This work was done when K. Järvinen was an FWO Pegasus Marie Curie Fellow. S. Sinha Roy was supported by the Erasmus Mundus PhD Scholarship. The work was partly funded by KU Leuven under GOA TENSE (GOA/11/007) and the F+ fellowship (F+/13/039) and by the Hercules Foundation (AKUL/11/19). We thank one of the anonymous reviewers of a preliminary version of this paper for pointing out the option of Remark 5.

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Helsinki, Gustaf Hällströmin katu 2b, 00560, Helsinki, Finland

    Kimmo Järvinen

  2. KU Leuven ESAT/COSIC and imec, Kasteelpark Arenberg 10 bus 2452, 3001, Leuven-Heverlee, Belgium

    Sujoy Sinha Roy & Ingrid Verbauwhede

Authors
  1. Kimmo Järvinen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Sujoy Sinha Roy
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ingrid Verbauwhede
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Kimmo Järvinen.

Additional information

This work was done when K. Järvinen was also with KU Leuven.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Järvinen, K., Sinha Roy, S. & Verbauwhede, I. Arithmetic of \(\tau \)-adic expansions for lightweight Koblitz curve cryptography. J Cryptogr Eng 8, 285–300 (2018). https://doi.org/10.1007/s13389-018-0182-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13389-018-0182-0

Keywords

Search

Navigation