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