Elliptic Curve Digital Signature Algorithm: Difference between revisions

From Bitcoin Wiki
Jump to navigation Jump to search
← Older editNewer edit →
NotATether (talk | contribs)
Editors, Permittors
156 edits
beautify variables and constants with code tags
NotATether (talk | contribs)
Editors, Permittors
156 edits
m add code tags for 'mod'
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> = z*s<sup>-1</sup></code> mod <code>n</code> and <code>u<sub>2</sub> = r*s<sup>-1</sup></code> mod <code>n</code>.
* Compute <code>u<sub>1</sub> = z*s<sup>-1</sup>< mod n</code> and <code>u<sub>2</sub> = r*s<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==

Revision as of 08:09, 13 May 2021

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:

  • 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 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).[1]

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.

  • r and s: 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.
  • k: A cryptographicly secure random number which is used as a nonce to calculate the r and s values.
  • dA and QA: 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

The signing algorithm computes the signature pair r and s from dA and z.

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

Important: Do not reuse k 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 k 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 r = x mod n. If r=0, generate another random k and start over.
  • Compute s = k-1(z + r*dA) mod n. If s=0, generate another random k and start over.

Verification Algorithm

The verification algorithm ensures that the signature pair r and s, QA and z are all consistent.

  • Verify that both r and s are between 1 and n-1.
  • Compute u1 = z*s-1< mod n and u2 = r*s-1 mod n.
  • Compute (x, y) = u1*G + u2*QA 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.

See also

References

  1. ↑ "ECDSA Signature Probability Basis". https://crypto.stackexchange.com/a/75997/28556/.

External Links

Retrieved from "https://en.bitcoin.it/w/index.php?title=Elliptic_Curve_Digital_Signature_Algorithm&oldid=68662"