Quote from: Nuclearkeys on June 03, 2025, 09:55:06 PM

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:

Quote

sudo apt install libgmp-dev libomp-dev xxhash pigz

Quote

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

Quote

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.