amaclin1 (OP)
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
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
2) is it possible to recover `message digest` from public key and signature (assume it is valid)?
|
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 04, 2018, 03:06:43 PM Last edit: November 07, 2018, 07:29:33 PM by 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: 03 78D430274F8C5EC1321338151E9F27F4C676A008BDF8638D07C0B6BE9AB35C7103 : y odd 78D430274F8C5EC1321338151E9F27F4C676A008BDF8638D07C0B6BE9AB35C71 : xThen you need only to compute the y value: (Python) > 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' 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 nThen 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
Copper Member
Jr. Member
Offline
Activity: 115
Merit: 4
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 20, 2018, 04:10:14 AM |
|
(Python) > 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' 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-bitcointo 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: 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
Legendary
Offline
Activity: 1040
Merit: 2785
Bitcoin and C♯ Enthusiast
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 20, 2018, 05:20:46 AM Last edit: November 20, 2018, 05:36:37 AM by Coding Enthusiast Merited by NeuroticFish (3), ABCbits (1) |
|
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: 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 y2=... is in fact y2=... 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
Copper Member
Jr. Member
Offline
Activity: 115
Merit: 4
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 20, 2018, 06:18:26 AM |
|
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. ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) 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 y2=... is in fact y2=... 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
Legendary
Offline
Activity: 1040
Merit: 2785
Bitcoin and C♯ Enthusiast
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 20, 2018, 07:53:36 AM |
|
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. ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) 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
Copper Member
Jr. Member
Offline
Activity: 115
Merit: 4
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 20, 2018, 11:48:09 AM |
|
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. ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif) Thanks, that was a very accessible post!
|
|
|
|
|
aplistir
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
November 20, 2018, 03:39:00 PM Last edit: November 20, 2018, 06:51:40 PM by 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.
|
My Address: 121f7zb2U4g9iM4MiJTDhEzqeZGHzq5wLh
|
|
|
arulbero
Legendary
Offline
Activity: 1915
Merit: 2074
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
December 27, 2018, 04:26:31 PM Last edit: December 27, 2018, 05:05:06 PM by 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.htmlwe see how this tx was constructed we get this data: >>> 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 >>> 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 04 X = 2CB265BF10707BF49346C3515DD3D16FC454618C58EC0A0FF448A676C54FF713 Y = B317A494AB75813F8737AC779BDF68AC5235C683A0FF92AEB81655DE137FB862
As expected, X = r !
|
|
|
|
a.a
Member
![*](https://bitcointalk.org/Themes/custom1/images/star.gif)
Offline
Activity: 126
Merit: 36
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
May 09, 2021, 12:43:35 AM Last edit: May 09, 2021, 01:26:07 AM by a.a Merited by NotATether (3) |
|
Leaving here the code for typescript/javascript as it is maybe useful for others. Thx arulbero for the python 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: console.log(retrieve(0x02a521a07e98f78b03fc1e039bc3a51408cd73119b5eb116e583fe57dc8db07aean)); results in 0x04a521a07e98f78b03fc1e039bc3a51408cd73119b5eb116e583fe57dc8db07aea6fb15c871dd 7cf7d287390acd4e09d41f705081a98d5fe3a930ca032525dbcdc console.log(retrieve(0x0378D430274F8C5EC1321338151E9F27F4C676A008BDF8638D07C0B6BE9AB35C71n)); results in 0x0478d430274f8c5ec1321338151e9f27f4c676a008bdf8638d07c0b6be9ab35c71a1518063243 acd4dfe96b66e3f2ec8013c8e072cd09b3834a19f81f659cc3455
|
|
|
|
|