Abstract:

The basic computation in Elliptic Curve Cryptography (ECC) is Elliptic Curve Point Multiplication (ECPM), which consists of a series of modular multiplications.Through Montgomery modular multiplications in Residue Number System (RNS),the modular multiplications inFpcan be transformed into modular arithmetic over RNS moduli.A new RNS approach is proposed to accelerate ECPM.Firstly,instead of almost two symmetric RNSs,two asymmetric RNSs are chosen,with 2 moduli  {2L, 2 L-1} for RNS Γ and 8 moduli with the form of　2L－2Ki+1 for RNS Ω,which makes the modular reductions quite easy.Secondly,in the asymmetric RNSs,most modular multiplications can be performed by direct multiplications in RNS rather than modular multiplications in Fp.Especially,Montgomery ladder with only x coordinates is used for ECPM. At the end of every parallel point doubling and point addition,4 RNS Montgomery modular multiplications are performed to narrow the output range.As a result, the total time for an Nbit Fp ECPM is around 55.5N·I,with I being the time delay of a (L/2)bit multiplication,a carry save addition,and a (L/2)bit full addition.

Key words: RNS;elliptic curve point multiplication;Montgomery ladder