String hashing using a number generator
In one embodiment, a mechanism for string hashing using a random number generator is disclosed. In one embodiment, a method includes dividing an input stream provided to a hashing module into a plurality of subsets of ‘n’ bits, entangling, by a mixer of the hashing module, one of the subsets of ‘n’ bits by a next sequential output of a pseudo-random number generator (PRNG), adding a product of the entangling to an accumulator of the hashing module, repeating the entangling and adding until all subsets of the plurality of subsets have been processed, and returning a value in the accumulator as a hash result value.
1. A method comprising:
dividing, by a hashing module executed by a processing device, an input stream into subsets of bits, wherein each subset comprises a same number of bits and wherein one or more of the subsets of bits of the input stream comprises an overlapping subset;
entangling, by a mixer of the hashing module, a subset of the subsets of bits by a next sequential output of a number generator, wherein the entangling comprises multiplication of the subset by the next sequential output of the number generator;
adding a product of the entangling to an accumulator of the hashing module;
deranging current data in the accumulator, the deranging comprising augmenting the current data to be non-linear by applying functions to the current data utilizing constant values;
repeating, by the hashing module, the entangling, the adding, and the deranging on at least a portion of a next sequential subset of the subsets of bits until all of the subsets of bits have been processed; and
when all of the subsets of bits have been processed, returning data in the accumulator as a hash result value.
2. The method of claim 1 , wherein deranging the data in the accumulator comprises multiplying the data in the accumulator by a first constant and adding a second constant to a product of the multiplying.
3. The method of claim 1 , wherein deranging the data in the accumulator comprises rotating the data in the accumulator by a predetermined amount and adding a first constant to a result of rotating the other data.
4. The method of claim 1 , wherein the multiplication is over at least one of a field of integers, a finite field, a group, or a ring.
5. A system, comprising:
a memory;
a processing device communicably coupled to the memory;
an input device communicably coupled to the memory and the processing device, the input device to receive a first sequence of bits;
a subset generator executable from the memory by the processing device, the subset generator to produce subsets of bits from the first sequence of bits, wherein each subset comprises a same number of bits and wherein one or more of the subsets of bits of the input stream comprises an overlapping subset;
a number generator communicably coupled to the subset generator to generate a plurality of random number outputs;
a mixer executable from the memory by the processing device, the mixer to entangle a subset of the subsets of bits from the subset generator with a next sequential output of the number generator, wherein the entangling comprises multiplication of the subset by the next sequential output of the number generator; and
an accumulator executable from the memory by the processing device, the accumulator to add a product of the entanglement received from the mixer to data stored in the accumulator in order to produce updated data;
a deranger to derange current data in the accumulator, the deranging comprising augmenting the current data to be non-linear by applying functions to the current data utilizing constant values;
wherein the mixer to repeat the entangling, the accumulator to repeat the adding, and the deranger to repeat the deranging on at least a portion of a next sequential subset of the subsets of bits until all of the subsets of bits have been processed.
6. The system of claim 5 , wherein the deranger to derange the data in the accumulator comprises the deranger multiplying the data in the accumulator by a first constant and adding a second constant to a product of the multiplying.
7. The system of claim 5 , wherein the deranger to derange the data in the accumulator comprises the deranger rotating the data in the accumulator by a predetermined amount and adding a first constant to a result of rotating the data.
8. The system of claim 5 , wherein the entangling comprises multiplication over at least one of the field of integers, a finite field, a group, or a ring.
9. A non-transitory machine-readable storage medium including instructions that, when accessed by a processing device, cause the processing device to perform operations comprising:
initializing, by a hashing module executed by the processing device, an accumulator with a non-zero value;
dividing an input stream into subsets of bits, wherein each subset comprises a same number of bits and wherein one or more of the subsets of bits of the input stream comprises an overlapping subset;
entangling, by a mixer of the hashing module, a subset of the subsets of bits by a next sequential output of a number generator, wherein the entangling comprises multiplication of the subset by the next sequential output of the number generator;
adding a product of the entangling to an accumulator of the hashing module;
deranging current data in the accumulator, the deranging comprising augmenting the current data to be non-linear by applying functions to the current data utilizing constant values;
repeating, by the hashing module, the entangling, the adding, and the deranging on at least a portion of a next sequential subset of the subsets of bits until all of the subsets of bits have been processed; and
when all of the subsets of bits have been processed, returning data in the accumulator as a hash result value.
10. The non-transitory machine-readable storage medium of claim 9 , wherein the deranging the data in the accumulator comprises multiplying the data in the accumulator by a first constant and adding a second constant to a product of the multiplying.
11. The non-transitory machine-readable storage medium of claim 9 , wherein the deranging the data in the accumulator comprises rotating the data in the accumulator by a predetermined amount and adding a first constant to a result of rotating the other data.
12. The non-transitory machine-readable storage medium of claim 9 , wherein the multiplication is over at least one of a field of integers, a finite field, a group, or a ring.
13. The method of claim 1 , wherein the number generator is a pseudo-random number generator (PRNG).
14. The system of claim 5 , wherein the number generator is a pseudo-random number generator (PRNG).
15. The non-transitory machine-readable storage medium of claim 9 , wherein the number generator is a pseudo-random number generator (PRNG).