Skip to content

Instantly share code, notes, and snippets.

@jhoenicke
Created April 6, 2017 09:31
Show Gist options
  • Save jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89 to your computer and use it in GitHub Desktop.
Save jhoenicke/2e39b3c6c49b1d7b216b8626197e4b89 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.
/**********************************************************************
* 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"
/* giant steps are 2^25 */
#define GSTEP (1<<25)
#define NUMPUBKEYS 51
unsigned char rawpubkeys[NUMPUBKEYS][33] = {
{ 0x02,0x79,0xbe,0x66,0x7e,0xf9,0xdc,0xbb,0xac,0x55,0xa0,0x62,0x95,0xce,0x87,0x0b,0x07,0x02,0x9b,0xfc,0xdb,0x2d,0xce,0x28,0xd9,0x59,0xf2,0x81,0x5b,0x16,0xf8,0x17,0x98 }, /* 1 */
{ 0x02,0xf9,0x30,0x8a,0x01,0x92,0x58,0xc3,0x10,0x49,0x34,0x4f,0x85,0xf8,0x9d,0x52,0x29,0xb5,0x31,0xc8,0x45,0x83,0x6f,0x99,0xb0,0x86,0x01,0xf1,0x13,0xbc,0xe0,0x36,0xf9 }, /* 2 */
{ 0x02,0x5c,0xbd,0xf0,0x64,0x6e,0x5d,0xb4,0xea,0xa3,0x98,0xf3,0x65,0xf2,0xea,0x7a,0x0e,0x3d,0x41,0x9b,0x7e,0x03,0x30,0xe3,0x9c,0xe9,0x2b,0xdd,0xed,0xca,0xc4,0xf9,0xbc }, /* 3 */
{ 0x02,0x2f,0x01,0xe5,0xe1,0x5c,0xca,0x35,0x1d,0xaf,0xf3,0x84,0x3f,0xb7,0x0f,0x3c,0x2f,0x0a,0x1b,0xdd,0x05,0xe5,0xaf,0x88,0x8a,0x67,0x78,0x4e,0xf3,0xe1,0x0a,0x2a,0x01 }, /* 4 */
{ 0x02,0x35,0x2b,0xbf,0x4a,0x4c,0xdd,0x12,0x56,0x4f,0x93,0xfa,0x33,0x2c,0xe3,0x33,0x30,0x1d,0x9a,0xd4,0x02,0x71,0xf8,0x10,0x71,0x81,0x34,0x0a,0xef,0x25,0xbe,0x59,0xd5 }, /* 5 */
{ 0x03,0xf2,0xda,0xc9,0x91,0xcc,0x4c,0xe4,0xb9,0xea,0x44,0x88,0x7e,0x5c,0x7c,0x0b,0xce,0x58,0xc8,0x00,0x74,0xab,0x9d,0x4d,0xba,0xeb,0x28,0x53,0x1b,0x77,0x39,0xf5,0x30 }, /* 6 */
{ 0x02,0x96,0x51,0x6a,0x8f,0x65,0x77,0x42,0x75,0x27,0x8d,0x0d,0x74,0x20,0xa8,0x8d,0xf0,0xac,0x44,0xbd,0x64,0xc7,0xba,0xe0,0x7c,0x3f,0xe3,0x97,0xc5,0xb3,0x30,0x0b,0x23 }, /* 7 */
{ 0x03,0x08,0xbc,0x89,0xc2,0xf9,0x19,0xed,0x15,0x88,0x85,0xc3,0x56,0x00,0x84,0x4d,0x49,0x89,0x09,0x05,0xc7,0x9b,0x35,0x73,0x22,0x60,0x9c,0x45,0x70,0x6c,0xe6,0xb5,0x14 }, /* 8 */
{ 0x02,0x43,0x60,0x1d,0x61,0xc8,0x36,0x38,0x74,0x85,0xe9,0x51,0x4a,0xb5,0xc8,0x92,0x4d,0xd2,0xcf,0xd4,0x66,0xaf,0x34,0xac,0x95,0x00,0x27,0x27,0xe1,0x65,0x9d,0x60,0xf7 }, /* 9 */
{ 0x03,0xa7,0xa4,0xc3,0x02,0x91,0xac,0x1d,0xb2,0x4b,0x4a,0xb0,0x0c,0x44,0x2a,0xa8,0x32,0xf7,0x79,0x4b,0x5a,0x09,0x59,0xbe,0xc6,0xe8,0xd7,0xfe,0xe8,0x02,0x28,0x9d,0xcd }, /* 10 */
{ 0x03,0x8b,0x05,0xb0,0x60,0x3a,0xbd,0x75,0xb0,0xc5,0x74,0x89,0xe4,0x51,0xf8,0x11,0xe1,0xaf,0xe5,0x4a,0x87,0x15,0x04,0x5c,0xdf,0x48,0x88,0x33,0x3f,0x3e,0xbc,0x6e,0x8b }, /* 11 */
{ 0x03,0x8b,0x00,0xfc,0xbf,0xc1,0xa2,0x03,0xf4,0x4b,0xf1,0x23,0xfc,0x7f,0x4c,0x91,0xc1,0x0a,0x85,0xc8,0xea,0xe9,0x18,0x7f,0x9d,0x22,0x24,0x2b,0x46,0x00,0xce,0x78,0x1c }, /* 12 */
{ 0x03,0xaa,0xda,0xaa,0xb1,0xdb,0x8d,0x5d,0x45,0x0b,0x51,0x17,0x89,0xc3,0x7e,0x7c,0xfe,0xb0,0xeb,0x8b,0x3e,0x61,0xa5,0x7a,0x34,0x16,0x6c,0x5e,0xdc,0x9a,0x4b,0x86,0x9d }, /* 13 */
{ 0x03,0xb4,0xf1,0xde,0x58,0xb8,0xb4,0x1a,0xfe,0x9f,0xd4,0xe5,0xff,0xbd,0xaf,0xae,0xab,0x86,0xc5,0xdb,0x47,0x69,0xc1,0x5d,0x6e,0x60,0x11,0xae,0x73,0x51,0xe5,0x47,0x59 }, /* 14 */
{ 0x02,0xfe,0xa5,0x8f,0xfc,0xf4,0x95,0x66,0xf6,0xe9,0xe9,0x35,0x0c,0xf5,0xbc,0xa2,0x86,0x13,0x12,0xf4,0x22,0x96,0x6e,0x8d,0xb1,0x60,0x94,0xbe,0xb1,0x4d,0xc3,0xdf,0x2c }, /* 15 */
{ 0x02,0x9d,0x8c,0x5d,0x35,0x23,0x1d,0x75,0xeb,0x87,0xfd,0x2c,0x5f,0x05,0xf6,0x52,0x81,0xed,0x95,0x73,0xdc,0x41,0x85,0x32,0x88,0xc6,0x2e,0xe9,0x4e,0xb2,0x59,0x0b,0x7a }, /* 16 */
{ 0x03,0x3f,0x68,0x8b,0xae,0x83,0x21,0xb8,0xe0,0x2b,0x7e,0x6c,0x0a,0x55,0xc2,0x51,0x5f,0xb2,0x5a,0xb9,0x7d,0x85,0xfd,0xa8,0x42,0x44,0x9f,0x7b,0xfa,0x04,0xe1,0x28,0xc3 }, /* 17 */
{ 0x02,0x0c,0xe4,0xa3,0x29,0x1b,0x19,0xd2,0xe1,0xa7,0xbf,0x73,0xee,0x87,0xd3,0x0a,0x6b,0xdb,0xc7,0x2b,0x20,0x77,0x1e,0x7d,0xff,0xf4,0x0d,0x0d,0xb7,0x55,0xcd,0x4a,0xf1 }, /* 18 */
{ 0x03,0x85,0x66,0x3c,0x8b,0x2f,0x90,0x65,0x9e,0x1c,0xca,0xb2,0x01,0x69,0x4f,0x4f,0x8e,0xc2,0x4b,0x37,0x49,0xcf,0xe5,0x03,0x0c,0x7c,0x36,0x46,0xa7,0x09,0x40,0x8e,0x19 }, /* 19 */
{ 0x03,0x3c,0x4a,0x45,0xcb,0xd6,0x43,0xff,0x97,0xd7,0x7f,0x41,0xea,0x37,0xe8,0x43,0x64,0x8d,0x50,0xfd,0x89,0x4b,0x86,0x4b,0x0d,0x52,0xfe,0xbc,0x62,0xf6,0x45,0x4f,0x7c }, /* 20 */
{ 0x03,0x1a,0x74,0x6c,0x78,0xf7,0x27,0x54,0xe0,0xbe,0x04,0x61,0x86,0xdf,0x8a,0x20,0xcd,0xce,0x5c,0x79,0xb2,0xed,0xa7,0x60,0x13,0xc6,0x47,0xaf,0x08,0xd3,0x06,0xe4,0x9e }, /* 21 */
{ 0x02,0x3e,0xd9,0x6b,0x52,0x4d,0xb5,0xff,0x4f,0xe0,0x07,0xce,0x73,0x03,0x66,0x05,0x2b,0x7c,0x51,0x1d,0xc5,0x66,0x22,0x7d,0x92,0x90,0x70,0xb9,0xce,0x91,0x7a,0xbb,0x43 }, /* 22 */
{ 0x03,0xf8,0x27,0x10,0x36,0x1b,0x8b,0x81,0xbd,0xed,0xb1,0x69,0x94,0xf3,0x0c,0x80,0xdb,0x52,0x24,0x50,0xa9,0x3e,0x8e,0x87,0xee,0xb0,0x7f,0x79,0x03,0xcf,0x28,0xd0,0x4b }, /* 23 */
{ 0x03,0x6e,0xa8,0x39,0xd2,0x28,0x47,0xee,0x1d,0xce,0x3b,0xfc,0x5b,0x11,0xf6,0xcf,0x78,0x5b,0x06,0x82,0xdb,0x58,0xc3,0x5b,0x63,0xd1,0x34,0x2e,0xb2,0x21,0xc3,0x49,0x0c }, /* 24 */
{ 0x03,0x05,0x7f,0xbe,0xa3,0xa2,0x62,0x33,0x82,0x62,0x8d,0xde,0x55,0x6b,0x2a,0x06,0x98,0xe3,0x24,0x28,0xd3,0xcd,0x22,0x5f,0x3b,0xd0,0x34,0xdc,0xa8,0x2d,0xd7,0x45,0x5a }, /* 25 */
{ 0x02,0x4e,0x4f,0x50,0xa2,0xa3,0xec,0xcd,0xb3,0x68,0x98,0x8a,0xe3,0x7c,0xd4,0xb6,0x11,0x69,0x7b,0x26,0xb2,0x96,0x96,0xe4,0x2e,0x06,0xd7,0x13,0x68,0xb4,0xf3,0x84,0x0f }, /* 26 */
{ 0x03,0x1a,0x86,0x4b,0xae,0x39,0x22,0xf3,0x51,0xf1,0xb5,0x7c,0xfd,0xd8,0x27,0xc2,0x5b,0x7e,0x09,0x3c,0xb9,0xc8,0x8a,0x72,0xc1,0xcd,0x89,0x3d,0x9f,0x90,0xf4,0x4e,0xce }, /* 27 */
{ 0x03,0xe9,0xe6,0x61,0x83,0x8a,0x96,0xa6,0x53,0x31,0x63,0x7e,0x2a,0x3e,0x94,0x8d,0xc0,0x75,0x6e,0x50,0x09,0xe7,0xcb,0x5c,0x36,0x66,0x4d,0x9b,0x72,0xdd,0x18,0xc0,0xa7 }, /* 28 */
{ 0x02,0x6c,0xaa,0xd6,0x34,0x38,0x2d,0x34,0x69,0x1e,0x3b,0xef,0x43,0xed,0x4a,0x12,0x4d,0x89,0x09,0xa8,0xa3,0x36,0x2f,0x91,0xf1,0xd2,0x0a,0xba,0xaf,0x7e,0x91,0x7b,0x36 }, /* 29 */
{ 0x03,0x0d,0x28,0x2c,0xf2,0xff,0x53,0x6d,0x2c,0x42,0xf1,0x05,0xd0,0xb8,0x58,0x88,0x21,0xa9,0x15,0xdc,0x3f,0x9a,0x05,0xbd,0x98,0xbb,0x23,0xaf,0x67,0xa2,0xe9,0x2a,0x5b }, /* 30 */
{ 0x03,0x87,0xdc,0x70,0xdb,0x18,0x06,0xcd,0x9a,0x9a,0x76,0x63,0x74,0x12,0xec,0x11,0xdd,0x99,0x8b,0xe6,0x66,0x58,0x48,0x49,0xb3,0x18,0x5f,0x7f,0x93,0x13,0xc8,0xfd,0x28 }, /* 31 */
{ 0x02,0x09,0xc5,0x82,0x40,0xe5,0x0e,0x3b,0xa3,0xf8,0x33,0xc8,0x26,0x55,0xe8,0x72,0x5c,0x03,0x7a,0x22,0x94,0xe1,0x4c,0xf5,0xd7,0x3a,0x5d,0xf8,0xd5,0x61,0x59,0xde,0x69 }, /* 32 */
{ 0x03,0xa3,0x55,0xaa,0x5e,0x2e,0x09,0xdd,0x44,0xbb,0x46,0xa4,0x72,0x2e,0x93,0x36,0xe9,0xe3,0xee,0x4e,0xe4,0xe7,0xb7,0xa0,0xcf,0x57,0x85,0xb2,0x83,0xbf,0x2a,0xb5,0x79 }, /* 33 */
{ 0x03,0x3c,0xdd,0x9d,0x6d,0x97,0xcb,0xfe,0x7c,0x26,0xf9,0x02,0xfa,0xf6,0xa4,0x35,0x78,0x0f,0xe6,0x52,0xe1,0x59,0xec,0x95,0x36,0x50,0xec,0x7b,0x10,0x04,0x08,0x27,0x90 }, /* 34 */
{ 0x02,0xf6,0xa8,0x14,0x8a,0x62,0x32,0x0e,0x14,0x9c,0xb1,0x5c,0x54,0x4f,0xe8,0xa2,0x5a,0xb4,0x83,0xa0,0x09,0x5d,0x22,0x80,0xd0,0x3b,0x8a,0x00,0xa7,0xfe,0xad,0xa1,0x3d }, /* 35 */
{ 0x02,0xb3,0xe7,0x72,0x21,0x66,0x95,0x84,0x5f,0xa9,0xdd,0xa4,0x19,0xfb,0x5d,0xac,0xa2,0x81,0x54,0xd8,0xaa,0x59,0xea,0x30,0x2f,0x05,0xe9,0x16,0x63,0x5e,0x47,0xb9,0xf6 }, /* 36 */
{ 0x02,0x7d,0x2c,0x03,0xc3,0xef,0x0a,0xec,0x70,0xf2,0xc7,0xe1,0xe7,0x54,0x54,0xa5,0xdf,0xdd,0x0e,0x1a,0xde,0xa6,0x70,0xc1,0xb3,0xa4,0x64,0x3c,0x48,0xad,0x0f,0x12,0x55 }, /* 37 */
{ 0x03,0xc0,0x60,0xe1,0xe3,0x77,0x1c,0xbe,0xcc,0xb3,0x8e,0x11,0x9c,0x24,0x14,0x70,0x2f,0x3f,0x51,0x81,0xa8,0x96,0x52,0x53,0x88,0x51,0xd2,0xe3,0x88,0x6b,0xdd,0x70,0xc6 }, /* 38 */
{ 0x02,0x2d,0x77,0xcd,0x14,0x67,0x01,0x9a,0x6b,0xf2,0x8f,0x73,0x75,0xd0,0x94,0x9c,0xe3,0x0e,0x6b,0x58,0x15,0xc2,0x75,0x8b,0x98,0xa7,0x4c,0x27,0x00,0xbc,0x00,0x65,0x43 }, /* 39 */
{ 0x03,0xa2,0xef,0xa4,0x02,0xfd,0x52,0x68,0x40,0x0c,0x77,0xc2,0x0e,0x57,0x4b,0xa8,0x64,0x09,0xed,0xed,0xee,0x7c,0x40,0x20,0xe4,0xb9,0xf0,0xed,0xbe,0xe5,0x3d,0xe0,0xd4 }, /* 40 */
{ 0x03,0xb3,0x57,0xe6,0x84,0x37,0xda,0x27,0x3d,0xcf,0x99,0x5a,0x47,0x4a,0x52,0x44,0x39,0xfa,0xad,0x86,0xfc,0x9e,0xff,0xc3,0x00,0x18,0x3f,0x71,0x4b,0x09,0x03,0x46,0x8b }, /* 41 */
{ 0x03,0xee,0xc8,0x83,0x85,0xbe,0x9d,0xa8,0x03,0xa0,0xd6,0x57,0x97,0x98,0xd9,0x77,0xa5,0xd0,0xc7,0xf8,0x09,0x17,0xda,0xb4,0x9c,0xb7,0x3c,0x9e,0x39,0x27,0x14,0x2c,0xb6 }, /* 42 */
{ 0x02,0xa6,0x31,0xf9,0xba,0x0f,0x28,0x51,0x16,0x14,0x90,0x4d,0xf8,0x0d,0x7f,0x97,0xa4,0xf4,0x3f,0x02,0x24,0x9c,0x89,0x09,0xda,0xc9,0x22,0x76,0xcc,0xf0,0xbc,0xda,0xed }, /* 43 */
{ 0x02,0x5e,0x46,0x6e,0x97,0xed,0x0e,0x79,0x10,0xd3,0xd9,0x0c,0xeb,0x03,0x32,0xdf,0x48,0xdd,0xf6,0x7d,0x45,0x6b,0x9e,0x73,0x03,0xb5,0x0a,0x3d,0x89,0xde,0x35,0x73,0x36 }, /* 44 */
{ 0x02,0x6e,0xca,0xbd,0x2d,0x22,0xfd,0xb7,0x37,0xbe,0x21,0x97,0x5c,0xe9,0xa6,0x94,0xe1,0x08,0xeb,0x94,0xf3,0x64,0x9c,0x58,0x6c,0xc7,0x46,0x1c,0x8a,0xbf,0x5d,0xa7,0x1a }, /* 45 */
{ 0x03,0xfd,0x54,0x87,0x72,0x2d,0x25,0x76,0xcb,0x6d,0x70,0x81,0x42,0x6b,0x66,0xa3,0xe2,0x98,0x6c,0x1c,0xe8,0x35,0x8d,0x47,0x90,0x63,0xfb,0x5f,0x2b,0xb6,0xdd,0x58,0x49 }, /* 46 */
{ 0x02,0x3a,0x12,0xbd,0x3c,0xaf,0x0b,0x0f,0x77,0xbf,0x4e,0xea,0x8e,0x7a,0x40,0xdb,0xe2,0x79,0x32,0xbf,0x80,0xb1,0x9a,0xc7,0x2f,0x5f,0x5a,0x64,0x92,0x5a,0x59,0x41,0x96 }, /* 47 */
{ 0x02,0x91,0xbe,0xe5,0xcf,0x4b,0x14,0xc2,0x91,0xc6,0x50,0x73,0x2f,0xaa,0x16,0x60,0x40,0xe4,0xc1,0x8a,0x14,0x73,0x1f,0x9a,0x93,0x0c,0x1e,0x87,0xd3,0xec,0x12,0xde,0xbb }, /* 48 */
{ 0x02,0x59,0x1d,0x68,0x2c,0x3d,0xa4,0xa2,0xa6,0x98,0x63,0x3b,0xf5,0x75,0x17,0x38,0xb6,0x7c,0x34,0x32,0x85,0xeb,0xdc,0x34,0x92,0x64,0x5c,0xb4,0x46,0x58,0x91,0x14,0x84 }, /* 49 */
{ 0x03,0xf4,0x6f,0x41,0x02,0x7b,0xbf,0x44,0xfa,0xfd,0x6b,0x05,0x90,0x91,0xb9,0x00,0xda,0xd4,0x1e,0x68,0x45,0xb2,0x24,0x1d,0xc3,0x25,0x4c,0x7c,0xdd,0x3c,0x5a,0x16,0xc6 }, /* 50 */
{ 0x02,0x8c,0x6c,0x67,0xbe,0xf9,0xe9,0xee,0xbe,0x6a,0x51,0x32,0x72,0xe5,0x0c,0x23,0x0f,0x0f,0x91,0xed,0x56,0x0c,0x37,0xbc,0x9b,0x03,0x32,0x41,0xff,0x6c,0x3b,0xe7,0x8f }, /* 51 */
};
typedef struct hashtable_entry {
uint32_t x;
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("Build Hash\n");
secp256k1_gej pt;
secp256k1_gej_set_ge(&pt, &secp256k1_ge_const_g);
for (size_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].x = xst.n[2];
secp256k1_gej_add_ge_var(&pt, &pt, &secp256k1_ge_const_g, NULL);
}
printf("Search Keys\n");
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);
for (size_t i = 0; i < 2*GSTEP; 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[j], 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);
uint32_t entry = xst.n[0] & (HASH_SIZE-1);
while (table[entry].exponent != 0) {
if (table[entry].x == (uint32_t) xst.n[2]) {
uint64_t key = (uint64_t) i * (uint64_t) (2 * GSTEP);
printf("Found private key %2d: %16lx or %16lx\n", j + 1,
key - table[entry].exponent,
key + table[entry].exponent);
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;
}
@sanhwy
Copy link

sanhwy commented Jul 9, 2019

bitcrack does not use Pollard kangaroo ?

@sairam17519
Copy link

Sir, Please suggest me how to run this code in windows 10. what are the softwares required?

@sairam17519
Copy link

Can you please share these include files
#include "libsecp256k1-config.h"
#include "include/secp256k1.h"
#include "secp256k1.c"

@dollarboy1
Copy link

Am I going to run discord with GPU kangaroo speed and computing power and is it offline or online cord?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment