Browse Prior Art Database

ANTI-SIMPLE POWER ANALYSIS (SPA) AND EFFICIENT IMPLEMENTATION OF ELLIPTIC CURVES DOUBLE AND ADD OPERATIONS USED IN CRYPTOSYSTEMS

IP.com Disclosure Number: IPCOM000245358D
Publication Date: 2016-Mar-03
Document File: 5 page(s) / 24K

Publishing Venue

The IP.com Prior Art Database

Related People

Orit Saban: AUTHOR

Abstract

A secure and efficient solution to side channel attacks in Elliptic Curve cryptosystems is provided. The internal operations of the Elliptic Curve (EC) addition and EC doubling calculations are composed and arranged such that the exact same sequence of (internal) operations is performed for both EC addition and EC doubling, without dummy operations. This makes these calculations indistinguishable from a side channel analysis perspective.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 32% of the total text.

Page 01 of 5

ANTI-SIMPLE POWER ANALYSIS (SPA) AND EFFICIENT IMPLEMENTATION OF ELLIPTIC CURVES DOUBLE AND ADD OPERATIONS USED IN

CRYPTOSYSTEMS

AUTHOR:

Orit Saban

CISCO SYSTEMS, INC.

ABSTRACT

    A secure and efficient solution to side channel attacks in Elliptic Curve cryptosystems is provided. The internal operations of the Elliptic Curve (EC) addition and EC doubling calculations are composed and arranged such that the exact same sequence of (internal) operations is performed for both EC addition and EC doubling, without dummy operations. This makes these calculations indistinguishable from a side channel analysis perspective.

DETAILED DESCRIPTION

     There are various cryptographic schemes (e.g. encryption, digital signature or Diffie-Hellman key exchange protocol) which are based on Elliptic Curve Cryptography. Like other cryptographic schemes, these have a secret key which is used in calculations. These schemes are considered to be secure as long as the secret key is not revealed.

    These schemes basically involve a scalar multiplication of d*P where scalar d is the secret key and P is a point on the curve. Usually, to calculate this product, one should use the primitive operations of Double and Add over the selected elliptic curve. The doubling operation is the formula used to calculate an addition of a point to itself: M+M (where M is a point on the curve), and the addition operation refers to addition of two different points M+L (M is different from L, M and L are points on the curve). These operations have two formulas which are extremely different (at least for the common Weierstrass form representation y^2=x^3+ax+b). For example, the addition formula requires 14 modular multiplications and the doubling formula has only 10 multiplications.

Copyright 2016 Cisco Systems, Inc.

1


Page 02 of 5

    The difference is the normal of modular multiplications for the doubling formula and the adding formula presents a security problem. Many side-channel attacks can exploit this difference, and it has been shown how the secret key can be leaked by monitoring some side channel information (e.g. power consumption or timing), especially when a hardware accelerator is used. This information can imply when a doubling operation is performed and when an addition operation is performed. In some popular algorithms, this is enough to deduce the secret key. For example, when using the "Double and Add" method for computing d*P, if an attacker can distinguish between point doubling and point addition, the attack can derive the secret key d.

    Presented herein is a secure and efficient solution to side channel attacks. Specifically, a novel method is provided for composing and arranging the internal operations of the EC addition and EC doubling calculations, such that the exact, same sequence of (internal) operations is performed in both the EC addition and EC doubling, without dummy operations. This makes these calculations indistinguishable from a side channel analysis persp...