Randomized modular polynomial reduction method and hardware therefor

Abstract

A cryptographically secure, computer hardware-implemented binary finite-field polynomial modular reduction method estimates and randomizes a polynomial quotient used for computation of a polynomial remainder. The randomizing error injected into the approximate polynomial quotient is limited to a few bits, e.g. less than half a word. The computed polynomial remainder is congruent with but a small random multiple of the residue, which can be found by a final strict binary field reduction by the modulus. In addition to a computational unit and operations sequencer, the computing hardware also includes a random or pseudo-random number generator for producing the random polynomial error. The modular reduction method thus resists hardware cryptoanalysis attacks, such as timing and power analysis attacks.

1 . A cryptographically secure, computer hardware-implemented modular polynomial reduction method in the binary finite field GF(2 n ), comprising:
 precomputing and storing in memory a polynomial constant u(x) representing a bit-scaled reciprocal of a polynomial modulus m(x);   estimating an approximate polynomial quotient q for a polynomial p(x) to be reduced modulo m(x), wherein said estimating is executed upon p(x) in a computation unit by a polynomial multiplication over GF(2 n ) by said constant u(x) and by bits shifts;   generating in a random number generator a random polynomial error value E(x) and applying said polynomial error value to said approximate polynomial quotient to obtain a randomized polynomial quotient q′(x)=q(x)+E(x); and   calculating a polynomial remainder r′(x)=p(x)+q′(x)·m(x) in said computation unit, said remainder r′(x) being of high degree than said modulus m(x) but congruent to p(x) modulo m(x) and where the degree of p(x) is less than or equal to 2k+1.