[curves] Ed25519 signatures from Curve25519 keys

[Trevor Perrin]

On Mon, Jun 16, 2014 at 5:33 PM, Trevor Perrin <trevp at trevp.net> wrote:
>
> Private-key conversion
> ----
> If the Ed25519 public-key sign-bit is assumed to be zero, the private
> key may need to be adjusted (per Jivsov [9]).  In other words, if
> multiplying the Curve25519 private key by the Ed25519 base point
> yields an Ed25519 x-coordinate that's "negative" as defined in [8],
> the private key (a) must be negated modulo the order of the base point
> (q), i.e. a = q - a.
>
> Some existing curve25519 implementations set bit 254 of the private
> key within the scalarmult function, so will interfere with this
> negation (observation due CodesInChaos).   Robert Ransom proposed
> another way to implement the negation that avoids having to modify
> that code:
>  - Before hashing, flip the sign bit of R
>  - Before hashing, encode the sign bit of A as zero
>  - As the last step, negate S, i.e. S = q - S

Instead of forcing the sign bit to be zero, Robert Ransom also
suggested another approach: Stash the Ed25519 public key's sign bit
alongside or inside the signature.  For example, it could be stored in
the unused high bit of the S value.

Signing with a curve25519 private key is easier than with previous
proposals, since you don't have to do scalar math to adjust the
private key.  You just do an Ed25519 fixed-base scalar mult to
discover the corresponding Ed25519 public key (which can be stored),
then copy the sign bit into the signature.

Thoughts?


Trevor