Bitcoin puzzle transaction ~32 BTC prize to who solves it

[nomachine]

Guys, have you ever thought that maybe it’s not a piece-by-piece puzzle at all, but simply a quiz?
I mean, maybe the creator hid a pattern that could lead us straight to the solution. Has this idea been discussed already?
Could you give us some hints, please @saatoshi_rising?
We would really appreciate it!

Whoever came up with this Puzzle knows exactly what he's doing.

I use a trial-and-error method a problem-solving approach where you systematically try different options or solutions until you find one that works or achieves the desired result.

This is like the movie Groundhog Day, about a man reliving the same day over and over again.

All puzzles are created with one or similar random, seed - known to the creator.  The puzzle creator tattooed it on their upper arm.
And there is no pattern. It’s not a timestamp. It can’t be reproduced by going back in time.

I think it's obvious that he has his own custom deterministic wallet with errors = ZERO

There is no limit and way someone can search for a puzzle. It's like art. Mostly worthless art collection.

[Akito S. M. Hosana]

This is like the movie Groundhog Day, about a man reliving the same day over and over again.

This is absolutely true. It's just that I'm not getting smarter and smarter like the character from the movie. Here  is always a groundhog behind the wheel driving down the cliff. Especially with AI experiments. A lost cause. 

[zion3301]

Guys, have you ever thought that maybe it’s not a piece-by-piece puzzle at all, but simply a quiz?
I mean, maybe the creator hid a pattern that could lead us straight to the solution. Has this idea been discussed already?
Could you give us some hints, please @saatoshi_rising?
We would really appreciate it!

Whoever came up with this Puzzle knows exactly what he's doing.

I use a trial-and-error method a problem-solving approach where you systematically try different options or solutions until you find one that works or achieves the desired result.

This is like the movie Groundhog Day, about a man reliving the same day over and over again.

All puzzles are created with one or similar random, seed - known to the creator.  The puzzle creator tattooed it on their upper arm.
And there is no pattern. It’s not a timestamp. It can’t be reproduced by going back in time.

I think it's obvious that he has his own custom deterministic wallet with errors = ZERO

There is no limit and way someone can search for a puzzle. It's like art. Mostly worthless art collection.

Thats true. The creator know 100% what he was doing. He constructed the a perfectly ordered transaction after he created consecutive keys and masked them. He also remembered the private keys after two years. He almost forgot about the puzzle and then moved funds from 162-255 to the lower ones.
if he used a seed-approach which contains methods like sha2, then there is truely no pattern, as the creator stated.
But in my opinion, if he used a seed approach then the seed is anywhere public or accessable.
I dont think its truely random, because of the fact, that the creator remembered the private keys after 2 years

[nomachine]

if he used a seed-approach which contains methods like sha2, then there is truely no pattern, as the creator stated.
But in my opinion, if he used a seed approach then the seed is anywhere public or accessable.
I dont think its truely random, because of the fact, that the creator remembered the private keys after 2 years

Here is example:

Code:

import random
import hashlib
import base58

for puzzle in range(1, 160):
      lower = 2 ** (puzzle - 1)
      upper = (2 ** puzzle) - 1
      seed = "SatoshiNakamotoPuzzle" + str(puzzle)
      random.seed(seed)
      dec = random.randint(lower, upper)
      private_key_hex = "%064x" %  dec
      private_key_bytes = bytes.fromhex(private_key_hex)
      extended_key = b'\x80' + private_key_bytes
      extended_key += b'\x01'
      checksum = hashlib.sha256(hashlib.sha256(extended_key).digest()).digest()[:4]
      wif_bytes = extended_key + checksum
      wif_compressed = base58.b58encode(wif_bytes).decode()
      print(f"Puzzle = {puzzle} seed = {seed} wif = {wif_compressed}")

Puzzle = 60 seed = SatoshiNakamotoPuzzle60 wif = KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYkwi7gQXBe3k1QZLZ3Z
Puzzle = 61 seed = SatoshiNakamotoPuzzle61 wif = KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYn9rYCpH1xFmXKYze83
Puzzle = 62 seed = SatoshiNakamotoPuzzle62 wif = KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYnqQxQ9uyUTp8A7vUwi
Puzzle = 63 seed = SatoshiNakamotoPuzzle63 wif = KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qYstQ4L2v4VZxu6s83mL
Puzzle = 64 seed = SatoshiNakamotoPuzzle64 wif = KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qZ6CF5Nc1QqBfAA1Ynme
Puzzle = 65 seed = SatoshiNakamotoPuzzle65 wif = KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qZCe9JmRWhdKweDYrcZo
Puzzle = 66 seed = SatoshiNakamotoPuzzle66 wif = KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qZWCKpZnZsCqVzc1f9vt
Puzzle = 67 seed = SatoshiNakamotoPuzzle67 wif = KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qbeiYkkDLY2iKmA6JS3q
Puzzle = 68 seed = SatoshiNakamotoPuzzle68 wif = KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qcopt3giY39KjX9pfekV
Puzzle = 69 seed = SatoshiNakamotoPuzzle69 wif = KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qkTtFZibZ9tNE96yFsjS
Puzzle = 70 seed = SatoshiNakamotoPuzzle70 wif = KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3qqDJuNu7s3FZKtsk9Pn7
Puzzle = 71 seed = SatoshiNakamotoPuzzle71 wif = KwDiBf89QgGbjEhKnhXJuH7LrciVrZi3rBGXpLd8yP9kGu7rqRvw

You don’t need anything else, not even a deterministic wallet.
Just a Google Doc to save the code, and you’ll have all the WIFs.

[zion3301]

if he used a seed-approach which contains methods like sha2, then there is truely no pattern, as the creator stated.
But in my opinion, if he used a seed approach then the seed is anywhere public or accessable.
I dont think its truely random, because of the fact, that the creator remembered the private keys after 2 years

Here is example:

Code:

import random
import hashlib
import base58

for puzzle in range(1, 160):
      lower = 2 ** (puzzle - 1)
      upper = (2 ** puzzle) - 1
      seed = "SatoshiNakamotoPuzzle" + str(puzzle)
      random.seed(seed)
      dec = random.randint(lower, upper)
      private_key_hex = "%064x" %  dec
      private_key_bytes = bytes.fromhex(private_key_hex)
      extended_key = b'\x80' + private_key_bytes
      extended_key += b'\x01'
      checksum = hashlib.sha256(hashlib.sha256(extended_key).digest()).digest()[:4]
      wif_bytes = extended_key + checksum
      wif_compressed = base58.b58encode(wif_bytes).decode()
      print(f"Puzzle = {puzzle} seed = {seed} wif = {wif_compressed}")

You don’t need anything else, not even a deterministic wallet.
Just a Google Doc to save the code, and you’ll have all the WIFs.

yes thats a kind of determinsitic wallet. you dont even need that line: dec = random.randint(lower, upper)
you can also take the sha256 output of the seed.
so there are many types of custom deterministic wallets and maaaany possible seed.
also the seed itsself dont have to be ascii compatible (human readable). we can input any kind of data om the sha256 methods in hex format

[Akito S. M. Hosana]

Just a Google Doc to save the code, and you’ll have all the WIFs.

Do you think the code is this simple? With a random seed in a document on Google Drive or ? 

[nomachine]

Just a Google Doc to save the code, and you’ll have all the WIFs.

Do you think the code is this simple? With a random seed in a document on Google Drive or ? 

Why would it be more complicated? Everything can die. A USB stick, an SSD, a hard drive, even a hardware wallet. You don’t have to publish the seed publicly, but you can publicly share the code on Git, Pastebin, your email, or Google Drive. Who cares? It’ll still be there 50 years from now. You could even tattoo the seed on your lower leg so you don’t forget. 

[kTimesG]

Okay. Will break it down to you.
Tests for bloomfilter creation were made in terms of final binary image being equal for one thread and multiple threads creation.
In both cases the resulting binary image was equal.
.

Not sure what you're trying to explain, I didn't see a mention that the insert method is thread-safe (that would have been sufficient, but also required). It's your code after all, so I guess when you get burned, you're doing it in a very assumed way. Bugs of these type can show up after executing many trillions of cycles, or instantly, depending on the input. Having identical outputs after thousands of runs means nothing, since the core issue is unaddressed.

[kTimesG]

Mutex locks are necessary when multiple threads read, write and modify the same value. And order of their actions matters.

