Line data Source code
1 : #include <stdint.h>
2 : #include "../../third_party/s2n-bignum/include/s2n-bignum.h"
3 :
4 : #ifndef __ADX__
5 240 : #define bignum_demont_p384 bignum_demont_p384_alt
6 240 : #define bignum_mod_n384 bignum_mod_n384_alt
7 6268 : #define bignum_montmul_p384 bignum_montmul_p384_alt
8 61000 : #define bignum_montsqr_p384 bignum_montsqr_p384_alt
9 240 : #define bignum_mul_6_12 bignum_mul_6_12_alt
10 400 : #define bignum_tomont_p384 bignum_tomont_p384_alt
11 2 : #define p384_montjdouble p384_montjdouble_alt
12 118 : #define p384_montjadd p384_montjadd_alt
13 240 : #define p384_montjscalarmul p384_montjscalarmul_alt
14 : #endif
15 :
16 : /* Scalars */
17 :
18 : static inline int
19 372 : fd_secp384r1_scalar_is_zero( fd_secp384r1_scalar_t const * a ) {
20 372 : return fd_uint384_is_zero( a );
21 372 : }
22 :
23 : static inline fd_secp384r1_scalar_t *
24 : fd_secp384r1_scalar_frombytes( fd_secp384r1_scalar_t * r,
25 363 : uchar const in[ 48 ] ) {
26 363 : memcpy( r->buf, in, 48 );
27 363 : fd_uint384_bswap( r, r );
28 363 : if( FD_LIKELY( fd_uint384_cmp( r, fd_secp384r1_const_n )<0 ) )
29 363 : return r;
30 0 : return NULL;
31 363 : }
32 :
33 : static inline fd_secp384r1_scalar_t *
34 : fd_secp384r1_scalar_frombytes_positive( fd_secp384r1_scalar_t * r,
35 9 : uchar const in[ 48 ] ) {
36 9 : memcpy( r->buf, in, 48 );
37 9 : fd_uint384_bswap( r, r );
38 9 : if( FD_LIKELY( fd_uint384_cmp( r, fd_secp384r1_const_n_m1_half )<=0 ) )
39 9 : return r;
40 0 : return NULL;
41 9 : }
42 :
43 : static inline void
44 : fd_secp384r1_scalar_from_digest( fd_secp384r1_scalar_t * r,
45 180 : uchar const in[ 48 ] ) {
46 180 : memcpy( r->buf, in, 48 );
47 180 : fd_uint384_bswap( r, r );
48 180 : bignum_mod_n384_6( r->limbs, r->limbs );
49 180 : }
50 :
51 : static inline fd_secp384r1_scalar_t *
52 : fd_secp384r1_scalar_mul( fd_secp384r1_scalar_t * r,
53 : fd_secp384r1_scalar_t const * a,
54 360 : fd_secp384r1_scalar_t const * b ) {
55 360 : ulong t[ 12 ];
56 360 : bignum_mul_6_12( t, (ulong *)a->limbs, (ulong *)b->limbs );
57 360 : bignum_mod_n384( r->limbs, 12, t );
58 360 : return r;
59 360 : }
60 :
61 : static inline fd_secp384r1_scalar_t *
62 : fd_secp384r1_scalar_inv( fd_secp384r1_scalar_t * r,
63 180 : fd_secp384r1_scalar_t const * a ) {
64 180 : ulong t[ 18 ];
65 180 : bignum_modinv( 6, r->limbs, (ulong *)a->limbs, (ulong *)fd_secp384r1_const_n[0].limbs, t );
66 180 : return r;
67 180 : }
68 :
69 : /* Field */
70 :
71 : static inline fd_secp384r1_fp_t *
72 : fd_secp384r1_fp_set( fd_secp384r1_fp_t * r,
73 360 : fd_secp384r1_fp_t const * a ) {
74 360 : memcpy( r->limbs, a->limbs, 48 );
75 360 : return r;
76 360 : }
77 :
78 : static inline fd_secp384r1_fp_t *
79 : fd_secp384r1_fp_frombytes( fd_secp384r1_fp_t * r,
80 609 : uchar const in[ 48 ] ) {
81 609 : memcpy( r->buf, in, 48 );
82 609 : fd_uint384_bswap( r, r );
83 609 : if( FD_LIKELY( fd_uint384_cmp( r, fd_secp384r1_const_p )<0 ) )
84 603 : return r;
85 6 : return NULL;
86 609 : }
87 :
88 : /* p \equiv 3 (mod 4), so sqrt(a) = a^((p+1)/4) mod p. */
89 : static inline fd_secp384r1_fp_t *
90 : fd_secp384r1_fp_sqrt( fd_secp384r1_fp_t * r,
91 180 : fd_secp384r1_fp_t const * a ) {
92 : /* (p+1)/4 bit pattern (382 bits, MSB first):
93 : 255 ones | 0 | 31 ones | 0 | 63 ones | 1 | 30 zeros */
94 :
95 180 : fd_secp384r1_fp_t _t0[1], _t1[1];
96 180 : ulong * t0 = _t0->limbs;
97 180 : ulong * t1 = _t1->limbs;
98 180 : ulong * x = (ulong *)a->limbs;
99 :
100 : /* Build x^(2^k - 1) chain */
101 180 : fd_secp384r1_fp_t e2[1], e4[1], e8[1], e16[1], e32[1], e64[1], e128[1];
102 :
103 : /* x^3 */
104 180 : bignum_montsqr_p384( t0, x );
105 180 : bignum_montmul_p384( t0, t0, x );
106 180 : memcpy( e2, t0, 48 );
107 :
108 : /* x^(2^4-1) */
109 540 : for( int i=0; i<2; i++ ) bignum_montsqr_p384( t0, t0 );
110 180 : bignum_montmul_p384( t0, t0, e2->limbs );
111 180 : memcpy( e4, t0, 48 );
112 :
113 : /* x^(2^8-1) */
114 180 : memcpy( t1, t0, 48 );
115 900 : for( int i=0; i<4; i++ ) bignum_montsqr_p384( t1, t1 );
116 180 : bignum_montmul_p384( t0, t1, t0 );
117 180 : memcpy( e8, t0, 48 );
118 :
119 : /* x^(2^16-1) */
120 180 : memcpy( t1, t0, 48 );
121 1620 : for( int i=0; i<8; i++ ) bignum_montsqr_p384( t1, t1 );
122 180 : bignum_montmul_p384( t0, t1, t0 );
123 180 : memcpy( e16, t0, 48 );
124 :
125 : /* x^(2^32-1) */
126 180 : memcpy( t1, t0, 48 );
127 3060 : for( int i=0; i<16; i++ ) bignum_montsqr_p384( t1, t1 );
128 180 : bignum_montmul_p384( t0, t1, t0 );
129 180 : memcpy( e32, t0, 48 );
130 :
131 : /* x^(2^64-1) */
132 180 : memcpy( t1, t0, 48 );
133 5940 : for( int i=0; i<32; i++ ) bignum_montsqr_p384( t1, t1 );
134 180 : bignum_montmul_p384( t0, t1, t0 );
135 180 : memcpy( e64, t0, 48 );
136 :
137 : /* x^(2^128-1) */
138 180 : memcpy( t1, t0, 48 );
139 11700 : for( int i=0; i<64; i++ ) bignum_montsqr_p384( t1, t1 );
140 180 : bignum_montmul_p384( t0, t1, t0 );
141 180 : memcpy( e128, t0, 48 );
142 :
143 : /* x^(2^255-1): build from sub-chains */
144 :
145 : /* x^(2^3-1) = x^7 */
146 180 : bignum_montsqr_p384( t0, e2->limbs );
147 180 : bignum_montmul_p384( t0, t0, x );
148 :
149 : /* x^(2^7-1) */
150 180 : memcpy( t1, e4->limbs, 48 );
151 720 : for( int i=0; i<3; i++ ) bignum_montsqr_p384( t1, t1 );
152 180 : bignum_montmul_p384( t0, t1, t0 );
153 :
154 : /* x^(2^15-1) */
155 180 : memcpy( t1, e8->limbs, 48 );
156 1440 : for( int i=0; i<7; i++ ) bignum_montsqr_p384( t1, t1 );
157 180 : bignum_montmul_p384( t0, t1, t0 );
158 :
159 : /* x^(2^31-1) */
160 180 : memcpy( t1, e16->limbs, 48 );
161 2880 : for( int i=0; i<15; i++ ) bignum_montsqr_p384( t1, t1 );
162 180 : bignum_montmul_p384( t0, t1, t0 );
163 :
164 : /* x^(2^63-1) */
165 180 : memcpy( t1, e32->limbs, 48 );
166 5760 : for( int i=0; i<31; i++ ) bignum_montsqr_p384( t1, t1 );
167 180 : bignum_montmul_p384( t0, t1, t0 );
168 :
169 : /* x^(2^127-1) */
170 180 : memcpy( t1, e64->limbs, 48 );
171 11520 : for( int i=0; i<63; i++ ) bignum_montsqr_p384( t1, t1 );
172 180 : bignum_montmul_p384( t0, t1, t0 );
173 :
174 : /* x^(2^255-1) */
175 180 : memcpy( t1, e128->limbs, 48 );
176 23040 : for( int i=0; i<127; i++ ) bignum_montsqr_p384( t1, t1 );
177 180 : bignum_montmul_p384( t0, t1, t0 );
178 :
179 : /* Process remaining exponent bits:
180 : 0 | 32 ones | 63 zeros | 1 | 30 zeros
181 : (bit 126 = 0, bits 125..94 = 32 ones, bits 93..31 = 63 zeros,
182 : bit 30 = 1, bits 29..0 = 30 zeros) */
183 :
184 180 : bignum_montsqr_p384( t0, t0 ); /* bit 126: 0 */
185 :
186 5940 : for( int i=0; i<32; i++ ) { /* bits 125..94: 32 ones */
187 5760 : bignum_montsqr_p384( t0, t0 );
188 5760 : bignum_montmul_p384( t0, t0, x );
189 5760 : }
190 :
191 11520 : for( int i=0; i<63; i++ ) bignum_montsqr_p384( t0, t0 ); /* bits 93..31: 63 zeros */
192 :
193 180 : bignum_montsqr_p384( t0, t0 ); /* bit 30: 1 */
194 180 : bignum_montmul_p384( t0, t0, x );
195 :
196 5580 : for( int i=0; i<30; i++ ) bignum_montsqr_p384( t0, t0 ); /* bits 29..0: 30 zeros */
197 :
198 : /* Verify: t0^2 == a */
199 180 : bignum_montsqr_p384( t1, t0 );
200 180 : if( FD_UNLIKELY( !fd_uint384_eq( (fd_uint384_t const *)t1, a ) ) )
201 0 : return NULL;
202 :
203 180 : return fd_secp384r1_fp_set( r, (fd_secp384r1_fp_t const *)t0 );
204 180 : }
205 :
206 : /* Points */
207 :
208 : static inline int
209 219 : fd_secp384r1_point_validate_uncompressed( uchar const in[ 97 ] ) {
210 219 : if( FD_UNLIKELY( in[ 0 ]!=0x04U ) ) return FD_SECP384R1_FAILURE;
211 :
212 216 : fd_secp384r1_fp_t x[1], y[1], lhs[1], rhs[1];
213 216 : if( FD_UNLIKELY( !fd_secp384r1_fp_frombytes( x, in+1 ) ) ) return FD_SECP384R1_FAILURE;
214 213 : if( FD_UNLIKELY( !fd_secp384r1_fp_frombytes( y, in+49 ) ) ) return FD_SECP384R1_FAILURE;
215 :
216 210 : bignum_tomont_p384( x->limbs, x->limbs );
217 210 : bignum_tomont_p384( y->limbs, y->limbs );
218 :
219 : /* Validate y^2 = x^3 + ax + b. */
220 210 : bignum_montsqr_p384( lhs->limbs, y->limbs );
221 210 : bignum_montsqr_p384( rhs->limbs, x->limbs );
222 210 : bignum_add_p384 ( rhs->limbs, rhs->limbs, (ulong *)fd_secp384r1_const_a_mont[0].limbs );
223 210 : bignum_montmul_p384( rhs->limbs, rhs->limbs, x->limbs );
224 210 : bignum_add_p384 ( rhs->limbs, rhs->limbs, (ulong *)fd_secp384r1_const_b_mont[0].limbs );
225 210 : return fd_uint384_eq( lhs, rhs );
226 213 : }
227 :
228 : static inline fd_secp384r1_point_t *
229 : fd_secp384r1_point_frombytes( fd_secp384r1_point_t * r,
230 180 : uchar const in[ 49 ] ) {
231 180 : fd_secp384r1_fp_t y2[1], demont_y[1];
232 :
233 180 : uchar sgn = in[0];
234 180 : if( FD_UNLIKELY( sgn!=2U && sgn!=3U ) )
235 0 : return NULL;
236 :
237 180 : if( FD_UNLIKELY( !fd_secp384r1_fp_frombytes( r->x, in+1 ) ) )
238 0 : return NULL;
239 :
240 180 : bignum_tomont_p384( r->x->limbs, r->x->limbs );
241 :
242 : /* y^2 = x^3 + ax + b */
243 180 : bignum_montsqr_p384( y2->limbs, r->x->limbs );
244 180 : bignum_add_p384 ( y2->limbs, y2->limbs, (ulong *)fd_secp384r1_const_a_mont[0].limbs );
245 180 : bignum_montmul_p384( y2->limbs, y2->limbs, r->x->limbs );
246 180 : bignum_add_p384 ( y2->limbs, y2->limbs, (ulong *)fd_secp384r1_const_b_mont[0].limbs );
247 :
248 180 : if( FD_UNLIKELY( !fd_secp384r1_fp_sqrt( r->y, y2 ) ) )
249 0 : return NULL;
250 :
251 180 : bignum_demont_p384( demont_y->limbs, r->y->limbs );
252 180 : ulong cond = (demont_y->limbs[0] % 2) != (sgn == 3U);
253 180 : bignum_optneg_p384( r->y->limbs, cond, r->y->limbs );
254 :
255 180 : fd_secp384r1_fp_set( r->z, fd_secp384r1_const_one_mont );
256 180 : return r;
257 180 : }
258 :
259 : static inline int
260 : fd_secp384r1_point_eq_x( fd_secp384r1_point_t const * p,
261 180 : fd_secp384r1_scalar_t const * r ) {
262 180 : fd_secp384r1_fp_t affine_x[1];
263 :
264 180 : if( FD_UNLIKELY( fd_uint384_is_zero( p->z ) ) )
265 0 : return FD_SECP384R1_FAILURE;
266 :
267 180 : bignum_montinv_p384( affine_x->limbs, (ulong *)p->z->limbs );
268 180 : bignum_montsqr_p384( affine_x->limbs, affine_x->limbs );
269 180 : bignum_montmul_p384( affine_x->limbs, affine_x->limbs, (ulong *)p->x->limbs );
270 180 : bignum_demont_p384( affine_x->limbs, affine_x->limbs );
271 180 : bignum_mod_n384_6 ( affine_x->limbs, affine_x->limbs );
272 :
273 180 : if( FD_LIKELY( fd_uint384_eq( r, (fd_uint384_t const *)affine_x ) ) )
274 168 : return FD_SECP384R1_SUCCESS;
275 12 : return FD_SECP384R1_FAILURE;
276 180 : }
277 :
278 : /* Returns 1 if the Jacobian points a and b represent the same curve point.
279 : Both points have their coordinates in the Montgomery domain. */
280 : static inline int
281 : fd_secp384r1_point_eq( fd_secp384r1_point_t const * a,
282 180 : ulong const b[ 18 ] ) {
283 180 : int a_is_zero = fd_uint384_is_zero( a->z );
284 180 : int b_is_zero = !(b[12] | b[13] | b[14] | b[15] | b[16] | b[17]);
285 :
286 180 : if( FD_UNLIKELY( a_is_zero ) ) return b_is_zero;
287 180 : if( FD_UNLIKELY( b_is_zero ) ) return 0;
288 :
289 180 : fd_secp384r1_fp_t z1z1[1], z2z2[1], lhs[1], rhs[1];
290 180 : bignum_montsqr_p384( z1z1->limbs, a->z->limbs );
291 180 : bignum_montsqr_p384( z2z2->limbs, b+12 );
292 :
293 : /* Compare X1*Z2^2 and X2*Z1^2. */
294 180 : bignum_montmul_p384( lhs->limbs, a->x->limbs, z2z2->limbs );
295 180 : bignum_montmul_p384( rhs->limbs, b, z1z1->limbs );
296 180 : if( FD_LIKELY( !fd_uint384_eq( lhs, rhs ) ) ) return 0;
297 :
298 : /* Compare Y1*Z2^3 and Y2*Z1^3. */
299 3 : bignum_montmul_p384( z1z1->limbs, z1z1->limbs, a->z->limbs );
300 3 : bignum_montmul_p384( z2z2->limbs, z2z2->limbs, b+12 );
301 3 : bignum_montmul_p384( lhs->limbs, a->y->limbs, z2z2->limbs );
302 3 : bignum_montmul_p384( rhs->limbs, b+6, z1z1->limbs );
303 3 : return fd_uint384_eq( lhs, rhs );
304 180 : }
305 :
306 : static inline void
307 : fd_secp384r1_double_scalar_mul_base( fd_secp384r1_point_t * r,
308 : fd_secp384r1_scalar_t const * u1,
309 : fd_secp384r1_point_t const * a,
310 180 : fd_secp384r1_scalar_t const * u2 ) {
311 : /* u1*G */
312 180 : ulong u1G[18];
313 180 : p384_montjscalarmul( u1G, (ulong *)u1->limbs, fd_secp384r1_const_g_mont );
314 :
315 : /* u2*A */
316 180 : p384_montjscalarmul( (ulong *)r, (ulong *)u2->limbs, (ulong const *)a );
317 :
318 : /* u1*G + u2*A */
319 180 : if( FD_UNLIKELY( fd_secp384r1_point_eq( r, u1G ) ) ) {
320 3 : p384_montjdouble( (ulong *)r, (ulong *)r );
321 177 : } else {
322 177 : p384_montjadd( (ulong *)r, (ulong *)r, u1G );
323 177 : }
324 180 : }
|
