/**********************************************************************
* Copyright (c) 2017, Jochen Hoenicke *
* *
* Compile with: *
* gcc -O2 -I secp256k1/src/ -I secp256k1/ break_short.c -lgmp *
**********************************************************************/

#include "libsecp256k1-config.h"

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <time.h>

#include "include/secp256k1.h"
#include "secp256k1.c"

//#define  MEM_SIZE    31  //for 64GB
#define  MEM_SIZE    30  //for 32GB
//#define  MEM_SIZE    29  //for 16GB
//#define  MEM_SIZE    28  //for 8GB
#define  CHECK_BITS  90

/* giant steps are 2^25 */
#define GSTEP ((uint64_t)1<<MEM_SIZE)


#define NUMPUBKEYS  17
unsigned char rawpubkeys[NUMPUBKEYS][33] = {
{ 0x03,0x29,0xc4,0x57,0x4a,0x4f,0xd8,0xc8,0x10,0xb7,0xe4,0x2a,0x4b,0x39,0x88,0x82,0xb3,0x81,0xbc,0xd8,0x5e,0x40,0xc6,0x88,0x37,0x12,0x91,0x2d,0x16,0x7c,0x83,0xe7,0x3a },//== 1Kh22PvXERd2xpTQk3ur6pPEqFeckCJfAr#85
{ 0x03,0x5c,0x38,0xbd,0x9a,0xe4,0xb1,0x0e,0x8a,0x25,0x08,0x57,0x00,0x6f,0x3c,0xfd,0x98,0xab,0x15,0xa6,0x19,0x6d,0x9f,0x4d,0xfd,0x25,0xbc,0x7e,0xcc,0x77,0xd7,0x88,0xd5 },//== 1L12FHH2FHjvTviyanuiFVfmzCy46RRATU#90
{ 0x02,0x96,0x7a,0x59,0x05,0xd6,0xf3,0xb4,0x20,0x95,0x9a,0x02,0x78,0x9f,0x96,0xab,0x4c,0x32,0x23,0xa2,0xc4,0xd2,0x76,0x2f,0x81,0x7b,0x78,0x95,0xc5,0xbc,0x88,0xa0,0x45 },//== 19eVSDuizydXxhohGh8Ki9WY9KsHdSwoQC#95
{ 0x03,0xd2,0x06,0x3d,0x40,0x40,0x2f,0x03,0x0d,0x4c,0xc7,0x13,0x31,0x46,0x88,0x27,0xaa,0x41,0xa8,0xa0,0x9b,0xd6,0xfd,0x80,0x1b,0xa7,0x7f,0xb6,0x4f,0x8e,0x67,0xe6,0x17 },//== 1KCgMv8fo2TPBpddVi9jqmMmcne9uSNJ5F#100
{ 0x03,0xbc,0xf7,0xce,0x88,0x7f,0xfc,0xa5,0xe6,0x2c,0x9c,0xab,0xbd,0xb7,0xff,0xa7,0x1d,0xc1,0x83,0xc5,0x2c,0x04,0xff,0x4e,0xe5,0xee,0x82,0xe0,0xc5,0x5c,0x39,0xd7,0x7b },//== 1CMjscKB3QW7SDyQ4c3C3DEUHiHRhiZVib#105
{ 0x03,0x09,0x97,0x6b,0xa5,0x57,0x09,0x66,0xbf,0x88,0x91,0x96,0xb7,0xfd,0xf5,0xa0,0xf9,0xa1,0xe9,0xab,0x34,0x05,0x56,0xec,0x29,0xf8,0xbb,0x60,0x59,0x96,0x16,0x16,0x7d },//== 12JzYkkN76xkwvcPT6AWKZtGX6w2LAgsJg#110
{ 0x02,0x48,0xd3,0x13,0xb0,0x39,0x8d,0x49,0x23,0xcd,0xca,0x73,0xb8,0xcf,0xa6,0x53,0x2b,0x91,0xb9,0x67,0x03,0x90,0x2f,0xc8,0xb3,0x2f,0xd4,0x38,0xa3,0xb7,0xcd,0x7f,0x55 },//== 1NLbHuJebVwUZ1XqDjsAyfTRUPwDQbemfv#115
{ 0x02,0xce,0xb6,0xcb,0xbc,0xdb,0xdf,0x5e,0xf7,0x15,0x06,0x82,0x15,0x0f,0x4c,0xe2,0xc6,0xf4,0x80,0x7b,0x34,0x98,0x27,0xdc,0xdb,0xdd,0x1f,0x2e,0xfa,0x88,0x5a,0x26,0x30 },//== 17s2b9ksz5y7abUm92cHwG8jEPCzK3dLnT#120
{ 0x02,0x33,0x70,0x9e,0xb1,0x1e,0x0d,0x44,0x39,0xa7,0x29,0xf2,0x1c,0x2c,0x44,0x3d,0xed,0xb7,0x27,0x52,0x82,0x29,0x71,0x3f,0x00,0x65,0x72,0x1b,0xa8,0xfa,0x46,0xf0,0x0e },//== 1PXAyUB8ZoH3WD8n5zoAthYjN15yN5CVq5#125
{ 0x03,0x63,0x3c,0xbe,0x3e,0xc0,0x2b,0x94,0x01,0xc5,0xef,0xfa,0x14,0x4c,0x5b,0x4d,0x22,0xf8,0x79,0x40,0x25,0x96,0x34,0x85,0x8f,0xc7,0xe5,0x9b,0x1c,0x09,0x93,0x78,0x52 },//== 1Fo65aKq8s8iquMt6weF1rku1moWVEd5Ua#130
{ 0x02,0x14,0x5d,0x26,0x11,0xc8,0x23,0xa3,0x96,0xef,0x67,0x12,0xce,0x0f,0x71,0x2f,0x09,0xb9,0xb4,0xf3,0x13,0x5e,0x3e,0x0a,0xa3,0x23,0x0f,0xb9,0xb6,0xd0,0x8d,0x1e,0x16 },//== 16RGFo6hjq9ym6Pj7N5H7L1NR1rVPJyw2v#135
{ 0x03,0x1f,0x6a,0x33,0x2d,0x3c,0x5c,0x4f,0x2d,0xe2,0x37,0x8c,0x01,0x2f,0x42,0x9c,0xd1,0x09,0xba,0x07,0xd6,0x96,0x90,0xc6,0xc7,0x01,0xb6,0xbb,0x87,0x86,0x0d,0x66,0x40 },//== 1QKBaU6WAeycb3DbKbLBkX7vJiaS8r42Xo#140
{ 0x03,0xaf,0xdd,0xa4,0x97,0x36,0x9e,0x21,0x9a,0x2c,0x1c,0x36,0x99,0x54,0xa9,0x30,0xe4,0xd3,0x74,0x09,0x68,0xe5,0xe4,0x35,0x24,0x75,0xbc,0xff,0xce,0x31,0x40,0xda,0xe5 },//== 19GpszRNUej5yYqxXoLnbZWKew3KdVLkXg#145
{ 0x03,0x13,0x78,0x07,0x79,0x0e,0xa7,0xdc,0x6e,0x97,0x90,0x1c,0x2b,0xc8,0x74,0x11,0xf4,0x5e,0xd7,0x4a,0x56,0x29,0x31,0x5c,0x4e,0x4b,0x03,0xa0,0xa1,0x02,0x25,0x0c,0x49 },//== 1MUJSJYtGPVGkBCTqGspnxyHahpt5Te8jy#150
{ 0x03,0x5c,0xd1,0x85,0x4c,0xae,0x45,0x39,0x1c,0xa4,0xec,0x42,0x8c,0xc7,0xe6,0xc7,0xd9,0x98,0x44,0x24,0xb9,0x54,0x20,0x9a,0x8e,0xea,0x19,0x7b,0x9e,0x36,0x4c,0x05,0xf6 },//== 1AoeP37TmHdFh8uN72fu9AqgtLrUwcv2wJ#155
{ 0x02,0xe0,0xa8,0xb0,0x39,0x28,0x2f,0xaf,0x6f,0xe0,0xfd,0x76,0x9c,0xfb,0xc4,0xb6,0xb4,0xcf,0x87,0x58,0xba,0x68,0x22,0x0e,0xac,0x42,0x0e,0x32,0xb9,0x1d,0xdf,0xa6,0x73 },//== 1NBC8uXJy1GiJ6drkiZa1WuKn51ps7EPTv#160
{ 0x02,0x5f,0x86,0x4e,0x8c,0xa1,0xe1,0x5a,0x54,0x1e,0xfa,0x6a,0x65,0x9b,0x4a,0x6e,0xb1,0xe3,0xab,0x4a,0xe8,0xeb,0x80,0xcf,0x7f,0x0b,0xdc,0xad,0xfb,0x16,0x52,0x5b,0x18 },//== 1PvaqLqRAivje7CactLR55xQBYvBeaDrXN
};

