With RSA PKCS#1 v1.5 it is possible to verify that the signature was generated by the correct private key without actually having access to the data. You just perform the modular exponentiation with the public key to retrieve the padded hash. Then it is possible to verify that the message was padded correctly. Moreover, you retrieve the hash value which can be used to try and guess the input (Internet search, DB lookup, guessing using dictionaries, brute force etc.).

Is there something similar possible with ECDSA? Is it at least possible to verify that the signature was created with a particular private key? Personally I don't see it because the value of $r$ is just random, and I don't see any way to reverse $s = k^{-1} (z + rd_A) \bmod n$ without the hash as input. Is there a way to do that or is it possible to prove mathematically that it infeasible to do so?

  • $\begingroup$ Couldn't find an answer to back up my claim at SO. $\endgroup$ – Maarten Bodewes Mar 31 '20 at 16:01

It is not possible:

Let $d_A, d_B$ be distinct private keys. Then

$$ s=k^{-1}(z+rd_A)=k^{-1}((z+r\;(d_A-d_B)) + rd_B) $$

So the pair $(r, s)$ is not only a valid signature for the public key $d_AG$ and the (partial) hash $z$, but also for the public key $d_BG$ and the message hash $z+r\,(d_A-d_B) \pmod n$.

So in many cases (if there are no restrictions on valid values for $z$), every valid signature $(r, s)$ ("valid" for some public key) and every public key $d_AG$ there will be a message $M$ such that $(r, s)$ is a signature for $M$ under $d_AG$.

  • $\begingroup$ Perfect, welcome to crypto.SE! $\endgroup$ – Maarten Bodewes Apr 1 '20 at 11:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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