Patent US6049610A successfully refreshed from Google Patents.
US6049610A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for digital signature authentication
Assignee: Next Software Inc
•
Filing: 1998-09-09
•
Granted: 2000-04-11
•
Expires: 2018-09-09
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-08 13:49
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: 20
Claim 1
Independent Claim
50 words
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.
Claim 2
Independent Claim
50 words
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.
Claim 3
Dependent Claim
27 words
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.
Claim 4
Dependent Claim
19 words
The method of claim 2 wherein the possibility of the existence of said second incorrect source is statistically insignificant.
Claim 5
Dependent Claim
27 words
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.
Claim 6
Dependent Claim
39 words
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 1 on an elliptic curve; computing an integer u using m and P1.
Claim 7
Dependent Claim
17 words
The method of claim 5 wherein said elliptic curve has a starting point (X 1 , 1).
Claim 8
Dependent Claim
29 words
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.
Claim 9
Dependent Claim
70 words
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 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 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
99 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 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.
Claim 12
Dependent Claim
99 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 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.
Claim 13
Dependent Claim
29 words
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.
Claim 14
Dependent Claim
21 words
The article of manufacture of claim 11 wherein the possibility of the existence of said second incorrect source is statistically insignificant.
Claim 15
Dependent Claim
29 words
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.
Claim 16
Dependent Claim
61 words
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 1 on an elliptic curve; computer readable program code configured to cause a computer to compute an integer it using m and P1.
Claim 17
Dependent Claim
19 words
The article of manufacture of claim 14 wherein said elliptic curve has a starting point (X 1 , 1).
Claim 18
Dependent Claim
31 words
The article of manufacture of claim 15 wherein said step of generating P 1 is accomplished by m°(X 1 , 1) and P1 has coordinates (X 1 , Y 1 ).
Claim 19
Dependent Claim
101 words
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 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 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 .
References Cited (Backward Citations)
US5581616A
Cited
US5805703A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-04-11 | 2003-10-11 | 2004-04-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-04-11 | 2007-10-11 | 2008-04-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-04-11 | 2011-10-11 | 2012-04-11 | $7700.00 | Window Closed / Lapsed |