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