nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

\(\mu \)Kummer: Efficient Hyperelliptic Signatures and Key Exchange on Microcontrollers

verfasst von : Joost Renes, Peter Schwabe, Benjamin Smith, Lejla Batina

Erschienen in: Cryptographic Hardware and Embedded Systems – CHES 2016

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We describe the design and implementation of efficient signature and key-exchange schemes for the AVR ATmega and ARM Cortex M0 microcontrollers, targeting the 128-bit security level. Our algorithms are based on an efficient Montgomery ladder scalar multiplication on the Kummer surface of Gaudry and Schost’s genus-2 hyperelliptic curve, combined with the Jacobian point recovery technique of Chung, Costello, and Smith. Our results are the first to show the feasibility of software-only hyperelliptic cryptography on constrained platforms, and represent a significant improvement on the elliptic-curve state-of-the-art for both key exchange and signatures on these architectures. Notably, our key-exchange scalar-multiplication software runs in under 9520k cycles on the ATmega and under 2640k cycles on the Cortex M0, improving on the current speed records by 32 % and 75 % respectively.

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 QcBits: Constant-Time Small-Key Code-Based Cryptography

Nächstes Kapitel Flush, Gauss, and Reload – A Cache Attack on the BLISS Lattice-Based Signature Scheme

We only call ADD once in our algorithms, so for lack of space we omit its description.

Note that \((A:B:C:D) = \mathcal {H}((a:b:c:d))\) and \((a:b:c:d) = \mathcal {H}((A:B:C:D))\).

We used the reference C implementation for the Cortex M0, and the assembly implementation for AVR; both are available from [28]. The only change required is to the padding, which must take domain separation into account according to [12, p. 28].

Bernstein, D.J.: Elliptic vs. hyperelliptic, part 1 (2006). http://cr.yp.to/talks/2006.09.20/slides.pdf

Bos, J.W., Costello, C., Hisil, H., Lauter, K.: Fast cryptography in genus 2. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 194–210. Springer, Heidelberg (2013). https://eprint.iacr.org/2012/670.pdf CrossRef

Bernstein, D.J., Chuengsatiansup, C., Lange, T., Schwabe, P.: Kummer strikes back: new DH speed records. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 317–337. Springer, Heidelberg (2014). https://cryptojedi.org/papers/#kummer

Costello, C., Longa, P.: Four\(\mathbb{Q}\): four-dimensional decompositions on a\(\mathbb{Q}\)-curve over the mersenne prime. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 214–235. Springer, Heidelberg (2015). https://eprint.iacr.org/2015/565 CrossRef

Batina, L., Hwang, D., Hodjat, A., Preneel, B., Verbauwhede, I.: Hardware/Software Co-design for Hyperelliptic Curve Cryptography (HECC) on the 8051 \(\mu P\). In: Rao, J.R., Sunar, B. (eds.) CHES 2005. LNCS, vol. 3659, pp. 106–118. Springer, Heidelberg (2005). https://www.iacr.org/archive/ches2005/008.pdf CrossRef

Hodjat, A., Batina, L., Hwang, D., Verbauwhede, I.: HW/SW co-design of a hyperelliptic curve cryptosystem using amicrocode instruction set coprocessor. Integr. VLSI J. 40, 45–51 (2007). https://www.cosic.esat.kuleuven.be/publications/article-622.pdf CrossRef

Düll, M., Haase, B., Hinterwälder, G., Hutter, M., Paar, C., Sánchez, A.H., Schwabe, P.: High-speed curve25519 on 8-bit, 16-bit and 32-bit microcontrollers. Des. Codes Crypt. 77, 493–514 (2015). http://cryptojedi.org/papers/#mu25519 MathSciNetCrossRefMATH

Costello, C., Chung, P.N., Smith, B.: Fast, uniform, and compact scalar multiplication for elliptic curves and genus 2 Jacobians with applications to signature schemes.Cryptology ePrint Archive, Report 2015/983 (2015). https://eprint.iacr.org/2015/983

Bernstein, D.J., Duif, N., Lange, T., Schwabe, P., Yang, B.Y.: High-speed high-security signatures. J. Cryptogr. Eng. 2, 77–89 (2012). https://cryptojedi.org/papers/ed25519 CrossRefMATH

10.

Nascimento, E., López, J., Dahab, R.: Efficient and secure elliptic curve cryptography for 8-bit AVR microcontrollers. In: Chakraborty, R.S., Schwabe, P., Solworth, J. (eds.) SPACE 2015. LNCS, vol. 9354, pp. 289–309. Springer, Heidelberg (2015)CrossRef

11.

Schnorr, C.-P.: Efficient identification and signatures for smart cards. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 239–252. Springer, Heidelberg (1990)

12.

Dworkin, M.J.:SHA-3 standard: Permutation-based hash and extendable-outputfunctions.Technical report, National Institute of Standards and Technology(NIST) (2015). http://www.nist.gov/manuscript-publication-search.cfm?pub_id=919061

13.

