Method and system for manipulating and telescoping a hash function

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
12Forward
Citations 
0
Petitions 
1
Assignment
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
26 Citations
View as Search Results
Reversible hashing for Esignature verification  
Patent #
US 7,882,358 B2
Filed 01/15/2007

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

System and method for balancing TCP/IP/workload of multiprocessor system based on hash buckets  
Patent #
US 7,694,009 B2
Filed 12/07/2005

Current Assignee
Apple Inc.

Sponsoring Entity
Novell Incorporated

SERVER SIDE REVERSIBLE HASH FOR TELEPHONEBASED LICENSING MECHANISM  
Patent #
US 20090006260A1
Filed 06/27/2007

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Technology Licensing LLC

Reversible Hashing for ESignature Verification  
Patent #
US 20080172560A1
Filed 01/15/2007

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Technology Licensing LLC

System and method for balancing TCP/IP/workload of multiprocessor system based on hash buckets  
Patent #
US 20060085554A1
Filed 12/07/2005

Current Assignee
Apple Inc.

Sponsoring Entity
Apple Inc.

Method and system for performing flow based hash transformation to generate hash pointers for a network device  
Patent #
US 7,085,271 B2
Filed 03/14/2002

Current Assignee
HewlettPackard Development Company L.P.

Sponsoring Entity
HewlettPackard Development Company L.P.

Method and system for performing a hash transformation to generate a hash pointer for an address input by using rotation  
Patent #
US 7,126,948 B2
Filed 03/21/2002

Current Assignee
HewlettPackard Development Company L.P.

Sponsoring Entity
HewlettPackard Development Company L.P.

Method and system for performing asymmetric address translation  
Patent #
US 7,136,385 B2
Filed 12/07/2001

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Method and system for performing asymmetric address translation  
Patent #
US 20030108055A1
Filed 12/07/2001

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Method and system for performing flow based hash transformation to generate hash pointers for a network device  
Patent #
US 20030174710A1
Filed 03/14/2002

Current Assignee
HewlettPackard Development Company L.P.

Sponsoring Entity
HewlettPackard Development Company L.P.

Method and system for performing a hash transformation to generate a hash pointer for an address input by using rotation  
Patent #
US 20030182448A1
Filed 03/21/2002

Current Assignee
HewlettPackard Development Company L.P.

Sponsoring Entity
HewlettPackard Development Company L.P.

Server side reversible hash for telephonebased licensing mechanism  
Patent #
US 8,266,062 B2
Filed 06/27/2007

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

Delayed removal of address mapping for terminated processes  
Patent #
US 6,047,362 A
Filed 11/08/1996

Current Assignee
Sun Microsystems Incorporated

Sponsoring Entity
Sun Microsystems Incorporated

System for managing cluster of network switches using IP address for commander switch and redirecting a managing request via forwarding an HTTP connection to an expansion switch  
Patent #
US 6,654,796 B1
Filed 10/07/1999

Current Assignee
Cisco Technology Incorporated

Sponsoring Entity
Cisco Technology Incorporated

Full match (FM) search algorithm implementation for a network processor  
Patent #
US 6,675,163 B1
Filed 04/06/2000

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Network address filter device  
Patent #
US 6,424,650 B1
Filed 02/09/1999

Current Assignee
HP Inc.

Sponsoring Entity
3Com Corporation

Modified computer motherboard security and identification system  
Patent #
US 6,463,537 B1
Filed 01/04/1999

Current Assignee
Coder Technologies Incorporated

Sponsoring Entity
Coder Technologies Incorporated

Method and apparatus for fragmenting messages for a wireless network using group sharing of reference numbers  
Patent #
US 6,185,208 B1
Filed 06/26/1998

Current Assignee
Unwired Planet LLC

Sponsoring Entity
Openwave Systems Incorporated

Hash equation for MAC addresses that supports cache entry tagging and virtual address tables  
Patent #
US 6,230,231 B1
Filed 03/19/1998

Current Assignee
HP Inc.

Sponsoring Entity
3Com Corporation

Method and system for creating a perfect hash using an offset table  
Patent #
US 6,014,733 A
Filed 06/05/1997

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

