Radix-2^w Arithmetic for Scalar Multiplication in Elliptic Curve Cryptography

Elliptic curve scalar multiplication k . P , where k is a nonnegative constant and P is a point on the elliptic curve, requires two distinct operations: addition (ADD) and doubling (DBL). To reduce the number of ADDs without increasing the number of DBLs, a recoding of k with fewer nonzero digits is necessary. Based on Radix- 2^w arithmetic, we introduce a principled w -bit windowing method where the properties of speed, memory, and security are described by exact analytic formulas as proof of superiority. Contrary to existing windowing algorithms, to minimize the number of ADDs the window size ( w ) is guided by an optimum depending on the bit-length ( l ) of the scalar k. The number of required precomputations is minimal regarding the value of w . The proposed method recodes the binary string k and evaluates the multiplication on-the-fly from right-to-left and left-to-right, likewise. Radix- 2^w method is very easy to be used and highly reconfigurable, allowing speed-memory and speed-security trade-offs to satisfy different crypto-system constraints. Furthermore, the method shows a high resilience to side-channel attacks based on power, timing, and statistical analysis. All Radix- 2^w properties are confronted to standard windowing methods’ through an in-depth analysis of the complexities. An overall comparison is made via NIST-recommended GF( 2^l ) finite fields.