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 : /* (p+1)/4 bit pattern (382 bits, MSB first):
93 : 255 ones | 0 | 31 ones | 0 | 63 ones | 1 | 30 zeros */
94 :
95 0 : fd_secp384r1_fp_t _t0[1], _t1[1];
96 0 : ulong * t0 = _t0->limbs;
97 0 : ulong * t1 = _t1->limbs;
98 0 : ulong * x = (ulong *)a->limbs;
99 :
100 : /* Build x^(2^k - 1) chain */
101 0 : fd_secp384r1_fp_t e2[1], e4[1], e8[1], e16[1], e32[1], e64[1], e128[1];
102 :
103 : /* x^3 */
104 0 : bignum_montsqr_p384( t0, x );
105 0 : bignum_montmul_p384( t0, t0, x );
106 0 : memcpy( e2, t0, 48 );
107 :
108 : /* x^(2^4-1) */
109 0 : for( int i=0; i<2; i++ ) bignum_montsqr_p384( t0, t0 );
110 0 : bignum_montmul_p384( t0, t0, e2->limbs );
111 0 : memcpy( e4, t0, 48 );
112 :
113 : /* x^(2^8-1) */
114 0 : memcpy( t1, t0, 48 );
115 0 : for( int i=0; i<4; i++ ) bignum_montsqr_p384( t1, t1 );
116 0 : bignum_montmul_p384( t0, t1, t0 );
117 0 : memcpy( e8, t0, 48 );
118 :
119 : /* x^(2^16-1) */
120 0 : memcpy( t1, t0, 48 );
121 0 : for( int i=0; i<8; i++ ) bignum_montsqr_p384( t1, t1 );
122 0 : bignum_montmul_p384( t0, t1, t0 );
123 0 : memcpy( e16, t0, 48 );
124 :
125 : /* x^(2^32-1) */
126 0 : memcpy( t1, t0, 48 );
127 0 : for( int i=0; i<16; i++ ) bignum_montsqr_p384( t1, t1 );
128 0 : bignum_montmul_p384( t0, t1, t0 );
129 0 : memcpy( e32, t0, 48 );
130 :
131 : /* x^(2^64-1) */
132 0 : memcpy( t1, t0, 48 );
133 0 : for( int i=0; i<32; i++ ) bignum_montsqr_p384( t1, t1 );
134 0 : bignum_montmul_p384( t0, t1, t0 );
135 0 : memcpy( e64, t0, 48 );
136 :
137 : /* x^(2^128-1) */
138 0 : memcpy( t1, t0, 48 );
139 0 : for( int i=0; i<64; i++ ) bignum_montsqr_p384( t1, t1 );
140 0 : bignum_montmul_p384( t0, t1, t0 );
141 0 : memcpy( e128, t0, 48 );
142 :
143 : /* x^(2^255-1): build from sub-chains */
144 :
145 : /* x^(2^3-1) = x^7 */
146 0 : bignum_montsqr_p384( t0, e2->limbs );
147 0 : bignum_montmul_p384( t0, t0, x );
148 :
149 : /* x^(2^7-1) */
150 0 : memcpy( t1, e4->limbs, 48 );
151 0 : for( int i=0; i<3; i++ ) bignum_montsqr_p384( t1, t1 );
152 0 : bignum_montmul_p384( t0, t1, t0 );
153 :
154 : /* x^(2^15-1) */
155 0 : memcpy( t1, e8->limbs, 48 );
156 0 : for( int i=0; i<7; i++ ) bignum_montsqr_p384( t1, t1 );
157 0 : bignum_montmul_p384( t0, t1, t0 );
158 :
159 : /* x^(2^31-1) */
160 0 : memcpy( t1, e16->limbs, 48 );
161 0 : for( int i=0; i<15; i++ ) bignum_montsqr_p384( t1, t1 );
162 0 : bignum_montmul_p384( t0, t1, t0 );
163 :
164 : /* x^(2^63-1) */
165 0 : memcpy( t1, e32->limbs, 48 );
166 0 : for( int i=0; i<31; i++ ) bignum_montsqr_p384( t1, t1 );
167 0 : bignum_montmul_p384( t0, t1, t0 );
168 :
169 : /* x^(2^127-1) */
170 0 : memcpy( t1, e64->limbs, 48 );
171 0 : for( int i=0; i<63; i++ ) bignum_montsqr_p384( t1, t1 );
172 0 : bignum_montmul_p384( t0, t1, t0 );
173 :
174 : /* x^(2^255-1) */
175 0 : memcpy( t1, e128->limbs, 48 );
176 0 : for( int i=0; i<127; i++ ) bignum_montsqr_p384( t1, t1 );
177 0 : 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 0 : bignum_montsqr_p384( t0, t0 ); /* bit 126: 0 */
185 :
186 0 : for( int i=0; i<32; i++ ) { /* bits 125..94: 32 ones */
187 0 : bignum_montsqr_p384( t0, t0 );
188 0 : bignum_montmul_p384( t0, t0, x );
189 0 : }
190 :
191 0 : for( int i=0; i<63; i++ ) bignum_montsqr_p384( t0, t0 ); /* bits 93..31: 63 zeros */
192 :
193 0 : bignum_montsqr_p384( t0, t0 ); /* bit 30: 1 */
194 0 : bignum_montmul_p384( t0, t0, x );
195 :
196 0 : for( int i=0; i<30; i++ ) bignum_montsqr_p384( t0, t0 ); /* bits 29..0: 30 zeros */
197 :
198 : /* Verify: t0^2 == a */
199 0 : bignum_montsqr_p384( t1, t0 );
200 0 : if( FD_UNLIKELY( !fd_uint384_eq( (fd_uint384_t const *)t1, a ) ) )
201 0 : return NULL;
202 :
203 0 : return fd_secp384r1_fp_set( r, (fd_secp384r1_fp_t const *)t0 );
204 0 : }
205 :
206 : /* Points */
207 :
208 : static inline int
209 0 : fd_secp384r1_point_validate_uncompressed( uchar const in[ 97 ] ) {
210 0 : if( FD_UNLIKELY( in[ 0 ]!=0x04U ) ) return FD_SECP384R1_FAILURE;
211 :
212 0 : fd_secp384r1_fp_t x[1], y[1], lhs[1], rhs[1];
213 0 : if( FD_UNLIKELY( !fd_secp384r1_fp_frombytes( x, in+1 ) ) ) return FD_SECP384R1_FAILURE;
214 0 : if( FD_UNLIKELY( !fd_secp384r1_fp_frombytes( y, in+49 ) ) ) return FD_SECP384R1_FAILURE;
215 :
216 0 : bignum_tomont_p384( x->limbs, x->limbs );
217 0 : bignum_tomont_p384( y->limbs, y->limbs );
218 :
219 : /* Validate y^2 = x^3 + ax + b. */
220 0 : bignum_montsqr_p384( lhs->limbs, y->limbs );
221 0 : bignum_montsqr_p384( rhs->limbs, x->limbs );
222 0 : bignum_add_p384 ( rhs->limbs, rhs->limbs, (ulong *)fd_secp384r1_const_a_mont[0].limbs );
223 0 : bignum_montmul_p384( rhs->limbs, rhs->limbs, x->limbs );
224 0 : bignum_add_p384 ( rhs->limbs, rhs->limbs, (ulong *)fd_secp384r1_const_b_mont[0].limbs );
225 0 : return fd_uint384_eq( lhs, rhs );
226 0 : }
227 :
228 : static inline fd_secp384r1_point_t *
229 : fd_secp384r1_point_frombytes( fd_secp384r1_point_t * r,
230 0 : uchar const in[ 49 ] ) {
231 0 : fd_secp384r1_fp_t y2[1], demont_y[1];
232 :
233 0 : uchar sgn = in[0];
234 0 : if( FD_UNLIKELY( sgn!=2U && sgn!=3U ) )
235 0 : return NULL;
236 :
237 0 : if( FD_UNLIKELY( !fd_secp384r1_fp_frombytes( r->x, in+1 ) ) )
238 0 : return NULL;
239 :
240 0 : bignum_tomont_p384( r->x->limbs, r->x->limbs );
241 :
242 : /* y^2 = x^3 + ax + b */
243 0 : bignum_montsqr_p384( y2->limbs, r->x->limbs );
244 0 : bignum_add_p384 ( y2->limbs, y2->limbs, (ulong *)fd_secp384r1_const_a_mont[0].limbs );
245 0 : bignum_montmul_p384( y2->limbs, y2->limbs, r->x->limbs );
246 0 : bignum_add_p384 ( y2->limbs, y2->limbs, (ulong *)fd_secp384r1_const_b_mont[0].limbs );
247 :
248 0 : if( FD_UNLIKELY( !fd_secp384r1_fp_sqrt( r->y, y2 ) ) )
249 0 : return NULL;
250 :
251 0 : bignum_demont_p384( demont_y->limbs, r->y->limbs );
252 0 : ulong cond = (demont_y->limbs[0] % 2) != (sgn == 3U);
253 0 : bignum_optneg_p384( r->y->limbs, cond, r->y->limbs );
254 :
255 0 : fd_secp384r1_fp_set( r->z, fd_secp384r1_const_one_mont );
256 0 : return r;
257 0 : }
258 :
259 : static inline int
260 : fd_secp384r1_point_eq_x( fd_secp384r1_point_t const * p,
261 0 : fd_secp384r1_scalar_t const * r ) {
262 0 : fd_secp384r1_fp_t affine_x[1];
263 :
264 0 : if( FD_UNLIKELY( fd_uint384_is_zero( p->z ) ) )
265 0 : return FD_SECP384R1_FAILURE;
266 :
267 0 : bignum_montinv_p384( affine_x->limbs, (ulong *)p->z->limbs );
268 0 : bignum_montsqr_p384( affine_x->limbs, affine_x->limbs );
269 0 : bignum_montmul_p384( affine_x->limbs, affine_x->limbs, (ulong *)p->x->limbs );
270 0 : bignum_demont_p384( affine_x->limbs, affine_x->limbs );
271 0 : bignum_mod_n384_6 ( affine_x->limbs, affine_x->limbs );
272 :
273 0 : if( FD_LIKELY( fd_uint384_eq( r, (fd_uint384_t const *)affine_x ) ) )
274 0 : return FD_SECP384R1_SUCCESS;
275 0 : return FD_SECP384R1_FAILURE;
276 0 : }
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 0 : ulong const b[ 18 ] ) {
283 0 : int a_is_zero = fd_uint384_is_zero( a->z );
284 0 : int b_is_zero = !(b[12] | b[13] | b[14] | b[15] | b[16] | b[17]);
285 :
286 0 : if( FD_UNLIKELY( a_is_zero ) ) return b_is_zero;
287 0 : if( FD_UNLIKELY( b_is_zero ) ) return 0;
288 :
289 0 : fd_secp384r1_fp_t z1z1[1], z2z2[1], lhs[1], rhs[1];
290 0 : bignum_montsqr_p384( z1z1->limbs, a->z->limbs );
291 0 : bignum_montsqr_p384( z2z2->limbs, b+12 );
292 :
293 : /* Compare X1*Z2^2 and X2*Z1^2. */
294 0 : bignum_montmul_p384( lhs->limbs, a->x->limbs, z2z2->limbs );
295 0 : bignum_montmul_p384( rhs->limbs, b, z1z1->limbs );
296 0 : if( FD_LIKELY( !fd_uint384_eq( lhs, rhs ) ) ) return 0;
297 :
298 : /* Compare Y1*Z2^3 and Y2*Z1^3. */
299 0 : bignum_montmul_p384( z1z1->limbs, z1z1->limbs, a->z->limbs );
300 0 : bignum_montmul_p384( z2z2->limbs, z2z2->limbs, b+12 );
301 0 : bignum_montmul_p384( lhs->limbs, a->y->limbs, z2z2->limbs );
302 0 : bignum_montmul_p384( rhs->limbs, b+6, z1z1->limbs );
303 0 : return fd_uint384_eq( lhs, rhs );
304 0 : }
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 0 : fd_secp384r1_scalar_t const * u2 ) {
311 : /* u1*G */
312 0 : ulong u1G[18];
313 0 : p384_montjscalarmul( u1G, (ulong *)u1->limbs, fd_secp384r1_const_g_mont );
314 :
315 : /* u2*A */
316 0 : p384_montjscalarmul( (ulong *)r, (ulong *)u2->limbs, (ulong const *)a );
317 :
318 : /* u1*G + u2*A */
319 0 : if( FD_UNLIKELY( fd_secp384r1_point_eq( r, u1G ) ) ) {
320 0 : p384_montjdouble( (ulong *)r, (ulong *)r );
321 0 : } else {
322 0 : p384_montjadd( (ulong *)r, (ulong *)r, u1G );
323 0 : }
324 0 : }
|
