crypto/ec/curve448/eddsa.c

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