Home › Blogs › garrett's blog ›

Project Euler Problem 59

garrett // Sep 11, 2009
//

Project Euler Problem 59 was actually a really nice change of pace. We're given a crypted chunk of data, told that it was produced using an XOR cypher with a three-character key consisting of characters a-z, that the plain-text is english-language, and that we should brute-force it.

Given that the plain-text is english-language, I was going to get fancy and use frequency analysis, but since I didn't have a pen or paper on my couch, I decided that I'd stick with the spirit of the problem and go ahead with a brute-force attack.

It would have taken longer to come up with an 'is this english-language?' heuristic to short-circuit a key than it would to use my brain and vim, so the solution takes awhile to come up with, but it's correct.

... and given that I've seen "Hackers" a thousand times, I probably should have just guessed the key. Oh well; read on for the code.

Oh, and yes, I could have folded the summation of the plain-text into the decryption function, but I forgot that's what the solution was going to be, so I just tacked it on at the end. Don't hate me.

usage: ./p59.pl < ciphertext > outfile

  1. #!/usr/bin/perl -w
  2.  
  3. my @cipher;
  4. my @keys = getKeys();
  5.  
  6. while ( <STDIN> ) {
  7.         @cipher = split( /,/, $_ );
  8. }
  9.  
  10. #
  11. # i don't feel like writing a heuristic to determine
  12. # if this is english language, as I have access to
  13. # vim
  14. #
  15. my $i = 0;
  16. foreach my $key ( @keys ) {
  17.         my $candidate = crack( $key );
  18.         printf("trying %d (sum %d)\n%s", $i, sum( $candidate ), $candidate );
  19.         $i++;
  20. }
  21.  
  22. #-------------------------------------------
  23. sub sum {
  24.         my $string = shift;
  25.         chomp($string);
  26.         my @arr = split( //, $string );
  27.         my $sum = 0;
  28.         foreach my $chr ( @arr ) {
  29.                 $sum += ord( $chr );
  30.         }
  31.         return $sum;
  32. }
  33.        
  34. #-------------------------------------------
  35. sub crack {
  36.         my $key = shift;
  37.         my $string;
  38.         for ( my $i = 0; $i < @cipher; $i++ ) {
  39.                 $string .= chr( $cipher[$i] ^ $key->[$i%3] );
  40.         }
  41.         $string .= "\n";
  42.         return $string;
  43. }
  44.  
  45. #-------------------------------------------
  46. # all possible permutations of a 3-character a-z key
  47. sub getKeys {
  48.         my @keys;
  49.         my $min = 97;  #ascii 'a'
  50.         my $max = 122; #ascii 'z'
  51.         for ( my $i = $min; $i <= $max; $i++ ) {
  52.                 for ( my $j = $min; $j <= $max; $j++ ) {
  53.                         for ( my $k = $min; $k <= $max; $k++ ) {
  54.                                 push @keys, [$i, $j, $k];
  55.                         }
  56.                 }
  57.         }
  58.         return @keys;
  59. }