At the beginning all bits of a bloomfilter are off (set to 0).
The insert function sets some bit to 1 according to hash_value modulo bloomfilter size.
The race condition may happen very often. But which one thread will set the bit to 1 first does not matter.
The bit will be set to one as a result.

Writing a value involves reading the value. You're just ignoring this, and describing a perfect fallacy. When the different bits that need to be written end up on the same cache lines (let's say, in the same 64 bytes region, and a lot of cache lines can fit in L1) of different cores, you have two different results, both wrong, and one of those will end up in your filter.

You're not seeing the issue because the allocated area is very large, so the probability of updating nearby bits is low, but a low probability just means it will eventually happen, not that it is impossible to happen.

[kTimesG]

Writing a value involves reading the value.

Since each thread is just a sequence of instructions. We can log each step of its insertion way and compare the results afterwards.

Yeah, but those instructions run in parallel, hence it's guaranteed that, without an access sync, at some point, a r/w race condition will occur. You should know best what'ya doin', so I won't insist.
Or are you saying this can never happen:

Code:

X = 0

Cycle T0       T1
0     read X   read X      // T0: is X 0 or 32? T1: is X 0 or 8?
1     set x[3] set X[5]    // T0: is X 8 or 40? T1: is X 32 or 40?
2     write X  write X     // what X is final? what about cache lines refresh?
3     X = ????????         // one of 8, 32, or 40

[Nuclearkeys]

3 seconds on PYTHON! PK found.

Code:

import math, time, sys, os
from gmpy2 import mpz, powmod, invert, jacobi
import xxhash  
from sortedcontainers import SortedDict 

# Clear screen and initialize
os.system("cls||clear")
t = time.ctime()
sys.stdout.write(f"\033[?25l\033[01;33m[+] BSGS: {t}\n")
sys.stdout.flush()

# Elliptic Curve Parameters (secp256k1)
modulo = mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
order = mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
Gx = mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
Gy = mpz(0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
PG = (Gx, Gy)

# Point Addition on Elliptic Curve
def add(P, Q):
    if P == (0, 0):
        return Q
    if Q == (0, 0):
        return P
    Px, Py = P
    Qx, Qy = Q
    if Px == Qx:
        if Py == Qy:
            inv_2Py = invert((Py << 1) % modulo, modulo)
            m = (3 * Px * Px * inv_2Py) % modulo
        else:
            return (0, 0)
    else:
        inv_diff_x = invert(Qx - Px, modulo)
        m = ((Qy - Py) * inv_diff_x) % modulo
    x = (m * m - Px - Qx) % modulo
    y = (m * (Px - x) - Py) % modulo
    return (x, y)

# Scalar Multiplication on Elliptic Curve
def mul(k, P=PG):
    R0, R1 = (0, 0), P
    for i in reversed(range(k.bit_length())):
        if (k >> i) & 1:
            R0, R1 = add(R0, R1), add(R1, R1)
        else:
            R1, R0 = add(R0, R1), add(R0, R0)
    return R0

# Point Subtraction
def point_subtraction(P, Q):
    Q_neg = (Q[0], (-Q[1]) % modulo)
    return add(P, Q_neg)

# Compute Y from X using curve equation
def X2Y(X, y_parity, p=modulo):
    X3_7 = (pow(X, 3, p) + 7) % p
    if jacobi(X3_7, p) != 1:
        return None
    Y = powmod(X3_7, (p + 1) >> 2, p)
    return Y if (Y & 1) == y_parity else (p - Y)

# Convert point to compressed public key
def point_to_cpub(point):
    x, y = point
    y_parity = y & 1
    prefix = '02' if y_parity == 0 else '03'
    compressed_pubkey = prefix + format(x, '064x')
    return compressed_pubkey

# Hash a compressed public key using xxhash and store only the first 8 characters
def hash_cpub(cpub):
    return xxhash.xxh64(cpub.encode()).hexdigest()[:8]

# Main Script
if __name__ == "__main__":
    # Puzzle Parameters
    puzzle = 40
    start_range, end_range = 2**(puzzle-1), (2**puzzle) - 1
    puzzle_pubkey = '03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4'

    # Parse Public Key
    if len(puzzle_pubkey) != 66:
        print("[error] Public key length invalid!")
        sys.exit(1)
    prefix = puzzle_pubkey[:2]
    X = mpz(int(puzzle_pubkey[2:], 16))
    y_parity = int(prefix) - 2
    Y = X2Y(X, y_parity)
    if Y is None:
        print("[error] Invalid compressed public key!")
        sys.exit(1)
    P = (X, Y)  # Uncompressed public key

    # Precompute m and mP for BSGS
    m = int(math.floor(math.sqrt(end_range - start_range)))
    m_P = mul(m)

    # Create Baby Table with SortedDict
    print('[+] Creating babyTable...')
    baby_table = SortedDict()  
    Ps = (0, 0)  # Start with the point at infinity
    for i in range(m + 1):
        cpub = point_to_cpub(Ps)
        cpub_hash = hash_cpub(cpub)  # Use xxhash and store only 8 characters
        baby_table[cpub_hash] = i  # Store the hash as the key and index as the value
        Ps = add(Ps, PG)  # Incrementally add PG

    # BSGS Search
    print('[+] BSGS Search in progress')
    S = point_subtraction(P, mul(start_range))
    step = 0
    st = time.time()
    while step < (end_range - start_range):
        cpub = point_to_cpub(S)
        cpub_hash = hash_cpub(cpub)  # Hash the current compressed public key
        # Check if the hash exists in the baby_table
        if cpub_hash in baby_table:
            b = baby_table[cpub_hash]
            k = start_range + step + b
            if point_to_cpub(mul(k)) == puzzle_pubkey:
                print(f'[+] m={m} step={step} b={b}')
                print(f'[+] Key found: {k}')
                print("[+] Time Spent : {0:.2f} seconds".format(time.time() - st))
                sys.exit()
        S = point_subtraction(S, m_P)
        step += m

    print('[+] Key not found')
    print("[+] Time Spent : {0:.2f} seconds".format(time.time() - st))

puzzle 40

• BSGS: Thu Feb 20 21:49:30 2025
• Creating babyTable...
• BSGS Search in progress
• m=741455 step=453895024440 b=574622
• Key found: 1003651412950
• Time Spent : 2.90 seconds

puzzle 50

• BSGS: Thu Feb 20 22:13:12 2025
• Creating babyTable...
• BSGS Search in progress
• m=23726566 step=48190529944714 b=12801738
• Key found: 611140496167764
• Time Spent : 12.71 seconds

This is the result... on a single core

P.S. For puzzles above 50, you'll need a Bloom Filter

Who wrote this code?!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Share your donation address I can see light at the end of a tunnel.

[cctv5go]

Does anyone know who the author of the puzzle is?JPL?…

[Frequence]

Does anyone know who the author of the puzzle is?JPL?…

Here is the creator :
https://bitcointalk.org/index.php?action=profile;u=991321

[Frequence]

3 seconds on PYTHON! PK found.

Code:

import math, time, sys, os
from gmpy2 import mpz, powmod, invert, jacobi
import xxhash  
from sortedcontainers import SortedDict 

# Clear screen and initialize
os.system("cls||clear")
t = time.ctime()
sys.stdout.write(f"\033[?25l\033[01;33m[+] BSGS: {t}\n")
sys.stdout.flush()

# Elliptic Curve Parameters (secp256k1)
modulo = mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
order = mpz(0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141)
Gx = mpz(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
Gy = mpz(0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8)
PG = (Gx, Gy)

# Point Addition on Elliptic Curve
def add(P, Q):
    if P == (0, 0):
        return Q
    if Q == (0, 0):
        return P
    Px, Py = P
    Qx, Qy = Q
    if Px == Qx:
        if Py == Qy:
            inv_2Py = invert((Py << 1) % modulo, modulo)
            m = (3 * Px * Px * inv_2Py) % modulo
        else:
            return (0, 0)
    else:
        inv_diff_x = invert(Qx - Px, modulo)
        m = ((Qy - Py) * inv_diff_x) % modulo
    x = (m * m - Px - Qx) % modulo
    y = (m * (Px - x) - Py) % modulo
    return (x, y)

# Scalar Multiplication on Elliptic Curve
def mul(k, P=PG):
    R0, R1 = (0, 0), P
    for i in reversed(range(k.bit_length())):
        if (k >> i) & 1:
            R0, R1 = add(R0, R1), add(R1, R1)
        else:
            R1, R0 = add(R0, R1), add(R0, R0)
    return R0

# Point Subtraction
def point_subtraction(P, Q):
    Q_neg = (Q[0], (-Q[1]) % modulo)
    return add(P, Q_neg)

# Compute Y from X using curve equation
def X2Y(X, y_parity, p=modulo):
    X3_7 = (pow(X, 3, p) + 7) % p
    if jacobi(X3_7, p) != 1:
        return None
    Y = powmod(X3_7, (p + 1) >> 2, p)
    return Y if (Y & 1) == y_parity else (p - Y)

# Convert point to compressed public key
def point_to_cpub(point):
    x, y = point
    y_parity = y & 1
    prefix = '02' if y_parity == 0 else '03'
    compressed_pubkey = prefix + format(x, '064x')
    return compressed_pubkey

# Hash a compressed public key using xxhash and store only the first 8 characters
def hash_cpub(cpub):
    return xxhash.xxh64(cpub.encode()).hexdigest()[:8]

# Main Script
if __name__ == "__main__":
    # Puzzle Parameters
    puzzle = 40
    start_range, end_range = 2**(puzzle-1), (2**puzzle) - 1
    puzzle_pubkey = '03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4'

    # Parse Public Key
    if len(puzzle_pubkey) != 66:
        print("[error] Public key length invalid!")
        sys.exit(1)
    prefix = puzzle_pubkey[:2]
    X = mpz(int(puzzle_pubkey[2:], 16))
    y_parity = int(prefix) - 2
    Y = X2Y(X, y_parity)
    if Y is None:
        print("[error] Invalid compressed public key!")
        sys.exit(1)
    P = (X, Y)  # Uncompressed public key

    # Precompute m and mP for BSGS
    m = int(math.floor(math.sqrt(end_range - start_range)))
    m_P = mul(m)

    # Create Baby Table with SortedDict
    print('[+] Creating babyTable...')
    baby_table = SortedDict()  
    Ps = (0, 0)  # Start with the point at infinity
    for i in range(m + 1):
        cpub = point_to_cpub(Ps)
        cpub_hash = hash_cpub(cpub)  # Use xxhash and store only 8 characters
        baby_table[cpub_hash] = i  # Store the hash as the key and index as the value
        Ps = add(Ps, PG)  # Incrementally add PG

    # BSGS Search
    print('[+] BSGS Search in progress')
    S = point_subtraction(P, mul(start_range))
    step = 0
    st = time.time()
    while step < (end_range - start_range):
        cpub = point_to_cpub(S)
        cpub_hash = hash_cpub(cpub)  # Hash the current compressed public key
        # Check if the hash exists in the baby_table
        if cpub_hash in baby_table:
            b = baby_table[cpub_hash]
            k = start_range + step + b
            if point_to_cpub(mul(k)) == puzzle_pubkey:
                print(f'[+] m={m} step={step} b={b}')
                print(f'[+] Key found: {k}')
                print("[+] Time Spent : {0:.2f} seconds".format(time.time() - st))
                sys.exit()
        S = point_subtraction(S, m_P)
        step += m

    print('[+] Key not found')
    print("[+] Time Spent : {0:.2f} seconds".format(time.time() - st))

puzzle 40

• BSGS: Thu Feb 20 21:49:30 2025
• Creating babyTable...
• BSGS Search in progress
• m=741455 step=453895024440 b=574622
• Key found: 1003651412950
• Time Spent : 2.90 seconds

puzzle 50

• BSGS: Thu Feb 20 22:13:12 2025
• Creating babyTable...
• BSGS Search in progress
• m=23726566 step=48190529944714 b=12801738
• Key found: 611140496167764
• Time Spent : 12.71 seconds

This is the result... on a single core

P.S. For puzzles above 50, you'll need a Bloom Filter

Who wrote this code?!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Share your donation address I can see light at the end of a tunnel.

Yes, I agree that NoMachine is great for coding, but did you know it only works if you have a public key!!? That’s clearly tied to the current puzzles.

Also, there's a better option from RC that uses GPU.

Regards.

[Vilandro]

Does anyone know who the author of the puzzle is?JPL?…

Adam Back

[nomachine]

Who wrote this code?!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Share your donation address I can see light at the end of a tunnel.

I wrote it. It's based on the lightweight database for publickeys from @Mcdouglas-X3. The difference is that my script empties RAM and stores the DB in parts compressed on disk. You need a huge amount of storage. And of course the public key.

Here is C++ version

Code:

#include <iostream>
#include <atomic>
#include <memory>
#include <fstream>
#include <string>
#include <cstdlib>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <gmpxx.h>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <sys/stat.h>
#include <xxhash.h>
#include <omp.h>
#include <unistd.h>
#include <iomanip>

using namespace std;

// Constants and typedefs
typedef array<mpz_class, 2> Point;

const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16);
const mpz_class order("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16);
const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16);
const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16);
const Point PG = {Gx, Gy};
const Point Z = {0, 0};

