Elliptic Curve Digital Signature Algorithm - Revision history

TeamDman at 02:31, 3 April 2022

2022-04-03T02:31:06Z

← Older revision		Revision as of 02:31, 3 April 2022
Line 33:		Line 33:

	* Verify that both <code>r</code> and <code>s</code> are between <code>1</code> and <code>n-1</code>.		* Verify that both <code>r</code> and <code>s</code> are between <code>1</code> and <code>n-1</code>.
	* Compute <code>u<sub>1</sub> = zs<sup>-1</sup>< mod n</code> and <code>u<sub>2</sub> = rs<sup>-1</sup> mod n</code>.		* Compute <code>u<sub>1</sub> = zs<sup>-1</sup> mod n</code> and <code>u<sub>2</sub> = rs<sup>-1</sup> mod n</code>.
	* Compute <code>(x, y) = u<sub>1</sub>G + u<sub>2</sub>Q<sub>A</sub></code> and ensure it is not equal to the point at infinity. The point at infinity is a special point that results when you add two points whose result would otherwise not lie on the curve, such as two points with the same X value but inverted Y values.		* Compute <code>(x, y) = u<sub>1</sub>G + u<sub>2</sub>Q<sub>A</sub></code> and ensure it is not equal to the point at infinity. The point at infinity is a special point that results when you add two points whose result would otherwise not lie on the curve, such as two points with the same X value but inverted Y values.
	* If <code>r = x mod n</code> then the signature is valid. Otherwise, or if any of the checks fail, then the signature is invalid.		* If <code>r = x mod n</code> then the signature is valid. Otherwise, or if any of the checks fail, then the signature is invalid.

NotATether: add code tags for 'mod'

2021-05-13T08:09:33Z

add code tags for 'mod'

NotATether: beautify variables and constants with code tags

2021-05-13T08:07:31Z

beautify variables and constants with code tags

Jessedegans: Fix typo

2021-05-10T11:39:03Z

Fix typo

← Older revision		Revision as of 11:39, 10 May 2021
Line 30:		Line 30:
	== Verification Algorithm ==		== Verification Algorithm ==

	The ~~verificatin~~ algorithm ensures that the signature pair ''r'' and ''s'', ''Q<sub>A</sub>'' and ''z'' are all consistent.		The verification algorithm ensures that the signature pair ''r'' and ''s'', ''Q<sub>A</sub>'' and ''z'' are all consistent.

	* Verify that both ''r'' and ''s'' are between ''1'' and ''n-1''.		* Verify that both ''r'' and ''s'' are between ''1'' and ''n-1''.

NotATether: Fix typo

2021-04-14T08:57:39Z

Fix typo

← Older revision		Revision as of 08:57, 14 April 2021
Line 35:		Line 35:
	* Compute ''u<sub>1</sub> = zs<sup>-1</sup>'' mod ''n'' and ''u<sub>2</sub> = rs<sup>-1</sup>'' mod ''n''.		* Compute ''u<sub>1</sub> = zs<sup>-1</sup>'' mod ''n'' and ''u<sub>2</sub> = rs<sup>-1</sup>'' mod ''n''.
	* Compute ''(x, y) = u<sub>1</sub>G + u<sub>2</sub>Q<sub>A</sub>'' and ensure it is not equal to the point at infinity. The point at infinity is a special point that results when you add two points who's result would otherwise not lie on the curve, such as two points with the same X value but inverted Y values.		* Compute ''(x, y) = u<sub>1</sub>G + u<sub>2</sub>Q<sub>A</sub>'' and ensure it is not equal to the point at infinity. The point at infinity is a special point that results when you add two points who's result would otherwise not lie on the curve, such as two points with the same X value but inverted Y values.
	* If ''r = x'' mod ''n'' then the signature is valid. Otherwise, or if any of the checks ~~gal~~, then the signature is invalid.		* If ''r = x'' mod ''n'' then the signature is valid. Otherwise, or if any of the checks fail, then the signature is invalid.

	==See also==		==See also==

NotATether: Add ECDSA algorithm

2021-04-14T08:57:10Z

Add ECDSA algorithm

@@ Line 1: / Line 1: @@
-'''Elliptic Curve Digital Signature Algorithm''' or '''ECDSA''' is a cryptographic algorithm used by Bitcoin to ensure that funds can only be spent by their rightful owners.
+'''Elliptic Curve Digital Signature Algorithm''' or '''ECDSA''' is a cryptographic algorithm used by Bitcoin to ensure that funds can only be spent by their rightful owners. It is dependent on the curve order and hash function used. For bitcoin these are [[Secp256k1]] and SHA256(SHA256()) respectively.
 A few concepts related to ECDSA:
