pubkey decompression | Bitcointalksearch.org

DarkDays

legendary

Activity: 2030

Merit: 1189

Here's a quote from an old thread that you might find useful.

Quote from: Zeilap on March 31, 2013, 08:12:55 PM

Quote from: jackjack on March 31, 2013, 07:56:54 PM

Hi,
I'd like to know if there is a formula to calculate the two possible values of Y from X
I use a library that needs them, and I don't really want to modify it

Actually it's very simple.

y² = x³+ ax² + b
so we need to perform square root to recover y from x. And it turns out that
sqrt(a) = a^(q+1)/4

Now you just have to pick either the positive or negative solution. If the y that you calculated is even, and the first byte of the key is even, then use this value, otherwise, use the negative value which is q-y.

EDIT: relevant code I wrote as a patch for bitaddress.org

Code:

ec.CurveFp.prototype.decompressPoint = function(yOdd, X) {
   if(this.q.mod(BigInteger.valueOf(4)).equals(BigInteger.valueOf(3))) {
   // y^2 = x^3 + ax^2 + b, so we need to perform sqrt to recover y
   var ySquared = X.multiply(X.square().add(this.a)).add(this.b);

   // sqrt(a) = a^((q+1)/4) if q = 3 mod 4
   var Y = ySquared.x.modPow(this.q.add(BigInteger.ONE).divide(BigInteger.valueOf(4)), this.q);

   if(Y.testBit(0) !== yOdd) {
   Y = this.q.subtract(Y);
   }

   return new ec.PointFp(this, X, this.fromBigInteger(Y));
   }
   else {
   // only implement sqrt for q = 3 mod 4
   return null;
   }
};

// for now, work with hex strings because they're easier in JS
ec.CurveFp.prototype.decodePointHex = function (s) {
   switch (parseInt(s.substr(0, 2), 16)) { // first byte
   case 0:
   return this.infinity;
   case 2:
   return this.decompressPoint(false, this.fromBigInteger(new BigInteger(s.substr(2), 16)));
   case 3:
   return this.decompressPoint(true, this.fromBigInteger(new BigInteger(s.substr(2), 16)));
   case 4:
   case 6:
   case 7:
   var len = (s.length - 2) / 2;
   var xHex = s.substr(2, len);
   var yHex = s.substr(len + 2, len);

   return new ec.PointFp(this,
   this.fromBigInteger(new BigInteger(xHex, 16)),
   this.fromBigInteger(new BigInteger(yHex, 16)));

   default: // unsupported
   return null;
   }
};

Link is at : https://bitcointalksearch.org/topic/compressed-keys-y-from-x-162805

Similar topics can be found being discussed at these links:
https://bitcoin.stackexchange.com/questions/86234/how-to-uncompress-a-public-key
https://gist.github.com/afk11/a3f1174f30e1e8d9ed2d

I hope these helped.

HCP

legendary

Activity: 2086

Merit: 4361

I got bored and started playing around with this... So, here is my pretty crappy 5 minute Python code that will take any form of the PubKey (compressed/uncompressed) and output the address of the compressed public key.

NOTE: The hexstring -> int conversion for "y" should be both Python 2.7 and Python 3 "safe"... If you're using Python 3 there is the int.from_bytes() function available, which is a bit tidier.

Code: (pubkey_fun.py)

import binascii
import hashlib
import codecs

def public_key_to_address(public_key):
print('Wanting to convert this [%s] to address'%public_key)
output = []; alphabet = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
var = hashlib.new('ripemd160')
if public_key[0:2] == "04":
print("------------------------")
print("Found UNcompressed PubKey, converting")

#break into x and y components
x = public_key[2:66]
y = public_key[66:]
#print('x: ' + x)
#print('y: ' + y)

#convert hex str to int
y = int(codecs.encode(binascii.unhexlify(y),'hex'),16)

#test if y is "odd" or "even" and assign prefix as appropriate
if 1 == (y % 2):
public_key = "03" + x
else:
public_key = "02" + x

print("Compressed PubKey: " + public_key)
print("------------------------")
try:
var.update(hashlib.sha256(binascii.unhexlify(public_key.encode())).digest())
var = '00' + var.hexdigest() + hashlib.sha256(hashlib.sha256(binascii.unhexlify(('00' + var.hexdigest()).encode())).digest()).hexdigest()[0:8]
count = [char != '0' for char in var].index(True) // 2
n = int(var, 16)
while n > 0:
n, remainder = divmod(n, 58)
output.append(alphabet[remainder])
for i in range(count): output.append(alphabet[0])
return ''.join(output[::-1])
except:
# Nothing
return -1

pubkey = '041A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7ACCF8E941F95AE80B8F373229B7A3F83144160D8982E648F60C8E5CB968EC72E'
print("CompressedAddress: " + public_key_to_address(pubkey) + "\n\n")

pubkey = '0408FD4E4E01356F3F0052E35FA186E54F736B209C025DFC5686FF98FF9A367A52520FAC06060EC7B3FEAE3F92EB840399B09E7E82AB332060D882ED4D4829D383'
print("CompressedAddress: " + public_key_to_address(pubkey) + "\n\n")

