Granted Patent B2

US 8,369,517 · App. 12/190,539 · Granted Feb 5, 2013

Abstract

Claims (107)

1. An elliptic curve cryptographic method performed by a device adapted to perform cryptographic operations, the method comprising:

obtaining a point P on an elliptic curve, the point P representing material to be encrypted, the point P defined in a three-dimensional projective coordinate system by x, y, z reference coordinates, the direction of the z reference coordinate in the coordinate system determined by the cross product of the x and y reference coordinates;

obtaining an n-bit integer k;

computing points P 1 , P 2 on the elliptic curve as a function of P;

performing a scalar multiplication operation using P 1 , P 2 , k and n, where during the scalar multiplication operation the point P is recomputed as a function of points P 1 and P 2 , the re-computing including addition and subtraction operations on points P 1 and P 2 , the re-computing resulting in the value of the z coordinate of P 1 being equal to the value of the z coordinate of P 2 ; and

providing encrypted material [k]P resulting from the scalar multiplication operation.

2. The method of claim 1 , where the coordinate system is a Jacobian coordinate system.

3. The method of claim 1 , where the elliptic curve is a Montgomery elliptic curve.

4. The method of claim 1 , where the addition is Meloni addition.

5. An elliptic curve cryptographic method performed by a device adapted to perform cryptographic operations, the method comprising:

obtaining a point P on an elliptic curve, the point P representing material to be encrypted, the point P defined in a three-dimensional coordinate system by x, y, z reference coordinates, the direction of the z reference coordinate in the coordinate system determined by the cross product of the x and y reference coordinates;

obtaining an n-bit integer k;

generating a point P 1 by doubling point P;

generating a point P 2 by setting P 2 equal to P, resulting in the value of the z coordinate of P 1 being equal to the value of the z coordinate of P 2 ;

setting point P 1 equal to the sum of points P 1 and P 2 ;

setting point P 2 equal to the difference of points P 1 and P 2 ;

determining if k is equal to zero;

if k is equal to zero, setting the y coordinate of point P 2 to a negative y coordinate of point P 2 ;

recomputing point P 1 to be equal to a recomputed version of point P 1 with an appropriate z-coordinate;

recomputing point P 2 to be equal to the sum of points P 1 and P 2 ;

if k is not equal to zero, recomputing point P 1 to be equal to the sum of points P 1 and P 2 ;

recomputing point P 2 to be equal to a recomputed version of point P 1 with an appropriate z-coordinate; and

providing point P 2 , where P 2 is equal to [k]P.

6. The method of claim 5 , where the coordinate system is a Jacobian coordinate system.

7. The method of claim 5 , where the elliptic curve is a Montgomery elliptic curve.

8. The method of claim 5 , where the sum of points is performed using Meloni addition.

9. An elliptic curve cryptographic method performed by a device adapted to perform cryptographic operations, the method comprising:

obtaining a point P on an elliptic curve, the point P representing material to be encrypted, the point P defined in a three-dimensional coordinate system by x, y, z reference coordinates, the direction of the z reference coordinate in the coordinate system determined by the cross product of the x and y reference coordinates;

obtaining an n-bit integer k;

generating a point P 1 by doubling point P;

generating a point P 2 by setting P 2 equal to P, resulting in the value of the z coordinate of P 1 being equal to the value of the z coordinate of P 2 ;

generating a point Psave by setting Psave equal to point P;

determining if n is equal to zero;

if n is not equal to zero;

setting point P 1 equal to the sum of points P 1 and P 2 ;

setting point P 2 equal to the difference of points P 1 and P 2 ;

determining if k is equal to zero;

if k is equal to zero, recomputing point P 1 to be equal to a recomputed version of point P 1 with an appropriate z-coordinate;

recomputing point P 2 to be equal to the sum of points P 1 and a negative of point P 2 ;

if k is not equal to zero, recomputing point P 1 to be equal to the sum of points P 1 and P 2 ;

recomputing point P 2 to be equal to a recomputed version of point P 1 with an appropriate z-coordinate;

if n is equal to zero, recomputing point P 1 to be equal to the sum of points P 1 and P 2 ;

recomputing point P 2 to be equal to the difference of points P 1 and P 2 ;

recomputing the z coordinate of point P 2 using the x, y, and z coordinates of point Psave and the x and y coordinates of point P 2 ;

recomputing the z coordinate of point P 2 to be equal to the difference between the x coordinate of point P 2 and the x coordinate of point P 1 multiplied by the z coordinate of point P 2 ;

determining if k is equal to zero;

if k is equal to zero, recomputing point P 1 to be equal to a recomputed version of point P 1 with an appropriate z-coordinate;

recomputing point P 2 to be equal to the sum of points P 1 and P 2 ;

if k is not equal to zero, recomputing point P 1 to be equal to the sum of points P 1 and P 2 ;

recomputing point P 2 to be equal a recomputed version of point P 1 with an appropriate z-coordinate; and

providing point P 2 , where P 2 is equal to P.

10. The method of claim 9 , where the coordinate system is a Jacobian coordinate system.

11. The method of claim 9 , where the elliptic curve is a Montgomery elliptic curve.

12. The method of claim 9 , where the sum of points is performed using Meloni addition.

