ECDSA math questions

[amaclin1]

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

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

[1714658096]

1714658096

[arulbero]

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

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.

[digitalcitizen]

(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

Wow, thank you for posting this.  I was driving myself insane trying to understand more of the math and how it's actually implemented, trying very small values from links like this one:

https://www.coindesk.com/math-behind-bitcoin

to get a feel for it.  I think I'm getting there.  I hope that ordering and reading Mastering Bitcoin: Programming the Open Blockchain will help with the math, and trying to write my own blockchain parser.

I'm not a math heavyweight, so I have a couple of questions if you have time:

From what I understand so far, there are constants that are always the same in Bitcoin.  This includes the Q (curve generator), the p (for mod p), taken from your code and which I noted in the link to coindesk.  I couldn't see how the order was calculated, given other values.  Can you briefly describe what a base point is?  I think I'm getting a decent idea of what a finite field is.

When trying to find:

Code:

y=pow(y2,(p+1)/4,p)  --> this line computes sqrt(y^2) = y

Is this always how it's done, for any y2, p is always the same, and the (p+1)/4 part is constant as well for getting y from y2?

Thanks again!

[Coding Enthusiast]

I hope that ordering and reading Mastering Bitcoin: Programming the Open Blockchain will help with the math, and trying to write my own blockchain parser.

FWIW you don't need to know "the math behind bitcoin" to write a blockchain parser.

This includes the Q (curve generator),

It is called "G" for Generator not Q!

I couldn't see how the order was calculated, given other values.

Order (or n) is the order of the generator or G.
Order of a point (G is a point on the curve) is the smallest positive integer such that nP = O.

Can you briefly describe what a base point is?

Base point is a point on the curve which is used in public key cryptography.

When trying to find:

Code:

y=pow(y2,(p+1)/4,p)  --> this line computes sqrt(y^2) = y

Is this always how it's done, for any y2, p is always the same, and the (p+1)/4 part is constant as well for getting y from y2?

What you need to have in mind is that calculations used in Elliptic Curve Cryptography are not regular arithmetic. Instead they are Modular Arithmetic. So y²=... is in fact y²=... mod p.
Calculating it requires using special algorithms one example is Tonelli–Shanks algorithm. There are special cases which can speed up the calculation. In case of secp256k1 elliptic curve that bitcoin is using, the prime number has a special characteristic which makes the calculation easier. And that is the fact that p%4=3 so you can use that formula above with (p+1/4 mod p)

[digitalcitizen]

FWIW you don't need to know "the math behind bitcoin" to write a blockchain parser.

Yes.  I just want to know a bit about the math for personal interest.  If that book can help a bit, then good.  Otherwise my primary interest is in writing a blockchain parser, with respect to the book.

It is called "G" for Generator not Q!

Thanks, I'm tired... haha.  But I still needed that pointed out...

I read somewhere that G is the same for everyone in Bitcoin.  I am guessing this means the Generator and its properties, not that it's a scalar or some type of simple constant.  Like you say, G is a point on a curve, and everyone uses the same curve.

Order (or n) is the order of the generator or G.
Order of a point (G is a point on the curve) is the smallest positive integer such that nP = O.

So with G point on the curve, P, n is the smallest positive integer that satisfies nP = O where O is the order.

Base point is a point on the curve which is used in public key cryptography.

This seems to be the same, but with or without a prefix of 04.  So this is a starting point to generate other points on the curve?  Oh hang on.  I'll get a book on crypto.

What you need to have in mind is that calculations used in Elliptic Curve Cryptography are not regular arithmetic. Instead they are Modular Arithmetic. So y²=... is in fact y²=... mod p.

Calculating it requires using special algorithms one example is Tonelli–Shanks algorithm. There are special cases which can speed up the calculation. In case of secp256k1 elliptic curve that bitcoin is using, the prime number has a special characteristic which makes the calculation easier. And that is the fact that p%4=3 so you can use that formula above with (p+1/4 mod p)

Thanks!  I appreciate the response.  That was illuminating.  I tried the Python code and it's becoming more concrete.

I'll have to go out now and dig around a little more.  But if it gets too hard, I'll stick to the coding then, and concentrate on a blockchain parser instead of trying to understand everything...

[Coding Enthusiast]

I read somewhere that G is the same for everyone in Bitcoin.  I am guessing this means the Generator and its properties, not that it's a scalar or some type of simple constant.  Like you say, G is a point on a curve, and everyone uses the same curve.

In order for the elliptic curve cryptography to work we all need to use the same Elliptic Curve. And that curve is defined by a sextuple T = (p, a, b, G, n, h), so yeah G is defined by the curve and is the same when using the same curve.

So with G point on the curve, P, n is the smallest positive integer that satisfies nP = O where O is the order.

No, O is defined as the point at infinity.

This seems to be the same, but with or without a prefix of 04.  So this is a starting point to generate other points on the curve?  Oh hang on.  I'll get a book on crypto.

If you want to understand why there are two public keys (with 0x04 and 0x02/0x03) read this comment:
https://bitcointalk.org/index.php?topic=5049111.msg46800542#msg46800542

[digitalcitizen]

I read somewhere that G is the same for everyone in Bitcoin.  I am guessing this means the Generator and its properties, not that it's a scalar or some type of simple constant.  Like you say, G is a point on a curve, and everyone uses the same curve.

In order for the elliptic curve cryptography to work we all need to use the same Elliptic Curve. And that curve is defined by a sextuple T = (p, a, b, G, n, h), so yeah G is defined by the curve and is the same when using the same curve.

So with G point on the curve, P, n is the smallest positive integer that satisfies nP = O where O is the order.

No, O is defined as the point at infinity.

In order for the elliptic curve cryptography to work we all need to use the same Elliptic Curve. And that curve is defined by a sextuple T = (p, a, b, G, n, h), so yeah G is defined by the curve and is the same when using the same curve.

So with G point on the curve, P, n is the smallest positive integer that satisfies nP = O where O is the order.

No, O is defined as the point at infinity.

So, we are aiming for the number of times a point can be added to itself so the slope is infinite? i.e. if you looked at a simplified graph, the slope of the line is vertical, or nearly vertical.  Or the order is some way you can detect the number of times a point addition can be done to itself before you hit O (infinity).  Is the order selected after a number of point additions, or is there an algorithm that gives you an order after repeated point doubling?  (Is that the same as adding a point to itself?)

This seems to be the same, but with or without a prefix of 04.  So this is a starting point to generate other points on the curve?  Oh hang on.  I'll get a book on crypto.

If you want to understand why there are two public keys (with 0x04 and 0x02/0x03) read this comment:
https://bitcointalk.org/index.php?topic=5049111.msg46800542#msg46800542

Thanks, that was a very accessible post!

[Coding Enthusiast]

My knowledge about point at infinity is a little shaky. Try reading this https://trustica.cz/en/2018/03/29/elliptic-curves-point-at-infinity/ it may help.

[aplistir]

No, O is defined as the point at infinity.

So, we are aiming for the number of times a point can be added to itself so the slope is infinite? i.e. if you looked at a simplified graph, the slope of the line is vertical, or nearly vertical.  Or the order is some way you can detect the number of times a point addition can be done to itself before you hit O (infinity).  Is the order selected after a number of point additions, or is there an algorithm that gives you an order after repeated point doubling?  (Is that the same as adding a point to itself?)

No no no,
you are mixing concepts of the real word with the finite field.
In the real world there is NO infinity (in elliptic curve calculations) You can forever keep doing the additions, and you will NEVER reach infinity.

In the finite field you will reach infinity, when you have to divide by 0 (in the equations).

The order is just the number of different points in the finite field. When you do additions in the finite field, you will go through them one by one, until you have gone through all of them. the last point will be infinity, because you have to divide by zero.

In finite fields, no matter what is your generator point, the point of infinity is the last point, after that the calculations start from the beginning.

------------------
Edit:
In numerical terms, the infinity always happens when the 2 points you are trying to add together are G and -G, two points with the same x coordinate. When calculating the slope s=(y2-y1)/(x2-x1),  the x values are the same, and you cant divide by 0

In real world this cannot happen, as there is no point X in the curve that would get you to -G when adding G to X.

[arulbero]

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.

Let's give an example.

From here: http://www.righto.com/2014/02/bitcoins-hard-way-using-raw-bitcoin.html

we see how this tx was constructed

we get this data:

Code:

>>> n=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 (this is the group order)
>>>
>>> d=0x0caecf01d74102a28aed6a64dcf1cf7b0e41c4dd6c62f70f46febdc32514f0bd (the private key)
>>> e=0x5fda68729a6312e17e641e9a49fac2a4a6a680126610af573caab270d232f850 (the double hash of the tx/message)
>>>
>>> r=0x2cb265bf10707bf49346c3515dd3d16fc454618c58ec0a0ff448a676c54ff713 (the first part of the signature)
>>> s=0x6c6624d762a1fcef4618284ead8f08678ac05b13c84235f1654e6ad168233e82 (the second part of the signature)

Now we try to retrieve the random nonce k  (remember,  k -> k*G = Q(xq,yq)  then r = xq mod n , namely r is the x coordinate of Q, a sort of a public key, and k is its private key)

e = (s*k - r*d)  mod n

s*k = (e + r*d) mod n

k = s^-1 * (e + r*d) mod n

Code:

>>> s_inv=pow(s,n-2,n)  --> we are using the Fermat's little theorem to compute 1/s
>>> hex(s_inv)
'0x947f7b9fc41f37348c3a53a146757b9759e79da5fe039a35a9024bec1fb0ea0cL'
>>>
>>> hex((s_inv * s) % n)  --> we check that s_inv * s = 1
'0x1L'
>>>
>>> k=(s_inv * (e + r*d)) % n
>>> hex(k)
'0x4526b5ab1973ab68afd06517996d22823441dd9ef52663a57de11d6642e961e7L'

k is supposed to be the private key to r.

To have a confirm let's put  4526b5ab1973ab68afd06517996d22823441dd9ef52663a57de11d6642e961e7  here and

we get the public key

Code:

04
X = 2CB265BF10707BF49346C3515DD3D16FC454618C58EC0A0FF448A676C54FF713
Y = B317A494AB75813F8737AC779BDF68AC5235C683A0FF92AEB81655DE137FB862

As expected, X = r !

[a.a]

Leaving here the code for typescript/javascript as it is maybe useful for others. Thx arulbero for the python code.

Code:

export function retrieve(publicKeyCompressed: bigint): string {
	const yOdd = publicKeyCompressed.toString(16).substring(0, 1) === "3";
	const x = BigInt("0x" + publicKeyCompressed.toString(16).substring(1));
	const p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2Fn;
	const x3 = modPow(x, 3n, p);
	const y2 = modPow(x3 + 7n, 1, p);
	let y = modPow(y2, (p + 1n) / 4n, p);
	if (yOdd) {
		y = p - y;
	}

	return "0x04" + bigIntToHex(x) + bigIntToHex(y);
}

function bigIntToHex(value: bigint): string {
	var hex = value.toString(16);
	if (hex.length % 2) {
		hex = '0' + hex;
	}
	return hex;
}

/** taken from npm package bigint-mod-arith */

/**
 * Modular exponentiation b**e mod n. Currently using the right-to-left binary method
 *
 * @param b base
 * @param e exponent
 * @param n modulo
 *
 * @throws {RangeError}
 * Exception thrown when n is not > 0
 *
 * @returns b**e mod n
 */
export function modPow(b: number | bigint, e: number | bigint, n: number | bigint): bigint {
	if (typeof b === 'number') b = BigInt(b)
	if (typeof e === 'number') e = BigInt(e)
	if (typeof n === 'number') n = BigInt(n)

	if (n <= 0n) {
		throw new RangeError('n must be > 0')
	} else if (n === 1n) {
		return 0n
	}

	b = toZn(b, n)

	if (e < 0n) {
		return modInv(modPow(b, abs(e), n), n)
	}

	let r = 1n
	while (e > 0) {
		if ((e % 2n) === 1n) {
			r = r * b % n
		}
		e = e / 2n
		b = b ** 2n % n
	}
	return r
}

/**
 * Finds the smallest positive element that is congruent to a in modulo n
 *
 * @remarks
 * a and b must be the same type, either number or bigint
 *
 * @param a - An integer
 * @param n - The modulo
 *
 * @throws {RangeError}
 * Exception thrown when n is not > 0
 *
 * @returns A bigint with the smallest positive representation of a modulo n
 */
export function toZn(a: number | bigint, n: number | bigint): bigint {
	if (typeof a === 'number') a = BigInt(a)
	if (typeof n === 'number') n = BigInt(n)

	if (n <= 0n) {
		throw new RangeError('n must be > 0')
	}

	const aZn = a % n
	return (aZn < 0n) ? aZn + n : aZn
}

/**
 * Absolute value. abs(a)==a if a>=0. abs(a)==-a if a<0
 *
 * @param a
 *
 * @returns The absolute value of a
 */
export function abs(a: number | bigint): number | bigint {
	return (a >= 0) ? a : -a
}
/**
 * Modular inverse.
 *
 * @param a The number to find an inverse for
 * @param n The modulo
 *
 * @throws {RangeError}
 * Exception thrown when a does not have inverse modulo n
 *
 * @returns The inverse modulo n
 */
export function modInv(a: number | bigint, n: number | bigint): bigint {
	const egcd = eGcd(toZn(a, n), n)
	if (egcd.g !== 1n) {
		throw new RangeError(`${a.toString()} does not have inverse modulo ${n.toString()}`) // modular inverse does not exist
	} else {
		return toZn(egcd.x, n)
	}
}
export interface Egcd {
	g: bigint
	x: bigint
	y: bigint
}
/**
 * An iterative implementation of the extended euclidean algorithm or extended greatest common divisor algorithm.
 * Take positive integers a, b as input, and return a triple (g, x, y), such that ax + by = g = gcd(a, b).
 *
 * @param a
 * @param b
 *
 * @throws {RangeError}
 * This exception is thrown if a or b are less than 0
 *
 * @returns A triple (g, x, y), such that ax + by = g = gcd(a, b).
 */
export function eGcd(a: number | bigint, b: number | bigint): Egcd {
	if (typeof a === 'number') a = BigInt(a)
	if (typeof b === 'number') b = BigInt(b)

	if (a <= 0n || b <= 0n) throw new RangeError('a and b MUST be > 0') // a and b MUST be positive

	let x = 0n
	let y = 1n
	let u = 1n
	let v = 0n

	while (a !== 0n) {
		const q = b / a
		const r: bigint = b % a
		const m = x - (u * q)
		const n = y - (v * q)
		b = a
		a = r
		x = u
		y = v
		u = m
		v = n
	}
	return {
		g: b,
		x: x,
		y: y
	}
}

You can test it:

Code:

console.log(retrieve(0x02a521a07e98f78b03fc1e039bc3a51408cd73119b5eb116e583fe57dc8db07aean));

results in 0x04a521a07e98f78b03fc1e039bc3a51408cd73119b5eb116e583fe57dc8db07aea6fb15c871dd 7cf7d287390acd4e09d41f705081a98d5fe3a930ca032525dbcdc

Code:

console.log(retrieve(0x0378D430274F8C5EC1321338151E9F27F4C676A008BDF8638D07C0B6BE9AB35C71n));

results in 0x0478d430274f8c5ec1321338151e9f27f4c676a008bdf8638d07c0b6be9ab35c71a1518063243 acd4dfe96b66e3f2ec8013c8e072cd09b3834a19f81f659cc3455