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

01.09.2015 | Regular Paper

Multiprecision multiplication on AVR revisited

verfasst von: Michael Hutter, Peter Schwabe

Erschienen in: Journal of Cryptographic Engineering | Ausgabe 3/2015

Einloggen

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

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.

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!

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!

Anhänge
Nur mit Berechtigung zugänglich
Literatur
1.
Zurück zum Zitat 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)
2.
8.
Zurück zum Zitat 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.
Zurück zum Zitat Gura, N., Patel, A., Wander, A., Eberle, H., Shantz, S.C.: Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In: Joye, M. (ed.) Cryptographic Hardware and Embedded Systems—CHES 2004, vol. 3156 of Lecture Notes in Computer Science, pp. 119–132. Springer, Berlin (2004). www.iacr.org/archive/ches2004/31560117/31560117.pdf Gura, N., Patel, A., Wander, A., Eberle, H., Shantz, S.C.: Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In: Joye, M. (ed.) Cryptographic Hardware and Embedded Systems—CHES 2004, vol. 3156 of Lecture Notes in Computer Science, pp. 119–132. Springer, Berlin (2004). www.​iacr.​org/​archive/​ches2004/​31560117/​31560117.​pdf
11.
Zurück zum Zitat 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
12.
16.
Zurück zum Zitat 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.
Zurück zum Zitat 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.
Zurück zum Zitat 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)
Metadaten
Titel
Multiprecision multiplication on AVR revisited
verfasst von
Michael Hutter
Peter Schwabe
Publikationsdatum
01.09.2015
Verlag
Springer Berlin Heidelberg
Erschienen in
Journal of Cryptographic Engineering / Ausgabe 3/2015
Print ISSN: 2190-8508
Elektronische ISSN: 2190-8516
DOI
https://doi.org/10.1007/s13389-015-0093-2

Weitere Artikel der Ausgabe 3/2015

Journal of Cryptographic Engineering 3/2015 Zur Ausgabe