Program to brute force private keys from public keys using the baby-step giant-step algorithm.

break-short.c

/**********************************************************************
 * 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;
}