Prize for importing private key [WON] - page 4.

Pieter Wuille

legendary

Activity: 1072

Merit: 1174

I've also created some code that generates a "full" (279-byte) private key based on a given 256-bit private key number (using openssl's EC_KEY_generate_key after setting the private key as a parameter). The problem is (more or less expected?) that the corresponding public key varies each time.

Are we sure that a public key can be generated deterministically from *just* the 256-bit private number? It is stored in full in the 279-byte version, which may be becsause multiple public keys can correspond to the same private number.

I do wonder why/how 0x6763 and m0mchil managed to get the same (wrong?) public key from that private number. Maybe I'm still not getting something

xenon481

sr. member

Activity: 406

Merit: 250

When trying to decode the Private Key, I'm not getting the same hex that y'all are. But that's because, apparently, our base58 alphabets are different from eachother.

My base58 alphabet (the one I see all over Google): "123456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ"

When I use your alphabet, I get the same thing y'all are. Why are the cases reversed between yours and my alphabets?

grondilu

legendary

Activity: 1288

Merit: 1076

Ok but how do you plan on making a transaction without having the key in your wallet ?

?

Activity: -

Merit: -

I'm not even bothering to put it in my wallet. I'm just going to create a transaction that spends it (sending it to one of the addresses already in my wallet) as soon as I get the correct private key. Putting it in my wallet would mean requiring bitcoin to rescan the block chain so it knows that it has another 21.05+ BTC to spend, and then after it's finally done doing that, I'd have to spend my entire bitcoin balance to a new address just to make sure that the official Bitcoin software spends the specific bitcoins we're all trying to get. Just sending out a transaction with my own custom code is a lot easier and faster. Wink

grondilu

legendary

Activity: 1288

Merit: 1076

To me the difficult part is the modification of the wallet.dat file.

To decode base58, one can use my bash library:

Code:

#!/bin/bash
#
# Requires bc, dc, openssl, xxd
#

base58=({1..9} {A..H} {J..N} {P..Z} {a..k} {m..z})
bitcoinregex="^[$(printf "%s" "${base58[@]}")]{34}$"

decodeBase58() {
local s=$1
for i in {0..57}
do s="${s//${base58[i]}/ $i}"
done
dc <<< "16o0d${s// /+58*}+f"
}

encodeBase58() {
# 58 = 0x3A
bc <<<"ibase=16; n=${1^^}; while(n>0) { n%3A ; n/=3A }" |
tac |
while read n
do echo -n ${base58[n]}
done
}

checksum() {
xxd -p -r <<<"$1" |
openssl dgst -sha256 -binary |
openssl dgst -sha256 -hex |
sed 's/^.* //' |
head -c 8
}

checkBitcoinAddress() {
if [[ "$1" =~ $bitcoinregex ]]
then
h=$(decodeBase58 "$1")
checksum "00${h::${#h}-8}" |
grep -qi "^${h: -8}$"
else return 2
fi
}

hash160() {
openssl dgst -sha256 -binary |
openssl dgst -rmd160 -hex |
sed 's/^.* //'
}

hash160ToAddress() {
printf "%34s\n" "$(encodeBase58 "00$1$(checksum "00$1")")" |
sed "y/ /1/"
}

publicKeyToAddress() {
hash160ToAddress $(
openssl ec -pubin -pubout -outform DER |
tail -c 65 |
hash160
)
}

timestamp() {
hash160ToAddress "$(hash160)"
}

$ decodeBase58 2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy
1B66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC4677BE50CA

$ !! |xxd -r -p |base64
G2b/n2Os5Te1N74ffwy1hWScImxy7v9D1Z+sRne+UMo=

FWIW

m0mchil

full member

Activity: 171

Merit: 127

Last four bytes of address are check sum. Not sure what happens to first byte though.

I guess there is some minor discrepancy between what Hal used to 'encode' his private key and what we use.

?

Activity: -

Merit: -

Quote from: ? on February 20, 2011, 11:29:34 AM

Quote from: jav on February 20, 2011, 11:11:55 AM

Quote from: theymos on February 20, 2011, 05:47:06 AM

You can get the hex version here:
http://blockexplorer.com/q/addresstohash/2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy

