A Methodology for High-Speed Software Implementations of Number-Theoretic CryptosystemsC. K. Koc and T. AcarTechnical Report, Electrical and Computer Engineering, Oregon State University, 12 pages, May 1997.AbstractBecause of their flexibility and cost effectiveness, software implementations of number-theoretic cryptographic algorithms (e.g., RSA and Diffie-Hellman) are often desired. In order to obtain the required level of performance (speed) on a selected platform, the developers turn to algorithm-level optimizations and assembly language programming. In this paper, we examine these implementation issues and propose a design methodology for obtaining high-speed implementations. We show that between the full assembler implementation and the standard C implementation, there is a design option in which only a small number of code segments (kernel operations) are written in assembler in order to obtain a significant portion of the speed increase gained by the full assembler implementation. We propose a small set of kernel operations which are as simple as a*b+c , where the numbers a, b, c are 1-word integers. The results of our experiments on several processors are also summarized. |