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 "word.h"
  16 #include "ed448.h"
  17 #include "shake.h"
  18 #include <string.h>
  19
  20 #define API_NAME "decaf_448"
  21 #define API_NS(_id) decaf_448_##_id
  22
  23 #define hash_ctx_t   decaf_shake256_ctx_t
  24 #define hash_init    decaf_shake256_init
  25 #define hash_update  decaf_shake256_update
  26 #define hash_final   decaf_shake256_final
  27 #define hash_destroy decaf_shake256_destroy
  28 #define hash_hash    decaf_shake256_hash
  29
  30 #define NO_CONTEXT DECAF_EDDSA_448_SUPPORTS_CONTEXTLESS_SIGS
  31 #define EDDSA_USE_SIGMA_ISOGENY 0
  32 #define COFACTOR 4
  33 #define EDDSA_PREHASH_BYTES 64
  34
  35 #if NO_CONTEXT
  36 const uint8_t NO_CONTEXT_POINTS_HERE = 0;
  37 const uint8_t * const DECAF_ED448_NO_CONTEXT = &NO_CONTEXT_POINTS_HERE;
  38 #endif
  39
  40 /* EDDSA_BASE_POINT_RATIO = 1 or 2
  41  * Because EdDSA25519 is not on E_d but on the isogenous E_sigma_d,
  42  * its base point is twice ours.
  43  */
  44 #define EDDSA_BASE_POINT_RATIO (1+EDDSA_USE_SIGMA_ISOGENY) /* TODO: remove */
  45
  46 static void clamp (
  47     uint8_t secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES]
  48 ) {
  49     /* Blarg */
  50     secret_scalar_ser[0] &= -COFACTOR;
  51     uint8_t hibit = (1<<0)>>1;
  52     if (hibit == 0) {
  53         secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES - 1] = 0;
  54         secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES - 2] |= 0x80;
  55     } else {
  56         secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES - 1] &= hibit-1;
  57         secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES - 1] |= hibit;
  58     }
  59 }
  60
  61 static void hash_init_with_dom(
  62     hash_ctx_t hash,
  63     uint8_t prehashed,
  64     uint8_t for_prehash,
  65     const uint8_t *context,
  66     uint8_t context_len
  67 ) {
  68     hash_init(hash);
  69
  70 #if NO_CONTEXT
  71     if (context_len == 0 && context == DECAF_ED448_NO_CONTEXT) {
  72         (void)prehashed;
  73         (void)for_prehash;
  74         (void)context;
  75         (void)context_len;
  76         return;
  77     }
  78 #endif
  79     const char *dom_s = "SigEd448";
  80     const uint8_t dom[2] = {2+word_is_zero(prehashed)+word_is_zero(for_prehash), context_len};
  81     hash_update(hash,(const unsigned char *)dom_s, strlen(dom_s));
  82     hash_update(hash,dom,2);
  83     hash_update(hash,context,context_len);
  84 }
  85
  86 void decaf_ed448_prehash_init (
  87     hash_ctx_t hash
  88 ) {
  89     hash_init(hash);
  90 }
  91
  92 /* In this file because it uses the hash */
  93 void decaf_ed448_convert_private_key_to_x448 (
  94     uint8_t x[DECAF_X448_PRIVATE_BYTES],
  95     const uint8_t ed[DECAF_EDDSA_448_PRIVATE_BYTES]
  96 ) {
  97     /* pass the private key through hash_hash function */
  98     /* and keep the first DECAF_X448_PRIVATE_BYTES bytes */
  99     hash_hash(
 100         x,
 101         DECAF_X448_PRIVATE_BYTES,
 102         ed,
 103         DECAF_EDDSA_448_PRIVATE_BYTES
 104     );
 105 }
 106
 107 void decaf_ed448_derive_public_key (
 108     uint8_t pubkey[DECAF_EDDSA_448_PUBLIC_BYTES],
 109     const uint8_t privkey[DECAF_EDDSA_448_PRIVATE_BYTES]
 110 ) {
 111     /* only this much used for keygen */
 112     uint8_t secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES];
 113
 114     hash_hash(
 115         secret_scalar_ser,
 116         sizeof(secret_scalar_ser),
 117         privkey,
 118         DECAF_EDDSA_448_PRIVATE_BYTES
 119     );
 120     clamp(secret_scalar_ser);
 121
 122     API_NS(scalar_t) secret_scalar;
 123     API_NS(scalar_decode_long)(secret_scalar, secret_scalar_ser, sizeof(secret_scalar_ser));
 124
 125     /* Since we are going to mul_by_cofactor during encoding, divide by it here.
 126      * However, the EdDSA base point is not the same as the decaf base point if
 127      * the sigma isogeny is in use: the EdDSA base point is on Etwist_d/(1-d) and
 128      * the decaf base point is on Etwist_d, and when converted it effectively
 129      * picks up a factor of 2 from the isogenies.  So we might start at 2 instead of 1.
 130      */
 131     for (unsigned int c=1; c<DECAF_448_EDDSA_ENCODE_RATIO; c <<= 1) {
 132         API_NS(scalar_halve)(secret_scalar,secret_scalar);
 133     }
 134
 135     API_NS(point_t) p;
 136     API_NS(precomputed_scalarmul)(p,API_NS(precomputed_base),secret_scalar);
 137
 138     API_NS(point_mul_by_ratio_and_encode_like_eddsa)(pubkey, p);
 139
 140     /* Cleanup */
 141     API_NS(scalar_destroy)(secret_scalar);
 142     API_NS(point_destroy)(p);
 143     decaf_bzero(secret_scalar_ser, sizeof(secret_scalar_ser));
 144 }
 145
 146 void decaf_ed448_sign (
 147     uint8_t signature[DECAF_EDDSA_448_SIGNATURE_BYTES],
 148     const uint8_t privkey[DECAF_EDDSA_448_PRIVATE_BYTES],
 149     const uint8_t pubkey[DECAF_EDDSA_448_PUBLIC_BYTES],
 150     const uint8_t *message,
 151     size_t message_len,
 152     uint8_t prehashed,
 153     const uint8_t *context,
 154     uint8_t context_len
 155 ) {
 156     API_NS(scalar_t) secret_scalar;
 157     hash_ctx_t hash;
 158     {
 159         /* Schedule the secret key */
 160         struct {
 161             uint8_t secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES];
 162             uint8_t seed[DECAF_EDDSA_448_PRIVATE_BYTES];
 163         } __attribute__((packed)) expanded;
 164         hash_hash(
 165             (uint8_t *)&expanded,
 166             sizeof(expanded),
 167             privkey,
 168             DECAF_EDDSA_448_PRIVATE_BYTES
 169         );
 170         clamp(expanded.secret_scalar_ser);
 171         API_NS(scalar_decode_long)(secret_scalar, expanded.secret_scalar_ser, sizeof(expanded.secret_scalar_ser));
 172
 173         /* Hash to create the nonce */
 174         hash_init_with_dom(hash,prehashed,0,context,context_len);
 175         hash_update(hash,expanded.seed,sizeof(expanded.seed));
 176         hash_update(hash,message,message_len);
 177         decaf_bzero(&expanded, sizeof(expanded));
 178     }
 179
 180     /* Decode the nonce */
 181     API_NS(scalar_t) nonce_scalar;
 182     {
 183         uint8_t nonce[2*DECAF_EDDSA_448_PRIVATE_BYTES];
 184         hash_final(hash,nonce,sizeof(nonce));
 185         API_NS(scalar_decode_long)(nonce_scalar, nonce, sizeof(nonce));
 186         decaf_bzero(nonce, sizeof(nonce));
 187     }
 188
 189     uint8_t nonce_point[DECAF_EDDSA_448_PUBLIC_BYTES] = {0};
 190     {
 191         /* Scalarmul to create the nonce-point */
 192         API_NS(scalar_t) nonce_scalar_2;
 193         API_NS(scalar_halve)(nonce_scalar_2,nonce_scalar);
 194         for (unsigned int c = 2; c < DECAF_448_EDDSA_ENCODE_RATIO; c <<= 1) {
 195             API_NS(scalar_halve)(nonce_scalar_2,nonce_scalar_2);
 196         }
 197
 198         API_NS(point_t) p;
 199         API_NS(precomputed_scalarmul)(p,API_NS(precomputed_base),nonce_scalar_2);
 200         API_NS(point_mul_by_ratio_and_encode_like_eddsa)(nonce_point, p);
 201         API_NS(point_destroy)(p);
 202         API_NS(scalar_destroy)(nonce_scalar_2);
 203     }
 204
 205     API_NS(scalar_t) challenge_scalar;
 206     {
 207         /* Compute the challenge */
 208         hash_init_with_dom(hash,prehashed,0,context,context_len);
 209         hash_update(hash,nonce_point,sizeof(nonce_point));
 210         hash_update(hash,pubkey,DECAF_EDDSA_448_PUBLIC_BYTES);
 211         hash_update(hash,message,message_len);
 212         uint8_t challenge[2*DECAF_EDDSA_448_PRIVATE_BYTES];
 213         hash_final(hash,challenge,sizeof(challenge));
 214         hash_destroy(hash);
 215         API_NS(scalar_decode_long)(challenge_scalar,challenge,sizeof(challenge));
 216         decaf_bzero(challenge,sizeof(challenge));
 217     }
 218
 219     API_NS(scalar_mul)(challenge_scalar,challenge_scalar,secret_scalar);
 220     API_NS(scalar_add)(challenge_scalar,challenge_scalar,nonce_scalar);
 221
 222     decaf_bzero(signature,DECAF_EDDSA_448_SIGNATURE_BYTES);
 223     memcpy(signature,nonce_point,sizeof(nonce_point));
 224     API_NS(scalar_encode)(&signature[DECAF_EDDSA_448_PUBLIC_BYTES],challenge_scalar);
 225
 226     API_NS(scalar_destroy)(secret_scalar);
 227     API_NS(scalar_destroy)(nonce_scalar);
 228     API_NS(scalar_destroy)(challenge_scalar);
 229 }
 230
 231
 232 void decaf_ed448_sign_prehash (
 233     uint8_t signature[DECAF_EDDSA_448_SIGNATURE_BYTES],
 234     const uint8_t privkey[DECAF_EDDSA_448_PRIVATE_BYTES],
 235     const uint8_t pubkey[DECAF_EDDSA_448_PUBLIC_BYTES],
 236     const decaf_ed448_prehash_ctx_t hash,
 237     const uint8_t *context,
 238     uint8_t context_len
 239 ) {
 240     uint8_t hash_output[EDDSA_PREHASH_BYTES];
 241     {
 242         decaf_ed448_prehash_ctx_t hash_too;
 243         memcpy(hash_too,hash,sizeof(hash_too));
 244         hash_final(hash_too,hash_output,sizeof(hash_output));
 245         hash_destroy(hash_too);
 246     }
 247
 248     decaf_ed448_sign(signature,privkey,pubkey,hash_output,sizeof(hash_output),1,context,context_len);
 249     decaf_bzero(hash_output,sizeof(hash_output));
 250 }
 251
 252 decaf_error_t decaf_ed448_verify (
 253     const uint8_t signature[DECAF_EDDSA_448_SIGNATURE_BYTES],
 254     const uint8_t pubkey[DECAF_EDDSA_448_PUBLIC_BYTES],
 255     const uint8_t *message,
 256     size_t message_len,
 257     uint8_t prehashed,
 258     const uint8_t *context,
 259     uint8_t context_len
 260 ) {
 261     API_NS(point_t) pk_point, r_point;
 262     decaf_error_t error = API_NS(point_decode_like_eddsa_and_mul_by_ratio)(pk_point,pubkey);
 263     if (DECAF_SUCCESS != error) { return error; }
 264
 265     error = API_NS(point_decode_like_eddsa_and_mul_by_ratio)(r_point,signature);
 266     if (DECAF_SUCCESS != error) { return error; }
 267
 268     API_NS(scalar_t) challenge_scalar;
 269     {
 270         /* Compute the challenge */
 271         hash_ctx_t hash;
 272         hash_init_with_dom(hash,prehashed,0,context,context_len);
 273         hash_update(hash,signature,DECAF_EDDSA_448_PUBLIC_BYTES);
 274         hash_update(hash,pubkey,DECAF_EDDSA_448_PUBLIC_BYTES);
 275         hash_update(hash,message,message_len);
 276         uint8_t challenge[2*DECAF_EDDSA_448_PRIVATE_BYTES];
 277         hash_final(hash,challenge,sizeof(challenge));
 278         hash_destroy(hash);
 279         API_NS(scalar_decode_long)(challenge_scalar,challenge,sizeof(challenge));
 280         decaf_bzero(challenge,sizeof(challenge));
 281     }
 282     API_NS(scalar_sub)(challenge_scalar, API_NS(scalar_zero), challenge_scalar);
 283
 284     API_NS(scalar_t) response_scalar;
 285     API_NS(scalar_decode_long)(
 286         response_scalar,
 287         &signature[DECAF_EDDSA_448_PUBLIC_BYTES],
 288         DECAF_EDDSA_448_PRIVATE_BYTES
 289     );
 290
 291     for (unsigned c=1; c<DECAF_448_EDDSA_DECODE_RATIO; c<<=1) {
 292         API_NS(scalar_add)(response_scalar,response_scalar,response_scalar);
 293     }
 294
 295
 296     /* pk_point = -c(x(P)) + (cx + k)G = kG */
 297     API_NS(base_double_scalarmul_non_secret)(
 298         pk_point,
 299         response_scalar,
 300         pk_point,
 301         challenge_scalar
 302     );
 303     return decaf_succeed_if(API_NS(point_eq(pk_point,r_point)));
 304 }
 305
 306
 307 decaf_error_t decaf_ed448_verify_prehash (
 308     const uint8_t signature[DECAF_EDDSA_448_SIGNATURE_BYTES],
 309     const uint8_t pubkey[DECAF_EDDSA_448_PUBLIC_BYTES],
 310     const decaf_ed448_prehash_ctx_t hash,
 311     const uint8_t *context,
 312     uint8_t context_len
 313 ) {
 314     decaf_error_t ret;
 315
 316     uint8_t hash_output[EDDSA_PREHASH_BYTES];
 317     {
 318         decaf_ed448_prehash_ctx_t hash_too;
 319         memcpy(hash_too,hash,sizeof(hash_too));
 320         hash_final(hash_too,hash_output,sizeof(hash_output));
 321         hash_destroy(hash_too);
 322     }
 323
 324     ret = decaf_ed448_verify(signature,pubkey,hash_output,sizeof(hash_output),1,context,context_len);
 325
 326     return ret;
 327 }