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