Katz, J., Wang, N.: Efficiency improvements for signature schemes with tight securityreductions.In: Proceedings of the 10th ACM Conference on Computer and Communications Security, CCS 2003, pp. 155–164. ACM (2003). https://www.cs.umd.edu/~jkatz/papers/CCCS03_sigs.pdf

14.

Vitek, J., Naccache, D., Pointcheval, D., Vaudenay, S.: Computational alternatives to random number generators. In: Tavares, S., Meijer, H. (eds.) SAC 1998. LNCS, vol. 1556, pp. 72–80. Springer, Heidelberg (1999). https://www.di.ens.fr/ pointche/Documents/Papers/1998_sac.pdf CrossRef

15.

Bernstein, D.J.: Differential addition chains (2006). http://cr.yp.to/ecdh/diffchain-20060219.pdf

16.

Stam, M.: Speeding up subgroup cryptosystems. Ph.D. thesis, Technische Universiteit Eindhoven (2003). http://alexandria.tue.nl/extra2/200311829.pdf?q=subgroup

17.

Hutter, M., Schwabe, P.: Multiprecision multiplication on AVR revisited. J. Cryptogr. Eng. 5, 201–214 (2015). http://cryptojedi.org/papers/#avrmul

18.

Gaudry, P., Schost, E.: Genus 2 point counting over prime fields. J Symb Comput 47, 368–400 (2012). https://cs.uwaterloo.ca/~eschost/publications/countg2.pdf

19.

Hisil, H., Costello, C.: Jacobian coordinates on genus 2 curves. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 338–357. Springer, Heidelberg (2014). https://eprint.iacr.org/2014/385.pdf

20.

Stahlke, C.: Point compression on jacobians of hyperelliptic curves over\(\mathbb{F}_q\).Cryptology ePrint Archive, Report 2004/030 (2004). https://eprint.iacr.org/2004/030

21.

Chudnovsky, D.V., Chudnovsky, G.V.: Sequences of numbers generated by addition in formal groups and new primality and factorization tests. Adv. Appl. Math. 7, 385–434 (1986)MathSciNetCrossRefMATH

22.

Cosset, R.: Applications of theta functions for hyperelliptic curvecryptography.Ph.D. thesis, Université Henri Poincaré - Nancy I (2011). https://tel.archives-ouvertes.fr/tel-00642951/file/main.pdf

23.

Gaudry, P.: Fast genus 2 arithmetic based on theta functions. J. Math. Cryptol. 1, 243–265 (2007). https://eprint.iacr.org/2005/314/ MathSciNetCrossRefMATH

24.

López, J., Dahab, R.: Fast multiplication on elliptic curves over \(GF\)(2\(_{\rm m}\)) without precomputation. In: Koç, Ç.K., Paar, C. (eds.) CHES 1999. LNCS, vol. 1717, pp. 316–327. Springer, Heidelberg (1999)CrossRef

25.

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

26.

Brier, E., Joye, M.: Weierstra elliptic curves and side-channel attacks. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 335–345. Springer, Heidelberg (2002). http://link.springer.com/content/pdf/10.1007%2F3-540-45664-3_24.pdf

27.

Cassels, J.W.S., Flynn, E.V.: Prolegomena to a Middlebrow Arithmetic of Curves of Genus 2, vol. 230. Cambridge University Press, Cambridge (1996)CrossRefMATH

28.

Bertoni, G., Daemen, J., Peeters, M., Assche, G.V.: The keccak sponge function family (2016). http://keccak.noekeon.org/

29.

Liu, Z., Wenger, E., Großschädl, J.: MoTE-ECC: energy-scalable elliptic curve cryptography for wireless sensor networks. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.) ACNS 2014. LNCS, vol. 8479, pp. 361–379. Springer, Heidelberg (2014). https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=77985

30.

Hutter, M., Schwabe, P.: NaCl on 8-bit AVR microcontrollers. In: Youssef, A., Nitaj, A., Hassanien, A.E. (eds.) AFRICACRYPT 2013. LNCS, vol. 7918, pp. 156–172. Springer, Heidelberg (2013). http://cryptojedi.org/papers/#avrnacl

31.

Wenger, E., Unterluggauer, T., Werner, M.: 8/16/32 shades of elliptic curve cryptography on embedded processors. In: Paul, G., Vaudenay, S. (eds.) INDOCRYPT 2013. LNCS, vol. 8250, pp. 244–261. Springer, Heidelberg (2013). https://online.tugraz.at/tug_online/voe_main2.getvolltext?pCurrPk=72486 CrossRef

Titel: Kummer: Efficient Hyperelliptic Signatures and Key Exchange on Microcontrollers
verfasst von: Joost Renes
Peter Schwabe
Benjamin Smith
Lejla Batina
Verlag: Springer Berlin Heidelberg
Buch: Cryptographic Hardware and Embedded Systems – CHES 2016
Print ISBN: 978-3-662-53139-6

Electronic ISBN: 978-3-662-53140-2

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-53140-2_15

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"