Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2010 | OriginalPaper | Buchkapitel

1. Modular Integer Arithmetic for Public Key Cryptography

verfasst von : Tim Güneysu, Christof Paar

Erschienen in: Secure Integrated Circuits and Systems

Verlag: Springer US

Einloggen

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

search-config
loading …

Abstract

This chapter discusses building blocks for implementing popular public key cryptosystems, like RSA, Diffie-Hellman Key Exchange (DHKE) and Elliptic Curve Cryptography (ECC). Therefore, we briefly introduce field-based arithmetic on which most of recently established public key cryptosystems rely. As most popular fields, we give examples for architecture implementing efficient arithmetic operations over prime and binary extension fields for use in cryptographic applications.

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
Nächstes Kapitel Introduction to Side-Channel Attacks
Fußnoten
1
According to [14], the discovery of public-key cryptography (PKC) in the intelligence community is attributed to John H. Ellis in 1970. The discovery of the equivalent of the RSA cryptosystem [38] is attributed to Clifford Cocks in 1973 while the equivalent of the Diffie–Hellman key exchange was discovered by Malcolm J. Williamson, in 1974. However, it is believed that these British scientists did not realize the practical implications of their discoveries at the time of their publication (see, for example, [39, 11]).
 
2
It is important to understand that NP-complete problems from computer science cannot be simply converted for use with PKC since a one-way function for PKC must guarantee hardness in all cases which is usually not the case for all NP-complete problems.
 
3
Recall that the time complexity of n-bit addition or subtraction is only in \(\mathcal{O}(n)\).
 
4
Exponentiation algorithms significantly influence the performance of cryptosystems like RSA, DHKE, and ElGamal. Please find further details how to speed up exponentiation methods in [31, 16, 44].
 
