The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Studies on High-Speed Hardware Implementation of Cryptographic Algorithms

Kimmo Järvinen

Dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Faculty of Electronics, Communications and Automation for public examination and debate in Auditorium S1 at Helsinki University of Technology (Espoo, Finland) on the 21st of November, 2008, at 12 noon.

Overview in PDF format (ISBN 978-951-22-9590-6)   [944 KB]
Dissertation is also available in print (ISBN 978-951-22-9589-0)

Abstract

Cryptographic algorithms are ubiquitous in modern communication systems where they have a central role in ensuring information security. This thesis studies efficient implementation of certain widely-used cryptographic algorithms. Cryptographic algorithms are computationally demanding and software-based implementations are often too slow or power consuming which yields a need for hardware implementation. Field Programmable Gate Arrays (FPGAs) are programmable logic devices which have proven to be highly feasible implementation platforms for cryptographic algorithms because they provide both speed and programmability. Hence, the use of FPGAs for cryptography has been intensively studied in the research community and FPGAs are also the primary implementation platforms in this thesis.

This thesis presents techniques allowing faster implementations than existing ones. Such techniques are necessary in order to use high-security cryptographic algorithms in applications requiring high data rates, for example, in heavily loaded network servers. The focus is on Advanced Encryption Standard (AES), the most commonly used secret-key cryptographic algorithm, and Elliptic Curve Cryptography (ECC), public-key cryptographic algorithms which have gained popularity in the recent years and are replacing traditional public-key cryptosystems, such as RSA. Because these algorithms are well-defined and widely-used, the results of this thesis can be directly applied in practice.

The contributions of this thesis include improvements to both algorithms and techniques for implementing them. Algorithms are modified in order to make them more suitable for hardware implementation, especially, focusing on increasing parallelism. Several FPGA implementations exploiting these modifications are presented in the thesis including some of the fastest implementations available in the literature. The most important contributions of this thesis relate to ECC and, specifically, to a family of elliptic curves providing faster computations called Koblitz curves. The results of this thesis can, in their part, enable increasing use of cryptographic algorithms in various practical applications where high computation speed is an issue.

This thesis consists of an overview and of the following 11 publications:

  1. Kimmo Järvinen, Matti Tommiska and Jorma Skyttä, Comparative Survey of High-Performance Cryptographic Algorithm Implementations on FPGAs, IEE Proceedings - Information Security, vol. 152, no. 1, Oct. 2005, pp. 3-12. © 2005 The Institution of Engineering and Technology (IET). By permission.
  2. Kimmo U. Järvinen, Matti T. Tommiska and Jorma O. Skyttä, A Fully Pipelined Memoryless 17.8 Gbps AES-128 Encryptor, in Proceedings of the 11th ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, FPGA 2003, Monterey, California, USA, Feb. 23-25, 2003, pp. 207-215.
  3. Kimmo Järvinen, Matti Tommiska and Jorma Skyttä, A Scalable Architecture for Elliptic Curve Point Multiplication, in Proceedings of the 2004 IEEE International Conference on Field-Programmable Technology, FPT 2004, Brisbane, Queensland, Australia, Dec. 6-8, 2004, pp. 303-306. © 2004 IEEE. By permission.
  4. Kimmo Järvinen and Jorma Skyttä, On Parallelization of High-Speed Processors for Elliptic Curve Cryptography, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 16, no. 9, Sep. 2008, pp. 1162-1175. © 2008 IEEE. By permission.
  5. Kimmo Järvinen, Juha Forsten and Jorma Skyttä, FPGA Design of Self-certified Signature Verification on Koblitz Curves, in Proceedings of the Workshop on Cryptographic Hardware and Embedded Systems, CHES 2007, Vienna, Austria, Sep. 10-13, 2007, Lecture Notes in Computer Science, vol. 4727, Springer, pp. 256-271. © 2007 Springer Science+Business Media. By permission.
  6. Kimmo Järvinen and Jorma Skyttä, Fast Point Multiplication on Koblitz Curves: Parallelization Method and Implementations, Microprocessors and Microsystems, in press, 11 pages. © 2008 Elsevier Science. By permission.
  7. Kimmo U. Järvinen and Jorma O. Skyttä, High-Speed Elliptic Curve Cryptography Accelerator for Koblitz Curves, in Proceedings of the 16th IEEE Symposium on Field-Programmable Custom Computing Machines, FCCM 2008, Stanford, California, USA, Apr. 14-15, 2008, in press, 10 pages. © 2008 IEEE. By permission.
  8. Kimmo Järvinen, Juha Forsten and Jorma Skyttä, Efficient Circuitry for Computing τ-adic Non-Adjacent Form, in Proceedings of the 13th IEEE International Conference on Electronics, Circuits and Systems, ICECS 2006, Nice, France, Dec. 10-13, 2006, pp. 232-235. © 2006 IEEE. By permission.
  9. Billy Bob Brumley and Kimmo Järvinen, Koblitz Curves and Integer Equivalents of Frobenius Expansions, in Revised Selected Papers of the 14th Annual Workshop on Selected Areas in Cryptography, SAC 2007, Ottawa, Ontario, Canada, Aug. 16-17, 2007, Lecture Notes in Computer Science, vol. 4876, Springer, pp. 126-137. © 2007 Springer Science+Business Media. By permission.
  10. V.S. Dimitrov, K.U. Järvinen, M.J. Jacobson, Jr., W.F. Chan, and Z. Huang, FPGA Implementation of Point Multiplication on Koblitz Curves Using Kleinian Integers, in Proceedings of the Workshop on Cryptographic Hardware and Embedded Systems, CHES 2006, Yokohama, Japan, Oct. 10-13, 2006, Lecture Notes in Computer Science, vol. 4249, Springer, pp. 445-459. © 2006 International Association for Cryptologic Research (IACR). By permission.
  11. Vassil S. Dimitrov, Kimmo U. Järvinen, Michael J. Jacobson, Jr., Wai Fong (Andy) Chan and Zhun Huang, Provably Sublinear Point Multiplication on Koblitz Curves and Its Hardware Implementation, IEEE Transactions on Computers, vol. 57, no. 11, Nov. 2008, pp. 1469-1481. © 2008 IEEE. By permission.

Errata of publications 2, 6 and 9

Keywords: cryptography, cryptographic algorithms, elliptic curve cryptography, AES, FPGA

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2008 Helsinki University of Technology

Last update 2011-05-26