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