[curves] Ed25519 sigs with Curve25519/X25519 keypairs

[Trevor Perrin]

We've discussed using Curve25519 keypairs for Ed25519 signatures: in
particular, converting the Curve25519/X25519 format public key to
Ed25519 format, and deriving the deterministic Schnorr nonce directly
from the private scalar:

https://moderncrypto.org/mail-archive/curves/2014/000205.html
https://moderncrypto.org/mail-archive/curves/2014/000212.html

If anyone's interested, I wrote up a spec for this:

https://github.com/trevp/curve25519sigs/blob/master/curve25519sigs.md

********************

Introduction
=
This document describes the use of [Curve25519][] keypairs for
creating and verifying [Ed25519][] signatures.  This enables using a
single public key format for ECDH and signatures.  In some situations,
a single keypair can be used for both ECDH and signatures.

Algorithms
=

Variables
-

    Name       Explanation                                  Size (bytes)
    -----      --------------                               ------------
    a          Private scalar                               32
    A          Curve25519 public key                        32
    A_ed       Ed25519 conversion of Curve25519 public key  32
    B          Ed25519 base point                           -
    random     Random value from secure RNG                 64
    label      [0xFE] || [0xFF]*31 (for different oracles)  32
    msg        Message to be signed                         any
    L          Order of base point                          -

Key generation
-
The private scalar is a typical Curve25519 or Ed25519 private key,
which can be generated by following the advice in
[Curve25519](#Curve25519): "generate 32 uniform random bytes, clear
bits 0, 1, 2 of the first byte, clear bit 7 of the last byte, and set
bit 6 of the last byte."

Signing
-

    Sign(a, msg, random):
      # Derive Schnorr nonce
      r = SHA512(label || a || msg || random)  (mod L)

      # Calculate Ed25519 public key
      A_ed = a * B

      # Create standard Ed25519 signature
      R = r * B
      S = r + SHA512(R || A_ed || msg) * a  (mod L)
      signature = R || S

      # Copy sign bit of public key into unused bit of signature:
      signature[63] |= (A_ed[31] & 0x80)
      return signature

Verifying
-

    Verify(A, msg, signature):
      # Convert Curve25519 public key to Ed25519 form
      A_ed = (A-1) * ((A+1)^-1)  (mod 2^255-19)

      # Move sign bit from signature to public key
      A_ed[31] |= (signature[63] & 0x80)
      signature[63] &= 0x7F

      # Verify standard Ed25519 signature
      return Ed25519_Verify(A_ed, signature, msg)


Implementation considerations
=

Key conversion
-

Converting the Curve25519 public key to Ed25519 is straightforward
using the equivalence `y = (A-1)/(A+1)` ([Ed25519](#Ed25519),
[TwistedEdwards][]).  To prevent `A=-1` causing a division-by-zero
error, this value should be mapped to an Ed25519 value of zero.  This
happens naturally if inversion is done by exponentiation to -1 (mod
2^255-19).

Performance
-
**Signing:** Recalculating the Ed25519 public key on every signature
is simple but slightly inefficient. The public key could be stored for
higher performance.

**Verifying:** Converting the public key and performing a standard
Ed25519 verification is simple but slightly inefficient.  Conversion
could be combined with decompression for higher performance.

Security considerations
=

Sign bit
-
The Ed25519 public key's sign bit is conveyed in the signature.  This
allows an attacker to try to forge a signature for Alice based on
either her actual Ed25519 public key or its negative.  Since both are
legitimate public keys, an attacker who can't break Ed25519 can't
forge signatures for either.

Nonce
-
The [Ed25519][] paper recommends deriving the Schnorr nonce as:

    r = SHA512(nonce_key || msg)  (mod L)

Where both `nonce_key` and the private scalar are derived from a
master key.  To sign with existing scalars we instead do:

    r = SHA512(label || a || msg || random)  (mod L)

The `label` is to aid security proofs in the Random Oracle Model (such
as [Pointcheval-Stern][]) by separating uses of the hash function.
Note that the `label` is not a possible value for `R`.  If using the
same keypair for signatures and ECDH, the ECDH output should be hashed
via a different "random oracle", e.g. SHA512 with a label prefix of
`[0xFF]*32`.

The random value is not essential but helps ensures the nonce and
scalar are independent, and reduces the risk of nonce collisions or
biases.

Acknowledgements
=

Thanks to Robert Ransom for suggesting storing the sign bit in the
signature.  Thanks to Robert Ransom, Mike Hamburg, Samuel Neves, and
Christian Winnerlein for advice and feedback.

References
=
[Curve25519]: #Curve25519
<a name="Curve25519">**Curve25519:**</a>
<http://cr.yp.to/ecdh/curve25519-20060209.pdf>

[Ed25519]: #Ed25519
<a name="Ed25519">**Ed25519:**</a>
<http://ed25519.cr.yp.to/ed25519-20110926.pdf>

[Pointcheval-Stern]: #Pointcheval-Stern
<a name="Pointcheval-Stern">**Pointcheval-Stern:**</a>
<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.8213>

[TwistedEdwards]: #TwistedEdwards
<a name="TwistedEdwards">**TwistedEdwards:**</a>
<http://eprint.iacr.org/2008/013.pdf>

Trevor