typedef struct hashtable_entry {
    uint32_t x2;
    uint32_t x3;
    uint32_t exponent;
} hashtable_entry;

#define HASH_SIZE (2*GSTEP)
hashtable_entry table[HASH_SIZE];
secp256k1_ge pubkeys[NUMPUBKEYS];

int main(int argc, char **argv) {
    secp256k1_context *ctx = secp256k1_context_create(SECP256K1_CONTEXT_NONE);

    int next = 0;
    
    for (int i = 0; i < NUMPUBKEYS; i++) {
        if (!secp256k1_eckey_pubkey_parse(&pubkeys[i], rawpubkeys[i], 33)) {
            printf("Unparsable pubkey %2d\n", i);
            return -1;
        }
    }

    printf("Check bit = %d only, pubkey is:\n",CHECK_BITS);
    for(uint32_t i= 0;i<33;i++)
      printf("%02x",rawpubkeys[CHECK_BITS/5 - 17][i]);
    printf("\n");
      

    int shift_gmax;
    shift_gmax = CHECK_BITS - MEM_SIZE*2 -1;
    if(shift_gmax <0 ){
       printf("Error, CHECK_BITS too small =%d, should >= %d\n",CHECK_BITS, MEM_SIZE*2 +1);
       return 1;
    }

    unsigned int skip_bits;
    skip_bits = CHECK_BITS - MEM_SIZE -2;
    //printf("skip bits %d\n",skip_bits);

    uint64_t skip;
    uint64_t g_max;
    skip  = (uint64_t)0x1 << skip_bits;
    g_max = ((uint64_t)0x1 << shift_gmax)* (uint64_t)(GSTEP);
    //printf("skip %016lx gmax %016lx\n",skip,g_max);

    uint128_t rstart,rend;
    uint64_t start_hi,start_lo;
    uint64_t end_hi,end_lo;

    rstart   = (uint128_t)skip *(uint128_t)(HASH_SIZE);
    rend     = (uint128_t)g_max*(uint128_t)(HASH_SIZE)-1;
    start_lo = rstart;
    start_hi = rstart>>64;
    end_lo   = rend;
    end_hi   = rend>>64;

    uint64_t one_table_bytes;
    one_table_bytes = (uint64_t)&table[1] - (uint64_t)&table[0];

    printf("Build Hash, MEM size = %dGB\n", (uint32_t)(HASH_SIZE*one_table_bytes>>30));
    secp256k1_gej pt;
    secp256k1_gej_set_ge(&pt, &secp256k1_ge_const_g);
    for (uint64_t i = 1; i < GSTEP; i++) {
        secp256k1_fe x,zinv;
        secp256k1_fe_storage xst;

        secp256k1_fe_inv_var(&zinv, &pt.z);
        secp256k1_fe_sqr(&zinv, &zinv);
        secp256k1_fe_mul(&x, &pt.x, &zinv);
        secp256k1_fe_to_storage(&xst, &x);
        uint32_t entry = xst.n[0] & (HASH_SIZE-1);
        while (table[entry].exponent != 0) {
            entry = (entry + (xst.n[1] | 1)) & (HASH_SIZE - 1);
        }
        table[entry].exponent = i;
        table[entry].x2 = (uint32_t)xst.n[2];
        table[entry].x3 = (uint32_t)xst.n[3];
        secp256k1_gej_add_ge_var(&pt, &pt, &secp256k1_ge_const_g, NULL);
    }

    secp256k1_ge ptgstep;
    secp256k1_gej_neg(&pt, &pt);
    secp256k1_gej_double_var(&pt, &pt, NULL);


    secp256k1_ge_set_gej(&ptgstep, &pt);

    //secp256k1_gej_set_infinity(&pt);
    

    printf("Search bits = %d\n",CHECK_BITS);
    //skip some point by power of 2, we dont care 0 to start point
    //TODO update to random postion in a region
    for (uint64_t i = 0; i < skip_bits; i+=1) {
      secp256k1_gej_double_var(&pt, &pt, NULL);
    }

    printf("Search Keys....  from %lx%016lx to %lx%016lx\n",start_hi,start_lo, end_hi,end_lo);
    for (uint64_t i = skip; i < g_max; i++) {

//        for (int j = next; j < NUMPUBKEYS; j++) {
            secp256k1_gej diff;
            secp256k1_fe x,zinv;
            secp256k1_fe_storage xst;

            secp256k1_gej_add_ge_var(&diff, &pt, &pubkeys[CHECK_BITS/5 - 17], NULL);//check
            secp256k1_fe_inv_var(&zinv, &diff.z);
            secp256k1_fe_sqr(&zinv, &zinv);
            secp256k1_fe_mul(&x, &diff.x, &zinv);
            secp256k1_fe_to_storage(&xst, &x);


            uint32_t entry = xst.n[0] & (HASH_SIZE-1);
            while (table[entry].exponent != 0) {
                //if (table[entry].x == (uint32_t) xst.n[2]) {
                if ((table[entry].x2 == (uint32_t)xst.n[2]) && (table[entry].x3 == (uint32_t)xst.n[3])) {

                    uint128_t key = (uint128_t) i *  (uint128_t) (2 * GSTEP);

                    uint128_t key1 = key - table[entry].exponent ;
                    uint128_t key2 = key + table[entry].exponent;

   uint64_t key1lo = key1;
   uint64_t key1hi = (key1 >> 64);
   uint64_t key2lo = key2;
   uint64_t key2hi = (key2 >> 64);
                    printf("Found private key %2d: %lx%016lx or %lx%016lx\n", CHECK_BITS,  key1hi,key1lo,key2hi,key2lo);

                    FILE *fp = fopen("key.log","a+");
//                    fprintf(fp,"Found private, i=%16lx, x 2 x %16lx, exp=%x\n",(uint64_t)i,GSTEP,table[entry].exponent);
                    fprintf(fp,"Found private key %2d: %lx%016lx or %lx%016lx\n", CHECK_BITS,  key1hi,key1lo,key2hi,key2lo);
                    fclose(fp);
 
//                    next++;
                    //if (next == NUMPUBKEYS)
                        return 0;
                }        
                entry = (entry + (xst.n[1] | 1)) & (HASH_SIZE - 1);
            }
        /   if (j == next)
        /       break;
        //}
        //
        secp256k1_gej_add_ge_var(&pt, &pt, &ptgstep, NULL);
    }
    return 0;
}