// Global variables
int puzzle = 40;
string puzzle_pubkey = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4";
int threads = 0;
bool verbose = false;
const size_t MAX_TABLE_SIZE = 200 * 1024 * 1024; // 200MB per part

// Function declarations
void print_help();
bool validate_pubkey(const string& pubkey);
Point parse_pubkey(const string& pubkey);
inline Point add(const Point& P, const Point& Q, const mpz_class& p = modulo);
inline Point mul(const mpz_class& k, const Point& P = PG, const mpz_class& p = modulo);
inline Point point_subtraction(const Point& P, const Point& Q);
inline mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo);
inline string point_to_cpub(const Point& point);
inline string hash_cpub(const string& cpub);
void save_baby_table_part(const unordered_map<string, int>& baby_table, int part_num);
void save_baby_table(const unordered_map<string, int>& baby_table);
unordered_map<string, int> load_baby_table_part(const string& filename);
unordered_map<string, int> load_baby_table();
void delete_existing_table();
unordered_map<string, int> generate_baby_table_parallel(const mpz_class& m);

void print_help() {
    cout << "BSGS (Baby-Step Giant-Step) Elliptic Curve Cryptography Tool\n\n";
    cout << "Usage: ./bsgs [options]\n\n";
    cout << "Options:\n";
    cout << "  -p <number>     Puzzle number (default: 40)\n";
    cout << "  -k <pubkey>     Compressed public key in hex format\n";
    cout << "  -t <threads>    Number of CPU cores to use (default: all available)\n";
    cout << "  -v              Verbose output\n";
    cout << "  -h              Show this help message\n\n";
    cout << "Example:\n";
    cout << "  ./bsgs -p 40 -k 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 -t 8\n";
}

bool validate_pubkey(const string& pubkey) {
    if (pubkey.length() != 66) {
        cerr << "[error] Public key must be 66 characters long (including 02/03 prefix)\n";
        return false;
    }
    
    if (pubkey[0] != '0' || (pubkey[1] != '2' && pubkey[1] != '3')) {
        cerr << "[error] Public key must start with 02 or 03\n";
        return false;
    }
    
    for (size_t i = 2; i < pubkey.length(); i++) {
        if (!isxdigit(pubkey[i])) {
            cerr << "[error] Public key contains invalid hex characters\n";
            return false;
        }
    }
    
    return true;
}

Point parse_pubkey(const string& pubkey) {
    string prefix = pubkey.substr(0, 2);
    mpz_class X(pubkey.substr(2), 16);
    int y_parity = stoi(prefix) - 2;
    mpz_class Y = X2Y(X, y_parity);
    
    if (Y == 0) {
        cerr << "[error] Invalid compressed public key!\n";
        exit(1);
    }
    
    return {X, Y};
}

inline Point add(const Point& P, const Point& Q, const mpz_class& p) {
    if (P == Z) return Q;
    if (Q == Z) return P;
    const mpz_class& P0 = P[0];
    const mpz_class& P1 = P[1];
    const mpz_class& Q0 = Q[0];
    const mpz_class& Q1 = Q[1];
    mpz_class lmbda, num, denom, inv;
    if (P != Q) {
        num = Q1 - P1;
        denom = Q0 - P0;
    } else {
        if (P1 == 0) return Z;
        num = 3 * P0 * P0;
        denom = 2 * P1;
    }
    mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t());
    lmbda = (num * inv) % p;
    mpz_class x = (lmbda * lmbda - P0 - Q0) % p;
    if (x < 0) x += p;
    mpz_class y = (lmbda * (P0 - x) - P1) % p;
    if (y < 0) y += p;
    return {x, y};
}

