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 14334 : #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 1549977 : 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 1549977 : fd_f25519_t x[1], y[1], z[1], t[1];
114 1549977 : fd_ed25519_point_to( x, y, z, t, a );
115 1549977 : return fd_f25519_is_zero( x ) | fd_f25519_is_zero( y )
116 1549977 : | fd_f25519_eq( y, fd_ed25519_order8_point_y0 )
117 1549977 : | fd_f25519_eq( y, fd_ed25519_order8_point_y1 );
118 1549977 : }
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 3000009 : fd_ed25519_scalar_validate( uchar const n[ 32 ] ) {
138 3000009 : return fd_curve25519_scalar_validate( n );
139 3000009 : }
140 :
141 : /* fd_ed25519_scalar_mul computes r = n * a, and returns r.
142 : n is a scalar. */
143 : fd_ed25519_point_t *
144 : fd_ed25519_scalar_mul( fd_ed25519_point_t * r,
145 : uchar const n[ 32 ],
146 : fd_ed25519_point_t const * a );
147 :
148 : /* fd_ed25519_scalar_mul_base_const_time computes r = n * P, and returns r.
149 : n is a scalar. P is the base point.
150 : Note: const time implementation, safe to use with n secret. */
151 : fd_ed25519_point_t * FD_FN_SENSITIVE
152 : fd_ed25519_scalar_mul_base_const_time( fd_ed25519_point_t * r,
153 : uchar const n[ 32 ] ); /* can be a secret */
154 :
155 : /* fd_ed25519_scalar_mul computes r = n1 * a + n2 * P, and returns r.
156 : n1, n2 are scalars. P is the base point. */
157 : fd_ed25519_point_t *
158 : fd_ed25519_double_scalar_mul_base( fd_ed25519_point_t * r,
159 : uchar const n1[ 32 ],
160 : fd_ed25519_point_t const * a,
161 : uchar const n2[ 32 ] );
162 :
163 : /* fd_ed25519_multi_scalar_mul computes r = n0 * a0 + n1 * a1 + ..., and returns r.
164 : n is a vector of sz scalars. a is a vector of sz points. */
165 : fd_ed25519_point_t *
166 : fd_ed25519_multi_scalar_mul( fd_ed25519_point_t * r,
167 : uchar const n[], /* sz * 32 */
168 : fd_ed25519_point_t const a[], /* sz */
169 : ulong const sz );
170 :
171 : /* fd_ed25519_multi_scalar_mul computes r = n0 * B + n1 * a1 + ..., and returns r.
172 : n is a vector of sz scalars. a is a vector of sz points.
173 : the first point is ignored, and the base point is used instead. */
174 : fd_ed25519_point_t *
175 : fd_ed25519_multi_scalar_mul_base( fd_ed25519_point_t * r,
176 : uchar const n[], /* sz * 32 */
177 : fd_ed25519_point_t const a[], /* sz */
178 : ulong const sz );
179 :
180 : /* fd_ed25519_point_frombytes deserializes a 32-byte buffer buf into a
181 : point r, and returns r (on success, NULL on error).
182 : buf is in little endian form, according to RFC 8032.
183 : Cost: 1sqrt ~= 1inv ~= 250mul */
184 : fd_ed25519_point_t *
185 : fd_ed25519_point_frombytes( fd_ed25519_point_t * r,
186 : uchar const buf[ 32 ] );
187 :
188 : /* fd_ed25519_point_frombytes_2x deserializes 2x 32-byte buffers buf1, buf2
189 : resp. into points r1, r2, and returns r.
190 : buf1, buf2 are in little endian form, according to RFC 8032.
191 : It returns 0 on success, 1 or 2 on failure.
192 : Cost: 2sqrt (executed concurrently if possible) */
193 : int
194 : fd_ed25519_point_frombytes_2x( fd_ed25519_point_t * r1,
195 : uchar const buf1[ 32 ],
196 : fd_ed25519_point_t * r2,
197 : uchar const buf2[ 32 ] );
198 :
199 : /* fd_ed25519_point_validate checks if buf represents a valid compressed point,
200 : by attempting to decompress it.
201 : Use fd_ed25519_point_frombytes if the decompressed point is needed.
202 : It returns 1 if buf represents a valid point, 0 if not. */
203 : FD_25519_INLINE int
204 1353 : fd_ed25519_point_validate(uchar const buf[ 32 ] ) {
205 1353 : fd_ed25519_point_t t[1];
206 1353 : return !!fd_ed25519_point_frombytes( t, buf );
207 1353 : }
208 :
209 : /* fd_ed25519_point_tobytes serializes a point a into
210 : a 32-byte buffer out, and returns out.
211 : out is in little endian form, according to RFC 8032. */
212 : uchar *
213 : fd_ed25519_point_tobytes( uchar out[ 32 ],
214 : fd_ed25519_point_t const * a );
215 :
216 : /* fd_ed25519_affine_tobytes serializes a point a into
217 : a 32-byte buffer out, and returns out.
218 : out is in little endian form, according to RFC 8032.
219 : a is an affine point, i.e. a->Z == 1; compared to
220 : fd_ed25519_point_tobytes, this function doesn't require inv. */
221 : FD_25519_INLINE uchar *
222 : fd_ed25519_affine_tobytes( uchar out[ 32 ],
223 0 : fd_ed25519_point_t const * a ) {
224 0 : fd_f25519_t x[1], y[1], z[1], t[1];
225 0 : fd_ed25519_point_to( x, y, z, t, a );
226 0 : fd_f25519_tobytes( out, y );
227 0 : out[31] ^= (uchar)(fd_f25519_sgn( x ) << 7);
228 0 : return out;
229 0 : }
230 :
231 : /* fd_curve25519_into_precomputed transforms a point into
232 : precomputed table format, e.g. replaces T -> kT to save
233 : 1mul in the dbl-and-add loop. */
234 : void
235 : fd_curve25519_into_precomputed( fd_ed25519_point_t * r );
236 :
237 : /*
238 : Affine (only for offline building precomputation tables, can be slow)
239 : */
240 : fd_ed25519_point_t *
241 : fd_curve25519_affine_frombytes( fd_ed25519_point_t * r,
242 : uchar const x[ 32 ],
243 : uchar const y[ 32 ] );
244 :
245 : fd_ed25519_point_t *
246 : fd_curve25519_into_affine( fd_ed25519_point_t * r );
247 :
248 : fd_ed25519_point_t *
249 : fd_curve25519_affine_add( fd_ed25519_point_t * r,
250 : fd_ed25519_point_t const * a,
251 : fd_ed25519_point_t const * b );
252 :
253 : fd_ed25519_point_t *
254 : fd_curve25519_affine_dbln( fd_ed25519_point_t * r,
255 : fd_ed25519_point_t const * a,
256 : int const n );
257 :
258 : FD_PROTOTYPES_END
259 :
260 : #endif /* HEADER_fd_src_ballet_ed25519_fd_curve25519_h */
|
