Line data Source code
1 : #ifndef HEADER_fd_src_ballet_ed25519_fd_curve25519_h
2 : #define HEADER_fd_src_ballet_ed25519_fd_curve25519_h
3 :
4 : /* fd_curve25519.h provides the public Curve25519 API.
5 :
6 : Most operations in this API should be assumed to take a variable
7 : amount of time depending on inputs. (And thus should not be exposed
8 : to secret data).
9 :
10 : Const time operations are made explicit, see fd_curve25519_secure.c */
11 :
12 : #if FD_HAS_AVX512
13 : #include "avx512/fd_curve25519.h"
14 : #else
15 : #include "ref/fd_curve25519.h"
16 : #endif
17 :
18 : /* Max batch size for MSM. */
19 15561 : #define FD_BALLET_CURVE25519_MSM_BATCH_SZ 32
20 :
21 : /* curve constants. these are imported from table/fd_curve25519_table_{arch}.c.
22 : they are (re)defined here to avoid breaking compilation when the table needs
23 : to be rebuilt. */
24 : static const fd_ed25519_point_t fd_ed25519_base_point[1];
25 : static const fd_ed25519_point_t fd_ed25519_base_point_wnaf_table[128];
26 : static const fd_ed25519_point_t fd_ed25519_base_point_const_time_table[32][8];
27 :
28 : FD_PROTOTYPES_BEGIN
29 :
30 : /* fd_ed25519_point_add computes r = a + b, and returns r.
31 : formulas are complete, i.e. it can be a == b.
32 : Cost: 9mul */
33 : fd_ed25519_point_t *
34 : fd_ed25519_point_add( fd_ed25519_point_t * r,
35 : fd_ed25519_point_t const * a,
36 : fd_ed25519_point_t const * b );
37 :
38 : /* fd_ed25519_point_dbln computes r = 2^n a, and returns r.
39 : More efficient than n fd_ed25519_point_add. */
40 : fd_ed25519_point_t *
41 : fd_ed25519_point_dbln( fd_ed25519_point_t * r,
42 : fd_ed25519_point_t const * a,
43 : int const n );
44 :
45 : /* fd_ed25519_point_sub computes r = a - b, and returns r.
46 : formulas are complete, i.e. it can be a == b.
47 : Cost: 9mul */
48 : fd_ed25519_point_t *
49 : fd_ed25519_point_sub( fd_ed25519_point_t * r,
50 : fd_ed25519_point_t const * a,
51 : fd_ed25519_point_t const * b );
52 :
53 : /* fd_ed25519_point_set sets r = 0 (point at infinity). */
54 : fd_ed25519_point_t *
55 : fd_ed25519_point_set_zero( fd_ed25519_point_t * r );
56 :
57 : /* fd_ed25519_point_set_zero_precomputed sets r = 0 (point at infinity). */
58 : fd_ed25519_point_t *
59 : fd_ed25519_point_set_zero_precomputed( fd_ed25519_point_t * r );
60 :
61 : /* fd_ed25519_point_set sets r = a. */
62 : fd_ed25519_point_t *
63 : fd_ed25519_point_set( fd_ed25519_point_t * r,
64 : fd_ed25519_point_t const * a );
65 :
66 : /* fd_ed25519_point_from sets r = (x : y : z : t). */
67 : fd_ed25519_point_t *
68 : fd_ed25519_point_from( fd_ed25519_point_t * r,
69 : fd_f25519_t const * x,
70 : fd_f25519_t const * y,
71 : fd_f25519_t const * z,
72 : fd_f25519_t const * t );
73 :
74 : /* fd_ed25519_point_sub sets r = -a. */
75 : fd_ed25519_point_t *
76 : fd_ed25519_point_neg( fd_ed25519_point_t * r,
77 : fd_ed25519_point_t const * a );
78 :
79 : fd_ed25519_point_t *
80 : fd_ed25519_point_dbl( fd_ed25519_point_t * r,
81 : fd_ed25519_point_t const * a );
82 :
83 : /* fd_ed25519_point_is_zero returns 1 if a == 0 (point at infinity), 0 otherwise. */
84 : int
85 : fd_ed25519_point_is_zero( fd_ed25519_point_t const * a );
86 :
87 : /* fd_ed25519_affine_is_small_order returns 1 if a has small order (order <= 8), 0 otherwise. */
88 : FD_25519_INLINE int
89 7024 : fd_ed25519_affine_is_small_order( fd_ed25519_point_t const * a ) {
90 : /* There are 8 points with order <= 8, aka low order:
91 : 0100000000000000000000000000000000000000000000000000000000000000 ( 0 : 1 ) P0: order 1
92 : ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f ( 0 : -1 ) P1: order 2
93 : 0000000000000000000000000000000000000000000000000000000000000000 ( b0.. : 0 ) P2: order 4
94 : 0000000000000000000000000000000000000000000000000000000000000080 ( 3d.. : 0 ) -P2: order 4
95 : 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05 ( 4a.. : 26.. ) P3: order 8
96 : 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc85 ( a3.. : 26.. ) -P3: order 8
97 : c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a ( 4a.. : c7.. ) P4: order 8
98 : c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa ( a3.. : c7.. ) -P4: order 8
99 :
100 : We could test:
101 : fd_ed25519_point_t r[1];
102 : fd_ed25519_point_dbln( r, a, 3 );
103 : return fd_ed25519_point_is_zero( r );
104 :
105 : When the point is affine (Z==1), we can simply check:
106 : - X==0
107 : - or, Y==0
108 : - or, Y==2a..., or Y==c7...
109 :
110 : And if the point is not affine, we could do 1 single dbl and check for X==0 or Y==0
111 : (currently not implemented as not needed).
112 : */
113 7024 : fd_f25519_t x[1], y[1], z[1], t[1];
114 7024 : fd_ed25519_point_to( x, y, z, t, a );
115 7024 : return fd_f25519_is_zero( x ) | fd_f25519_is_zero( y )
116 7024 : | fd_f25519_eq( y, fd_ed25519_order8_point_y0 )
117 7024 : | fd_f25519_eq( y, fd_ed25519_order8_point_y1 );
118 7024 : }
119 :
120 : /* fd_ed25519_point_eq returns 1 if a == b, 0 otherwise. */
121 : int
122 : fd_ed25519_point_eq( fd_ed25519_point_t const * a,
123 : fd_ed25519_point_t const * b );
124 :
125 : /* fd_ed25519_point_eq returns 1 if a == b, 0 otherwise.
126 : b is a point with Z==1, e.g. a decompressed point. */
127 : int
128 : fd_ed25519_point_eq_z1( fd_ed25519_point_t const * a,
129 : fd_ed25519_point_t const * b ); /* b.Z == 1, e.g. a decompressed point */
130 :
131 : /* fd_ed25519_scalar_validate is an alias of fd_curve25519_scalar_validate
132 : It checks whether the given Ed25519 scalar n matches the canonical byte
133 : representation. Not constant time and thus should not be exposed to secrets.
134 : Returns s if canonical, NULL otherwise. */
135 :
136 : FD_25519_INLINE uchar const *
137 0 : fd_ed25519_scalar_validate( uchar const n[ 32 ] ) {
138 0 : return fd_curve25519_scalar_validate( n );
139 0 : }
140 :
141 : /* fd_ed25519_scalar_mul computes r = n * a, and returns r.
142 : n is a scalar.
143 : Precondition: a must be affine (Z==1). */
144 : fd_ed25519_point_t *
145 : fd_ed25519_scalar_mul( fd_ed25519_point_t * r,
146 : uchar const n[ 32 ],
147 : fd_ed25519_point_t const * a );
148 :
149 : /* fd_ed25519_scalar_mul_base_const_time computes r = n * P, and returns r.
150 : n is a scalar. P is the base point.
151 : Note: const time implementation, safe to use with n secret. */
152 : fd_ed25519_point_t * FD_FN_SENSITIVE
153 : fd_ed25519_scalar_mul_base_const_time( fd_ed25519_point_t * r,
154 : uchar const n[ 32 ] ); /* can be a secret */
155 :
156 : /* fd_ed25519_double_scalar_mul_base computes r = n1 * a + n2 * P, and returns r.
157 : n1, n2 are scalars. P is the base point.
158 : Precondition: a must be affine (Z==1). */
159 : fd_ed25519_point_t *
160 : fd_ed25519_double_scalar_mul_base( fd_ed25519_point_t * r,
161 : uchar const n1[ 32 ],
162 : fd_ed25519_point_t const * a,
163 : uchar const n2[ 32 ] );
164 :
165 : /* Split tables for fd_ed25519_double_scalar_mul_base_split. A scalar
166 : is processed as FD_ED25519_SPLIT_SEG_CNT segments of
167 : FD_ED25519_SPLIT_SEG_BITS bits. The A table holds, for each segment
168 : j, the odd multiples 1,3,..,2^FD_ED25519_SPLIT_A_BITS-1 of [2^(bj)]A
169 : where b=FD_ED25519_SPLIT_SEG_BITS (FD_ED25519_SPLIT_A_SEG_CNT points
170 : per segment, table index FD_ED25519_SPLIT_A_SEG_CNT*j+i holds
171 : [(2i+1) 2^(bj)]A). The B table holds, for each segment j>0, the odd
172 : multiples 1,3,..,255 of [2^(bj)]B (128 points per segment, table
173 : index 128*(j-1)+i holds [(2i+1) 2^(bj)]B). Segment 0 of B uses
174 : fd_ed25519_base_point_wnaf_table. All points are in precomputed
175 : form (see fd_curve25519_into_precomputed).
176 :
177 : More segments trade doublings in the shared loop for a larger per
178 : key A table (and a larger fixed B table). The caches hold 2k-4k
179 : keys, so the per key table (which is what misses) is what limits
180 : the geometry: 8 segments of 32 bits with a 3 bit A window keeps the
181 : per key table at 32 points while halving the doublings. Larger
182 : tables are faster when hot but slower once the key set exceeds the
183 : L2. */
184 :
185 0 : #define FD_ED25519_SPLIT_SEG_CNT (8)
186 0 : #define FD_ED25519_SPLIT_SEG_BITS (256/FD_ED25519_SPLIT_SEG_CNT)
187 0 : #define FD_ED25519_SPLIT_A_BITS (3)
188 0 : #define FD_ED25519_SPLIT_A_SEG_CNT (1<<(FD_ED25519_SPLIT_A_BITS-1))
189 0 : #define FD_ED25519_SPLIT_A_TBL_CNT ((ulong)(FD_ED25519_SPLIT_SEG_CNT*FD_ED25519_SPLIT_A_SEG_CNT))
190 : #define FD_ED25519_SPLIT_B_TBL_CNT ((ulong)((FD_ED25519_SPLIT_SEG_CNT-1)*128))
191 :
192 : /* fd_ed25519_split_table_a fills tbl with the split table of a (any
193 : valid curve point). fd_ed25519_split_table_b fills tbl with the
194 : split table of the base point. */
195 : void
196 : fd_ed25519_split_table_a( fd_ed25519_point_t tbl[ FD_ED25519_SPLIT_A_TBL_CNT ],
197 : fd_ed25519_point_t const * a );
198 :
199 : void
200 : fd_ed25519_split_table_b( fd_ed25519_point_t tbl[ FD_ED25519_SPLIT_B_TBL_CNT ] );
201 :
202 : /* fd_ed25519_double_scalar_mul_base_split computes r = n1 * a + n2 * P,
203 : where a_tbl is the split table of a, b_tbl is the split table of the
204 : base point P, and returns r. n1, n2 are scalars in [0,2^253). The
205 : result is the same group element fd_ed25519_double_scalar_mul_base
206 : computes for any curve point a (including mixed order points). */
207 : fd_ed25519_point_t *
208 : fd_ed25519_double_scalar_mul_base_split( fd_ed25519_point_t * r,
209 : uchar const n1[ 32 ],
210 : fd_ed25519_point_t const * a_tbl,
211 : uchar const n2[ 32 ],
212 : fd_ed25519_point_t const * b_tbl );
213 :
214 : /* fd_ed25519_double_scalar_mul_base_split_decode is the same but
215 : advances dec between its point ops. The caller still calls
216 : fd_ed25519_point_decode_fini. */
217 : fd_ed25519_point_t *
218 : fd_ed25519_double_scalar_mul_base_split_decode( fd_ed25519_point_t * r,
219 : uchar const n1[ 32 ],
220 : fd_ed25519_point_t const * a_tbl,
221 : uchar const n2[ 32 ],
222 : fd_ed25519_point_t const * b_tbl,
223 : fd_ed25519_point_decode_t * dec );
224 :
225 : /* fd_ed25519_multi_scalar_mul computes r = n0 * a0 + n1 * a1 + ..., and returns r.
226 : n is a vector of sz scalars. a is a vector of sz points.
227 : Precondition: all points in a[] must be affine (Z==1), e.g. from
228 : fd_ed25519_point_frombytes. Passing projective points (Z!=1) will
229 : produce silently wrong results. */
230 : fd_ed25519_point_t *
231 : fd_ed25519_multi_scalar_mul( fd_ed25519_point_t * r,
232 : uchar const n[], /* sz * 32 */
233 : fd_ed25519_point_t const a[], /* sz */
234 : ulong const sz );
235 :
236 : /* fd_ed25519_point_frombytes deserializes a 32-byte buffer buf into a
237 : point r, and returns r (on success, NULL on error).
238 : buf is in little endian form, we accept non-canonical points unlike RFC 8032.
239 : Cost: 1sqrt ~= 1inv ~= 250mul */
240 : fd_ed25519_point_t *
241 : fd_ed25519_point_frombytes( fd_ed25519_point_t * r,
242 : uchar const buf[ 32 ] );
243 :
244 : /* fd_ed25519_point_frombytes_2x deserializes 2x 32-byte buffers buf1, buf2
245 : resp. into points r1, r2, and returns r.
246 : buf1, buf2 are in little endian form, we accept non-canonical points unlike RFC 8032.
247 : It returns 0 on success, -1 or -2 on failure.
248 : Cost: 2sqrt (executed concurrently if possible) */
249 : int
250 : fd_ed25519_point_frombytes_2x( fd_ed25519_point_t * r1,
251 : uchar const buf1[ 32 ],
252 : fd_ed25519_point_t * r2,
253 : uchar const buf2[ 32 ] );
254 :
255 : /* fd_ed25519_point_validate checks if buf represents a valid compressed
256 : point, i.e. if fd_ed25519_point_frombytes would succeed, without
257 : decompressing it. Use fd_ed25519_point_frombytes if the decompressed
258 : point is needed. It returns 1 if buf represents a valid point, 0 if
259 : not. Variable time, do not use with secret data. */
260 : int
261 : fd_ed25519_point_validate( uchar const buf[ 32 ] );
262 :
263 : /* fd_ed25519_point_frombytes_1x deserializes a 32-byte buffer buf into
264 : the point r. Returns 0 on success and -1 on failure. On success, r
265 : is bit-for-bit identical to the point fd_ed25519_point_frombytes_2x
266 : produces for the same buf (in either slot), such that representation
267 : dependent checks (e.g. fd_ed25519_affine_is_small_order) give the
268 : same answer. */
269 : int
270 : fd_ed25519_point_frombytes_1x( fd_ed25519_point_t * r,
271 : uchar const buf[ 32 ] );
272 :
273 : /* Staged fd_ed25519_point_frombytes_1x, so the decode's long
274 : dependency chain can be interleaved with other work. init starts
275 : decoding buf (only read here), step advances up to n chain ops and
276 : fini stores the point in r and returns what frombytes_1x would. */
277 :
278 : void
279 : fd_ed25519_point_decode_init( fd_ed25519_point_decode_t * st,
280 : uchar const buf[ 32 ] );
281 :
282 : void
283 : fd_ed25519_point_decode_step( fd_ed25519_point_decode_t * st,
284 : ulong n );
285 :
286 : int
287 : fd_ed25519_point_decode_fini( fd_ed25519_point_t * r,
288 : fd_ed25519_point_decode_t * st );
289 :
290 : /* fd_ed25519_point_tobytes serializes a point a into
291 : a 32-byte buffer out, and returns out.
292 : out is in little endian form, according to RFC 8032
293 : (we don't output non-canonical points). */
294 : uchar *
295 : fd_ed25519_point_tobytes( uchar out[ 32 ],
296 : fd_ed25519_point_t const * a );
297 :
298 : /* fd_ed25519_point_tobytes_batch8 serializes n points pt[0..n), n in
299 : [1,8], into out (32 bytes each, point i at out+32*i), sharing one
300 : field inversion across the n points. n is asserted to be in
301 : [1,8]. Returns out. */
302 : uchar *
303 : fd_ed25519_point_tobytes_batch8( uchar out[], /* 32*n */
304 : fd_ed25519_point_t const * pt, /* n */
305 : ulong n );
306 :
307 : /* fd_ed25519_affine_tobytes serializes a point a into
308 : a 32-byte buffer out, and returns out.
309 : out is in little endian form, according to RFC 8032.
310 : a is an affine point, i.e. a->Z == 1; compared to
311 : fd_ed25519_point_tobytes, this function doesn't require inv. */
312 : FD_25519_INLINE uchar *
313 : fd_ed25519_affine_tobytes( uchar out[ 32 ],
314 0 : fd_ed25519_point_t const * a ) {
315 0 : fd_f25519_t x[1], y[1], z[1], t[1];
316 0 : fd_ed25519_point_to( x, y, z, t, a );
317 0 : fd_f25519_tobytes( out, y );
318 0 : out[31] ^= (uchar)(fd_f25519_sgn( x ) << 7);
319 0 : return out;
320 0 : }
321 :
322 : /* fd_curve25519_into_precomputed transforms a point into
323 : precomputed table format, e.g. replaces T -> kT to save
324 : 1mul in the dbl-and-add loop. */
325 : void
326 : fd_curve25519_into_precomputed( fd_ed25519_point_t * r );
327 :
328 : /*
329 : Affine (only for offline building precomputation tables, can be slow)
330 : */
331 : fd_ed25519_point_t *
332 : fd_curve25519_affine_frombytes( fd_ed25519_point_t * r,
333 : uchar const x[ 32 ],
334 : uchar const y[ 32 ] );
335 :
336 : fd_ed25519_point_t *
337 : fd_curve25519_into_affine( fd_ed25519_point_t * r );
338 :
339 : fd_ed25519_point_t *
340 : fd_curve25519_affine_add( fd_ed25519_point_t * r,
341 : fd_ed25519_point_t const * a,
342 : fd_ed25519_point_t const * b );
343 :
344 : fd_ed25519_point_t *
345 : fd_curve25519_affine_dbln( fd_ed25519_point_t * r,
346 : fd_ed25519_point_t const * a,
347 : int const n );
348 :
349 : /* fd_ed25519_debug prints the point a, for debugging purposes. */
350 : void
351 : fd_ed25519_debug( char const * name,
352 : fd_ed25519_point_t const * a );
353 :
354 : FD_PROTOTYPES_END
355 :
356 : #endif /* HEADER_fd_src_ballet_ed25519_fd_curve25519_h */
|