inline Point mul(const mpz_class& k, const Point& P, const mpz_class& p) {
    Point R0 = Z, R1 = P;
    unsigned long bit_length = mpz_sizeinbase(k.get_mpz_t(), 2);
    for (unsigned long i = bit_length - 1; i < bit_length; --i) {
        if (mpz_tstbit(k.get_mpz_t(), i)) {
            R0 = add(R0, R1, p);
            R1 = add(R1, R1, p);
        } else {
            R1 = add(R0, R1, p);
            R0 = add(R0, R0, p);
        }
    }
    return R0;
}

inline Point point_subtraction(const Point& P, const Point& Q) {
    Point Q_neg = {Q[0], (-Q[1]) % modulo};
    return add(P, Q_neg);
}

inline mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p) {
    mpz_class X_cubed = (X * X * X) % p;
    mpz_class tmp = (X_cubed + mpz_class(7)) % p;
    mpz_class Y;
    mpz_class exp = (p + mpz_class(1)) / mpz_class(4);
    mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t());
    if ((Y % 2) != y_parity) {
        Y = p - Y;
    }
    return Y;
}

inline string point_to_cpub(const Point& point) {
    mpz_class x = point[0], y = point[1];
    int y_parity = y.get_ui() & 1;
    string prefix = y_parity == 0 ? "02" : "03";
    char buffer[65];
    mpz_get_str(buffer, 16, x.get_mpz_t());
    return prefix + string(buffer);
}

inline string hash_cpub(const string& cpub) {
    XXH64_hash_t hash = XXH64(cpub.c_str(), cpub.size(), 0);
    char buffer[17];
    snprintf(buffer, sizeof(buffer), "%016lx", hash);
    return string(buffer, 8);
}

void save_baby_table_part(const unordered_map<string, int>& baby_table, int part_num) {
    string filename = "baby_table_part_" + to_string(part_num);
    ofstream outfile(filename, ios::binary);
    if (!outfile) {
        cerr << "[error] Failed to open file for writing: " << filename << endl;
        return;
    }
    
    for (const auto& entry : baby_table) {
        outfile.write(entry.first.c_str(), 8);
        int index = entry.second;
        outfile.write(reinterpret_cast<const char*>(&index), sizeof(index));
    }
    
    if (verbose) {
        cout << "[+] Saved baby table part " << part_num << " with " << baby_table.size() << " entries" << endl;
    }
    
    string command = "pigz -9 -b 128 -f " + filename;
    FILE* pipe = popen(command.c_str(), "r");
    if (!pipe) {
        cerr << "[error] Failed to compress file: " << filename << endl;
        return;
    }
    pclose(pipe);
}

void save_baby_table(const unordered_map<string, int>& baby_table) {
    size_t current_size = 0;
    int part_num = 1;
    unordered_map<string, int> current_part;
    
    for (const auto& entry : baby_table) {
        size_t entry_size = entry.first.size() + sizeof(int);
        if (current_size + entry_size > MAX_TABLE_SIZE && !current_part.empty()) {
            save_baby_table_part(current_part, part_num++);
            current_part.clear();
            current_size = 0;
        }
        current_part.insert(entry);
        current_size += entry_size;
    }
    
    if (!current_part.empty()) {
        save_baby_table_part(current_part, part_num);
    }
}

unordered_map<string, int> load_baby_table_part(const string& filename) {
    string command = "pigz -d -c " + filename;
    FILE* pipe = popen(command.c_str(), "r");
    if (!pipe) {
        cerr << "[error] Failed to decompress file: " << filename << endl;
        return {};
    }
    
    unordered_map<string, int> baby_table_part;
    char key_buffer[9];
    int index;
    
    while (fread(key_buffer, 8, 1, pipe) == 1) {
        key_buffer[8] = '\0';
        fread(&index, sizeof(index), 1, pipe);
        baby_table_part[key_buffer] = index;
    }
    
    pclose(pipe);
    return baby_table_part;
}

unordered_map<string, int> load_baby_table() {
    unordered_map<string, int> baby_table;
    int part_num = 1;
    
    while (true) {
        string filename = "baby_table_part_" + to_string(part_num) + ".gz";
        ifstream test(filename);
        if (!test.good()) {
            if (part_num == 1) {
                cerr << "[error] No baby table parts found!" << endl;
                return {};
            }
            break;
        }
        test.close();
        
        string command = "pigz -d -c " + filename;
        FILE* pipe = popen(command.c_str(), "r");
        if (!pipe) {
            cerr << "[error] Failed to decompress file: " << filename << endl;
            return {};
        }
        
        char key[9] = {0};
        int index;
        size_t entries = 0;
        
        while (fread(key, 8, 1, pipe) == 1) {
            if (fread(&index, sizeof(int), 1, pipe) != 1) break;
            key[8] = '\0';
            baby_table[key] = index;
            entries++;
        }
        
        pclose(pipe);
        if (verbose) {
            cout << "[+] Loaded part " << part_num << " with " << entries << " entries" << endl;
        }
        part_num++;
    }
    
    cout << "[+] Loaded baby table with " << baby_table.size() << " total entries" << endl;
    return baby_table;
}

void delete_existing_table() {
    int part_num = 1;
    while (true) {
        string filename = "baby_table_part_" + to_string(part_num);
        string compressed_filename = filename + ".gz";
        
        struct stat buffer;
        bool found = false;
        
        if (stat(filename.c_str(), &buffer) == 0) {
            if (remove(filename.c_str()) != 0) {
                cerr << "[error] Failed to delete file: " << filename << endl;
            } else {
                found = true;
            }
        }
        
        if (stat(compressed_filename.c_str(), &buffer) == 0) {
            if (remove(compressed_filename.c_str()) != 0) {
                cerr << "[error] Failed to delete file: " << compressed_filename << endl;
            } else {
                found = true;
            }
        }
        
        if (!found) {
            if (part_num == 1 && verbose) {
                cout << "[+] No existing table parts found to delete" << endl;
            }
            break;
        }
        
        part_num++;
    }
}

unordered_map<string, int> generate_baby_table_parallel(const mpz_class& m) {
    const int num_threads = threads > 0 ? threads : omp_get_max_threads();
    const unsigned long total_entries = m.get_ui();
    const size_t max_part_size = MAX_TABLE_SIZE * 0.99; // 99% threshold
    std::atomic<int> parts_created(0);
    std::atomic<size_t> current_part_size(0);
    std::atomic<size_t> total_entries_written(0);
    
    system("rm -f baby_table_part_* baby_table_part_*.gz 2>/dev/null");
  
    cout << "[+] Generating " << total_entries << " baby steps" << endl;

    #pragma omp parallel num_threads(num_threads)
    {
        vector<pair<string, int>> local_buffer;
        local_buffer.reserve(100000);

        #pragma omp for schedule(dynamic, 100000)
        for (unsigned long i = 0; i < total_entries; ++i) {
            Point P = mul(i);
            string cpub_hash = hash_cpub(point_to_cpub(P));
            local_buffer.emplace_back(cpub_hash, i);

            if (local_buffer.size() >= 100000) {
                #pragma omp critical
                {
                    int current_part = parts_created + 1;
                    string filename = "baby_table_part_" + to_string(current_part);
                    ofstream outfile(filename, ios::binary | ios::app);
                    if (outfile) {
                        for (const auto& entry : local_buffer) {
                            outfile.write(entry.first.c_str(), 8);
                            outfile.write(reinterpret_cast<const char*>(&entry.second), sizeof(int));
                            total_entries_written++;
                            current_part_size += 12;
                            
                            if (current_part_size >= max_part_size) {
                                outfile.close();
                                string cmd = "pigz -9 -b 128 -f " + filename;
                                system(cmd.c_str());
                                parts_created++;
                                current_part_size = 0;
                            }
                        }
                    }
                    local_buffer.clear();
                }
            }
        }

        #pragma omp critical
        {
            if (!local_buffer.empty()) {
                int current_part = parts_created + 1;
                string filename = "baby_table_part_" + to_string(current_part);
                ofstream outfile(filename, ios::binary | ios::app);
                if (outfile) {
                    for (const auto& entry : local_buffer) {
                        outfile.write(entry.first.c_str(), 8);
                        outfile.write(reinterpret_cast<const char*>(&entry.second), sizeof(int));
                        total_entries_written++;
                    }
                    outfile.close();
                    string cmd = "pigz -9 -b 128 -f " + filename;
                    system(cmd.c_str());
                    parts_created++;
                }
            }
        }
    }

    cout << "[+] Generated " << parts_created << " compressed parts ("
         << total_entries_written << " total entries) " << endl;

    return {};
}

