Line data Source code
1 : #ifndef HEADER_fd_src_ballet_ed25519_fd_f25519_h
2 : #define HEADER_fd_src_ballet_ed25519_fd_f25519_h
3 :
4 : /* fd_f25519.h provides the public field API for the base field of curve25519.
5 :
6 : Most operations in this API should be assumed to take a variable amount
7 : of time depending on inputs, and thus should not be exposed to secret data.
8 :
9 : Constant-time operations are made explicit. */
10 :
11 : #include "../fd_ballet_base.h"
12 : #include "../../util/rng/fd_rng.h"
13 :
14 : #define FD_25519_INLINE static inline
15 :
16 : /* fd_f25519_t is the type of a field element, i.e. an integer
17 : mod p = 2^255 - 19.
18 : it's internal representation (and alignment) depends on the
19 : backend: ref, avx, avx512. */
20 :
21 : #if FD_HAS_AVX512
22 : #include "avx512/fd_f25519.h"
23 : #else
24 : #include "ref/fd_f25519.h"
25 : #endif
26 :
27 : /* field constants. these are imported from table/fd_f25519_table_{arch}.c.
28 : they are (re)defined here to avoid breaking compilation when the table needs
29 : to be rebuilt. */
30 : static const fd_f25519_t fd_f25519_zero[1];
31 : static const fd_f25519_t fd_f25519_one[1];
32 : static const fd_f25519_t fd_f25519_minus_one[1];
33 : static const fd_f25519_t fd_f25519_two[1];
34 : static const fd_f25519_t fd_f25519_nine[1];
35 : static const fd_f25519_t fd_f25519_k[1];
36 : static const fd_f25519_t fd_f25519_minus_k[1];
37 : static const fd_f25519_t fd_f25519_d[1];
38 : static const fd_f25519_t fd_f25519_sqrtm1[1];
39 : static const fd_f25519_t fd_f25519_invsqrt_a_minus_d[1];
40 : static const fd_f25519_t fd_f25519_one_minus_d_sq[1];
41 : static const fd_f25519_t fd_f25519_d_minus_one_sq[1];
42 : static const fd_f25519_t fd_f25519_sqrt_ad_minus_one[1];
43 :
44 : FD_PROTOTYPES_BEGIN
45 :
46 : /* fd_f25519_mul computes r = a * b, and returns r. */
47 : fd_f25519_t *
48 : fd_f25519_mul( fd_f25519_t * r,
49 : fd_f25519_t const * a,
50 : fd_f25519_t const * b );
51 :
52 : /* fd_f25519_sqr computes r = a^2, and returns r. */
53 : fd_f25519_t *
54 : fd_f25519_sqr( fd_f25519_t * r,
55 : fd_f25519_t const * a );
56 :
57 : /* fd_f25519_add computes r = a + b, and returns r. */
58 : fd_f25519_t *
59 : fd_f25519_add( fd_f25519_t * r,
60 : fd_f25519_t const * a,
61 : fd_f25519_t const * b );
62 :
63 : /* fd_f25519_add computes r = a - b, and returns r. */
64 : fd_f25519_t *
65 : fd_f25519_sub( fd_f25519_t * r,
66 : fd_f25519_t const * a,
67 : fd_f25519_t const * b );
68 :
69 : /* fd_f25519_add_nr computes r = a + b, and returns r.
70 : Note: this does NOT reduce the result mod p.
71 : It can be used before mul, sqr. */
72 : fd_f25519_t *
73 : fd_f25519_add_nr( fd_f25519_t * r,
74 : fd_f25519_t const * a,
75 : fd_f25519_t const * b );
76 :
77 : /* fd_f25519_sub_nr computes r = a - b, and returns r.
78 : Note: this does NOT reduce the result mod p.
79 : It can be used before mul, sqr. */
80 : fd_f25519_t *
81 : fd_f25519_sub_nr( fd_f25519_t * r,
82 : fd_f25519_t const * a,
83 : fd_f25519_t const * b );
84 :
85 : /* fd_f25519_add computes r = -a, and returns r. */
86 : fd_f25519_t *
87 : fd_f25519_neg( fd_f25519_t * r,
88 : fd_f25519_t const * a );
89 :
90 : /* fd_f25519_mul_121666 computes r = a * k, k=121666, and returns r. */
91 : fd_f25519_t *
92 : fd_f25519_mul_121666( fd_f25519_t * r,
93 : fd_f25519_t const * a );
94 :
95 : /* fd_f25519_frombytes deserializes a 32-byte buffer buf into a
96 : fd_f25519_t element r, and returns r.
97 : buf is in little endian form, we accept non-canonical elements
98 : unlike RFC 8032. */
99 : fd_f25519_t *
100 : fd_f25519_frombytes( fd_f25519_t * r,
101 : uchar const buf[ 32 ] );
102 :
103 : /* fd_f25519_tobytes serializes a fd_f25519_t element a into
104 : a 32-byte buffer out, and returns out.
105 : out is in little endian form, according to RFC 8032
106 : (we don't output non-canonical elements). */
107 : uchar *
108 : fd_f25519_tobytes( uchar out[ 32 ],
109 : fd_f25519_t const * a );
110 :
111 : /* fd_f25519_set copies r = a, and returns r. */
112 : fd_f25519_t *
113 : fd_f25519_set( fd_f25519_t * r,
114 : fd_f25519_t const * a );
115 :
116 : /* fd_f25519_is_zero returns 1 if a == 0, 0 otherwise. */
117 : int
118 : fd_f25519_is_zero( fd_f25519_t const * a );
119 :
120 : /* fd_f25519_if sets r = a0 if cond, else r = a1, equivalent to:
121 : r = cond ? a0 : a1.
122 : Note: this is constant time. */
123 : fd_f25519_t *
124 : fd_f25519_if( fd_f25519_t * r,
125 : int const cond, /* 0, 1 */
126 : fd_f25519_t const * a0,
127 : fd_f25519_t const * a1 );
128 :
129 : /* fd_f25519_rng generates a random fd_f25519_t element.
130 : Note: insecure, for tests only. */
131 : fd_f25519_t *
132 : fd_f25519_rng_unsafe( fd_f25519_t * r,
133 : fd_rng_t * rng );
134 :
135 : /*
136 : * Derived
137 : */
138 :
139 : /* fd_f25519_eq returns 1 if a == b, 0 otherwise. */
140 : FD_25519_INLINE int
141 : fd_f25519_eq( fd_f25519_t const * a,
142 9582853 : fd_f25519_t const * b ) {
143 9582853 : fd_f25519_t r[1];
144 9582853 : fd_f25519_sub( r, a, b );
145 9582853 : return fd_f25519_is_zero( r );
146 9582853 : }
147 :
148 : /* fd_f25519_is_nonzero returns 1 (true) if a != 0, 0 if a == 0. */
149 : FD_25519_INLINE int
150 300000 : fd_f25519_is_nonzero( fd_f25519_t const * a ) {
151 300000 : return !fd_f25519_is_zero( a );
152 300000 : }
153 :
154 : /* fd_f25519_sgn returns the sign of a (lsb). */
155 : FD_25519_INLINE int
156 6167687 : fd_f25519_sgn( fd_f25519_t const * a ) {
157 : //TODO: make it faster (unless inlining already optimizes out unnecessary code)
158 6167687 : uchar buf[32];
159 6167687 : fd_f25519_tobytes( buf, a );
160 6167687 : return buf[0] & 1;
161 6167687 : }
162 :
163 : /* fd_f25519_abs sets r = |a|. */
164 : FD_25519_INLINE fd_f25519_t *
165 : fd_f25519_abs( fd_f25519_t * r,
166 2424525 : fd_f25519_t const * a ) {
167 2424525 : fd_f25519_t neg_a[1];
168 2424525 : fd_f25519_neg( neg_a, a );
169 2424525 : return fd_f25519_if( r, fd_f25519_sgn(a), neg_a, a );
170 2424525 : }
171 :
172 : /* fd_f25519_abs sets r = -|a|. */
173 : FD_25519_INLINE fd_f25519_t *
174 : fd_f25519_neg_abs( fd_f25519_t * r,
175 90006 : fd_f25519_t const * a ) {
176 90006 : fd_f25519_t neg_a[1];
177 90006 : fd_f25519_neg( neg_a, a );
178 90006 : return fd_f25519_if( r, fd_f25519_sgn(a), a, neg_a );
179 90006 : }
180 :
181 : /*
182 : * Inv & Sqrt
183 : */
184 :
185 : /* fd_f25519_inv computes r = 1/a, and returns r. */
186 : fd_f25519_t *
187 : fd_f25519_inv( fd_f25519_t * r,
188 : fd_f25519_t const * a );
189 :
190 : /* fd_f25519_pow22523 computes r = a^(2^252-3), and returns r. */
191 : fd_f25519_t *
192 : fd_f25519_pow22523( fd_f25519_t * r,
193 : fd_f25519_t const * a );
194 :
195 : /* fd_f25519_sqrt_ratio computes r = (u * v^3) * (u * v^7)^((p-5)/8),
196 : returns 0 on success, 1 on failure. */
197 : int
198 : fd_f25519_sqrt_ratio( fd_f25519_t * r,
199 : fd_f25519_t const * u,
200 : fd_f25519_t const * v );
201 :
202 : /* fd_f25519_sqrt_ratio computes r = 1/sqrt(v),
203 : returns 0 on success, 1 on failure. */
204 : FD_25519_INLINE int
205 : fd_f25519_inv_sqrt( fd_f25519_t * r,
206 601713 : fd_f25519_t const * v ) {
207 601713 : return fd_f25519_sqrt_ratio( r, fd_f25519_one, v );
208 601713 : }
209 :
210 : /*
211 : * Vectorized
212 : */
213 :
214 : /* fd_f25519_muln computes r_i = a_i * b_i */
215 : void
216 : fd_f25519_mul2( fd_f25519_t * r1, fd_f25519_t const * a1, fd_f25519_t const * b1,
217 : fd_f25519_t * r2, fd_f25519_t const * a2, fd_f25519_t const * b2 );
218 :
219 : void
220 : fd_f25519_mul3( fd_f25519_t * r1, fd_f25519_t const * a1, fd_f25519_t const * b1,
221 : fd_f25519_t * r2, fd_f25519_t const * a2, fd_f25519_t const * b2,
222 : fd_f25519_t * r3, fd_f25519_t const * a3, fd_f25519_t const * b3 );
223 :
224 : void
225 : fd_f25519_mul4( fd_f25519_t * r1, fd_f25519_t const * a1, fd_f25519_t const * b1,
226 : fd_f25519_t * r2, fd_f25519_t const * a2, fd_f25519_t const * b2,
227 : fd_f25519_t * r3, fd_f25519_t const * a3, fd_f25519_t const * b3,
228 : fd_f25519_t * r4, fd_f25519_t const * a4, fd_f25519_t const * b4 );
229 :
230 : /* fd_f25519_sqrn computes r_i = a_i^2 */
231 : void
232 : fd_f25519_sqr2( fd_f25519_t * r1, fd_f25519_t const * a1,
233 : fd_f25519_t * r2, fd_f25519_t const * a2 );
234 :
235 : void
236 : fd_f25519_sqr3( fd_f25519_t * r1, fd_f25519_t const * a1,
237 : fd_f25519_t * r2, fd_f25519_t const * a2,
238 : fd_f25519_t * r3, fd_f25519_t const * a3 );
239 :
240 : void
241 : fd_f25519_sqr4( fd_f25519_t * r1, fd_f25519_t const * a1,
242 : fd_f25519_t * r2, fd_f25519_t const * a2,
243 : fd_f25519_t * r3, fd_f25519_t const * a3,
244 : fd_f25519_t * r4, fd_f25519_t const * a4 );
245 :
246 : /* fd_f25519_pow22523 computes r = a^(2^252-3), and returns r. */
247 : fd_f25519_t *
248 : fd_f25519_pow22523_2( fd_f25519_t * r1, fd_f25519_t const * a1,
249 : fd_f25519_t * r2, fd_f25519_t const * a2 );
250 :
251 : /* fd_f25519_sqrt_ratio computes r = (u * v^3) * (u * v^7)^((p-5)/8),
252 : returns 0 on success, 1 on failure. */
253 : int
254 : fd_f25519_sqrt_ratio2( fd_f25519_t * r1, fd_f25519_t const * u1, fd_f25519_t const * v1,
255 : fd_f25519_t * r2, fd_f25519_t const * u2, fd_f25519_t const * v2 );
256 :
257 : /* fd_f25519_debug prints the element a, for debugging purposes. */
258 : void
259 : fd_f25519_debug( char const * name,
260 : fd_f25519_t const * a );
261 :
262 : FD_PROTOTYPES_END
263 :
264 : #endif /* HEADER_fd_src_ballet_ed25519_fd_f25519_h */
|
