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