News for hackers. Stuff that matters.
Re:Shortest program to print "Never gonna give you up..." by blauwbilgorgel on Friday June 01, 2012 @09:04AM (#4053143)
Joke answer

  $h = "549d9635795ef37857e0b3dc02e52e53";
  $v = 0;
  while( $v == 0 ){
    $n = "";
    for( $i=0; $i<1943; $i++ ){
      $n .= chr(rand(0, 127));
    }
    if( md5($n) == $h ){
      echo $n;
      $v = 42;
    }
  }
By the time we have our answer (or a collision), we forgot what the question was.
Re:Shortest program to print "Never gonna give you up..." by btilly on Friday June 01, 2012 @01:04PM (#4054445)
It is only funny because it is true.

Change your loop to only loop while $v < 42, and then when the md5 matches, set $v to be the number of copies of "gonna" in the text. ( * ) Print the final string at the end.

If you had a good random generator then with very high probability this program would be correct, although it is unable to run in any reasonable time.

* There are exactly 42 copies of "gonna" in that text. Did God speaking through Douglas Adams subtly rickroll all of us?

Re:Shortest program to print "Never gonna give you up..." by christiangenco on Sunday June 03, 2012 @03:49AM (#4060315)
Could this not also theoretically colide with a string with the same hash and more than 42 occurrences of "gonna"? Better set the flag to `$v==42` just to be safe.
Re:Shortest program to print "Never gonna give you up..." by btilly on Sunday June 03, 2012 @02:08PM (#4061379)
The probability is overwhelmingly against there being another string of the same length and even 10 copies of "gonna".

The odds of another one with under 2k bytes and exactly 42 copies of "gonna" is a lot higher than having one with 43 copies of "gonna".

In a code golf competition, one character matters. Therefore the odds are that you should use "<" not "==" here.

Re:Shortest program to print "Never gonna give you up..." by krisoft on Friday June 01, 2012 @09:32AM (#4053256)
Is there a way to tell approximately how many 1943 character long string are expected to have the same md5 hash? A lot, or just a few? Or it's not possible to tell because of the properties of md5?

Sorry for all the silly questions, I'm curious, but my cryto knowledge is weak.

Re:Shortest program to print "Never gonna give you up..." by simcop2387 on Friday June 01, 2012 @09:48AM (#4053315)
Probably not truly possible to calculate. But if we can probably figure out a rough estimate.

Let's setup what is valid in the string and we can go from there.

  a-z | 26 characters
  A-Z | 26 characters again
  \x20| 1  character, space
  .,' | 3 characters for punctuation
  ()  | 2 characters
  \n  | 1 more character
Now these describe just a string that is very similar to the original pastebin (with a few extra characters). If we were to consider all possible 1943 byte strings it'd be fairly different.

So we've now got that we're looking at strings with 59 distinct characters in them. That means we can consider that it encodes log2[59^1943] bits of information, which comes out to 11429.975..., let's just call that 11430 bits. An md5sum contains 128bits, and we're after ones that match just the string we're after. We've already figured out that there should be 2^11430 possible 1943 character strings. So let's divide the possible choices by the number of possible md5sums and we can get a rough idea.

  (2^11430)/(2^128) => 2^(11430-128) => 2^11302
Throwing this in a calculator since I don't want to flood HN with a gigantic number, that comes out to about 1.74 * 10^3402 possible strings that will match the MD5.

This is just an approximation and I bet I made a mistake on the math somewhere.

Re:Shortest program to print "Never gonna give you up..." by Animus7 on Friday June 01, 2012 @12:57PM (#4054407)
Awesome, I wouldn't have thought of this.

But to pick nits, it could be argued that you're using md5 as a trial/error "compression algorithm" without including its source.

Re:Shortest program to print "Never gonna give you up..." by nthitz on Friday June 01, 2012 @11:14AM (#4053829)
Nice touch setting $v = 42