Efficient elliptic curve double-and-add calculator

• US 20040001590A1
• Filed: 06/27/2002
• Published: 01/01/2004
• Est. Priority Date: 06/27/2002
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Eisentraeger, Anne Kirsten, Montgomery, Peter L., Lauter, Kristin Estella
• Application Number:
  US10/185,782
• Publication Number:
  US 20040001590A1
• Time in Patent Office: Days
• US Class Current: 380/30
• CPC Class Codes: G06F 7/725 over elliptic curves

Abstract

An implementation of a technology, described herein, for facilitating cryptography and other security processing. At least one implementation, described herein, maximizes the speed and security of fast exponentiation. At least one implementation, described herein, employs exponentiation with optimized elliptic curve “double-and-add” techniques to maximize speed and security of cryptosystems. This abstract itself is not intended to limit the scope of this patent. The scope of the present invention is pointed out in the appending claims.

Claims

1. A computer-readable medium having computer-executable instructions that, when executed by a computer, performs a method facilitating the efficiency of a “

double-and-add”

operation, where P and Q are points on an elliptic curve, the method comprising;

combining point P and point Q to produce point S, wherein fewer than all of the coordinates of point S are determined;

combining point S and point P to produce point T.

2. A medium as recited in claim 1, wherein the combining of point P and point Q comprises adding point P to point Q.

3. A medium as recited in claim 1, wherein the combining of point P and point Q comprises subtracting one point from another.

4. A medium as recited in claim 1, wherein the combining point S to point P comprises adding point S to point P.

5. A medium as recited in claim 1, wherein a “

double-and-add”

operation, where P and Q are points on an elliptic curve, produces the point T.

6. A medium as recited in claim 1, wherein a y-coordinate of S is not determined but the slope of the line through P and ±

Q is output along with the x-coordinate of S.

7. A medium as recited in claim 1, wherein during one or more of the combinations, m, m′

, x₄, and y₄ are determined as follows;

8. A medium as recited in claim 1, wherein the elliptic curve is defined over a field of characteristic 2.

9. A medium as recited in claim 1, wherein the elliptic curve is characterized by y²+xy=x³+ax²+b over a field of characteristic 2.

10. A medium as recited in claim 1, wherein the elliptic curve is defined over a field of characteristic 3.

11. A medium as recited in claim 1, wherein the elliptic curve is characterized by y²=x³+ax²+bx+c over a field of characteristic 3.

12. A medium as recited in claim 1, wherein the elliptic curve is defined over a field of odd characteristic not equal to 3.

13. A medium as recited in claim 1, wherein the elliptic curve is characterized by y²=x³+ax+b over a field of odd characteristic not equal to 3.

14. A medium as recited in claim 1, wherein the elliptic curve is characterized by y²=x³+ax+b over a field of characteristic 0.

15. A device comprising a computer-readable medium as recited in claim 1.

16. A computer-readable medium having computer-executable instructions that, when executed by a computer, performs a method facilitating the efficiency of a “

double-and-add”

operation, where P and Q are points on an elliptic curve, the method comprising;

combining point P and point Q to produce point S;

combining point S and point P to produce point T.

17. A medium as recited in claim 16, wherein at least one coordinate of the point S is not determined.

18. A medium as recited in claim 16, wherein the combining of point P and point Q comprises adding point P to point Q.

19. A medium as recited in claim 16, wherein the combining of point P and point Q comprises subtracting one point from another.

20. A medium as recited in claim 16, wherein the combining point S to point P comprises adding point S to point P.

21. A medium as recited in claim 16, wherein a “

double-and-add”

operation, where P and Q are points on an elliptic curve, produces the point T.

22. A medium as recited in claim 16, wherein a y-coordinate of S is not determined but the slope of the line through P and ±

Q is output along with the x-coordinate of S.

23. A medium as recited in claim 16, wherein during one or more of the combinations, m, m′

, x₄, and y₄ are determined as follows;

24. A medium as recited in claim 16, wherein the elliptic curve is defined over a field of characteristic 2.

25. A medium as recited in claim 16, wherein the elliptic curve is characterized by y²+xy=x³+ax²+b over a field of characteristic 2.

26. A medium as recited in claim 16, wherein the elliptic curve is defined over a field of characteristic 3.

27. A medium as recited in claim 16, wherein the elliptic curve is characterized by y²=x³+ax²+bx+c over a field of characteristic 3.

28. A medium as recited in claim 16, wherein the elliptic curve is defined over a field of characteristic not equal to 2 or 3.

29. A medium as recited in claim 16, wherein the elliptic curve is characterized by y²=x³+ax+b over a field of characteristic not equal to 2 or 3.

30. A medium as recited in claim 16, wherein the elliptic curve is characterized by y²=x²+ax+b over a field of characteristic 0.

31. A device comprising a computer-readable medium as recited in claim 16.