@@ Line 5: / Line 5: @@
 * [[public key]]: A number that corresponds to a private key, but does not need to be kept secret.  A public key can be calculated from a private key, but not vice versa.  A public key can be used to determine if a signature is genuine (in other words, produced with the proper key) without requiring the private key to be divulged.  In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called ''x''. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called ''x'' and ''y'' (2 * 32 bytes). The prefix of a compressed key allows for the ''y'' value to be derived from the ''x'' value.
 * [[signature]]: A number that proves that a signing operation took place.  A signature is mathematically generated from a [[hash]] of something to be signed, plus a private key.  The signature itself is two numbers known as ''r'' and ''s''.  With the public key, a mathematical algorithm can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Resulting signatures are either 73, 72, or 71 bytes long (with approximate probabilities of 25%, 50%, and 25%, respectively--although sizes even smaller than that are possible with exponentially decreasing probability).<ref>{{cite web | url=https://crypto.stackexchange.com/a/75997/28556/ | title=ECDSA Signature Probability Basis }}</ref>
 ==See also==

Jhfrontz: Add clarification of (and reference to) signature length

2019-11-25T19:33:57Z

Add clarification of (and reference to) signature length

← Older revision		Revision as of 19:33, 25 November 2019
Line 4:		Line 4:
	* [[private key]]: A secret number, known only to the person that generated it. A private key is essentially a randomly generated number. In Bitcoin, someone with the private key that corresponds to funds on the [[block chain]] can spend the funds. In Bitcoin, a private key is a single unsigned 256 bit integer (32 bytes).		* [[private key]]: A secret number, known only to the person that generated it. A private key is essentially a randomly generated number. In Bitcoin, someone with the private key that corresponds to funds on the [[block chain]] can spend the funds. In Bitcoin, a private key is a single unsigned 256 bit integer (32 bytes).
	* [[public key]]: A number that corresponds to a private key, but does not need to be kept secret. A public key can be calculated from a private key, but not vice versa. A public key can be used to determine if a signature is genuine (in other words, produced with the proper key) without requiring the private key to be divulged. In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called ''x''. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called ''x'' and ''y'' (2 * 32 bytes). The prefix of a compressed key allows for the ''y'' value to be derived from the ''x'' value.		* [[public key]]: A number that corresponds to a private key, but does not need to be kept secret. A public key can be calculated from a private key, but not vice versa. A public key can be used to determine if a signature is genuine (in other words, produced with the proper key) without requiring the private key to be divulged. In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called ''x''. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called ''x'' and ''y'' (2 * 32 bytes). The prefix of a compressed key allows for the ''y'' value to be derived from the ''x'' value.
	* [[signature]]: A number that proves that a signing operation took place. A signature is mathematically generated from a [[hash]] of something to be signed, plus a private key. The signature itself is two numbers known as ''r'' and ''s''. With the public key, a mathematical algorithm can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. ~~Signatures~~ are either 73, 72, or 71 bytes long, with probabilities ~~approximately~~ 25%, 50% and 25% respectively, although sizes even smaller than that are possible with exponentially decreasing probability.		* [[signature]]: A number that proves that a signing operation took place. A signature is mathematically generated from a [[hash]] of something to be signed, plus a private key. The signature itself is two numbers known as ''r'' and ''s''. With the public key, a mathematical algorithm can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Resulting signatures are either 73, 72, or 71 bytes long (with approximate probabilities of 25%, 50%, and 25%, respectively--although sizes even smaller than that are possible with exponentially decreasing probability).<ref>{{cite web \| url=https://crypto.stackexchange.com/a/75997/28556/ \| title=ECDSA Signature Probability Basis }}</ref>

	==See also==		==See also==
	* [[Secp256k1]]		* [[Secp256k1]]
			==References==
			<references />
	==External Links==		==External Links==
	* [https://en.wikipedia.org/wiki/Elliptic_Curve_DSA Elliptic Curve Digital Signature Algorithm - Wikipedia article]		* [https://en.wikipedia.org/wiki/Elliptic_Curve_DSA Elliptic Curve Digital Signature Algorithm - Wikipedia article]

Jhfrontz: Undo revision 67054 by Jhfrontz (talk): Misunderstood context/sentence.

2019-11-25T19:08:09Z

Undo revision 67054 by Jhfrontz (talk): Misunderstood context/sentence.

← Older revision		Revision as of 19:08, 25 November 2019
Line 4:		Line 4:
	* [[private key]]: A secret number, known only to the person that generated it. A private key is essentially a randomly generated number. In Bitcoin, someone with the private key that corresponds to funds on the [[block chain]] can spend the funds. In Bitcoin, a private key is a single unsigned 256 bit integer (32 bytes).		* [[private key]]: A secret number, known only to the person that generated it. A private key is essentially a randomly generated number. In Bitcoin, someone with the private key that corresponds to funds on the [[block chain]] can spend the funds. In Bitcoin, a private key is a single unsigned 256 bit integer (32 bytes).
	* [[public key]]: A number that corresponds to a private key, but does not need to be kept secret. A public key can be calculated from a private key, but not vice versa. A public key can be used to determine if a signature is genuine (in other words, produced with the proper key) without requiring the private key to be divulged. In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called ''x''. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called ''x'' and ''y'' (2 * 32 bytes). The prefix of a compressed key allows for the ''y'' value to be derived from the ''x'' value.		* [[public key]]: A number that corresponds to a private key, but does not need to be kept secret. A public key can be calculated from a private key, but not vice versa. A public key can be used to determine if a signature is genuine (in other words, produced with the proper key) without requiring the private key to be divulged. In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called ''x''. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called ''x'' and ''y'' (2 * 32 bytes). The prefix of a compressed key allows for the ''y'' value to be derived from the ''x'' value.
	* [[signature]]: A number that proves that a signing operation took place. A signature is mathematically generated from a [[hash]] of something to be signed, plus a private key. The signature itself is two numbers known as ''r'' and ''s''. With the public key, a mathematical algorithm can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Signatures are either 73, 72, or 71 bytes long, with ~~[[probability \|~~ probabilities]] approximately 25%, 50% and 25% respectively, although sizes even smaller than that are possible with exponentially decreasing probability.		* [[signature]]: A number that proves that a signing operation took place. A signature is mathematically generated from a [[hash]] of something to be signed, plus a private key. The signature itself is two numbers known as ''r'' and ''s''. With the public key, a mathematical algorithm can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Signatures are either 73, 72, or 71 bytes long, with probabilities approximately 25%, 50% and 25% respectively, although sizes even smaller than that are possible with exponentially decreasing probability.

	==See also==		==See also==

Jhfrontz: Add link to probability

2019-11-25T17:51:18Z

Add link to probability

← Older revision		Revision as of 17:51, 25 November 2019
Line 4:		Line 4:
	* [[private key]]: A secret number, known only to the person that generated it. A private key is essentially a randomly generated number. In Bitcoin, someone with the private key that corresponds to funds on the [[block chain]] can spend the funds. In Bitcoin, a private key is a single unsigned 256 bit integer (32 bytes).		* [[private key]]: A secret number, known only to the person that generated it. A private key is essentially a randomly generated number. In Bitcoin, someone with the private key that corresponds to funds on the [[block chain]] can spend the funds. In Bitcoin, a private key is a single unsigned 256 bit integer (32 bytes).
	* [[public key]]: A number that corresponds to a private key, but does not need to be kept secret. A public key can be calculated from a private key, but not vice versa. A public key can be used to determine if a signature is genuine (in other words, produced with the proper key) without requiring the private key to be divulged. In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called ''x''. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called ''x'' and ''y'' (2 * 32 bytes). The prefix of a compressed key allows for the ''y'' value to be derived from the ''x'' value.		* [[public key]]: A number that corresponds to a private key, but does not need to be kept secret. A public key can be calculated from a private key, but not vice versa. A public key can be used to determine if a signature is genuine (in other words, produced with the proper key) without requiring the private key to be divulged. In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called ''x''. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called ''x'' and ''y'' (2 * 32 bytes). The prefix of a compressed key allows for the ''y'' value to be derived from the ''x'' value.
	* [[signature]]: A number that proves that a signing operation took place. A signature is mathematically generated from a [[hash]] of something to be signed, plus a private key. The signature itself is two numbers known as ''r'' and ''s''. With the public key, a mathematical algorithm can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Signatures are either 73, 72, or 71 bytes long, with probabilities approximately 25%, 50% and 25% respectively, although sizes even smaller than that are possible with exponentially decreasing probability.		* [[signature]]: A number that proves that a signing operation took place. A signature is mathematically generated from a [[hash]] of something to be signed, plus a private key. The signature itself is two numbers known as ''r'' and ''s''. With the public key, a mathematical algorithm can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Signatures are either 73, 72, or 71 bytes long, with [[probability \| probabilities]] approximately 25%, 50% and 25% respectively, although sizes even smaller than that are possible with exponentially decreasing probability.

	==See also==		==See also==

Belcher: Fix link

2019-02-16T16:28:51Z

Fix link

← Older revision		Revision as of 16:28, 16 February 2019
Line 2:		Line 2:

	A few concepts related to ECDSA:		A few concepts related to ECDSA:
	* [[private key]]: A secret number, known only to the person that generated it. A private key is essentially a randomly generated number. In Bitcoin, someone with the private key that corresponds to funds on the [[~~public ledger~~]] can spend the funds. In Bitcoin, a private key is a single unsigned 256 bit integer (32 bytes).		* [[private key]]: A secret number, known only to the person that generated it. A private key is essentially a randomly generated number. In Bitcoin, someone with the private key that corresponds to funds on the [[block chain]] can spend the funds. In Bitcoin, a private key is a single unsigned 256 bit integer (32 bytes).
	* [[public key]]: A number that corresponds to a private key, but does not need to be kept secret. A public key can be calculated from a private key, but not vice versa. A public key can be used to determine if a signature is genuine (in other words, produced with the proper key) without requiring the private key to be divulged. In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called ''x''. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called ''x'' and ''y'' (2 * 32 bytes). The prefix of a compressed key allows for the ''y'' value to be derived from the ''x'' value.		* [[public key]]: A number that corresponds to a private key, but does not need to be kept secret. A public key can be calculated from a private key, but not vice versa. A public key can be used to determine if a signature is genuine (in other words, produced with the proper key) without requiring the private key to be divulged. In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called ''x''. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called ''x'' and ''y'' (2 * 32 bytes). The prefix of a compressed key allows for the ''y'' value to be derived from the ''x'' value.
	* [[signature]]: A number that proves that a signing operation took place. A signature is mathematically generated from a [[hash]] of something to be signed, plus a private key. The signature itself is two numbers known as ''r'' and ''s''. With the public key, a mathematical algorithm can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Signatures are either 73, 72, or 71 bytes long, with probabilities approximately 25%, 50% and 25% respectively, although sizes even smaller than that are possible with exponentially decreasing probability.		* [[signature]]: A number that proves that a signing operation took place. A signature is mathematically generated from a [[hash]] of something to be signed, plus a private key. The signature itself is two numbers known as ''r'' and ''s''. With the public key, a mathematical algorithm can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Signatures are either 73, 72, or 71 bytes long, with probabilities approximately 25%, 50% and 25% respectively, although sizes even smaller than that are possible with exponentially decreasing probability.

← Older revision		Revision as of 08:09, 13 May 2021
Line 2:		Line 2:

	A few concepts related to ECDSA:		A few concepts related to ECDSA:
	* [[private key]]: A secret number, known only to the person that generated it. A private key is essentially a randomly generated number. In Bitcoin, someone with the private key that corresponds to funds on the [[~~block chain~~]] can spend the funds. In Bitcoin, a private key is a single unsigned 256 bit integer (32 bytes).		* [[private key]]: A secret number, known only to the person that generated it. A private key is essentially a randomly generated number. In Bitcoin, someone with the private key that corresponds to funds on the [[blockchain]] can spend the funds. In Bitcoin, a private key is a single unsigned 256 bit integer (32 bytes).
	* [[public key]]: A number that corresponds to a private key, but does not need to be kept secret. A public key can be calculated from a private key, but not vice versa. A public key can be used to determine if a signature is genuine (in other words, produced with the proper key) without requiring the private key to be divulged. In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called <code>x</code>. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called <code>x</code> and <code>y</code> (2 * 32 bytes). The prefix of a compressed key allows for the <code>y</code> value to be derived from the <code>x</code> value.		* [[public key]]: A number that corresponds to a private key, but does not need to be kept secret. A public key can be calculated from a private key, but not vice versa. A public key can be used to determine if a signature is genuine (in other words, produced with the proper key) without requiring the private key to be divulged. In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called <code>x</code>. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called <code>x</code> and <code>y</code> (2 * 32 bytes). The prefix of a compressed key allows for the <code>y</code> value to be derived from the <code>x</code> value.
	* [[signature]]: A number that proves that a signing operation took place. A signature is mathematically generated from a [[hash]] of something to be signed, plus a private key. The signature itself is two numbers known as <code>r</code> and <code>s</code>. With the public key, a mathematical algorithm can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Resulting signatures are either 73, 72, or 71 bytes long (with approximate probabilities of 25%, 50%, and 25%, respectively--although sizes even smaller than that are possible with exponentially decreasing probability).<ref>{{cite web \| url=https://crypto.stackexchange.com/a/75997/28556/ \| title=ECDSA Signature Probability Basis }}</ref>		* [[signature]]: A number that proves that a signing operation took place. A signature is mathematically generated from a [[hash]] of something to be signed, plus a private key. The signature itself is two numbers known as <code>r</code> and <code>s</code>. With the public key, a mathematical algorithm can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Resulting signatures are either 73, 72, or 71 bytes long (with approximate probabilities of 25%, 50%, and 25%, respectively--although sizes even smaller than that are possible with exponentially decreasing probability).<ref>{{cite web \| url=https://crypto.stackexchange.com/a/75997/28556/ \| title=ECDSA Signature Probability Basis }}</ref>
Line 25:		Line 25:

	* Compute <code>(x, y) = k*G</code>, where <code>G</code> is the generator point of the secp256k1 curve, which is <code>04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8</code> in uncompressed form, however the compressed form can also be used.		* Compute <code>(x, y) = k*G</code>, where <code>G</code> is the generator point of the secp256k1 curve, which is <code>04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8</code> in uncompressed form, however the compressed form can also be used.
	* Compute <code>r = x~~</code>~~ mod ~~<code>~~n</code>. If <code>r=0</code>, generate another random <code>k</code> and start over.		* Compute <code>r = x mod n</code>. If <code>r=0</code>, generate another random <code>k</code> and start over.
	* Compute <code>s = k<sup>-1</sup>(z + r*d<sub>A</sub>)~~</code>~~ mod ~~<code>~~n</code>. If <code>s=0</code>, generate another random <code>k</code> and start over.		* Compute <code>s = k<sup>-1</sup>(z + r*d<sub>A</sub>) mod n</code>. If <code>s=0</code>, generate another random <code>k</code> and start over.

	== Verification Algorithm ==		== Verification Algorithm ==
Line 33:		Line 33:

	* Verify that both <code>r</code> and <code>s</code> are between <code>1</code> and <code>n-1</code>.		* Verify that both <code>r</code> and <code>s</code> are between <code>1</code> and <code>n-1</code>.
	* Compute <code>u<sub>1</sub> = zs<sup>-1</sup><~~/code>~~ mod ~~<code>~~n</code> and <code>u<sub>2</sub> = rs<sup>-1</sup~~></code~~> mod ~~<code>~~n</code>.		* Compute <code>u<sub>1</sub> = zs<sup>-1</sup>< mod n</code> and <code>u<sub>2</sub> = rs<sup>-1</sup> mod n</code>.
	* Compute <code>(x, y) = u<sub>1</sub>G + u<sub>2</sub>Q<sub>A</sub></code> and ensure it is not equal to the point at infinity. The point at infinity is a special point that results when you add two points whose result would otherwise not lie on the curve, such as two points with the same X value but inverted Y values.		* Compute <code>(x, y) = u<sub>1</sub>G + u<sub>2</sub>Q<sub>A</sub></code> and ensure it is not equal to the point at infinity. The point at infinity is a special point that results when you add two points whose result would otherwise not lie on the curve, such as two points with the same X value but inverted Y values.
	* If <code>r = x~~</code>~~ mod ~~<code>~~n</code> then the signature is valid. Otherwise, or if any of the checks fail, then the signature is invalid.		* If <code>r = x mod n</code> then the signature is valid. Otherwise, or if any of the checks fail, then the signature is invalid.

	==See also==		==See also==

← Older revision		Revision as of 08:07, 13 May 2021
Line 1:		Line 1:
	'''Elliptic Curve Digital Signature Algorithm''' or '''ECDSA''' is a cryptographic algorithm used by Bitcoin to ensure that funds can only be spent by their rightful owners. It is dependent on the curve order and hash function used. For bitcoin these are [[Secp256k1]] and SHA256(SHA256()) respectively.		'''Elliptic Curve Digital Signature Algorithm''' or '''ECDSA''' is a cryptographic algorithm used by Bitcoin to ensure that funds can only be spent by their rightful owners. It is dependent on the curve order and hash function used. For bitcoin these are [[Secp256k1]] and <code>SHA256(SHA256())</code> respectively.

	A few concepts related to ECDSA:		A few concepts related to ECDSA:
	* [[private key]]: A secret number, known only to the person that generated it. A private key is essentially a randomly generated number. In Bitcoin, someone with the private key that corresponds to funds on the [[block chain]] can spend the funds. In Bitcoin, a private key is a single unsigned 256 bit integer (32 bytes).		* [[private key]]: A secret number, known only to the person that generated it. A private key is essentially a randomly generated number. In Bitcoin, someone with the private key that corresponds to funds on the [[block chain]] can spend the funds. In Bitcoin, a private key is a single unsigned 256 bit integer (32 bytes).
	* [[public key]]: A number that corresponds to a private key, but does not need to be kept secret. A public key can be calculated from a private key, but not vice versa. A public key can be used to determine if a signature is genuine (in other words, produced with the proper key) without requiring the private key to be divulged. In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called ''x''. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called ''x'' and ''y'' (2 * 32 bytes). The prefix of a compressed key allows for the ''y'' value to be derived from the ''x'' value.		* [[public key]]: A number that corresponds to a private key, but does not need to be kept secret. A public key can be calculated from a private key, but not vice versa. A public key can be used to determine if a signature is genuine (in other words, produced with the proper key) without requiring the private key to be divulged. In Bitcoin, public keys are either compressed or uncompressed. Compressed public keys are 33 bytes, consisting of a prefix either 0x02 or 0x03, and a 256-bit integer called <code>x</code>. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256-bit integers called <code>x</code> and <code>y</code> (2 * 32 bytes). The prefix of a compressed key allows for the <code>y</code> value to be derived from the <code>x</code> value.
	* [[signature]]: A number that proves that a signing operation took place. A signature is mathematically generated from a [[hash]] of something to be signed, plus a private key. The signature itself is two numbers known as ''r'' and ''s''. With the public key, a mathematical algorithm can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Resulting signatures are either 73, 72, or 71 bytes long (with approximate probabilities of 25%, 50%, and 25%, respectively--although sizes even smaller than that are possible with exponentially decreasing probability).<ref>{{cite web \| url=https://crypto.stackexchange.com/a/75997/28556/ \| title=ECDSA Signature Probability Basis }}</ref>		* [[signature]]: A number that proves that a signing operation took place. A signature is mathematically generated from a [[hash]] of something to be signed, plus a private key. The signature itself is two numbers known as <code>r</code> and <code>s</code>. With the public key, a mathematical algorithm can be used on the signature to determine that it was originally produced from the hash and the private key, without needing to know the private key. Resulting signatures are either 73, 72, or 71 bytes long (with approximate probabilities of 25%, 50%, and 25%, respectively--although sizes even smaller than that are possible with exponentially decreasing probability).<ref>{{cite web \| url=https://crypto.stackexchange.com/a/75997/28556/ \| title=ECDSA Signature Probability Basis }}</ref>

	== Primitives ==		== Primitives ==

	The ECDSA signing and verification algorithms make use of a few fundamental variables which are used to obtain a signature, and the reverse process of getting a message from a signature.		The ECDSA signing and verification algorithms make use of a few fundamental variables which are used to obtain a signature and the reverse process of getting a message from a signature.

	* ''r'' and ''s'': These numbers uniquely represent the signature.		* <code>r</code> and <code>s</code>: These numbers uniquely represent the signature.
	* ''z'': The hash of the message we want to sign. Normally we are required to use the left-most N bits of the message hash, where ''N'' is the length of the hash function used, however, this rule does not apply to bitcoin signatures because the length of the hash function used, SHA256, equals the bit length of the secp256k1 curve (256) so no truncation is necessary.		* <code>z</code>: The hash of the message we want to sign. Normally we are required to use the left-most N bits of the message hash, where <code>N</code> is the length of the hash function used, however, this rule does not apply to bitcoin signatures because the length of the hash function used, SHA256, equals the bit length of the secp256k1 curve (256) so no truncation is necessary.
	* ''k'': A cryptographicly secure random number which is used as a nonce to calculate the ''r'' and ''s'' values.		* <code>k</code>: A cryptographicly secure random number which is used as a nonce to calculate the <code>r</code> and <code>s</code> values.
	* ''d<sub>A</sub>'' and ''Q<sub>A</sub>'': These are the private key number and public key point respectively, used to sign and verify the message. Wallets can derive a copy of these when give an address contained inside the wallet.		* <code>d<sub>A</sub></code> and <code>Q<sub>A</sub></code>: These are the private key number and public key point respectively, used to sign and verify the message. Wallets can derive a copy of these when give an address contained inside the wallet.

	== Signing Algorithm ==		== Signing Algorithm ==

	The signing algorithm computes the signature pair ''r'' and ''s'' from ''d<sub>A</sub>'' and ''z''.		The signing algorithm computes the signature pair <code>r</code> and <code>s</code> from <code>d<sub>A</sub></code> and <code>z</code>.

	* Obtain the group order ''n'' of the curve. For Secp256k1 this is FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141.		* Obtain the group order <code>n</code> of the curve. For Secp256k1 this is <code>FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141</code>.
	* Generate a cryptographically secure random number ''k'' between ''1'' and ''n-1''.		* Generate a cryptographically secure random number <code>k</code> between <code>1</code> and <code>n-1</code>.

	'''Important: ''' Do not reuse ''k'' after a signature is made with it, because there are flaws ~~which~~ enable an attacker to derive private keys from signed messages if they know the shared nonce ''k'' used in them.		'''Important: ''' Do not reuse <code>k</code> after a signature is made with it because there are flaws that enable an attacker to derive private keys from signed messages if they know the shared nonce <code>k</code> used in them.

	* Compute ''(x, y) = k*G'', where G is the generator point of the secp256k1 curve, which is 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8 in uncompressed form, however the compressed form can also be used.		* Compute <code>(x, y) = k*G</code>, where <code>G</code> is the generator point of the secp256k1 curve, which is <code>04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8</code> in uncompressed form, however the compressed form can also be used.
	* Compute ''r = x'' mod ''n''. If ''r=0'', generate another random ''k'' and start over.		* Compute <code>r = x</code> mod <code>n</code>. If <code>r=0</code>, generate another random <code>k</code> and start over.
	* Compute ''s = k<sup>-1</sup>(z + r*d<sub>A</sub>)'' mod ''n''. If ''s=0'', generate another random ''k'' and start over.		* Compute <code>s = k<sup>-1</sup>(z + r*d<sub>A</sub>)</code> mod <code>n</code>. If <code>s=0</code>, generate another random <code>k</code> and start over.

	== Verification Algorithm ==		== Verification Algorithm ==

	The verification algorithm ensures that the signature pair ''r'' and ''s'', ''Q<sub>A</sub>'' and ''z'' are all consistent.		The verification algorithm ensures that the signature pair <code>r</code> and <code>s</code>, <code>Q<sub>A</sub></code> and <code>z</code> are all consistent.

	* Verify that both ''r'' and ''s'' are between ''1'' and ''n-1''.		* Verify that both <code>r</code> and <code>s</code> are between <code>1</code> and <code>n-1</code>.
	* Compute ''u<sub>1</sub> = zs<sup>-1</sup>'' mod ''n'' and ''u<sub>2</sub> = rs<sup>-1</sup>'' mod ''n''.		* Compute <code>u<sub>1</sub> = zs<sup>-1</sup></code> mod <code>n</code> and <code>u<sub>2</sub> = rs<sup>-1</sup></code> mod <code>n</code>.
	* Compute ''(x, y) = u<sub>1</sub>G + u<sub>2</sub>Q<sub>A</sub>'' and ensure it is not equal to the point at infinity. The point at infinity is a special point that results when you add two points ~~who's~~ result would otherwise not lie on the curve, such as two points with the same X value but inverted Y values.		* Compute <code>(x, y) = u<sub>1</sub>G + u<sub>2</sub>Q<sub>A</sub></code> and ensure it is not equal to the point at infinity. The point at infinity is a special point that results when you add two points whose result would otherwise not lie on the curve, such as two points with the same X value but inverted Y values.
	* If ''r = x'' mod ''n'' then the signature is valid. Otherwise, or if any of the checks fail, then the signature is invalid.		* If <code>r = x</code> mod <code>n</code> then the signature is valid. Otherwise, or if any of the checks fail, then the signature is invalid.

	==See also==		==See also==