Fast Arithmetic for Public-Key Algorithms in Galois Fields with Composite Exponents

Chris­tof Paar, P. Fleischmann, P. Soria-Rodriguez

IEEE Transactions on Computers, vol. 48, no. 10, pp. 1025-1034, October, 1999.


This contribution describes a new class of arithmetic architectures for Galois fi elds GF(2^k). The main applications of the architecture are public-key systems which are based on the discrete logarithm problem for elliptic curves. The architectures use a representation of the eld GF(2^k) as GF((2^n)^m), where k = n.m. The approach explores bit parallel arithmetic in the sub eld GF(2^n), and serial processing for the extension eld arithmetic. This mixed parallel-serial (hybrid) approach can lead to fast implementations. As the core module, a hybrid multiplier is introduced and several optimizations are discussed. We provide two di erent approaches to squaring. We develop exact expressions for the complexity of parallel squarers in composite fi elds which can have a surprisingly low complexity. The hybrid architectures are capable of exploring the time-space trade-o paradigm in a flexible manner. In particular, the number of clock cycles for one eld multiplication, which is the atomic operation in most public-key schemes, can be reduced by a factor of n compared to other known realizations. The acceleration is achieved at the cost of an increased computational complexity. We describe a proof-of-concept implementation of an ASIC for multiplication and squaring in GF((2^n)^m), m variable.

[gz] [pdf]

tags: ieee