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 11130 : #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 52536 : 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 52536 : fd_f25519_t x[1], y[1], z[1], t[1];
114 52536 : fd_ed25519_point_to( x, y, z, t, a );
115 52536 : return fd_f25519_is_zero( x ) | fd_f25519_is_zero( y )
116 52536 : | fd_f25519_eq( y, fd_ed25519_order8_point_y0 )
117 52536 : | fd_f25519_eq( y, fd_ed25519_order8_point_y1 );
118 52536 : }
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 3000012 : fd_ed25519_scalar_validate( uchar const n[ 32 ] ) {
138 3000012 : return fd_curve25519_scalar_validate( n );
139 3000012 : }
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 : /* fd_ed25519_multi_scalar_mul computes r = n0 * a0 + n1 * a1 + ..., and returns r.
166 : n is a vector of sz scalars. a is a vector of sz points.
167 : Precondition: all points in a[] must be affine (Z==1), e.g. from
168 : fd_ed25519_point_frombytes. Passing projective points (Z!=1) will
169 : produce silently wrong results. */
170 : fd_ed25519_point_t *
171 : fd_ed25519_multi_scalar_mul( fd_ed25519_point_t * r,
172 : uchar const n[], /* sz * 32 */
173 : fd_ed25519_point_t const a[], /* sz */
174 : ulong const sz );
175 :
176 : /* fd_ed25519_point_frombytes deserializes a 32-byte buffer buf into a
177 : point r, and returns r (on success, NULL on error).
178 : buf is in little endian form, we accept non-canonical points unlike RFC 8032.
179 : Cost: 1sqrt ~= 1inv ~= 250mul */
180 : fd_ed25519_point_t *
181 : fd_ed25519_point_frombytes( fd_ed25519_point_t * r,
182 : uchar const buf[ 32 ] );
183 :
184 : /* fd_ed25519_point_frombytes_2x deserializes 2x 32-byte buffers buf1, buf2
185 : resp. into points r1, r2, and returns r.
186 : buf1, buf2 are in little endian form, we accept non-canonical points unlike RFC 8032.
187 : It returns 0 on success, -1 or -2 on failure.
188 : Cost: 2sqrt (executed concurrently if possible) */
189 : int
190 : fd_ed25519_point_frombytes_2x( fd_ed25519_point_t * r1,
191 : uchar const buf1[ 32 ],
192 : fd_ed25519_point_t * r2,
193 : uchar const buf2[ 32 ] );
194 :
195 : /* fd_ed25519_point_validate checks if buf represents a valid compressed point,
196 : by attempting to decompress it.
197 : Use fd_ed25519_point_frombytes if the decompressed point is needed.
198 : It returns 1 if buf represents a valid point, 0 if not. */
199 : FD_25519_INLINE int
200 798 : fd_ed25519_point_validate(uchar const buf[ 32 ] ) {
201 798 : fd_ed25519_point_t t[1];
202 798 : return !!fd_ed25519_point_frombytes( t, buf );
203 798 : }
204 :
205 : /* fd_ed25519_point_tobytes serializes a point a into
206 : a 32-byte buffer out, and returns out.
207 : out is in little endian form, according to RFC 8032
208 : (we don't output non-canonical points). */
209 : uchar *
210 : fd_ed25519_point_tobytes( uchar out[ 32 ],
211 : fd_ed25519_point_t const * a );
212 :
213 : /* fd_ed25519_point_tobytes_batch8 serializes n points pt[0..n), n in
214 : [1,8], into out (32 bytes each, point i at out+32*i), sharing one
215 : field inversion across the n points. n is asserted to be in
216 : [1,8]. Returns out. */
217 : uchar *
218 : fd_ed25519_point_tobytes_batch8( uchar out[], /* 32*n */
219 : fd_ed25519_point_t const * pt, /* n */
220 : ulong n );
221 :
222 : /* fd_ed25519_affine_tobytes serializes a point a into
223 : a 32-byte buffer out, and returns out.
224 : out is in little endian form, according to RFC 8032.
225 : a is an affine point, i.e. a->Z == 1; compared to
226 : fd_ed25519_point_tobytes, this function doesn't require inv. */
227 : FD_25519_INLINE uchar *
228 : fd_ed25519_affine_tobytes( uchar out[ 32 ],
229 0 : fd_ed25519_point_t const * a ) {
230 0 : fd_f25519_t x[1], y[1], z[1], t[1];
231 0 : fd_ed25519_point_to( x, y, z, t, a );
232 0 : fd_f25519_tobytes( out, y );
233 0 : out[31] ^= (uchar)(fd_f25519_sgn( x ) << 7);
234 0 : return out;
235 0 : }
236 :
237 : /* fd_curve25519_into_precomputed transforms a point into
238 : precomputed table format, e.g. replaces T -> kT to save
239 : 1mul in the dbl-and-add loop. */
240 : void
241 : fd_curve25519_into_precomputed( fd_ed25519_point_t * r );
242 :
243 : /*
244 : Affine (only for offline building precomputation tables, can be slow)
245 : */
246 : fd_ed25519_point_t *
247 : fd_curve25519_affine_frombytes( fd_ed25519_point_t * r,
248 : uchar const x[ 32 ],
249 : uchar const y[ 32 ] );
250 :
251 : fd_ed25519_point_t *
252 : fd_curve25519_into_affine( fd_ed25519_point_t * r );
253 :
254 : fd_ed25519_point_t *
255 : fd_curve25519_affine_add( fd_ed25519_point_t * r,
256 : fd_ed25519_point_t const * a,
257 : fd_ed25519_point_t const * b );
258 :
259 : fd_ed25519_point_t *
260 : fd_curve25519_affine_dbln( fd_ed25519_point_t * r,
261 : fd_ed25519_point_t const * a,
262 : int const n );
263 :
264 : /* fd_ed25519_debug prints the point a, for debugging purposes. */
265 : void
266 : fd_ed25519_debug( char const * name,
267 : fd_ed25519_point_t const * a );
268 :
269 : FD_PROTOTYPES_END
270 :
271 : #endif /* HEADER_fd_src_ballet_ed25519_fd_curve25519_h */
|
