# Understanding example of ECDSA P256

I am new to cryptography, I found the below Example on a nice website, but I am not able to understand the most of the terms used (H:Hash, K:Random number,E=?, Kinv=?,Rx=?=RY?,R=Private key?,D?,S? same in verification). Please help me with the Nomenclature/representation/what is what, of the example ill try to figure out other parts myself. Thanks ahead

##############################################################
Elliptic Curve Digital Signature Algorithm
Curve: P-256 Hash Algorithm: SHA-256
Message to be signed: "Example of ECDSA with P-256"
##############################################################
Signature Generation
H:       A41A41A12A799548211C410C65D8133AFDE34D28BDD542E4B680CF2899C8A8C4
E:       A41A41A12A799548211C410C65D8133AFDE34D28BDD542E4B680CF2899C8A8C4
K:       7A1A7E52797FC8CAAA435D2A4DACE39158504BF204FBE19F14DBB427FAEE50AE
Kinv:    62159E5BA9E712FB098CCE8FE20F1BED8346554E98EF3C7C1FC3332BA67D87EF
R_x:     2B42F576D07F4165FF65D1F3B1500F81E44C316F1F0B3EF57325B69ACA46104F
R_y:     3CE76603264661EA2F602DF7B4510BBC9ED939233C553EA5F42FB3F1338174B5
R:       2B42F576D07F4165FF65D1F3B1500F81E44C316F1F0B3EF57325B69ACA46104F
D:       C477F9F65C22CCE20657FAA5B2D1D8122336F851A508A1ED04E479C34985BF96
S:       DC42C2122D6392CD3E3A993A89502A8198C1886FE69D262C4B329BDB6B63FAF1
Signature
R:       2B42F576D07F4165FF65D1F3B1500F81E44C316F1F0B3EF57325B69ACA46104F
S:       DC42C2122D6392CD3E3A993A89502A8198C1886FE69D262C4B329BDB6B63FAF1
=============================================================
Signature Verification
H:       A41A41A12A799548211C410C65D8133AFDE34D28BDD542E4B680CF2899C8A8C4
E:       A41A41A12A799548211C410C65D8133AFDE34D28BDD542E4B680CF2899C8A8C4
Sinv:    F63AFA3939902A4CA9F019CE77E5A59FB48E4CAA50EB9601EF02809E033F9057
U:       B807BF3281DD13849958F444FD9AEA808D074C2C48EE8382F6C47A435389A17E
V:       1777F73443A4D68C23D1FC4CB5F8B7F2554578EE87F04C253DF44EFD181C184C
Rprime.X:2B42F576D07F4165FF65D1F3B1500F81E44C316F1F0B3EF57325B69ACA46104F
Rprime.Y:3CE76603264661EA2F602DF7B4510BBC9ED939233C553EA5F42FB3F1338174B5
Rprime:  2B42F576D07F4165FF65D1F3B1500F81E44C316F1F0B3EF57325B69ACA46104F
Verification Passed!

• @fgrieu Thank you so much – Yash Vardhan Apr 21 at 8:09

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. 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.

• In your first (above the line) description, verification does NOT use d. Also 'avhoc' is not a word; 'awry' is but has the connotation 'wrong in only a minor unimportant way', so it would be better to use the simple, clear 'wrong'. OTOH I notice you spelled 'renowned' correctly, but left out 'of'; it used to be a purported 'rule' on Usenet that any post about grammatical correction would itself contain a grammatical error. – dave_thompson_085 Apr 22 at 1:24
• @dave_thompson_085: thank you for the corrections. Having the private key in verification was baad! – fgrieu Apr 22 at 4:28