Skip to main content
Top
Published in: Journal of Cryptographic Engineering 3/2015

01-09-2015 | Regular Paper

Multiprecision multiplication on AVR revisited

Authors: Michael Hutter, Peter Schwabe

Published in: Journal of Cryptographic Engineering | Issue 3/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

This paper presents new speed records for multiprecision multiplication on the AVR ATmega family of 8-bit microcontrollers. For example, our software takes only 1,969 cycles for the multiplication of two 160-bit integers; this is more than 15 % faster than that demonstrated in previous work. For 256-bit inputs, our software is not only the first to break through the 6,000-cycle barrier; with only 4,771 cycles it also breaks through the 5,000-cycle barrier and is more than 21 % faster than previous work. We achieve these speed records by carefully optimizing the Karatsuba multiplication technique for AVR ATmega. One might expect that subquadratic-complexity Karatsuba multiplication is only faster than algorithms with quadratic complexity for large inputs. This paper shows that it is in fact faster than fully unrolled product-scanning multiplication already for surprisingly small inputs, starting at 48 bits. Our results thus make Karatsuba multiplication the method of choice for high-performance implementations of elliptic-curve cryptography on AVR ATmega microcontrollers.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

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!

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!

Appendix
Available only for authorised users
Literature
1.
go back to reference Barrett, P.: Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In: Andrew, O.M. (ed.) Advances in Cryptology—CRYPTO ’86. Lecture Notes in Computer Science, vol. 263, pp. 311–323. Springer, Berlin (1987) Barrett, P.: Implementing the Rivest Shamir and Adleman public key encryption algorithm on a standard digital signal processor. In: Andrew, O.M. (ed.) Advances in Cryptology—CRYPTO ’86. Lecture Notes in Computer Science, vol. 263, pp. 311–323. Springer, Berlin (1987)
8.
go back to reference Großschädl, J., Avanzi, R.M., Savaş, E., Tillich, S.: Energy-efficient software implementation of long integer modular arithmetic. In: Rao, J.R., Sunar, B. (eds.) Cryptographic Hardware and Embedded Systems—CHES 2005, vol. 3659 of Lecture Notes in Computer Science, pp. 75–90. Springer, Berlin (2005). www.iacr.org/archive/ches2005/006.pdf Großschädl, J., Avanzi, R.M., Savaş, E., Tillich, S.: Energy-efficient software implementation of long integer modular arithmetic. In: Rao, J.R., Sunar, B. (eds.) Cryptographic Hardware and Embedded Systems—CHES 2005, vol. 3659 of Lecture Notes in Computer Science, pp. 75–90. Springer, Berlin (2005). www.​iacr.​org/​archive/​ches2005/​006.​pdf
9.
11.
go back to reference Hutter, M., Schwabe, P.: NaCl on 8-bit AVR microcontrollers. In: Youssef, A., Nitaj, A. (eds) Progress in Cryptology—AFRICACRYPT 2013, vol. 7918 of Lecture Notes in Computer Science, pp. 156–172. Springer, Berlin (2013). http://cryptojedi.org/papers/#avrnacl Hutter, M., Schwabe, P.: NaCl on 8-bit AVR microcontrollers. In: Youssef, A., Nitaj, A. (eds) Progress in Cryptology—AFRICACRYPT 2013, vol. 7918 of Lecture Notes in Computer Science, pp. 156–172. Springer, Berlin (2013). http://​cryptojedi.​org/​papers/​#avrnacl
16.
go back to reference Lederer, C., Mader, R., Koschuch, M., Großschädl, J., Szekely, A., Tillich, S.: Energy-efficient implementation of ECDH key exchange for wireless sensor networks. In: Markowitch, O., Bilas, A., Hoepman, J.-H., Mitchell, C.J., Quisquater, J.-J. (eds) Information Security Theory and Practice, vol. 5746 of Lecture Notes in Computer Science, pp. 112–127. Springer, Berlin (2009). http://www.cs.bris.ac.uk/Publications/Papers/2001061.pdf Lederer, C., Mader, R., Koschuch, M., Großschädl, J., Szekely, A., Tillich, S.: Energy-efficient implementation of ECDH key exchange for wireless sensor networks. In: Markowitch, O., Bilas, A., Hoepman, J.-H., Mitchell, C.J., Quisquater, J.-J. (eds) Information Security Theory and Practice, vol. 5746 of Lecture Notes in Computer Science, pp. 112–127. Springer, Berlin (2009). http://​www.​cs.​bris.​ac.​uk/​Publications/​Papers/​2001061.​pdf
21.
go back to reference Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing 7(3), 281–292 (1971)CrossRefMATH Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing 7(3), 281–292 (1971)CrossRefMATH
26.
go back to reference Swetz, F.J.: Capitalism and Arithmetic: the new math of the 15th century. Open Court (1987) Swetz, F.J.: Capitalism and Arithmetic: the new math of the 15th century. Open Court (1987)
Metadata
Title
Multiprecision multiplication on AVR revisited
Authors
Michael Hutter
Peter Schwabe
Publication date
01-09-2015
Publisher
Springer Berlin Heidelberg
Published in
Journal of Cryptographic Engineering / Issue 3/2015
Print ISSN: 2190-8508
Electronic ISSN: 2190-8516
DOI
https://doi.org/10.1007/s13389-015-0093-2

Other articles of this Issue 3/2015

Journal of Cryptographic Engineering 3/2015 Go to the issue

Premium Partner