Method and system for manipulating and telescoping a hash function

• US 6,928,162 B1
• Filed: 04/07/2000
• Issued: 08/09/2005
• Est. Priority Date: 04/07/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Jeffries, Clark Debs, Heddes, Marco C., Patel, Piyush Chunilal
• Primary Examiner(s): Morse, Gregory
• Assistant Examiner(s): Tran, Tongoc
• Application Number:
  US09/543,674
• Time in Patent Office: 1,950 Days
• Field of Search: 380/28, 380/46, 380/59, 380/217, 380/209, 713/154, 713/162, 713/167, 713/194, 713/190, 713/164, 370/392
• US Class Current: 380/28
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544

Abstract

A method and system for providing a hash and a complement of the hash for an item in a computer system are disclosed. The method and system include providing a plurality of components from the item. The plurality of components include a first component and a last component. Each of the plurality of components includes a particular number of bits. The method and system also include cascading the plurality of components through at least one XOR to provide a plurality of resultants. The plurality of resultants includes a first resultant and a final resultant. The final resultant includes only the last component. The first resultant includes an XOR of the first component and remaining cascaded components of the plurality of components. The method and system also include applying an invertible hash function and an invertible hash function complement to at least the first resultant to provide the hash. The complement of the hash includes the plurality of resultants except the first resultant. In another aspect, the method and system include applying the invertible hash function and its complement to at least the first component of the plurality of components, before the plurality of components are cascaded through the at least one XOR. In this aspect, the hash includes the first resultant. The complement of the hash includes the plurality of resultants except the first resultant.

Claims

1. A method for providing a hash and a complement of the hash for an item in a computer system, the method comprising the steps of:

(a) providing a plurality of components from the item, the plurality of components including a first component and a last component, each of the plurality of components includes a particular number of bits;

(b) cascading the plurality of components through at least one XOR to provide a plurality of resultants, the plurality of resultants including a first resultant and a final resultant, the final resultant including only the last component and the first resultant including an XOR of the first component and remaining cascaded components of the plurality of components; and

(c) applying an invertible hash function and an invertible hash function complement to at least the first resultant to provide the hash, the complement of the hash including the plurality of resultants except the first resultant.

2. The method of claim 1 wherein the invertible hash function is an invertible geometric hash function and the invertible hash function complement an invertible geometric hash function complement.

3. The method of claim 1 wherein each of the plurality of components includes thirty-two bits.

4. The method of claim 1 wherein the final component includes a plurality of bits used to pad the final component to the particular number of bits.

5. The method of claim 1 wherein the invertible hash function and the invertible hash function complement providing step (c) further includes the step of:

(c1) applying the invertible hash function and the invertible hash function complement to each of the plurality of resultants, the hash including the invertible hash function and the invertible hash function complement of the first resultant, the complement of the hash including the invertible hash function and the invertible hash function complement of each of the plurality of resultants except the first resultant.

6. The method of claim 1 further comprising the step of:

(d) providing a permutation of at least one component of the plurality of components.

37. The method of claim 2 wherein the invertible hash function applying step (c) further includes the steps of:

(c1) dividing the at least the first resultant into a plurality of subsets of equal length, the plurality of subsets including a first primary subset and a second primary subset;

(c2) selecting the first primary subset and the second primary subset of the plurality of subsets;

(c3) dividing a space defined by the first primary subset and the second primary subset into a plurality of regions including an origin region;

(c4) flipping the first primary subset and the second primary subset into the origin region;

(c5) concatenating a portion of the first primary subset and the second primary subset after flipping with most significant bits of a remaining portion of the plurality of subsets to provide the hash; and

(c6) determining the complement of the hash using the remaining portion of the plurality of subsets.

7. A method for providing a hash and a complement of the hash for an item in a computer system, the method comprising the steps of:

(a) providing a plurality of components from the item, the plurality of components including a first component and a last component, each of the plurality of components includes a particular number of bits;

(b) applying an invertible hash function and an invertible hash function complement to at least the first component of the plurality of components; and

(c) cascading the plurality of components after application of the hash function and the hash function complement through at least one XOR to provide a plurality of resultants, the plurality of resultants including a first resultant and a final resultant, the final resultant including only the last component and the first resultant including an XOR of the first component and remaining cascaded components of the plurality of components, the hash including the first resultant and the complement of the hash including the plurality of resultants except the first resultant.

8. The method of claim 7 wherein the invertible hash function is an invertible geometric hash function and the invertible hash function complement is an invertible geometric hash function complement.

9. The method of claim 7 wherein each of the plurality of components includes thirty-two bits.

