Cryptology ePrint Archive: Report 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.

Category / Keywords: Montgomery multiplication, squaring, bit-parallel, trinomials

Date: received 16 Apr 2014, last revised 30 Apr 2014

Contact author: yunfeiyangli at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20140430:082532 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]