The mathematics, computer science and electrical engineering academic communities began paying attention to cryptography sometime in the mid-1970s. The fruits of the work that was performed at MIT and Stanford in the 1970s now forms the backbone of communication security, including online shopping, logging into email servers and corporate VPNs, and many other activities we perform over the Internet or via cellular communication networks. A handful of people in several universities and research centers in the US and Europe created a set of cryptographic algorithms and protocols that demonstrated the meaning and the measure of cryptographic strength. The online security of billions of consumers now depends on the infrastructure developed according to these cryptographic principles.

Popular interest aside, the network and software engineers of the 1980s who were building the next generation of point-to-point communication protocols, email servers and file-transfer protocols were in great need of software implementations of the RSA public-key encryption and decryption algorithms, and the RSA digital signature algorithm. As a counterpart to the theory of cryptography, this area covers efficient hardware and software realizations of cryptographic algorithms. I have seen many different names for our field: applied cryptography, algorithm engineering, cryptographic hardware and embedded systems, and finally cryptographic engineering. Each one tries to capture one aspect of this exciting field, which is an overlapped area of mathematics, electrical engineering and computer science.

As soon as cryptographic algorithms were invented or published, papers and reports on their hardware and software realizations appeared in conference proceedings and engineering journals. Interestingly, one of the first papers was written by Ron Rivest, the co-inventor of the RSA public-key cryptosystem. I believe this paper, published in 1980, is the very first paper on RSA implementation. The fact that it is a hardware implementation makes it even more interesting, since one would expect reports of the software implementations (algorithmic, benchmarking, etc.) to come first because they are easier and less costly to implement.

The following 30 years produced significant amounts of academic research and industrial design work; hardware and software implementations of security suites (SSL, TLS) and devices (cell phones, Bluetooth earphones) and larger systems (SSL and IPSec boxes) were designed, developed and deployed. Phases of this development may be seen as follows:

- Naive algorithms: This phase started with the invention of the Diffie–Hellman and the RSA algorithms (1976–78). Trying to benefit from the developments of computer arithmetic during the previous 25 years, the designers aimed to create hardware and software implementations by simply scaling up the size of numbers they worked with. Since the RSA or the Diffie– Hellman algorithms need 512-bit numbers, 512-bit registers were created to deal with such large numbers. Since they need modular multiplication operations, they first multiply the numbers and then reduce them with multiple subtractions, essentially performing a division by the large modulus. Unfortunately and expectedly, such designs were slow, required large space and were not workable or scalable.

- The Montgomery algorithm: Such naive approaches were ended with the invention of the Montgomery algorithm. Peter Montgomery showed that it is possible to perform modular reductions without resorting to the costly division operation. In fact, the entire reduction can be performed with just two multiplications, instead of a division. In the following 10–15 years, as the Montgomery algorithm was better understood and applied, very efficient software and hardware realizations of public-key cryptography were designed, and software toolkits such as the RSA Labs BSAFE made public-key cryptography accessible to any software designer. These toolkits made it possible to develop and deploy the popular security suites, such as SSL/TLS during the late 1990s. The popular RSA Labs technical reports made the material accessible to hundreds of software and hardware design engineers. In some ways, the contributions of the Montgomery algorithm to cryptographic engineering are similar to the contributions of the Fast Fourier Transform algorithm to digital signal processing. It brought down the complexity of an arithmetic operation which is performed in almost all public-key cryptographic functions, making high-speed implementations possible.

- The last phase which will be with us for some time is the introduction of the side-channel attacks and countermeasures, which approximately followed the introduction and development of the CHES Workshop in the summer of 1999. The timing attacks and power attacks papers made us realize that a cryptographic algorithm implemented in software or hardware is a quite different thing from its description on a piece of paper. While it may be nearly impossible to break the RSA algorithm theoretically and obtain the private exponent, since it requires the factoring of large integers that are beyond our current ability both algorithmically and architecturally, it may be quite easy to obtain the very same private exponent practically, by simply observing the timing or power data from a device performing the RSA signature or decryption operation. Academic work in the field of side-channel attacks flourished in the decade that followed, and it significantly affected the way we design cryptographic software and hardware.

Selected Publications

• Ç. K. Koç. Algorithms for inversion mod p^k. IEEE Transactions on Computers, 69(6): 907-913, June 2020.   pdf
• C. Kızılkale, Ö. Eğecioğlu, and Ç. K. Koç. A matrix decomposition method for optimal normal basis multiplication. IEEE Transactions on Computers, 65(11):3239-3250, November 2016.   pdf
• V. Trujillo-Olaya, T. Sherwood, and Ç. K. Koç. Analysis of performance versus security in hardware realizations of small elliptic curves for lightweight applications. Journal of Cryptographic Engineering, 2(3):179-188, 2012.   pdf
• Ç. K. Koç. Introduction to the Journal of Cryptographic Engineering. Journal of Cryptographic Engineering, 1(1):1-3, April 2011.   pdf
• Ç. K. Koç, editor. Cryptographic Engineering. Springer, 2009.   URL
• O. Acıiçmez, J. P. Seifert, and Ç. K. Koç. Micro-architectural cryptanalysis. IEEE Security & Privacy, 5(4):62-64, July/August 2007.   pdf
• F. Rodríguez-Henríquez, N. A. Saqib, A. D. Perez, and Ç. K. Koç. Cryptographic Algorithms on Reconfigurable Hardware. Springer, 2007.   URL

→   Finite Field Arithmetic