2016/advent14.c

   1 #define _GNU_SOURCE 1
   2 #include <stdio.h>
   3 #include <string.h>
   4 #include <stdlib.h>
   5 #include <unistd.h>
   6 #include "md5.h"
   7
   8 char buf[1000][33];
   9
  10 void
  11 hash (const char *start, char *out)
  12 {
  13   unsigned char sum[16];
  14   int i, j;
  15   md5_buffer(start, strlen (start), sum);
  16   for (j = 0; j < 16; j++) {
  17     out[j * 2] = "0123456789abcdef"[sum[j] >> 4];
  18     out[j * 2 + 1] = "0123456789abcdef"[sum[j] & 0xf];
  19   }
  20   for (i = 0; i < 2016; i++) {
  21     md5_buffer(out, 32, sum);
  22     for (j = 0; j < 16; j++) {
  23       out[j * 2] = "0123456789abcdef"[sum[j] >> 4];
  24       out[j * 2 + 1] = "0123456789abcdef"[sum[j] & 0xf];
  25     }
  26   }
  27 }
  28
  29 int
  30 main (int argc, char **argv)
  31 {
  32   char *salt = "zpqevtbw";
  33   if (argc == 2)
  34     salt = argv[1];
  35   char str[] = "xxxxxxxx99999999";
  36   char *p = stpcpy (str, salt);
  37   int i, j;
  38   for (i = 0; i < 1000; i++) {
  39     sprintf (p, "%d", i);
  40     hash (str, buf[i]);
  41   }
  42   int keys = 0;
  43   i = 0;
  44   while (keys < 64) {
  45     char candidate[5] = "";
  46     for (j = 0; j < 32 - 2; j++)
  47       if (buf[i % 1000][j] == buf[i % 1000][j + 1] &&
  48           buf[i % 1000][j] == buf[i % 1000][j + 2]) {
  49         printf ("found a triple at index %d\n", i);
  50         memset (candidate, buf[i % 1000][j], 5);
  51         break;
  52       }
  53     sprintf (p, "%d", i + 1000);
  54     hash (str, buf[i % 1000]);
  55     i++;
  56     if (*candidate && memmem (buf, 33 * 1000, candidate, 5)) {
  57       printf ("candidate was a key\n");
  58       keys++;
  59     }
  60   }
  61   printf ("final index: %d\n", i - 1);
  62   return 0;
  63 }