Method and system for atomicity for elliptic curve cryptosystems
AssigneeInternational Business Machines Corporation
InventorLars Elmegaard-Fessel
Life of this patent
Estimating the term…
Abstract
A method and system are provided for atomicity for elliptic curve cryptosystems (ECC-systems). The method includes a side channel atomic scalar multiplication algorithm using mixed coordinates. The mixed coordinates are chosen based on a ratio of I/M where I and M are the time required to execute an inversion and a multiplication in the ground field respectively. If the I/M ratio is less than 60, a mixture of affine and Jacobian coordinates are used during scalar multiplication. If the I/M ratio is 60 or more, a mixture of Chudnovsky-Jacobian and Jacobian coordinates are used during scalar multiplication. The method is optimized for elliptic curves over Fp defined by an equation of the form y2=x3+ax+b, where a, bεFp, having a=−3.
Claims9
A method of providing atomicity for cryptosystems based on elliptic curves, comprising:
- using a computing device comprising:
- a side channel atomic scalar multiplication algorithm using mixed coordinates, including:
- repeating a sequence of field operations for each elliptic curve addition or doubling operation to provide an atomic block, wherein the atomic block appears equivalent by side-channel analysis;
- and
- choosing the coordinates based on a ratio of I/M where I and M are the time required to execute an inversion and a multiplication in the ground field respectively, wherein when the I/M ratio is less than 60, a combination of both affine and Jacobian coordinates are used during scalar multiplication and when the I/M ratio is 60 or more, a combination of both Chudnovsky-Jacobian and Jacobian coordinates are used during scalar multiplication.
An elliptic curve cryptography system (ECC-system) providing atomicity, comprising:
- means for encryption including means for applying a side channel atomic scalar multiplication using mixed coordinates, including:
- means for repeating a sequence of field operations for each elliptic curve addition or doubling operation to provide an atomic block, wherein the atomic block appears equivalent by side-channel analysis;
- and
- means for choosing the coordinates based on a ratio of I/M where I and M are the time required to execute an inversion and a multiplication in the ground field respectively, wherein when the I/M ratio is less than 60, a combination of both affine and Jacobian coordinates are used during scalar multiplication and when the I/M ratio is 60 or more, a combination of both Chudnovsky-Jacobian and Jacobian coordinates are used during scalar multiplication;
- and
- means for transferring encrypted data, wherein the encrypted data is protected from side-channel analysis.
A computer program product stored on a non-transitory computer readable storage medium, comprising computer readable program code means for performing the steps of, when executed on a computer:
- a side channel atomic scalar multiplication algorithm using mixed coordinates, including:
- repeating a sequence of field operations for each elliptic curve addition or doubling operation to provide an atomic block, wherein the atomic block appears equivalent by side-channel analysis;
- and
- choosing the coordinates based on a ratio of I/M where I and M are the time required to execute an inversion and a multiplication in the ground field respectively, wherein when the I/M ratio is less than 60, a combination of both affine and Jacobian coordinates are used during scalar multiplication and when the I/M ratio is 60 or more, a combination of both Chudnovsky-Jacobian and Jacobian coordinates are used during scalar multiplication.
Dependencies are inferred from the claim text.