1
$\begingroup$

The private key is any random 256 bit (but smaller than prime p) number or must be prime or other condition? For selected $x$ can be found $y$ - decompressing key:

#! /usr/bin/env python3
import binascii
import math
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

print(binascii.hexlify(decompress_pubkey(binascii.unhexlify('0229b3e0919adc41a316aad4f41444d9bf3a9b639550f2aa735676ffff25ba3898'))).decode())
print(binascii.hexlify(decompress_pubkey(binascii.unhexlify('02f15446771c5c585dd25d8d62df5195b77799aa8eac2f2196c54b73ca05f72f27'))).decode())
print(binascii.hexlify(decompress_pubkey(binascii.unhexlify('0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798'))).decode())

Only last x,y pair fulfill (x3+7-y2) % p is zero. Two previous pairs are wrong?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Reading the doc helps, here section 3.2.1 in Sec1v2. It allows to answer the first sentence by: other condition, but the first guess was close. $\endgroup$
    – fgrieu ♦
    Nov 19, 2020 at 13:52
  • $\begingroup$ Note for the programming part see Deriving an ECDSA uncompressed public key from a compressed one $\endgroup$
    – kelalaka
    Nov 19, 2020 at 15:14
  • 1
    $\begingroup$ @fgrieu I've read this question incorrectly. This is a completely a python coding problem. The OP wants to find the $y$ coordinate of the public key and the coding part is not correct. I've given a link that handles this correctly, $\endgroup$
    – kelalaka
    Nov 19, 2020 at 15:18

1 Answer 1

Reset to default
3
$\begingroup$

You are confusing the concepts; the private key vs the public key. Your private key $k$ is an integer which is selected uniform randomly between $1$ to order of the base point $G$, $k \in[1,n-1]$.

  • Basepoint $G$ in compressed for

      0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

  • The order $n$ of $G$, i.e. $[n]G = \mathcal{O}$, where $\mathcal{O}$ is point at infinity, or the identity element in additive elliptic curve group.

    FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C

Your (or any) public key is $[k]G$, which is scalar multiplication and defined as.

$$[k]G = \overbrace{G+\cdots+G}^{{k\hbox{ - }times}}$$

With add double-and-add it can be calculated very efficiently in $\mathcal{O}(\log(n))$-time.

Your failures are due to your python coding ( that is off-topic here) where you want to recover the $y$ value from a compressed public key, not the private key. Rasmus Faber's has an answer in StackOverflow. That is the way you need to find it with Python.

Note: All parameters of the curve can be found on Certicom's SEC 2: Recommended Elliptic Curve Domain Parameters

Improve this answer
$\endgroup$
2
  • $\begingroup$ Not for all x is solution, but how to choose correct x? because private key must have correct x. $\endgroup$
    – Andrzej
    Nov 19, 2020 at 15:26
  • 1
    $\begingroup$ No, as written, the private key is an integer. The public key is a point. What you want is given a compressed public key, you want to find the $y$. In this case, with correct implementation, as linked, you can find it. Note that with the compressed you will reach $y$ and $-y$. The encoding tells to choose the correct one. $\endgroup$
    – kelalaka
    Nov 19, 2020 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.