Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.)

share|improve this question

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
    
I guess you then just compare $h$ to $H((sB-hA)AM)$ for verification? –  otus May 20 at 5:34
    
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. –  otus May 20 at 7:02
    
Would you post the numbers you are using? –  Ryan Stovall May 21 at 13:23
    
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 –  otus May 21 at 14:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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