5
$\begingroup$

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
Q_x:     B7E08AFDFE94BAD3F1DC8C734798BA1C62B3A0AD1E9EA2A38201CD0889BC7A19
Q_y:     3603F747959DBF7A4BB226E41928729063ADC7AE43529E61B563BBC606CC5E09
H:       A41A41A12A799548211C410C65D8133AFDE34D28BDD542E4B680CF2899C8A8C4
E:       A41A41A12A799548211C410C65D8133AFDE34D28BDD542E4B680CF2899C8A8C4
Sinv:    F63AFA3939902A4CA9F019CE77E5A59FB48E4CAA50EB9601EF02809E033F9057
U:       B807BF3281DD13849958F444FD9AEA808D074C2C48EE8382F6C47A435389A17E
V:       1777F73443A4D68C23D1FC4CB5F8B7F2554578EE87F04C253DF44EFD181C184C
Rprime.X:2B42F576D07F4165FF65D1F3B1500F81E44C316F1F0B3EF57325B69ACA46104F
Rprime.Y:3CE76603264661EA2F602DF7B4510BBC9ED939233C553EA5F42FB3F1338174B5
Rprime:  2B42F576D07F4165FF65D1F3B1500F81E44C316F1F0B3EF57325B69ACA46104F
Verification Passed!
$\endgroup$
1
  • $\begingroup$ @fgrieu Thank you so much $\endgroup$ Apr 21, 2020 at 8:09

1 Answer 1

10
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 22, 2020 at 1:24
  • $\begingroup$ @dave_thompson_085: thank you for the corrections. Having the private key in verification was baad! $\endgroup$
    – fgrieu
    Apr 22, 2020 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.