Quote from: jpyao78 on June 21, 2019, 12:23:48 AM

I modified some code for catching bit90 with small memory
need someone to test Grin

Code:

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

#include "libsecp256k1-config.h"

#include
#include
#include

#include

#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<

#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;
}

sup@vm:~/Downloads$ ./break-short.exe
Check bit = 90 only, pubkey is:
035c38bd9ae4b10e8a250857006f3cfd98ab15a6196d9f4dfd25bc7ecc77d788d5
Build Hash, MEM size = 48GB

I have 64GB of RAM on the VM but is taking 48.
How long will take for building hash ?
The script can be used with more than 64 RAM?