Unbalanced Exponent Modular Reduction over Binary Field and Its Implementation

Modular reduction is the basic operation of cryptographic systems. The Barrett´s algorithm and Montgomery´s algorithm are widely used nowadays and they are both based on pre-computation. In the field of elliptic curve cryptosystem (ECC) over GF(2^m), the reduction polynomials recommended by SEC have few items and the degree of second item is much less than that of the first one. Making use of this characteristic, the paper presents a new method to accelerate modular reduction without pre-computation which speeds up modular reduction by 10-30 times over GF(2^m) and speeds up ECC point multiplication by 40%-50%. This algorithm has been implemented in a high-speed public-key cipher accelerator