1
$\begingroup$

Ed25519 signatures consist of $(R, s)$, where $s = r + H(RAM)a$ $mod$ $l$, and $R = rB$. This differs from the Schnorr signature where instead of $R$, the signature contains the hash $h=H(RAM)$. According to the Elligator paper (page 5) "one can reconstruct $(h, s)$ from $(R, s)$ and vice versa".

I see that $(R, s) => (h, s)$ is trivial, but how would one derive $(R, s)$ from $(h, s)$?

Or more generally, how would the verification equation look like with $(h, s)$ as the signature?

(Motivation: I'd like to use $(h, s)$ as the signature to get indistinguishability from random numbers without needing the Elligator 2 map. Probably means no bulk verification, but that's not needed for what I'm thinking about.)

$\endgroup$

1 Answer 1

1
$\begingroup$

Unless I am missing something, I believe that you can simply compute $R = s*B - h*A$ using point subtraction.

$\endgroup$
4
  • $\begingroup$ I guess you then just compare $h$ to $H((sB-hA)AM)$ for verification? $\endgroup$
    – otus
    May 20, 2014 at 5:34
  • $\begingroup$ I had to do $R = -(h*A-s*B)$ instead. Seems weird, but I think has to do with the modulus $l$. I'll have to figure it out. Pointers would be appreciated. $\endgroup$
    – otus
    May 20, 2014 at 7:02
  • $\begingroup$ Would you post the numbers you are using? $\endgroup$ May 21, 2014 at 13:23
  • $\begingroup$ Link below. It's the ed25519.py from ed25519.cr.yp.to with minimal changes. Switching the commented lines in checkvalid makes the signature no longer pass. gist.github.com/jvarho/0d654fdfb26d0cb2f4cb $\endgroup$
    – otus
    May 21, 2014 at 14:21

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.