Browse Prior Art Database

An Elliptic Curve Scalar Multiplication Algorithm Resistant to Simple Power Analysis

IP.com Disclosure Number: IPCOM000006768D
Original Publication Date: 2002-Jan-30
Included in the Prior Art Database: 2002-Jan-30
Document File: 5 page(s) / 94K

Publishing Venue

Motorola

Related People

Paul Montague: AUTHOR [+2]

Related Documents

CHES 1999, Volume 1717: OTHER [+3]

Abstract

Elliptic curve cryptography is rapidly becoming the public key cryptographic algorithm of choice for a variety of portable/embedded devices, such as PDAs, mobile phones, smart cards, etc, because of the reduced number of key bits required in comparison to other cryptosystems. However, this class of devices is uniquely susceptible to so-called side-channel attacks, aimed at discovering information about the users private key by monitoring of e.g. power consumption during a computation using this key. The problem then is to render such attacks either infeasible or impractical by an appropriate choice of algorithm and/or implementation of the private key computation in the device. We present an algorithm for elliptic curve scalar multiplication using a reformatted scalar. Our solution is shown to be more efficient than those previously proposed in the literature (either in terms of the impact on the computational time due to addition of the defences or on the memory requirements).

This text was extracted from a Microsoft Word document.
This is the abbreviated version, containing approximately 23% of the total text.

An Elliptic Curve Scalar Multiplication Algorithm Resistant  to Simple Power Analysis

Paul Montague,

Yvonne Hitchcock,                        

Abstract

Elliptic curve cryptography is rapidly becoming the public key cryptographic algorithm of choice for a variety of portable/embedded devices, such as PDAs, mobile phones, smart cards, etc, because of the reduced number of key bits required in comparison to other cryptosystems. However, this class of devices is uniquely susceptible to so-called side-channel attacks, aimed at discovering information about the user’s private key by monitoring of e.g. power consumption during a computation using this key. The problem then is to render such attacks either infeasible or impractical by an appropriate choice of algorithm and/or implementation of the private key computation in the device. We present an algorithm for elliptic curve scalar multiplication using a reformatted scalar. Our solution is shown to be more efficient than those previously proposed in the literature (either in terms of the impact on the computational time due to addition of the defences or on the memory requirements).

1.      Introduction

Elliptic curves were first proposed as a basis for public key cryptography in the mid 1980’s. They have a number of advantages over more traditional schemes, e.g. RSA. For example, they provide equivalent levels of security at much shorter key sizes (it is widely accepted that 160 bit elliptic curves currently offer a similar level of security to 1024 bit RSA keys). In addition, computational requirements can be less.

The cryptographic community is rather conservative in the adoption of new algorithms and protocols. It is only with the test of time, and resistance to attacks during that time, that algorithms gain acceptance. Recently confidence in the security of elliptic curve algorithms has risen to a point where they are now being included in standards, such as IEEE P1363, WAP, ANSI X9.62 and ANSI X9.63.  Because of the nature of the advantages of elliptic curves over more tradi­tional public key methods, as described above, one of the main domains for their implementation is in embedded devices of limited computational power and wireless devices with limited bandwidth, e.g. smart cards, PDAs, mobile phones, etc. With the recent drive towards mobile e-commerce and wireless enabling of security-requiring applications (such as digital rights management (DRM)), the implementation of security on such devices and consequently the need for widespread deployment of elliptic curve methods is manifest. The uptake of DRM will be enabled and driven by the forthcoming 3G standards for wireless communications.  This class of embedded devices upon which such deployment is required is, unfortunately, also highly susceptible to so-called side-channel attacks. These are a class of attacks against cryptographic systems in which the attacker measures some information leaked by the system during its operation (such as power con­sumption, radiatio...