0
$\begingroup$

In the context of ECDSA , given that i have a message and a private key , i can change value of k and i will get different signature , doesn't that mean i can create infinite signatures and all of those will be valid and that means i can forge a signature right as i can assume that random signature that i guessed for a message will also be one of those infinite signatures that can be generated using different value of k.

I know things don't work this way so any help in clearing my misunderstanding would be appreciated.

$\endgroup$

1 Answer 1

3
$\begingroup$

There are effectively infinite signatures you can produce, yes. Technically not infinite because $k$ must be less than the order of the elliptic curve group you are using. But that's so many options that you'll never possibly be able to use them all.

That definitely doesn't mean you can forge a signature. Just because there are infinite doesn't mean that they're easy to find. The values you use need to satisfy the verification equation. Brute-force generation of random signatures until one validates will take literally forever. That's why these signature schemes are considered secure. Usually such brute forcing would be as difficult as finding the secret key by brute-force.

$\endgroup$
5
  • $\begingroup$ So is it more like for all k's used there won't be k or k/2 signautres (k/2 because reflection of signature about x axis is also valid) , instead it might be that for multiple k it might generate same signature and hence there will be some finite signatures $\endgroup$
    – Darshan V
    Feb 17, 2022 at 4:56
  • 2
    $\begingroup$ Addition of an analogy: there (most likely) are infinitely many bitstrings which SHA3-256 is all-zero. But we can't find any. $\endgroup$
    – fgrieu
    Feb 17, 2022 at 8:26
  • $\begingroup$ Very informally, there are tonnes of valid signatures (one for each choice of $k$), but many, many, many more invalid ones. The valid ones are well hidden amongst all the invalid ones. $\endgroup$ Feb 17, 2022 at 10:11
  • $\begingroup$ @meshcollider Actually, I think that statement is not provable and might be false. For fixed input, the hash function could be injective (or very close to it) between the domain of $k$ and the image of the hash, even if unlikely. Of course everyone can check that points are on the curve, so only those have to be considered at all. $\endgroup$
    – tylo
    Feb 18, 2022 at 4:32
  • $\begingroup$ @tylo what do you mean by injective for a fixed input? For a fixed input, the hash function is fixed :) $\endgroup$ Feb 18, 2022 at 5:24

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.