ECDSA is specified in SEC1. It's instantiation with curve P-256 is specified in FIPS 186-4 (or equivalently in SEC2 under the name secp256r1
), and tells that it must use the SHA-256 hash defined by FIPS 180-4.
I'll leave aside ASN.1 decoration (since the question uses none), conversions between integer to bytestring of fixed width (which all are per big-endian convention), and to hexadecimal¹.
Signing using ECDSA on P-256 takes as input
- a private key $d$ (the question's
D
), which is a 32-byte bytestring
- a message, which is bytestring $M$ of $0$ to $2^{61}-1$ bytes
- a random number generator
and outputs
- a signature $S=(r,s)$ consisting of
- an $r$ component (the question's
R
), which is a 32-byte bytestring
- an $s$ component (the question's
S
), which is a 32-byte bytestring
Verifying a signature using ECDSA on P-256 takes as input
- a trusted public key $Q$, which should be a point of curve P-256 other than the point at infinity. It was originally computed as $d\,G$ during key generation. It is defined by its Cartesian coordinates
- $x_Q$ (the question's
Qx
), which is a 32-byte bytestring
- $y_Q$ (the question's
Qy
), which in the question is³ a 32-byte bytestring
- a message $M$
- the signature $S=(r,s)$ in the form output by the signature process.
and outputs valid (if the message matches the one signed and there was no errors) or invalid (in all other cases except a successful forgery).
The question's message is the 27-character Example of ECDSA with P-256
converted to bytestring per some unspecified convention, likely ASCII or UTF-8. Both yield the same 27-byte bytestring $M$
4578616D706C65206F66204543445341207769746820502D323536
Both signing and verification manipulate $M$ only to compute it's SHA-256 hash $H$ (the question's H
), which is a 32-byte bytestring. It is converted to an integer $e$ (the question's E
), which when using P-256 thus SHA-256 is² $H$.
Signing is per SEC1 section 4.1.3. In a nutshell:
- Draw a secret random number $k$ (the question's
K
) in range $[1,n)$, where $n$ is the order of the curve P-256. It is critically important that $k$ is uniformly distributed on this interval and independent⁴ of other $k$.
- Compute the Elliptic Curve point $R=k\,G$ of the curve P-256, where $G$ is the generator point. $R$ has Cartesian coordinates $(x_R,y_R)$ (the question's
R_x
and R_y
), but only $x_R$ is needed.
- Compute $r=x_R\bmod n$ (the question's
R
). If $r=0$ something went wrong⁵, ⁶.
- Compute $k^{-1}$ modulo $n$ (the question's
Kinv
), that is the integer in range $[1,n)$ with $k\,k^{-1}-1$ a multiple of $n$.
- Compute $s=k^{-1}(e+r\,d)\bmod n$. If $s=0$, something went wrong⁵.
- Output $(r,s)$.
CAUTION: Signing can be the target of various attacks, e.g. timing or other side channel, and fault injection. Mitigation of these attacks is difficult.
Verification is per SEC1 section 4.1.4. In a nutshell:
- Check that the point $Q$ of coordinates $(x_Q,y_Q)$ is an ordinary point of P-256; otherwise, output invalid.
- Check that $r$ and $s$ both are in range $[1,n)$; otherwise, output invalid
- Compute $s^{-1}$ modulo $n$ (the question's
Sinv
), that is the integer in range $[1,n)$ with $s\,s^{-1}-1$ a multiple of $n$.
- Compute $u_1=e\,s^{-1}\bmod n$ (the question's
U
)
- Compute $u_2=r\,s^{-1}\bmod n$ (the question's
V
)
- Compute the Elliptic Curve point $R=u_1\,G+u_2\,Q$ of the curve P-256, where $G$ is the generator point, and $Q$ is as determined by the public key. $R$ has Cartesian coordinates $(x_R,y_R)$ (the question's
Rprime.X
and Rprime.Y
), but only $x_R$ is needed.
- If $R$ is the point at infinity, output invalid.
- If $e\bmod n\ne x_R\bmod n$, output invalid (see note⁶).
- Output valid.
DISCLAIMER: This contains simplifications and likely errors⁷. It is only meant as an aid to understand the standards.
¹ Hexadecimal is only for display purposes in the question and this answer. It's use in application is uncommon, and would waste space.
² Some implementations avoid the rare case $e\ge n$ (where $n$ is the order of the curve P-256) by reducing $H$ modulo $n$ to produce $e$. That changes the outcome of neither signature nor verification, thus does not hamper interoperability.
³ If point compression is used, $y_Q$ is reduced to its low-order bit, which combined with $x_Q$ and the curve's equation is enough to fully define point $Q$.
⁴ In particular, independence precludes reuse. If we want to be standards-conformant, that's including when signing the same message with the same key. However, from a security perspective it is safe, exclusively in this case, to reuse an earlier $k$. In some ECDSA variants, that's used to generate $k$ as the output of a Pseudo Random Function keyed by $d$ with input $H$.
⁵ It is then advisable to consider this an attack and erase/zeroize/burninate the private key, although the official thing to do is to try another $k$.
⁶ In overwhelmingly most cases occurring absent attack or deliberate test, $x_R<n$. The official thing is to handle the contrary unmoved, but it is a corner case worth consideration, if only to handle it as above⁵ during signature. The case $e\ge n$ is rare² (like one in four billion), but comparatively very common.
⁷ Thanks to dave_thompson_085 for pointing some of the many errors I made, as usual; and pardon the endless stream of edits.