1
$\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 https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm#cite_note-4

for the value of $k$ which was used to generate the signature.

(Variable names taken from https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm)

$\endgroup$
  • 1
    $\begingroup$ By $K$, do you mean $k$ (as in the article)? $\endgroup$ – fkraiem Nov 5 '15 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 '15 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 '15 at 10:56
  • 1
    $\begingroup$ See this help page on Math.SE about TeX formatting. $\endgroup$ – fkraiem Nov 5 '15 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 '15 at 11:18
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.

$\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.