Distributed fingerprints for information integrity verification

• US 5,530,757 A
• Filed: 06/28/1994
• Issued: 06/25/1996
• Est. Priority Date: 06/28/1994
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Krawczyk, Hugo M.
• Primary Examiner(s): Cain, David C.
• Application Number:
  US08/267,083
• Time in Patent Office: 728 Days
• Field of Search: 380/23, 380/25, 380/4, 380/49
• US Class Current: 713/188
• CPC Class Codes: H04L 2209/26 Testing cryptographic entity, e.g. testing integrity of encryption key or encryption algorithm
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

A method and apparatus for determining when a original document has been altered. With this invention the original information in the document is hashed using a one-way hash function. The hashed information is then encoded into a number of fingerprint pieces which are then transmitted to a number of locations. To verify the originality of the document a minimum number of fingerprint pieces are decoded and the purported genuine document is hashed using the one-way hash function. If the results of the latter hash equal the results of decoding the minimum number of fingerprint pieces, then the purported document is accepted as the genuine document.

Claims

1. A method of verifying the integrity of an original document having original information, said method comprising:

when initializing said original document for possible future verification;

a) hashing said original information into a fingerprint using a one-way hash function;

b) encoding said fingerprint into a plurality of original fingerprint pieces;

c) distributing said original fingerprint pieces to a plurality of locations with each of said locations receiving at least one of said original fingerprint pieces;

when verifying the integrity of a test document purported to be said an original document and having test information;

d) retrieving a first number of test fingerprint pieces purported to be said original fingerprint pieces from a plurality of said locations;

e) decoding at least a predetermined number of said first number of test fingerprint pieces into a first test fingerprint;

f) hashing said test information into a second test fingerprint using said hash function; and

g) comparing said first test fingerprint with said second test fingerprint and accepting said test document as being said genuine document if said first test fingerprint equals said second test fingerprint.

2. A method as recited in claim 1, wherein each of said locations is a memory location.

3. A method as recited in claim 1, wherein the encoding of said original fingerprint is an error correction encoding procedure.

11. A method as recited in claim 3, wherein the error correction encoding procedure is a replication code.

4. An apparatus for verifying the integrity of an original document having original information, said apparatus comprising:

for initializing said genuine document for possible future verification;

a) a hasher to hash said original information into a fingerprint using a one-way hash function;

b) an encoder to encode said fingerprint into a plurality of original fingerprint pieces;

c) a distributor to distribute said original fingerprint pieces to a plurality of locations with each of said locations receiving at least one of said original fingerprint pieces;

for verifying the integrity of a test document purported to be said genuine document and having said test information;

d) a retriever for retrieving a first number of test fingerprint pieces purported to be said original fingerprint pieces from a plurality of said locations;

e) a decoder for decoding at least a predetermined number of said first number of test fingerprint pieces into a first test fingerprint;

f) said hasher also hashing said test information into a second test fingerprint using said hash function;

g) a comparator to compare said first test fingerprint with said second test fingerprint and accepting said test document as being said genuine document if said first test fingerprint equals said second test fingerprint.

5. In a computer system having a plurality of servers and at least one user terminal electronically connected to said servers, a method of verifying the integrity of an original original having original information, comprising:

when initializing said original document for possible future verification;

a) hashing said original information into a fingerprint using a one-way hash function;

b) encoding said fingerprint into a plurality of original fingerprint pieces;

c) distributing said original fingerprint pieces to said servers with each of a number of said servers receiving at least one of said original fingerprint pieces;

when verifying the integrity of a test document purported to be said genuine document and having test information;

d) retrieving a first number of test fingerprint pieces purported to be said original fingerprint pieces from a plurality of said servers;

e) decoding at least a predetermined number of said first number of test fingerprint pieces into a first test fingerprint;

f) hashing said test information into a second test fingerprint using said hash function; and

g) comparing said first test fingerprint with said second test fingerprint and accepting said test document as being said genuine document if said first test fingerprint equals said second test fingerprint.

6. A method as recited in claim 5, wherein said original document is stored in a centralized memory of said server.

7. A method as recited in claim 5, wherein said document is a computer program.

8. A method as recited in claim 5, wherein said document is executable computer code.

9. A method as recited in claim 5, wherein said document is replicated and a number of copies of said document is stored into a number of said terminals of said computer system.

10. A method as recited in claim 5, wherein said document is partitioned into a number of partitions, each of which is stored in one of said terminals.