crypto/ec/curve448/eddsa.c

   1 /*
   2  * Copyright 2017-2018 The OpenSSL Project Authors. All Rights Reserved.
   3  * Copyright 2015-2016 Cryptography Research, Inc.
   4  *
   5  * Licensed under the OpenSSL license (the "License").  You may not use
   6  * this file except in compliance with the License.  You can obtain a copy
   7  * in the file LICENSE in the source distribution or at
   8  * https://www.openssl.org/source/license.html
   9  *
  10  * Originally written by Mike Hamburg
  11  */
  12 #include <string.h>
  13 #include <openssl/crypto.h>
  14 #include <openssl/evp.h>
  15 #include "curve448_lcl.h"
  16 #include "word.h"
  17 #include "ed448.h"
  18 #include "internal/numbers.h"
  19
  20 #define COFACTOR 4
  21
  22 static c448_error_t oneshot_hash(uint8_t *out, size_t outlen,
  23                                  const uint8_t *in, size_t inlen)
  24 {
  25     EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
  26
  27     if (hashctx == NULL)
  28         return C448_FAILURE;
  29
  30     if (!EVP_DigestInit_ex(hashctx, EVP_shake256(), NULL)
  31             || !EVP_DigestUpdate(hashctx, in, inlen)
  32             || !EVP_DigestFinalXOF(hashctx, out, outlen)) {
  33         EVP_MD_CTX_free(hashctx);
  34         return C448_FAILURE;
  35     }
  36
  37     EVP_MD_CTX_free(hashctx);
  38     return C448_SUCCESS;
  39 }
  40
  41 static void clamp(uint8_t secret_scalar_ser[EDDSA_448_PRIVATE_BYTES])
  42 {
  43     secret_scalar_ser[0] &= -COFACTOR;
  44     secret_scalar_ser[EDDSA_448_PRIVATE_BYTES - 1] = 0;
  45     secret_scalar_ser[EDDSA_448_PRIVATE_BYTES - 2] |= 0x80;
  46 }
  47
  48 static c448_error_t hash_init_with_dom(EVP_MD_CTX *hashctx, uint8_t prehashed,
  49                                        uint8_t for_prehash,
  50                                        const uint8_t *context,
  51                                        size_t context_len)
  52 {
  53     const char *dom_s = "SigEd448";
  54     uint8_t dom[2];
  55
  56     if (context_len > UINT8_MAX)
  57         return C448_FAILURE;
  58
  59     dom[0] = (uint8_t)(2 - (prehashed == 0 ? 1 : 0)
  60                        - (for_prehash == 0 ? 1 : 0));
  61     dom[1] = (uint8_t)context_len;
  62
  63     if (!EVP_DigestInit_ex(hashctx, EVP_shake256(), NULL)
  64             || !EVP_DigestUpdate(hashctx, dom_s, strlen(dom_s))
  65             || !EVP_DigestUpdate(hashctx, dom, sizeof(dom))
  66             || (context_len > 0
  67                 && !EVP_DigestUpdate(hashctx, context, context_len)))
  68         return C448_FAILURE;
  69
  70     return C448_SUCCESS;
  71 }
  72
  73 /* In this file because it uses the hash */
  74 c448_error_t c448_ed448_convert_private_key_to_x448(
  75                             uint8_t x[X448_PRIVATE_BYTES],
  76                             const uint8_t ed [EDDSA_448_PRIVATE_BYTES])
  77 {
  78     /* pass the private key through oneshot_hash function */
  79     /* and keep the first X448_PRIVATE_BYTES bytes */
  80     return oneshot_hash(x, X448_PRIVATE_BYTES, ed,
  81                         EDDSA_448_PRIVATE_BYTES);
  82 }
  83
  84 c448_error_t c448_ed448_derive_public_key(
  85                         uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
  86                         const uint8_t privkey[EDDSA_448_PRIVATE_BYTES])
  87 {
  88     /* only this much used for keygen */
  89     uint8_t secret_scalar_ser[EDDSA_448_PRIVATE_BYTES];
  90     curve448_scalar_t secret_scalar;
  91     unsigned int c;
  92     curve448_point_t p;
  93
  94     if (!oneshot_hash(secret_scalar_ser, sizeof(secret_scalar_ser), privkey,
  95                       EDDSA_448_PRIVATE_BYTES))
  96         return C448_FAILURE;
  97
  98     clamp(secret_scalar_ser);
  99
 100     curve448_scalar_decode_long(secret_scalar, secret_scalar_ser,
 101                                 sizeof(secret_scalar_ser));
 102
 103     /*
 104      * Since we are going to mul_by_cofactor during encoding, divide by it
 105      * here. However, the EdDSA base point is not the same as the decaf base
 106      * point if the sigma isogeny is in use: the EdDSA base point is on
 107      * Etwist_d/(1-d) and the decaf base point is on Etwist_d, and when
 108      * converted it effectively picks up a factor of 2 from the isogenies.  So
 109      * we might start at 2 instead of 1.
 110      */
 111     for (c = 1; c < C448_EDDSA_ENCODE_RATIO; c <<= 1)
 112         curve448_scalar_halve(secret_scalar, secret_scalar);
 113
 114     curve448_precomputed_scalarmul(p, curve448_precomputed_base, secret_scalar);
 115
 116     curve448_point_mul_by_ratio_and_encode_like_eddsa(pubkey, p);
 117
 118     /* Cleanup */
 119     curve448_scalar_destroy(secret_scalar);
 120     curve448_point_destroy(p);
 121     OPENSSL_cleanse(secret_scalar_ser, sizeof(secret_scalar_ser));
 122
 123     return C448_SUCCESS;
 124 }
 125
 126 c448_error_t c448_ed448_sign(
 127                         uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
 128                         const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],
 129                         const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
 130                         const uint8_t *message, size_t message_len,
 131                         uint8_t prehashed, const uint8_t *context,
 132                         size_t context_len)
 133 {
 134     curve448_scalar_t secret_scalar;
 135     EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
 136     c448_error_t ret = C448_FAILURE;
 137     curve448_scalar_t nonce_scalar;
 138     uint8_t nonce_point[EDDSA_448_PUBLIC_BYTES] = { 0 };
 139     unsigned int c;
 140     curve448_scalar_t challenge_scalar;
 141
 142     if (hashctx == NULL)
 143         return C448_FAILURE;
 144
 145     {
 146         /*
 147          * Schedule the secret key, First EDDSA_448_PRIVATE_BYTES is serialised
 148          * secret scalar,next EDDSA_448_PRIVATE_BYTES bytes is the seed.
 149          */
 150         uint8_t expanded[EDDSA_448_PRIVATE_BYTES * 2];
 151
 152         if (!oneshot_hash(expanded, sizeof(expanded), privkey,
 153                           EDDSA_448_PRIVATE_BYTES))
 154             goto err;
 155         clamp(expanded);
 156         curve448_scalar_decode_long(secret_scalar, expanded,
 157                                     EDDSA_448_PRIVATE_BYTES);
 158
 159         /* Hash to create the nonce */
 160         if (!hash_init_with_dom(hashctx, prehashed, 0, context, context_len)
 161                 || !EVP_DigestUpdate(hashctx,
 162                                      expanded + EDDSA_448_PRIVATE_BYTES,
 163                                      EDDSA_448_PRIVATE_BYTES)
 164                 || (message_len > 0
 165                     && !EVP_DigestUpdate(hashctx, message, message_len))) {
 166             OPENSSL_cleanse(expanded, sizeof(expanded));
 167             goto err;
 168         }
 169         OPENSSL_cleanse(expanded, sizeof(expanded));
 170     }
 171
 172     /* Decode the nonce */
 173     {
 174         uint8_t nonce[2 * EDDSA_448_PRIVATE_BYTES];
 175
 176         if (!EVP_DigestFinalXOF(hashctx, nonce, sizeof(nonce)))
 177             goto err;
 178         curve448_scalar_decode_long(nonce_scalar, nonce, sizeof(nonce));
 179         OPENSSL_cleanse(nonce, sizeof(nonce));
 180     }
 181
 182     {
 183         /* Scalarmul to create the nonce-point */
 184         curve448_scalar_t nonce_scalar_2;
 185         curve448_point_t p;
 186
 187         curve448_scalar_halve(nonce_scalar_2, nonce_scalar);
 188         for (c = 2; c < C448_EDDSA_ENCODE_RATIO; c <<= 1)
 189             curve448_scalar_halve(nonce_scalar_2, nonce_scalar_2);
 190
 191         curve448_precomputed_scalarmul(p, curve448_precomputed_base,
 192                                        nonce_scalar_2);
 193         curve448_point_mul_by_ratio_and_encode_like_eddsa(nonce_point, p);
 194         curve448_point_destroy(p);
 195         curve448_scalar_destroy(nonce_scalar_2);
 196     }
 197
 198     {
 199         uint8_t challenge[2 * EDDSA_448_PRIVATE_BYTES];
 200
 201         /* Compute the challenge */
 202         if (!hash_init_with_dom(hashctx, prehashed, 0, context, context_len)
 203                 || !EVP_DigestUpdate(hashctx, nonce_point, sizeof(nonce_point))
 204                 || !EVP_DigestUpdate(hashctx, pubkey, EDDSA_448_PUBLIC_BYTES)
 205                 || (message_len > 0
 206                     && !EVP_DigestUpdate(hashctx, message, message_len))
 207                 || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge)))
 208             goto err;
 209
 210         curve448_scalar_decode_long(challenge_scalar, challenge,
 211                                     sizeof(challenge));
 212         OPENSSL_cleanse(challenge, sizeof(challenge));
 213     }
 214
 215     curve448_scalar_mul(challenge_scalar, challenge_scalar, secret_scalar);
 216     curve448_scalar_add(challenge_scalar, challenge_scalar, nonce_scalar);
 217
 218     OPENSSL_cleanse(signature, EDDSA_448_SIGNATURE_BYTES);
 219     memcpy(signature, nonce_point, sizeof(nonce_point));
 220     curve448_scalar_encode(&signature[EDDSA_448_PUBLIC_BYTES],
 221                            challenge_scalar);
 222
 223     curve448_scalar_destroy(secret_scalar);
 224     curve448_scalar_destroy(nonce_scalar);
 225     curve448_scalar_destroy(challenge_scalar);
 226
 227     ret = C448_SUCCESS;
 228  err:
 229     EVP_MD_CTX_free(hashctx);
 230     return ret;
 231 }
 232
 233 c448_error_t c448_ed448_sign_prehash(
 234                         uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
 235                         const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],
 236                         const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
 237                         const uint8_t hash[64], const uint8_t *context,
 238                         size_t context_len)
 239 {
 240     return c448_ed448_sign(signature, privkey, pubkey, hash, 64, 1, context,
 241                            context_len);
 242 }
 243
 244 c448_error_t c448_ed448_verify(
 245                     const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
 246                     const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
 247                     const uint8_t *message, size_t message_len,
 248                     uint8_t prehashed, const uint8_t *context,
 249                     uint8_t context_len)
 250 {
 251     curve448_point_t pk_point, r_point;
 252     c448_error_t error =
 253         curve448_point_decode_like_eddsa_and_mul_by_ratio(pk_point, pubkey);
 254     curve448_scalar_t challenge_scalar;
 255     curve448_scalar_t response_scalar;
 256
 257     if (C448_SUCCESS != error)
 258         return error;
 259
 260     error =
 261         curve448_point_decode_like_eddsa_and_mul_by_ratio(r_point, signature);
 262     if (C448_SUCCESS != error)
 263         return error;
 264
 265     {
 266         /* Compute the challenge */
 267         EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
 268         uint8_t challenge[2 * EDDSA_448_PRIVATE_BYTES];
 269
 270         if (hashctx == NULL
 271                 || !hash_init_with_dom(hashctx, prehashed, 0, context,
 272                                        context_len)
 273                 || !EVP_DigestUpdate(hashctx, signature, EDDSA_448_PUBLIC_BYTES)
 274                 || !EVP_DigestUpdate(hashctx, pubkey, EDDSA_448_PUBLIC_BYTES)
 275                 || !EVP_DigestUpdate(hashctx, message, message_len)
 276                 || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge))) {
 277             EVP_MD_CTX_free(hashctx);
 278             return C448_FAILURE;
 279         }
 280
 281         EVP_MD_CTX_free(hashctx);
 282         curve448_scalar_decode_long(challenge_scalar, challenge,
 283                                     sizeof(challenge));
 284         OPENSSL_cleanse(challenge, sizeof(challenge));
 285     }
 286     curve448_scalar_sub(challenge_scalar, curve448_scalar_zero,
 287                         challenge_scalar);
 288
 289     curve448_scalar_decode_long(response_scalar,
 290                                 &signature[EDDSA_448_PUBLIC_BYTES],
 291                                 EDDSA_448_PRIVATE_BYTES);
 292
 293     /* pk_point = -c(x(P)) + (cx + k)G = kG */
 294     curve448_base_double_scalarmul_non_secret(pk_point,
 295                                               response_scalar,
 296                                               pk_point, challenge_scalar);
 297     return c448_succeed_if(curve448_point_eq(pk_point, r_point));
 298 }
 299
 300 c448_error_t c448_ed448_verify_prehash(
 301                     const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
 302                     const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
 303                     const uint8_t hash[64], const uint8_t *context,
 304                     uint8_t context_len)
 305 {
 306     return c448_ed448_verify(signature, pubkey, hash, 64, 1, context,
 307                              context_len);
 308 }
 309
 310 int ED448_sign(uint8_t *out_sig, const uint8_t *message, size_t message_len,
 311                const uint8_t public_key[57], const uint8_t private_key[57],
 312                const uint8_t *context, size_t context_len)
 313 {
 314     return c448_ed448_sign(out_sig, private_key, public_key, message,
 315                            message_len, 0, context, context_len)
 316         == C448_SUCCESS;
 317 }
 318
 319 int ED448_verify(const uint8_t *message, size_t message_len,
 320                  const uint8_t signature[114], const uint8_t public_key[57],
 321                  const uint8_t *context, size_t context_len)
 322 {
 323     return c448_ed448_verify(signature, public_key, message, message_len, 0,
 324                              context, (uint8_t)context_len) == C448_SUCCESS;
 325 }
 326
 327 int ED448ph_sign(uint8_t *out_sig, const uint8_t hash[64],
 328                  const uint8_t public_key[57], const uint8_t private_key[57],
 329                  const uint8_t *context, size_t context_len)
 330 {
 331     return c448_ed448_sign_prehash(out_sig, private_key, public_key, hash,
 332                                    context, context_len) == C448_SUCCESS;
 333
 334 }
 335
 336 int ED448ph_verify(const uint8_t hash[64], const uint8_t signature[114],
 337                    const uint8_t public_key[57], const uint8_t *context,
 338                    size_t context_len)
 339 {
 340     return c448_ed448_verify_prehash(signature, public_key, hash, context,
 341                                      (uint8_t)context_len) == C448_SUCCESS;
 342 }
 343
 344 int ED448_public_from_private(uint8_t out_public_key[57],
 345                               const uint8_t private_key[57])
 346 {
 347     return c448_ed448_derive_public_key(out_public_key, private_key)
 348         == C448_SUCCESS;
 349 }