Method and apparatus for digital signature authentication

• US 6,049,610 A
• Filed: 09/09/1998
• Issued: 04/11/2000
• Est. Priority Date: 09/17/1991
• Status: Expired due to Term

• Current Assignee: Next Software Incorporated (Apple Inc.)
• Original Assignee: Next Software Incorporated (Apple Inc.)
• Inventors: Crandall, Richard E.
• Primary Examiner(s): CANGIALOSI, SALVATORE A
• Application Number:
  US09/149,876
• Time in Patent Office: 580 Days
• Field of Search: 380/30
• US Class Current: 380/30
• CPC Class Codes: G06F 7/725 over elliptic curves
• CPC Class Codes: G06F 7/727 Modulo N arithmetic, with N being either (2**n)-1,2**n or (2**n)+1, e.g. mod 3, mod 4 or mod 5 G06F7/728 takes precedence
• CPC Class Codes: H04L 9/3066 involving algebraic varieties, e.g. elliptic or hyper-elliptic curves

Abstract

The present invention improves speed and reduces complexity in a digital signature scheme that uses elliptic algebra. The signature scheme generates two points that are compared. If the points do not match, the signature is not authentic. The present invention reduces computations by comparing only the x coordinates of the two generated points. The invention provides a scheme for deducing the possible values of the x-coordinate of a sum of two points using only the x coordinates of the original two points in question. The present invention provides a scheme that limits the possible solutions that satisfy the equation to two (the authentic signature and one other). Because of the large number of possible inauthentic solutions, the chance of a false authentic signature is statistically insignificant.

Claims

1. A method of creating and authenticating a digital signature comprising the steps of:

generating a signature with two points having x and y coordinates;

generating a sum of said two points;

deducing possible values of the x coordinate of said sum using only the x coordinates of said two points.

2. The method of claim 1 wherein said possible values can be generated by at least two possible sources, a first correct source and a second incorrect source.

3. The method of claim 2 wherein the possibility of the existence of said second incorrect source is statistically insignificant.

4. The method of claim 1 further including the steps of comparing said possible values to a predicted value and assuming authenticity when said comparing step is satisfied.

5. The method of claim 1 wherein said step of creating a digital signature comprises the steps of:

generating a random integer m;

computing a point P₁ on an elliptic curve;

computing an integer u using m and P1.

6. The method of claim 5 wherein said elliptic curve has a starting point (X₁, 1).

7. The method of claim 5 wherein said integer u is generated by m+ourPri*M(ciphertext, P) where ciphertext is the encrypted message to be sent and M is a hash function.

8. The method of claim 6 further including a method of authenticating said digital signature comprising the steps of:

using u, generating a point Q having coordinates (X, Y);

using P₁, generating a point P₂ having coordinates (X₂, Y₂);

testing the equality P₁ +P₂ =Q;

identifying a signature as not authentic when the equality P₁ +P₂ =Q is not satisfied.

9. The method of claim 8 wherein said step of testing the equality P₁ +P₂ =Q;

is performed without using Y₁ and Y₂.

10. An article of manufacture comprising:

a computer usable medium having computer readable program code embodied therein for creating a digital signature, the computer readable program code in said article of manufacture comprising;

computer readable program code configured to cause a computer to generate a signature with two points having x and y coordinates;

computer readable program code configured to cause a computer to generate a sum of said two points;

computer readable program code configured to cause a computer to deduce possible values of the x coordinate of said sum using only the x coordinates of said two points.

11. The article of manufacture of claim 10 wherein said possible values can be generated by at least two possible sources, a first correct source and a second incorrect source.

12. The article of manufacture of claim 11 wherein the possibility of the existence of said second incorrect source is statistically insignificant.

13. The article of manufacture of claim 10 further including the steps of comparing said possible values to a predicted value and assuming authenticity when said comparing step is satisfied.

14. The article of manufacture of claim 10 further including;

computer readable program code configured to cause a computer to generate a random integer m;

computer readable program code configured to cause a computer to compute a point P₁ on an elliptic curve;

computer readable program code configured to cause a computer to compute an integer it using m and P1.

15. The article of manufacture of claim 14 wherein said elliptic curve has a starting point (X₁, 1).

16. The article of manufacture of claim 15 wherein said step of generating P₁ is accomplished by m°

(X₁,

     1) and P1 has coordinates (X₁, Y₁).

17. The article of manufacture of claim 16 further including computer readable program code configured to authenticate said digital signature comprising the steps of:

computer readable program code configured to use u, to generate a point Q having coordinates (X, Y);

computer readable program code configured to use P₁, to generate a point P₂ having coordinates (X₂, Y₂);

computer readable program code configured to test the equality P₁ +P₂ =Q;

computer readable program code configured to identify a signature as not authentic when the equality P₁ +P₂ =Q is not satisfied.

18. The article of manufacture of claim 17 wherein said step of testing the equality P₁ +P₂ =Q;

is performed without using Y₁ and Y₂.