International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 07 August 2015

R\\\'emi G\\\'eraud, Diana Maimut, David Naccache
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.