0
$\begingroup$

With ECDSA, given $(r,s)$ and $m$, is there a way for a verifier to calculate any (boolean) properties of $k$, without knowing $k$ or the private key $D_A$?

(I understand that $k$ should be random, or follow RFC6979, but I'm curious.)

In particular, could the verifier compute, given a signature $(r,s)$ and a message $m$, that:

  1. $k$ is odd
  2. $k$ has some mathematical relation to one of the curve parameters
  3. $k$ has some mathematical relation to the public key $Q_A$
  4. $k$ has some mathematical relation to the (truncated) message hash $z$
  5. $k$ was deterministically generated with RFC6979. See the article Android Security Vulnerability for the value of $k$ which was used to generate the signature.

(Variable names were taken from here.)

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ By $K$, do you mean $k$ (as in the article)? $\endgroup$
    – fkraiem
    Nov 5, 2015 at 10:44
  • 1
    $\begingroup$ Also, to whom should this be proven? By itself, the statement "$k$ is odd" is meaningless since $k$ is not defined. However, given a signature $(r,s)$ and a message $m$, the statement "the value of $k$ which was used to generate this signature is odd" may be meaningful, assuming there is only one possible $k$, or all the possible $k$s have the same parity. $\endgroup$
    – fkraiem
    Nov 5, 2015 at 10:56
  • $\begingroup$ Yes, I've corrected my question. How did you write the pretty-k in your comment? $\endgroup$
    – Thomas Von Panom
    Nov 5, 2015 at 10:56
  • 1
    $\begingroup$ See this help page on Math.SE about TeX formatting. $\endgroup$
    – fkraiem
    Nov 5, 2015 at 10:59
  • 1
    $\begingroup$ I think you may be using the word "to prove" in a different way than it is normally used in cryptography. Do you actually mean "it is possible to compute/obtain the parity of $k$ from $(r,s)$ and $m$"? $\endgroup$
    – fkraiem
    Nov 5, 2015 at 11:18

1 Answer 1

Reset to default
1
$\begingroup$

There are no relation we are currently aware of. The reason is as follows. The map $$k \mapsto (k G).x$$ is assumed to be a good pseudo random number generator.
(The NSA infiltration of the Dual EC drgb has nothing to do with that fact).
This basically says that k and r can be seen as independant random variables.

Improve this answer
$\endgroup$

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.