Literatur
1.
2.
D. N. Amanor, C. Paar, J. Pelzl, V. Bunimov, and M. Schimmler. Efficient Hardware Architectures for Modular Multiplication on FPGAs. In 2005 International Conference on Field Programmable Logic and Applications (FPL), Tampere, Finland, pages 539–542. IEEE Circuits and Systems Society, August 2005.
3.
D. V. Bailey and C. Paar. Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms. In H. Krawczyk, editor, Advances in Cryptology — CRYPTO ’98, volume LNCS 1462, pages 472–485, Springer-Verlag, Berlin, 1998.
4.
D. V. Bailey and C. Paar. Efficient Arithmetic in Finite Field Extensions with Application in Elliptic Curve Cryptography. Journal of Cryptology, 14(3):153–176, 2001.MathSciNetMATH
5.
P. Barrett. Implementing the Rivest, Shamir and Adleman public-key encryption algorithm on standard digital signal processor. In A. Odlyzko, editor, Advances in Cryptology — CRYPTO’86, volume 263 of LNCS, pages 311–323. Springer-Verlag, Berlin 1987.
6.
L. Batina, S. B. Ors, B. Preneel, and J. Vandewalle. Hardware architectures for public key cryptography. Integration, the VLSI Journal, 34(6):1–64, 2003.CrossRef
7.
G. Blakley. A computer algorithm for calculating the product \(A \cdot B\) modulo M. IEEE Transactions on Computers, C-32(5):497–500, May 1983.CrossRef
8.
D. Boneh and M. Franklin. Identity-Based Encryption from the Weil Pairing. In J. Kilian, editor, Advances in Cryptology — CRYPTO 2001, volume LNCS 2139, pages 213–229. Springer-Verlag, Berlin 2001.
9.
V. Bunimov and M. Schimmler. Area and Time Efficient Modular Multiplication of Large Integers. In IEEE 14th International Conference on Application-specific Systems, Architectures and Processors, June 2003.
10.
A. Daly, L. Marnaney, and E. Popovici. Fast Modular Inversion in the Montgomery Domain on Reconfigurable Logic. Technical report, University College Cork, Cork, Ireland, 2004.
11.
12.
W. Diffie and M. E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6):644–654, November 1976.CrossRefMathSciNet
13.
T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31:469–472, 1985.CrossRefMathSciNetMATH
14.
15.
I. E. T. Force. The Kerberos Network Authentication Service (V5). RFC 4120, July 2005.
16.
17.
J. Guajardo, T. Güneysu, S. S. Kumar, C. Paar, and J. Pelzl. Efficient hardware implementation of finite fields with applications to cryptography. Acta Applicandae Mathematicae, 93:75–118, 2006.CrossRefMathSciNetMATH
18.
J. Guajardo and C. Paar. Efficient Algorithms for Elliptic Curve Cryptosystems. In B. Kaliski, Jr., editor, Advances in Cryptology — CRYPTO ’97, volume 1294, pages 342–356, Springer Verlag, Berlin August 1997.
19.
J. Hoffstein, D. Lieman, J. Pipher, and J. H. Silverman. NTRU: A Public Key Cryptosystem. Technical report, Aug. 11 1999.
20.
K. Hwang. Computer Arithmetic: Principles, Architecture and Design. John Wiley & Sons, Inc. New York, 1979.
21.
T. Itoh and S. Tsujii. A fast algorithm for computing multiplicative inverses in \(GF(2^m)\) using normal bases. Information and Computation, 78:171–177, 1988.CrossRefMathSciNetMATH
22.
D. Knuth. The Art of Computer Programming, Seminumerical Algorithms, volume 2. Addison-Wesley, Reading, MA November 1971. 2nd printing.
23.
D. E. Knuth. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, volume 2. Second edition, Addison-Wesley, Reading, MA 1973.
24.
25.
26.
N. Koblitz. A Course in Number Theory and Cryptography. Springer Verlag, New York, 1994.
27.
N. Koblitz. An Elliptic Curve Implementation of the Finite Field Digital Signature Algorithm. In H. Krawczyk, editor, Advances in Cryptology — CRYPTO 98, volume LNCS 1462, pages 327–337. Springer-Verlag, Berlin 1998.CrossRef
28.
Ç. K. Koç, T. Acar, and B. S. Kaliski. Analyzing and comparing Montgomery multiplication algorithms. IEEE Micro, 16(3):26–33, June 1996.CrossRef
29.
A. Lenstra and E. Verheul. Selecting Cryptographic Key Sizes. In H. Imai and Y. Zheng, editors, Practice and Theory in Public Key Cryptography–-PKC 2000, volume 1751, pages 446–465, January 2000.
30.
R. J. McEliece. A public-key cryptosystem based on algebraic coding theory. DSN Progress Report, pages 42–44, 1987.
31.
A. J. Menezes, P. C. van Oorschot, and S. A. Vanstone. Handbook of Applied Cryptography. The CRC Press series on discrete mathematics and its applications. 1997.
32.
R. C. Merkle. Secure communications over insecure channels. Communications of the ACM, 21(4):294–299, 1978.CrossRef
33.
P. Mihăilescu. Optimal Galois Field Bases Which Are Not Normal. Recent Results Session — FSE ’97, 1997.
34.
V. S. Miller. Use of Elliptic Curves in Cryptography. In H. C. Williams, editor, Advances in Cryptology — CRYPTO ’85, volume 218, pages 417–426, August 1986.
35.
36.
National Institute of Standards and Technology (NIST). Recommended Elliptic Curves for Federal Government Use, July 1999. csrc.nist.gov/csrc/fedstandards.html.
37.
J. Pollard. Monte Carlo methods for index computation mod p. Mathematics of Computation, 32(143):918–924, July 1978.MathSciNetMATH
38.
R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2):120–126, February 1978.CrossRefMathSciNetMATH
39.
40.
K. Sloan. Comments on a computer algorithm for calculating the product \(A \cdot B\) modulo M. IEEE Transactions on Computers, C-34(3):290–292, March 1985.CrossRefMathSciNet
41.
N. Smart. Elliptic curve cryptosystems over small fields of odd characteristic. Journal of Cryptology, 12(2):141–151, Spring 1999.CrossRefMathSciNetMATH
42.
J. Solinas. Generalized Mersenne Numbers. Technical Report, CORR 99-39, Department of Combinatorics and Optimization, University of Waterloo, Canada,, 1999.
43.
L. Song and K. K. Parhi. Low energy digit-serial/parallel finite field multipliers. Journal of VLSI Signal Processing, 19(2):149–166, June 1998.CrossRef
44.
J. von zur Gathen and M. Nöcker. Exponentiation in Finite Fields: Theory and Practice. In T. Mora and H. Mattson, editors, Applied Algebra, Algebraic Algorithms and Error Correcting Codes — AAECC-12, volume LNCS 1255, pages 88–113. Springer-Verlag, 2000.
45.
C. Walter. Logarithmic speed modular multiplication. Electronics Letters, 30(17):1397–1398, 1994.CrossRef
Metadaten
Titel
Modular Integer Arithmetic for Public Key Cryptography
verfasst von
Tim Güneysu
Christof Paar
Copyright-Jahr
2010
Verlag
Springer US
Buch
Secure Integrated Circuits and Systems

Print ISBN: 978-0-387-71827-9

Electronic ISBN: 978-0-387-71829-3

Copyright-Jahr: 2010

DOI
https://doi.org/10.1007/978-0-387-71829-3_1