Bitcoin Forum
February 17, 2019, 05:14:08 AM
 News: Latest Bitcoin Core release: 0.17.1 [Torrent]
 Home Help Search Login Register More
 Pages: [1]
 Author Topic: How to get uncompressed public key from compressed one ?  (Read 3048 times)
Farghaly
Newbie

Offline

Activity: 38
Merit: 0

 June 08, 2014, 11:48:14 PM

Uncompressed public key is:
0x04 + x-coordinate + y-coordinate

Compressed public key is:
0x02 + x-coordinate if y is even
0x03 + x-coordinate if y is odd

How to use this equation to derive the uncompressed public key

y^2 mod p = (x^3 + 7) mod p

1550380448
Hero Member

Offline

Posts: 1550380448

Ignore
 1550380448

1550380448
 Report to moderator
1550380448
Hero Member

Offline

Posts: 1550380448

Ignore
 1550380448

1550380448
 Report to moderator
1550380448
Hero Member

Offline

Posts: 1550380448

Ignore
 1550380448

1550380448
 Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
TimS
Sr. Member

Offline

Activity: 250
Merit: 251

 June 09, 2014, 12:53:21 AMLast edit: June 09, 2014, 01:14:02 AM by TimSMerited by fronti (1)

r^2 = a mod m where m = 3 mod 4 (as secp256k1's p does)
then
r = +-a^((m+1)/4) mod m

So:

y^2 mod p = (x^3 + 7) mod p
y mod p = +-(x^3 + 7)^((p+1)/4) mod p

So calculate (x^3 + 7)^((p+1)/4) mod p, and if the parity of the first answer you get is wrong, then take the negative of that answer (since we're working modulo an odd number, taking the negative will flip the even/odd parity).

Just for fun, here's some Python code that'll do the calculation in the blink of an eye, preset to work on the public key of (the random) private key 55255657523dd1c65a77d3cb53fcd050bf7fc2c11bb0bb6edabdbd41ea51f641

Code:
def pow_mod(x, y, z):
"Calculate (x ** y) % z efficiently."
number = 1
while y:
if y & 1:
number = number * x % z
y >>= 1
x = x * x % z
return number

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
compressed_key = '0314fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267'
y_parity = int(compressed_key[:2]) - 2
x = int(compressed_key[2:], 16)
a = (pow_mod(x, 3, p) + 7) % p
y = pow_mod(a, (p+1)//4, p)
if y % 2 != y_parity:
y = -y % p
uncompressed_key = '04{:x}{:x}'.format(x, y)
print(uncompressed_key)
deepceleron
Legendary

Offline

Activity: 1512
Merit: 1000

 June 09, 2014, 06:07:36 PM

Be mindful that there is no practical reason to "convert" between uncompressed and compressed public keys. Each has their own Bitcoin address - you cannot spend funds sent to the uncompressed public key's address with the compressed public key.
ftc-c
Newbie

Offline

Activity: 31
Merit: 0

 May 09, 2015, 03:05:01 PM

Who can give a C++ implementation ?
fbueller
Sr. Member

Offline

Activity: 412
Merit: 250

 May 10, 2015, 01:01:24 AM

@ftc-c: Use libsecp256k1, AFAIK it has preprocessor stuff for C++ support, and it's easy enough to work through.

Bitwasp Developer.
samson
Legendary

Offline

Activity: 1624
Merit: 1014

 May 10, 2015, 05:22:53 PMLast edit: May 10, 2015, 06:58:01 PM by samson

The following link shows how to do it in C using the polarssl / mbedTLS library, you should be able to port this across a different crypto library so long as it has a proper 'bignum'/mpi implementation.

https://gist.github.com/flying-fury/6bc42c8bb60e5ea26631

The above example contains test data as well, from the comments '// Set y2 = X^3 + B' and '// Compute square root of y2' you can see where the important part is done.

I used the above to make a dll/so/dylib which does this useful conversion based on the above code.

What deepceleron said also applies, there are two distinct coin addresses which can be created from a single private key depending on whether the public key is 'compressed' or not.

The above conversion is still useful if you use ECC for things like verifying signatures.
CIYAM
Legendary

Offline

Activity: 1890
Merit: 1000

Ian Knowles - CIYAM Lead Developer

 May 10, 2015, 05:28:55 PM

Welcome to use the CIYAM code which includes parts of the Bitcoin code as well (but might be easier to follow in terms of the C++ classes as it doesn't involve any Boost stuff).

https://github.com/ciyam/ciyam/blob/master/src/crypto_keys.cpp

With CIYAM anyone can create 100% generated C++ web applications in literally minutes.

GPG Public Key | 1ciyam3htJit1feGa26p2wQ4aw6KFTejU
Blockchain Mechanic
Full Member

Offline

Activity: 224
Merit: 100

www.patreon.com/blockmechanic

 January 09, 2017, 08:46:38 AM

Be mindful that there is no practical reason to "convert" between uncompressed and compressed public keys. Each has their own Bitcoin address - you cannot spend funds sent to the uncompressed public key's address with the compressed public key.

Hi

So I could use both addresses to receive funds so long as i have the one private key?

Equality vs Equity...
ranochigo
Legendary

Offline

Activity: 1638
Merit: 1126

Somewhat inactive.

 January 09, 2017, 01:22:30 PM

Be mindful that there is no practical reason to "convert" between uncompressed and compressed public keys. Each has their own Bitcoin address - you cannot spend funds sent to the uncompressed public key's address with the compressed public key.

Hi

So I could use both addresses to receive funds so long as i have the one private key?

Yes. The compressed public key and the uncompressed ones have different public keys but they can be derived from the same private key. However, they may be different in the Wallet Import Format, private keys starting with 5 are compressed while the uncompressed ones starts from K or L.

 ░░░░░▄▄██████▄▄░░▄████▀▀▀▀▀▀████▄░███▀░░░░░░░░░░▀█▀████░░░▄██████▄▄░░░██░░░░░█████████░░░░██▌░░░░█████████████████░░░░█████████████████░░░░░███████████████████▄░░▀██████▀░░░████▀█▄▄░░░░░░░░░░▄███░░▀████▄▄▄▄▄▄████▀░░░░░▀▀██████▀▀ .ChipMixer.{ MIXING REINVENTED FOR YOUR PRIVACY #.ChipMixer. ░░░░░▄▄██████▄▄░░▄████▀▀▀▀▀▀████▄░███▀░░░░░░░░░░▀█▀████░░░▄██████▄▄░░░██░░░░░█████████░░░░██▌░░░░█████████████████░░░░█████████████████░░░░░███████████████████▄░░▀██████▀░░░████▀█▄▄░░░░░░░░░░▄███░░▀████▄▄▄▄▄▄████▀░░░░░▀▀██████▀▀
chutium
Newbie

Offline

Activity: 1
Merit: 0

 November 26, 2018, 10:41:57 AMLast edit: November 26, 2018, 11:38:56 AM by chutium

I wrote a converter in javascript language, may will be useful for mobile apps or browser extensions.

It is using javascript big integer library latest version 1.6.36, and work with hex string directly:

Code:
const bigInt = require("big-integer");

var retval = '' + number;
while (retval.length < length) {
retval = '0' + retval;
}
return retval;
}

// Consts for secp256k1 curve. Adjust accordingly
// https://en.bitcoin.it/wiki/Secp256k1
const prime = new bigInt('fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f', 16),

/**
* Point decompress secp256k1 curve
* @param {string} Compressed representation in hex string
* @return {string} Uncompressed representation in hex string
*/
function ECPointDecompress( comp ) {
var signY = new Number(comp[1]) - 2;
var x = new bigInt(comp.substring(2), 16);
// y mod p = +-(x^3 + 7)^((p+1)/4) mod p
var y = x.modPow(3, prime).add(7).mod(prime).modPow( pIdent, prime );
// If the parity doesn't match it's the *other* root
if( y.mod(2).toJSNumber() !== signY ) {
// y = prime - y
y = prime.subtract( y );
}
}

Test with private key from Tim's example 55255657523dd1c65a77d3cb53fcd050bf7fc2c11bb0bb6edabdbd41ea51f641:

Code:
ECPointDecompress('0314fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267')
returns:
Code:
'0414fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267be5645686309c6e6736dbd93940707cc9143d3cf29f1b877ff340e2cb2d259cf'

refer to https://stackoverflow.com/a/53480175/5630352

r^2 = a mod m where m = 3 mod 4 (as secp256k1's p does)
then
r = +-a^((m+1)/4) mod m

So:

y^2 mod p = (x^3 + 7) mod p
y mod p = +-(x^3 + 7)^((p+1)/4) mod p

So calculate (x^3 + 7)^((p+1)/4) mod p, and if the parity of the first answer you get is wrong, then take the negative of that answer (since we're working modulo an odd number, taking the negative will flip the even/odd parity).

Just for fun, here's some Python code that'll do the calculation in the blink of an eye, preset to work on the public key of (the random) private key 55255657523dd1c65a77d3cb53fcd050bf7fc2c11bb0bb6edabdbd41ea51f641

Code:
def pow_mod(x, y, z):
"Calculate (x ** y) % z efficiently."
number = 1
while y:
if y & 1:
number = number * x % z
y >>= 1
x = x * x % z
return number

p = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
compressed_key = '0314fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267'
y_parity = int(compressed_key[:2]) - 2
x = int(compressed_key[2:], 16)
a = (pow_mod(x, 3, p) + 7) % p
y = pow_mod(a, (p+1)//4, p)
if y % 2 != y_parity:
y = -y % p
uncompressed_key = '04{:x}{:x}'.format(x, y)
print(uncompressed_key)
 Pages: [1]