System and method for sequential data signatures
First Claim
Patent Images
1. A method for signing a digital message, comprising:
- computing a password sequence comprising a plurality of passwords such that each respective password corresponds to an index unit;
receiving the message;
submitting a current request to a signature server, said current request being computed as a first function of the message and a current one of the passwords; and
if the request is approved, receiving from the signature server a current time-stamp for the current request and forming a signature for the message to include at least the current time-stamp;
further comprising;
computing each of the plurality of passwords as a second function of a respective subsequent password, said sequence terminating with an initial password that forms a first public key verification parameter for the password sequence;
computing for the password sequence a verification hash tree comprising a plurality of leaf nodes and a single root node, such that the lowest-level leaf nodes include at least a subset of the passwords of the sequence in order, each node above the lowest-level nodes being computed as a hash of the values of two immediately lower-level nodes, and the uppermost node being the root node, which has a root hash value that forms a second public key verification parameter for the password sequence.
3 Assignments
0 Petitions
Accused Products
Abstract
A digital message is signed and, if a request is approved, receives a time stamp. The request is computed as a first function of the message and a current one of a sequence of passwords computed such that each password corresponds to an index unit. Each of the passwords may be computed as a function, such as a hash function, pseudo-random function, or encryption function, of the subsequent password, whereby the sequence terminates with an initial password that forms a public key parameter for the password sequence. At least one hash tree uses at least a subset of the passwords as inputs to a hash tree used to verify the passwords.
26 Citations
39 Claims
-
1. A method for signing a digital message, comprising:
-
computing a password sequence comprising a plurality of passwords such that each respective password corresponds to an index unit; receiving the message; submitting a current request to a signature server, said current request being computed as a first function of the message and a current one of the passwords; and if the request is approved, receiving from the signature server a current time-stamp for the current request and forming a signature for the message to include at least the current time-stamp; further comprising; computing each of the plurality of passwords as a second function of a respective subsequent password, said sequence terminating with an initial password that forms a first public key verification parameter for the password sequence; computing for the password sequence a verification hash tree comprising a plurality of leaf nodes and a single root node, such that the lowest-level leaf nodes include at least a subset of the passwords of the sequence in order, each node above the lowest-level nodes being computed as a hash of the values of two immediately lower-level nodes, and the uppermost node being the root node, which has a root hash value that forms a second public key verification parameter for the password sequence. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21)
-
-
22. A system for signing a digital message, comprising:
-
a processor; a memory; a password module comprising computer-executable code including instructions which, upon execution by the processor, cause the processor to compute a password sequence comprising a plurality of passwords such that each respective password corresponds to an index unit; to compute each of the plurality of passwords as a second function of a respective subsequent password, said sequence terminating with an initial password that forms a first public key parameter for the password sequence; and
to compute a current request as a first function of a message and a current one of the passwords;a certificate software module comprising computer-executable code including instructions which, upon execution by the processor, cause the processor to submit the current request to a signature server and, if the request is approved, to receive from the signature server a current time-stamp for the current request and forming a signature for the message to include at least the current time-stamp; a hash tree module comprising computer-executable code including instructions which, upon execution by the processor, cause the processor to compute for the password sequence a verification hash tree comprising a plurality of leaf nodes and a single root node, such that the lowest-level leaf nodes include at least a subset of the passwords of the sequence in order, each node above the lowest-level nodes being computed as a hash of the values of two immediately lower-level nodes, and the uppermost node being the root node, which has a root hash value that forms a second public key parameter for the password sequence. - View Dependent Claims (23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38)
the current password is valid if, as determined by backwards computation of the password sequence, it is in the correct index order relative to one of the subset of passwords in the password sequence that, used as input to a lowest level node of the verification hash tree, and given sibling node values in the verification hash tree, re-computes upward through the verification hash tree to the root hash value.
-
-
32. The system of claim 22, in which the password module is further configured to generate a public key certificate including a client ID, identifying a client entity that submits the request, and a server ID, identifying a signature server authorized to receive requests from the client entity;
- and
to include the client ID along with the request; and whereby the time stamp is received only if the public key certificate has not been revoked for a client entity identified by the client ID.
- and
-
33. The system of claim 32, in which the signature module is provided to include, in the signature, at least two of the values chosen from the group consisting of:
- the client ID, a position indicator indicating the position of the current password in the password sequence, the current password, re-computation parameters enabling re-computation of the root hash value from the current password, and the time-stamp.
-
34. The system of claim 22, in which the index units are non-temporal.
-
35. The system of claim 22, in which the index units are time units.
-
36. The system of claim 22, in which the current password, after the signature is formed, forms a self-revocation notice to the signature server such that the current password can no longer be used to request another signature.
-
37. The system of claim 22, in which:
-
the password sequence is divided into a plurality of validity time periods; for each time period, a respective secondary password sequence is generated; and a public key parameter of each secondary password sequence is signed using a respective one of the passwords in the password sequence.
-
-
38. The system of claim 37, in which the respective secondary password in the sequence is generated by applying a hash function recursively backwards from a respective final secondary password value until reaching an initial secondary password value.
-
39. A password generation system comprising:
-
a client server that includes a processor and a non-volatile memory, said client server communicating with a signature device and a signature server; said client server being configured to receive a message, to submit the message along with an index value to the signature device; to receive the request back from the signature device, said request being computed as a cryptographic function of the message and a password corresponding to the index value; said password further being computed as a function of a subsequent, password in a sequence, said sequence terminating with an initial password that forms a first public key parameter for the password sequence; and to submit the request to the signature server and, if the request is approved, to receive from the signature server a current time-stamp for the current request and to a signature for the message to include at least the current time-stamp; in which the client server is synchronized with the signature device to within a predetermined margin, said client server receiving from the signature device a hash chain corresponding to a hash tree computation path from at least a subset of the passwords to a verifying root value, said subset of passwords including previously used passwords and a current password, but only within a predetermined period relative to the submitted index value.
-
Specification