Verification protocol
First Claim
1. A method of verifying at a recipient a digital signature generated by a signor in a data communication system, said signature having a pair of signature components, one of said components incorporating first and second private keys with said first private key known to said recipient and signor and the other of said components having a value equivalent to a function associated with said second private key, said method of verifying comprising the steps of applying at said recipient said first of said private keys to said signature components to recover a value equivalent to said function associated with said second of said private keys and comparing said recovered value wit said other signature component to determine the authenticity of said signature.
1 Assignment
0 Petitions
Accused Products
Abstract
A digital signature verification protocol utilises a pair of signature components incorporating a pair of private keys, one of which is a long term key and the other of which is a short term key.
The long term key is applied to one of the signature components to reveal the short term key.
The short term key is then used to compute a value of a signature component contained in the signature. If the computed value and received values agree then authenticity is verified.
-
Citations
30 Claims
- 1. A method of verifying at a recipient a digital signature generated by a signor in a data communication system, said signature having a pair of signature components, one of said components incorporating first and second private keys with said first private key known to said recipient and signor and the other of said components having a value equivalent to a function associated with said second private key, said method of verifying comprising the steps of applying at said recipient said first of said private keys to said signature components to recover a value equivalent to said function associated with said second of said private keys and comparing said recovered value wit said other signature component to determine the authenticity of said signature.
-
8. A method of verifying a digital signature generated by a signor in a computer system, said signor having a private key d and a public key y, derived from an element g and said private key d said signature being generated by signing a message m in said computer system by:
-
a) generating a first signature component by combining at least said element g and a value k used by said signor as a short signature parameter according to a first mathematical function; and
b) generating a second signature component by mathematically combing said first signature component with said private key d;
said message m and said signature parameter k;
said method of verifying said digital signature comprising the steps of;
c) recovering a value k′
from said signature without using said public key y, and;
d) utilizing said recovered value k′
in said first mathematical function to derive a value r′
to verify said signature parameter k and k ′
are equivalent.- View Dependent Claims (9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
(a) calculating a value z=(h(m)+dr)mod q;
(b) calculating z−
1 inverting z mod q;
(c) calculating k′
−
1=s(z−
1) mod q; and
(d) calculating k′
by inverting k−
1 mod q.
-
-
15. A method as defined in claim 14, said step of verifying that said signature parameter k and said value k′
- are equivalent including tie steps of calculating r′
=gk′
mod p mod q and comparing r′
ro r in order to verify k=k′
.
- are equivalent including tie steps of calculating r′
-
16. A method as defined in claim 14 including utilizing precomputed tables in said calculations.
-
17. A method as defined in claim 10, said signature parameter k being a statistically unique and unpredictable integer k selected in an interval {2, n−
- 2} and said fist signature component having a form defined by r=x, mod n wherein x is a co-ordinate of a private key.
-
18. A method as defined in claim 17, including calculating a value e=h(m) wherein h is a hash function and said second signature component is given by s=k−
- 1(e+dr) mod n.
-
19. A method as defined in claim 18, wherein said step of recovering said value k′
- includes;
a) calculating a value z=(h(m)+dr) mod n;
b) calculating z−
1 by inverting z mod n;
c) calculating k′
−
1=s(z−
1) mod n, andd) calculating k′
by invert k−
1 mod n.
- includes;
-
20. A method as defined in claim 19, wherein said step of verifying that said signature parameter k and said k′
- are equivalent including the steps of calculating r′
=gk′
mod n and comparing r′
to r in order to verify k=k′
.
- are equivalent including the steps of calculating r′
-
21. A method as defined in claim 19, wherein said signature parameter k is a randomly selected integer in an interval, and said first signature component has a form defined by e=h(m r′
- );
wherein r=gk mod p, h is a hash function and denotes concatenation.
- );
-
22. A method as defined in claim 21, wherein said second signature component is defined by s=(de+k) mod p.
-
23. A method as defined in claim 22, wherein said step of recovering said value k′
- includes;
a) calculating a value k′
=(s−
de) mod p;
b) calculating a value r′
=gk mod p;
c) calculating a value e′
=h(m r′
); and
d) comparing said value e′
to e in order to verify k′
=k.
- includes;
- 24. A method of verifying the authenticity of a certificate issued by a certifying authority in an electronic data communication system, said method including the steps of said certifying authority including in said certificate a pair of signature components derived from a pair of private keys, said certifying authority retaining one of said private keys, said certifying authority receiving said certificate and applying said private key to said signature components to derive therefrom a value corresponding to a function of the other of said private keys and comparing said derived value with said function to determine the authenticity of said certificate.
- 29. A data communication system having a pair of correspondents connected by a data communication link, each of said correspondents having a cryptographic function to implement a public key cryptographic scheme utilising a pair of private keys, one of said private keys being utilised for multiple communications between said correspondents and the other of said private keys being generated by one of said correspondents at each communication, said one private key being shared by said correspondents to permit the other of said private keys to be recovered by said other correspondent from a digital signature generated by said one correspondent and compared to a signature component of said digital to verify the authenticity of said one correspondent.
Specification