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
}

5 files changed, 991 insertions, 2 deletions

diff --git a/src/include/gnunet_crypto_lib.h b/src/include/gnunet_crypto_lib.h
index 77abab45d..582a58861 100644
--- a/src/include/gnunet_crypto_lib.h
+++ b/src/include/gnunet_crypto_lib.h
@@ -287,6 +287,59 @@ struct GNUNET_CRYPTO_EddsaPrivateScalar
   unsigned char s[512 / 8];
 };
 
+/**
+ * Private ECC key material encoded for transmission.  To be used only for
+ * Edx25519 signatures.  An inital key corresponds to data from the key
+ * expansion and clamping in the EdDSA key generation.
+ */
+struct GNUNET_CRYPTO_Edx25519PrivateKey
+{
+  /**
+   * a is a value mod n, where n has at most 256 bits.  It is the first half of
+   * the seed-expansion of EdDSA and will be clamped.
+   */
+  unsigned char a[256 / 8];
+
+  /**
+   * b consists of 32 bytes which where originally the lower 32bytes of the key
+   * expansion.  Subsequent calls to derive_private will change this value, too.
+   */
+  unsigned char b[256 / 8];
+};
+
+
+/**
+ * Public ECC key (always for curve Ed25519) encoded in a format suitable for
+ * network transmission and Edx25519 (same as EdDSA) signatures.  Refer to
+ * section 5.1.3 of rfc8032, for a thorough explanation of how this value maps
+ * to the x- and y-coordinates.
+ */
+struct GNUNET_CRYPTO_Edx25519PublicKey
+{
+  /**
+   * Point Q consists of a y-value mod p (256 bits); the x-value is
+   * always positive. The point is stored in Ed25519 standard
+   * compact format.
+   */
+  unsigned char q_y[256 / 8];
+};
+
+/**
+ * @brief an ECC signature using Edx25519 (same as in EdDSA).
+ */
+struct GNUNET_CRYPTO_Edx25519Signature
+{
+  /**
+   * R value.
+   */
+  unsigned char r[256 / 8];
+
+  /**
+   * S value.
+   */
+  unsigned char s[256 / 8];
+};
+
 
 /**
  * @brief type for session keys
@@ -1279,6 +1332,17 @@ GNUNET_CRYPTO_eddsa_key_get_public (
   const struct GNUNET_CRYPTO_EddsaPrivateKey *priv,
   struct GNUNET_CRYPTO_EddsaPublicKey *pub);
 
+/**
+ * @ingroup crypto
+ * Extract the public key for the given private key.
+ *
+ * @param priv the private key
+ * @param pub where to write the public key
+ */
+void
+GNUNET_CRYPTO_edx25519_key_get_public (
+  const struct GNUNET_CRYPTO_Edx25519PrivateKey *priv,
+  struct GNUNET_CRYPTO_Edx25519PublicKey *pub);
 
 /**
  * @ingroup crypto
@@ -1465,6 +1529,30 @@ GNUNET_CRYPTO_eddsa_key_create (struct GNUNET_CRYPTO_EddsaPrivateKey *pk);
 
 /**
  * @ingroup crypto
+ * Create a new private key.
+ *
+ * @param[out] pk private key to initialize
+ */
+void
+GNUNET_CRYPTO_edx25519_key_create (struct GNUNET_CRYPTO_Edx25519PrivateKey *pk);
+
+/**
+ * @ingroup crypto
+ * Create a new private key for Edx25519 from a given seed.  After expanding
+ * the seed, the first half of the key will be clamped according to EdDSA.
+ *
+ * @param seed seed input
+ * @param seedsize size of the seed in bytes
+ * @param[out] pk private key to initialize
+ */
+void
+GNUNET_CRYPTO_edx25519_key_create_from_seed (
+  const void *seed,
+  size_t seedsize,
+  struct GNUNET_CRYPTO_Edx25519PrivateKey *pk);
+
+/**
+ * @ingroup crypto
  * Create a new private key.  Clear with #GNUNET_CRYPTO_ecdhe_key_clear().
  *
  * @param[out] pk set to fresh private key;
@@ -1492,6 +1580,14 @@ GNUNET_CRYPTO_eddsa_key_clear (struct GNUNET_CRYPTO_EddsaPrivateKey *pk);
 void
 GNUNET_CRYPTO_ecdsa_key_clear (struct GNUNET_CRYPTO_EcdsaPrivateKey *pk);
 
+/**
+ * @ingroup crypto
+ * Clear memory that was used to store a private key.
+ *
+ * @param pk location of the key
+ */
+void
+GNUNET_CRYPTO_edx25519_key_clear (struct GNUNET_CRYPTO_Edx25519PrivateKey *pk);
 
 /**
  * @ingroup crypto
@@ -1874,6 +1970,53 @@ GNUNET_CRYPTO_ecdsa_sign_ (
                                               sig));               \
 } while (0)
 
+/**
+ * @ingroup crypto
+ * @brief Edx25519 sign a given block.
+ *
+ * The @a purpose data is the beginning of the data of which the signature is
+ * to be created. The `size` field in @a purpose must correctly indicate the
+ * number of bytes of the data structure, including its header.  If possible,
+ * use #GNUNET_CRYPTO_edx25519_sign() instead of this function (only if @a
+ * validate is not fixed-size, you must use this function directly).
+ *
+ * @param priv private key to use for the signing
+ * @param purpose what to sign (size, purpose)
+ * @param[out] sig where to write the signature
+ * @return #GNUNET_SYSERR on error, #GNUNET_OK on success
+ */
+enum GNUNET_GenericReturnValue
+GNUNET_CRYPTO_edx25519_sign_ (
+  const struct GNUNET_CRYPTO_Edx25519PrivateKey *priv,
+  const struct GNUNET_CRYPTO_EccSignaturePurpose *purpose,
+  struct GNUNET_CRYPTO_Edx25519Signature *sig);
+
+
+/**
+ * @ingroup crypto
+ * @brief Edx25519 sign a given block.  The resulting signature is compatible
+ * with EdDSA.
+ *
+ * The @a ps data must be a fixed-size struct for which the signature is to be
+ * created. The `size` field in @a ps->purpose must correctly indicate the
+ * number of bytes of the data structure, including its header.
+ *
+ * @param priv private key to use for the signing
+ * @param ps packed struct with what to sign, MUST begin with a purpose
+ * @param[out] sig where to write the signature
+ */
+#define GNUNET_CRYPTO_edx25519_sign(priv,ps,sig) do {              \
+    /* check size is set correctly */                              \
+    GNUNET_assert (ntohl ((ps)->purpose.size) == sizeof (*(ps)));  \
+    /* check 'ps' begins with the purpose */                       \
+    GNUNET_static_assert (((void*) (ps)) ==                        \
+                          ((void*) &(ps)->purpose));               \
+    GNUNET_assert (GNUNET_OK ==                                    \
+                   GNUNET_CRYPTO_edx25519_sign_ (priv,             \
+                                                 &(ps)->purpose,   \
+                                                 sig));            \
+} while (0)
+
 
 /**
  * @ingroup crypto
@@ -1917,7 +2060,7 @@ GNUNET_CRYPTO_eddsa_verify_ (
  */
 #define GNUNET_CRYPTO_eddsa_verify(purp,ps,sig,pub) ({             \
     /* check size is set correctly */                              \
