Patent US5600725A successfully refreshed from Google Patents.
US5600725A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Digital signature method and key agreement method
Assignee: Certicom Corp
•
Filing: 1994-08-17
•
Granted: 1997-02-04
•
Expires: 2014-08-17
Abstract
Abstract A digital signature method based on the discrete logarithm problem is provided that allows message recovery. The message x is transformed according to the rule e=x g -r mod p, where r is a secret value generated by the signer. A value y is then calculated according to the rule y=r+s e mod q, where y is the signer's secret key. The signature of x consists of the pair (e,y). The verifier recovers the message x according to the rule x=g y k e mod p, where k is the signer's public key. The validation of x can be based on some redundancy contained in x. Alternatively, a conventional verification equation can be constructed by using the signature method together with a hash function H. In addition, a key agreement method based on the signature method is provided which establishes with a single transmission pass a shared secret key K between two parties A and B in an authenticated fashion.
Inventors
- 👤 Rainer A. Rueppel
- 👤 Kaisa Nyberg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 13:32
CPC Classifications
H; H04; H04L; H04L9/00; H04L9/08; H04L9/0816; H04L9/0838; H04L9/0841; H04L9/0844; G; G07; G07F; G07F7/00; G07F7/08; G07F7/10; G07F7/1016; H04L9/30; H04L9/3006; H04L9/32; H04L9/3247; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724; G06F7/725
Claims Analysis
Total Claims: 38
Claim 1
Independent Claim
178 words
A method for generating a digital signature e, y, of a message x, comprising the steps of a) providing a secret and random value r; b) providing a public value g; c) providing an element u=g -r in a group G having a cyclic subgroup S of order p-1 and a cyclic subgroup T of the subgroup S of order q where q divides p-1; d) calculating the value e from said message x and said value u according to the rule e=f(G(x),u) wherein G(x) is a value derived from said message x and the function f is such that G(x) is able to be calculated from e and u using a function H(u -I ,e)=G(x); e) calculating said value y proceeding from a value a selected to be a divisor of p-1 according to the rule ar+bs+c=0 (mod q) where (a,b,c) is a permutation of the values e',y, l; and where e' is an integer and is derived from e and where s is a secret value; and f) transmitting said values e, y to a recipient.
Claim 2
Independent Claim
178 words
A method for generating a digital signature e, y, of a message x, comprising the steps of a) providing a secret and random value r; b) providing a public value g; c) providing an element u=g -r in a group G having a cyclic subgroup S of order p-1 and a cyclic subgroup T of the subgroup S of order q where q divides p-1; d) calculating the value e from said message x and said value u according to the rule e=f(G(x),u) wherein G(x) is a value derived from said message x and the function f is such that G(x) is able to be calculated from e and u using a function H(u -I ,e)=G(x); e) calculating said value y proceeding from a value a selected to be a divisor of p-1 according to the rule ar+bs+c=0 (mod q) where (a,b,c) is a permutation of the values e',y, l; and where e' is an integer and is derived from e and where s is a secret value; and f) transmitting said values e, y to a recipient.
Claim 3
Dependent Claim
24 words
A method according to claim 1 wherein a=1 and b=e' so that the value y is calculated according to the rule y=r+se' mod q.
Claim 4
Dependent Claim
24 words
A method according to claim 1 wherein G(x) is a hash value H(x) generated by applying a hash function H to said message x.
Claim 5
Dependent Claim
14 words
A method according to claim 1 wherein e' is a hash value of e.
Claim 6
Dependent Claim
27 words
A method according to claim 1 wherein both G(x) and u are represented as integers and e=G(x)·u (mod t), where t is an integer greater than G(x).
Claim 7
Dependent Claim
27 words
A method according to claim 5 wherein u represents a key for a symmetric encryption algorithm whereby e is the encryption of G(x) under the key u.
Claim 8
Dependent Claim
17 words
A method according to claim 6 wherein said symmetric encryption algorithm implements the data encryption standard (DES).
Claim 9
Dependent Claim
27 words
A method according to claim 5 wherein the group G is the set of non-zero elements in the integers mod p where p is a prime number.
Claim 10
Dependent Claim
17 words
A method according to claim 8 wherein the cyclic subgroup S and the group G are coterminous.
Claim 11
Dependent Claim
29 words
A method according to claim 9 wherein the value e=f(G(x),u) is given G(x)·u mod p, and the value h(u -1 ,e) is given by u -1 ·e mod p.
Claim 12
Dependent Claim
30 words
A method according to claim 9 wherein the value of e is given by G(x)+u mod p and the value h(u -1 , e) is given by e-u mod p.
Claim 13
Dependent Claim
31 words
A method according to claim 11 wherein the value e is given by G(x)• u and h(u -1 ,e) is given by e ⊕ u where ⊕ represents an XOR function.
Claim 14
Dependent Claim
11 words
A method according to claim 8 wherein G(x) corresponds to x.
Claim 15
Dependent Claim
27 words
A method according to claim 1 wherein the cyclic subgroup S is a subgroup of the group of points of an elliptic curve over a finite field.
Claim 16
Dependent Claim
17 words
A method according to claim 14 wherein both G(x) and u are points on the elliptic curve.
Claim 17
Dependent Claim
26 words
A method according to claim 15 wherein e is derived by multiplying G(x) and u in the group to provide an additional point on the curve.
Claim 18
Dependent Claim
51 words
A method according to claim 14 wherein u is a point on the curve represented by a pair of coordinates (a,b) where both a and b come from the underlying finite field and e is derived from multiplying G(x) with one of the coordinates a or b in the finite field.
Claim 19
Dependent Claim
25 words
A method according to claim 14 wherein the value e is given by XORing a binary representation of G(x) with a binary representation of u.
Claim 20
Independent Claim
274 words
A method of verifying a digital signature e,y of a message x which has been generated by a) providing a secret and random value r; b) providing a public value g; c) providing an element u=g -r in a group G having a cyclic subgroup S of order p-1 and a cyclic subgroup T of the subgroup S of order q where q divides p-l; d) calculating the value e from said message x and said value u according to the rule e=f (G(x)),u) wherein G(x) is a value derived from said message x and the function f is such that G(x) is able to be calculated from e and u using a function H(u -1 ,e)=G(x); and e) calculating said value y proceeding from a value q selected to be a divisor of p-1 according to the rule ar+bs+c=0 (mod q) where (a,b,c) is a permutation of the values e', y, l and where e' is an integer and is derived from e and where s is a secret value, said method verification comprising f) receiving said signature e,y; g) deriving e' from e; h) deriving the value b'=-a -I b (mod q); i) deriving the value c'=a -I b (mod q); j) deriving the inverse of the group G of the value u from the relationship u=lk b' g c' , where k=g -B and S is a secret value; k) reconstructing G(x) from u -1 and e according to the rule G(x)=h (u -I ,e); l) examining G(x) to verify the presence of a predetermined characteristic; and m) detecting the validity of the signature upon said predetermined characteristic not being found.
Claim 21
Independent Claim
274 words
A method of verifying a digital signature e,y of a message x which has been generated by a) providing a secret and random value r; b) providing a public value g; c) providing an element u=g -r in a group G having a cyclic subgroup S of order p-1 and a cyclic subgroup T of the subgroup S of order q where q divides p-l; d) calculating the value e from said message x and said value u according to the rule e=f (G(x)),u) wherein G(x) is a value derived from said message x and the function f is such that G(x) is able to be calculated from e and u using a function H(u -1 ,e)=G(x); and e) calculating said value y proceeding from a value q selected to be a divisor of p-1 according to the rule ar+bs+c=0 (mod q) where (a,b,c) is a permutation of the values e', y, l and where e' is an integer and is derived from e and where s is a secret value, said method verification comprising f) receiving said signature e,y; g) deriving e' from e; h) deriving the value b'=-a -I b (mod q); i) deriving the value c'=a -I b (mod q); j) deriving the inverse of the group G of the value u from the relationship u=lk b' g c' , where k=g -B and S is a secret value; k) reconstructing G(x) from u -1 and e according to the rule G(x)=h (u -I ,e); l) examining G(x) to verify the presence of a predetermined characteristic; and m) detecting the validity of the signature upon said predetermined characteristic not being found.
Claim 22
Dependent Claim
32 words
The method of claim 19 wherein the value of a=1 and b=e' so that y=r+se' (mod q) and the value of u is derived from the relationship u -1 =g y k.sup.•.spsp.l.
Claim 23
Dependent Claim
16 words
The method of claim 19 wherein said predetermined characteristic includes a redundancy in the message x.
Claim 24
Dependent Claim
10 words
The method of claim 20 wherein said redundancy is natural.
Claim 25
Dependent Claim
10 words
The method of claim 20 wherein said redundancy is inserted.
Claim 26
Dependent Claim
12 words
The method of claim 21 wherein G(x) corresponds to the message x.
Claim 27
Dependent Claim
38 words
The method of claim 19 wherein G(x) is a hash value H(x) computed by applying a hash function H to said message x and said predetermined characteristic is a value obtained by applying H to the message x.
Claim 28
Dependent Claim
27 words
The method according to claim 19 wherein the group G is a set of non-zero elements in the integers mod p where p is a prime number.
Claim 29
Dependent Claim
30 words
A method according to claim 26 wherein the value e=f(G(x),u) is given by G(x).u mod p and the value h(u -1 ,e) is given by u -1 ·e mod p.
Claim 30
Dependent Claim
29 words
A method according to claim 27 wherein the value of e is given by G(x)+u mod p and the value h(u -1 ,e) is given by e-u mod p.
Claim 31
Dependent Claim
44 words
A method according to claim 28 wherein the value e is given by XORing a binary representation of G(x) with a binary representation of u and h(u -1 ,e) is given by XORing a binary representation of e with a binary representation of u.
Claim 32
Dependent Claim
27 words
A method according to claim 29 wherein the cyclic subgroup S is a subgroup of a group of points of an elliptic curve over a finite field.
Claim 33
Independent Claim
371 words
A method for establishing a shared secret key K between two parties A and B comprising the steps of: a) providing t party A random integer R and calculating a message x by exponentiating a first public value to a power derived from R; b) providing for parties A and B respective keys k A ,k B derived from respective private keys S A , S B where k A =g -SA and where k B =g -AB ; c) generating a digital signature e, y of said message x by: i) providing a secret and random value r; (ii) providing an element u=g -r in a group G having a cyclic subgroup S of order p-1 and a cyclic subgroup T of the subgroup S of order q where q divides p-1; (iii) calculating the value e from said message x and said value u according to the rule e-f(G(x), u) wherein G(x) is a value derived from said message x and the function f is such that G(x) is able to be calculated from e and u using a function H(u -1 ,e)=G(x); and (iv) calculating said value y proceeding from a value q selected to be a divisor of p-1 according to the rule ar+bS A +c=0 (mod q) where (a,b,c) is a permutation of the values e',Y,l; where e' is an integer and is derived from e and S A is a secret value; (d) transmitting the signature e,y from A to B; (e) extracting the message x from the signature e,y by: (i) deriving e' from e; (ii) deriving the value b'=a -1 c (mod q); (iii) deriving the value c'=a -1 c (mod q); (iv) deriving the inverse in the group G of the value u from the relationship u=k A b' g c' ; (v) reconstructing G(x) from u -1 and e according to the rule G(x)=h(u -1 ,e), (f) generating at party B said shared secret key K by exponentiating the message x to a power derived from the private key S B ; and (g) generating at party A said shared secret key K by exponentiating to said power derived from R a second public value related to said first public value.
Claim 34
Independent Claim
371 words
A method for establishing a shared secret key K between two parties A and B comprising the steps of: a) providing t party A random integer R and calculating a message x by exponentiating a first public value to a power derived from R; b) providing for parties A and B respective keys k A ,k B derived from respective private keys S A , S B where k A =g -SA and where k B =g -AB ; c) generating a digital signature e, y of said message x by: i) providing a secret and random value r; (ii) providing an element u=g -r in a group G having a cyclic subgroup S of order p-1 and a cyclic subgroup T of the subgroup S of order q where q divides p-1; (iii) calculating the value e from said message x and said value u according to the rule e-f(G(x), u) wherein G(x) is a value derived from said message x and the function f is such that G(x) is able to be calculated from e and u using a function H(u -1 ,e)=G(x); and (iv) calculating said value y proceeding from a value q selected to be a divisor of p-1 according to the rule ar+bS A +c=0 (mod q) where (a,b,c) is a permutation of the values e',Y,l; where e' is an integer and is derived from e and S A is a secret value; (d) transmitting the signature e,y from A to B; (e) extracting the message x from the signature e,y by: (i) deriving e' from e; (ii) deriving the value b'=a -1 c (mod q); (iii) deriving the value c'=a -1 c (mod q); (iv) deriving the inverse in the group G of the value u from the relationship u=k A b' g c' ; (v) reconstructing G(x) from u -1 and e according to the rule G(x)=h(u -1 ,e), (f) generating at party B said shared secret key K by exponentiating the message x to a power derived from the private key S B ; and (g) generating at party A said shared secret key K by exponentiating to said power derived from R a second public value related to said first public value.
Claim 35
Dependent Claim
22 words
A method according to claim 31 wherein said first public value is g and said second public value is k B .
Claim 36
Dependent Claim
22 words
A method according to claim 32 wherein x is computed by exponentiating g to the power R such that x=g R .
Claim 37
Dependent Claim
24 words
A method according to claim 31 wherein said first public value is said public key k B and said second public value is g.
Claim 38
Dependent Claim
23 words
A method according to claim 34 wherein x is computed by exponentiating k B to the power R such that x=k B .
References Cited (Backward Citations)
US4991210A
Cited
US4996711A
Cited
US5199070A
Cited
US5146500A
Cited
US5299262A
Cited
US5442707A
Cited
US5299263A
Cited
US5406628A
Cited
US5347581A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-02-04 | 2000-08-05 | 2001-02-04 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-02-04 | 2004-08-05 | 2005-02-04 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-02-04 | 2008-08-05 | 2009-02-04 | $7700.00 | Window Closed / Lapsed |