10. The method of claim 7 wherein the final component includes a plurality of bits used to pad the final component to the particular number of bits.

11. The method of claim 7 wherein the invertible hash function and the invertible hash function complement providing step (b) further includes the step of:

(b1) applying the invertible hash function and the invertible hash function complement to each of the plurality of components.

12. The method of claim 7 further comprising the step of:

(d) providing a permutation of at least one component of the plurality of components.

38. The method of claim 8 wherein the invertible hash function applying step (b) further includes the steps of:

(b1) dividing the at least the first component into a plurality of subsets of equal length, the plurality of subsets including a first primary subset and a second primary subset;

(b2) selecting the first primary subset and the second primary subset of the plurality of subsets;

(b3) dividing a space defined by the first primary subset and the second primary subset into a plurality of regions including an origin region;

(b4) flipping the first primary subset and the second primary subset into the origin region;

(b5) concatenating a portion of the first primary subset and the second primary subset after flipping with most significant bits of a remaining portion of the plurality of subsets to provide the hash; and

(b6) determining the complement of the hash using the remaining portion of the plurality of subsets.

39. The computer-readable medium of claim 8 wherein the invertible hash function applying instructions (c) further includes instructions for:

(c1) dividing the at least the first resultant into a plurality of subsets of equal length, the plurality of subsets including a first primary subset and a second primary subset;

(c2) selecting the first primary subset and the second primary subset of the plurality of subsets;

(c3) dividing a space defined by the first primary subset and the second primary subset into a plurality of regions including an origin region;

(c4) flipping the first primary subset and the second primary subset into the origin region;

(c5) concatenating a portion of the first primary subset and the second primary subset after flipping with most significant bits of a remaining portion of the plurality of subsets to provide the hash; and

(c6) determining the complement of the hash using the remaining portion of the plurality of subsets.

13. A computer-readable medium containing a program for providing a hash and a complement of the hash for an item in a computer system, the program including instructions for:

(a) providing a plurality of components from the item, the plurality of components including a first component and a last component, each of the plurality of components includes a particular number of bits;

(b) cascading the plurality of components through at least one XOR to provide a plurality of resultants, the plurality of resultants including a first resultant and a final resultant, the final resultant including only the last component and the first resultant including an XOR of the first component and remaining cascaded components of the plurality of components; and

(c) applying an invertible hash function and an invertible hash function complement to at least the first resultant to provide the hash, the complement of the hash including the plurality of resultants except the first resultant.

14. The computer-readable medium of claim 13 wherein the invertible hash function is an invertible geometric hash function and the invertible hash function complement is an invertible geometric hash function complement.

15. The computer-readable medium of claim 13 wherein each of the plurality of components includes thirty-two bits.

16. The computer-readable medium of claim 13 wherein the final component includes a plurality of bits used to pad the final component to the particular number of bits.

17. The computer-readable medium of claim 13 wherein the invertible hash function and the invertible hash function complement providing instructions (c) further includes instructions for:

(c1) applying the invertible hash and the invertible hash function complement to each of the plurality of resultants, the hash including the invertible hash function and the invertible hash function complement of the first resultant, the complement of the hash including the invertible hash function and the invertible hash function complement of each of the plurality of resultants except the first resultant.

18. The computer-readable medium of claim 13 further comprising instructions for:

(d) providing a permutation of at least one component of the plurality of components.

19. A computer-readable medium for providing a hash and a complement of the hash for an item in a computer system, the program including instructions for:

(a) providing a plurality of components from the item, the plurality of components including a first component and a last component, each of the plurality of components includes a particular number of bits;

(b) applying an invertible hash function and an invertible hash function complement to at least the first component of the plurality of components;

(c) cascading the plurality of components after application of the hash function and the hash function complement through at least one XOR to provide a plurality of resultants, the plurality of resultants including a first resultant and a final resultant, the final resultant including only the last component and the first resultant including an XOR of the first component and remaining cascaded components of the plurality of components, the hash including the first resultant and the complement of the hash including the plurality of resultants except the first resultant.

20. The computer-readable medium of claim 19 wherein the invertible hash function is an invertible geometric hash function and the invertible hash function complement is an invertible geometric hash function complement.

21. The computer-readable medium of claim 19 wherein each of the plurality of components includes thirty-two bits.

22. The computer-readable medium of claim 19 wherein the final component includes a plurality of bits used to pad the final component to the particular number of bits.

23. The computer-readable medium of claim 19 wherein the invertible hash function and the invertible hash function complement providing instructions (b) further includes instructions for:

(b1) applying the invertible hash function and the invertible hash function complement to each of the plurality of components.

