// Challenge: keygen THIS
// Andy Sloane <andy@a1k0n.net>
//
// Here's the code to a theoretical software license key check routine
// inside some theoretical commercial application.  Can you make a key
// generator for it?
//
// I'll even give you some working keys:
//
// 53CPY-EJ2FY-EJ1R9-YWB5B-E4HFG
// YABEU-89UT7-HUOSX-49Y4F-UR25C
// K9W8E-U6KB1-S8PGV-SR4XO-PA4JA

#include <stdio.h>
#include <stdlib.h>
#include "bn.h"

// Turn a key formatted e.g. "12345-ABCDE-FGHIJ-KLMNO-PQRST" into a
// 125-bit extended precision number
unsigned char xlat[256];
const char *codetable="123456789ABCDEFGHJKLMNOPRSTUVWXY";
void init_codetbl()
{
  memset(xlat,255,sizeof(xlat));
  for(int i=0;i<32;i++)
    xlat[(int)codetable[i]] = i;
  // to translate to canonical form: 0=Q=O, I=1, Z=2
  xlat[(int)'0'] = xlat[(int)'O'];
  xlat[(int)'Q'] = xlat[(int)'O'];
  xlat[(int)'I'] = xlat[(int)'1'];
  xlat[(int)'Z'] = xlat[(int)'2'];
}

ubint<4> decode(const char *code)
{
  int n=strlen(code);
  ubint<4> k(0);
  for(int i=n-1;i>=0;i--) {
    unsigned char c = code[i];
    unsigned x = xlat[(int)c];
    if(x == 255) continue;
    k=k*32+x;
  }
  return k;
}

int main(int argc, char **argv)
{
  if(argc<2) {
    printf("usage: %s <keycode>\n", argv[0]);
    return 0;
  }

  init_codetbl();

  // Initialize some magic numbers
  ubint<4> n,d,k,check_mod;
  n[0]=0x776f80c3; n[1]=0x9f46d28b; n[2]=0xf71b044b; n[3]=0x1086ceba;
  d[0]=0xa4856acf; d[1]=0x77f3c3aa; d[2]=0xf60149d3; d[3]=0x03580e8b;
  check_mod = n>>32;

  // Here's the math.
  k = decode(argv[1]);

  /* Thanks to LoneStar309 on reddit... */
  if(k > n) {
    printf("FAIL\n");
    return 0;
  }

  k = expmod(k, d, n);
  ubint<8> _k(k), keyidx;
  div(_k, check_mod, keyidx);

  // Here's the check.
  if(_k[0] == 12345678 && _k[1] == 0 && _k[2] == 0 && _k[3] == 0) {
    printf("ok %u\n", keyidx[0]);
  } else {
    printf("FAIL\n");
  }

  return 0;
}