Cryptology ePrint Archive: Report 2015/785

Double-Speed Barrett Moduli

Rémi Géraud and Diana Maimut and David Naccache

Abstract: Modular multiplication and modular reduction are the atomic constituents of most public-key cryptosystems. Amongst the numerous algorithms for performing these operations, a particularly elegant method was proposed by Barrett. This method builds the operation $a \bmod b$ from bit shifts, multiplications and additions in $\mathbb{Z}$. This allows building modular reduction at very marginal code or silicon costs by leveraging existing hardware or software multipliers. This paper presents a method allowing doubling the speed of Barrett’s algorithm by using specific composite moduli. This is particularly useful for lightweight devices where such an optimization can make a difference in terms of power consumption, cost and processing time. The generation of composite moduli with a predetermined portion is a well-known technique and the use of such moduli is considered, in statu scientae, as safe as using randomly generated composite moduli.

Category / Keywords: public-key cryptography / modular multiplication

Date: received 6 Aug 2015

Contact author: david naccache at ens fr

Available format(s): PDF | BibTeX Citation

Version: 20150807:141415 (All versions of this report)

Short URL: ia.cr/2015/785

Discussion forum: Show discussion | Start new discussion