Line data Source code
1 : #include <stdint.h>
2 : #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 44038 : #define bignum_demont_p256 bignum_demont_p256_alt
9 204018 : #define bignum_mod_n256 bignum_mod_n256_alt
10 340274 : #define bignum_montmul_p256 bignum_montmul_p256_alt
11 10721170 : #define bignum_montsqr_p256 bignum_montsqr_p256_alt
12 204018 : #define bignum_mul_4_8 bignum_mul_4_8_alt
13 26044 : #define bignum_tomont_p256 bignum_tomont_p256_alt
14 4 : #define p256_montjdouble p256_montjdouble_alt
15 2012 : #define p256_montjmixadd p256_montjmixadd_alt
16 2010 : #define p256_montjscalarmul p256_montjscalarmul_alt
17 2010 : #define p256_scalarmulbase p256_scalarmulbase_alt
18 : #endif
19 :
20 : #include "fd_secp256r1_table.c"
21 :
22 : /* Scalars */
23 :
24 : static inline int
25 6024 : fd_secp256r1_scalar_is_zero( fd_secp256r1_scalar_t const * a ) {
26 6024 : return fd_uint256_eq( a, fd_secp256r1_const_zero );
27 6024 : }
28 :
29 : static inline fd_secp256r1_scalar_t *
30 : fd_secp256r1_scalar_frombytes( fd_secp256r1_scalar_t * r,
31 3003045 : uchar const in[ 32 ] ) {
32 3003045 : memcpy( r->buf, in, 32 );
33 3003045 : fd_uint256_bswap( r, r );
34 3003045 : if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n )<0 ) ) {
35 3003045 : return r;
36 3003045 : };
37 0 : return NULL;
38 3003045 : }
39 :
40 : static inline fd_secp256r1_scalar_t *
41 : fd_secp256r1_scalar_frombytes_positive( fd_secp256r1_scalar_t * r,
42 3003021 : uchar const in[ 32 ] ) {
43 3003021 : memcpy( r->buf, in, 32 );
44 3003021 : fd_uint256_bswap( r, r );
45 3003021 : if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n_m1_half )<=0 ) ) {
46 3003015 : return r;
47 3003015 : };
48 6 : return NULL;
49 3003021 : }
50 :
51 : static inline void
52 : fd_secp256r1_scalar_from_digest( fd_secp256r1_scalar_t * r,
53 3012 : uchar const in[ 32 ] ) {
54 3012 : memcpy( r->buf, in, 32 );
55 3012 : fd_uint256_bswap( r, r );
56 3012 : bignum_mod_n256_4( r->limbs, r->limbs );
57 3012 : }
58 :
59 : static inline fd_secp256r1_scalar_t *
60 : fd_secp256r1_scalar_mul( fd_secp256r1_scalar_t * r,
61 : fd_secp256r1_scalar_t const * a,
62 306027 : fd_secp256r1_scalar_t const * b ) {
63 306027 : ulong t[ 8 ];
64 306027 : bignum_mul_4_8( t, (ulong *)a->limbs, (ulong *)b->limbs );
65 306027 : bignum_mod_n256( r->limbs, 8, t );
66 306027 : return r;
67 306027 : }
68 :
69 : static inline fd_secp256r1_scalar_t *
70 : fd_secp256r1_scalar_inv( fd_secp256r1_scalar_t * r,
71 33015 : fd_secp256r1_scalar_t const * a ) {
72 33015 : ulong t[ 12 ];
73 33015 : bignum_modinv( 4, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp256r1_const_n[0].limbs, t );
74 33015 : return r;
75 33015 : }
76 :
77 : /* Field */
78 :
79 : static inline fd_secp256r1_fp_t *
80 : fd_secp256r1_fp_set( fd_secp256r1_fp_t * r,
81 96072 : fd_secp256r1_fp_t const * a ) {
82 96072 : r->limbs[0] = a->limbs[0];
83 96072 : r->limbs[1] = a->limbs[1];
84 96072 : r->limbs[2] = a->limbs[2];
85 96072 : r->limbs[3] = a->limbs[3];
86 96072 : return r;
87 96072 : }
88 :
89 : static inline fd_secp256r1_fp_t *
90 : fd_secp256r1_fp_frombytes( fd_secp256r1_fp_t * r,
91 3033051 : uchar const in[ 32 ] ) {
92 3033051 : memcpy( r->buf, in, 32 );
93 3033051 : fd_uint256_bswap( r, r );
94 3033051 : if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_p )<0 ) ) {
95 3033048 : return r;
96 3033048 : };
97 3 : return NULL;
98 3033051 : }
99 :
100 : static inline fd_secp256r1_fp_t *
101 : fd_secp256r1_fp_sqrt( fd_secp256r1_fp_t * r,
102 63042 : fd_secp256r1_fp_t const * a ) {
103 : /* https://github.com/golang/go/blob/master/src/crypto/internal/fips140/nistec/p256.go#L656 */
104 63042 : fd_secp256r1_fp_t _t0[1], _t1[1];
105 63042 : ulong * t0 = _t0->limbs;
106 63042 : ulong * t1 = _t1->limbs;
107 63042 : ulong * x = (ulong *)a->limbs;
108 :
109 63042 : bignum_montsqr_p256( t0, x );
110 63042 : bignum_montmul_p256( t0, t0, x );
111 126084 : bignum_montsqr_p256( t1, t0 ); for( int i=1; i<2; i++ ) bignum_montsqr_p256( t1, t1 );
112 63042 : bignum_montmul_p256( t0, t0, t1);
113 252168 : bignum_montsqr_p256( t1, t0 ); for( int i=1; i<4; i++ ) bignum_montsqr_p256( t1, t1 );
114 63042 : bignum_montmul_p256( t0, t0, t1);
115 504336 : bignum_montsqr_p256( t1, t0 ); for( int i=1; i<8; i++ ) bignum_montsqr_p256( t1, t1 );
116 63042 : bignum_montmul_p256( t0, t0, t1);
117 1008672 : bignum_montsqr_p256( t1, t0 ); for( int i=1; i<16; i++ ) bignum_montsqr_p256( t1, t1 );
118 63042 : bignum_montmul_p256( t0, t0, t1);
119 2080386 : for( int i=0; i<32; i++ ) bignum_montsqr_p256( t0, t0 );
120 63042 : bignum_montmul_p256( t0, t0, x );
121 6115074 : for( int i=0; i<96; i++ ) bignum_montsqr_p256( t0, t0 );
122 63042 : bignum_montmul_p256( t0, t0, x );
123 5988990 : for( int i=0; i<94; i++ ) bignum_montsqr_p256( t0, t0 );
124 :
125 63042 : bignum_montsqr_p256( t1, t0 );
126 63042 : if( FD_UNLIKELY( !fd_uint256_eq( _t1, a ) ) ) {
127 6 : return NULL;
128 6 : }
129 :
130 63036 : return fd_secp256r1_fp_set( r, _t0 );
131 63042 : }
132 :
133 : /* Points */
134 :
135 : static inline fd_secp256r1_point_t *
136 : fd_secp256r1_point_frombytes( fd_secp256r1_point_t * r,
137 33042 : uchar const in[ 33 ] ) {
138 33042 : fd_secp256r1_fp_t y2[1], demont_y[1];
139 :
140 33042 : uchar sgn = in[0];
141 33042 : if( FD_UNLIKELY( sgn!=2U && sgn!=3U ) ) {
142 3 : return FD_SECP256R1_FAILURE;
143 3 : }
144 :
145 33039 : if( FD_UNLIKELY( !fd_secp256r1_fp_frombytes( r->x, in+1 ) ) ) {
146 3 : return FD_SECP256R1_FAILURE;
147 3 : }
148 :
149 33036 : bignum_tomont_p256( r->x->limbs, r->x->limbs );
150 :
151 : /* y^2 = x^3 + ax + b */
152 33036 : bignum_montsqr_p256( y2->limbs, r->x->limbs );
153 33036 : bignum_add_p256 ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_a_mont[0].limbs );
154 33036 : bignum_montmul_p256( y2->limbs, y2->limbs, r->x->limbs );
155 33036 : bignum_add_p256 ( y2->limbs, y2->limbs, (ulong *)fd_secp256r1_const_b_mont[0].limbs );
156 :
157 : /* y = sqrt(y^2) */
158 33036 : if( FD_UNLIKELY( !fd_secp256r1_fp_sqrt( r->y, y2 ) ) ) {
159 3 : return FD_SECP256R1_FAILURE;
160 3 : }
161 :
162 : /* choose y or -y */
163 33033 : bignum_demont_p256( demont_y->limbs, r->y->limbs );
164 33033 : ulong cond = (demont_y->limbs[0] % 2) != (sgn == 3U);
165 33033 : bignum_optneg_p256( r->y->limbs, cond, r->y->limbs );
166 :
167 33033 : fd_secp256r1_fp_set( r->z, fd_secp256r1_const_one_mont );
168 :
169 33033 : return r;
170 33036 : }
171 :
172 : static inline int
173 : fd_secp256r1_point_eq_x( fd_secp256r1_point_t const * p,
174 33027 : fd_secp256r1_scalar_t const * r ) {
175 33027 : fd_secp256r1_fp_t affine_x[1];
176 33027 : fd_secp256r1_scalar_t * affine_x_mod_n = affine_x;
177 :
178 33027 : if( FD_UNLIKELY( fd_uint256_eq( p->z, fd_secp256r1_const_zero ) ) ) {
179 3 : return FD_SECP256R1_FAILURE;
180 3 : }
181 :
182 : /* x = demont(X / Z^2) mod n */
183 33024 : bignum_montinv_p256( affine_x->limbs, (ulong *)p->z->limbs );
184 33024 : bignum_montsqr_p256( affine_x->limbs, affine_x->limbs );
185 33024 : bignum_montmul_p256( affine_x->limbs, affine_x->limbs, (ulong *)p->x->limbs );
186 33024 : bignum_demont_p256( affine_x_mod_n->limbs, affine_x->limbs );
187 33024 : bignum_mod_n256_4 ( affine_x_mod_n->limbs, affine_x_mod_n->limbs );
188 :
189 33024 : if( FD_LIKELY( fd_uint256_eq( r, affine_x_mod_n ) ) ) {
190 33021 : return FD_SECP256R1_SUCCESS;
191 33021 : }
192 3 : return FD_SECP256R1_FAILURE;
193 33024 : }
194 :
195 : /* Given the projective point `r` and the affine point `p`,
196 : returns 1 if they are equal and 0 otherwise.
197 : Assumes that `p` X and Y coordinates are in Montgomery domain. */
198 : static inline int
199 : fd_secp256r1_point_eq_mixed( fd_secp256r1_point_t const * a,
200 3033 : ulong const b[ 8 ] ) {
201 3033 : fd_secp256r1_fp_t x[1], y[1];
202 3033 : fd_memcpy( x->limbs, b+0, sizeof(fd_secp256r1_fp_t) );
203 3033 : fd_memcpy( y->limbs, b+4, sizeof(fd_secp256r1_fp_t) );
204 : /* Indicates if the affine point is zero. */
205 3033 : int is_zero = fd_uint256_eq( x, fd_secp256r1_const_zero ) & fd_uint256_eq( y, fd_secp256r1_const_zero );
206 :
207 : /* Easy cases */
208 3033 : if( FD_UNLIKELY( fd_uint256_eq( a->z, fd_secp256r1_const_zero ) ) ) {
209 6 : return is_zero;
210 6 : }
211 3027 : if( FD_UNLIKELY( is_zero ) ) {
212 0 : return 0;
213 0 : }
214 :
215 3027 : fd_secp256r1_fp_t z1z1[1];
216 3027 : bignum_montsqr_p256( z1z1->limbs, (ulong *)a->z->limbs );
217 :
218 3027 : fd_secp256r1_fp_t temp[1];
219 3027 : bignum_montmul_p256( temp->limbs, (ulong *)x->limbs, z1z1->limbs );
220 :
221 3027 : if( FD_UNLIKELY( fd_uint256_eq( a->x, temp ) ) ) {
222 15 : bignum_montmul_p256( temp->limbs, z1z1->limbs, (ulong *)a->z->limbs );
223 15 : bignum_montmul_p256( temp->limbs, temp->limbs, (ulong *)y->limbs );
224 15 : return fd_uint256_eq( a->y, temp );
225 3012 : } else {
226 3012 : return 0;
227 3012 : }
228 3027 : }
229 :
230 : /* Adds projective point `a` and affine-Montgomery point `b`, both
231 : in Montgomery domain. Handles identity elements and the equal-point
232 : (doubling) case. */
233 : static inline void
234 : fd_secp256r1_point_add_mixed( fd_secp256r1_point_t * r,
235 : fd_secp256r1_point_t const * a,
236 3030 : ulong b[ 8 ] ) {
237 3030 : int b_is_zero = fd_uint256_eq( (fd_uint256_t const *)(b+0), fd_secp256r1_const_zero ) &
238 3030 : fd_uint256_eq( (fd_uint256_t const *)(b+4), fd_secp256r1_const_zero );
239 :
240 3030 : if( FD_UNLIKELY( b_is_zero ) ) {
241 : /* a + 0 = a */
242 6 : if( r != a ) fd_memcpy( r, a, sizeof(fd_secp256r1_point_t) );
243 6 : return;
244 6 : }
245 :
246 3024 : if( FD_UNLIKELY( fd_secp256r1_point_eq_mixed( a, b ) ) ) {
247 6 : p256_montjdouble( (ulong *)r, (ulong *)a );
248 3018 : } else {
249 : /* Also handles a == 0 and a == -b */
250 3018 : p256_montjmixadd( (ulong *)r, (ulong *)a, b );
251 3018 : }
252 3024 : }
253 :
254 : static inline void
255 : fd_secp256r1_double_scalar_mul_base( fd_secp256r1_point_t * r,
256 : fd_secp256r1_scalar_t const * u1,
257 : fd_secp256r1_point_t const * a,
258 3015 : fd_secp256r1_scalar_t const * u2 ) {
259 : /* u1*G */
260 3015 : ulong rtmp[ 8 ];
261 3015 : p256_scalarmulbase( rtmp, (ulong *)u1->limbs, 6, (ulong *)fd_secp256r1_base_point_table );
262 3015 : bignum_tomont_p256( rtmp, rtmp );
263 3015 : bignum_tomont_p256( rtmp+4, rtmp+4 );
264 :
265 : /* u2*A */
266 3015 : p256_montjscalarmul( (ulong *)r, (ulong *)u2->limbs, (ulong *)a );
267 :
268 : /* u1*G + u2*A */
269 3015 : fd_secp256r1_point_add_mixed( r, r, rtmp );
270 3015 : }
|