32. A computer-readable medium having computer-executable instructions that, when executed by a computer, performs a method facilitating the efficiency of a “

double-and-add”

operation with a collection of points on an elliptic curve, the method comprises combining multiples of one or more points of the collection to produce point S on the elliptic curve.

33. A medium as recited in claim 32, wherein at least one coordinate of the point S is not determined.

34. A medium as recited in claim 32, wherein the combining comprises adding multiples of one or more points of the collection on the elliptic curve.

35. A medium as recited in claim 32, wherein the combining comprises subtracting multiples of one or more points of the collection on the elliptic curve.

36. A medium as recited in claim 32, wherein the elliptic curve is defined over a field of characteristic 2.

37. A medium as recited in claim 32, wherein the elliptic curve is characterized by y²+xy=x³+ax²+b over a field of characteristic 2.

38. A medium as recited in claim 32, wherein the elliptic curve is defined over a field of characteristic 3.

39. A medium as recited in claim 32, wherein the elliptic curve is characterized by y²=x³+ax²+bx+c over a field of characteristic 3.

40. A medium as recited in claim 32, wherein the elliptic curve is defined over a field of characteristic not equal to 2 or 3.

41. A medium as recited in claim 32, wherein the elliptic curve is characterized by y²=x³+ax+b over a field of characteristic not equal to 2 or 3.

42. A medium as recited in claim 32, wherein the elliptic curve is characterized by y²=x³+ax+b over a field of characteristic 0.

43. A device comprising a computer-readable medium as recited in claim 32.

44. A method facilitating the efficiency of a “

double-and-add”

operation, where P and Q are points on an elliptic curve, the method comprising;

combining point P and point Q to produce point S, wherein fewer than all of the coordinates of point S are determined;

combining point S and point P to produce point T.

45. A method as recited in claim 44, wherein the combining of point P and point Q comprises adding point P to point Q.

46. A method as recited in claim 44, wherein the combining of point P and point Q comprises subtracting one point from another.

47. A method as recited in claim 44, wherein the combining point S to point P comprises adding point S to point P.

48. A method as recited in claim 44, wherein a “

double-and-add”

operation, where P and Q are points on an elliptic curve, produces the point T.

49. A method as recited in claim 44, wherein at least one coordinate of the point S is not determined.

50. A method as recited in claim 44, wherein a y-coordinate of S is not determined but the slope of the line through P and ±

Q is output along with the x-coordinate of S.

51. A method as recited in claim 44, wherein during one or more of the combinations, m, m′

, x₄, and y₄ are determined as follows;

52. A method as recited in claim 44, wherein the elliptic curve is defined over a field of characteristic 2.

53. A method as recited in claim 44, wherein the elliptic curve is characterized by y²+xy=x³+ax²+b over a field of characteristic 2.

54. A method as recited in claim 44, wherein the elliptic curve is defined characterized over a field of characteristic not equal to 2 or 3.

55. A method as recited in claim 44, wherein the elliptic curve is characterized by y²=x³+ax+b over a field of characteristic not equal to 2 or 3.

56. A method as recited in claim 44, wherein the elliptic curve is characterized by y²=x³+ax+b over a field of characteristic 0.

57. A method facilitating the efficiency of a “

double-and-add”

operation with a collection of points on an elliptic curve, the method comprises combining multiples of one or more points of the collection to produce point S on the elliptic curve.

58. A method as recited in claim 57, wherein at least one coordinate of the point S is not determined.

59. A method as recited in claim 57, wherein the combining comprises adding multiples of one or more points of the collection on the elliptic curve.

60. A method as recited in claim 57, wherein the combining comprises subtracting multiples of one or more points of the collection on the elliptic curve.

61. A method as recited in claim 57, wherein the elliptic curve is defined over a field of characteristic 2.

62. A method as recited in claim 57, wherein the elliptic curve is characterized by y²+xy=x³+ax²+b over a field of characteristic 2.

63. A method as recited in claim 57, wherein the elliptic curve is defined over a field of characteristic 3.

64. A method as recited in claim 57, wherein the elliptic curve is characterized by y²=x³+ax²+bx+c over a field of characteristic 3.

65. A method as recited in claim 57, wherein the elliptic curve is defined over a field of characteristic not equal to 2 or 3.

66. A method as recited in claim 57, wherein the elliptic curve is characterized by y²=x³+ax+b over a field of characteristic not equal to 2 or 3.

67. A method as recited in claim 57, wherein the elliptic curve is characterized by y²=x³+ax+b over a field of characteristic 0.

68. A crypto-system comprising:

a memory comprising a set of computer program instructions; and

a processor coupled to the memory, the processor being configured to execute the computer program instructions facilitating the efficiency of a “

double-and-add”

operation, where P and Q are points on an elliptic curve, the instructions comprising;

combining point P and point Q to produce point S, wherein fewer than all of the coordinates of point S are determined;

combining point S and point P to produce point T.