Quote from: amaclin1 on November 04, 2018, 02:01:29 PM

1) is it possible to recover non-compressed key from compressed one?
for example: given compressed public key ( this one is well-known CHBS )
0378D430274F8C5EC1321338151E9F27F4C676A008BDF8638D07C0B6BE9AB35C71
need to get
0478D430274F8C5EC1321338151E9F27F4C676A008BDF8638D07C0B6BE9AB35C71A1518063243AC D4DFE96B66E3F2EC8013C8E072CD09B3834A19F81F659CC3455

Yes, it is possible.

public uncompressed key : '04' + 'x' + 'y'

public compressed key : '02' or '03' + 'x' (02 if y is even, 03 if y is odd)

curve equation y^2 = x^3 + 7 mod p
(that means that if (x,y) satisfies the equation, then (x,-y) satisfies the equation too --> https://github.com/bitcoinbook/bitcoinbook/blob/develop/images/mbc2_0407.png )

compressed key: 0378D430274F8C5EC1321338151E9F27F4C676A008BDF8638D07C0B6BE9AB35C71
03 : y odd
78D430274F8C5EC1321338151E9F27F4C676A008BDF8638D07C0B6BE9AB35C71 : x

Then you need only to compute the y value:

(Python)

Code:

> p=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
>
> x=0x78D430274F8C5EC1321338151E9F27F4C676A008BDF8638D07C0B6BE9AB35C71
>
> x3=pow(x,3,p) --> x^3 = x^3 mod p
>
> y2=(x3+7) % p --> y^2 = x^3 + 7 mod p
>
> y=pow(y2,(p+1)/4,p) --> this line computes sqrt(y^2) = y
>
> hex(y)
'0x5eae7f9cdbc532b201694991c0d137fec371f8d32f64c7cb5e607e08a633c7da'
>
because this y is even, we compute -y = p-y (if y is even, p-y is always odd and viceversa)
>
> hex(p-y)
>'0xa1518063243acd4dfe96b66e3f2ec8013c8e072cd09b3834a19f81f659cc3455'

then: A1518063243ACD4DFE96B66E3F2EC8013C8E072CD09B3834A19F81F659CC3455 : y (odd)

uncompressed key = '04' + 'x' + 'y'

Code:

0478D430274F8C5EC1321338151E9F27F4C676A008BDF8638D07C0B6BE9AB35C71A1518063243ACD4DFE96B66E3F2EC8013C8E072CD09B3834A19F81F659CC3455

Quote from: amaclin1 on November 04, 2018, 02:01:29 PM

2) is it possible to recover `message digest` from public key and signature (assume it is valid)?

No, I think it is not possible.
Let (r,s) be the signature, m the message, e = H(m) the message digest, G the curve generator, d the private key, P=d*G the public key.

ECDSA works this way:
1) pick a random nonce k (a private key you use once) in [1,n-1]
2) k -> k*G = Q(xq,yq) then r = xq mod n (r is more or less like the x coordinate of Q)
3) s = k^-1 * (r*d + e) mod n

Then k*s = (r*d + e) mod n --> e = (s*k - r*d) mod n you know r and s (the signature) but not k and s (the two private keys), then you cannot retrieve the value of 'e'. (Usually you know 'e' too, in that case if you found out k, you could get d easily or viceversa, because it would be an equation with 4 known values and only 1 unknown.)

You could retrieve only e*G, because:

e*G = s*k*G - r*d*G = s*Q - r*P mod n, but again from e*G you can't retrieve the message digest 'e' (it would be like getting a private key from the public one).

Usually, when you verify a signature, you know 'e', and s*Q = e*G + r*P mod n -> Q = s^-1*e*G + s^-1*r*P, the last equation can be verified by knowing r, s, e, P.