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 14340 : #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_is_zero returns 1 if a == 0 (point at infinity), 0 otherwise. */
80 : int
81 : fd_ed25519_point_is_zero( fd_ed25519_point_t const * a );
82 :
83 : /* fd_ed25519_affine_is_small_order returns 1 if a has small order (order <= 8), 0 otherwise. */
84 : FD_25519_INLINE int
85 1549971 : fd_ed25519_affine_is_small_order( fd_ed25519_point_t const * a ) {
86 : /* There are 8 points with order <= 8, aka low order:
87 : 0100000000000000000000000000000000000000000000000000000000000000 ( 0 : 1 ) P0: order 1
88 : ecffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff7f ( 0 : -1 ) P1: order 2
89 : 0000000000000000000000000000000000000000000000000000000000000000 ( b0.. : 0 ) P2: order 4
90 : 0000000000000000000000000000000000000000000000000000000000000080 ( 3d.. : 0 ) -P2: order 4
91 : 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc05 ( 4a.. : 26.. ) P3: order 8
92 : 26e8958fc2b227b045c3f489f2ef98f0d5dfac05d3c63339b13802886d53fc85 ( a3.. : 26.. ) -P3: order 8
93 : c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac037a ( 4a.. : c7.. ) P4: order 8
94 : c7176a703d4dd84fba3c0b760d10670f2a2053fa2c39ccc64ec7fd7792ac03fa ( a3.. : c7.. ) -P4: order 8
95 :
96 : We could test:
97 : fd_ed25519_point_t r[1];
98 : fd_ed25519_point_dbln( r, a, 3 );
99 : return fd_ed25519_point_is_zero( r );
100 :
101 : When the point is affine (Z==1), we can simply check:
102 : - X==0
103 : - or, Y==0
104 : - or, Y==2a..., or Y==c7...
105 :
106 : And if the point is not affine, we could do 1 single dbl and check for X==0 or Y==0
107 : (currently not implemented as not needed).
108 : */
109 1549971 : fd_f25519_t x[1], y[1], z[1], t[1];
110 1549971 : fd_ed25519_point_to( x, y, z, t, a );
111 1549971 : return fd_f25519_is_zero( x ) | fd_f25519_is_zero( y )
112 1549971 : | fd_f25519_eq( y, fd_ed25519_order8_point_y0 )
113 1549971 : | fd_f25519_eq( y, fd_ed25519_order8_point_y1 );
114 1549971 : }
115 :
116 : /* fd_ed25519_point_eq returns 1 if a == b, 0 otherwise. */
117 : int
118 : fd_ed25519_point_eq( fd_ed25519_point_t const * a,
119 : fd_ed25519_point_t const * b );
120 :
121 : /* fd_ed25519_point_eq returns 1 if a == b, 0 otherwise.
122 : b is a point with Z==1, e.g. a decompressed point. */
123 : int
124 : fd_ed25519_point_eq_z1( fd_ed25519_point_t const * a,
125 : fd_ed25519_point_t const * b ); /* b.Z == 1, e.g. a decompressed point */
126 :
127 : /* fd_ed25519_scalar_validate is an alias of fd_curve25519_scalar_validate
128 : It checks whether the given Ed25519 scalar n matches the canonical byte
129 : representation. Not constant time and thus should not be exposed to secrets.
130 : Returns s if canonical, NULL otherwise. */
131 :
132 : FD_25519_INLINE uchar const *
133 3000009 : fd_ed25519_scalar_validate( uchar const n[ 32 ] ) {
134 3000009 : return fd_curve25519_scalar_validate( n );
135 3000009 : }
136 :
137 : /* fd_ed25519_scalar_mul computes r = n * a, and returns r.
138 : n is a scalar. */
139 : fd_ed25519_point_t *
140 : fd_ed25519_scalar_mul( fd_ed25519_point_t * r,
141 : uchar const n[ 32 ],
142 : fd_ed25519_point_t const * a );
143 :
144 : /* fd_ed25519_scalar_mul_base_const_time computes r = n * P, and returns r.
145 : n is a scalar. P is the base point.
146 : Note: const time implementation, safe to use with n secret. */
147 : fd_ed25519_point_t * FD_FN_SENSITIVE
148 : fd_ed25519_scalar_mul_base_const_time( fd_ed25519_point_t * r,
149 : uchar const n[ 32 ] ); /* can be a secret */
150 :
151 : /* fd_ed25519_scalar_mul computes r = n1 * a + n2 * P, and returns r.
152 : n1, n2 are scalars. P is the base point. */
153 : fd_ed25519_point_t *
154 : fd_ed25519_double_scalar_mul_base( fd_ed25519_point_t * r,
155 : uchar const n1[ 32 ],
156 : fd_ed25519_point_t const * a,
157 : uchar const n2[ 32 ] );
158 :
159 : /* fd_ed25519_multi_scalar_mul computes r = n0 * a0 + n1 * a1 + ..., and returns r.
160 : n is a vector of sz scalars. a is a vector of sz points. */
161 : fd_ed25519_point_t *
162 : fd_ed25519_multi_scalar_mul( fd_ed25519_point_t * r,
163 : uchar const n[], /* sz * 32 */
164 : fd_ed25519_point_t const a[], /* sz */
165 : ulong const sz );
166 :
167 : /* fd_ed25519_multi_scalar_mul computes r = n0 * B + n1 * a1 + ..., and returns r.
168 : n is a vector of sz scalars. a is a vector of sz points.
169 : the first point is ignored, and the base point is used instead. */
170 : fd_ed25519_point_t *
171 : fd_ed25519_multi_scalar_mul_base( 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, according to 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, according to 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 1242 : fd_ed25519_point_validate(uchar const buf[ 32 ] ) {
201 1242 : fd_ed25519_point_t t[1];
202 1242 : return !!fd_ed25519_point_frombytes( t, buf );
203 1242 : }
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 : uchar *
209 : fd_ed25519_point_tobytes( uchar out[ 32 ],
210 : fd_ed25519_point_t const * a );
211 :
212 : /* fd_ed25519_affine_tobytes serializes a point a into
213 : a 32-byte buffer out, and returns out.
214 : out is in little endian form, according to RFC 8032.
215 : a is an affine point, i.e. a->Z == 1; compared to
216 : fd_ed25519_point_tobytes, this function doesn't require inv. */
217 : FD_25519_INLINE uchar *
218 : fd_ed25519_affine_tobytes( uchar out[ 32 ],
219 0 : fd_ed25519_point_t const * a ) {
220 0 : fd_f25519_t x[1], y[1], z[1], t[1];
221 0 : fd_ed25519_point_to( x, y, z, t, a );
222 0 : fd_f25519_tobytes( out, y );
223 0 : out[31] ^= (uchar)(fd_f25519_sgn( x ) << 7);
224 0 : return out;
225 0 : }
226 :
227 : /* fd_curve25519_into_precomputed transforms a point into
228 : precomputed table format, e.g. replaces T -> kT to save
229 : 1mul in the dbl-and-add loop. */
230 : void
231 : fd_curve25519_into_precomputed( fd_ed25519_point_t * r );
232 :
233 : /*
234 : Affine (only for offline building precomputation tables, can be slow)
235 : */
236 : fd_ed25519_point_t *
237 : fd_curve25519_affine_frombytes( fd_ed25519_point_t * r,
238 : uchar const x[ 32 ],
239 : uchar const y[ 32 ] );
240 :
241 : fd_ed25519_point_t *
242 : fd_curve25519_into_affine( fd_ed25519_point_t * r );
243 :
244 : fd_ed25519_point_t *
245 : fd_curve25519_affine_add( fd_ed25519_point_t * r,
246 : fd_ed25519_point_t const * a,
247 : fd_ed25519_point_t const * b );
248 :
249 : fd_ed25519_point_t *
250 : fd_curve25519_affine_dbln( fd_ed25519_point_t * r,
251 : fd_ed25519_point_t const * a,
252 : int const n );
253 :
254 : FD_PROTOTYPES_END
255 :
256 : #endif /* HEADER_fd_src_ballet_ed25519_fd_curve25519_h */
|
