crypto/ec/curve448/eddsa.c

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