Spectral Modular Arithmetic

Cetin Koc
Oregon State University

We describe a new hardware architecture to perform the modular
exponentiation operation, i.e., the computation of $c=m^e \bmod{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 as the spectral modular exponentiation,
uses the discrete Fourier transform over a finite
ring, and relies on new techniques to perform
multiplication and reduction operations. The method yields
an efficient and highly parallel architecture for hardware
realizations of public-key cryptosystems which use the
modular exponentiation as the core computation, such
as the RSA and Diffie-Hellman algorithms.

Presentation (PDF File)

Back to Workshop IV: Special purpose hardware for cryptography: Attacks and Applications