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)
Assignee:
International Classification:
G06F 7/38 (20060101)
Expiration Date:
5/06/12018