1
$\begingroup$

Suppose in a network, the identity of users is their public key, which is generated based on the ECDSA algorithm. That is, to create a valid identity, a user must generate an ECDSA public key and then send it to the network administrator for validation. Then, the network administrator needs to know if the user followed all the ECDSA key generation steps correctly to ensure that the user's public key is a valid ECDSA public key.

The question is if the administrator is able to do this confirmation? and how to do it?

I propose here my solution, although I am not sure if the approach is Ok.

Assume a user generates a fake public key claiming it is generated according to the ECDSA algorithm. He must send the key to the network administrator for verification.

The committee then to verify the key sends a text to the user and requests him to sign in. After receiving the signed text verifies the signature using the user's public key. If the result of signature verification is true, it means that the public key is a correct public key, otherwise the user's public key is rejected as an invalid public key which is not generated based on the ECDSA algorithm.

$\endgroup$
13
  • $\begingroup$ You have a strange question. Does the user really have a fake public key or not? During registration get the public key, done! $\endgroup$
    – kelalaka
    Commented Nov 4, 2022 at 18:31
  • $\begingroup$ @Questioner: Your answer has nothing to do with your question. I have changed the title so that it corresponds to the answer. $\endgroup$
    – mentallurg
    Commented Nov 4, 2022 at 19:58
  • $\begingroup$ @mentallurg , No, you can reject my answer, but the question is clear. A public key has been sent to you; Are you able to know if the public key is a correct ECDSA public key? If yes, how? $\endgroup$
    – Questioner
    Commented Nov 4, 2022 at 21:10
  • 2
    $\begingroup$ ECDSA is one of the various algorithms that you can perform using an EC key. ECDH is another. So there is no such thing as an "ECDSA key". Furthermore, if the verification fails is says nothing about the type of key, only that the public key doesn't belong to the same key pair as the private key. Your method of first sending a public key and then a signature doesn't put any trust in the public key; it is vulnerable to man-in-the-middle attacks amongst others. Not sure if that's OK with you; generally it isn't. $\endgroup$
    – Maarten Bodewes
    Commented Nov 5, 2022 at 0:59
  • 1
    $\begingroup$ In Bitcoin network one doesn't care who is the owner. What they care the creator of the transaction has the money or not. This is why people protect their private key as their most valuable asset.. $\endgroup$
    – kelalaka
    Commented Nov 5, 2022 at 7:43

1 Answer 1

2
$\begingroup$

to create a valid identity, a user must generate an ECDSA public key and then send it to the network administrator for validation

That's under-specified, lacking:

With this, there is a well-defined process to verify that the public key is valid. First check that it is per the specified format, and peel that as necessary to perform Validation of Elliptic Curve Public Key, and within this the Elliptic Curve Public Key Validation Primitive (notice that depending on the public key format, it might be necessary to first perform point decompression as in Octet-String-to-Elliptic-Curve-Point Conversion).

Update: A common public key format in bitcoin (after 0.6) is the raw compressed public-key format for the implicitly specified curve secp256k1. A validity check of that boils down to:

  • Check that the public key is exactly 33 bytes.

  • Check that its first byte is 02h or 03h (this byte codes the parity of the $y$ coordinate, and needs no further check).

  • Convert the remaining 32 bytes to integer $x$ per big-endian binary convention, which implies $0\le x<2^{256}$.

  • Check that $x<p$, where $p$ is the prime $2^{256}-2^{32}-977$.

  • Compute $s\gets(x^3+7)\bmod p\,$

  • Check that $s^{(p-1)/2}\bmod p\,=\,1$. Per Euler's criterion, this verifies that there exists integer solutions $y$ to the curve's equation $y^2\equiv x^3+7\pmod p\,$. On curves with cofactor $h=1$, including secp256k1, this proves there exists a matching private key.

    Note: Sometime we need the Cartesian coordinates of the curve point defined by the public key. Since $p\equiv 3\pmod 4$ for secp256k1, that can be done efficiently together with a slightly modified version of the above last step:

    • Compute $y\gets s^{(p+1)/4}\bmod p\,$.
    • Check that $y^2\bmod p\,=\,s$, which completes the check.
    • If the low order bit of $y$ does not match the low order bit of the first byte of the public key, then change $y$ to $p-y\,$. Now $(x,y)$ are the desired Cartesian coordinates, with both $x$ and $y$ in $[1,p)$.

The above tells how to check that the public key is valid, but not that the user (or anyone) knows the corresponding private key. This is best done after validation of the public key (in the above sense), then by the challenge/response method in the question.

Checking that the user knows the corresponding private key has one advantage: if the "text to the user" is unique to each key validation, and can't be confused with other messages that the key will sign, then this prevents a user from registering the preexisting public key of another person (which private key is secret).

$\endgroup$
7
  • $\begingroup$ Thx for your answer. There are two points: The first one is that the link with title : " Validation of Elliptic Curve Public Key" does not open. The second one is that user @mentallurg had changed the title of my question. I changed it again to the correct title. The title of the question is : "How to know if a public key has been created based on the ECDSA algorithm?" And based on your answer apparently based on the format of the public key it is possible to know whether the user has followed the ECDSA algorithm to generate the key. I just need the link to know how to verify the key's format. $\endgroup$
    – Questioner
    Commented Nov 4, 2022 at 21:30
  • $\begingroup$ Additional comment is that the network is similar to the Bitcoin network and there is no centralized entity for the registration. $\endgroup$
    – Questioner
    Commented Nov 4, 2022 at 21:31
  • $\begingroup$ I found the document using its title. It's here: iacr.org/archive/pkc2003/25670211/25670211.pdf $\endgroup$
    – Questioner
    Commented Nov 4, 2022 at 21:59
  • 1
    $\begingroup$ @Questioner: that was not the document that I had in mind. I fixed the links, and added some details. If you decide on a curve and key format (e.g. secp256k1 and 33-byte compressed public key format) I can detail how that's verified by a simple (yet strictly correct) method, without any reference. $\endgroup$
    – fgrieu
    Commented Nov 5, 2022 at 15:56
  • 1
    $\begingroup$ @Questioner: yes. That's two common and equivalent notations to designate base 16. the $_h$ stands for hexadecimal. $\endgroup$
    – fgrieu
    Commented Nov 7, 2022 at 18:14

Your Answer

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

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