Paper 2014/268

A low complexity bit-parallel Montgomery multiplier based on squaring for trinomials

Yin Li and Yiyang Chen

Abstract

In this paper, we present a new bit-parallel Montgomery multiplier for $GF(2^m)$ generated with an irreducible trinomial. A newly proposed divide-and-conquer approach is applied to simplify the polynomial multiplication while the Montgomery squaring is induced to optimize the modular reduction. Meanwhile, this design effectively exploits the overlapped elements in squaring and reduction operations to reduce the space complexity. As a result, the proposed multiplier has about 25\% reduced space complexity compared with previous multipliers, with a slight increase of time complexity. Among the five binary fields recommended by NIST for the ECDSA (Elliptic Curve Digital Signature Algorithm), there exist two fields, i.e., $GF(2^{409})$, $GF(2^{233})$, defined by trinomials. For these two fields, we show that our proposal outperforms the previous best known results if the space and time complexities are both considered.