US5805703A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for digital signature authentication
Assignee: Next Software Inc
•
Filing: 1996-11-27
•
Granted: 1998-09-08
•
Expires: 2016-11-27
Abstract
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.
Inventors
- 👤 Richard E. Crandall
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 06:19
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/30; H04L9/3066; G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724; G06F7/725; G06F7/727
Claims Analysis
Total Claims: 30
Claim 1
Independent Claim
33 words
A method of creating a digital signature comprising the steps of: generating a random integer m; computing a point P 1 on an elliptic curve; computing an integer u using m and P1.
Claim 2
Independent Claim
33 words
A method of creating a digital signature comprising the steps of: generating a random integer m; computing a point P 1 on an elliptic curve; computing an integer u using m and P1.
Claim 3
Dependent Claim
17 words
The method of claim 1 wherein said elliptic curve has a starting point (X 1 , 1).
Claim 4
Dependent Claim
29 words
The method of claim 2 wherein said step of generating P 1 is accomplished by m°(X 1 , 1) and P1 has coordinates (X 1 , Y 1 ).
Claim 5
Dependent Claim
30 words
The method of claim 1 wherein said integer u is generated by m+our Pri*M(ciphertext, P) where ciphertext is the encrypted message to be sent and M is a hash function.
Claim 6
Dependent Claim
21 words
The method of claim 4 further including sending the pair (u, P 1 ) as a digital signature to a receiver.
Claim 7
Dependent Claim
70 words
The method of claim 2 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 1 , generating a point P 2 having coordinates (X 2 , Y 2 ); testing the equality P 1 +P 2 =Q; identifying a signature as not authentic when the equality P 1 +P 2 =Q is not satisfied.
Claim 8
Dependent Claim
27 words
The method of claim 6 wherein said step of testing the equality P 1 +P 2 =Q; is performed without using Y 1 and Y 2 .
Claim 9
Dependent Claim
68 words
The method of claim 2 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 1 , generating a point P 2 having coordinates (X 2 , Y 2 ); testing the equality P 1 +P 2 =Q; identifying a signature as authentic when the equality P 1 +P 2 =Q is satisfied.
Claim 10
Dependent Claim
27 words
The method of claim 8 wherein said step of testing the equality P 1 +P 2 =Q; is performed without using Y 1 and Y 2 .
Claim 11
Dependent Claim
84 words
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 random integer m; computer readable program code configured to cause a computer to compute a point P 1 on an elliptic curve; computer readable program code configured to cause a computer to compute an integer u using m and P1.
Claim 12
Dependent Claim
84 words
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 random integer m; computer readable program code configured to cause a computer to compute a point P 1 on an elliptic curve; computer readable program code configured to cause a computer to compute an integer u using m and P1.
Claim 13
Dependent Claim
19 words
The article of manufacture of claim 10 wherein said elliptic curve has a starting point (X 1 , 1).
Claim 14
Dependent Claim
31 words
The article of manufacture of claim 11 wherein said step of generating P 1 is accomplished by m°(X 1 , 1) and P1 has coordinates (X 1 , Y 1 ).
Claim 15
Dependent Claim
32 words
The article of manufacture of claim 10 wherein said integer u is generated by m+our Pri*M(ciphertext, P) where ciphertext is the encrypted message to be sent and M is a hash function.
Claim 16
Dependent Claim
23 words
The article of manufacture of claim 13 further including sending the pair (u, P 1 ) as a digital signature to a receiver.
Claim 17
Dependent Claim
101 words
The article of manufacture of claim 11 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 1 , to generate a point P 2 having coordinates (X 2 , Y 2 ); computer readable program code configured to test the equality P 1 +P 2 =Q; computer readable program code configured to identify a signature as not authentic when the equality P 1 +P 2 =Q is not satisfied.
Claim 18
Dependent Claim
29 words
The article of manufacture of claim 15 wherein said step of testing the equality P 1 +P 2 =Q; is performed without using Y 1 and Y 2 .
Claim 19
Dependent Claim
99 words
The article of manufacture of claim 11 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 1 , to generate a point P 2 having coordinates (X 2 , Y 2 ); computer readable program code configured to test the equality P 1 +P 2 =Q; computer readable program code configured to identify a signature as authentic when the equality P 1 +P 2 =Q is satisfied.
Claim 20
Dependent Claim
29 words
The article of manufacture of claim 17 wherein said step of testing the equality P 1 +P 2 =Q; is performed without using Y 1 and Y 2 .
Claim 21
Independent Claim
33 words
A system for creating a digital signature comprising: processing means for: generating a random integer m; computing a point P 1 on an elliptic curve; computing an integer u using m and P1.
Claim 22
Independent Claim
33 words
A system for creating a digital signature comprising: processing means for: generating a random integer m; computing a point P 1 on an elliptic curve; computing an integer u using m and P1.
Claim 23
Dependent Claim
17 words
The system of claim 19 wherein said elliptic curve has a starting point (X 1 , 1).
Claim 24
Dependent Claim
25 words
The system of claim 19 wherein P 1 is generated by m°(X 1 , 1) and P1 has coordinates (X 1 , Y 1 ).
Claim 25
Dependent Claim
30 words
The system of claim 19 wherein said integer u is generated by m+our Pri*M(ciphertext, P) where ciphertext is the encrypted message to be sent and M is a hash function.
Claim 26
Dependent Claim
21 words
The method of claim 22 further including sending the pair (u, P 1 ) as a digital signature to a receiver.
Claim 27
Dependent Claim
72 words
The system of claim 20 further including using said processing means to authenticate said digital signature wherein said processing means: generates a point Q having coordinates (X, Y) using u,; generates a point P 2 having coordinates (X 2 , Y 2 ) using P 1 ,; tests the equality P 1 +P 2 =Q; identifies a signature as not authentic when the equality P 1 +P 2 =Q is not satisfied.
Claim 28
Dependent Claim
24 words
The system of claim 24 wherein testing the equality P 1 +P 2 =Q; is performed without using Y 1 and Y 2 .
Claim 29
Dependent Claim
72 words
The system of claim 20 further including using said processing means to authenticate said digital signature wherein said processing means: generates a point Q having coordinates (X, Y) using u,; generates a point P 2 having coordinates (X 2 , Y 2 ) using P 1 ,; tests the equality P 1 +P 2 =Q; identifies a signature as not authentic when the equality P 1 +P 2 =Q is not satisfied.
Claim 30
Dependent Claim
25 words
The system of claim 26 wherein said testing the equality P 1 +P 2 =Q; is performed without using Y 1 and Y 2 .
References Cited (Backward Citations)
US5146500A
Cited
US5159632A
Cited
US5271061A
Cited
US5463690A
Cited
US5581616A
Cited
US5497423A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-09-07 | 2002-03-09 | 2002-09-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-09-07 | 2006-03-09 | 2006-09-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-09-07 | 2010-03-09 | 2010-09-08 | $7700.00 | Window Closed / Lapsed |