24. The computer-readable medium of claim 19 further comprising instructions for:

(e) providing a permutation of at least one component of the plurality of components.

40. The computer-readable medium of claim 20 wherein the invertible hash function applying instructions (b) further includes instructions for:

(b1) dividing the at least the first component into a plurality of subsets of equal length, the plurality of subsets including a first primary subset and a second primary subset;

(b2) selecting the first primary subset and the second primary subset of the plurality of subsets;

(b3) dividing a space defined by the first primary subset and the second primary subset into a plurality of regions including an origin region;

(b4) flipping the first primary subset and the second primary subset into the origin region;

(b5) concatenating a portion of the first primary subset and the second primary subset after flipping with most significant bits of a remaining portion of the plurality of subsets to provide the hash; and

(b6) determining the complement of the hash using the remaining portion of the plurality of subsets.

25. A system for providing a hash and a complement of the hash for an item in a computer system, the system comprising:

means for providing a plurality of components from the item, the plurality of components including a first component and a last component, each of the plurality of components includes a particular number of bits;

means for cascading the plurality of components through at least one XOR to provide a plurality of resultants, the plurality of resultants including a first resultant and a final resultant, the final resultant including only the last component and the first resultant including an XOR of the first component and remaining cascaded components of the plurality of components; and

means for applying an invertible hash function and an invertible hash function complement to at least the first resultant to provide the hash, the complement of the hash including the plurality of resultants except the first resultant.

26. The system of claim 25 wherein the invertible hash function is an invertible geometric hash function and the invertible hash function complement is an invertible geometric hash function complement.

27. The system of claim 25 wherein each of the plurality of components includes thirty-two bits.

28. The system of claim 25 wherein the final component includes a plurality of bits used to pad the final component to the particular number of bits.

29. The system of claim 25 wherein the invertible hash function providing means further includes:

means for applying the invertible hash function and the invertible hash function complement to each of the plurality of resultants, the hash including the invertible hash function and the invertible hash function complement of the first resultant, the complement hash including the invertible hash and the invertible hash function complement of each of the plurality of resultants except the first resultant.

30. The system of claim 25 further comprising:

means for providing a permutation of at least one component of the plurality of components.

41. The system of claim 26 wherein the invertible hash function applying means further divide the at least the first resultant into a plurality of subsets of equal length, the plurality of subsets including a first primary subset and a second primary subset;

select the first primary subset and the second primary subset of the plurality of subsets;

divide a space defined by the first primary subset and the second primary subset into a plurality of regions including an origin region;

flip the first primary subset and the second primary subset into the origin region;

concatenate a portion of the first primary subset and the second primary subset after flipping with most significant bits of a remaining portion of the plurality of subsets to provide the hash; and

determine the complement of the hash using the remaining portion of the plurality of subsets.

31. A system for providing a hash and a complement of the hash for an item in a computer system, the system comprising:

means for providing a plurality of components from the item, the plurality of components including a first component and a last component, each of the plurality of components includes a particular number of bits;

means for applying an invertible hash function and an invertible hash function complement to at least the first component of the plurality of components; and

means for cascading the plurality of components through at least one XOR after application of the hash function and the hash function complement to provide a plurality of resultants, the plurality of resultants including a first resultant and a final resultant, the final resultant including only the last component and the first resultant including an XOR of the first component and remaining cascaded components of the plurality of components, the hash including the first resultant and the complement of the hash including the plurality of resultants except the first resultant.

32. The system of claim 31 wherein the invertible hash function is an invertible geometric hash function and the invertible hash function complement is an invertible geometric hash function complement.

33. The system of claim 31 wherein each of the plurality of components includes thirty-two bits.

34. The system of claim 31 wherein the final component includes a plurality of bits used to pad the final component to the particular number of bits.

35. The system of claim 31 wherein the invertible hash function and the invertible hash function complement providing means further includes:

means for applying the invertible hash function and the invertible hash function complement to each of the plurality of components.

36. The system of claim 31 further comprising:

means for providing a permutation of at least one component of the plurality of components.

42. The system of claim 32 wherein the invertible hash function applying means further divide the at least the first component into a plurality of subsets of equal length, the plurality of subsets including a first primary subset and a second primary subset;

select the first primary subset and the second primary subset of the plurality of subsets;

divide a space defined by the first primary subset and the second primary subset into a plurality of regions including an origin region;

flip the first primary subset and the second primary subset into the origin region; and

concatenate a portion of the first primary subset and the second primary subset after flipping with most significant bits of a remaining portion of the plurality of subsets to provide the hash; and

determine the complement of the hash using the remaining portion of the plurality of subsets.