Line data Source code
1 : #include <stdint.h>
2 : #include "../../third_party/s2n-bignum/include/s2n-bignum.h"
3 : #include "../../util/sanitize/fd_msan.h"
4 :
5 : /* On CPUs without ADX (mulx/adcx/adox), redirect the ADX-optimized
6 : s2n-bignum symbols to their _alt equivalents, which use only base
7 : x86-64 instructions and are functionally identical. */
8 : #ifndef __ADX__
9 62402808 : #define bignum_montmul_p256k1 bignum_montmul_p256k1_alt
10 20795400 : #define bignum_montsqr_p256k1 bignum_montsqr_p256k1_alt
11 60102 : #define bignum_tomont_p256k1 bignum_tomont_p256k1_alt
12 2504882 : #define bignum_triple_p256k1 bignum_triple_p256k1_alt
13 : #endif
14 :
15 : /* Scalars */
16 :
17 : static inline int
18 120213 : fd_secp256k1_scalar_is_zero( fd_secp256k1_scalar_t const *r ) {
19 120213 : return fd_uint256_eq( r, fd_secp256k1_const_zero );
20 120213 : }
21 :
22 : /* Returns the scalar in NON Montgomery form. */
23 : static inline fd_secp256k1_scalar_t *
24 : fd_secp256k1_scalar_frombytes( fd_secp256k1_scalar_t * r,
25 120231 : uchar const input[ 32 ] ) {
26 120231 : memcpy( r, input, 32 );
27 120231 : fd_uint256_bswap( r, r );
28 :
29 : /*
30 : The verifier SHALL check that 0 < r' < q and 0 < s' < q.
31 : The r' element is parsed as a scalar, and checked against r' < n.
32 : Later it is re-used as fp_t, however n < p, so we do not need to
33 : perform any additional checks after this.
34 : */
35 120231 : if( FD_UNLIKELY( fd_uint256_cmp( r, fd_secp256k1_const_n ) >= 0 ) ) {
36 18 : return NULL;
37 18 : }
38 120213 : if( FD_UNLIKELY( fd_secp256k1_scalar_is_zero( r ) ) ) {
39 15 : return NULL;
40 15 : }
41 120198 : return r;
42 120213 : }
43 :
44 : /* r = 1 / a
45 : Operates on scalars NOT in the montgomery domain.
46 : a MUST not be 0. */
47 : fd_secp256k1_scalar_t *
48 : fd_secp256k1_scalar_invert( fd_secp256k1_scalar_t * r,
49 30060 : fd_secp256k1_scalar_t const * a ) {
50 30060 : ulong t[ 12 ];
51 30060 : bignum_modinv( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256k1_const_n[ 0 ].limbs, t );
52 30060 : fd_msan_unpoison( r->limbs, 32UL );
53 30060 : return r;
54 30060 : }
55 :
56 : /* None of the arguments may alias. */
57 : static inline fd_secp256k1_scalar_t *
58 : fd_secp256k1_scalar_mul( fd_secp256k1_scalar_t * restrict r,
59 : fd_secp256k1_scalar_t const * restrict a,
60 60120 : fd_secp256k1_scalar_t const * restrict b ) {
61 60120 : bignum_montmul( 4, r->limbs, (ulong *)a->limbs, (ulong *)b->limbs, (ulong *)fd_secp256k1_const_n[0].limbs );
62 60120 : fd_msan_unpoison( r->limbs, 32UL );
63 60120 : return r;
64 60120 : }
65 :
66 : /* r = -a */
67 : static inline fd_secp256k1_scalar_t *
68 : fd_secp256k1_scalar_negate( fd_secp256k1_scalar_t * r,
69 30060 : fd_secp256k1_scalar_t const * a ) {
70 : /* We cannot use bignum_modsub() as it requires a < n /\ b < n.
71 :
72 : The best way to implement it using the current API is to use
73 : bignum_sub(n, a), getting a result bounded within [0, n+1). Then
74 : we perform a second reduction from [0, n+1) to [0, n) with
75 : bignum_mod_n256k1_4(). */
76 :
77 : /* t \in [0, n + 1). There is no carry-out, as a < n. */
78 30060 : ulong t[4];
79 30060 : bignum_sub( 4, t, 4, (ulong *)fd_secp256k1_const_n[ 0 ].limbs, 4, (ulong *)a->limbs );
80 30060 : fd_msan_unpoison( t, 32UL );
81 30060 : bignum_mod_n256k1_4( r->limbs, t );
82 30060 : fd_msan_unpoison( r->limbs, 32UL );
83 30060 : return r;
84 30060 : }
85 :
86 : static inline fd_secp256k1_scalar_t *
87 : fd_secp256k1_scalar_tomont( fd_secp256k1_scalar_t * r,
88 90180 : fd_secp256k1_scalar_t const * a ) {
89 : /* bignum_montmul has an undocumented restriction
90 : that the input and outputs may not alias. */
91 90180 : ulong t[4];
92 90180 : memcpy( t, a->limbs, 32 );
93 90180 : bignum_montmul( 4, r->limbs, t, (ulong *)fd_secp256k1_const_scalar_rr_mont, (ulong *)fd_secp256k1_const_n[ 0 ].limbs );
94 90180 : fd_msan_unpoison( r->limbs, 32UL );
95 90180 : return r;
96 90180 : }
97 :
98 : static inline fd_secp256k1_scalar_t *
99 : fd_secp256k1_scalar_demont( fd_secp256k1_scalar_t * r,
100 60120 : fd_secp256k1_scalar_t const * a ) {
101 60120 : bignum_demont( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256k1_const_n[ 0 ].limbs );
102 60120 : fd_msan_unpoison( r->limbs, 32UL );
103 60120 : return r;
104 60120 : }
105 :
106 : /* r = a mod n, where a < 2^256 < 2n. NOT Montgomery. */
107 : static inline fd_secp256k1_scalar_t *
108 : fd_secp256k1_scalar_reduce( fd_secp256k1_scalar_t * r,
109 30060 : fd_secp256k1_scalar_t const * a ) {
110 30060 : bignum_mod_n256k1_4( r->limbs, (ulong *)a->limbs );
111 30060 : fd_msan_unpoison( r->limbs, 32UL );
112 30060 : return r;
113 30060 : }
114 :
115 : /* Field */
116 :
117 : static inline fd_secp256k1_fp_t *
118 : fd_secp256k1_fp_set( fd_secp256k1_fp_t * r,
119 4687968 : fd_secp256k1_fp_t const * a ) {
120 4687968 : r->limbs[ 0 ] = a->limbs[ 0 ];
121 4687968 : r->limbs[ 1 ] = a->limbs[ 1 ];
122 4687968 : r->limbs[ 2 ] = a->limbs[ 2 ];
123 4687968 : r->limbs[ 3 ] = a->limbs[ 3 ];
124 4687968 : return r;
125 4687968 : }
126 :
127 : /* r = (a == b) */
128 : static inline int
129 : fd_secp256k1_fp_eq( fd_secp256k1_fp_t const * a,
130 180324 : fd_secp256k1_fp_t const * b ) {
131 180324 : return fd_uint256_eq( a, b );
132 180324 : }
133 :
134 : /* r = a + b */
135 : static inline fd_secp256k1_fp_t *
136 : fd_secp256k1_fp_add( fd_secp256k1_fp_t * r,
137 : fd_secp256k1_fp_t const * a,
138 99856464 : fd_secp256k1_fp_t const * b ) {
139 99856464 : bignum_add_p256k1( r->limbs, (ulong *)a->limbs, (ulong *)b->limbs );
140 99856464 : fd_msan_unpoison( r->limbs, 32UL );
141 99856464 : return r;
142 99856464 : }
143 :
144 : /* r = a - b */
145 : static inline fd_secp256k1_fp_t *
146 : fd_secp256k1_fp_sub( fd_secp256k1_fp_t * r,
147 : fd_secp256k1_fp_t const * a,
148 26722455 : fd_secp256k1_fp_t const * b ) {
149 26722455 : bignum_sub_p256k1( r->limbs, (ulong *)a->limbs, (ulong *)b->limbs );
150 26722455 : fd_msan_unpoison( r->limbs, 32UL );
151 26722455 : return r;
152 26722455 : }
153 :
154 : /* r = 2 * a */
155 : static inline fd_secp256k1_fp_t *
156 : fd_secp256k1_fp_dbl( fd_secp256k1_fp_t * r,
157 101481144 : fd_secp256k1_fp_t const * a ) {
158 101481144 : bignum_double_p256k1( r->limbs, (ulong *)a->limbs );
159 101481144 : fd_msan_unpoison( r->limbs, 32UL );
160 101481144 : return r;
161 101481144 : }
162 :
163 : /* r = a * b */
164 : static inline fd_secp256k1_fp_t *
165 : fd_secp256k1_fp_mul( fd_secp256k1_fp_t * r,
166 : fd_secp256k1_fp_t const * a,
167 93604212 : fd_secp256k1_fp_t const * b ) {
168 93604212 : bignum_montmul_p256k1( r->limbs, (ulong *)a->limbs, (ulong *)b->limbs );
169 93604212 : fd_msan_unpoison( r->limbs, 32UL );
170 93604212 : return r;
171 93604212 : }
172 :
173 : /* r = a^2 */
174 : static inline fd_secp256k1_fp_t *
175 : fd_secp256k1_fp_sqr( fd_secp256k1_fp_t * r,
176 31193100 : fd_secp256k1_fp_t const * a ) {
177 31193100 : bignum_montsqr_p256k1( r->limbs, (ulong *)a->limbs );
178 31193100 : fd_msan_unpoison( r->limbs, 32UL );
179 31193100 : return r;
180 31193100 : }
181 :
182 : /* r = -a */
183 : static inline fd_secp256k1_fp_t *
184 : fd_secp256k1_fp_negate( fd_secp256k1_fp_t * r,
185 2043414 : fd_secp256k1_fp_t const * a ) {
186 2043414 : bignum_neg_p256k1( r->limbs, (ulong *)a->limbs );
187 2043414 : fd_msan_unpoison( r->limbs, 32UL );
188 2043414 : return r;
189 2043414 : }
190 :
191 : static inline int
192 30060 : fd_secp256k1_fp_is_odd( fd_secp256k1_fp_t const *r ) {
193 30060 : fd_secp256k1_fp_t scratch[1];
194 30060 : bignum_demont_p256k1( scratch->limbs, (ulong *)r->limbs );
195 30060 : fd_msan_unpoison( scratch->limbs, 32UL );
196 30060 : return scratch->limbs[ 0 ] & 1;
197 30060 : }
198 :
199 : /* r = 1 / a
200 : a MUST not be 0. */
201 : static inline fd_secp256k1_fp_t *
202 : fd_secp256k1_fp_invert( fd_secp256k1_fp_t * r,
203 30060 : fd_secp256k1_fp_t const * a ) {
204 30060 : fd_secp256k1_fp_t ad[1];
205 30060 : bignum_demont_p256k1( ad->limbs, (ulong *)a->limbs );
206 30060 : fd_msan_unpoison( ad->limbs, 32UL );
207 30060 : ulong t[ 12 ];
208 30060 : bignum_modinv( 4, r->limbs, (ulong *)ad->limbs, (ulong *)fd_secp256k1_const_p[0].limbs, t );
209 30060 : fd_msan_unpoison( r->limbs, 32UL );
210 30060 : bignum_tomont_p256k1( r->limbs, (ulong *)r->limbs );
211 30060 : fd_msan_unpoison( r->limbs, 32UL );
212 30060 : return r;
213 30060 : }
214 :
215 : static inline uchar *
216 : fd_secp256k1_fp_tobytes( uchar r[ 32 ],
217 60120 : fd_secp256k1_fp_t const *a ) {
218 60120 : fd_secp256k1_fp_t swapped[1];
219 60120 : bignum_demont_p256k1( swapped->limbs, (ulong *)a->limbs );
220 60120 : fd_msan_unpoison( swapped->limbs, 32UL );
221 60120 : fd_uint256_bswap( swapped, swapped );
222 60120 : memcpy( r, swapped->buf, 32 );
223 60120 : return r;
224 60120 : }
225 :
226 : /* r = 3 * a */
227 : static inline fd_secp256k1_fp_t *
228 : fd_secp256k1_fp_triple( fd_secp256k1_fp_t * r,
229 3757323 : fd_secp256k1_fp_t const * a ) {
230 3757323 : bignum_triple_p256k1( r->limbs, (ulong *)a->limbs );
231 3757323 : fd_msan_unpoison( r->limbs, 32UL );
232 3757323 : return r;
233 3757323 : }
234 :
235 : /* r = a * R, i.e. converts a plain residue into the Montgomery domain. */
236 : static inline fd_secp256k1_fp_t *
237 : fd_secp256k1_fp_tomont( fd_secp256k1_fp_t * r,
238 60093 : fd_secp256k1_fp_t const * a ) {
239 60093 : bignum_tomont_p256k1( r->limbs, (ulong *)a->limbs );
240 60093 : fd_msan_unpoison( r->limbs, 32UL );
241 60093 : return r;
242 60093 : }
|
