40 sats \ 6 replies \ @ZezzebbulTheMysterious 5 Mar freebie \ parent \ on: Did we just pass the P2PK brute force price point, or are we getting prepared? bitcoin
Close but Bitcoin uses ECDSA and Schnorr Sigs, which don’t rely on hardness factoring primes like in RSA. They rely on the hardness of the Discrete Log Problem.
Otherwise yes, by double hashing the pub key, we make it much harder to find the actually used pubkey to try to attack the DLP with.
write
preview
21 sats \ 5 replies \ @antic OP 5 Mar
ECDSA using Secp256k1 can still be brute forced (albeit inefficiently) using a discrete log solving method like rho:
from sympy import isprime, nextprime

def pollards_rho(G, Q, curve_order):
    x = G
    y = G
    factor = 1
    while factor == 1:
        x = curve_add(x, G, curve_order)
        y = curve_add(y, G, curve_order)
        y = curve_add(y, G, curve_order)
        factor = gcd(abs(x[0]-y[0]), curve_order)
    return factor

def curve_add(p1, p2, curve_order):
    # Simplified elliptic curve addition
    return (p1[0] + p2[0], p1[1] + p2[1]) % curve_order

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

# Example parameters (not for secp256k1)
G = (3, 7)  # Generator point
Q = (13, 17)  # Public key
curve_order = 19  # Elliptic curve order

d = pollards_rho(G, Q, curve_order)
print(f"Private key (d): {d}")
This would take a gazillion lifetimes of the universe to compute. It could be ported to Shor's on a quantum cluster if the cluster gets stupid large and actually corrects for errors.
Schnorr signatures are also reliant on the difficulty of solving the discrete log problem.
reply
121 sats \ 4 replies \ @ZezzebbulTheMysterious 5 Mar
Yes correct, Nothing to do with prime factoring as your previous message indicated. Did ChatGPT write that code block?
reply
0 sats \ 3 replies \ @antic OP 5 Mar
hah, my brain is still wired in GPG/PGP thinking. Correct, I have a tendency to blurt "large primes! It's all primes!" in my sleep. And yes, that's some unoptimized quick hackery from chatgpt in python. Not usable but readable enough to make the point.
reply
111 sats \ 2 replies \ @ZezzebbulTheMysterious 5 Mar
AI gen code sucks, you will notice it’s importing but not using the isprime, nextprime. We generally called that “Pollards Rho”, not “Rho”.
It’s hallucinating fragments contextually related from a cryptography library.
I would recommend not using chatgpt for code.
reply
0 sats \ 1 reply \ @antic OP 5 Mar
it is absolute garbage at writing code. I didn't even notice that excess import. It did at least correctly name the function pollards_rho :)
reply
0 sats \ 0 replies \ @ZezzebbulTheMysterious 5 Mar
Yes :-) all good! Just wanted to mention ECC/DLP va RSA in terminology;
I see people confuse factoring primes (RSA) with ECDLP (ECC). Bitcoin doesn’t specifically have to worry about prime factoring! (It may however indicate further advances in number theory…)
reply