80-bit Private Key Puzzle

Status: SOLVED
Prize: 0.005 BTC
Creator: kTimesG
Start Date: 2024-11-01
Solve Date: 2024-11-02
Address: 1ECDLP8osCZHBB1LH5PVAUfFegeMgFb52q
Private Key: b40e7d34265ab9533a64622bd1a188fb8abb8829af545169abad49b46be5fe56

Description

Given an Bitcoin address, associated with an 80-bit secure private key:

BTC Address(c): 1ECDLP8osCZHBB1LH5PVAUfFegeMgFb52q

minKey = 0x659756abf6c17ca70e0000000000000000000140be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
maxKey = 0x659756abf6c17ca70fffffffffffffffffffff40be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355

Between 20 and 28 hours after the puzzle is published, the outgoing TX will be pushed.

SHA-256 of correct solve steps:

a6c39217128593909a1fcc0fd92c07a6f5abd32c36a8e7cf4e91f1a8f0651db0

Hints

"The challenge involves correctly extracting pubkey from the raw TX, otherwise it's a no brainer.

What is a good way to set sat/vB such that it's both not stuck but also not urgent, e.g. mined in the block after next one? The challenge is not about "let's see if a 80 bit key can be cracked in less than 6 hours", we already have an answer to that."

kTimesG on BitcoinTalk

Original solution by kTimesG

minKey = 0x659756abf6c17ca70e0000000000000000000140be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
maxKey = 0x659756abf6c17ca70fffffffffffffffffffff40be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355

# PubKey:
#  X: a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7
#  Y: 1203ad05355adda4bb954e52adb62aaccbdbee069610cb20e566e26e9102b565
# BTC Address(c): 1ECDLP8osCZHBB1LH5PVAUfFegeMgFb52q

# Step 1: determine position and size of the middle (unknown) bits

range_mask = min_key ^ max_key          # every 1 bit in result = input bits differed

# get number of zeroes
shift = range_mask.bit_length() - range_mask.bit_count()

# remove the right zeros
range_mask >>= shift

# if at least one 0 is still present, the mask is invalid (and we shifted at least one 1 as well)
if range_mask.bit_count() != range_mask.bit_length():
    raise ValueError('Invalid mask')

assert range_mask.bit_length() <= 80

assert shift == 361

# Step 2: normalize private key search interval to [1, max]

min_elem = min_key * G

# check that the middle (unknown) bits are not all 0
if min_elem == public_key:
    # if hidden bits are all 0, key normalization would result in PAI -> unsolvable
    private_key = min_key
    return

# subtract min_key from unknown private_key
elem = public_key - min_elem    # guaranteed to be a valid point

# right-shift the unknown subtracted key ("divide" by the nth power of two)
# because we know the number of even bits, it's guaranteed the keyspace is reduced by 2**shift
shift_inv = pow(1 << shift, -1, secp256k1.N)    # == inv(2**shift)
elem = shift_inv * elem

# IDLP PubKey:
#  X: 0x34a20e64c9a70138783b125ad81196c76585403905dda56a644ac83ac9620045
#  Y: 0x6f7db39f0310d65e68dc83fe9c538c4a62ef8e70db4b0d44adbabd5245dd23ff

# Step 3: solve the key, as it resides in the [1, 2**range_len - 1] interval
# this would be the input to kangaroo, BSGS, etc. which could internally adjust,
# if needed, the public key, working interval, etc.
idlp_key = solve_ecdlp(elem, 1, range_mask)

# reverse steps: left-shift the key, fill back subtracted value
private_key = min_key | (idlp_key << shift)

# if the solved key is correct, then the original key must also be correct
assert (private_key * G) == public_key      # X0 == X1 and Y0 == Y1

# for brevity
assert idlp_key == 0x2d56cbf370cbeef9e80a
assert private_key == 0x659756abf6c17ca70e5aad97e6e197ddf3d01540be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
assert private_key % secp256k1.N == 0xb40e7d34265ab9533a64622bd1a188fb8abb8829af545169abad49b46be5fe56

Solution by albert0bsd

Take original public key: 03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7

./keymath 03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7 - 0x20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
Result: 036f778728f5a13be638ffb3935e4cc629b92c69612f7bb7921811a97b51bd8b66

./keymath  036f778728f5a13be638ffb3935e4cc629b92c69612f7bb7921811a97b51bd8b66 / 0x1000000000000000000000000000000000000000000000000000000000000000
Result: 034c32bfc4e92bfdd9dcb7b6cd1c88da23cc588c0718440e10a297296da3b2713e

