Skip to content

Instantly share code, notes, and snippets.

@daedalus

daedalus/break-short.c

Last active April 20, 2020 08:42
Show Gist options
  • Save daedalus/630a63b00f063e24ad1eaf3d7e4cc0c8 to your computer and use it in GitHub Desktop.
Save daedalus/630a63b00f063e24ad1eaf3d7e4cc0c8 to your computer and use it in GitHub Desktop.
Download ZIP
Program to brute force private keys from public keys using the baby-step giant-step algorithm. Improved to use threads.
Raw
break-short.c
/***********************************************************************************************************
* 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