The search functionality is under construction.

The search functionality is under construction.

Simple power analysis (SPA) can be employed in examining the power consumption trace of elliptic curve scalar multiplication to retrieve the computational sequence. However, SPA cannot distinguish point addition from point subtraction. The attacker still requires an exhaustive search to recover the private key when it is recoded in NAF or recoded by the 2-bit sliding window method. The average Hamming weight of an *n*-bit NAF recoded scalar is *n*/3, and an exhaustive search among the 2^{n/3} candidates is required. This paper shows that in a *left-to-right* NAF recoded or a *left-to-right* 2-bit sliding window manipulated scalar the relative position of nonzero bits will reveal their values. Our analysis skill reduces the number of candidates of the scalar from the naive search of 2^{n/3} to 2^{2n/9} and 2^{0.19n} respectively for the cases of NAF and sliding window method.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.10 pp.1806-1812

- Publication Date
- 2010/10/01

- Publicized

- Online ISSN
- 1745-1337

- DOI
- 10.1587/transfun.E93.A.1806

- Type of Manuscript
- PAPER

- Category
- Cryptography and Information Security

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Chien-Ning CHEN, Sung-Ming YEN, SangJae MOON, "On the Computational Sequence of Scalar Multiplication with Left-to-Right Recoded NAF and Sliding Window Technique" in IEICE TRANSACTIONS on Fundamentals,
vol. E93-A, no. 10, pp. 1806-1812, October 2010, doi: 10.1587/transfun.E93.A.1806.

Abstract: Simple power analysis (SPA) can be employed in examining the power consumption trace of elliptic curve scalar multiplication to retrieve the computational sequence. However, SPA cannot distinguish point addition from point subtraction. The attacker still requires an exhaustive search to recover the private key when it is recoded in NAF or recoded by the 2-bit sliding window method. The average Hamming weight of an *n*-bit NAF recoded scalar is *n*/3, and an exhaustive search among the 2^{n/3} candidates is required. This paper shows that in a *left-to-right* NAF recoded or a *left-to-right* 2-bit sliding window manipulated scalar the relative position of nonzero bits will reveal their values. Our analysis skill reduces the number of candidates of the scalar from the naive search of 2^{n/3} to 2^{2n/9} and 2^{0.19n} respectively for the cases of NAF and sliding window method.

URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.1806/_p

Copy

@ARTICLE{e93-a_10_1806,

author={Chien-Ning CHEN, Sung-Ming YEN, SangJae MOON, },

journal={IEICE TRANSACTIONS on Fundamentals},

title={On the Computational Sequence of Scalar Multiplication with Left-to-Right Recoded NAF and Sliding Window Technique},

year={2010},

volume={E93-A},

number={10},

pages={1806-1812},

abstract={Simple power analysis (SPA) can be employed in examining the power consumption trace of elliptic curve scalar multiplication to retrieve the computational sequence. However, SPA cannot distinguish point addition from point subtraction. The attacker still requires an exhaustive search to recover the private key when it is recoded in NAF or recoded by the 2-bit sliding window method. The average Hamming weight of an *n*-bit NAF recoded scalar is *n*/3, and an exhaustive search among the 2^{n/3} candidates is required. This paper shows that in a *left-to-right* NAF recoded or a *left-to-right* 2-bit sliding window manipulated scalar the relative position of nonzero bits will reveal their values. Our analysis skill reduces the number of candidates of the scalar from the naive search of 2^{n/3} to 2^{2n/9} and 2^{0.19n} respectively for the cases of NAF and sliding window method.},

keywords={},

doi={10.1587/transfun.E93.A.1806},

ISSN={1745-1337},

month={October},}

Copy

TY - JOUR

TI - On the Computational Sequence of Scalar Multiplication with Left-to-Right Recoded NAF and Sliding Window Technique

T2 - IEICE TRANSACTIONS on Fundamentals

SP - 1806

EP - 1812

AU - Chien-Ning CHEN

AU - Sung-Ming YEN

AU - SangJae MOON

PY - 2010

DO - 10.1587/transfun.E93.A.1806

JO - IEICE TRANSACTIONS on Fundamentals

SN - 1745-1337

VL - E93-A

IS - 10

JA - IEICE TRANSACTIONS on Fundamentals

Y1 - October 2010

AB - Simple power analysis (SPA) can be employed in examining the power consumption trace of elliptic curve scalar multiplication to retrieve the computational sequence. However, SPA cannot distinguish point addition from point subtraction. The attacker still requires an exhaustive search to recover the private key when it is recoded in NAF or recoded by the 2-bit sliding window method. The average Hamming weight of an *n*-bit NAF recoded scalar is *n*/3, and an exhaustive search among the 2^{n/3} candidates is required. This paper shows that in a *left-to-right* NAF recoded or a *left-to-right* 2-bit sliding window manipulated scalar the relative position of nonzero bits will reveal their values. Our analysis skill reduces the number of candidates of the scalar from the naive search of 2^{n/3} to 2^{2n/9} and 2^{0.19n} respectively for the cases of NAF and sliding window method.

ER -