int main(int argc, char* argv[]) {
    // Parse command line arguments
    int opt;
    while ((opt = getopt(argc, argv, "p:k:t:vh")) != -1) {
        switch (opt) {
            case 'p':
                puzzle = atoi(optarg);
                if (puzzle < 1 || puzzle > 256) {
                    cerr << "[error] Invalid puzzle number (must be between 1-256)\n";
                    print_help();
                    return 1;
                }
                break;
            case 'k':
                puzzle_pubkey = optarg;
                if (!validate_pubkey(puzzle_pubkey)) {
                    print_help();
                    return 1;
                }
                break;
            case 't':
                threads = atoi(optarg);
                if (threads < 1) {
                    cerr << "[error] Thread count must be at least 1\n";
                    print_help();
                    return 1;
                }
                break;
            case 'v':
                verbose = true;
                break;
            case 'h':
            default:
                print_help();
                return 0;
        }
    }

    // Initialize OpenMP threads
    if (threads > 0) {
        omp_set_num_threads(threads);
    }
    int actual_threads = omp_get_max_threads();

    // Print configuration
    time_t currentTime = time(nullptr);
    cout << "\n\033[01;33m[+]\033[32m BSGS Started: \033[01;33m" << ctime(&currentTime);
    cout << "\033[0m[+] Puzzle: " << puzzle << endl;
    cout << "[+] Public Key: " << puzzle_pubkey << endl;
    cout << "[+] Using " << actual_threads << " CPU cores" << endl;

    // Initialize range and point
    mpz_class start_range = mpz_class(1) << (puzzle - 1);
    mpz_class end_range = (mpz_class(1) << puzzle) - 1;
    Point P = parse_pubkey(puzzle_pubkey);

    // Calculate m and generate baby table
    mpz_class m = sqrt(end_range - start_range);
    m = m * 4;
    Point m_P = mul(m);

    if (verbose) {
        cout << "[+] Range: 2^" << (puzzle-1) << " to 2^" << puzzle << "-1" << endl;
        cout << "[+] Baby-step count (m): " << m << endl;
    }

    delete_existing_table();

    cout << "[+] Generating baby table..." << endl;
    auto baby_table = generate_baby_table_parallel(m);

    cout << "[+] Loading baby table..." << endl;
    baby_table = load_baby_table();
    if (baby_table.empty()) {
        cerr << "[error] Failed to load baby table\n";
        return 1;
    }

    cout << "[+] Starting BSGS search..." << endl;
    Point S = point_subtraction(P, mul(start_range));
    mpz_class step = 0;
    bool found = false;
    mpz_class found_key;
    
    auto st = chrono::high_resolution_clock::now();
    
    #pragma omp parallel
    {
        Point local_S = S;
        mpz_class local_step = step;
        
        #pragma omp for schedule(dynamic)
        for (int i = 0; i < actual_threads; ++i) {
            while (local_step < (end_range - start_range)) {
                #pragma omp flush(found)
                if (found) break;
                
                string cpub = point_to_cpub(local_S);
                string cpub_hash = hash_cpub(cpub);
                auto it = baby_table.find(cpub_hash);
                if (it != baby_table.end()) {
                    int b = it->second;
                    mpz_class k = start_range + local_step + b;
                    if (point_to_cpub(mul(k)) == puzzle_pubkey) {
                        #pragma omp critical
                        {
                            if (!found) {
                                found = true;
                                found_key = k;
                                auto et = chrono::high_resolution_clock::now();
                                chrono::duration<double> elapsed = et - st;
                                
                                cout << "\n\033[01;32m[+] Solution found!\033[0m" << endl;
                                cout << "[+] Private key: " << k << endl;
                                cout << "[+] Hex: 0x" << hex << k << dec << endl;
                                cout << "[+] Time elapsed: " << elapsed.count() << " seconds\n";
                            }
                        }
                        #pragma omp flush(found)
                        break;
                    }
                }
                local_S = point_subtraction(local_S, m_P);
                local_step += m;
            }
        }
    }

    if (!found) {
        auto et = chrono::high_resolution_clock::now();
        chrono::duration<double> elapsed = et - st;
        cout << "\n\033[01;31m[!] Key not found in the specified range\033[0m" << endl;
        cout << "[+] Time elapsed: " << elapsed.count() << " seconds\n";
    }

    return 0;
}

Makefile

Code:

# Detect OS
UNAME_S := $(shell uname -s)

# Enable static linking by default (change to 'no' to use dynamic linking)
STATIC_LINKING = yes

# Compiler settings based on OS
ifeq ($(UNAME_S),Linux)
# Linux settings

# Compiler
CXX = g++

# Compiler flags
CXXFLAGS = -m64 -std=c++17 -march=native -mtune=native -Ofast -mssse3 -Wall -Wextra \
           -funroll-loops -ftree-vectorize -fstrict-aliasing -fno-semantic-interposition \
           -fvect-cost-model=unlimited -fno-trapping-math -fipa-ra -flto -fopenmp \
           -mavx2 -mbmi2 -madx
LDFLAGS = -lgmp -lgmpxx -lxxhash

# Source files
SRCS = bsgs.cpp

# Object files
OBJS = $(SRCS:.cpp=.o)

# Target executable
TARGET = bsgs 

# Default target
all: $(TARGET)

# Link the object files to create the executable
$(TARGET): $(OBJS)
	$(CXX) $(CXXFLAGS) -o $(TARGET) $(OBJS) $(LDFLAGS)
	rm -f $(OBJS) && chmod +x $(TARGET)

# Compile each source file into an object file
%.o: %.cpp
	$(CXX) $(CXXFLAGS) -c $< -o $@

# Clean up build files
clean:
	@echo "Cleaning..."
	rm -f $(OBJS) $(TARGET)

.PHONY: all clean

else
# Windows settings (MinGW-w64)

# Compiler
CXX = g++

# Check if compiler is found
CHECK_COMPILER := $(shell which $(CXX) 2>/dev/null)

# Add MSYS path if the compiler is not found
ifeq ($(CHECK_COMPILER),)
  $(info Compiler not found. Adding MSYS path to the environment...)
  SHELL := cmd
  PATH := C:\msys64\mingw64\bin;$(PATH)
endif

# Compiler flags
CXXFLAGS = -m64 -std=c++17 -march=native -mtune=native -Ofast -mssse3 -Wall -Wextra \
           -funroll-loops -ftree-vectorize -fstrict-aliasing -fno-semantic-interposition \
           -fvect-cost-model=unlimited -fno-trapping-math -fipa-ra -flto -fopenmp \
           -mavx2 -mbmi2 -madx
LDFLAGS = -lgmp -lgmpxx -lxxhash

# Add -static flag if STATIC_LINKING is enabled
ifeq ($(STATIC_LINKING),yes)
    LDFLAGS += -static
else
    $(info Dynamic linking will be used. Ensure required DLLs are distributed)
endif

# Source files
SRCS = bsgs.cpp

# Object files
OBJS = $(SRCS:.cpp=.o)

# Target executable
TARGET = bsgs.exe

# Default target
all: $(TARGET)

# Link the object files to create the executable
$(TARGET): $(OBJS)
	$(CXX) $(CXXFLAGS) -o $(TARGET) $(OBJS) $(LDFLAGS)
	del /q $(OBJS) 2>nul

# Compile each source file into an object file
%.o: %.cpp
	$(CXX) $(CXXFLAGS) -c $< -o $@

# Clean up build files
clean:
	@echo Cleaning...
	del /q $(OBJS) $(TARGET) 2>nul

.PHONY: all clean
endif

dependencies:

sudo apt install libgmp-dev libomp-dev xxhash pigz

• BSGS Started: Wed Jun  4 01:56:48 2025
• Puzzle: 40
• Public Key: 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4
• Using 12 CPU cores
• Generating baby table...
• Generating 2965820 baby steps
• Generated 1 compressed parts (2965820 total entries)
• Loading baby table...
• Loaded baby table with 2964816 total entries
• Starting BSGS search...
• Solution found!
• Private key: 1003651412950
• Hex: 0xe9ae4933d6
• Time elapsed: 0.612888 seconds

# ./bsgs -p 50  -k 03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6 -t 12

