Edx25519 implemented

Edx25519 is a variant of EdDSA on curve25519 which allows for repeated
derivation of private and public keys, independently.  The private keys
in Edx25519 initially correspond to the data after expansion and
clamping in EdDSA.  However, this correspondence is lost after deriving
further keys from existing ones.  The public keys and signature
verification are compatible with EdDSA.

The ability to repeatedly derive key material is used for example in the
context of age restriction in GNU Taler.

The scheme that has been implemented is as follows:

/* Private keys in Edx25519 are pairs (a, b) of 32 byte each.
 * Initially they correspond to the result of the expansion
 * and clamping in EdDSA.
 */

Edx25519_generate_private(seed) {
  /* EdDSA expand and clamp */
  dh := SHA-512(seed)
  a := dh[0..31]
  b := dh[32..64]
  a[0]  &= 0b11111000
  a[31] &= 0b01111111
  a[31] |= 0b01000000

  return (a, b)
}

Edx25519_public_from_private(private) {
  /* Public keys are the same as in EdDSA */
  (a, _) := private
  return [a] * G
}

Edx25519_blinding_factor(P, seed) {
  /* This is a helper function used in the derivation of
   * private/public keys from existing ones.  */
  h1 := HKDF_32(P, seed)

  /* Ensure that h == h % L */
  h := h1 % L

  /* Optionally: Make sure that we don't create weak keys. */
  P' := [h] * P
  if !( (h!=1) && (h!=0) && (P'!=E) ) {
    return Edx25519_blinding_factor(P, seed+1)
  }

  return h
}

Edx25519_derive_private(private, seed) {
  /* This is based on the definition in
   * GNUNET_CRYPTO_eddsa_private_key_derive.  But it accepts
   * and returns a private pair (a, b) and allows for iteration.
   */
  (a, b) := private
  P := Edx25519_public_key_from_private(private)
  h := Edx25519_blinding_factor(P, seed)

  /* Carefully calculate the new value for a */
  a1 := a / 8;
  a2 := (h  * a1) % L
  a' := (a2 *  8) % L

  /* Update b as well, binding it to h.
     This is an additional step compared to GNS. */
  b' := SHA256(b ∥ h)

  return (a', b')
}

Edx25519_derive_public(P, seed) {
  h := Edx25519_blinding_factor(P, seed)
  return [h]*P
}

Edx25519_sign(private, message) {
  /* As in Ed25519, except for the origin of b */
  (d, b) := private
  P := Edx25519_public_from_private(private)
  r := SHA-512(b ∥ message)
  R := [r] * G
  s := r + SHA-512(R ∥ P ∥ message) * d % L

  return (R,s)
}

Edx25519_verify(P, message, signature) {
  /* Identical to Ed25519 */
  (R, s) := signature
  return [s] * G == R + [SHA-512(R ∥ P ∥ message)] * P
}

1 files changed, 8 insertions, 0 deletions

diff --git a/src/util/Makefile.am b/src/util/Makefile.am
index 406d42b1e..9cb7da15b 100644
--- a/src/util/Makefile.am
+++ b/src/util/Makefile.am
@@ -66,6 +66,7 @@ libgnunetutil_la_SOURCES = \
   crypto_ecc_gnsrecord.c \
   $(DLOG) \
   crypto_ecc_setup.c \
+  crypto_edx25519.c \
   crypto_hash.c \
   crypto_hash_file.c \
   crypto_hkdf.c \
@@ -297,6 +298,7 @@ check_PROGRAMS = \
  test_crypto_ecdhe \
  test_crypto_ecdh_eddsa \
  test_crypto_ecdh_ecdsa \
+ test_crypto_edx25519 \
  $(DLOG_TEST) \
  test_crypto_hash \
  test_crypto_hash_context \
@@ -470,6 +472,12 @@ test_crypto_eddsa_LDADD = \
  libgnunetutil.la \
  $(LIBGCRYPT_LIBS)
 
+test_crypto_edx25519_SOURCES = \
+ test_crypto_edx25519.c
+test_crypto_edx25519_LDADD = \
+ libgnunetutil.la \
+ $(LIBGCRYPT_LIBS)
+
 test_crypto_ecc_dlog_SOURCES = \
  test_crypto_ecc_dlog.c
 test_crypto_ecc_dlog_LDADD = \