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)