Difference between revisions of "Elliptic Curve Digital Signature Algorithm"
(Update with compressed keys) 
NotATether (talk  contribs) m (add code tags for 'mod') 

(17 intermediate revisions by 10 users not shown)  
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 <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 [[  +  * [[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  +  * [[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 256bit integer called <code>x</code>. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256bit 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  +  * [[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%, respectivelyalthough 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 ==  
+  
+  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.  
+  
+  * <code>r</code> and <code>s</code>: These numbers uniquely represent the signature.  
+  * <code>z</code>: The hash of the message we want to sign. Normally we are required to use the leftmost 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.  
+  * <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.  
+  * <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 ==  
+  
+  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 <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 <code>k</code> between <code>1</code> and <code>n1</code>.  
+  
+  '''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 <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 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>) mod n</code>. If <code>s=0</code>, generate another random <code>k</code> and start over.  
+  
+  == Verification Algorithm ==  
+  
+  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 <code>r</code> and <code>s</code> are between <code>1</code> and <code>n1</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.  
+  * 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==  
+  * [[Secp256k1]]  
+  ==References==  
+  <references />  
+  ==External Links==  
+  * [https://en.wikipedia.org/wiki/Elliptic_Curve_DSA Elliptic Curve Digital Signature Algorithm  Wikipedia article]  
+  
+  {{wpElliptic_Curve_DSA}}  
+  
+  [[Category:Technical]] 
Latest 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 256bit integer called
x
. The older uncompressed keys are 65 bytes, consisting of constant prefix (0x04), followed by two 256bit integers calledx
andy
(2 * 32 bytes). The prefix of a compressed key allows for they
value to be derived from thex
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
ands
. 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%, respectivelyalthough sizes even smaller than that are possible with exponentially decreasing probability).^{[1]}
Contents
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
ands
: These numbers uniquely represent the signature. 
z
: The hash of the message we want to sign. Normally we are required to use the leftmost N bits of the message hash, whereN
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 ther
ands
values. 
d_{A}
andQ_{A}
: 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 d_{A}
and z
.
 Obtain the group order
n
of the curve. For Secp256k1 this isFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141
.  Generate a cryptographically secure random number
k
between1
andn1
.
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
, whereG
is the generator point of the secp256k1 curve, which is04 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
. Ifr=0
, generate another randomk
and start over.  Compute
s = k^{1}(z + r*d_{A}) mod n
. Ifs=0
, generate another randomk
and start over.
Verification Algorithm
The verification algorithm ensures that the signature pair r
and s
, Q_{A}
and z
are all consistent.
 Verify that both
r
ands
are between1
andn1
.  Compute
u_{1} = z*s^{1}< mod n
andu_{2} = r*s^{1} mod n
.  Compute
(x, y) = u_{1}*G + u_{2}*Q_{A}
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.