/*
elliptic curve discrete logarithm cracker
breaks a ecdlp by pollard's rho algorithm

written by seth hardy, shardy@aculei.net

license-ish thing:
you can use this code if you give credit where credit is due.
I assume no responsibility for what happens if you use it, though.

*/  


#include <stdio.h>
#include <time.h>
#include "gmp.h"

#define BREAKPOINT 10000
#define MAXSIZE 100
#define FALSE 0
#define TRUE  1

struct ecc_pt {
  mpz_t x; mpz_t y;
  int infin;  };


void about(void);
void ecc_add(struct ecc_pt *, struct ecc_pt *, struct ecc_pt *, mpz_t *,
mpz_t *);

main(int argc,char *argv[]) {

  mpz_t a,b,p,n,h;
  mpz_t xi,ai,bi,x2i,a2i,b2i;
  mpz_t temp,temp2,count;
  struct ecc_pt *P,*Q,*R,*S;  

  int debug;
  int timing;
  int testing;

  unsigned long start,end,startrand;

  int loop;
  size_t size;

  char instr[MAXSIZE];

  debug = timing = FALSE;

  if (argc>1) { 
    if((strcmp(argv[1],"-h") == 0) || (strcmp(argv[1],"-H") == 0))
      about();
    for(testing=1;testing<argc;testing++) {
      if ((strcmp(argv[testing],"-d") == 0) || (strcmp(argv[testing],"-D")
        == 0)) debug = TRUE;
      if ((strcmp(argv[testing],"-t") == 0) || (strcmp(argv[testing],"-T")
        == 0)) timing = TRUE;
    }
  }
  

  srand(time(NULL));

  P = (struct ecc_pt *) malloc(sizeof(struct ecc_pt));
  Q = (struct ecc_pt *) malloc(sizeof(struct ecc_pt));
  R = (struct ecc_pt *) malloc(sizeof(struct ecc_pt));
  S = (struct ecc_pt *) malloc(sizeof(struct ecc_pt));
    
  mpz_init(a);
  mpz_init(b);
  mpz_init(p);
  mpz_init(n);
  mpz_init(h);
  mpz_init(P->x);
  mpz_init(P->y);
  mpz_init(Q->x);
  mpz_init(Q->y);
  mpz_init(R->x);
  mpz_init(R->y);
  mpz_init(S->x);
  mpz_init(S->y);
  P->infin = 0;
  Q->infin = 0;
  R->infin = 0;
  S->infin = 0;

  mpz_init(xi);
  mpz_init(ai);
  mpz_init(bi);
  mpz_init(x2i);
  mpz_init(a2i);
  mpz_init(b2i);
  mpz_init(temp);
  mpz_init(temp2);
  mpz_init(count);

  printf("\necc-crack starting...\n\n");
  printf("          a: ");
  scanf("%s",instr);
  if(debug) printf("%s scanned as a.\n",instr);
  mpz_set_str(a,instr,10);
  printf("           b: ");
  scanf("%s",instr);
  if(debug) printf("%s scanned as b.\n",instr);
  mpz_set_str(b,instr,10);
  printf("fin. field order p: ");
  scanf("%s",instr);
  if(debug) printf("%s scanned as p.\n",instr);
  mpz_set_str(p,instr,10);
  printf("          x-coord of P: ");
  scanf("%s",instr);
  if(debug) printf("%s scanned as xp.\n",instr);
  mpz_set_str(P->x,instr,10);
  printf("          y-coord of P: ");
  scanf("%s",instr);
  if(debug) printf("%s scanned as yp.\n",instr);
  mpz_set_str(P->y,instr,10);
  printf("          x-coord of Q: ");
  scanf("%s",instr);
  if(debug) printf("%s scanned as xq.\n",instr);
  mpz_set_str(Q->x,instr,10);
  printf("          y-coord of Q: ");
  scanf("%s",instr);
  if(debug) printf("%s scanned as xq.\n",instr);
  mpz_set_str(Q->y,instr,10);
  printf("  Group order n: ");
  scanf("%s",instr);
  if(debug) printf("%s scanned as n.\n",instr);
  mpz_set_str(n,instr,10);
  printf("\n");

  // Begin cracking!

  start = clock();
  size = mpz_size(n);
  testing = 1;

  mpz_set_ui(count,0);
 
  mpz_set(R->x,P->x);
  mpz_set(R->y,P->y);
  mpz_set(S->x,Q->x);
  mpz_set(S->y,Q->y);
 
  startrand = rand();
 
  for(end=2;end <= startrand;end++) {
    ecc_add(R,R,P,&a,&p);
  }   

  mpz_set_ui(ai,startrand);
  startrand = rand();

  for(end=2;end <= startrand;end++) {
    ecc_add(S,S,Q,&a,&p);
  }

  mpz_set_ui(bi,startrand);

  ecc_add(R,R,S,&a,&p);

  mpz_set(x2i,xi);
  mpz_set(a2i,ai);
  mpz_set(b2i,bi);

  do {
    if(debug) {
       printf("i = ");
       mpz_out_str(stdout,10,count);
       printf(": ");
       printf("(xi,ai,bi) = ");
       mpz_out_str(stdout,10,xi);
       printf(",");
       mpz_out_str(stdout,10,ai);
       printf(",");
       mpz_out_str(stdout,10,bi);
       printf(" -- (x2i,a2i,b2i) = ");
       mpz_out_str(stdout,10,x2i);
       printf(",");
       mpz_out_str(stdout,10,a2i);
       printf(",");
       mpz_out_str(stdout,10,b2i);
       printf("\n");

       if(testing > BREAKPOINT) {
         printf("Program breakpoint hit. Terminating...\n");
         return;
       }
    }

  mpz_add_ui(count,count,1);

  switch(mpz_mod_ui(temp,R->x,3))
  {
    case 0 : ecc_add(R,R,R,&a,&p);
             mpz_mul_ui(ai,ai,2);
             mpz_mul_ui(bi,bi,2);
             break;
    case 1 : ecc_add(R,R,Q,&a,&p);
             mpz_add_ui(bi,bi,1);
             break;
    case 2 : ecc_add(R,R,P,&a,&p);
             mpz_add_ui(ai,ai,1);
             break;
  }

  mpz_mod(ai,ai,n);
  mpz_mod(bi,bi,n);

  switch(mpz_mod_ui(temp,S->x,3))
  {
    case 0 : ecc_add(S,S,S,&a,&p);
             mpz_mul_ui(a2i,a2i,2);
             mpz_mul_ui(b2i,b2i,2);
             break;
    case 1 : ecc_add(S,S,Q,&a,&p);
             mpz_add_ui(b2i,b2i,1);
             break;
    case 2 : ecc_add(S,S,P,&a,&p);
             mpz_add_ui(a2i,a2i,1);
             break;
  }

		
  switch(mpz_mod_ui(temp,S->x,3))
  {
    case 0 : ecc_add(S,S,S,&a,&p);
             mpz_mul_ui(a2i,a2i,2);
             mpz_mul_ui(b2i,b2i,2);
             break;
    case 1 : ecc_add(S,S,Q,&a,&p);
             mpz_add_ui(b2i,b2i,1);
             break;
    case 2 : ecc_add(S,S,P,&a,&p);
             mpz_add_ui(a2i,a2i,1);
             break;
  }

  mpz_mod(a2i,a2i,n);
  mpz_mod(b2i,b2i,n);

  if(debug) testing++;	

  } while(mpz_cmp(R->x,S->x) != 0);
	
  if(debug) {
    printf("Collision found!\n");
    printf("Rx = ");
    mpz_out_str(stdout,10,xi);
    printf("   Sx = ");
    mpz_out_str(stdout,10,x2i);
    printf("\nai = ");
    mpz_out_str(stdout,10,ai);
    printf("   a2i = ");
    mpz_out_str(stdout,10,a2i);
    printf("\nbi = ");
    mpz_out_str(stdout,10,bi);
    printf("   b2i = ");
    mpz_out_str(stdout,10,b2i);
    printf("\n");
    }
	
  mpz_sub(temp,bi,b2i);
  mpz_mod(temp,temp,n);
	
  if(mpz_cmp_ui(temp,0) == 0) printf("Solution failed.\n");
  else {
    mpz_sub(temp2,a2i,ai);
    mpz_invert(temp,temp,n);
    mpz_mul(temp,temp,temp2);
    mpz_mod(temp,temp,n);
  }

  end = clock();

  printf("Solution for Elliptic Curve DLP: ");
  mpz_out_str(stdout,10,temp);
  printf("\nIterations: ");
  mpz_out_str(stdout,10,count);
  printf("\n");
  if(timing) 
    printf("Time taken (sec): %f\n",(float)(end-start)/1000000);

  mpz_clear(a);
  mpz_clear(b);
  mpz_clear(n);
  mpz_clear(p);

  mpz_clear(P->x);
  mpz_clear(P->y);
  mpz_clear(Q->x);
  mpz_clear(Q->y);
  mpz_clear(R->x);
  mpz_clear(R->y);
  mpz_clear(S->x);
  mpz_clear(S->y);
 
  free(P);
  free(Q);
  free(R);
  free(S);

  mpz_clear(xi);
  mpz_clear(x2i);
  mpz_clear(ai);
  mpz_clear(a2i);
  mpz_clear(bi);
  mpz_clear(b2i);
  mpz_clear(temp);
  mpz_clear(count);
  mpz_clear(temp2);

  printf("ecc-crack terminated successfully.\n\n");

  return;

}