• BSGS Started: Wed Jun  4 02:20:52 2025
• Puzzle: 50
• Public Key: 03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6
• Using 12 CPU cores
• Generating baby table...
• Generating 94906264 baby steps
• Generated 6 compressed parts (94906264 total entries)
• Loading baby table...
• Loaded baby table with 93398236 total entries
• Starting BSGS search...
• Solution found!
• Private key: 611140496167764
• Hex: 0x22bd43c2e9354
• Time elapsed: 4.83157 seconds

P.S. This can be easily modified to use a Bloom Filter. And probably the GPU version. Use it for whatever you want.

[kTimesG]

The most amusing stuff using mutex locks and creating bloomfilters with the same inputs two times in row.

Code:

alexander@alexander-home:~/Documents/Test_Dir/Point_Search_GMP$ diff bloom1B.bf bloom1.bf
Binary files bloom1B.bf and bloom1.bf differ

What did you expect? I looked at your update, and you are simply creating multiple mutexes, one for each thread that runs process_chunk. And locking the entire loop. Basically protecting nothing.

That's not mutexes are for. You only need a single mutex, and you only need to lock the "bf.insert" call, not the entire loop (or else the entire loops will be exclusive).

I'd personally move the mutex to the bloom filter code, and further block only the actual code that accesses data which can potentially be shared (for example, the hashing part probably doesn't need exclusive access).

But I'm glad that at least you got to a case where you can clearly see that the output is wrong, when synchronization is missing. So which one of those 2 outputs is the right one? You'll never know, since they were basically in a race condition, running both in parallel under different mutexes (so, identical as not having a mutex at all).

If you wanna go fancy you can implement a multi-mutex scheme, one for each some memory area size, and only lock the specific mutex for the area the bloom filter writes. This may increase throughput, or it may not, the right balance needs to be found by trial and error. But this is not a programming thread, after all.

LE: another option is to compute the points in parallel, and queue them in a producer-consumer fashion. And consuming the queue in a single thread, that only does the BF insertions. This simply moves the sync on the queue itself, of course, if you don't want to mess with the bloom class.

[vneos]

Does anyone know who the author of the puzzle is?JPL?…

Adam Back

I think it's satoshi himself. The way @satoshi and @saatoshi_rising break up their sentences is the same.

Looking at their posts, they both like to leave two spaces after a period.

@saatoshi_rising: "I am the creator" is also quite thought-provoking. Does it refer to the creator of the puzzle, or the creator of bitcoin?

Of course, this is just my guess.

[axwfae]

Who wrote this code?!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Share your donation address I can see light at the end of a tunnel.

I wrote it. It's based on the lightweight database for publickeys from @Mcdouglas-X3. The difference is that my script empties RAM and stores the DB in parts compressed on disk. You need a huge amount of storage. And of course the public key.

Here is C++ version

Code:

#include <iostream>
#include <atomic>
#include <memory>
#include <fstream>
#include <string>
#include <cstdlib>
#include <vector>
#include <unordered_map>
#include <cmath>
#include <gmpxx.h>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <sys/stat.h>
#include <xxhash.h>
#include <omp.h>
#include <unistd.h>
#include <iomanip>

using namespace std;

// Constants and typedefs
typedef array<mpz_class, 2> Point;

const mpz_class modulo("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", 16);
const mpz_class order("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16);
const mpz_class Gx("79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", 16);
const mpz_class Gy("483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8", 16);
const Point PG = {Gx, Gy};
const Point Z = {0, 0};

// Global variables
int puzzle = 40;
string puzzle_pubkey = "03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4";
int threads = 0;
bool verbose = false;
const size_t MAX_TABLE_SIZE = 200 * 1024 * 1024; // 200MB per part

// Function declarations
void print_help();
bool validate_pubkey(const string& pubkey);
Point parse_pubkey(const string& pubkey);
inline Point add(const Point& P, const Point& Q, const mpz_class& p = modulo);
inline Point mul(const mpz_class& k, const Point& P = PG, const mpz_class& p = modulo);
inline Point point_subtraction(const Point& P, const Point& Q);
inline mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p = modulo);
inline string point_to_cpub(const Point& point);
inline string hash_cpub(const string& cpub);
void save_baby_table_part(const unordered_map<string, int>& baby_table, int part_num);
void save_baby_table(const unordered_map<string, int>& baby_table);
unordered_map<string, int> load_baby_table_part(const string& filename);
unordered_map<string, int> load_baby_table();
void delete_existing_table();
unordered_map<string, int> generate_baby_table_parallel(const mpz_class& m);

void print_help() {
    cout << "BSGS (Baby-Step Giant-Step) Elliptic Curve Cryptography Tool\n\n";
    cout << "Usage: ./bsgs [options]\n\n";
    cout << "Options:\n";
    cout << "  -p <number>     Puzzle number (default: 40)\n";
    cout << "  -k <pubkey>     Compressed public key in hex format\n";
    cout << "  -t <threads>    Number of CPU cores to use (default: all available)\n";
    cout << "  -v              Verbose output\n";
    cout << "  -h              Show this help message\n\n";
    cout << "Example:\n";
    cout << "  ./bsgs -p 40 -k 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4 -t 8\n";
}

bool validate_pubkey(const string& pubkey) {
    if (pubkey.length() != 66) {
        cerr << "[error] Public key must be 66 characters long (including 02/03 prefix)\n";
        return false;
    }
    
    if (pubkey[0] != '0' || (pubkey[1] != '2' && pubkey[1] != '3')) {
        cerr << "[error] Public key must start with 02 or 03\n";
        return false;
    }
    
    for (size_t i = 2; i < pubkey.length(); i++) {
        if (!isxdigit(pubkey[i])) {
            cerr << "[error] Public key contains invalid hex characters\n";
            return false;
        }
    }
    
    return true;
}

Point parse_pubkey(const string& pubkey) {
    string prefix = pubkey.substr(0, 2);
    mpz_class X(pubkey.substr(2), 16);
    int y_parity = stoi(prefix) - 2;
    mpz_class Y = X2Y(X, y_parity);
    
    if (Y == 0) {
        cerr << "[error] Invalid compressed public key!\n";
        exit(1);
    }
    
    return {X, Y};
}

inline Point add(const Point& P, const Point& Q, const mpz_class& p) {
    if (P == Z) return Q;
    if (Q == Z) return P;
    const mpz_class& P0 = P[0];
    const mpz_class& P1 = P[1];
    const mpz_class& Q0 = Q[0];
    const mpz_class& Q1 = Q[1];
    mpz_class lmbda, num, denom, inv;
    if (P != Q) {
        num = Q1 - P1;
        denom = Q0 - P0;
    } else {
        if (P1 == 0) return Z;
        num = 3 * P0 * P0;
        denom = 2 * P1;
    }
    mpz_invert(inv.get_mpz_t(), denom.get_mpz_t(), p.get_mpz_t());
    lmbda = (num * inv) % p;
    mpz_class x = (lmbda * lmbda - P0 - Q0) % p;
    if (x < 0) x += p;
    mpz_class y = (lmbda * (P0 - x) - P1) % p;
    if (y < 0) y += p;
    return {x, y};
}

inline Point mul(const mpz_class& k, const Point& P, const mpz_class& p) {
    Point R0 = Z, R1 = P;
    unsigned long bit_length = mpz_sizeinbase(k.get_mpz_t(), 2);
    for (unsigned long i = bit_length - 1; i < bit_length; --i) {
        if (mpz_tstbit(k.get_mpz_t(), i)) {
            R0 = add(R0, R1, p);
            R1 = add(R1, R1, p);
        } else {
            R1 = add(R0, R1, p);
            R0 = add(R0, R0, p);
        }
    }
    return R0;
}

inline Point point_subtraction(const Point& P, const Point& Q) {
    Point Q_neg = {Q[0], (-Q[1]) % modulo};
    return add(P, Q_neg);
}

inline mpz_class X2Y(const mpz_class& X, int y_parity, const mpz_class& p) {
    mpz_class X_cubed = (X * X * X) % p;
    mpz_class tmp = (X_cubed + mpz_class(7)) % p;
    mpz_class Y;
    mpz_class exp = (p + mpz_class(1)) / mpz_class(4);
    mpz_powm(Y.get_mpz_t(), tmp.get_mpz_t(), exp.get_mpz_t(), p.get_mpz_t());
    if ((Y % 2) != y_parity) {
        Y = p - Y;
    }
    return Y;
}

