Post
Topic
Board Development & Technical Discussion
Re: Determining the positivity or negativity of a Bitcoin public key
by
bjpark
on 17/01/2025, 20:53:02 UTC
Code:
import random
import ecdsa
import binascii

# Define the range
def generate_random_values():
    a = random.randint(2**134, 2**135)
    am = 10**37
    b = a - am

    # Set pma and pmb: both values should have the same sign
    sign = random.choice([1, -1])  # Set both as either positive or negative
    pma = sign * a
    pmb = sign * b

    return a, b, am, pma, pmb

# Define N (order of the secp256k1 curve)
N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

# Function to generate a public key from a private key
def generate_public_key(private_key_int):
    # Convert the private key to a 32-byte format
    private_key_bytes = abs(private_key_int).to_bytes(32, byteorder="big", signed=True)
   
    # Generate the elliptic curve public key (secp256k1)
    sk = ecdsa.SigningKey.from_string(private_key_bytes, curve=ecdsa.SECP256k1)
    vk = sk.verifying_key
   
    # Create uncompressed public key format
    public_key_bytes_uncompressed = b"\x04" + vk.to_string()
   
    # Determine the compressed public key's prefix based on the private key's sign
    if private_key_int < 0:
        public_key_bytes_compressed = (
            b"\x03" + vk.to_string()[:32] if vk.to_string()[-1] % 2 == 0 else b"\x02" + vk.to_string()[:32]
        )
    else:
        public_key_bytes_compressed = (
            b"\x02" + vk.to_string()[:32] if vk.to_string()[-1] % 2 == 0 else b"\x03" + vk.to_string()[:32]
        )
   
    # Convert the public keys to hexadecimal strings
    public_key_uncompressed = binascii.hexlify(public_key_bytes_uncompressed).decode()
    public_key_compressed = binascii.hexlify(public_key_bytes_compressed).decode()
   
    return public_key_uncompressed, public_key_compressed

# Adjust private key representation
def adjust_private_key(private_key_int):
    if private_key_int < 0:
        adjusted_key = N + private_key_int
        return f"0x{adjusted_key:064x}"
    else:
        return str(private_key_int)

# Generate and output results 10 times
for i in range(1, 11):
    print(f"\n=== Random Output {i} ===")
    a, b, am, pma, pmb = generate_random_values()
    public_key_a_uncompressed, public_key_a_compressed = generate_public_key(pma)
    public_key_b_uncompressed, public_key_b_compressed = generate_public_key(pmb)

    print("a:", a)
    print("b:", b)
    print("am:", am)
    print("pma (Private Key a):", adjust_private_key(pma))
    print("pmb (Private Key b):", adjust_private_key(pmb))

    print("public_key_a (Compressed Public Key a):", public_key_a_compressed)
    print("public_key_b (Compressed Public Key b):", public_key_b_compressed)

The purpose of this program is to distinguish whether a given public key corresponds to a positive or negative private key. Once the program is executed, it generates a series of random private keys and their associated public keys. By analyzing the public key alone, the program can determine whether the original private key was positive or negative.

Key Conditions:
Always a > b: This ensures that the value of a is strictly greater than b in all generated cases.
am can be modified: The value of am (used to calculate b) can be adjusted by the user or problem setter to fall within the range of
10**35 ~ 10**38
Functionality:
After execution, the program outputs 10 sets of public keys (public_key_a and public_key_b), each derived from randomly generated private keys (pma and pmb).
By analyzing these 10 public keys, it is possible to accurately determine whether the original private keys are positive or negative with 100% certainty.
This distinction is made based on the structure and prefix of the generated compressed public keys, which encode the sign of the private key in their format.