./keymath  034c32bfc4e92bfdd9dcb7b6cd1c88da23cc588c0718440e10a297296da3b2713e - 0x40be6ddd93e441f8d4b4a85653b
Result: 03595f999c25e5afdd1ae1bfb1710924b26698eb51d3e2c131749fb54c018d896c

./keymath  03595f999c25e5afdd1ae1bfb1710924b26698eb51d3e2c131749fb54c018d896c / 0x1000000000000000000000000000
Result: 0228239ee788ae6784f825e96e31110097929ef0b4348cd6041f5335a542d47f18

./keymath  0228239ee788ae6784f825e96e31110097929ef0b4348cd6041f5335a542d47f18 - 0x659756abf6c17ca70000000000000000000000
Result: 02bfc064566b29109fa93495d1a47cd499889cd708674e0200a2cd5db57138741e

./keymath  02bfc064566b29109fa93495d1a47cd499889cd708674e0200a2cd5db57138741e - 0xe00000000000000000000
Result: 03a4134422eef408a6f8cb1aa8256bfd20cb0852d1fa4a06de5f3e8134e87b3271

./keymath  03a4134422eef408a6f8cb1aa8256bfd20cb0852d1fa4a06de5f3e8134e87b3271 - 1
Result: 03a1708bbb4e9b81a738eaca200d2b06a8f1d351aa3b07c8e255850500bef5ec2b

./keymath  03a1708bbb4e9b81a738eaca200d2b06a8f1d351aa3b07c8e255850500bef5ec2b / 2
Result: 0334a20e64c9a70138783b125ad81196c76585403905dda56a644ac83ac9620045

This last is the transformed/rotated key: 0334a20e64c9a70138783b125ad81196c76585403905dda56a644ac83ac9620045

Once that you solve that key now we do modmath operations in backwards order:

./modmath 0x2d56cbf370cbeef9e80a x 2
Result: 5aad97e6e197ddf3d014

./modmath 0x5aad97e6e197ddf3d014 + 1
Result: 5aad97e6e197ddf3d015

./modmath 0x5aad97e6e197ddf3d015 + 0xe00000000000000000000
Result: e5aad97e6e197ddf3d015

./modmath 0xe5aad97e6e197ddf3d015 + 0x659756abf6c17ca70000000000000000000000
Result: 659756abf6c17ca70e5aad97e6e197ddf3d015

./modmath 0x659756abf6c17ca70e5aad97e6e197ddf3d015 x 0x1000000000000000000000000000
Result: 59756abf6c17ca70e5aad97e6e197de6dce82297e44c3e998111c8b31eba787a

./modmath 0x59756abf6c17ca70e5aad97e6e197de6dce82297e44c3e998111c8b31eba787a + 0x40be6ddd93e441f8d4b4a85653b
Result: 59756abf6c17ca70e5aad97e6e197de6dce826a3cb2a17d7c53155fe693fddb5

./modmath 0x59756abf6c17ca70e5aad97e6e197de6dce826a3cb2a17d7c53155fe693fddb5 x 0x1000000000000000000000000000000000000000000000000000000000000000
Result: b203305760937132c056b815b884815764e3801d87e4bd57647f458a85ca3b01

./modmath 0xb203305760937132c056b815b884815764e3801d87e4bd57647f458a85ca3b01 + 0x20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
Result: b40e7d34265ab9533a64622bd1a188fb8abb8829af545169abad49b46be5fe56
Original key: b40e7d34265ab9533a64622bd1a188fb8abb8829af545169abad49b46be5fe56
Extended key: 0x659756abf6c17ca70e5aad97e6e197ddf3d01540be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355

Solution by Etar

03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7 - minrange = 03634641685eca3f8284bcd4ddf233dac92a551bb5ff74a0b3fd587d4da7c13eea
03634641685eca3f8284bcd4ddf233dac92a551bb5ff74a0b3fd587d4da7c13eea / (2^361) = 0334a20e64c9a70138783b125ad81196c76585403905dda56a644ac83ac9620045
0334a20e64c9a70138783b125ad81196c76585403905dda56a644ac83ac9620045 in range 1..2^80
The private key from the kangaroo was 0x2d56cbf370cbeef9e80a
(0x2d56cbf370cbeef9e80a * (2^361) +  minrange) % N = 0xb40e7d34265ab9533a64622bd1a188fb8abb8829af545169abad49b46be5fe56

