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 _______________________________________________ Curves mailing list [email protected] https://moderncrypto.org/mailman/listinfo/curves