That website claims 66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC46 is the hash version.
What exactly is being calculated there? I wrote my own decode58 code and I get this value:
1B66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC4677BE50CA

Represented in binary the blockexplorer hex is only 215 bit, whereas my hex is 253 bit. Add another 3 leading zeroes and you get 256 bit.

Theymos's link doesn't make any sense, since 2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy is not an address, but is instead a base58 encoded 256-bit number. Bitcoin addresses are much shorter than that base58 encoded number.

I'm also getting 1b66ff9f63ace537b537be1f7f0cb585649c226c72eeff43d59fac4677be50ca when I decode the base58 string.

However it does show that our base58 decoding functions must be functioning the same as Theymos's (which I suspect is correct as it's consistent with other instances of the base58 decoding that I've seen):

Code:

Ours: 1B66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC4677BE50CA
Theymos: 66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC46

(the first and last 4 bytes are removed after decoding the base58 encoded data in attempt to extract the hash of the public key, which is obviously incorrect here)

Currently my conclusion is that Hal made an error either in finding the correct private key that goes along with the address he shared, or in encoding the key in base58.

?

Activity: -

Merit: -

Quote from: jav on February 20, 2011, 11:11:55 AM

Quote from: theymos on February 20, 2011, 05:47:06 AM

You can get the hex version here:
http://blockexplorer.com/q/addresstohash/2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy

That website claims 66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC46 is the hash version.
What exactly is being calculated there? I wrote my own decode58 code and I get this value:
1B66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC4677BE50CA

Represented in binary the blockexplorer hex is only 215 bit, whereas my hex is 253 bit. Add another 3 leading zeroes and you get 256 bit.

Theymos's link doesn't make any sense, since 2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy is not an address, but is instead a base58 encoded 256-bit number. Bitcoin addresses are much shorter than that base58 encoded number.

I'm also getting 1b66ff9f63ace537b537be1f7f0cb585649c226c72eeff43d59fac4677be50ca when I decode the base58 string.

jav

sr. member

Activity: 249

Merit: 251

Quote from: theymos on February 20, 2011, 05:47:06 AM

You can get the hex version here:
http://blockexplorer.com/q/addresstohash/2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy

That website claims 66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC46 is the hash version.
What exactly is being calculated there? I wrote my own decode58 code and I get this value:
1B66FF9F63ACE537B537BE1F7F0CB585649C226C72EEFF43D59FAC4677BE50CA

Represented in binary the blockexplorer hex is only 215 bit, whereas my hex is 253 bit. Add another 3 leading zeroes and you get 256 bit.

Here is the Haskell code I used to decode the string:

import Maybe decode :: [Char] -> [(Char, Integer)] -> Integer decode s mapping = worker (reverse s) mapping bases where bases = iterate (58 *) 1 worker :: [Char] -> [(Char, Integer)] -> [Integer] -> Integer worker [] _ _ = 0 worker (c:cs) mapping (b:bs) = (fromJust (lookup c mapping)) * b + (worker cs mapping bs) main = do let chars = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz" let mapping = zip chars [0..] print $ decode "2qy6pGXd5yCo9qy3vxnN7rALgsXXcdboReZ9NZx5aExy" mapping

?

Activity: -

Merit: -

Haha, the stakes are a little higher now. Another 1.05 BTC went to that address. http://blockexplorer.com/address/17kzeh4N8g49GFvdDzSf8PjaPfyoD1MndL

?

Activity: -

Merit: -

If Hal did give us the wrong private key on accident, he might want to remove that key pair from his wallet so he doesn't accidentally give that address out in the future, since anyone else could spend any money sent to that address.

?

Activity: -

Merit: -

Quote from: Pieter Wuille on February 20, 2011, 09:43:16 AM

Quote from: ?? on ??

Correct me if I'm wrong, but aren't Bitcoin private keys 279 bytes long?

As I understand it, private keys are indeed 279 bytes long (though with some redundancy in them), public keys are 0x04 + 32-byte X-coordinate + 32-byte Y-coordinate (totalling 65 bytes, 520 bits), and addresses contain a 20-byte (160 bit) hash of the public key.

Not sure what you've given us Hal, but as it is only 256 bit, I doubt it's a private key.