inline string point_to_cpub(const Point& point) {
    mpz_class x = point[0], y = point[1];
    int y_parity = y.get_ui() & 1;
    string prefix = y_parity == 0 ? "02" : "03";
    char buffer[65];
    mpz_get_str(buffer, 16, x.get_mpz_t());
    return prefix + string(buffer);
}

inline string hash_cpub(const string& cpub) {
    XXH64_hash_t hash = XXH64(cpub.c_str(), cpub.size(), 0);
    char buffer[17];
    snprintf(buffer, sizeof(buffer), "%016lx", hash);
    return string(buffer, 8);
}

void save_baby_table_part(const unordered_map<string, int>& baby_table, int part_num) {
    string filename = "baby_table_part_" + to_string(part_num);
    ofstream outfile(filename, ios::binary);
    if (!outfile) {
        cerr << "[error] Failed to open file for writing: " << filename << endl;
        return;
    }
    
    for (const auto& entry : baby_table) {
        outfile.write(entry.first.c_str(), 8);
        int index = entry.second;
        outfile.write(reinterpret_cast<const char*>(&index), sizeof(index));
    }
    
    if (verbose) {
        cout << "[+] Saved baby table part " << part_num << " with " << baby_table.size() << " entries" << endl;
    }
    
    string command = "pigz -9 -b 128 -f " + filename;
    FILE* pipe = popen(command.c_str(), "r");
    if (!pipe) {
        cerr << "[error] Failed to compress file: " << filename << endl;
        return;
    }
    pclose(pipe);
}

void save_baby_table(const unordered_map<string, int>& baby_table) {
    size_t current_size = 0;
    int part_num = 1;
    unordered_map<string, int> current_part;
    
    for (const auto& entry : baby_table) {
        size_t entry_size = entry.first.size() + sizeof(int);
        if (current_size + entry_size > MAX_TABLE_SIZE && !current_part.empty()) {
            save_baby_table_part(current_part, part_num++);
            current_part.clear();
            current_size = 0;
        }
        current_part.insert(entry);
        current_size += entry_size;
    }
    
    if (!current_part.empty()) {
        save_baby_table_part(current_part, part_num);
    }
}

unordered_map<string, int> load_baby_table_part(const string& filename) {
    string command = "pigz -d -c " + filename;
    FILE* pipe = popen(command.c_str(), "r");
    if (!pipe) {
        cerr << "[error] Failed to decompress file: " << filename << endl;
        return {};
    }
    
    unordered_map<string, int> baby_table_part;
    char key_buffer[9];
    int index;
    
    while (fread(key_buffer, 8, 1, pipe) == 1) {
        key_buffer[8] = '\0';
        fread(&index, sizeof(index), 1, pipe);
        baby_table_part[key_buffer] = index;
    }
    
    pclose(pipe);
    return baby_table_part;
}

unordered_map<string, int> load_baby_table() {
    unordered_map<string, int> baby_table;
    int part_num = 1;
    
    while (true) {
        string filename = "baby_table_part_" + to_string(part_num) + ".gz";
        ifstream test(filename);
        if (!test.good()) {
            if (part_num == 1) {
                cerr << "[error] No baby table parts found!" << endl;
                return {};
            }
            break;
        }
        test.close();
        
        string command = "pigz -d -c " + filename;
        FILE* pipe = popen(command.c_str(), "r");
        if (!pipe) {
            cerr << "[error] Failed to decompress file: " << filename << endl;
            return {};
        }
        
        char key[9] = {0};
        int index;
        size_t entries = 0;
        
        while (fread(key, 8, 1, pipe) == 1) {
            if (fread(&index, sizeof(int), 1, pipe) != 1) break;
            key[8] = '\0';
            baby_table[key] = index;
            entries++;
        }
        
        pclose(pipe);
        if (verbose) {
            cout << "[+] Loaded part " << part_num << " with " << entries << " entries" << endl;
        }
        part_num++;
    }
    
    cout << "[+] Loaded baby table with " << baby_table.size() << " total entries" << endl;
    return baby_table;
}

void delete_existing_table() {
    int part_num = 1;
    while (true) {
        string filename = "baby_table_part_" + to_string(part_num);
        string compressed_filename = filename + ".gz";
        
        struct stat buffer;
        bool found = false;
        
        if (stat(filename.c_str(), &buffer) == 0) {
            if (remove(filename.c_str()) != 0) {
                cerr << "[error] Failed to delete file: " << filename << endl;
            } else {
                found = true;
            }
        }
        
        if (stat(compressed_filename.c_str(), &buffer) == 0) {
            if (remove(compressed_filename.c_str()) != 0) {
                cerr << "[error] Failed to delete file: " << compressed_filename << endl;
            } else {
                found = true;
            }
        }
        
        if (!found) {
            if (part_num == 1 && verbose) {
                cout << "[+] No existing table parts found to delete" << endl;
            }
            break;
        }
        
        part_num++;
    }
}

unordered_map<string, int> generate_baby_table_parallel(const mpz_class& m) {
    const int num_threads = threads > 0 ? threads : omp_get_max_threads();
    const unsigned long total_entries = m.get_ui();
    const size_t max_part_size = MAX_TABLE_SIZE * 0.99; // 99% threshold
    std::atomic<int> parts_created(0);
    std::atomic<size_t> current_part_size(0);
    std::atomic<size_t> total_entries_written(0);
    
    system("rm -f baby_table_part_* baby_table_part_*.gz 2>/dev/null");
  
    cout << "[+] Generating " << total_entries << " baby steps" << endl;

    #pragma omp parallel num_threads(num_threads)
    {
        vector<pair<string, int>> local_buffer;
        local_buffer.reserve(100000);

        #pragma omp for schedule(dynamic, 100000)
        for (unsigned long i = 0; i < total_entries; ++i) {
            Point P = mul(i);
            string cpub_hash = hash_cpub(point_to_cpub(P));
            local_buffer.emplace_back(cpub_hash, i);

            if (local_buffer.size() >= 100000) {
                #pragma omp critical
                {
                    int current_part = parts_created + 1;
                    string filename = "baby_table_part_" + to_string(current_part);
                    ofstream outfile(filename, ios::binary | ios::app);
                    if (outfile) {
                        for (const auto& entry : local_buffer) {
                            outfile.write(entry.first.c_str(), 8);
                            outfile.write(reinterpret_cast<const char*>(&entry.second), sizeof(int));
                            total_entries_written++;
                            current_part_size += 12;
                            
                            if (current_part_size >= max_part_size) {
                                outfile.close();
                                string cmd = "pigz -9 -b 128 -f " + filename;
                                system(cmd.c_str());
                                parts_created++;
                                current_part_size = 0;
                            }
                        }
                    }
                    local_buffer.clear();
                }
            }
        }

        #pragma omp critical
        {
            if (!local_buffer.empty()) {
                int current_part = parts_created + 1;
                string filename = "baby_table_part_" + to_string(current_part);
                ofstream outfile(filename, ios::binary | ios::app);
                if (outfile) {
                    for (const auto& entry : local_buffer) {
                        outfile.write(entry.first.c_str(), 8);
                        outfile.write(reinterpret_cast<const char*>(&entry.second), sizeof(int));
                        total_entries_written++;
                    }
                    outfile.close();
                    string cmd = "pigz -9 -b 128 -f " + filename;
                    system(cmd.c_str());
                    parts_created++;
                }
            }
        }
    }

    cout << "[+] Generated " << parts_created << " compressed parts ("
         << total_entries_written << " total entries) " << endl;

    return {};
}

