Low-Latency Digit-Serial and Digit-Parallel Systolic Multipliers for Large Binary Extension Fields

For cryptographic algorithms, such as elliptic curve digital signature algorithm (ECDSA) and pairing algorithm, the crypto-processors are required to perform large number of additions and multiplications over finite fields of large orders. To have a balanced trade-off between space complexity and time complexity, in this paper, novel digit-serial and digit-parallel systolic structures are presented for computing multiplication over GF(2^m). Based on novel decomposition algorithm, we have derived an efficient digit-serial systolic architecture, which involves latency of O(√{m/d}) clock cycles, while the existing digit-serial systolic multipliers involve at least O(m/d) latency for digit-size d. The proposed digit-serial design could be used for AESP-based fields with the same digit-size as the case of trinomial-based fields with a small increase in area. We have also proposed digit-parallel systolic architecture employing n-term Karatsuba-like method, where the latency can be reduced from O(√{m/d}) to O(√{m/nd}). This feature would be a major advantage for implementing multiplication for the fields of large orders. From synthesis results, it is shown that the proposed architectures have significantly lower time complexity, lower area-delay product, and higher bit-throughput than the existing digit-serial multipliers.