39 sats \ 10 replies \ @037447d9ca 5 Mar \ on: Did we just pass the P2PK brute force price point, or are we getting prepared? bitcoin
afaik keys are only exposed once used. so they were safe... until now.
address reuse is discouraged for this reason (amongst others)
The thing that gets exposed when you spend from a P2PKH (pay to public key hash) is the unhashed PK (public key). Factoring large primes requires knowing one of the two large numbers. The private key is one number, the public key is the other number. By using P2PK, the original block rewards were paid out directly to the public key number itself without any secret being made of it. Hashing the public key prevents anyone from deriving the actual number that is the public key, which prevents using a number factoring attack (as long as you keep both the private key and the public key secret).
You could reduce this to make visualization easier by imagining a keyspace of only 10 numbers. By using P2PK, they were saying to the world, "my secret key maps to the public key for the number 6" and then someone can simply find the private key that matches the number 6. Hashing the public key prevents anyone from knowing which of the 10 numbers your private key pairs with, so they would have to brute force and test each one, which is very doable for a keyspace of 10, but relatively impossible for a keyspace of 2^128
reply
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.
reply
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
Yes correct, Nothing to do with prime factoring as your previous message indicated. Did ChatGPT write that code block?
reply
reply
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
reply
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
Sipa explained this in 2018:
https://bitcoin.stackexchange.com/questions/72184/why-is-p2pkh-used-instead-of-the-simpler-p2pk
I don’t think it’s a problem today.
reply