Line data Source code
1 : #include <stdint.h>
2 : #include "../../third_party/s2n-bignum/include/s2n-bignum.h"
3 :
4 : /* On CPUs without ADX (mulx/adcx/adox), redirect the ADX-optimized
5 : s2n-bignum symbols to their _alt equivalents, which use only base
6 : x86-64 instructions and are functionally identical. */
7 : #ifndef __ADX__
8 : #define bignum_demont_p256 bignum_demont_p256_alt
9 : #define bignum_mod_n256 bignum_mod_n256_alt
10 : #define bignum_montmul_p256 bignum_montmul_p256_alt
11 : #define bignum_montsqr_p256 bignum_montsqr_p256_alt
12 : #define bignum_mul_4_8 bignum_mul_4_8_alt
13 : #define bignum_tomont_p256 bignum_tomont_p256_alt
14 : #define p256_montjdouble p256_montjdouble_alt
15 : #define p256_montjmixadd p256_montjmixadd_alt
16 : #define p256_montjscalarmul p256_montjscalarmul_alt
17 : #define p256_scalarmulbase p256_scalarmulbase_alt
18 : #endif
19 :
20 : #include "fd_secp256r1_table.c"
21 :
22 : /* p256_base_table_size is used for p256_scalarmulbase with a blocksize=6.
23 : B=2^(6-1)=32, there are 43 blocks i with 6*i<=256 (6*42=252<=256), and
24 : 43 * 32 * 8 = 11008 entries.
25 : https://github.com/awslabs/s2n-bignum/blob/9061e8b76522beafa5ca020f3c8d99b23eba4fbc/x86/p256/p256_scalarmulbase.S#L14-L23 */
26 : FD_STATIC_ASSERT( sizeof(fd_secp256r1_base_point_table)==(43UL*32UL*8UL)*sizeof(ulong), p256_base_table_size );
27 :
28 : /* Scalars */
29 :
30 : static inline int
31 14916 : fd_secp256r1_scalar_is_zero( fd_secp256r1_scalar_t const * a ) {
32 14916 : return fd_uint256_eq( a, fd_secp256r1_const_zero );
33 14916 : }
34 :
35 : static inline fd_secp256r1_scalar_t *
36 : fd_secp256r1_scalar_frombytes( fd_secp256r1_scalar_t * r,
37 13093 : uchar const in[ 32 ] ) {
38 13093 : memcpy( r->buf, in, 32 );
39 13093 : fd_uint256_bswap( r, r );
40 13093 : if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n )<0 ) ) {
41 12967 : return r;
42 12967 : };
43 126 : return NULL;
44 13093 : }
45 :
46 : static inline fd_secp256r1_scalar_t *
47 : fd_secp256r1_scalar_frombytes_positive( fd_secp256r1_scalar_t * r,
48 12955 : uchar const in[ 32 ] ) {
49 12955 : memcpy( r->buf, in, 32 );
50 12955 : fd_uint256_bswap( r, r );
51 12955 : if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n_m1_half )<=0 ) ) {
52 7464 : return r;
53 7464 : };
54 5491 : return NULL;
55 12955 : }
56 :
57 : static inline void
58 : fd_secp256r1_scalar_from_digest( fd_secp256r1_scalar_t * r,
59 7295 : uchar const in[ 32 ] ) {
60 7295 : memcpy( r->buf, in, 32 );
61 7295 : fd_uint256_bswap( r, r );
62 7295 : bignum_mod_n256_4( r->limbs, r->limbs );
63 7295 : }
64 :
65 : static inline fd_secp256r1_scalar_t *
66 : fd_secp256r1_scalar_mul( fd_secp256r1_scalar_t * r,
67 : fd_secp256r1_scalar_t const * a,
68 14591 : fd_secp256r1_scalar_t const * b ) {
69 14591 : ulong t[ 8 ];
70 14591 : bignum_mul_4_8( t, (ulong *)a->limbs, (ulong *)b->limbs );
71 14591 : bignum_mod_n256( r->limbs, 8, t );
72 14591 : return r;
73 14591 : }
74 :
75 : static inline fd_secp256r1_scalar_t *
76 : fd_secp256r1_scalar_inv( fd_secp256r1_scalar_t * r,
77 7298 : fd_secp256r1_scalar_t const * a ) {
78 7298 : ulong t[ 12 ];
79 7298 : bignum_modinv( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256r1_const_n[0].limbs, t );
80 7298 : return r;
81 7298 : }
82 :
83 : /* Field */
84 :
85 : static inline fd_secp256r1_fp_t *
86 : fd_secp256r1_fp_set( fd_secp256r1_fp_t * r,
87 14594 : fd_secp256r1_fp_t const * a ) {
88 14594 : r->limbs[0] = a->limbs[0];
89 14594 : r->limbs[1] = a->limbs[1];
90 14594 : r->limbs[2] = a->limbs[2];
91 14594 : r->limbs[3] = a->limbs[3];
92 14594 : return r;
93 14594 : }
94 :
95 : /* r = -a, Montgomery domain */
96 : static inline fd_secp256r1_fp_t *
97 : fd_secp256r1_fp_neg( fd_secp256r1_fp_t * r,
98 0 : fd_secp256r1_fp_t const * a ) {
99 0 : bignum_optneg_p256( r->limbs, 1UL, (ulong *)a->limbs );
100 0 : return r;
101 0 : }
102 :
103 : static inline fd_secp256r1_fp_t *
104 : fd_secp256r1_fp_frombytes( fd_secp256r1_fp_t * r,
105 7365 : uchar const in[ 32 ] ) {
106 7365 : memcpy( r->buf, in, 32 );
107 7365 : fd_uint256_bswap( r, r );
108 7365 : if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_p )<0 ) ) {
109 7363 : return r;
110 7363 : };
111 2 : return NULL;
112 7365 : }
113 :
114 : static inline fd_secp256r1_fp_t *
115 : fd_secp256r1_fp_sqrt( fd_secp256r1_fp_t * r,
116 7365 : fd_secp256r1_fp_t const * a ) {
117 : /* https://github.com/golang/go/blob/master/src/crypto/internal/fips140/nistec/p256.go#L656 */
118 7365 : fd_secp256r1_fp_t _t0[1], _t1[1];
119 7365 : ulong * t0 = _t0->limbs;
120 7365 : ulong * t1 = _t1->limbs;
121 7365 : ulong * x = (ulong *)a->limbs;
122 :
123 7365 : bignum_montsqr_p256( t0, x );
124 7365 : bignum_montmul_p256( t0, t0, x );
125 14732 : bignum_montsqr_p256( t1, t0 ); for( int i=1; i<2; i++ ) bignum_montsqr_p256( t1, t1 );
126 7365 : bignum_montmul_p256( t0, t0, t1);
127 29476 : bignum_montsqr_p256( t1, t0 ); for( int i=1; i<4; i++ ) bignum_montsqr_p256( t1, t1 );
128 7365 : bignum_montmul_p256( t0, t0, t1);
129 58903 : bignum_montsqr_p256( t1, t0 ); for( int i=1; i<8; i++ ) bignum_montsqr_p256( t1, t1 );
130 7365 : bignum_montmul_p256( t0, t0, t1);
131 117632 : bignum_montsqr_p256( t1, t0 ); for( int i=1; i<16; i++ ) bignum_montsqr_p256( t1, t1 );
132 7365 : bignum_montmul_p256( t0, t0, t1);
133 242233 : for( int i=0; i<32; i++ ) bignum_montsqr_p256( t0, t0 );
134 7365 : bignum_montmul_p256( t0, t0, x );
135 709089 : for( int i=0; i<96; i++ ) bignum_montsqr_p256( t0, t0 );
136 7365 : bignum_montmul_p256( t0, t0, x );
137 694275 : for( int i=0; i<94; i++ ) bignum_montsqr_p256( t0, t0 );
138 :
139 7365 : bignum_montsqr_p256( t1, t0 );
140 7365 : if( FD_UNLIKELY( !fd_uint256_eq( _t1, a ) ) ) {
141 73 : return NULL;
142 73 : }
143 :
144 7292 : return fd_secp256r1_fp_set( r, _t0 );
145 7365 : }
146 :
147 : /* Points */
148 :
149 : static inline int
150 0 : fd_secp256r1_point_validate_uncompressed( uchar const in[ 65 ] ) {
151 0 : if( FD_UNLIKELY( in[ 0 ]!=0x04U ) ) return FD_SECP256R1_FAILURE;
152 :
153 0 : fd_secp256r1_fp_t x[1], y[1], lhs[1], rhs[1];
154 0 : if( FD_UNLIKELY( !fd_secp256r1_fp_frombytes( x, in+1 ) ) ) return FD_SECP256R1_FAILURE;
155 0 : if( FD_UNLIKELY( !fd_secp256r1_fp_frombytes( y, in+33 ) ) ) return FD_SECP256R1_FAILURE;
156 :
157 0 : bignum_tomont_p256( x->limbs, x->limbs );
158 0 : bignum_tomont_p256( y->limbs, y->limbs );
159 :
160 : /* Validate y^2 = x^3 + ax + b. */
161 0 : bignum_montsqr_p256( lhs->limbs, y->limbs );
162 0 : bignum_montsqr_p256( rhs->limbs, x->limbs );
163 0 : bignum_add_p256 ( rhs->limbs, rhs->limbs, (ulong *)fd_secp256r1_const_a_mont[0].limbs );
164 0 : bignum_montmul_p256( rhs->limbs, rhs->limbs, x->limbs );
165 0 : bignum_add_p256 ( rhs->limbs, rhs->limbs, (ulong *)fd_secp256r1_const_b_mont[0].limbs );
166 0 : return fd_uint256_eq( lhs, rhs );
167 0 : }
168 :
169 : static inline fd_secp256r1_point_t *
170 : fd_secp256r1_point_frombytes( fd_secp256r1_point_t * r,
171 7369 : uchar const in[ 33 ] ) {
172 7369 : fd_secp256r1_fp_t y2[1], demont_y[1];
173 :
174 7369 : uchar sgn = in[0];
175 7369 : if( FD_UNLIKELY( sgn!=2U && sgn!=3U ) ) {
176 5 : return FD_SECP256R1_FAILURE;
177 5 : }
178 :
179 7364 : if( FD_UNLIKELY( !fd_secp256r1_fp_frombytes( r->x, in+1 ) ) ) {
180 0 : return FD_SECP256R1_FAILURE;
181 0 : }
182 :
183 7364 : bignum_tomont_p256( r->x->limbs, r->x->limbs );
184 :
185 : /* y^2 = x^3 + ax + b */
186 7364 : bignum_montsqr_p256( y2->limbs, r->x->limbs );
187 7364 : bignum_add_p256 ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_a_mont[0].limbs );
188 7364 : bignum_montmul_p256( y2->limbs, y2->limbs, r->x->limbs );
189 7364 : bignum_add_p256 ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_b_mont[0].limbs );
190 :
191 : /* y = sqrt(y^2) */
192 7364 : if( FD_UNLIKELY( !fd_secp256r1_fp_sqrt( r->y, y2 ) ) ) {
193 73 : return FD_SECP256R1_FAILURE;
194 73 : }
195 :
196 : /* choose y or -y */
197 7291 : bignum_demont_p256( demont_y->limbs, r->y->limbs );
198 7291 : ulong cond = (demont_y->limbs[0] % 2) != (sgn == 3U);
199 7291 : bignum_optneg_p256( r->y->limbs, cond, r->y->limbs );
200 :
201 7291 : fd_secp256r1_fp_set( r->z, fd_secp256r1_const_one_mont );
202 :
203 7291 : return r;
204 7364 : }
205 :
206 : static inline int
207 : fd_secp256r1_point_eq_x( fd_secp256r1_point_t const * p,
208 7303 : fd_secp256r1_scalar_t const * r ) {
209 7303 : fd_secp256r1_fp_t affine_x[1];
210 7303 : fd_secp256r1_scalar_t * affine_x_mod_n = affine_x;
211 :
212 7303 : if( FD_UNLIKELY( fd_uint256_eq( p->z, fd_secp256r1_const_zero ) ) ) {
213 22 : return FD_SECP256R1_FAILURE;
214 22 : }
215 :
216 : /* x = demont(X / Z^2) mod n */
217 7281 : bignum_montinv_p256( affine_x->limbs, (ulong *)p->z->limbs );
218 7281 : bignum_montsqr_p256( affine_x->limbs, affine_x->limbs );
219 7281 : bignum_montmul_p256( affine_x->limbs, affine_x->limbs, (ulong *)p->x->limbs );
220 7281 : bignum_demont_p256( affine_x_mod_n->limbs, affine_x->limbs );
221 7281 : bignum_mod_n256_4 ( affine_x_mod_n->limbs, affine_x_mod_n->limbs );
222 :
223 7281 : if( FD_LIKELY( fd_uint256_eq( r, affine_x_mod_n ) ) ) {
224 4641 : return FD_SECP256R1_SUCCESS;
225 4641 : }
226 2640 : return FD_SECP256R1_FAILURE;
227 7281 : }
228 :
229 : /* Given the projective point `r` and the affine point `p`,
230 : returns 1 if they are equal and 0 otherwise.
231 : Assumes that `p` X and Y coordinates are in Montgomery domain. */
232 : static inline int
233 : fd_secp256r1_point_eq_mixed( fd_secp256r1_point_t const * a,
234 7299 : ulong const b[ 8 ] ) {
235 7299 : fd_secp256r1_fp_t x[1], y[1];
236 7299 : fd_memcpy( x->limbs, b+0, sizeof(fd_secp256r1_fp_t) );
237 7299 : fd_memcpy( y->limbs, b+4, sizeof(fd_secp256r1_fp_t) );
238 : /* Indicates if the affine point is zero. */
239 7299 : int is_zero = fd_uint256_eq( x, fd_secp256r1_const_zero ) & fd_uint256_eq( y, fd_secp256r1_const_zero );
240 :
241 : /* Easy cases */
242 7299 : if( FD_UNLIKELY( fd_uint256_eq( a->z, fd_secp256r1_const_zero ) ) ) {
243 0 : return is_zero;
244 0 : }
245 7299 : if( FD_UNLIKELY( is_zero ) ) {
246 0 : return 0;
247 0 : }
248 :
249 7299 : fd_secp256r1_fp_t z1z1[1];
250 7299 : bignum_montsqr_p256( z1z1->limbs, (ulong *)a->z->limbs );
251 :
252 7299 : fd_secp256r1_fp_t temp[1];
253 7299 : bignum_montmul_p256( temp->limbs, (ulong *)x->limbs, z1z1->limbs );
254 :
255 7299 : if( FD_UNLIKELY( fd_uint256_eq( a->x, temp ) ) ) {
256 35 : bignum_montmul_p256( temp->limbs, z1z1->limbs, (ulong *)a->z->limbs );
257 35 : bignum_montmul_p256( temp->limbs, temp->limbs, (ulong *)y->limbs );
258 35 : return fd_uint256_eq( a->y, temp );
259 7264 : } else {
260 7264 : return 0;
261 7264 : }
262 7299 : }
263 :
264 : /* Adds projective point `a` and affine-Montgomery point `b`, both
265 : in Montgomery domain. Handles identity elements and the equal-point
266 : (doubling) case. */
267 : static inline void
268 : fd_secp256r1_point_add_mixed( fd_secp256r1_point_t * r,
269 : fd_secp256r1_point_t const * a,
270 7304 : ulong b[ 8 ] ) {
271 7304 : int b_is_zero = fd_uint256_eq( (fd_uint256_t const *)(b+0), fd_secp256r1_const_zero ) &
272 7304 : fd_uint256_eq( (fd_uint256_t const *)(b+4), fd_secp256r1_const_zero );
273 :
274 7304 : if( FD_UNLIKELY( b_is_zero ) ) {
275 : /* a + 0 = a */
276 0 : if( r != a ) fd_memcpy( r, a, sizeof(fd_secp256r1_point_t) );
277 0 : return;
278 0 : }
279 :
280 7304 : if( FD_UNLIKELY( fd_secp256r1_point_eq_mixed( a, b ) ) ) {
281 13 : p256_montjdouble( (ulong *)r, (ulong *)a );
282 7291 : } else {
283 : /* Also handles a == 0 and a == -b */
284 7291 : p256_montjmixadd( (ulong *)r, (ulong *)a, b );
285 7291 : }
286 7304 : }
287 :
288 : static inline void
289 : fd_secp256r1_double_scalar_mul_base( fd_secp256r1_point_t * r,
290 : fd_secp256r1_scalar_t const * u1,
291 : fd_secp256r1_point_t const * a,
292 7301 : fd_secp256r1_scalar_t const * u2 ) {
293 : /* u1*G */
294 7301 : ulong rtmp[ 8 ];
295 7301 : p256_scalarmulbase( rtmp, (ulong *)u1->limbs, 6, (ulong *)fd_secp256r1_base_point_table );
296 7301 : bignum_tomont_p256( rtmp, rtmp );
297 7301 : bignum_tomont_p256( rtmp+4, rtmp+4 );
298 :
299 : /* u2*A */
300 7301 : p256_montjscalarmul( (ulong *)r, (ulong *)u2->limbs, (ulong *)a );
301 :
302 : /* u1*G + u2*A */
303 7301 : fd_secp256r1_point_add_mixed( r, r, rtmp );
304 7301 : }
|