pubkey = '021A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7'
print("CompressedAddress: " + public_key_to_address(pubkey) + "\n\n")

hardcorepawn@HardCorePC:~$ vi pubkey_fun.py
hardcorepawn@HardCorePC:~$ python pubkey_fun.py
Wanting to convert this [041A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7ACCF8E941F95AE80B8F373229B7A3F83144160D8982E648F60C8E5CB968EC72E] to address
------------------------
Found UNcompressed PubKey, converting
Compressed PubKey: 021A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7
------------------------
CompressedAddress: 1AYNNMBpXwV7kVveDmFALhCU8VTA3yTs88

Wanting to convert this [0408FD4E4E01356F3F0052E35FA186E54F736B209C025DFC5686FF98FF9A367A52520FAC06060EC7B3FEAE3F92EB840399B09E7E82AB332060D882ED4D4829D383] to address
------------------------
Found UNcompressed PubKey, converting
Compressed PubKey: 0308FD4E4E01356F3F0052E35FA186E54F736B209C025DFC5686FF98FF9A367A52
------------------------
CompressedAddress: 1NCasbMhu3gUjmN6nNmrX3Kqb2H6bzY6Lw

Wanting to convert this [021A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7] to address
CompressedAddress: 1AYNNMBpXwV7kVveDmFALhCU8VTA3yTs88

hardcorepawn@HardCorePC:~$ vi pubkey_fun.py
hardcorepawn@HardCorePC:~$ python pubkey_fun.py
Even Y uncompressed PubKey
Wanting to convert this [041A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7ACCF8E941F95AE80B8F373229B7A3F83144160D8982E648F60C8E5CB968EC72E] to address
------------------------
Found UNcompressed PubKey, converting
Compressed PubKey: 021A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7
------------------------
CompressedAddress: 1AYNNMBpXwV7kVveDmFALhCU8VTA3yTs88

Odd Y uncompressed PubKey
Wanting to convert this [0408FD4E4E01356F3F0052E35FA186E54F736B209C025DFC5686FF98FF9A367A52520FAC06060EC7B3FEAE3F92EB840399B09E7E82AB332060D882ED4D4829D383] to address
------------------------
Found UNcompressed PubKey, converting
Compressed PubKey: 0308FD4E4E01356F3F0052E35FA186E54F736B209C025DFC5686FF98FF9A367A52
------------------------
CompressedAddress: 1NCasbMhu3gUjmN6nNmrX3Kqb2H6bzY6Lw

Compressed PubKey
Wanting to convert this [021A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7] to address
CompressedAddress: 1AYNNMBpXwV7kVveDmFALhCU8VTA3yTs88

hardcorepawn@HardCorePC:~$ cat pubkey_fun.py
import binascii
import hashlib
import codecs

def public_key_to_address(public_key):
print('Wanting to convert this [%s] to address'%public_key)
output = []; alphabet = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
var = hashlib.new('ripemd160')
if public_key[0:2] == "04":
print("------------------------")
print("Found UNcompressed PubKey, converting")

#break into x and y components
x = public_key[2:66]
y = public_key[66:]
#print('x: ' + x)
#print('y: ' + y)

#convert hex str to int
y = int(codecs.encode(binascii.unhexlify(y),'hex'),16)

#test if y is "odd" or "even" and assign prefix as appropriate
if (y % 2) == 1:
public_key = "03" + x
else:
public_key = "02" + x

print("Compressed PubKey: " + public_key)
print("------------------------")
try:
var.update(hashlib.sha256(binascii.unhexlify(public_key.encode())).digest())
var = '00' + var.hexdigest() + hashlib.sha256(hashlib.sha256(binascii.unhexlify(('00' + var.hexdigest()).encode())).digest()).hexdigest()[0:8]
count = [char != '0' for char in var].index(True) // 2
n = int(var, 16)
while n > 0:
n, remainder = divmod(n, 58)
output.append(alphabet[remainder])
for i in range(count): output.append(alphabet[0])
return ''.join(output[::-1])
except:
# Nothing
return -1

pubkey = '041A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7ACCF8E941F95AE80B8F373229B7A3F83144160D8982E648F60C8E5CB968EC72E'
print("Even Y uncompressed PubKey:")
print("CompressedAddress: " + public_key_to_address(pubkey) + "\n\n")

pubkey = '0408FD4E4E01356F3F0052E35FA186E54F736B209C025DFC5686FF98FF9A367A52520FAC06060EC7B3FEAE3F92EB840399B09E7E82AB332060D882ED4D4829D383'
print("Odd Y uncompressed PubKey:")
print("CompressedAddress: " + public_key_to_address(pubkey) + "\n\n")

pubkey = '021A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7'
print("Compressed PubKey:")
print("CompressedAddress: " + public_key_to_address(pubkey) + "\n\n")

Output should be:

Code:

