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(sqrt{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(sqrt{m/d})$ to $O(sqrt{md})$ . 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.