31b4bb5f79d97bb1279828c2ab2df444962edd3a
[openssl.git] / crypto / ec / curve448 / point_448.h
1 /**
2  * @file decaf/point_448.h
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  * @brief A group of prime order p, based on Ed448-Goldilocks.
10  *
11  * @warning This file was automatically generated in Python.
12  * Please do not edit it.
13  */
14
15 #ifndef __DECAF_POINT_448_H__
16 #define __DECAF_POINT_448_H__ 1
17
18 #include "curve448utils.h"
19 #include "field.h"
20
21 #ifdef __cplusplus
22 extern "C" {
23 #endif
24
25 /** @cond internal */
26 #define DECAF_448_SCALAR_LIMBS ((446-1)/DECAF_WORD_BITS+1)
27 /** @endcond */
28
29 /** The number of bits in a scalar */
30 #define DECAF_448_SCALAR_BITS 446
31
32 /** Number of bytes in a serialized point. */
33 #define DECAF_448_SER_BYTES 56
34
35 /** Number of bytes in an elligated point.  For now set the same as SER_BYTES
36  * but could be different for other curves.
37  */
38 #define DECAF_448_HASH_BYTES 56
39
40 /** Number of bytes in a serialized scalar. */
41 #define DECAF_448_SCALAR_BYTES 56
42
43 /** Number of bits in the "which" field of an elligator inverse */
44 #define DECAF_448_INVERT_ELLIGATOR_WHICH_BITS 3
45
46 /** The cofactor the curve would have, if we hadn't removed it */
47 #define DECAF_448_REMOVED_COFACTOR 4
48
49 /** X448 encoding ratio. */
50 #define DECAF_X448_ENCODE_RATIO 2
51
52 /** Number of bytes in an x448 public key */
53 #define DECAF_X448_PUBLIC_BYTES 56
54
55 /** Number of bytes in an x448 private key */
56 #define DECAF_X448_PRIVATE_BYTES 56
57
58 /** Twisted Edwards extended homogeneous coordinates */
59 typedef struct curve448_point_s {
60     /** @cond internal */
61     gf_448_t x,y,z,t;
62     /** @endcond */
63 } curve448_point_t[1];
64
65 /** Precomputed table based on a point.  Can be trivial implementation. */
66 struct curve448_precomputed_s;
67
68 /** Precomputed table based on a point.  Can be trivial implementation. */
69 typedef struct curve448_precomputed_s curve448_precomputed_s; 
70
71 /** Scalar is stored packed, because we don't need the speed. */
72 typedef struct curve448_scalar_s {
73     /** @cond internal */
74     decaf_word_t limb[DECAF_448_SCALAR_LIMBS];
75     /** @endcond */
76 } curve448_scalar_t[1];
77
78 /** A scalar equal to 1. */
79 extern const curve448_scalar_t curve448_scalar_one DECAF_API_VIS;
80
81 /** A scalar equal to 0. */
82 extern const curve448_scalar_t curve448_scalar_zero DECAF_API_VIS;
83
84 /** The identity point on the curve. */
85 extern const curve448_point_t curve448_point_identity DECAF_API_VIS;
86
87 /** An arbitrarily chosen base point on the curve. */
88 extern const curve448_point_t curve448_point_base DECAF_API_VIS;
89
90 /** Precomputed table for the base point on the curve. */
91 extern const struct curve448_precomputed_s *curve448_precomputed_base DECAF_API_VIS;
92
93 /**
94  * @brief Read a scalar from wire format or from bytes.
95  *
96  * @param [in] ser Serialized form of a scalar.
97  * @param [out] out Deserialized form.
98  *
99  * @retval DECAF_SUCCESS The scalar was correctly encoded.
100  * @retval DECAF_FAILURE The scalar was greater than the modulus,
101  * and has been reduced modulo that modulus.
102  */
103 decaf_error_t curve448_scalar_decode (
104     curve448_scalar_t out,
105     const unsigned char ser[DECAF_448_SCALAR_BYTES]
106 ) DECAF_API_VIS DECAF_WARN_UNUSED DECAF_NONNULL DECAF_NOINLINE;
107
108 /**
109  * @brief Read a scalar from wire format or from bytes.  Reduces mod
110  * scalar prime.
111  *
112  * @param [in] ser Serialized form of a scalar.
113  * @param [in] ser_len Length of serialized form.
114  * @param [out] out Deserialized form.
115  */
116 void curve448_scalar_decode_long (
117     curve448_scalar_t out,
118     const unsigned char *ser,
119     size_t ser_len
120 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE;
121     
122 /**
123  * @brief Serialize a scalar to wire format.
124  *
125  * @param [out] ser Serialized form of a scalar.
126  * @param [in] s Deserialized scalar.
127  */
128 void curve448_scalar_encode (
129     unsigned char ser[DECAF_448_SCALAR_BYTES],
130     const curve448_scalar_t s
131 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE DECAF_NOINLINE;
132         
133 /**
134  * @brief Add two scalars.  The scalars may use the same memory.
135  * @param [in] a One scalar.
136  * @param [in] b Another scalar.
137  * @param [out] out a+b.
138  */
139 void curve448_scalar_add (
140     curve448_scalar_t out,
141     const curve448_scalar_t a,
142     const curve448_scalar_t b
143 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE;
144
145 /**
146  * @brief Compare two scalars.
147  * @param [in] a One scalar.
148  * @param [in] b Another scalar.
149  * @retval DECAF_TRUE The scalars are equal.
150  * @retval DECAF_FALSE The scalars are not equal.
151  */    
152 decaf_bool_t curve448_scalar_eq (
153     const curve448_scalar_t a,
154     const curve448_scalar_t b
155 ) DECAF_API_VIS DECAF_WARN_UNUSED DECAF_NONNULL DECAF_NOINLINE;
156
157 /**
158  * @brief Subtract two scalars.  The scalars may use the same memory.
159  * @param [in] a One scalar.
160  * @param [in] b Another scalar.
161  * @param [out] out a-b.
162  */  
163 void curve448_scalar_sub (
164     curve448_scalar_t out,
165     const curve448_scalar_t a,
166     const curve448_scalar_t b
167 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE;
168
169 /**
170  * @brief Multiply two scalars.  The scalars may use the same memory.
171  * @param [in] a One scalar.
172  * @param [in] b Another scalar.
173  * @param [out] out a*b.
174  */  
175 void curve448_scalar_mul (
176     curve448_scalar_t out,
177     const curve448_scalar_t a,
178     const curve448_scalar_t b
179 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE;
180         
181 /**
182 * @brief Halve a scalar.  The scalars may use the same memory.
183 * @param [in] a A scalar.
184 * @param [out] out a/2.
185 */
186 void curve448_scalar_halve (
187    curve448_scalar_t out,
188    const curve448_scalar_t a
189 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE;
190
191 /**
192  * @brief Invert a scalar.  When passed zero, return 0.  The input and output may alias.
193  * @param [in] a A scalar.
194  * @param [out] out 1/a.
195  * @return DECAF_SUCCESS The input is nonzero.
196  */  
197 decaf_error_t curve448_scalar_invert (
198     curve448_scalar_t out,
199     const curve448_scalar_t a
200 ) DECAF_API_VIS DECAF_WARN_UNUSED DECAF_NONNULL DECAF_NOINLINE;
201
202 /**
203  * @brief Copy a scalar.  The scalars may use the same memory, in which
204  * case this function does nothing.
205  * @param [in] a A scalar.
206  * @param [out] out Will become a copy of a.
207  */
208 static inline void DECAF_NONNULL curve448_scalar_copy (
209     curve448_scalar_t out,
210     const curve448_scalar_t a
211 ) {
212     *out = *a;
213 }
214
215 /**
216  * @brief Set a scalar to an unsigned 64-bit integer.
217  * @param [in] a An integer.
218  * @param [out] out Will become equal to a.
219  */  
220 void curve448_scalar_set_unsigned (
221     curve448_scalar_t out,
222     uint64_t a
223 ) DECAF_API_VIS DECAF_NONNULL;
224
225 /**
226  * @brief Copy a point.  The input and output may alias,
227  * in which case this function does nothing.
228  *
229  * @param [out] a A copy of the point.
230  * @param [in] b Any point.
231  */
232 static inline void DECAF_NONNULL curve448_point_copy (
233     curve448_point_t a,
234     const curve448_point_t b
235 ) {
236     *a=*b;
237 }
238
239 /**
240  * @brief Test whether two points are equal.  If yes, return
241  * DECAF_TRUE, else return DECAF_FALSE.
242  *
243  * @param [in] a A point.
244  * @param [in] b Another point.
245  * @retval DECAF_TRUE The points are equal.
246  * @retval DECAF_FALSE The points are not equal.
247  */
248 decaf_bool_t curve448_point_eq (
249     const curve448_point_t a,
250     const curve448_point_t b
251 ) DECAF_API_VIS DECAF_WARN_UNUSED DECAF_NONNULL DECAF_NOINLINE;
252
253 /**
254  * @brief Double a point.  Equivalent to
255  * curve448_point_add(two_a,a,a), but potentially faster.
256  *
257  * @param [out] two_a The sum a+a.
258  * @param [in] a A point.
259  */
260 void curve448_point_double (
261     curve448_point_t two_a,
262     const curve448_point_t a
263 ) DECAF_API_VIS DECAF_NONNULL;
264
265 /**
266  * @brief RFC 7748 Diffie-Hellman scalarmul.  This function uses a different
267  * (non-Decaf) encoding.
268  *
269  * @param [out] scaled The scaled point base*scalar
270  * @param [in] base The point to be scaled.
271  * @param [in] scalar The scalar to multiply by.
272  *
273  * @retval DECAF_SUCCESS The scalarmul succeeded.
274  * @retval DECAF_FAILURE The scalarmul didn't succeed, because the base
275  * point is in a small subgroup.
276  */
277 decaf_error_t decaf_x448 (
278     uint8_t out[DECAF_X448_PUBLIC_BYTES],
279     const uint8_t base[DECAF_X448_PUBLIC_BYTES],
280     const uint8_t scalar[DECAF_X448_PRIVATE_BYTES]
281 ) DECAF_API_VIS DECAF_NONNULL DECAF_WARN_UNUSED DECAF_NOINLINE;
282
283 /**
284  * @brief Multiply a point by DECAF_X448_ENCODE_RATIO,
285  * then encode it like RFC 7748.
286  *
287  * This function is mainly used internally, but is exported in case
288  * it will be useful.
289  *
290  * The ratio is necessary because the internal representation doesn't
291  * track the cofactor information, so on output we must clear the cofactor.
292  * This would multiply by the cofactor, but in fact internally libdecaf's
293  * points are always even, so it multiplies by half the cofactor instead.
294  *
295  * As it happens, this aligns with the base point definitions; that is,
296  * if you pass the Decaf/Ristretto base point to this function, the result
297  * will be DECAF_X448_ENCODE_RATIO times the X448
298  * base point.
299  *
300  * @param [out] out The scaled and encoded point.
301  * @param [in] p The point to be scaled and encoded.
302  */
303 void curve448_point_mul_by_ratio_and_encode_like_x448 (
304     uint8_t out[DECAF_X448_PUBLIC_BYTES],
305     const curve448_point_t p
306 ) DECAF_API_VIS DECAF_NONNULL;
307
308 /** The base point for X448 Diffie-Hellman */
309 extern const uint8_t decaf_x448_base_point[DECAF_X448_PUBLIC_BYTES] DECAF_API_VIS;
310     
311 /**
312  * @brief RFC 7748 Diffie-Hellman base point scalarmul.  This function uses
313  * a different (non-Decaf) encoding.
314  *
315  * Does exactly the same thing as decaf_x448_generate_key,
316  * but has a better name.
317  *
318  * @param [out] scaled The scaled point base*scalar
319  * @param [in] scalar The scalar to multiply by.
320  */
321 void decaf_x448_derive_public_key (
322     uint8_t out[DECAF_X448_PUBLIC_BYTES],
323     const uint8_t scalar[DECAF_X448_PRIVATE_BYTES]
324 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE;
325
326 /* FUTURE: uint8_t curve448_encode_like_curve448) */
327
328 /**
329  * @brief Precompute a table for fast scalar multiplication.
330  * Some implementations do not include precomputed points; for
331  * those implementations, this implementation simply copies the
332  * point.
333  *
334  * @param [out] a A precomputed table of multiples of the point.
335  * @param [in] b Any point.
336  */
337 void curve448_precompute (
338     curve448_precomputed_s *a,
339     const curve448_point_t b
340 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE;
341
342 /**
343  * @brief Multiply a precomputed base point by a scalar:
344  * scaled = scalar*base.
345  * Some implementations do not include precomputed points; for
346  * those implementations, this function is the same as
347  * curve448_point_scalarmul
348  *
349  * @param [out] scaled The scaled point base*scalar
350  * @param [in] base The point to be scaled.
351  * @param [in] scalar The scalar to multiply by.
352  */
353 void curve448_precomputed_scalarmul (
354     curve448_point_t scaled,
355     const curve448_precomputed_s *base,
356     const curve448_scalar_t scalar
357 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE;
358
359
360 /**
361  * @brief Multiply two base points by two scalars:
362  * scaled = scalar1*curve448_point_base + scalar2*base2.
363  *
364  * Otherwise equivalent to curve448_point_double_scalarmul, but may be
365  * faster at the expense of being variable time.
366  *
367  * @param [out] combo The linear combination scalar1*base + scalar2*base2.
368  * @param [in] scalar1 A first scalar to multiply by.
369  * @param [in] base2 A second point to be scaled.
370  * @param [in] scalar2 A second scalar to multiply by.
371  *
372  * @warning: This function takes variable time, and may leak the scalars
373  * used.  It is designed for signature verification.
374  */
375 void curve448_base_double_scalarmul_non_secret (
376     curve448_point_t combo,
377     const curve448_scalar_t scalar1,
378     const curve448_point_t base2,
379     const curve448_scalar_t scalar2
380 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE;
381
382 /**
383  * @brief Constant-time decision between two scalars.  If pick_b
384  * is zero, out = a; else out = b.
385  *
386  * @param [out] out The output.  It may be the same as either input.
387  * @param [in] a Any scalar.
388  * @param [in] b Any scalar.
389  * @param [in] pick_b If nonzero, choose scalar b.
390  */
391 void curve448_scalar_cond_sel (
392     curve448_scalar_t out,
393     const curve448_scalar_t a,
394     const curve448_scalar_t b,
395     decaf_word_t pick_b
396 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE;
397
398 /**
399  * @brief Test that a point is valid, for debugging purposes.
400  *
401  * @param [in] to_test The point to test.
402  * @retval DECAF_TRUE The point is valid.
403  * @retval DECAF_FALSE The point is invalid.
404  */
405 decaf_bool_t curve448_point_valid (
406     const curve448_point_t to_test
407 ) DECAF_API_VIS DECAF_WARN_UNUSED DECAF_NONNULL DECAF_NOINLINE;
408
409
410 /**
411  * @brief Almost-Elligator-like hash to curve.
412  *
413  * Call this function with the output of a hash to make a hash to the curve.
414  *
415  * This function runs Elligator2 on the curve448 Jacobi quartic model.  It then
416  * uses the isogeny to put the result in twisted Edwards form.  As a result,
417  * it is safe (cannot produce points of order 4), and would be compatible with
418  * hypothetical other implementations of Decaf using a Montgomery or untwisted
419  * Edwards model.
420  *
421  * Unlike Elligator, this function may be up to 4:1 on [0,(p-1)/2]:
422  *   A factor of 2 due to the isogeny.
423  *   A factor of 2 because we quotient out the 2-torsion.
424  *
425  * This makes it about 8:1 overall, or 16:1 overall on curves with cofactor 8.
426  *
427  * Negating the input (mod q) results in the same point.  Inverting the input
428  * (mod q) results in the negative point.  This is the same as Elligator.
429  *
430  * This function isn't quite indifferentiable from a random oracle.
431  * However, it is suitable for many protocols, including SPEKE and SPAKE2 EE. 
432  * Furthermore, calling it twice with independent seeds and adding the results
433  * is indifferentiable from a random oracle.
434  *
435  * @param [in] hashed_data Output of some hash function.
436  * @param [out] pt The data hashed to the curve.
437  */
438 void
439 curve448_point_from_hash_nonuniform (
440     curve448_point_t pt,
441     const unsigned char hashed_data[DECAF_448_HASH_BYTES]
442 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE;
443
444 /**
445  * @brief Indifferentiable hash function encoding to curve.
446  *
447  * Equivalent to calling curve448_point_from_hash_nonuniform twice and adding.
448  *
449  * @param [in] hashed_data Output of some hash function.
450  * @param [out] pt The data hashed to the curve.
451  */ 
452 void curve448_point_from_hash_uniform (
453     curve448_point_t pt,
454     const unsigned char hashed_data[2*DECAF_448_HASH_BYTES]
455 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE;
456
457 /**
458  * @brief Inverse of elligator-like hash to curve.
459  *
460  * This function writes to the buffer, to make it so that
461  * curve448_point_from_hash_nonuniform(buffer) = pt if
462  * possible.  Since there may be multiple preimages, the
463  * "which" parameter chooses between them.  To ensure uniform
464  * inverse sampling, this function succeeds or fails
465  * independently for different "which" values.
466  *
467  * This function isn't guaranteed to find every possible
468  * preimage, but it finds all except a small finite number.
469  * In particular, when the number of bits in the modulus isn't
470  * a multiple of 8 (i.e. for curve25519), it sets the high bits
471  * independently, which enables the generated data to be uniform.
472  * But it doesn't add p, so you'll never get exactly p from this
473  * function.  This might change in the future, especially if
474  * we ever support eg Brainpool curves, where this could cause
475  * real nonuniformity.
476  *
477  * @param [out] recovered_hash Encoded data.
478  * @param [in] pt The point to encode.
479  * @param [in] which A value determining which inverse point
480  * to return.
481  *
482  * @retval DECAF_SUCCESS The inverse succeeded.
483  * @retval DECAF_FAILURE The inverse failed.
484  */
485 decaf_error_t
486 curve448_invert_elligator_nonuniform (
487     unsigned char recovered_hash[DECAF_448_HASH_BYTES],
488     const curve448_point_t pt,
489     uint32_t which
490 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE DECAF_WARN_UNUSED;
491
492 /**
493  * @brief Inverse of elligator-like hash to curve.
494  *
495  * This function writes to the buffer, to make it so that
496  * curve448_point_from_hash_uniform(buffer) = pt if
497  * possible.  Since there may be multiple preimages, the
498  * "which" parameter chooses between them.  To ensure uniform
499  * inverse sampling, this function succeeds or fails
500  * independently for different "which" values.
501  *
502  * @param [out] recovered_hash Encoded data.
503  * @param [in] pt The point to encode.
504  * @param [in] which A value determining which inverse point
505  * to return.
506  *
507  * @retval DECAF_SUCCESS The inverse succeeded.
508  * @retval DECAF_FAILURE The inverse failed.
509  */
510 decaf_error_t
511 curve448_invert_elligator_uniform (
512     unsigned char recovered_hash[2*DECAF_448_HASH_BYTES],
513     const curve448_point_t pt,
514     uint32_t which
515 ) DECAF_API_VIS DECAF_NONNULL DECAF_NOINLINE DECAF_WARN_UNUSED;
516
517 /**
518  * @brief Overwrite scalar with zeros.
519  */
520 void curve448_scalar_destroy (
521     curve448_scalar_t scalar
522 ) DECAF_NONNULL DECAF_API_VIS;
523
524 /**
525  * @brief Overwrite point with zeros.
526  */
527 void curve448_point_destroy (
528     curve448_point_t point
529 ) DECAF_NONNULL DECAF_API_VIS;
530
531 #ifdef __cplusplus
532 } /* extern "C" */
533 #endif
534
535 #endif /* __DECAF_POINT_448_H__ */