Re: Had an idea - looking for a math buff to tell me if it's possible with today's technology.

[Brett Frankenberger <rbf+nanog () panix com>]

On Thu, May 19, 2011 at 12:26:26AM +0100, Heath Jones wrote:
> I wonder if this is possible:
>
> - Take a hash of the original file. Keep a counter.
> - Generate data in some sequential method on sender side (for example simply
> starting at 0 and iterating until you generate the same as the original
> data)
> - Each time you iterate, take the hash of the generated data. If it matches
> the hash of the original file, increment counter.
> - Send the hash and the counter value to recipient.
> - Recipient performs same sequential generation method, stopping when
> counter reached.
>
> Any thoughts?

That will work.  Of course, the CPU usage will be overwhelming --
longer than the age of the universe to do a large file -- but,
theoretically, with enough CPU power, it will work.

For a 8,000,000,000 bit file and a 128 bit hash, you will need a
counter of at least 7,999,999,872 bits to cover the number of possible
collisions.

So you will need at leat 7,999,999,872 + 128 = 8,000,000,000 bits to
send your 8,000,000,000 bit file.  If your goal is to reduce the number
of bits you send, this wouldn't be a good choice.

     -- Brett