Paper 2001/103

Countermeasures against Side-Channel Attacks for Elliptic Curve Cryptosystems

Antonio Bellezza

Abstract

Some attacks on cryptographic systems exploit the leakage of information through so-called ``side channels'', such as power consumption or time employed by a computation. For cryptosystems involving an exponentiation, a few possible countermeasures are suggested. In the case of elliptic curves over a binary finite field, we show how to split point addition into two blocks which, through the addition of a little overhead, can be made undistinguishable from a point doubling. This allows the whole exponentiation process to be performed as a sequence of homogeneous steps. To add some randomization to the exponentiation process in the ECC case, we suggest the use of points of small order, computed on the fly. This presents some disadvantages over known methods, but allows to avoid the storage of points in non-volatile RAM. A multiplicative variation of ``additive exponent blinding'' is suggested. This involves a two-phase exponentiation and is valid both for discrete log and RSA settings. Computer experiments implementing some of these ideas are described and analyzed.