A High-Speed Elliptic Curve Cryptographic Processor for Generic Curves over GF(p)

Abstract

Elliptic curve cryptography (ECC) is preferred for high- speed applications due to the lower computational complexity compared with other public-key cryptographic schemes. As the basic arithmetic, the modular multiplication is the most time-consuming operation in public- key cryptosystems. The existing high-radix Montgomery multipliers per- formed a single Montgomery multiplication either in approximately 2n clock cycles, or approximately n cycles but with a very low frequency, where n is the number of words. In this paper, we first design a novel Montgomery multiplier by combining a quotient pipelining Montgomery multiplication algorithm with a parallel array design. The parallel design with one-way carry propagation can determine the quotients in one clock cycle, thus one Montgomery multiplication can be completed in approx- imately n clock cycles. Meanwhile, by the quotient pipelining technique applied in digital signal processing (DSP) blocks, our multiplier works in a high frequency. We also implement an ECC processor for generic curves over GF(p) using the novel multiplier on FPGAs. To the best of our knowledge, our processor is the fastest among the existing ECC implementations over GF(p).