Re: Don Knuth - Uncompressable sequences



On Mar 23, 8:46 am, Josiah Carlson <josiah.carl...@xxxxxxxxxxxxx>
wrote:
tan_st...@xxxxxxxxx wrote:
Algorithmically, is it not possible that there exists an oracle, that
given a sha or other hash of the input sequence, can predict or
reconstruct the original sequence regardless of the length of the
original sequence?

No. There only exists 2^160 sha1 hashes. Under the assumption that it
produces as few collisions as possible, you would only be able to
identify the 2^160 unique 20 byte files. Even if you specified the
length (and assuming that the sha1 hash was uniformly distributed), you
would have 256 possible matches for a 21 byte file with a particular
sha1 hash, 65536 for a 22 byte file, etc.

Despite what the internet says, Bruce Schneier does not see sha1 as an
invertible compression algorithm. :)

- Josiah

This makes me wonder... if the start point of the universe were
treated as a compressed string, then somehow there exists some
compression algorithm the universe is using that is causing that small
piece of information to expand constantly, into something that
obviously isn't just noise. While I understand the math behind why an
oracle could not magically map small numbers to all possible
combinations of strings greater than what the hash can represent, I
still must admit that I am confused by how, if evolution and the
theory of the universe is true, how so much expansion has been done
from possibly just one bit of information in the beginning.

Unless the universe were a program as big as itself. In which case,
who created that program and how big were they?

Can all this must mean only one thing... there must be a god, and the
theories of the universe are wrong?

I think I need to lay off the bong :)

.



Relevant Pages

  • Re: Don Knuth - Uncompressable sequences
    ... reconstruct the original sequence regardless of the length of the ... Even if you specified the length (and assuming that the sha1 hash was uniformly distributed), you would have 256 possible matches for a 21 byte file with a particular sha1 hash, 65536 for a 22 byte file, etc. ...
    (comp.compression)
  • Re: File Hashing
    ... Are you a programmer at all? ... definitely off-topic in the VB.NET newsgroup, ... Two different files will NEVER have the same hash value? ... SHA1 hash value? ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: The death of global warming
    ... The Universe is mostly devoid of substance and it takes up a LOT ... the next time you are in a hash den in Amsterdam. ... But you CAN read the English language, ...
    (alt.smokers.cigars)
  • Re: Is MD5 outdated ?
    ... > the same hash, ... That's a misunderstanding of the attack. ... Not in this universe. ... I found the half-life of a proton exceeds 10**33 ...
    (sci.crypt)
  • Re: API to access loaded assembly hash
    ... > same way as the strong name public key used in evidence. ... here is how to get the sha1 hash. ... >>> Dominick Baier - DevelopMentor ...
    (microsoft.public.dotnet.security)