PS: base58 encoding is more efficient than hex encoding, but it still can't turn a 279-byte key into a 44-character string...

The private key is actually just a 256-bit number. The public key is two 256-bit numbers. All of those other bytes that Bitcoin is using just contains redundant information about the elliptic curve (redundant since Bitcoin already knows the curve info anyway, and therefore doesn't need it stored with the key).

Pieter Wuille

legendary

Activity: 1072

Merit: 1174

Quote from: ?? on ??

Correct me if I'm wrong, but aren't Bitcoin private keys 279 bytes long?

As I understand it, private keys are indeed 279 bytes long (though with some redundancy in them), public keys are 0x04 + 32-byte X-coordinate + 32-byte Y-coordinate (totalling 65 bytes, 520 bits), and addresses contain a 20-byte (160 bit) hash of the public key.

Not sure what you've given us Hal, but as it is only 256 bit, I doubt it's a private key.

PS: base58 encoding is more efficient than hex encoding, but it still can't turn a 279-byte key into a 44-character string...

?

Activity: -

Merit: -

Quote from: m0mchil on February 20, 2011, 09:37:30 AM

0x6763, what public key do you get?

17KzV7RfQnmqcFC3cnS3RqWXQm1CREtNmj or something else?

Yeah, that's it.

m0mchil

full member

Activity: 171

Merit: 127

0x6763, what public key do you get?

17KzV7RfQnmqcFC3cnS3RqWXQm1CREtNmj or something else?

?

Activity: -

Merit: -

Quote from: theymos on February 20, 2011, 06:37:59 AM

Quote from: kvk on February 20, 2011, 06:30:59 AM

As far i understand the bitcoin, it's not really possible to redeem the coins with only private key, the script expects full public key to compare with hash160 and to verify signature. Since no coins were redeemed with this address, the pubkey is not known and the task of reversing the hash is impossible.

ECDSA public keys are derived from their private keys. It makes the challenge even more difficult, though.

I wrote some code (that I'll share after I get the 20 BTC, haha) that will generate a public key from a private key. I've tested it on multiple private keys in my wallet and it always generated the correct public key. The problem is that it doesn't generate a public key that makes the address Hal provided. Either my base58 decoding function is wrong, or Hal's base58 encoding function is wrong, or he gave us the wrong private key.

Quote from: theymos on February 20, 2011, 06:37:59 AM

Quote from: myrkul on February 20, 2011, 06:35:26 AM

Address is the public key. He's given us everything we need, we just need to figure out how to stick the private key into a wallet, and then send ourselves the coins.

The address is the hash of the public key. You need the full public key to spend it.

The private key was really the only info we needed, since the public key could be calculated from that, and then the address created from that, and the block chain could be searched for any payments to that address.

m0mchil

full member

Activity: 171

Merit: 127

Hal, could you please provide HEX encoded private key ?

myrkul

hero member

Activity: 532

Merit: 500

FIAT LIBERTAS RVAT CAELVM

Quote from: theymos on February 20, 2011, 06:37:59 AM

The address is the hash of the public key. You need the full public key to spend it.

Ahhh... Interesting. Deceptively simple problem he's given us... essentially, we need to re-mine his block, then?

Binford 6100

hero member

Activity: 504

Merit: 500

PGP OTC WOT: EB7FCE3D

so it goes like this?
1) base58decode the private key
2) find out the public key
3) modify your wallet.dat to include the key pair
4) rescan the blockchain
5) spend

btw added a btc to the bounty (hope hal does not spend it Wink

theymos

administrator

Activity: 5222

Merit: 13027

Quote from: kvk on February 20, 2011, 06:30:59 AM

As far i understand the bitcoin, it's not really possible to redeem the coins with only private key, the script expects full public key to compare with hash160 and to verify signature. Since no coins were redeemed with this address, the pubkey is not known and the task of reversing the hash is impossible.

ECDSA public keys are derived from their private keys. It makes the challenge even more difficult, though.

Quote from: myrkul on February 20, 2011, 06:35:26 AM

Address is the public key. He's given us everything we need, we just need to figure out how to stick the private key into a wallet, and then send ourselves the coins.

The address is the hash of the public key. You need the full public key to spend it.

Topic: Prize for importing private key [WON] - page 4. (Read 18052 times)