grind.py

import secrets
from statistics import mean

# secp256k1 parameters
p = 2**256 - 2**32 - 977
b = 7  # y^2 = x^3 + 7

def is_quadratic_residue(n):
    """Return True if n is a quadratic residue mod p (including 0)."""
    if n == 0:
        return True
    # Euler's criterion: n^((p-1)/2) mod p is 1 for residues, p-1 for non-residues
    return pow(n, (p - 1) // 2, p) == 1

def sqrt_mod_p(n):
    """
    Compute sqrt(n) mod p for secp256k1 (p % 4 == 3).
    Assumes n is a quadratic residue mod p.
    """
    if n == 0:
        return 0
    # For p ≡ 3 (mod 4), sqrt is n^((p+1)/4) mod p
    return pow(n, (p + 1) // 4, p)

def embed_payload_as_pubkey(payload: bytes):
    """
    Given a 31-byte payload, grind a 1-byte nonce until
    payload || nonce is an x-coordinate for a valid secp256k1 point.

    Returns (compressed_pubkey_bytes, nonce, attempts).
    """
    assert len(payload) == 31, "Payload must be exactly 31 bytes"

    attempts = 0
    for nonce in range(256):
        attempts += 1

        x_bytes = payload + bytes([nonce])
        x = int.from_bytes(x_bytes, "big")

        # Very rarely x >= p, but we handle it anyway.
        if x >= p:
            continue

        rhs = (pow(x, 3, p) + b) % p  # x^3 + 7 mod p

        if not is_quadratic_residue(rhs):
            continue

        # We have a valid point; compute y to get the correct prefix.
        y = sqrt_mod_p(rhs)

        # Choose the even/odd y that matches the compressed key rules.
        prefix = 0x02 | (y & 1)  # 0x02 if y even, 0x03 if y odd

        compressed_pubkey = bytes([prefix]) + x_bytes
        return compressed_pubkey, nonce, attempts

    raise RuntimeError("Failed to embed payload as pubkey after 256 nonces")

def demo(trials=1000):
    attempts_list = []

    for i in range(trials):
        payload = secrets.token_bytes(31)
        pubkey, nonce, attempts = embed_payload_as_pubkey(payload)
        attempts_list.append(attempts)

        if i < 3:  # print a few examples
            print(f"Example #{i+1}")
            print(f"  payload: {payload.hex()}")
            print(f"  nonce:   {nonce}")
            print(f"  attempts:{attempts}")
            print(f"  pubkey:  {pubkey.hex()}")
            print()

    print(f"Trials: {trials}")
    print(f"Min attempts: {min(attempts_list)}")
    print(f"Max attempts: {max(attempts_list)}")
    print(f"Average attempts: {mean(attempts_list):.3f}")

if __name__ == "__main__":
    demo(1000)