Optimization methods for the insertion, protection, and detection of digital watermarks in digitized data  
Patent #
US 5,889,868 A
Filed 07/02/1996

Current Assignee
Wistaria Trading Inc.

Sponsoring Entity
Wistaria Trading Inc.

High speed cache management unit for use in a bridge/router  
Patent #
US 5,978,951 A
Filed 09/11/1997

Current Assignee
Plectrum LLC

Sponsoring Entity
3Com Corporation

Method and apparatus for hashing addresses in a network switch  
Patent #
US 5,757,795 A
Filed 05/20/1996

Current Assignee
Hewlett Packard Enterprise Development LP

Sponsoring Entity
Compaq Computer Corporation

Twodimensional affineinvariant hashing defined over any twodimensional convex domain and producing uniformlydistributed hash keys  
Patent #
US 5,802,525 A
Filed 01/21/1997

Current Assignee
International Business Machines Corporation

Sponsoring Entity
International Business Machines Corporation

Addressing mechanism for multiple lookup tables  
Patent #
US 5,852,607 A
Filed 02/26/1997

Current Assignee
Cisco Technology Incorporated

Sponsoring Entity
Cisco Technology Incorporated

Automatic data generation for selftest of cryptographic hash algorithms in personal security devices  
Patent #
US 5,623,545 A
Filed 08/31/1995

Current Assignee
National Semiconductor Corporation

Sponsoring Entity
National Semiconductor Corporation

42 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.  View Dependent Claims (2, 3, 4, 5, 6, 37)
 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.  View Dependent Claims (8, 9, 10, 11, 12, 38, 39)
 13. A computerreadable 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.  View Dependent Claims (14, 15, 16, 17, 18)
 19. A computerreadable 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.  View Dependent Claims (20, 21, 22, 23, 24, 40)
 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.  View Dependent Claims (26, 27, 28, 29, 30, 41)
 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.  View Dependent Claims (32, 33, 34, 35, 36, 42)
