System and method for generating unique secure values for digitally signing documents

• US 6,079,018 A
• Filed: 10/08/1997
• Issued: 06/20/2000
• Est. Priority Date: 10/08/1997
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Agorics Incorporated
• Inventors: Vetter, Linda L., Tribble, E. Dean, Hardy, Norman
• Primary Examiner(s): Swann, Tod R.
• Assistant Examiner(s): Smithers, Matthew
• Application Number:
  US08/947,375
• Time in Patent Office: 986 Days
• Field of Search: 380/30, 380/23, 380/46, 713/170, 713/176, 713/180, 713/181
• US Class Current: 713/170
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

A document is digitally signed with a digital signature that is unique to the signer/document pair. A document digest is generated by applying a predefined one-way hash function to the document. A pseudo-random key is generated by combining the document digest with at least one other value in accordance with a predefined computational procedure. The digital signature is then generated as a predefined function of the private key, the document digest, and the pseudo-random key k. A distinct pseudo-random key is generated for each distinct specified document, and for a given value of the private key, a distinct digital signature is generated for each distinct specified document. In a preferred embodiment the pseudo-random key generating step includes combining the document digest with a value corresponding to the private key to generate an intermediate value, and hashing the intermediate value with the predefined one-way hash function to generate the pseudo-random key k. In another preferred embodiment the pseudo-random key generating step includes hashing the private key with the predefined one-way hash function to generate a first intermediate value, combining the document digest with a value corresponding to the first intermediate value and an ancillary secret value to generate a second intermediate value, and hashing the second intermediate value with the predefined one-way hash function to generate the pseudo-random key k.

Claims

1. A method of digitally signing a specified document, comprising the steps of:

receiving a private key associated with a person or entity signing the document;

generating a digest of the specified document using a predefined one-way hash function;

generating a pseudo-random key, k, including combining the document digest with at least one other value in accordance with a predefined computational procedure; and

generating a digital signature for the specified document as a predefined function of the private key, the document digest, and the pseudo-random key k;

whereby

a distinct pseudo-random key is generated for each distinct specified document; and

for a given value of the private key, a distinct digital signature is generated for each distinct specified document.

2. The method of claim 1, wherein the predefined one-way hash function has the property that it generates distinct digest values for virtually all pairs of distinct documents.

3. A method of digitally signing a specified document, comprising the steps of:

receiving a private key associated with a person or entity signing the document;

generating a digest of the specified document using a predefined one-way hash function;

generating a pseudo-random key, k, including combining the document digest with a value corresponding to the private key to generate an intermediate value, and hashing the intermediate value with the predefined one-way hash function to generate the pseudo-random key k; and

generating a digital signature for the specified document as a predefined function of the private key, the document digest, and the pseudo-random key k;

whereby

a distinct pseudo-random key is generated for each distinct specified document; and

for a given value of the private key, a distinct digital signature is generated for each distinct specified document.

4. A method of digitally signing a specified document, comprising the steps of:

receiving a private key associated with a person or entity signing the document;

generating a digest of the specified document using a predefined one-way hash function;

generating a pseudo-random key, k, including;

hashing the private key with the predefined one-way hash function to generate a first intermediate value;

combining the document digest with a value corresponding to the first intermediate value and an ancillary secret value to generate a second intermediate value, and hashing the second intermediate value with the predefined one-way hash function to generate the pseudo-random key k; and

generating a digital signature for the specified document as a predefined function of the private key, the document digest, and the pseudo-random key k;

whereby

a distinct pseudo-random key is generated for each distinct specified document; and

for a given value of the private key, a distinct digital signature is generated for each distinct specified document.

5. A method of digitally signing a specified document, comprising the steps of:

receiving a private key associated with a person or entity signing the document;

generating a digest of the specified document using a predefined one-way hash function;

generating a pseudo-random key, k, including;

hashing the private key with the predefined one-way hash function to generate a first intermediate value;

combining the document digest with a value corresponding to the first intermediate value and an ancillary secret value to generate a second intermediate value;

hashing the second intermediate value with the predefined one-way hash function to generate a seed key value; and

performing a predefined pseudo-random key generation procedure, using the generated seed key value as an input thereto, to generate the pseudo-random key k; and

generating a digital signature for the specified document as a predefined function of the private key, the document digest, and the pseudo-random key k;

whereby

a distinct pseudo-random key is generated for each distinct specified document; and

for a given value of the private key, a distinct digital signature is generated for each distinct specified document.

6. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a one-way hash procedure for generating a digest of a specified document;

pseudo-random key generation instructions, including instructions for combining the document digest with at least one other value in accordance with a predefined computational methodology to generate a pseudo-random key k; and

digital signature generation instructions for generating a digital signature for the specified document as a predefined function of a private key, the document digest, and the pseudo-random key k;

wherein the private key is associated with a person or entity signing the specified document;

whereby

a distinct pseudo-random key is generated for each distinct specified document; and

for a given value of the private key, a distinct digital signature is generated for each distinct specified document.

7. The computer program product of claim 6, wherein the predefined one-way hash function has the property that it generates distinct digest values for virtually all pairs of distinct documents.

8. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a one-way hash procedure for generating a digest of a specified document;