int main(int argc, char* argv[]) {
    // Parse command line arguments
    int opt;
    while ((opt = getopt(argc, argv, "p:k:t:vh")) != -1) {
        switch (opt) {
            case 'p':
                puzzle = atoi(optarg);
                if (puzzle < 1 || puzzle > 256) {
                    cerr << "[error] Invalid puzzle number (must be between 1-256)\n";
                    print_help();
                    return 1;
                }
                break;
            case 'k':
                puzzle_pubkey = optarg;
                if (!validate_pubkey(puzzle_pubkey)) {
                    print_help();
                    return 1;
                }
                break;
            case 't':
                threads = atoi(optarg);
                if (threads < 1) {
                    cerr << "[error] Thread count must be at least 1\n";
                    print_help();
                    return 1;
                }
                break;
            case 'v':
                verbose = true;
                break;
            case 'h':
            default:
                print_help();
                return 0;
        }
    }

    // Initialize OpenMP threads
    if (threads > 0) {
        omp_set_num_threads(threads);
    }
    int actual_threads = omp_get_max_threads();

    // Print configuration
    time_t currentTime = time(nullptr);
    cout << "\n\033[01;33m[+]\033[32m BSGS Started: \033[01;33m" << ctime(&currentTime);
    cout << "\033[0m[+] Puzzle: " << puzzle << endl;
    cout << "[+] Public Key: " << puzzle_pubkey << endl;
    cout << "[+] Using " << actual_threads << " CPU cores" << endl;

    // Initialize range and point
    mpz_class start_range = mpz_class(1) << (puzzle - 1);
    mpz_class end_range = (mpz_class(1) << puzzle) - 1;
    Point P = parse_pubkey(puzzle_pubkey);

    // Calculate m and generate baby table
    mpz_class m = sqrt(end_range - start_range);
    m = m * 4;
    Point m_P = mul(m);

    if (verbose) {
        cout << "[+] Range: 2^" << (puzzle-1) << " to 2^" << puzzle << "-1" << endl;
        cout << "[+] Baby-step count (m): " << m << endl;
    }

    delete_existing_table();

    cout << "[+] Generating baby table..." << endl;
    auto baby_table = generate_baby_table_parallel(m);

    cout << "[+] Loading baby table..." << endl;
    baby_table = load_baby_table();
    if (baby_table.empty()) {
        cerr << "[error] Failed to load baby table\n";
        return 1;
    }

    cout << "[+] Starting BSGS search..." << endl;
    Point S = point_subtraction(P, mul(start_range));
    mpz_class step = 0;
    bool found = false;
    mpz_class found_key;
    
    auto st = chrono::high_resolution_clock::now();
    
    #pragma omp parallel
    {
        Point local_S = S;
        mpz_class local_step = step;
        
        #pragma omp for schedule(dynamic)
        for (int i = 0; i < actual_threads; ++i) {
            while (local_step < (end_range - start_range)) {
                #pragma omp flush(found)
                if (found) break;
                
                string cpub = point_to_cpub(local_S);
                string cpub_hash = hash_cpub(cpub);
                auto it = baby_table.find(cpub_hash);
                if (it != baby_table.end()) {
                    int b = it->second;
                    mpz_class k = start_range + local_step + b;
                    if (point_to_cpub(mul(k)) == puzzle_pubkey) {
                        #pragma omp critical
                        {
                            if (!found) {
                                found = true;
                                found_key = k;
                                auto et = chrono::high_resolution_clock::now();
                                chrono::duration<double> elapsed = et - st;
                                
                                cout << "\n\033[01;32m[+] Solution found!\033[0m" << endl;
                                cout << "[+] Private key: " << k << endl;
                                cout << "[+] Hex: 0x" << hex << k << dec << endl;
                                cout << "[+] Time elapsed: " << elapsed.count() << " seconds\n";
                            }
                        }
                        #pragma omp flush(found)
                        break;
                    }
                }
                local_S = point_subtraction(local_S, m_P);
                local_step += m;
            }
        }
    }

    if (!found) {
        auto et = chrono::high_resolution_clock::now();
        chrono::duration<double> elapsed = et - st;
        cout << "\n\033[01;31m[!] Key not found in the specified range\033[0m" << endl;
        cout << "[+] Time elapsed: " << elapsed.count() << " seconds\n";
    }

    return 0;
}

Makefile

Code:

# Detect OS
UNAME_S := $(shell uname -s)

# Enable static linking by default (change to 'no' to use dynamic linking)
STATIC_LINKING = yes

# Compiler settings based on OS
ifeq ($(UNAME_S),Linux)
# Linux settings

# Compiler
CXX = g++

# Compiler flags
CXXFLAGS = -m64 -std=c++17 -march=native -mtune=native -Ofast -mssse3 -Wall -Wextra \
           -funroll-loops -ftree-vectorize -fstrict-aliasing -fno-semantic-interposition \
           -fvect-cost-model=unlimited -fno-trapping-math -fipa-ra -flto -fopenmp \
           -mavx2 -mbmi2 -madx
LDFLAGS = -lgmp -lgmpxx -lxxhash

# Source files
SRCS = bsgs.cpp

# Object files
OBJS = $(SRCS:.cpp=.o)

# Target executable
TARGET = bsgs 

# Default target
all: $(TARGET)

# Link the object files to create the executable
$(TARGET): $(OBJS)
	$(CXX) $(CXXFLAGS) -o $(TARGET) $(OBJS) $(LDFLAGS)
	rm -f $(OBJS) && chmod +x $(TARGET)

# Compile each source file into an object file
%.o: %.cpp
	$(CXX) $(CXXFLAGS) -c $< -o $@

# Clean up build files
clean:
	@echo "Cleaning..."
	rm -f $(OBJS) $(TARGET)

.PHONY: all clean

else
# Windows settings (MinGW-w64)

# Compiler
CXX = g++

# Check if compiler is found
CHECK_COMPILER := $(shell which $(CXX) 2>/dev/null)

# Add MSYS path if the compiler is not found
ifeq ($(CHECK_COMPILER),)
  $(info Compiler not found. Adding MSYS path to the environment...)
  SHELL := cmd
  PATH := C:\msys64\mingw64\bin;$(PATH)
endif

# Compiler flags
CXXFLAGS = -m64 -std=c++17 -march=native -mtune=native -Ofast -mssse3 -Wall -Wextra \
           -funroll-loops -ftree-vectorize -fstrict-aliasing -fno-semantic-interposition \
           -fvect-cost-model=unlimited -fno-trapping-math -fipa-ra -flto -fopenmp \
           -mavx2 -mbmi2 -madx
LDFLAGS = -lgmp -lgmpxx -lxxhash

# Add -static flag if STATIC_LINKING is enabled
ifeq ($(STATIC_LINKING),yes)
    LDFLAGS += -static
else
    $(info Dynamic linking will be used. Ensure required DLLs are distributed)
endif

# Source files
SRCS = bsgs.cpp

# Object files
OBJS = $(SRCS:.cpp=.o)

# Target executable
TARGET = bsgs.exe

# Default target
all: $(TARGET)

# Link the object files to create the executable
$(TARGET): $(OBJS)
	$(CXX) $(CXXFLAGS) -o $(TARGET) $(OBJS) $(LDFLAGS)
	del /q $(OBJS) 2>nul

# Compile each source file into an object file
%.o: %.cpp
	$(CXX) $(CXXFLAGS) -c $< -o $@

# Clean up build files
clean:
	@echo Cleaning...
	del /q $(OBJS) $(TARGET) 2>nul

.PHONY: all clean
endif

dependencies:

sudo apt install libgmp-dev libomp-dev xxhash pigz

• BSGS Started: Wed Jun  4 01:56:48 2025
• Puzzle: 40
• Public Key: 03a2efa402fd5268400c77c20e574ba86409ededee7c4020e4b9f0edbee53de0d4
• Using 12 CPU cores
• Generating baby table...
• Generating 2965820 baby steps
• Generated 1 compressed parts (2965820 total entries)
• Loading baby table...
• Loaded baby table with 2964816 total entries
• Starting BSGS search...
• Solution found!
• Private key: 1003651412950
• Hex: 0xe9ae4933d6
• Time elapsed: 0.612888 seconds

# ./bsgs -p 50  -k 03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6 -t 12

• BSGS Started: Wed Jun  4 02:20:52 2025
• Puzzle: 50
• Public Key: 03f46f41027bbf44fafd6b059091b900dad41e6845b2241dc3254c7cdd3c5a16c6
• Using 12 CPU cores
• Generating baby table...
• Generating 94906264 baby steps
• Generated 6 compressed parts (94906264 total entries)
• Loading baby table...
• Loaded baby table with 93398236 total entries
• Starting BSGS search...
• Solution found!
• Private key: 611140496167764
• Hex: 0x22bd43c2e9354
• Time elapsed: 4.83157 seconds

P.S. This can be easily modified to use a Bloom Filter. And probably the GPU version. Use it for whatever you want.

make  fail  , 

1. sudo apt install libxxhash-dev
2. bsgs.cpp   add  " #include <array>"

I'm very sorry, my English is not good, I can only explain it this way

[Akito S. M. Hosana]

make  fail  , 

1. sudo apt install libxxhash-dev
2. bsgs.cpp   add  " #include <array>"

I'm very sorry, my English is not good, I can only explain it this way

Yep. On Windows it must be like this. But he doesn't have Windows to see.