Here is an example of a script that will allow you to learn how to work with points:

# (Gx,Gy)  is the secp256k1 generator point
Gx=0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy=0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
p = 2**256 - 2**32 - 977
import operator
import math

def inverse(x, p):
    """
    Calculate the modular inverse of x ( mod p )
    the modular inverse is a number such that:
    (inverse(x, p) * x) % p  ==  1
    you could think of this as: 1/x
    """
    inv1 = 1
    inv2 = 0
    n=1
    while p != 1 and p!=0:
        quotient = x // p
        inv1, inv2 = inv2, inv1 - inv2 * quotient
        x, p = p, x % p
        n = n+1

    return inv2

def dblpt(pt, p):
    """
    Calculate pt+pt = 2*pt
    """
    if pt is None:
        return None
    (x,y)= pt
    if y==0:
        return None

    slope= 3*pow(x,2,p)*pow(2*y,p-2,p)
    xsum= pow(slope,2,p)-2*x
    ysum= slope*(x-xsum)-y

    return (xsum%p, ysum%p)

def addpt(p1,p2, p):
    """
    Calculate p1+p2
    """
    if p1 is None or p2 is None:
        return None
    (x1,y1)= p1
    (x2,y2)= p2
    if x1==x2:
        return dblpt(p1, p)

    # calculate (y1-y2)/(x1-x2)  modulus p

    slope=(y1-y2)*pow(x1-x2,p-2,p)
    xsum= pow(slope,2,p)-(x1+x2)
    ysum= slope*(x1-xsum)-y1


    return (xsum%p, ysum%p)

def ptmul(pt,a, p):
    """
    Scalar multiplication: calculate pt*a
    basically adding pt to itself a times
    """
    scale= pt
    acc=None
    while a:
        if a&1:
            if acc is None:
                acc= scale
            else:
                acc= addpt(acc,scale, p)

        scale= dblpt(scale, p)
        a >>= 1
    return acc

def ptdiv(pt,a,p,n):
    divpt=inverse(a, n)%n
    return ptmul(pt, divpt, p)


def isoncurve(pt,p):
    """
    returns True when pt is on the secp256k1 curve
    """
    (x,y)= pt
    return (y**2 - x**3 - 7)%p == 0


def getuncompressedpub(compressed_key):
    """
    returns uncompressed public key
    """
    y_parity = int(compressed_key[:2]) - 2
    if y_parity>1:
      #it is uncompresse dpub
      x = int(compressed_key[2:66], 16)
      y = int(compressed_key[66:130], 16)
      return (x,y)

    x = int(compressed_key[2:], 16)
    a = (pow(x, 3, p) + 7) % p
    y = pow(a, (p+1)//4, p)
    if y % 2 != y_parity:
        y = -y % p
    return (x,y)

def compresspub(uncompressed_key):
    """
    returns uncompressed public key
    """
    (x,y)=uncompressed_key
    y_parity = y&1
    head='02'
    if y_parity ==1:
        head='03'
    compressed_key = head+'{:064x}'.format(x)
    return compressed_key


rangeBegin = 0x659756abf6c17ca70e0000000000000000000140be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
rangeEnd =   0x659756abf6c17ca70fffffffffffffffffffff40be6ddd93e441f8d4b4a85653b20b4cdcc5c748207a0daa16191d07a425d8080c276f9412472e0429e61bc355
pub_compressed = '03a61fc84b6429f07fc0edf25265ef7a0ced3cd9a0edea85e9f58b50b5d73f66e7'
Bits = 361

(pubx,puby) = getuncompressedpub(pub_compressed)
(x,y) = ptmul((Gx,Gy),rangeBegin,p)
#substract rangeBegin from public key
(Shiftpubx,Shiftpuby) = addpt((pubx,puby), (x,(p-y)%p), p)
print ("Shifted pub> ",compresspub((Shiftpubx,Shiftpuby)))
#pub / (2**361)
(SPubx,SPuby) = ptdiv((Shiftpubx,Shiftpuby),2**361,p,n)
print ("Pub> ",compresspub((SPubx,SPuby)))

#Convert private key
kangarooPrivKey=0x2d56cbf370cbeef9e80a
RealPrivKey = (kangarooPrivKey * (2**361) + rangeBegin ) % n
print ("Key> %x"% RealPrivKey)

Links