1 Specification
The present invention is related to U.S. patent application Ser. No. 09/210,222 now U.S. Pat. No. 6,785,278 and entitled “SYSTEM, METHOD AND COMPUTER PROGRAM PRODUCTS FOR HASHING ADDRESS VALUES” (RA998056) and assigned to the assignee of the present invention.
The present invention relates to computer systems, and more particularly to a method and system for allowing an invertible hash function to be extended to components having a greater number of bits.
Hash functions are used throughout computer networks for many purposes. For example, in routing traffic between networks or through a particular network, the source and destination addresses of particular packets are utilized to determine how to route the packet. Similarly, when packets are transmitted through components of a network, such as a switch, all or part of the IP fivetuple (the source address, the destination address, the source port, the destination port and the protocol) may be used to classify the packet. Items, such as the IP fivetuple or the address of a packet, are often several bits to hundreds of bits in length. For example, the IP address is typically thirtytwo bits, while the IP fivetuple is typically one hundred and four bits in length. In order to improve the time taken to perform operations using these items and thus improve the efficiency of the network, a hash function is typically used. The hash of the item is shorter than the item and can be used to identify the item. For example, a thirtytwo bit address may be hashed to sixteen bits. This sixteen bit hash is then used by the network to identify the address and perform operations on the corresponding hash. Because the hash is shorthand, nickname for the item, these operations can typically be performed more rapidly, improving the efficiency of the network.
Although use of a hash improves the performance of the network, one of ordinary skill in the art will readily realize that there are problems inherent in using a hash. In particular, a hash function may map multiple items to the same hash. This phenomenon is known as a collision. When there is a collision, the item to which the hash corresponds must be capable of being uniquely determined. Typically, hash functions are not invertible. Thus, it generally cannot be determined from the hash to which of the items that collided the hash corresponds. In order to resolve the collision, therefore, the conventional network must search for original item. Such a search is time consuming and degrades performance of the network.
Furthermore, as discussed above, it may be desirable to employ a hash function on many different kinds of items having different lengths. For example, a hash for the source address for a particular packet as well as a hash for the IP fivetuple for the particular packet may be desired. In order to simplify the network, it would also be desirable for similar hash functions to be capable of providing hashes for items of different lengths.
Accordingly, what is needed is a system and method for providing a hash function which allows collisions to be more easily resolved and which can be telescoped, or expanded, so that the hash function can be used with items of different lengths. The present invention addresses such a need.
The present invention provides a method and system for providing a hash and a complement of the hash for an item in a computer system. The method and system comprise providing a plurality of components from the item. The plurality of components includes a first component and a last component. Each of the plurality of components includes a particular number of bits. In one aspect, the method and system comprise 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 comprise 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 comprise 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.
According to the system and method disclosed herein, the present invention provides an invertible hash that can be extended to items having larger numbers of bits.
The present invention relates to an improvement in computer systems. The following description is presented to enable one of ordinary skill in the art to make and use the invention and is provided in the context of a patent application and its requirements. Various modifications to the preferred embodiment will be readily apparent to those skilled in the art and the generic principles herein may be applied to other embodiments. Thus, the present invention is not intended to be limited to the embodiment shown, but is to be accorded the widest scope consistent with the principles and features described herein.
Copending U.S. patent application Ser. No. 09/210,222, and entitled “SYSTEM, METHOD AND COMPUTER PROGRAM PRODUCTS FOR HASHING ADDRESS VALUES” (RAL998056) and assigned to the assignee of the present invention also describes a hash function. Applicants hereby incorporate by reference the abovementioned copending patent application. The hash function described in the abovementioned copending application is an invertible, geometric hash function for use with an item having a particular number of bits, preferably thirtytwo bits. The hash function provides a hash and its complement. In the preferred embodiment described in the abovementioned copending application, the hash is sixteen bits and the complement is sixteen bits.
The hash and the complement together correspond uniquely to a particular item that is hashed. Thus, the hash function is invertible. In particular, the hash function ensures that if a collision does occur in the sixteen bit hash, then no collisions will occur in the complement. Thus, a search of the original item does not need to be commenced if there is a collision in the hash. Instead, the complement can be accessed and the collision resolved through the use of the complement. The hash function is considered to be geometric because the hash function can be considered to fold in a particular way lines in a scatter plot representing the item. The hash function also preferably exploits statistical properties of items being hashed so that fewer collisions occur in the sixteen bit hash. Thus, not only can collisions be resolved using the hash and its complement, but fewer collisions occur in the hash.
The address space defined by A and B is then subdivided into four quadrants, an origin region consisting of the seven bit region of the AB address space adjacent the origin of the (A,B) address space (the origin region), the seven bit address space where the most significant bits of A and B are both a logic “1” value (the diagonal region) and the two seven bit regions where the most significant bits of A and B are logic “1” and logic “0” and logic “0” and logic “1” respectively (the A adjacent region and the B adjacent region), via step 54. Addresses which fall into the diagonal address space are translated from the diagonal region to the origin region, via step 56. Such a translation in the present example may be accomplished by replacing the most significant bits of both A and B with logic “0” or truncating these address bits which translates an address in the diagonal region to the origin region.
The address values in the A adjacent region are “flipped” into the origin region, via step 58, as follows. The address values are first flipped into the origin region by mirroring the addresses around the boundary between the origin region and the A adjacent region to provide first mirrored values, second, by mirroring the first mirrored values around the diagonal line of combinations with A=B to provide respective second mirrored values and finally, by mirroring the second mirrored values about an axis parallel to the A axis and halfway form the A axis to the boundary between the origin region and the A region.
Such a triple flipping operation on the A region can also be expressed as follows. Any point in the A region has coordinates (0, A_{6}, . . . A_{0}, 1, B_{6}, . . . , B_{0}). The first flip yields (0, A_{6}, . . . A_{0}, 1, −B_{6}, . . . , −B_{0}) where “−” denotes bit reversal. The second diagonal flip then yields (0, −B_{6}, . . . −B_{0}, 0, A_{6}, . . . , A_{0}). The third flip then yields (0, −B_{6}, −B_{0}, 0, −A_{6}, . . . , −A_{0}). In the present example, the initial point is 8+8=16 bits, however, the same sequence of operations could be executed in any dimension. Furthermore, the goal is to map the A region into the origin region so that the horizontal bands of points become vertical bands of points. Other related sequences of geometric operations could have this same effect.
Similarly, a point in the B region of the form (1, A_{6}, . . . A_{0}, 0, B_{6}, . . . , B_{0}) is flipped three times to become (0, −B_{6}, . . . −B_{0}, 0, −A_{6}, . . . , −A_{0}) in the origin region. Thus, the sixteen bit (A,B) values are hashed to a fourteen bit value. More generally, 2n bits are hashed to 2(n−1) bits.
To return the fourteen bit hash value to a sixteen bit value (which would decrease the hash collisions), the MSB'"'"'s of A and B may be used to form the least significant bits of the sixteen bit hash value by XORing these values with the MSB bit values from the other segments C and D and then XORing that result with the XOR of lower order bits of C and D. In general, XORing bits is a good hash technique. This comes from the following fact. Suppose a fair coin and a biased coin are simultaneously flipped. Suppose the value of the fair coin is used to either keep or reverse the value of the biased coin. The final value of the biased coin is, therefore, random. Likewise, suppose the value of the biased coin is used to either keep or reverse the value of the fair coin. The final value of the fair coin is random.
Thus, the hash function of the abovementioned copending application improves upon simple XORing of bits in A.B.C.D by using a very first step mapping A,B values into a subset of A,B values which distributes initial scatter plots with bands and voids more uniformly in the subset (the above origin quadrant). After this condensation, XORing values in any standard way preserves the randomness of the scatter plot so obtained.
As described above, the result of the translation and “flipping” of the addresses from the three regions to the origin region is to reduce the sixteen bit value A.B to a fourteen bit value. These fourteen bits are then XORed with the seven least significant bits with respective ones of the remaining segments of the address C and D, via step 60. These fourteen bits may then be combined with the two bits derived from the MSB of A and B to provide a sixteen bit hash value for A.B.C.D. the XORing with the remaining bits further reduces collisions in that address values with the same A and B would have differing hash values based on the C and D XOR and, therefore, not collide. While a specific XORing example has been provided, the hash function of the abovementioned copending application should not be construed as limited to a specific XORing as other XORing operations may also be used which preserve the randomness of the initial operations of flipping of coordinate values which converts scatter plots which are more random.
Thus, a hash value may be provided which converts the vertical and horizontal bands of address in the A and B address space to a more compact cross pattern in the origin region of A and B. the inclusion of C and D further reduces the likelihood of a hash collision by incorporating all thirtytwo bits into the hash function. Furthermore, as is seen in
As a particular example of the hash function of the abovementioned copending application, the hash function H[n] and its complement H′[i] are listed below, where n and i are bit numbers thirty one through zero.
Where f=A[7] XOR B[7] and g=NOT f.
Although the abovementioned copending application functions well for its intended purpose, the hash function of the above mentioned copending application is preferably used with items having a particular number of bits. The hash function of the abovementioned copending application is preferably used with an item, such as an address, having thirtytwo bits. It may thus be difficult to apply the hash function of the abovementioned copending application to items having a larger number of bits. For example, it may be difficult to extend the hash function of the abovementioned copending application to an item that includes IP fivetuple, which contains 104 bits. Thus, it would be desirable to have an invertible hash function that can be used with items having variable numbers of bits.
The present invention provides a method and system for providing a hash and a complement of the hash for an item in a computer system. The method and system comprise providing a plurality of components from the item. The plurality of components includes a first component and a last component. Each of the plurality of components includes a particular number of bits. The method and system also comprise 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 comprise 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 comprise 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.
The present invention will be described in terms of particular hash functions However, one of ordinary skill in the art will readily recognize that this method and system will operate effectively for other hash functions. Furthermore, the present invention will be described in terms of a particular algorithm, however, one of ordinary skill in the art will readily recognize that the present invention can be used with other algorithms.
To more particularly illustrate the method and system in accordance with the present invention, refer now to
The components are then cascaded through a plurality of XORs to provide a plurality of resultants, via step 104. The components are cascaded as follows. The plurality of components includes a first component through a last component. The last component is passed unchanged (not passed through an XOR). The last component thus becomes the final resultant. In addition, the last component and is XORed with the second to the last component. In other words, each bit of the last component is XORed with a corresponding bit of the second to the last component. Thus, the first bit of the last component is XORed with the first bit of the second to the last component. The XOR of the last component and the second to the last component become the second to the last resultant. The second to the last resultant (the XOR of the last component and the second to the last component) is then XORed with the third to the last component to become the third to the last resultant. This cascading of the components through the XORs is continued through the first component. The first component is XORed with the second resultant (the XORs of previous components) to provide the first resultant. Thus, through the cascaded XORs, the first resultant depends upon each of the plurality of components.
An invertible hash function and its complement are then applied to at least the first resultant, via step 106. The invertible hash function and its complement are applied in step 106 because, as discussed with respect to the abovementioned copending patent application, the invertible hash function may require the complement to be invertible. Thus, applying the invertible hash function and the invertible hash function complement could be equivalent to applying a single hash function, assuming that the single hash function is invertible in and of itself. The hash function applied in step 106 is an invertible hash function because the hash function and its complement correspond uniquely to an item to which the invertible hash function and the complement are applied. In a preferred embodiment, the invertible hash function and the complement applied in step 106 are the invertible geometric hash and its complement described in the abovementioned copending application. Thus, in a preferred embodiment, the invertible hash and its complement applied in step 106 are H and H′, discussed above.
The hash in accordance with the present invention for the item results from the application of the invertible hash function and its complement to the first resultant. The complement of the hash in accordance with the present invention includes the remaining portion of the resultants, some of which the invertible hash function and its complement may have been applied to. Thus, if each component is thirtytwo bits in length, the hash is thirtytwo bits in length and the complement is n32 bits, where n is the number of bits in the plurality of components.
Referring back to
A plurality of components of equal length is provided from the item to be hashed, including the bits used for padding if any, via step 114. Each of the plurality of components is preferably thirtytwo bits in length. One or more of the components may then be permuted, via step 116. For example, suppose that one of the components includes subcomponents A.B.C.D, where each of A, B, C and D are eightbit addresses. This component could be permuted to B.C.D.A or any other of the total of twentyfour possible permutations of A, B, C and D. Permuting the subcomponents makes it more difficult to determine the original item from the hash function in accordance with the present invention. Thus, it becomes more difficult for an attacker to discern the correspondence between the hash and the original item, making the system more secure.
After the permuting step 116, the components are cascaded through a plurality of XORs to provide a plurality of resultants, via step 118. The components are cascaded as follows. The plurality of components includes a first component through a last component. The last component is passed unchanged (not passed through an XOR). The last component thus becomes the final resultant. In addition, the last component and is XORed with the second to the last component. In other words, each bit of the last component is XORed with a corresponding bit of the second to the last component. Thus, the first bit of the last component is XORed with the first bit of the second to the last component. The XOR of the last component and the second to the last component become the second to the last resultant. The second to the last resultant (the XOR of the last component and the second to the last component) is then XORed with the third to the last component to become the third to the last resultant. This cascading of the components through the XORs is continued through the first component. The first component is XORed with the second resultant (the XORs of previous components) to provide the first resultant. Thus, through the cascaded XORs, the first resultant depends upon each of the plurality of components.
An invertible hash function and its complement are then applied to at least the first resultant, via step 120. The invertible hash function and its complement are applied in step 120 because, as discussed with respect to the abovementioned copending patent application, the invertible hash function may require the complement to be invertible. Thus, applying the invertible hash function and the invertible hash function complement could be equivalent to applying a single hash function, assuming that the single hash function is invertible in and of itself. The hash function applied in step 120 is an invertible hash function because the hash function and its complement correspond uniquely to an item to which the invertible hash function and the complement are applied. In a preferred embodiment, the invertible hash function and the complement applied in step 120 are the invertible geometric hash and its complement described in the abovementioned copending application. Thus, in a preferred embodiment, the invertible hash and its complement applied in step 106 are H and H′, discussed above.
The hash in accordance with the present invention for the item results from the application of the invertible hash function and its complement to the first resultant. The complement of the hash in accordance with the present invention includes the remaining portion of the resultants, some of which the invertible hash function and its complement may have been applied to. Thus, if each component is thirtytwo bits in length, the hash is thirtytwo bits in length and the complement is n32 bits, where n is the number of bits in the plurality of components.
The methods 100 and 110, and the system 200 can easily be extended to a larger number of bits. This can be accomplished by adding one or more additional components. The additional components are also cascaded through the XORs to provide a different number of resultants and the invertible hash and its complement are applied to some number of the resultants, including at least the first resultant. Thus, the hash function in accordance with the present invention can be easily extended to a higher number of bits. The first resultant, to which the invertible hash function and its complement are applied, includes each of the components because of the cascaded XORs. As a result, the variability present in each of the components is included in the first resultant. In addition, as discussed above with respect to the abovementioned copending patent application, the XORs preserve the variability present in the components. Thus, the first resultant includes the variability of the item that is being hashed. In addition, the invertible hash function and its complement are applied to the first resultant to provide the hash in accordance with the present invention. Because of the cascaded XORs and the invertible hash function and its complement, the hash in accordance with the present invention of an item is less likely to collide with the hash in accordance with the present invention of another item. This is particularly true if the invertible hash function and its complement are the invertible geometric hash function and the complement described in the abovementioned copending application.
Furthermore, the complement of the hash in accordance with the present invention includes the remaining resultants, to some of which the invertible hash function and its complement may have been applied. The hash and the complement in accordance with the present invention are also invertible. Thus, there is a onetoone correspondence between the hash and the complement and the item which is being hashed. Thus, if there is a collision between the hash of one item and the hash of another item, it is guaranteed that there will be no collision in the complement for the item and the complement of the other item. Consequently, there will be no need to search for the original item if a collision occurs in the hash. Instead, the complement of the hash can be used.
An invertible hash function and its complement are then applied to at least the first component, via step 154. The invertible hash function and its complement are applied in step 154 because, as discussed with respect to the abovementioned copending patent application, the invertible hash function may require the complement to be invertible. Thus, applying the invertible hash function and the invertible hash function complement could be equivalent to applying a single hash function, assuming that the single hash function is invertible in and of itself. The hash function applied in step 154 is an invertible hash function because the hash function and its complement correspond uniquely to an item to which the invertible hash function and the complement are applied. In a preferred embodiment, the invertible hash function and the complement applied in step 154 are the invertible geometric hash and its complement described in the abovementioned copending application. Thus, in a preferred embodiment, the invertible hash and its complement applied in step 154 are H and H′, discussed above.
After the application of the invertible hash function and its complement, the components are then cascaded through a plurality of XORs to provide a plurality of resultants, via step 156. The components are cascaded as follows. The plurality of components includes a first component through a last component. After application of the invertible hash function and its complement (if applied to the last component), the last component is passed unchanged (not passed through an XOR). The last component thus becomes the final resultant. In addition, the last component and is XORed with the second to the last component, to which the invertible hash function and its complement may have been applied. In other words, each bit of the last component is XORed with a corresponding bit of the second to the last component. Thus, the first bit of the last component is XORed with the first bit of the second to the last component. The XOR of the last component and the second to the last component become the second to the last resultant. The second to the last resultant (the XOR of the last component and the second to the last component) is then XORed with the third to the last component, to which the invertible hash function and its complement may have been applied, thereby providing the third to the last resultant. This cascading of the components through the XORs is continued through the first component. The first component, to which the invertible hash function and its complement have been applied, is XORed with the second resultant (the XORs of previous components) to provide the first resultant. Thus, through the cascaded XORs, the first resultant depends upon each of the plurality of components.
The hash in accordance with the present invention for the item is the first resultant. The complement of the hash in accordance with the present invention includes the remaining portion of the resultants. Thus, if each component is thirtytwo bits in length, the hash is thirtytwo bits in length and the complement is n32 bits, where n is the number of bits in the plurality of components.
In the system 250, the invertible hash function h and its complement h′ are applied to each of the components using hash function providing means 260, 262, 264 and 266. However, nothing prevents the use of a different invertible hash function and its complement. In addition, nothing prevents applying the invertible hash function to fewer components, including only the first component X 252. In an alternate embodiment, a single means could be used to apply the invertible hash function and its complement to the components. In a preferred embodiment, the invertible geometric hash function H and its complement H′ of the abovementioned copending application are used. In a preferred embodiment, each of the hash function providing means 260, 262, 264 and 266 are depicted in FIG. 3. However, as depicted in
Referring back to
The hash in accordance with the present invention is the first resultant. Thus, the hash in accordance with the present invention is (h[W],h′[W]) XOR ((h[X],h′[X]) XOR ((h[Y],h′[Y]) XOR (h[Z],h′[Z]))). The complement of the hash in accordance with the present invention is the remaining resultants. Thus, the complement of the hash in accordance with the present invention is (h[X],h′[X]) XOR ((h[Y],h′[Y]) XOR (h[Z],h′[Z])), (h[Z],h′[Z]) XOR (h[Y],h′[Y]), h[Z], h′[Z].
A plurality of components of equal length is provided from the item to be hashed, including the bits used for padding if any, via step 164. Each of the plurality of components is preferably thirtytwo bits in length. One or more of the components may then be permuted, via step 166. For example, suppose that one of the components includes subcomponents A.B.C.D, where each of A, B, C and D are eightbit addresses. This component could be permuted to B.C.D.A or any other of the total of twentyfour possible permutations of A, B, C and D. Permuting the subcomponents makes it more difficult to determine the original item from the hash function in accordance with the present invention. Thus, it becomes more difficult for an attacker to discern the correspondence between the hash and the original item, making the system more secure.
After the permuting step 166, an invertible hash function and its complement are then applied to at least the first component, via step 168. The invertible hash function and its complement are applied in step 168 because, as discussed with respect to the abovementioned copending patent application, the invertible hash function may require the complement to be invertible. Thus, applying the invertible hash function and the invertible hash function complement could be equivalent to applying a single hash function, assuming that the single hash function is invertible in and of itself. The hash function applied in step 168 is an invertible hash function because the hash function and its complement correspond uniquely to an item to which the invertible hash function and the complement are applied. In a preferred embodiment, the invertible hash function and the complement applied in step 168 are the invertible geometric hash and its complement described in the abovementioned copending application. Thus, in a preferred embodiment, the invertible hash and its complement applied in step 168 are H and H′ of the abovementioned copending application, discussed above. However, as depicted in
After the application of the invertible hash function and its complement, the components are then cascaded through a plurality of XORs to provide a plurality of resultants, via step 170. The components are cascaded as follows. The plurality of components includes a first component through a last component. After application of the invertible hash function and its complement (if applied to the last component), the last component is passed unchanged (not passed through an XOR). The last component thus becomes the final resultant. In addition, the last component and is XORed with the second to the last component, to which the invertible hash function and its complement may have been applied. In other words, each bit of the last component is XORed with a corresponding bit of the second to the last component. Thus, the first bit of the last component is XORed with the first bit of the second to the last component. The XOR of the last component and the second to the last component become the second to the last resultant. The second to the last resultant (the XOR of the last component and the second to the last component) is then XORed with the third to the last component, to which the invertible hash function and its complement may have been applied, thereby providing the third to the last resultant. This cascading of the components through the XORs is continued through the first component. The first component, to which the invertible hash function and its complement have been applied, is. XORed with the second resultant (the XORs of previous components) to provide the first resultant. Thus, through the cascaded XORs, the first resultant depends upon each of the plurality of components.
The hash in accordance with the present invention for the item is the first resultant. The complement of the hash in accordance with the present invention includes the remaining portion of the resultants. Thus, if each component is thirtytwo bits in length, the hash is thirtytwo bits in length and the complement is n32 bits, where n is the number of bits in the plurality of components.
The methods 150 and 160, and the system 250 can easily be extended to a larger number of bits. This can be accomplished by adding one or more additional components. The additional components are also cascaded through the XORs to provide a different number of resultants. The invertible hash and its complement are applied to some number of the components, including at least the first component. Thus, the hash function in accordance with the present invention can be easily extended to a higher number of bits. The first resultant includes each of the components because of the cascaded XORs. As a result, the variability present in each of the components is included in the first resultant. In addition, as discussed above with respect to the abovementioned copending patent application, the XORs preserve the variability present in the components. Thus, the first resultant includes the variability of the item that is being hashed. In addition, the invertible hash function and its complement are applied to at least the first component. Because of the cascaded XORs and the invertible hash function and its complement, the hash in accordance with the present invention of an item is less likely to collide with the hash in accordance with the present invention of another item. This is particularly true if the invertible hash function and its complement are the invertible geometric hash function and the complement described in the abovementioned copending application.
Furthermore, the complement of the hash in accordance with the present invention includes the remaining resultants. The hash and the complement in accordance with the present invention are invertible. Thus, there is a onetoone correspondence between the hash and the complement and the item which is being hashed. Thus, if there is a collision between the hash of one item and the hash of another item, it is guaranteed that there will be no collision in the complement for the item and the complement of the other item. Consequently, there will be no need to search for distinguishing bits in the original item if a collision occurs in the hash. Instead, the complement of the hash can be used.
To more clearly indicate how the methods 100, 110, 150 and 106 and the system 200 and 250 can be extended to items having a different number of bits, refer to FIG. 9.
The system 300 includes means 301 for providing the plurality of components from the item. In the system 300, five components U 302, W 304, X 306, Y 308 and Z 310 are depicted. However, nothing prevents the use of another number of components. The components U 302, W 304, X 306, Y 308 and Z 310 are permuted by permutation blocks 312, 314, 316, 318 and 320, respectively. The permutation blocks 312, 314, 316, 318 and 320 need not provide the same permutation for each of the components U 302, W 304, X 306, Y 308 and Z 310, respectively. Furthermore, in an alternate embodiment, only some or none of the permutations blocks 302, 304, 306, 308 and 310 may be used. The permuted components U 302, W 304, X 306, Y 308 and Z 310 are then provided to a plurality XORs 322, 324, 326 and 328. Thus, the final permuted component, Z 310 is transmitted without XORing as well as being XORed with the component Y 308, using XOR 322. Thus, the permuted final component Z 310 can be considered to be the last, fifth resultant. The output of the XOR 322, (permuted Z) XOR (permuted Y), is the second to the last (the fourth) resultant. The output of the XOR 322 is also provided to the XOR 324. Another input to the XOR 324 is the permuted third component X 306. The output of the XOR 324 is a third resultant which is (permuted X) XOR ((permuted Y) XOR (permuted Z)). In addition, the output of the XOR 324 is provided as an input to the XOR 326. The other input of the XOR 326 is the permuted second component W 304. The output of the XOR 326 is the second resultant (permuted W) XOR ((permuted X) XOR ((permuted Y) XOR (permuted Z))). The second resultant and the permuted first component V 302 are provided to the input of the XOR 328. The output of the XOR 328 is the first resultant, (permuted V) XOR {(permuted W) XOR ((permuted X) XOR ((permuted Y) XOR (permuted Z)))}. In the system 300, the invertible hash function h and its complement h′ are applied to each of the resultants using hash function providing means 330, 332, 334, 336 and 338. However, nothing prevents the to use of a different invertible hash function and its complement. Note that in an alternate embodiment, a single means could be used to apply the invertible hash function and its complement to the resultants. In a preferred embodiment, the invertible geometric hash function H and its complement H′ are used. In a preferred embodiment, each of the hash function providing means 330, 332, 334, 336 and 338 are depicted in FIG. 3.
Referring back to
Thus, the method and system in accordance with the present invention can provide an hash and its complement that are invertible. Thus, there is a onetoone correspondence between the hash and its complement and the original item hashed. In other words, if there are collisions in the hash, there are guaranteed not to be collisions in the complement. Thus, collisions in the hash can be resolved using the complement, without searching for the original item. In addition, the hash and its complement can easily be extended to items having greater numbers of bits. Even if the items do not have a number of bits that can be evenly divided into the components, the items can be padded to the desired number of bits. Thus, the hash and its complement in accordance with the present invention are extendable to larger numbers of bits and invertible.
A method and system has been disclosed for providing a hash function which is invertible and can be used with keys having a variety of sizes. Software written according to the present invention is to be stored in some form of computerreadable medium, such as memory, CDROM or transmitted over a network, and executed by a processor. Consequently, a computerreadable medium is intended to include a computer readable signal which, for example, may be transmitted over a network. Although the present invention has been described in accordance with the embodiments shown, one of ordinary skill in the art will readily recognize that there could be variations to the embodiments and those variations would be within the spirit and scope of the present invention. Accordingly, many modifications may be made by one of ordinary skill in the art without departing from the spirit and scope of the appended claims.