A Simple Power Attack on a Randomized Addition-Subtraction Chains Method for Elliptic Curve Cryptosystems

Katsuyuki Okeya, Kouichi Sakurai

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


We show that a randomized addition-subtraction chains countermeasure against side channel attacks is vulnerable to an SPA attack, which is a kind of side channel attack, under distinguishability between addition and doubling. The side channel attack takes advantage of information leaked during execution of a cryptographic procedure. The randomized addition-subtraction chains countermeasure was proposed by Oswald-Aigner, and is based on a random decision inserted into computations. However, the question of its immunity to side channel attacks is still controversial. The randomized addition-subtraction chains countermeasure has security flaw in timing attacks, another kind of side channel attack. We have implemented the proposed attack algorithm, whose input is a set of AD sequences, which consist of the characters "A" and "D" to indicate addition and doubling, respectively. Our program has clarified the effectiveness of the attack. The attack algorithm could actually detect secret scalars for given AD sequences. The average time to detect a 160-bit scalar was about 6 milliseconds, and only 30 AD sequences were enough to detect such a scalar. Compared with other countermeasures against side channel attacks, the randomized addition-subtraction chains countermeasure is much slower.

Original languageEnglish
Pages (from-to)1171-1180
Number of pages10
JournalIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
Issue number5
Publication statusPublished - May 2003

All Science Journal Classification (ASJC) codes

  • Signal Processing
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering
  • Applied Mathematics


Dive into the research topics of 'A Simple Power Attack on a Randomized Addition-Subtraction Chains Method for Elliptic Curve Cryptosystems'. Together they form a unique fingerprint.

Cite this