Last active
April 20, 2020 08:42
-
-
Save daedalus/630a63b00f063e24ad1eaf3d7e4cc0c8 to your computer and use it in GitHub Desktop.
Program to brute force private keys from public keys using the baby-step giant-step algorithm. Improved to use threads.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/*********************************************************************************************************** | |
* Copyright (c) 2017, Jochen Hoenicke | |
* Modified by: jpyao78 https://bitcointalk.org/index.php?topic=1306983.msg51542451#msg51542451 | |
* * | |
* Compile with: | |
* gcc -O2 -I secp256k1/src/ -I secp256k1/ break_short.c -lgmp | |
* gcc -O2 -I secp256k1/src/ -I secp256k1/ break-short.c -lgmp -lpthread -o break-short -mcmodel=large | |
***********************************************************************************************************/ | |
#include "libsecp256k1-config.h" | |
#include <stdio.h> | |
#include <stdlib.h> | |
#include <string.h> | |
#include <unistd.h> | |
#include <pthread.h> | |
#include "include/secp256k1.h" | |
#include "secp256k1.c" | |
#define TIME | |
#define EXPONENT64 | |
#ifdef TIME | |
#include <time.h> | |
#endif | |
#define NUMPUBKEYS 256 | |
static void secp256k1_fe_get_hex(char *r64, const secp256k1_fe *a) { | |
secp256k1_fe b; | |
int i; | |
unsigned char tmp[32]; | |
b = *a; | |
secp256k1_fe_normalize(&b); | |
secp256k1_fe_get_b32(tmp, &b); | |
for (i=0; i<32; i++) { | |
/* Hex character table. */ | |
static const char *c = "0123456789ABCDEF"; | |
r64[2*i] = c[(tmp[i] >> 4) & 0xF]; | |
r64[2*i+1] = c[(tmp[i]) & 0xF]; | |
} | |
} | |
static int secp256k1_fe_set_hex(secp256k1_fe *r, const char *a64) { | |
int i; | |
unsigned char tmp[32]; | |
/* Byte to hex value table. */ | |
static const int cvt[256] = {0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0, | |
0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0, | |
0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0, | |
0, 1, 2, 3, 4, 5, 6,7,8,9,0,0,0,0,0,0, | |
0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0, | |
0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0, | |
0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0, | |
0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0, | |
0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0, | |
0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0, | |
0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0, | |
0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0, | |
0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0, | |
0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0, | |
0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0, | |
0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0}; | |
for (i=0; i<32; i++) { | |
tmp[i] = (cvt[(unsigned char)a64[2*i]] << 4) + cvt[(unsigned char)a64[2*i+1]]; | |
} | |
return secp256k1_fe_set_b32(r, tmp); | |
} | |
typedef struct hashtable_entry { | |
uint32_t x2; | |
uint32_t x3; | |
#ifndef EXPONENT64 | |
uint32_t exponent; | |
#else | |
uint64_t exponent; | |
#endif | |
} hashtable_entry; | |
hashtable_entry *table; | |
secp256k1_ge *pubkeys; | |
#ifdef TIME | |
time_t time1, time2; | |
#endif | |
uint64_t skip, g_max; | |
secp256k1_gej pt; | |
secp256k1_ge ptgstep; | |
secp256k1_ge P[256]; | |
uint64_t GSTEP, HASH_SIZE; | |
unsigned int MEM_SIZE, CHECK_BITS, THREADS; | |
int DEBUG = 0; | |
uint64_t *status; | |
void *memoryInit(void *z); | |
void *searchKeys(void *z); | |
// Copy gej element | |
static void secp256k1_gej_copy(secp256k1_gej *r, secp256k1_gej *a) { | |
r->infinity = a->infinity; | |
r->x = a->x; | |
r->y = a->y; | |
r->z = a->z; | |
} | |
void usage(unsigned char *name) { | |
printf("Usage: %s -b [BITS] -m [BITS] [OPTION]...\n\n\ | |
-m BITS memory size\n\ | |
31 for 48GB\n\ | |
30 for 24GB\n\ | |
29 for 12GB\n\ | |
28 for 6GB\n\ | |
-b BITS bits\n\ | |
-t THREADS number of threads\n\ | |
-d debug\n\ | |
-h show this help\n", name); | |
exit(1); | |
} | |
char *bin2hex(unsigned char *p, int len) | |
{ | |
char *hex = malloc(((2*len) + 1)); | |
char *r = hex; | |
while(len && p) | |
{ | |
(*r) = ((*p) & 0xF0) >> 4; | |
(*r) = ((*r) <= 9 ? '0' + (*r) : 'A' - 10 + (*r)); | |
r++; | |
(*r) = ((*p) & 0x0F); | |
(*r) = ((*r) <= 9 ? '0' + (*r) : 'A' - 10 + (*r)); | |
r++; | |
p++; | |
len--; | |
} | |
*r = '\0'; | |
return hex; | |
} | |
unsigned char *hex2bin(const char *str) | |
{ | |
int len, h; | |
unsigned char *result, *err, *p, c; | |
err = malloc(1); | |
*err = 0; | |
/*if (!str) | |
printf("hex2bin input error\n"); | |
return err; | |
if (!*str) | |
printf("hex2bin input error\n"); | |
return err; | |
*/ | |
len = 0; | |
p = (unsigned char*) str; | |
while (*p++) | |
len++; | |
result = malloc((len/2)+1); | |
h = !(len%2) * 4; | |
p = result; | |
*p = 0; | |
c = *str; | |
while(c) | |
{ | |
if(('0' <= c) && (c <= '9')) | |
*p += (c - '0') << h; | |
else if(('A' <= c) && (c <= 'F')) | |
*p += (c - 'A' + 10) << h; | |
else if(('a' <= c) && (c <= 'f')) | |
*p += (c - 'a' + 10) << h; | |
else | |
{ | |
return err; | |
} | |
str++; | |
c = *str; | |
if (h) | |
h = 0; | |
else | |
{ | |
h = 4; | |
p++; | |
*p = 0; | |
} | |
} | |
return result; | |
} | |
int main(int argc, char **argv) { | |
int c; | |
while ((c = getopt(argc, argv, "hdt:b:m:")) != -1) { | |
switch (c) { | |
case 'b': | |
CHECK_BITS = atoi(optarg); | |
break; | |
case 'm': | |
MEM_SIZE = atoi(optarg); | |
break; | |
case 't': | |
THREADS = atoi(optarg); | |
break; | |
case 'd': | |
DEBUG++; | |
break; | |
case 'h': | |
usage(argv[0]); | |
return 0; | |
default: | |
return 1; | |
} | |
} | |
if(!THREADS) THREADS = 1; | |
status = malloc((uint64_t) THREADS*sizeof(status)); | |
/*if(!CHECK_BITS) { | |
fprintf(stderr,"Number of bits not defined\n"); | |
usage(argv[0]); | |
exit(1); | |
} else if(CHECK_BITS<1 || CHECK_BITS>NUMPUBKEYS) { | |
fprintf(stderr,"Number of bits not valid\n"); | |
exit(1); | |
}*/ | |
secp256k1_ge *pubkeys = malloc(sizeof(secp256k1_ge)); | |
if(!MEM_SIZE) { | |
fprintf(stderr,"Memory bits not defined\n"); | |
usage(argv[0]); | |
exit(1); | |
#ifndef EXPONENT64 | |
} else if(MEM_SIZE>32) { | |
fprintf(stderr,"Memory is limited to 32 bits. Compile with EXPONENT64 flag for 64bits.\n"); | |
exit(1); | |
#endif | |
} else if(MEM_SIZE<1 || MEM_SIZE>60) { | |
fprintf(stderr,"Memory bits not valid\n"); | |
exit(1); | |
} | |
if(DEBUG) | |
printf("Debug level: %d\n", DEBUG); | |
GSTEP = ((uint64_t)1<<MEM_SIZE); | |
HASH_SIZE = (2*GSTEP); | |
if(DEBUG) | |
printf("HASH_SIZE: 0x%lx\n", HASH_SIZE); | |
table = malloc((uint64_t) HASH_SIZE*sizeof(hashtable_entry)); | |
if(!table) { | |
fprintf(stderr,"Failed to allocate %luGB of memory\n", HASH_SIZE*sizeof(hashtable_entry)/1073741824); | |
exit(1); | |
} | |
secp256k1_context *ctx = secp256k1_context_create(SECP256K1_CONTEXT_NONE); | |
FILE *fp = stdin; | |
char * line = NULL; | |
size_t len = 0; | |
ssize_t read; | |
long i=0; | |
int r; | |
while ((read = getline(&line, &len, fp)) != -1) { | |
//printf(line); | |
if(line[read-1] == '\n') { | |
line[read-1] = '\0'; | |
--read; | |
} | |
unsigned char *h = hex2bin(line); | |
//printf("len: %d\nread: %s\nbin: %s\n",read,line,h); | |
pubkeys = realloc(pubkeys, (i+1) * sizeof(secp256k1_ge)); | |
r = secp256k1_eckey_pubkey_parse(&pubkeys[i], hex2bin(line), 33); | |
printf("r: %d\n",r); | |
const char cx[65]; | |
secp256k1_fe_get_hex(cx, &pubkeys[i].x); | |
printf("x: %s\n",cx); | |
i++; | |
} | |
//exit(0); | |
if(DEBUG) | |
printf("GSTEP: 0x%lx\n", GSTEP); | |
/*printf("Threads: %d\n", THREADS); | |
printf("Check bit = %d only, pubkey is:\n", CHECK_BITS); | |
for(uint32_t i=0;i<33;i++) | |
printf("%02x",pubkeys[CHECK_BITS - 1][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; | |
skip = (uint64_t)0x1 << skip_bits; | |
g_max = ((uint64_t)0x1 << shift_gmax)* (uint64_t)(GSTEP); | |
if(DEBUG) | |
printf("skip %016lx gmax %016lx\n",skip,g_max); | |
uint128_t rstart = (uint128_t)skip *(uint128_t)(HASH_SIZE); | |
uint128_t rend = (uint128_t)g_max*(uint128_t)(HASH_SIZE)-1; | |
uint64_t start_lo = rstart; | |
uint64_t start_hi = rstart>>64; | |
uint64_t end_lo = rend; | |
uint64_t 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 (%d) = %dGB\n", MEM_SIZE, (uint32_t)(HASH_SIZE*one_table_bytes>>30)); | |
#ifdef TIME | |
time1 = time(0); | |
#endif | |
// Precalculate 2**i table | |
secp256k1_gej_set_ge(&pt, &secp256k1_ge_const_g); | |
for(int i = 0; i<256; i++) { | |
secp256k1_ge_set_gej(&P[i], &pt); | |
secp256k1_gej_double_var(&pt, &pt, NULL); | |
} | |
// Memory Init | |
pthread_t tid; | |
for (int z = 0; z < THREADS; z++) { | |
status[z] = 0; | |
int *arg = malloc(sizeof(*arg)); | |
*arg = z; | |
pthread_create(&tid, NULL, memoryInit, arg); | |
} | |
pthread_join(tid, NULL); | |
#ifdef TIME | |
time2 = time(NULL); | |
sleep(1); | |
printf("\rCompleted in %d seconds \n", (time2 - time1)); | |
#else | |
printf("\rCompleted \n"); | |
#endif | |
secp256k1_gej_neg(&pt, &pt); | |
secp256k1_gej_double_var(&pt, &pt, NULL); | |
secp256k1_ge_set_gej(&ptgstep, &pt); | |
printf("[+] Search bits = %d\n", CHECK_BITS); | |
secp256k1_ge_set_gej(&P[0], &pt); | |
for (uint64_t i = 0; i < skip_bits; i+=1) { | |
secp256k1_gej_double_var(&pt, &pt, NULL); | |
secp256k1_ge_set_gej(&P[i+1], &pt); | |
} | |
// Search Keys | |
printf("[+] Search Keys.... from %lx%016lx to %lx%016lx\n",start_hi,start_lo, end_hi,end_lo); | |
if(DEBUG) | |
printf("SKIP: %lu - G_MAX: %lu\n", skip, g_max); | |
pthread_t tid2; | |
for (int z = 0; z < THREADS; z++) { | |
status[z] = 0; | |
int *arg = malloc(sizeof(*arg)); | |
*arg = z; | |
pthread_create(&tid2, NULL, searchKeys, arg); | |
} | |
pthread_join(tid2, NULL); | |
return 0; | |
} | |
void *memoryInit(void *arg) { | |
int d = *((int*)arg); | |
free(arg); | |
uint64_t start = 1 + (GSTEP)/THREADS * (d); | |
uint64_t end = start + GSTEP/THREADS; | |
if(d==THREADS-1) end = GSTEP; | |
secp256k1_gej pt2; | |
if(DEBUG) | |
printf("Thread %02d - %lu - %lu - %lu\n", d, start, end, GSTEP); | |
// Init 'pt2' in thread using binary P table. | |
if(d!=0) { | |
int pt_init = 0; | |
for(uint64_t a = 0; a<64; a++) { | |
if(start>>a & 0x1 == 0x1) { | |
if(pt_init) { | |
secp256k1_gej_add_ge_var(&pt2, &pt2, &P[a], NULL); | |
} else { | |
secp256k1_gej_set_ge(&pt2, &P[a]); | |
pt_init = 1; | |
} | |
} | |
} | |
} else { | |
secp256k1_gej_set_ge(&pt2, &secp256k1_ge_const_g); | |
} | |
for (uint64_t i = start; i < end; i++) { | |
#ifdef TIME | |
if ((i % 200000)==0 && i>0 && (time(0)-time2)>0) { | |
status[d] = i-start; | |
if(d==0) { | |
float tmpstatus = 0.0; | |
for(int j=0; j<THREADS; j++) tmpstatus += (float) status[j]*100/(end-start); | |
tmpstatus /= THREADS; | |
printf("\r %02.2f%% - %d seconds. Remaining %.0f seconds. ", tmpstatus, (time(0) - time1), ((time(0) - time1)*(float)(100-tmpstatus))/(float)(tmpstatus)); | |
fflush(stdout); | |
} | |
} | |
#else | |
if ((i % 200000) == 0 && i>0) { | |
status[d] = i-start; | |
if(d==0) { | |
float tmpstatus = 0; | |
for(int j=0; j<THREADS; j++) tmpstatus += (float) status[j]*100/(end-start); | |
tmpstatus /= THREADS; | |
printf("\r %02.2f%%", tmpstatus); | |
fflush(stdout); | |
} | |
} | |
#endif | |
secp256k1_fe x, zinv; | |
secp256k1_fe_storage xst; | |
secp256k1_fe_inv_var(&zinv, &pt2.z); | |
secp256k1_fe_sqr(&zinv, &zinv); | |
secp256k1_fe_mul(&x, &pt2.x, &zinv); | |
secp256k1_fe_to_storage(&xst, &x); | |
uint64_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(&pt2, &pt2, &secp256k1_ge_const_g, NULL); | |
} | |
// Write final pt (GSTEP) in global var pt | |
if(d==THREADS-1) { | |
secp256k1_gej_copy(&pt, &pt2); | |
} | |
} | |
void *searchKeys(void *arg) { | |
int d = *((int*)arg); | |
free(arg); | |
uint64_t start = skip + (g_max-skip)/THREADS * (d); | |
uint64_t end = skip + (g_max-skip)/THREADS * (d+1); | |
if(d==THREADS-1) end = g_max; | |
// Thread variable por 'pt' | |
secp256k1_gej pt2; | |
secp256k1_gej_copy(&pt2, &pt); | |
if(DEBUG) | |
printf("Thread %02d - %lu - %lu - %lu\n", d, start, end, g_max); | |
// Init 'pt2' in thread using binary P table. | |
if(d!=0) { | |
for(uint64_t a = 0; a<64; a++) { | |
if((start-skip)>>a & 0x1 == 0x1) { | |
secp256k1_gej_add_ge_var(&pt2, &pt2, &P[a], NULL); | |
} | |
} | |
} | |
for (uint64_t i = start; i < end; i++) { | |
#ifdef TIME | |
if ((i % 200000)==0 && i>0 && (time(0)-time2)>0) { | |
status[d] = i-start; | |
if(d==0) { | |
float tmpstatus = 0.0; | |
for(int j=0; j<THREADS; j++) tmpstatus += (float) status[j]*100/(end-start); | |
tmpstatus /= THREADS; | |
printf("\r %02.2f%% - %d seconds. Remaining %.0f seconds. ", tmpstatus, (time(0) - time2), ((time(0) - time2)*(float)(100-tmpstatus))/(float)(tmpstatus)); | |
fflush(stdout); | |
} | |
} | |
#else | |
if ((i % 200000) == 0 && i>0) { | |
status[d] = i-start; | |
if(d==0) { | |
float tmpstatus = 0; | |
for(int j=0; j<THREADS; j++) tmpstatus += (float) status[j]*100/(end-start); | |
tmpstatus /= THREADS; | |
printf("\r %02.2f%%", tmpstatus); | |
fflush(stdout); | |
} | |
} | |
#endif | |
secp256k1_gej diff; | |
secp256k1_fe x, zinv; | |
secp256k1_fe_storage xst; | |
secp256k1_gej_add_ge_var(&diff, &pt2, &pubkeys[CHECK_BITS - 1], NULL); | |
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); | |
uint64_t entry = xst.n[0] & (HASH_SIZE-1); | |
while (table[entry].exponent != 0) { | |
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("\nFound private key in thread %d %2d: %048lx%016lx or %048lx%016lx\n", d, CHECK_BITS, key1hi, key1lo, key2hi, key2lo); | |
#ifdef TIME | |
printf("Found in %d seconds. Total: %d seconds\n", (time(0) - time2), (time(0) - time1)); | |
#endif | |
FILE *fp = fopen("key.log","a+"); | |
if (DEBUG) | |
fprintf(fp,"Found private, b=%02d i=%16lx, x 2 x %16lx, exp=%x\n", CHECK_BITS, (uint64_t)i, GSTEP, table[entry].exponent); | |
fprintf(fp,"Found private key %2d:\n%048lx%016lx\n%048lx%016lx\n", CHECK_BITS, key1hi, key1lo, key2hi, key2lo); | |
fclose(fp); | |
exit(0); | |
return 0; | |
} | |
entry = (entry + (xst.n[1] | 1)) & (HASH_SIZE - 1); | |
} | |
secp256k1_gej_add_ge_var(&pt2, &pt2, &ptgstep, NULL); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment