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 1543278 : 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 1543278 : fd_f25519_t x[1], y[1], z[1], t[1];
114 1543278 : fd_ed25519_point_to( x, y, z, t, a );
115 1543278 : return fd_f25519_is_zero( x ) | fd_f25519_is_zero( y )
116 1543278 : | fd_f25519_eq( y, fd_ed25519_order8_point_y0 )
117 1543278 : | fd_f25519_eq( y, fd_ed25519_order8_point_y1 );
118 1543278 : }
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 381 : fd_ed25519_point_validate(uchar const buf[ 32 ] ) {
201 381 : fd_ed25519_point_t t[1];
202 381 : return !!fd_ed25519_point_frombytes( t, buf );
203 381 : }
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_affine_tobytes serializes a point a into
214 : a 32-byte buffer out, and returns out.
215 : out is in little endian form, according to RFC 8032.
216 : a is an affine point, i.e. a->Z == 1; compared to
217 : fd_ed25519_point_tobytes, this function doesn't require inv. */
218 : FD_25519_INLINE uchar *
219 : fd_ed25519_affine_tobytes( uchar out[ 32 ],
220 0 : fd_ed25519_point_t const * a ) {
221 0 : fd_f25519_t x[1], y[1], z[1], t[1];
222 0 : fd_ed25519_point_to( x, y, z, t, a );
223 0 : fd_f25519_tobytes( out, y );
224 0 : out[31] ^= (uchar)(fd_f25519_sgn( x ) << 7);
225 0 : return out;
226 0 : }
227 :
228 : /* fd_curve25519_into_precomputed transforms a point into
229 : precomputed table format, e.g. replaces T -> kT to save
230 : 1mul in the dbl-and-add loop. */
231 : void
232 : fd_curve25519_into_precomputed( fd_ed25519_point_t * r );
233 :
234 : /*
235 : Affine (only for offline building precomputation tables, can be slow)
236 : */
237 : fd_ed25519_point_t *
238 : fd_curve25519_affine_frombytes( fd_ed25519_point_t * r,
239 : uchar const x[ 32 ],
240 : uchar const y[ 32 ] );
241 :
242 : fd_ed25519_point_t *
243 : fd_curve25519_into_affine( fd_ed25519_point_t * r );
244 :
245 : fd_ed25519_point_t *
246 : fd_curve25519_affine_add( fd_ed25519_point_t * r,
247 : fd_ed25519_point_t const * a,
248 : fd_ed25519_point_t const * b );
249 :
250 : fd_ed25519_point_t *
251 : fd_curve25519_affine_dbln( fd_ed25519_point_t * r,
252 : fd_ed25519_point_t const * a,
253 : int const n );
254 :
255 : /* fd_ed25519_debug prints the point a, for debugging purposes. */
256 : void
257 : fd_ed25519_debug( char const * name,
258 : fd_ed25519_point_t const * a );
259 :
260 : FD_PROTOTYPES_END
261 :
262 : #endif /* HEADER_fd_src_ballet_ed25519_fd_curve25519_h */
|
