[curves] Ed25519 sigs with Curve25519/X25519 keypairs
Trevor Perrin
trevp at trevp.net
Mon Oct 13 00:06:05 PDT 2014
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/mailarchive/curves/2014/000205.html
https://moderncrypto.org/mailarchive/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 = (A1) * ((A+1)^1) (mod 2^25519)
# 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 = (A1)/(A+1)` ([Ed25519](#Ed25519),
[TwistedEdwards][]). To prevent `A=1` causing a divisionbyzero
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^25519).
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 [PointchevalStern][]) 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/curve2551920060209.pdf>
[Ed25519]: #Ed25519
<a name="Ed25519">**Ed25519:**</a>
<http://ed25519.cr.yp.to/ed2551920110926.pdf>
[PointchevalStern]: #PointchevalStern
<a name="PointchevalStern">**PointchevalStern:**</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
More information about the Curves
mailing list