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