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)

Extended run example:

Example #1
  payload: 0c4dcb8b56f5deaf7ca91101ea071a0776ef8043fd288af7056a7bf5deb0d7
  nonce:   1
  attempts:2
  pubkey:  020c4dcb8b56f5deaf7ca91101ea071a0776ef8043fd288af7056a7bf5deb0d701

Example #2
  payload: 6f74132b21371df0c03df9676e430905c70ae7093d6328bf2e7de6dd549ebe
  nonce:   3
  attempts:4
  pubkey:  036f74132b21371df0c03df9676e430905c70ae7093d6328bf2e7de6dd549ebe03

Example #3
  payload: bbeedc4d780ef48669217f16992909e083a51e2277771273aa338d0479623c
  nonce:   0
  attempts:1
  pubkey:  02bbeedc4d780ef48669217f16992909e083a51e2277771273aa338d0479623c00

Example #4
  payload: fd353e82d0a20d200cc63dfcd6f1d77972823c3d6aa5af9e60b49d1511afef
  nonce:   3
  attempts:4
  pubkey:  02fd353e82d0a20d200cc63dfcd6f1d77972823c3d6aa5af9e60b49d1511afef03

Example #5
  payload: 9b19c0c4206e9c8c8be551cf92f46bc725ef83e371792017a6f2f07b092304
  nonce:   0
  attempts:1
  pubkey:  039b19c0c4206e9c8c8be551cf92f46bc725ef83e371792017a6f2f07b09230400

Example #6
  payload: fb75dc3c45c91b38b63d62cbf0917f9c5573f1e5c88d501136a8756d3909c3
  nonce:   4
  attempts:5
  pubkey:  02fb75dc3c45c91b38b63d62cbf0917f9c5573f1e5c88d501136a8756d3909c304

Example #7
  payload: 040768dcef788a61913ec092d96c5319f982a83cb26427054b76b6314812ea
  nonce:   2
  attempts:3
  pubkey:  02040768dcef788a61913ec092d96c5319f982a83cb26427054b76b6314812ea02

Example #8
  payload: 6b240c04b0fe83dd4af5311e2f68b989fbbfc0a40c47053b4c83ed8dda644d
  nonce:   0
  attempts:1
  pubkey:  036b240c04b0fe83dd4af5311e2f68b989fbbfc0a40c47053b4c83ed8dda644d00

Example #9
  payload: 6065c9631a479899cb022ac0d8f4f5d21a8c560026f3cc327b5eae055c812c
  nonce:   0
  attempts:1
  pubkey:  036065c9631a479899cb022ac0d8f4f5d21a8c560026f3cc327b5eae055c812c00

Trials: 1000
Min attempts: 1
Max attempts: 10
Average attempts: 2.026