void about(void) {

  printf("\n\necc-crack v1.0 -- Elliptic Curve Cryptography Cracker\n\n");
  printf("USAGE: ecc-crack [options]\n\n");
  printf("\t-d   Show debug information\n");
  printf("\t-t   Show timing information\n\n\n");
  exit(0);

}

void ecc_add(struct ecc_pt *R, struct ecc_pt *P, struct ecc_pt *Q, mpz_t
*a, mpz_t *p) {

  mpz_t etemp,lambda,etemp2;

  mpz_init(etemp);
  mpz_init(etemp2);
  mpz_init(lambda);

  /* printf("P->x: ");
  mpz_out_str(stdout,10,P->x);
  printf("\nP->y: ");
  mpz_out_str(stdout,10,P->y);
  printf("Q->x: ");
  mpz_out_str(stdout,10,Q->x);
  printf("\nQ->y: ");
  mpz_out_str(stdout,10,Q->y); */

  if(P->infin && Q->infin) {
    R->infin = TRUE;
    return;
  }

  mpz_add(etemp,P->y,Q->y);
  mpz_mod(etemp,etemp,*p);

  if(mpz_cmp_ui(etemp,0) == 0) {
    R->infin = TRUE;
    return;
  }

  if(P->infin && !Q->infin) {
    mpz_set(R->x,Q->x);
    mpz_set(R->y,Q->y);
    R->infin = FALSE;
    return;
  }

  if(!P->infin && Q->infin) {
    mpz_set(R->x,P->x);
    mpz_set(R->y,P->y);
    R->infin = FALSE;
    return;
  }

  if((mpz_cmp(P->x,Q->x) == 0) && (mpz_cmp(P->y,Q->y) == 0)) {
    mpz_mul(etemp,P->x,P->x);
    mpz_add(etemp2,etemp,etemp);
    mpz_add(etemp,etemp,etemp2);
    mpz_add(etemp,etemp,*a);
    mpz_add(etemp2,P->y,P->y);
    mpz_invert(etemp2,etemp2,*p);
    mpz_mul(lambda,etemp,etemp2);
    mpz_mul(etemp,lambda,lambda);
    mpz_add(etemp2,P->x,P->x);
    mpz_sub(R->x,etemp,etemp2);
    mpz_mod(R->x,R->x,*p);
    mpz_sub(etemp,P->x,R->x);
    mpz_mul(etemp,lambda,etemp);
    mpz_sub(R->y,etemp,P->y);
    mpz_mod(R->y,R->y,*p);
    R->infin = FALSE;
  }
  else {
    mpz_sub(etemp,Q->y,P->y);
    mpz_sub(etemp2,Q->x,P->x);
    mpz_invert(etemp2,etemp2,*p);
    mpz_mul(lambda,etemp,etemp2);
    mpz_mul(etemp,lambda,lambda);
    mpz_sub(etemp,etemp,P->x);
    mpz_sub(R->x,etemp,Q->x);
    mpz_mod(R->x,R->x,*p);
    mpz_sub(etemp,P->x,R->x);
    mpz_mul(etemp,lambda,etemp);
    mpz_sub(R->y,etemp,P->y);
    mpz_mod(R->y,R->y,*p);
    R->infin = FALSE;
  }

  mpz_clear(etemp);
  mpz_clear(etemp2);
  mpz_clear(lambda);

}