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