-    GNUNET_assert (ntohl ((ps)->purpose.size) == sizeof (*(ps))); \
+    GNUNET_assert (ntohl ((ps)->purpose.size) == sizeof (*(ps)));  \
     /* check 'ps' begins with the purpose */                       \
     GNUNET_static_assert (((void*) (ps)) ==                        \
                           ((void*) &(ps)->purpose));               \
@@ -1927,7 +2070,6 @@ GNUNET_CRYPTO_eddsa_verify_ (
                                  pub);                             \
   })
 
-
 /**
  * @ingroup crypto
  * @brief Verify ECDSA signature.
@@ -1982,6 +2124,58 @@ GNUNET_CRYPTO_ecdsa_verify_ (
 
 /**
  * @ingroup crypto
+ * @brief Verify Edx25519 signature.
+ *
+ * The @a validate data is the beginning of the data of which the signature
+ * is to be verified. The `size` field in @a validate must correctly indicate
+ * the number of bytes of the data structure, including its header.  If @a
+ * purpose does not match the purpose given in @a validate (the latter must be
+ * in big endian), signature verification fails.  If possible, use
+ * #GNUNET_CRYPTO_edx25519_verify() instead of this function (only if @a
+ * validate is not fixed-size, you must use this function directly).
+ *
+ * @param purpose what is the purpose that the signature should have?
+ * @param validate block to validate (size, purpose, data)
+ * @param sig signature that is being validated
+ * @param pub public key of the signer
+ * @returns #GNUNET_OK if ok, #GNUNET_SYSERR if invalid
+ */
+enum GNUNET_GenericReturnValue
+GNUNET_CRYPTO_edx25519_verify_ (
+  uint32_t purpose,
+  const struct GNUNET_CRYPTO_EccSignaturePurpose *validate,
+  const struct GNUNET_CRYPTO_Edx25519Signature *sig,
+  const struct GNUNET_CRYPTO_Edx25519PublicKey *pub);
+
+
+/**
+ * @ingroup crypto
+ * @brief Verify Edx25519 signature.
+ *
+ * The @a ps data must be a fixed-size struct for which the signature is to be
+ * created. The `size` field in @a ps->purpose must correctly indicate the
+ * number of bytes of the data structure, including its header.
+ *
+ * @param purp purpose of the signature, must match 'ps->purpose.purpose'
+ *              (except in host byte order)
+ * @param priv private key to use for the signing
+ * @param ps packed struct with what to sign, MUST begin with a purpose
+ * @param sig where to write the signature
+ */
+#define GNUNET_CRYPTO_edx25519_verify(purp,ps,sig,pub) ({         \
+    /* check size is set correctly */                             \
+    GNUNET_assert (ntohl ((ps)->purpose.size) == sizeof (*(ps))); \
+    /* check 'ps' begins with the purpose */                      \
+    GNUNET_static_assert (((void*) (ps)) ==                       \
+                          ((void*) &(ps)->purpose));              \
+    GNUNET_CRYPTO_edx25519_verify_ (purp,                         \
+                                    &(ps)->purpose,               \
+                                    sig,                          \
+                                    pub);                         \
+  })
+
+/**
+ * @ingroup crypto
  * Derive a private key from a given private key and a label.
  * Essentially calculates a private key 'h = H(l,P) * d mod n'
  * where n is the size of the ECC group and P is the public
@@ -2115,6 +2309,43 @@ GNUNET_CRYPTO_eddsa_key_get_public_from_scalar (
   const struct GNUNET_CRYPTO_EddsaPrivateScalar *s,
   struct GNUNET_CRYPTO_EddsaPublicKey *pkey);
 
+/**
+ * @ingroup crypto
+ * Derive a private scalar from a given private key and a label.
+ * Essentially calculates a private key 'h = H(l,P) * d mod n'
+ * where n is the size of the ECC group and P is the public
+ * key associated with the private key 'd'.
+ *
+ * @param priv original private key
+ * @param seed input seed
+ * @param seedsize size of the seed
+ * @param result derived private key
+ */
+void
+GNUNET_CRYPTO_edx25519_private_key_derive (
+  const struct GNUNET_CRYPTO_Edx25519PrivateKey *priv,
+  const void *seed,
+  size_t seedsize,
+  struct GNUNET_CRYPTO_Edx25519PrivateKey *result);
+
+
+/**
+ * @ingroup crypto
+ * Derive a public key from a given public key and a label.
+ * Essentially calculates a public key 'V = H(l,P) * P'.
+ *
+ * @param pub original public key
+ * @param seed input seed
+ * @param seedsize size of the seed
+ * @param result where to write the derived public key
+ */
+void
+GNUNET_CRYPTO_edx25519_public_key_derive (
+  const struct GNUNET_CRYPTO_Edx25519PublicKey *pub,
+  const void *seed,
+  size_t seedsize,
+  struct GNUNET_CRYPTO_Edx25519PublicKey *result);
+
 
 /**
  * Output the given MPI value to the given buffer in network
diff --git a/src/util/.gitignore b/src/util/.gitignore
index 51eab71db..0e3449fed 100644
--- a/src/util/.gitignore
+++ b/src/util/.gitignore
@@ -36,6 +36,7 @@ test_crypto_ecdh_eddsa
 test_crypto_ecdhe
 test_crypto_ecdsa
 test_crypto_eddsa
+test_crypto_edx25519
 test_crypto_hash
 test_crypto_hash_context
 test_crypto_hkdf
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 = \
diff --git a/src/util/crypto_edx25519.c b/src/util/crypto_edx25519.c
new file mode 100644
index 000000000..bb5c6d177
--- /dev/null
+++ b/src/util/crypto_edx25519.c
@@ -0,0 +1,423 @@
+/*
+     This file is part of GNUnet.
+     Copyright (C) 2022 GNUnet e.V.
+
+     GNUnet is free software: you can redistribute it and/or modify it
+     under the terms of the GNU Affero General Public License as published
+     by the Free Software Foundation, either version 3 of the License,
+     or (at your option) any later version.
+
+     GNUnet is distributed in the hope that it will be useful, but
+     WITHOUT ANY WARRANTY; without even the implied warranty of
+     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+     Affero General Public License for more details.
+
+     You should have received a copy of the GNU Affero General Public License
+     along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+     SPDX-License-Identifier: AGPL3.0-or-later
+ */
+
+/**
+ * @file util/crypto_edx25519.c
+ * @brief An variant of EdDSA which allows for iterative derivation of key pairs.
+ * @author Özgür Kesim
+ * @author Christian Grothoff
+ * @author Florian Dold
+ * @author Martin Schanzenbach
+ */
+#include "platform.h"
+#include <gcrypt.h>
+#include <sodium.h>
+#include "gnunet_crypto_lib.h"
+#include "gnunet_strings_lib.h"
+
+#define CURVE "Ed25519"
+
+void
+GNUNET_CRYPTO_edx25519_key_clear (struct GNUNET_CRYPTO_Edx25519PrivateKey *pk)
+{
+  memset (pk, 0, sizeof(struct GNUNET_CRYPTO_Edx25519PrivateKey));
+}
+
+
+void
+GNUNET_CRYPTO_edx25519_key_create_from_seed (
+  const void *seed,
+  size_t seedsize,
+  struct GNUNET_CRYPTO_Edx25519PrivateKey *pk)
+{
+
+  GNUNET_static_assert (sizeof(*pk) == sizeof(struct GNUNET_HashCode));
+  GNUNET_CRYPTO_hash (seed,
+                      seedsize,
+                      (struct GNUNET_HashCode *) pk);
+
+  /* Clamp the first half of the key. The second half is used in the signature
+   * process. */
+  pk->a[0] &= 248;
+  pk->a[31] &= 127;
+  pk->a[31] |= 64;
+}
+
+
+void
+GNUNET_CRYPTO_edx25519_key_create (
+  struct GNUNET_CRYPTO_Edx25519PrivateKey *pk)
+{
+  char seed[256 / 8];
+  GNUNET_CRYPTO_random_block (GNUNET_CRYPTO_QUALITY_NONCE,
+                              seed,
+                              sizeof (seed));
+  GNUNET_CRYPTO_edx25519_key_create_from_seed (seed,
+                                               sizeof(seed),
+                                               pk);
+}
+
+
+void
+GNUNET_CRYPTO_edx25519_key_get_public (
+  const struct GNUNET_CRYPTO_Edx25519PrivateKey *priv,
+  struct GNUNET_CRYPTO_Edx25519PublicKey *pub)
+{
+  crypto_scalarmult_ed25519_base_noclamp (pub->q_y,
+                                          priv->a);
+}
+
+
+/**
+ * This function operates the basically same way as the signature function for
+ * EdDSA. But instead of expanding a private seed (which is usually the case
+ * for crypto APIs) and using the resulting scalars, it takes the scalars
+ * directly from Edx25519PrivateKey.  We require this functionality in order to
+ * use derived private keys for signatures.
+ *
+ * The resulting signature is a standard EdDSA signature
+ * which can be verified using the usual APIs.
+ *
+ * @param priv the private key (containing two scalars .a and .b)
+ * @param purp the signature purpose
+ * @param sig the resulting signature
+ */
+enum GNUNET_GenericReturnValue
+GNUNET_CRYPTO_edx25519_sign_ (
+  const struct GNUNET_CRYPTO_Edx25519PrivateKey *priv,
+  const struct GNUNET_CRYPTO_EccSignaturePurpose *purpose,
+  struct GNUNET_CRYPTO_Edx25519Signature *sig)
+{
+
+  crypto_hash_sha512_state hs;
+  unsigned char r[64];
+  unsigned char hram[64];
+  unsigned char P[32];
+  unsigned char R[32];
+  unsigned char tmp[32];
+
+  crypto_hash_sha512_init (&hs);
+
+  /**
+   * Calculate the public key P from the private scalar in the key.
+   */
+  crypto_scalarmult_ed25519_base_noclamp (P,
+                                          priv->a);
+
+  /**
+   * Calculate r:
+   * r = SHA512 (b ∥ M)
+   * where M is our message (purpose).
+   */
+  crypto_hash_sha512_update (&hs,
+                             priv->b,
+                             sizeof(priv->b));
+  crypto_hash_sha512_update (&hs,
+                             (uint8_t*) purpose,
+                             ntohl (purpose->size));
+  crypto_hash_sha512_final (&hs,
+                            r);
+
+  /**
+   * Temporarily put P into S
+   */
+  memcpy (sig->s, P, 32);
+
+  /**
+   * Reduce the scalar value r
+   */
+  unsigned char r_mod[64];
+  crypto_core_ed25519_scalar_reduce (r_mod, r);
+
+  /**
+   * Calculate R := r * G of the signature
+   */
+  crypto_scalarmult_ed25519_base_noclamp (R, r_mod);
+  memcpy (sig->r, R, sizeof (R));
+
+  /**
+   * Calculate
+   * hram := SHA512 (R ∥ P ∥ M)
+   */
+  crypto_hash_sha512_init (&hs);
+  crypto_hash_sha512_update (&hs, (uint8_t*) sig, 64);
+  crypto_hash_sha512_update (&hs, (uint8_t*) purpose,
+                             ntohl (purpose->size));
+  crypto_hash_sha512_final (&hs, hram);
+
+  /**
+   * Reduce the resulting scalar value
+   */
+  unsigned char hram_mod[64];
+  crypto_core_ed25519_scalar_reduce (hram_mod, hram);
+
+  /**
+   * Calculate
+   * S := r + hram * s mod L
+   */
+  crypto_core_ed25519_scalar_mul (tmp, hram_mod, priv->a);
+  crypto_core_ed25519_scalar_add (sig->s, tmp, r_mod);
+
+  sodium_memzero (r, sizeof (r));
+  sodium_memzero (r_mod, sizeof (r_mod));
+
+  return GNUNET_OK;
+}
+
+
+enum GNUNET_GenericReturnValue
+GNUNET_CRYPTO_edx25519_verify_ (
+  uint32_t purpose,
+  const struct GNUNET_CRYPTO_EccSignaturePurpose *validate,
+  const struct GNUNET_CRYPTO_Edx25519Signature *sig,
+  const struct GNUNET_CRYPTO_Edx25519PublicKey *pub)
+{
+  const unsigned char *m = (const void *) validate;
+  size_t mlen = ntohl (validate->size);
+  const unsigned char *s = (const void *) sig;
+
+  int res;
+
+  if (purpose != ntohl (validate->purpose))
+    return GNUNET_SYSERR; /* purpose mismatch */
+
+  res = crypto_sign_verify_detached (s, m, mlen, pub->q_y);
+  return (res == 0) ? GNUNET_OK : GNUNET_SYSERR;
+}
+
+
+/**
+ * Derive the 'h' value for key derivation, where
+ * 'h = H(P ∥ seed) mod n' and 'n' is the size of the cyclic subroup.
+ *
+ * @param pub public key for deriviation
+ * @param seed seed for key the deriviation
+ * @param seedsize the size of the seed
+ * @param n The value for the modulus 'n'
+ * @param[out] phc if not NULL, the output of H() will be written into
+ * return h_mod_n (allocated by this function)
+ */
+static gcry_mpi_t
+derive_h_mod_n (
+  const struct GNUNET_CRYPTO_Edx25519PublicKey *pub,
+  const void *seed,
+  size_t seedsize,
+  const gcry_mpi_t n,
+  struct GNUNET_HashCode *phc)
+{
+  static const char *const salt = "edx2559-derivation";
+  struct GNUNET_HashCode hc;
+  gcry_mpi_t h;
+  gcry_mpi_t h_mod_n;
+
+  if (NULL == phc)
+    phc = &hc;
+
+  GNUNET_CRYPTO_kdf (phc, sizeof(*phc),
+                     salt, strlen (salt),
+                     pub, sizeof(*pub),
+                     seed, seedsize,
+                     NULL, 0);
+
+  /* calculate h_mod_n = h % n */
+  GNUNET_CRYPTO_mpi_scan_unsigned (&h,
+                                   (unsigned char *) phc,
+                                   sizeof(*phc));
+  h_mod_n = gcry_mpi_new (256);
+  gcry_mpi_mod (h_mod_n, h, n);
+
+#ifdef CHECK_RARE_CASES
+  /**
+   * Note that the following cases would be problematic:
+   *    1.) h == 0 mod n
+   *    2.) h == 1 mod n
+   *    3.) [h] * P == E
+   * We assume that the probalities for these cases to occur are neglegible.
+   */
+  GNUNET_assert (! gcry_mpi_cmp_ui (h_mod_n, 0));
+  GNUNET_assert (! gcry_mpi_cmp_ui (h_mod_n, 1));
+#endif
+
+  return h_mod_n;
+}
+
+
+void
+GNUNET_CRYPTO_edx25519_private_key_derive (
+  const struct GNUNET_CRYPTO_Edx25519PrivateKey *priv,
+  const void *seed,
+  size_t seedsize,
+  struct GNUNET_CRYPTO_Edx25519PrivateKey *result)
+{
+  struct GNUNET_CRYPTO_Edx25519PublicKey pub;
+  struct GNUNET_HashCode hc;
+  uint8_t a[32];
+  unsigned char sk[64];
+  gcry_ctx_t ctx;
+  gcry_mpi_t h;
+  gcry_mpi_t h_mod_n;
+  gcry_mpi_t x;
+  gcry_mpi_t n;
+  gcry_mpi_t a1;
+  gcry_mpi_t a2;
+  gcry_mpi_t ap; // a'
+
+  GNUNET_CRYPTO_edx25519_key_get_public (priv, &pub);
+
+  /**
+   * Libsodium does not offer an API with arbitrary arithmetic.
+   * Hence we have to use libgcrypt here.
+   */
+  GNUNET_assert (0 == gcry_mpi_ec_new (&ctx, NULL, "Ed25519"));
+
+  /**
+   * Get our modulo
+   */
+  n = gcry_mpi_ec_get_mpi ("n", ctx, 1);
+  GNUNET_assert (NULL != n);
+
+  /**
+   * Get h mod n
+   */
+  h_mod_n = derive_h_mod_n (&pub,
+                            seed,
+                            seedsize,
+                            n,
+                            &hc);
+
+  /* Convert priv->a scalar to big endian for libgcrypt */
+  for (size_t i = 0; i < 32; i++)
+    a[i] = priv->a[31 - i];
+
+  /**
+   * dc now contains the private scalar "a".
+   * We carefully remove the clamping and derive a'.
+   * Calculate:
+   * a1 := a / 8
+   * a2 := h * a1 mod n
+   * a' := a2 * 8 mod n
+   */
+  GNUNET_CRYPTO_mpi_scan_unsigned (&x, a, sizeof(a)); // a
+  a1 = gcry_mpi_new (256);
+  gcry_mpi_t eight = gcry_mpi_set_ui (NULL, 8);
+  gcry_mpi_div (a1, NULL, x, eight, 0); // a1 := a / 8
+  a2 = gcry_mpi_new (256);
+  gcry_mpi_mulm (a2, h_mod_n, a1, n); // a2 := h * a1 mod n
+  ap = gcry_mpi_new (256);
+  gcry_mpi_mul (ap, a2, eight); // a' := a2 * 8
+
+#ifdef CHECK_RARE_CASES
+  /* The likelihood for a' == 0 or a' == 1 is neglegible */
+  GNUNET_assert (! gcry_mpi_cmp_ui (ap, 0));
+  GNUNET_assert (! gcry_mpi_cmp_ui (ap, 1));
+#endif
+
+  gcry_mpi_release (h_mod_n);
+  gcry_mpi_release (h);
+  gcry_mpi_release (x);
+  gcry_mpi_release (n);
+  gcry_mpi_release (a1);
+  gcry_mpi_release (a2);
+  gcry_ctx_release (ctx);
+  GNUNET_CRYPTO_mpi_print_unsigned (a, sizeof(a), ap);
+  gcry_mpi_release (ap);
+
+  /**
+   * We hash the derived "h" parameter with the other half of the expanded
+   * private key (that is: priv->b). This ensures that for signature
+   * generation, the "R" is derived from the same derivation path as "h" and is
+   * not reused.
+   */
+  {
+    crypto_hash_sha256_state hs;
+    crypto_hash_sha256_init (&hs);
+    crypto_hash_sha256_update (&hs, priv->b, sizeof(priv->b));
+    crypto_hash_sha256_update (&hs, (unsigned char*) &hc, sizeof (hc));
+    crypto_hash_sha256_final (&hs, result->b);
+  }
+
+  /* Convert to little endian for libsodium */
+  for (size_t i = 0; i < 32; i++)
+    result->a[i] = a[31 - i];
+
+  sodium_memzero (a, sizeof(a));
+}
+
+
+void
+GNUNET_CRYPTO_edx25519_public_key_derive (
+  const struct GNUNET_CRYPTO_Edx25519PublicKey *pub,
+  const void *seed,
+  size_t seedsize,
+  struct GNUNET_CRYPTO_Edx25519PublicKey *result)
+{
+  struct GNUNET_HashCode hc;
+  gcry_ctx_t ctx;
+  gcry_mpi_t q_y;
+  gcry_mpi_t h;
+  gcry_mpi_t n;
+  gcry_mpi_t h_mod_n;
+  gcry_mpi_point_t q;
+  gcry_mpi_point_t v;
+
+  GNUNET_assert (0 == gcry_mpi_ec_new (&ctx, NULL, "Ed25519"));
+
+  /* obtain point 'q' from original public key.  The provided 'q' is
+     compressed thus we first store it in the context and then get it
+     back as a (decompresssed) point.  */
+  q_y = gcry_mpi_set_opaque_copy (NULL,
+                                  pub->q_y,
+                                  8 * sizeof(pub->q_y));
+  GNUNET_assert (NULL != q_y);
+  GNUNET_assert (0 == gcry_mpi_ec_set_mpi ("q", q_y, ctx));
+  gcry_mpi_release (q_y);
+  q = gcry_mpi_ec_get_point ("q", ctx, 0);
+  GNUNET_assert (q);
+
+  /**
+   * Get h mod n
+   */
+  n = gcry_mpi_ec_get_mpi ("n", ctx, 1);
+  GNUNET_assert (NULL != n);
+  GNUNET_assert (NULL != pub);
+  h_mod_n = derive_h_mod_n (pub,
+                            seed,
+                            seedsize,
+                            n,
+                            NULL /* We don't need hc here */);
+
+  /* calculate v = h_mod_n * q */
+  v = gcry_mpi_point_new (0);
+  gcry_mpi_ec_mul (v, h_mod_n, q, ctx);
+  gcry_mpi_release (h_mod_n);
+  gcry_mpi_release (h);
+  gcry_mpi_release (n);
+  gcry_mpi_point_release (q);
+
+  /* convert point 'v' to public key that we return */
+  GNUNET_assert (0 == gcry_mpi_ec_set_point ("q", v, ctx));
+  gcry_mpi_point_release (v);
+  q_y = gcry_mpi_ec_get_mpi ("q@eddsa", ctx, 0);
+  GNUNET_assert (q_y);
+  GNUNET_CRYPTO_mpi_print_unsigned (result->q_y, sizeof(result->q_y), q_y);
+  gcry_mpi_release (q_y);
+  gcry_ctx_release (ctx);
+
+}
diff --git a/src/util/test_crypto_edx25519.c b/src/util/test_crypto_edx25519.c
new file mode 100644
index 000000000..ead6f0bb9
--- /dev/null
+++ b/src/util/test_crypto_edx25519.c
@@ -0,0 +1,326 @@
+/*
+     This file is part of GNUnet.
+     Copyright (C) 2022 GNUnet e.V.
+
+     GNUnet is free software: you can redistribute it and/or modify it
+     under the terms of the GNU Affero General Public License as published
+     by the Free Software Foundation, either version 3 of the License,
+     or (at your option) any later version.
+
+     GNUnet is distributed in the hope that it will be useful, but
+     WITHOUT ANY WARRANTY; without even the implied warranty of
+     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+     Affero General Public License for more details.
+
+     You should have received a copy of the GNU Affero General Public License
+     along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+     SPDX-License-Identifier: AGPL3.0-or-later
+
+ */
+/**
+ * @file util/test_crypto_edx25519.c
+ * @brief testcase for ECC public key crypto for edx25519
+ * @author Özgür Kesim
+ */
+#include "platform.h"
+#include "gnunet_util_lib.h"
+#include "gnunet_signatures.h"
+#include <gcrypt.h>
+
+#define ITER 25
+
+#define KEYFILE "/tmp/test-gnunet-crypto-edx25519.key"
+
+#define PERF GNUNET_YES
+
+
+static struct GNUNET_CRYPTO_Edx25519PrivateKey key;
+
+
+static int
+testSignVerify (void)
+{
+  struct GNUNET_CRYPTO_Edx25519Signature sig;
+  struct GNUNET_CRYPTO_EccSignaturePurpose purp;
+  struct GNUNET_CRYPTO_Edx25519PublicKey pkey;
+  struct GNUNET_TIME_Absolute start;
+  int ok = GNUNET_OK;
+
+  fprintf (stderr, "%s", "W");
+  GNUNET_CRYPTO_edx25519_key_get_public (&key,
+                                         &pkey);
+  start = GNUNET_TIME_absolute_get ();
+  purp.size = htonl (sizeof(struct GNUNET_CRYPTO_EccSignaturePurpose));
+  purp.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_TEST);
+
+  for (unsigned int i = 0; i < ITER; i++)
+  {
+    fprintf (stderr, "%s", "."); fflush (stderr);
+    if (GNUNET_SYSERR == GNUNET_CRYPTO_edx25519_sign_ (&key,
+                                                       &purp,
+                                                       &sig))
+    {
+      fprintf (stderr,
+               "GNUNET_CRYPTO_edx25519_sign returned SYSERR\n");
+      ok = GNUNET_SYSERR;
+      continue;
+    }
+    if (GNUNET_SYSERR ==
+        GNUNET_CRYPTO_edx25519_verify_ (GNUNET_SIGNATURE_PURPOSE_TEST,
+                                        &purp,
+                                        &sig,
+                                        &pkey))
+    {
+      fprintf (stderr,
+               "GNUNET_CRYPTO_edx25519_verify failed!\n");
+      ok = GNUNET_SYSERR;
+      continue;
+    }
+    if (GNUNET_SYSERR !=
+        GNUNET_CRYPTO_edx25519_verify_ (
+          GNUNET_SIGNATURE_PURPOSE_TRANSPORT_PONG_OWN,
+          &purp,
+          &sig,
+          &pkey))
+    {
+      fprintf (stderr,
+               "GNUNET_CRYPTO_edx25519_verify failed to fail!\n");
+      ok = GNUNET_SYSERR;
+      continue;
+    }
+  }
+  fprintf (stderr, "\n");
+  printf ("%d EdDSA sign/verify operations %s\n",
+          ITER,
+          GNUNET_STRINGS_relative_time_to_string (
+            GNUNET_TIME_absolute_get_duration (start),
+            GNUNET_YES));
+  return ok;
+}
+
+
+static int
+testDeriveSignVerify (void)
+{
+  struct GNUNET_CRYPTO_EccSignaturePurpose purp;
+  struct GNUNET_CRYPTO_Edx25519Signature sig;
+  struct GNUNET_CRYPTO_Edx25519PrivateKey dkey;
+  struct GNUNET_CRYPTO_Edx25519PublicKey pub;
+  struct GNUNET_CRYPTO_Edx25519PublicKey dpub;
+  struct GNUNET_CRYPTO_Edx25519PublicKey dpub2;
+
+  GNUNET_CRYPTO_edx25519_key_get_public (&key, &pub);
+  GNUNET_CRYPTO_edx25519_private_key_derive (&key,
+                                             "test-derive",
+                                             sizeof("test-derive"),
+                                             &dkey);
+  GNUNET_CRYPTO_edx25519_public_key_derive (&pub,
+                                            "test-derive",
+                                            sizeof("test-derive"),
+                                            &dpub);
+  GNUNET_CRYPTO_edx25519_key_get_public (&dkey, &dpub2);
+
+  if (0 != GNUNET_memcmp (&dpub.q_y, &dpub2.q_y))
+  {
+    fprintf (stderr, "key deriviation failed\n");
+    return GNUNET_SYSERR;
+  }
+
+  purp.size = htonl (sizeof(struct GNUNET_CRYPTO_EccSignaturePurpose));
+  purp.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_TEST);
+
+  GNUNET_CRYPTO_edx25519_sign_ (&dkey,
+                                &purp,
+                                &sig);
+
+  if (GNUNET_SYSERR ==
+      GNUNET_CRYPTO_edx25519_verify_ (GNUNET_SIGNATURE_PURPOSE_TEST,
+                                      &purp,
+                                      &sig,
+                                      &dpub))
+  {
+    fprintf (stderr,
+             "GNUNET_CRYPTO_edx25519_verify failed after derivation!\n");
+    return GNUNET_SYSERR;
+  }
+
+  if (GNUNET_SYSERR !=
+      GNUNET_CRYPTO_edx25519_verify_ (GNUNET_SIGNATURE_PURPOSE_TEST,
+                                      &purp,
+                                      &sig,
+                                      &pub))
+  {
+    fprintf (stderr,
+             "GNUNET_CRYPTO_edx25519_verify failed to fail after derivation!\n");
+    return GNUNET_SYSERR;
+  }
+
+  if (GNUNET_SYSERR !=
+      GNUNET_CRYPTO_edx25519_verify_ (
+        GNUNET_SIGNATURE_PURPOSE_TRANSPORT_PONG_OWN,
+        &purp,
+        &sig,
+        &dpub))
+  {
+    fprintf (stderr,
+             "GNUNET_CRYPTO_edx25519_verify failed to fail after derivation!\n");
+    return GNUNET_SYSERR;
+  }
+  return GNUNET_OK;
+}
+
+
+#if PERF
+static int
+testSignPerformance ()
+{
+  struct GNUNET_CRYPTO_EccSignaturePurpose purp;
+  struct GNUNET_CRYPTO_Edx25519Signature sig;
+  struct GNUNET_CRYPTO_Edx25519PublicKey pkey;
+  struct GNUNET_TIME_Absolute start;
+  int ok = GNUNET_OK;
+
+  purp.size = htonl (sizeof(struct GNUNET_CRYPTO_EccSignaturePurpose));
+  purp.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_TEST);
+  fprintf (stderr, "%s", "W");
+  GNUNET_CRYPTO_edx25519_key_get_public (&key,
+                                         &pkey);
+  start = GNUNET_TIME_absolute_get ();
+  for (unsigned int i = 0; i < ITER; i++)
+  {
+    fprintf (stderr, "%s", ".");
+    fflush (stderr);
+    if (GNUNET_SYSERR ==
+        GNUNET_CRYPTO_edx25519_sign_ (&key,
+                                      &purp,
+                                      &sig))
+    {
+      fprintf (stderr, "%s", "GNUNET_CRYPTO_edx25519_sign returned SYSERR\n");
+      ok = GNUNET_SYSERR;
+      continue;
+    }
+  }
+  fprintf (stderr, "\n");
+  printf ("%d EdDSA sign operations %s\n",
+          ITER,
+          GNUNET_STRINGS_relative_time_to_string (
+            GNUNET_TIME_absolute_get_duration (start),
+            GNUNET_YES));
+  return ok;
+}
+
+
+#endif
+
+
+#if 0 /* not implemented */
+static int
+testCreateFromFile (void)
+{
+  struct GNUNET_CRYPTO_Edx25519PublicKey p1;
+  struct GNUNET_CRYPTO_Edx25519PublicKey p2;
+
+  /* do_create == GNUNET_YES and non-existing file MUST return GNUNET_YES */
+  GNUNET_assert (0 == unlink (KEYFILE) || ENOENT == errno);
+  GNUNET_assert (GNUNET_YES ==
+                 GNUNET_CRYPTO_edx25519_key_from_file (KEYFILE,
+                                                       GNUNET_YES,
+                                                       &key));
+  GNUNET_CRYPTO_edx25519_key_get_public (&key,
+                                         &p1);
+
+  /* do_create == GNUNET_YES and _existing_ file MUST return GNUNET_NO */
+  GNUNET_assert (GNUNET_NO ==
+                 GNUNET_CRYPTO_edx25519_key_from_file (KEYFILE,
+                                                       GNUNET_YES,
+                                                       &key));
+  GNUNET_CRYPTO_edx25519_key_get_public (&key,
+                                         &p2);
+  GNUNET_assert (0 ==
+                 GNUNET_memcmp (&p1,
+                                &p2));
+
+  /* do_create == GNUNET_NO and non-existing file MUST return GNUNET_SYSERR */
+  GNUNET_assert (0 == unlink (KEYFILE));
+  GNUNET_assert (GNUNET_SYSERR ==
+                 GNUNET_CRYPTO_edx25519_key_from_file (KEYFILE,
+                                                       GNUNET_NO,
+                                                       &key));
+  return GNUNET_OK;
+}
+
+
+#endif
+
+
+static void
+perf_keygen (void)
+{
+  struct GNUNET_TIME_Absolute start;
+  struct GNUNET_CRYPTO_Edx25519PrivateKey pk;
+
+  fprintf (stderr, "%s", "W");
+  start = GNUNET_TIME_absolute_get ();
+  for (unsigned int i = 0; i < 10; i++)
+  {
+    fprintf (stderr, ".");
+    fflush (stderr);
+    GNUNET_CRYPTO_edx25519_key_create (&pk);
+  }
+  fprintf (stderr, "\n");
+  printf ("10 EdDSA keys created in %s\n",
+          GNUNET_STRINGS_relative_time_to_string (
+            GNUNET_TIME_absolute_get_duration (start), GNUNET_YES));
+}
+
+
+int
+main (int argc, char *argv[])
+{
+  int failure_count = 0;
+
+  if (! gcry_check_version ("1.6.0"))
+  {
+    fprintf (stderr,
+             "libgcrypt has not the expected version (version %s is required).\n",
+             "1.6.0");
+    return 0;
+  }
+  if (getenv ("GNUNET_GCRYPT_DEBUG"))
+    gcry_control (GCRYCTL_SET_DEBUG_FLAGS, 1u, 0);
+  GNUNET_log_setup ("test-crypto-edx25519",
+                    "WARNING",
+                    NULL);
+  GNUNET_CRYPTO_edx25519_key_create (&key);
+  if (GNUNET_OK != testDeriveSignVerify ())
+  {
+    failure_count++;
+    fprintf (stderr,
+             "\n\n%d TESTS FAILED!\n\n", failure_count);
+    return -1;
+  }
+#if PERF
+  if (GNUNET_OK != testSignPerformance ())
+    failure_count++;
+#endif
+  if (GNUNET_OK != testSignVerify ())
+    failure_count++;
+#if 0 /* not implemented */
+  if (GNUNET_OK != testCreateFromFile ())
+    failure_count++;
+#endif
+  perf_keygen ();
+
+  if (0 != failure_count)
+  {
+    fprintf (stderr,
+             "\n\n%d TESTS FAILED!\n\n",
+             failure_count);
+    return -1;
+  }
+  return 0;
+}
+
+
+/* end of test_crypto_edx25519.c */