Simple Power Analysis on Fast Modular Reduction with Generalized Mersenne Prime for Elliptic Curve Cryptosystems

Yasuyuki SAKAI; Kouichi SAKURAI

doi:10.1093/ietfec/e89-a.1.231

Simple Power Analysis on Fast Modular Reduction with Generalized Mersenne Prime for Elliptic Curve Cryptosystems

Yasuyuki SAKAI, Kouichi SAKURAI

Full Text Views

0

Share
Cite this

Summary :

We discuss side channel leakage from modular reduction for NIST recommended domain parameters. FIPS 186-2 has 5 recommended prime fields. These primes have a special form which is referred to as generalized Mersenne prime. These special form primes facilitate especially efficient implementation. A typical implementation of efficient modular reduction with such primes includes conditional reduction. A conditional reduction in modular reduction can constitute an information channel on the secret exponent. Several researchers have produced unified code for elliptic point addition and doubling in order to avoid a simple power analysis (SPA). However, Walter showed that SPA still be possible if Montgomery multiplication with conditional reduction is implemented within the unified code. In this paper we show SPA on the modular reduction with NIST recommended primes, combining with the unified code for elliptic point operations. As Walter stated, our results also indicate that even if the unified codes are implemented for elliptic point operations, underlying field operations should be implemented in constant time. The unified approach in itself can not be a countermeasure for side channel attacks.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E89-A No.1 pp.231-237

Publication Date: 2006/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1093/ietfec/e89-a.1.231

Type of Manuscript: Special Section LETTER (Special Section on Cryptography and Information Security)

Category: Side Channel Analysis

Cite this

Copy

Yasuyuki SAKAI, Kouichi SAKURAI, "Simple Power Analysis on Fast Modular Reduction with Generalized Mersenne Prime for Elliptic Curve Cryptosystems" in IEICE TRANSACTIONS on Fundamentals, vol. E89-A, no. 1, pp. 231-237, January 2006, doi: 10.1093/ietfec/e89-a.1.231.
Abstract: We discuss side channel leakage from modular reduction for NIST recommended domain parameters. FIPS 186-2 has 5 recommended prime fields. These primes have a special form which is referred to as generalized Mersenne prime. These special form primes facilitate especially efficient implementation. A typical implementation of efficient modular reduction with such primes includes conditional reduction. A conditional reduction in modular reduction can constitute an information channel on the secret exponent. Several researchers have produced unified code for elliptic point addition and doubling in order to avoid a simple power analysis (SPA). However, Walter showed that SPA still be possible if Montgomery multiplication with conditional reduction is implemented within the unified code. In this paper we show SPA on the modular reduction with NIST recommended primes, combining with the unified code for elliptic point operations. As Walter stated, our results also indicate that even if the unified codes are implemented for elliptic point operations, underlying field operations should be implemented in constant time. The unified approach in itself can not be a countermeasure for side channel attacks.
URL: https://globals.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e89-a.1.231/_p

Copy

@ARTICLE{e89-a_1_231,
author={Yasuyuki SAKAI, Kouichi SAKURAI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Simple Power Analysis on Fast Modular Reduction with Generalized Mersenne Prime for Elliptic Curve Cryptosystems},
year={2006},
volume={E89-A},
number={1},
pages={231-237},
abstract={We discuss side channel leakage from modular reduction for NIST recommended domain parameters. FIPS 186-2 has 5 recommended prime fields. These primes have a special form which is referred to as generalized Mersenne prime. These special form primes facilitate especially efficient implementation. A typical implementation of efficient modular reduction with such primes includes conditional reduction. A conditional reduction in modular reduction can constitute an information channel on the secret exponent. Several researchers have produced unified code for elliptic point addition and doubling in order to avoid a simple power analysis (SPA). However, Walter showed that SPA still be possible if Montgomery multiplication with conditional reduction is implemented within the unified code. In this paper we show SPA on the modular reduction with NIST recommended primes, combining with the unified code for elliptic point operations. As Walter stated, our results also indicate that even if the unified codes are implemented for elliptic point operations, underlying field operations should be implemented in constant time. The unified approach in itself can not be a countermeasure for side channel attacks.},
keywords={},
doi={10.1093/ietfec/e89-a.1.231},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Simple Power Analysis on Fast Modular Reduction with Generalized Mersenne Prime for Elliptic Curve Cryptosystems
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 231
EP - 237
AU - Yasuyuki SAKAI
AU - Kouichi SAKURAI
PY - 2006
DO - 10.1093/ietfec/e89-a.1.231
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E89-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2006
AB - We discuss side channel leakage from modular reduction for NIST recommended domain parameters. FIPS 186-2 has 5 recommended prime fields. These primes have a special form which is referred to as generalized Mersenne prime. These special form primes facilitate especially efficient implementation. A typical implementation of efficient modular reduction with such primes includes conditional reduction. A conditional reduction in modular reduction can constitute an information channel on the secret exponent. Several researchers have produced unified code for elliptic point addition and doubling in order to avoid a simple power analysis (SPA). However, Walter showed that SPA still be possible if Montgomery multiplication with conditional reduction is implemented within the unified code. In this paper we show SPA on the modular reduction with NIST recommended primes, combining with the unified code for elliptic point operations. As Walter stated, our results also indicate that even if the unified codes are implemented for elliptic point operations, underlying field operations should be implemented in constant time. The unified approach in itself can not be a countermeasure for side channel attacks.
ER -