How to get uncompressed public key from compressed one ?

brainless

member

Activity: 330

Merit: 34

compress to uncompress

Code:

import binascii

p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F

def decompress_pubkey(pk):
x = int.from_bytes(pk[1:33], byteorder='big')
y_sq = (pow(x, 3, p) + 7) % p
y = pow(y_sq, (p + 1) // 4, p)
if y % 2 != pk[0] % 2:
y = p - y
y = y.to_bytes(32, byteorder='big')
return b'\x04' + pk[1:33] + y

with open('add.txt') as f:
for line in f:
line=line.strip()
print(binascii.hexlify(decompress_pubkey(binascii.unhexlify(line))).decode(),file=open("uncomp.txt", "a"))

uncompress to compress

Code:

def cpub(x,y):
prefix = '02' if y % 2 == 0 else '03'
c = prefix+ hex(x)[2:].zfill(64)
return c
with open('add.txt') as f:
for line in f:
line=line.strip()
x = int(line[2:66], 16)
y = int(line[66:], 16)
pub04=cpub(x,y)

print(pub04,file=open("comp.txt", "a"))

brainless

member

Activity: 330

Merit: 34

https://bitcointalksearch.org/topic/m.57700007

easy script mention here, where you can load pubkeys from file and result print back into new file

pooya87

legendary

Activity: 3472

Merit: 10611

Quote from: Frodek on October 07, 2019, 01:02:35 PM

I wonder, how to compute y = prime - y when y will larger than prime?

in modular arithmetic, the numbers in the group defined by p aren't bigger than p, if they were their remainder (mod p) is calculated hence the finite group. if prime was 5 the group is like this:
{0, 1, 2, 3, 4} when we have 5 we calculate its mod prime and put 0 in its place. for 6 we put 1,...

as for y, it is the vertical coordinate of the points on the curve. and -y is not like regular arithmetic where you flip the sign, -y is defined as (prime - y) so that we mirror the point over x axis and find the other point on curve.

Frodek

member

Activity: 138

Merit: 25

We have:
const prime = new bigInt('fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f', 16),
if( y.mod(2).toJSNumber() !== signY ) {
// y = prime - y
y = prime.subtract( y );

I wonder, how to compute y = prime - y when y will larger than prime?
(may be problem with signed/big unsinged)
Very large case, I don't know how to reproduce,
this cases will throw away when generated private keys?

chutium

newbie

Activity: 1

Merit: 0

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:

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

Code:

ECPointDecompress('0314fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267')

returns:

Code:

'0414fc03b8df87cd7b872996810db8458d61da8448e531569c8517b469a119d267be5645686309c6e6736dbd93940707cc9143d3cf29f1b877ff340e2cb2d259cf'

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

Quote from: TimS on June 08, 2014, 07:53:21 PM

From https://en.wikipedia.org/wiki/Quadratic_residue and http://mersennewiki.org/index.php/Modular_Square_Root, if

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)

ranochigo

legendary

Activity: 3038

Merit: 4418

Crypto Swap Exchange

Quote from: Blockchain Mechanic on January 09, 2017, 03:46:38 AM

Quote from: deepceleron on June 09, 2014, 01: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.

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.

Blockchain Mechanic

full member

Activity: 380

Merit: 103

Developer and Consultant

Quote from: deepceleron on June 09, 2014, 01: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.

Hi

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

CIYAM

legendary

Activity: 1890

Merit: 1086

Ian Knowles - CIYAM Lead Developer

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

samson

legendary

Activity: 2097

Merit: 1070

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.

fbueller

sr. member

Activity: 412

Merit: 287

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

ftc-c

newbie

Activity: 31

Merit: 0

Who can give a C++ implementation ?

deepceleron

legendary

Activity: 1512

Merit: 1036

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.

TimS

sr. member

Activity: 250

Merit: 253

From https://en.wikipedia.org/wiki/Quadratic_residue and http://mersennewiki.org/index.php/Modular_Square_Root, if

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)

Farghaly

newbie

Activity: 38

Merit: 0

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

Topic: How to get uncompressed public key from compressed one ? (Read 3629 times)