pseudo-random key generation instructions, including instructions for combining the document digest with a value corresponding to the private key to generate an intermediate value, and hashing the intermediate value with the predefined one-way hash function to generate the pseudo-random key k; and

digital signature generation instructions for generating a digital signature for the specified document as a predefined function of a private key, the document digest, and the pseudo-random key k;

wherein the private key is associated with a person or entity signing the specified document;

whereby

a distinct pseudo-random key is generated for each distinct specified document; and

for a given value of the private key, a distinct digital signature is generated for each distinct specified document.

9. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a one-way hash procedure for generating a digest of a specified document;

pseudo-random key generating instructions, including instructions for;

hashing the private key with the predefined one-way hash function to generate a first intermediate value;

combining the document digest with a value corresponding to the first intermediate value and an ancillary secret value to generate a second intermediate value, and hashing the second intermediate value with the predefined one-way hash function to generate the pseudo-random key k; and

digital signature generation instructions for generating a digital signature for the specified document as a predefined function of a private key, the document digest, and the pseudo-random key k;

wherein the private key is associated with a person or entity signing the specified document;

whereby

a distinct pseudo-random key is generated for each distinct specified document; and

for a given value of the private key, a distinct digital signature is generated for each distinct specified document.

10. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium and a computer program mechanism embedded therein, the computer program mechanism comprising:

a one-way hash procedure for generating a digest of a specified document;

pseudo-random key generating instructions, including instructions for;

hashing the private key with the predefined one-way hash function to generate a first intermediate value;

combining the document digest with a value corresponding to the first intermediate value and an ancillary secret value to generate a second intermediate value;

hashing the second intermediate value with the predefined one-way hash function to generate a seed key value; and

performing a predefined pseudo-random key generation procedure, using the generated seed key value as an input thereto, to generate the pseudo-random key k; and

digital signature generation instructions for generating a digital signature for the specified document as a predefined function of a private key, the document digest, and the pseudo-random key k;

wherein the private key is associated with a person or entity signing the specified document;

whereby

a distinct pseudo-random key is generated for each distinct specified document; and

for a given value of the private key, a distinct digital signature is generated for each distinct specified document.

11. A system for digitally signing a specified document, comprising:

means for receiving a private key associated with a person or entity signing the document;

means for generating a digest of the specified document using a predefined one-way hash function;

means for generating a pseudo-random key, k, including combining the document digest with at least one other value in accordance with a predefined computational procedure; and

means for generating a digital signature for the specified document as a predefined function of the private key, the document digest, and the pseudo-random key k;

whereby

a distinct pseudo-random key is generated for each distinct specified document; and

for a given value of the private key, a distinct digital signature is generated for each distinct specified document.

12. The system of claim 11, wherein the predefined one-way hash function has the property that it generates distinct digest values for virtually all pairs of distinct documents.

13. A system for digitally signing a specified document, comprising:

means for receiving a private key associated with a person or entity signing the document;

means for generating a digest of the specified document using a predefined one-way hash function;

means for generating a pseudo-random key, k, including means for combining the document digest with a value corresponding to the private key to generate an intermediate value, and hashing the intermediate value with the predefined one-way hash function to generate the pseudo-random key k; and

means for generating a digital signature for the specified document as a predefined function of the private key, the document digest, and the pseudo-random key k;

whereby

a distinct pseudo-random key is generated for each distinct specified document; and

for a given value of the private key, a distinct digital signature is generated for each distinct specified document.

14. A system for digitally signing a specified document, comprising:

means for receiving a private key associated with a person or entity signing the document;

means for generating a digest of the specified document using a predefined one-way hash function;

means for generating a pseudo-random key, k, including means for hashing the private key with the predefined one-way hash function to generate a first intermediate value, and combining the document digest with a value corresponding to the first intermediate value and an ancillary secret value to generate a second intermediate value, and hashing the second intermediate value with the predefined one-way hash function to generate the pseudo-random key k; and

means for generating a digital signature for the specified document as a predefined function of the private key, the document digest, and the pseudo-random key k;

whereby

a distinct pseudo-random key is generated for each distinct specified document; and

for a given value of the private key, a distinct digital signature is generated for each distinct specified document.

15. A system for digitally signing a specified document, comprising:

means for receiving a private key associated with a person or entity signing the document;

means for generating a digest of the specified document using a predefined one-way hash function;

means for generating a pseudo-random key, k, including combining the document digest with at least one other value in accordance with a predefined computational procedure; and

means for generating a pseudo-random key, k, including means for;

hashing the private key with the predefined one-way hash function to generate a first intermediate value;

combining the document digest with a value corresponding to the first intermediate value and an ancillary secret value to generate a second intermediate value;

hashing the second intermediate value with the predefined one-way hash function to generate a seed key value; and

performing a predefined pseudo-random key generation procedure, using the generated seed key value as an input thereto, to generate the pseudo-random key k; and

means for generating a digital signature for the specified document as a predefined function of the private key, the document digest, and the pseudo-random key k;

whereby

a distinct pseudo-random key is generated for each distinct specified document; and

for a given value of the private key, a distinct digital signature is generated for each distinct specified document.