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, according to RFC 8032. */
98 : fd_f25519_t *
99 : fd_f25519_frombytes( fd_f25519_t * r,
100 : uchar const buf[ 32 ] );
101 :
102 : /* fd_f25519_tobytes serializes a fd_f25519_t element a into
103 : a 32-byte buffer out, and returns out.
104 : out is in little endian form, according to RFC 8032. */
105 : uchar *
106 : fd_f25519_tobytes( uchar out[ 32 ],
107 : fd_f25519_t const * a );
108 :
109 : /* fd_f25519_set copies r = a, and returns r. */
110 : fd_f25519_t *
111 : fd_f25519_set( fd_f25519_t * r,
112 : fd_f25519_t const * a );
113 :
114 : /* fd_f25519_is_zero returns 1 if a == 0, 0 otherwise. */
115 : int
116 : fd_f25519_is_zero( fd_f25519_t const * a );
117 :
118 : /* fd_f25519_if sets r = a0 if cond, else r = a1, equivalent to:
119 : r = cond ? a0 : a1.
120 : Note: this is constant time. */
121 : fd_f25519_t *
122 : fd_f25519_if( fd_f25519_t * r,
123 : int const cond, /* 0, 1 */
124 : fd_f25519_t const * a0,
125 : fd_f25519_t const * a1 );
126 :
127 : /* fd_f25519_rng generates a random fd_f25519_t element.
128 : Note: insecure, for tests only. */
129 : fd_f25519_t *
130 : fd_f25519_rng_unsafe( fd_f25519_t * r,
131 : fd_rng_t * rng );
132 :
133 : /*
134 : * Derived
135 : */
136 :
137 : /* fd_f25519_eq returns 1 if a == b, 0 otherwise. */
138 : FD_25519_INLINE int
139 : fd_f25519_eq( fd_f25519_t const * a,
140 9641186 : fd_f25519_t const * b ) {
141 9641186 : fd_f25519_t r[1];
142 9641186 : fd_f25519_sub( r, a, b );
143 9641186 : return fd_f25519_is_zero( r );
144 9641186 : }
145 :
146 : /* fd_f25519_is_nonzero returns 1 (true) if a != 0, 0 if a == 0. */
147 : FD_25519_INLINE int
148 300000 : fd_f25519_is_nonzero( fd_f25519_t const * a ) {
149 300000 : return !fd_f25519_is_zero( a );
150 300000 : }
151 :
152 : /* fd_f25519_sgn returns the sign of a (lsb). */
153 : FD_25519_INLINE int
154 6250784 : fd_f25519_sgn( fd_f25519_t const * a ) {
155 : //TODO: make it faster (unless inlining already optimizes out unnecessary code)
156 6250784 : uchar buf[32];
157 6250784 : fd_f25519_tobytes( buf, a );
158 6250784 : return buf[0] & 1;
159 6250784 : }
160 :
161 : /* fd_f25519_abs sets r = |a|. */
162 : FD_25519_INLINE fd_f25519_t *
163 : fd_f25519_abs( fd_f25519_t * r,
164 2444283 : fd_f25519_t const * a ) {
165 2444283 : fd_f25519_t neg_a[1];
166 2444283 : fd_f25519_neg( neg_a, a );
167 2444283 : return fd_f25519_if( r, fd_f25519_sgn(a), neg_a, a );
168 2444283 : }
169 :
170 : /* fd_f25519_abs sets r = -|a|. */
171 : FD_25519_INLINE fd_f25519_t *
172 : fd_f25519_neg_abs( fd_f25519_t * r,
173 90006 : fd_f25519_t const * a ) {
174 90006 : fd_f25519_t neg_a[1];
175 90006 : fd_f25519_neg( neg_a, a );
176 90006 : return fd_f25519_if( r, fd_f25519_sgn(a), a, neg_a );
177 90006 : }
178 :
179 : /*
180 : * Inv & Sqrt
181 : */
182 :
183 : /* fd_f25519_inv computes r = 1/a, and returns r. */
184 : fd_f25519_t *
185 : fd_f25519_inv( fd_f25519_t * r,
186 : fd_f25519_t const * a );
187 :
188 : /* fd_f25519_pow22523 computes r = a^(2^252-3), and returns r. */
189 : fd_f25519_t *
190 : fd_f25519_pow22523( fd_f25519_t * r,
191 : fd_f25519_t const * a );
192 :
193 : /* fd_f25519_sqrt_ratio computes r = (u * v^3) * (u * v^7)^((p-5)/8),
194 : returns 0 on success, 1 on failure. */
195 : int
196 : fd_f25519_sqrt_ratio( fd_f25519_t * r,
197 : fd_f25519_t const * u,
198 : fd_f25519_t const * v );
199 :
200 : /* fd_f25519_sqrt_ratio computes r = 1/sqrt(v),
201 : returns 0 on success, 1 on failure. */
202 : FD_25519_INLINE int
203 : fd_f25519_inv_sqrt( fd_f25519_t * r,
204 608016 : fd_f25519_t const * v ) {
205 608016 : return fd_f25519_sqrt_ratio( r, fd_f25519_one, v );
206 608016 : }
207 :
208 : /*
209 : * Vectorized
210 : */
211 :
212 : /* fd_f25519_muln computes r_i = a_i * b_i */
213 : void
214 : fd_f25519_mul2( fd_f25519_t * r1, fd_f25519_t const * a1, fd_f25519_t const * b1,
215 : fd_f25519_t * r2, fd_f25519_t const * a2, fd_f25519_t const * b2 );
216 :
217 : void
218 : fd_f25519_mul3( fd_f25519_t * r1, fd_f25519_t const * a1, fd_f25519_t const * b1,
219 : fd_f25519_t * r2, fd_f25519_t const * a2, fd_f25519_t const * b2,
220 : fd_f25519_t * r3, fd_f25519_t const * a3, fd_f25519_t const * b3 );
221 :
222 : void
223 : fd_f25519_mul4( fd_f25519_t * r1, fd_f25519_t const * a1, fd_f25519_t const * b1,
224 : fd_f25519_t * r2, fd_f25519_t const * a2, fd_f25519_t const * b2,
225 : fd_f25519_t * r3, fd_f25519_t const * a3, fd_f25519_t const * b3,
226 : fd_f25519_t * r4, fd_f25519_t const * a4, fd_f25519_t const * b4 );
227 :
228 : /* fd_f25519_sqrn computes r_i = a_i^2 */
229 : void
230 : fd_f25519_sqr2( fd_f25519_t * r1, fd_f25519_t const * a1,
231 : fd_f25519_t * r2, fd_f25519_t const * a2 );
232 :
233 : void
234 : fd_f25519_sqr3( fd_f25519_t * r1, fd_f25519_t const * a1,
235 : fd_f25519_t * r2, fd_f25519_t const * a2,
236 : fd_f25519_t * r3, fd_f25519_t const * a3 );
237 :
238 : void
239 : fd_f25519_sqr4( fd_f25519_t * r1, fd_f25519_t const * a1,
240 : fd_f25519_t * r2, fd_f25519_t const * a2,
241 : fd_f25519_t * r3, fd_f25519_t const * a3,
242 : fd_f25519_t * r4, fd_f25519_t const * a4 );
243 :
244 : /* fd_f25519_pow22523 computes r = a^(2^252-3), and returns r. */
245 : fd_f25519_t *
246 : fd_f25519_pow22523_2( fd_f25519_t * r1, fd_f25519_t const * a1,
247 : fd_f25519_t * r2, fd_f25519_t const * a2 );
248 :
249 : /* fd_f25519_sqrt_ratio computes r = (u * v^3) * (u * v^7)^((p-5)/8),
250 : returns 0 on success, 1 on failure. */
251 : int
252 : fd_f25519_sqrt_ratio2( fd_f25519_t * r1, fd_f25519_t const * u1, fd_f25519_t const * v1,
253 : fd_f25519_t * r2, fd_f25519_t const * u2, fd_f25519_t const * v2 );
254 :
255 : FD_PROTOTYPES_END
256 :
257 : #endif /* HEADER_fd_src_ballet_ed25519_fd_f25519_h */
|