13. An elliptic curve cryptosystem, comprising:

an interface operable for receiving a point P on an elliptic curve, the point P representing material to be encrypted, the point P defined in a three-dimensional coordinate system by x, y, z reference coordinates, the direction of the z reference coordinate in the coordinate system determined by the cross product of the x and y reference coordinates, the interface further operable for receiving an n-bit integer k; and

a computer processor coupled to the interface, the processor operable for:

computing points P 1 , P 2 on the elliptic curve as a function of P;

performing a scalar multiplication operation using P 1 , P 2 , k and n, where during the scalar multiplication operation the point P is recomputed as a function of points P 1 and P 2 , the re-computing including addition and subtraction operations on points P 1 and P 2 , the re-computing resulting in the value of the z coordinate of P 1 being equal to the value of the z coordinate of P 2 ; and

providing encrypted material [k]P resulting from the scalar multiplication operation through the interface, where [k]P is encrypted material.

14. The system of claim 13 , where the coordinate system is a Jacobian coordinate system.

15. The system of claim 13 , where the elliptic curve is a Montgomery elliptic curve.

16. The system of claim 13 , where the addition is Meloni addition.

17. An elliptic curve cryptosystem, comprising:

an interface operable for receiving a point P on an elliptic curve, the point P representing material to be encrypted, the point P defined in a three-dimensional coordinate system by x, y, z reference coordinates, the direction of the z reference coordinate in the coordinate system determined by the cross product of the x and y reference coordinates, the interface further operable for receiving an n-bit integer k; and

a computer processor coupled to the interface and operable for:

generating a point P 1 by doubling point P;

generating a point P 2 by setting P 2 equal to P, resulting in the value of the z coordinate of P 1 being equal to the value of the z coordinate of P 2 ;

setting point P 1 equal to the sum of points P 1 and P 2 ;

setting point P 2 equal to the difference of points P 1 and P 2 ;

determining if k is equal to zero;

if k is equal to zero, setting the y coordinate of point P 2 to a negative y coordinate of point P 2 ;

recomputing point P 1 to be equal to a recomputed version of point P 1 with an appropriate z-coordinate;

recomputing point P 2 to be equal to the sum of points P 1 and P 2 ;

if k is not equal to zero, recomputing point P 1 to be equal to the sum of points P 1 and P 2 ;

recomputing point P 2 to be equal to a recomputed version of point P 1 with an appropriate z-coordinate; and

making point P 2 available through the interface, where P 2 is equal to [k]P, and [k]P is encrypted material.

18. The system of claim 17 , where the coordinate system is a Jacobian coordinate system.

19. The system of claim 17 , where the elliptic curve is a Montgomery elliptic curve.

20. The system of claim 17 , where the sum of points is performed using Meloni addition.

21. An elliptic curve cryptosystem, comprising:

an interface operable for receiving a point P on an elliptic curve, the point P representing material to be encrypted, the point P defined in a three-dimensional coordinate system by x, y, z reference coordinates, the direction of the z reference coordinate in the coordinate system determined by the cross product of the x and y reference coordinates, the interface further operable for receiving an n-bit integer k; and

a computer processor coupled to the interface and operable for:

generating a point P 1 by doubling point P;

generating a point P 2 by setting P 2 equal to P, resulting in the value of the z coordinate of P 1 being equal to the value of the z coordinate of P 2 ;

generating a point Psave by setting Psave equal to point P;

determining if n is equal to zero;

if n is not equal to zero;

setting point P 1 equal to the sum of points P 1 and P 2 ;

setting point P 2 equal to the difference of points P 1 and P 2 ;

determining if k is equal to zero;

if k is equal to zero, recomputing point P 1 to be equal to a recomputed version of point P 1 with an appropriate z-coordinate;

recomputing point P 2 to be equal to the sum of points P 1 and a negative of point P 2 ;

if k is not equal to zero, recomputing point P 1 to be equal to the sum of points P 1 and P 2 ;

recomputing point P 2 to be equal to a recomputed version of point P 1 with an appropriate z-coordinate;

if n is equal to zero, recomputing point P 1 to be equal to the sum of points P 1 and P 2 ;

recomputing point P 2 to be equal to the difference of point P 1 and P 2 ;

recomputing the z coordinate of point P 2 using the x,y, and z coordinates of point Psave and the x and y coordinates of point P 2 ;

determining if k is equal to zero;

recomputing the z coordinate of point P 2 to be equal to the difference between the x coordinate of point P 2 and the x coordinate of point P 1 multiplied by the z coordinate of point P 2 ;

if k is equal to zero, recomputing point P 1 to be equal to a recomputed version of point P 1 with an appropriate z-coordinate;

recomputing point P 2 to be equal to the sum of points P 1 and P 2 ;

if k is not equal to zero, recomputing point P 1 to be equal to the sum of points P 1 and P 2 ;

recomputing point P 2 to be equal to a recomputed version of point P 1 with an appropriate z-coordinate; and providing point P 2 , where P 2 is equal to P.

22. The system of claim 21 , where the coordinate system is a Jacobian coordinate system.

23. The system of claim 21 , where the elliptic curve is a Montgomery elliptic curve.

24. The system of claim 21 , where the sum of points is performed using Meloni addition.

Assignments (7)