Even Y uncompressed PubKey:
Wanting to convert this [041A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7ACCF8E941F95AE80B8F373229B7A3F83144160D8982E648F60C8E5CB968EC72E] to address
------------------------
Found UNcompressed PubKey, converting
Compressed PubKey: 021A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7
------------------------
CompressedAddress: 1AYNNMBpXwV7kVveDmFALhCU8VTA3yTs88

Odd Y uncompressed PubKey:
Wanting to convert this [0408FD4E4E01356F3F0052E35FA186E54F736B209C025DFC5686FF98FF9A367A52520FAC06060EC7B3FEAE3F92EB840399B09E7E82AB332060D882ED4D4829D383] to address
------------------------
Found UNcompressed PubKey, converting
Compressed PubKey: 0308FD4E4E01356F3F0052E35FA186E54F736B209C025DFC5686FF98FF9A367A52
------------------------
CompressedAddress: 1NCasbMhu3gUjmN6nNmrX3Kqb2H6bzY6Lw

Compressed PubKey:
Wanting to convert this [021A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7] to address
CompressedAddress: 1AYNNMBpXwV7kVveDmFALhCU8VTA3yTs88

DougM

full member

Activity: 173

Merit: 120

Quote from: HCP on July 29, 2020, 07:20:01 PM

If you're just trying to convert ONE uncompressed pubkey to compressed (or vice versa)... you can use this: https://iancoleman.io/bitcoin-key-compression/

Good site! thanks HCP. RBan, I am not 100% sure what you are trying to do in the end, but I have a potentially similar thread going that you might want check out:
how do I extract the address from the output scriptPubKey for early coinbse tx?

HCP

legendary

Activity: 2086

Merit: 4361

If you're just trying to convert ONE uncompressed pubkey to compressed (or vice versa)... you can use this: https://iancoleman.io/bitcoin-key-compression/

If you want to do it in code, then the algorithm is:

Code:

1. Starting with uncompressed Pubkey, drop the "04" prefix
041A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7ACCF8E941F95AE80B8F373229B7A3F83144160D8982E648F60C8E5CB968EC72E
--> 1A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7ACCF8E941F95AE80B8F373229B7A3F83144160D8982E648F60C8E5CB968EC72E

2. Split into X (1st 32 bytes) and Y (2nd 32 bytes)
1A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7ACCF8E941F95AE80B8F373229B7A3F83144160D8982E648F60C8E5CB968EC72E
X -> 1A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7
Y -> ACCF8E941F95AE80B8F373229B7A3F83144160D8982E648F60C8E5CB968EC72E

3. Determine if Y is "Even" or "Odd"

If Y = even, then compressed prefix = 02
If Y = odd, then compressed prefix = 03

ACCF8E941F95AE80B8F373229B7A3F83144160D8982E648F60C8E5CB968EC72E is an "Even" number, so Compressed Prefix = 02

4. "Compressed" Public Key = Compressed Prefix + X

Compressed Prefix == 02
X == 1A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7
Compressed Pubkey -> 021A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7

TheArchaeologist

sr. member

Activity: 310

Merit: 727

---------> 1231006505

Quote from: RBan on July 22, 2020, 01:36:10 PM

Anyone know how to modify this code so that it converts the input public key into a compressed P2PKH address instead of uncompressed ?

You don't need to change any code in that function. You pass a compressed public key as parameter to the function and you get the P2PKH-address for the compressed key. Or you pass an uncompressed public key and get the P2PKH-address returned for the uncompressed address. There is no difference between the two in the steps from public key to the base-58 encoded address.

Code:

#example for uncompressed
pubkey = '041A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7ACCF8E941F95AE80B8F373229B7A3F83144160D8982E648F60C8E5CB968EC72E'
print(public_key_to_address(pubkey))

Results in:
Wanting to [041A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7ACCF8E941F95AE80B8F373229B7A3F83144160D8982E648F60C8E5CB968EC72E] this to address
1BoatSLRHtKNngkdXEeobR76b53LETtpyT

#example for compressed
pubkey = '021A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7'
print(public_key_to_address(pubkey))

Results in:
Wanting to [021A87E4688D8B9445B5B038CB3B34C186331F1AB4FC0822DCCA44192043EAB3B7] this to address
1AYNNMBpXwV7kVveDmFALhCU8VTA3yTs88

RBan

newbie

Activity: 12

Merit: 10

Anyone know how to modify this code so that it converts the input public key into a compressed P2PKH address instead of uncompressed ?

Code:

def public_key_to_address(public_key):
#print('Wanting to [%s] this to address'%public_key)
output = []; alphabet = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
var = hashlib.new('ripemd160')
try:
var.update(hashlib.sha256(binascii.unhexlify(public_key.encode())).digest())
var = '00' + var.hexdigest() + hashlib.sha256(hashlib.sha256(binascii.unhexlify(('00' + var.hexdigest()).encode())).digest()).hexdigest()[0:8]
count = [char != '0' for char in var].index(True) // 2
n = int(var, 16)
while n > 0:
n, remainder = divmod(n, 58)
output.append(alphabet[remainder])
for i in range(count): output.append(alphabet[0])
return ''.join(output[::-1])
except:
# Nothing
return -1

Topic: pubkey decompression (Read 252 times)