Patent Number: 8,719,324

Title: Spectral modular arithmetic method and apparatus

Abstract: A new hardware architecture is disclosed that performs the modular exponentiation operation, i.e., the computation of c=m.sup.e mod n where c, m, e, n are large integers. The modular exponentiation operation is the most common operation in public-key cryptography. The new method, named the Spectral Modular Exponentiation method, uses the Discrete Fourier Transform over a finite ring, and relies on new techniques to perform the modular multiplication and reduction operations. The method yields an efficient and highly parallel architecture for hardware implementations of public-key cryptosystems which use the modular exponentiation operation as the basic step, such as the RSA and Diffie-Hellman algorithms. The method is extended to perform the multiplication operation in extension fields which is necessary to perform exponentiation or various other operations over these extension fields.

Inventors: Koc; Cetin K. (Corvallis, OR), Saldamli; Gokay (Richmond, CA)


International Classification: G06F 7/38 (20060101)

Expiration Date: 5/06/12018