Line data Source code
1 : #include "fd_secp256r1_private.h"
2 :
3 : #define PCURVE_NAME fd_secp256r1
4 0 : #define PCURVE_SCALAR_SZ 32
5 13088 : #define PCURVE_SCALAR_T fd_secp256r1_scalar_t
6 13088 : #define PCURVE_POINT_T fd_secp256r1_point_t
7 : #define PCURVE_SHA_NAME fd_sha256
8 : #define PCURVE_SHA_T fd_sha256_t
9 : #define PCURVE_SHA_SZ FD_SHA256_HASH_SZ
10 4642 : #define PCURVE_SUCCESS FD_SECP256R1_SUCCESS
11 8446 : #define PCURVE_FAILURE FD_SECP256R1_FAILURE
12 :
13 : #include "../pcurves/fd_pcurve_tmpl.c"
14 :
15 : /* Syscalls */
16 :
17 : /* Loads a 32 byte integer, big or little endian, as plain limbs. */
18 : static inline fd_uint256_t *
19 : fd_secp256r1_uint256_frombytes( fd_uint256_t * r,
20 : uchar const in[ 32 ],
21 0 : int big_endian ) {
22 0 : memcpy( r->buf, in, 32 );
23 0 : if( big_endian ) fd_uint256_bswap( r, r );
24 0 : return r;
25 0 : }
26 :
27 : static inline uchar *
28 : fd_secp256r1_uint256_tobytes( uchar out[ 32 ],
29 : fd_uint256_t const * a,
30 0 : int big_endian ) {
31 0 : fd_uint256_t t[1];
32 0 : if( big_endian ) a = fd_uint256_bswap( t, a );
33 0 : memcpy( out, a->buf, 32 );
34 0 : return out;
35 0 : }
36 :
37 : /* Loads a scalar, NULL if not canonical (>= n). */
38 : static inline fd_secp256r1_scalar_t *
39 : fd_secp256r1_scalar_frombytes_syscall( fd_secp256r1_scalar_t * r,
40 : uchar const in[ 32 ],
41 0 : int big_endian ) {
42 0 : fd_secp256r1_uint256_frombytes( r, in, big_endian );
43 0 : if( FD_LIKELY( fd_uint256_cmp( r, fd_secp256r1_const_n )<0 ) ) return r;
44 0 : return NULL;
45 0 : }
46 :
47 : /* Decodes x || y into affine-Montgomery (x, y) as 8 limbs. 64 zero
48 : bytes decode to (0, 0), infinity. Returns NULL if a coordinate is
49 : not canonical (>= p) or the point is not on the curve. */
50 : static ulong *
51 : fd_secp256r1_affine_frombytes( ulong r[ 8 ],
52 : uchar const in[ 64 ],
53 0 : int big_endian ) {
54 0 : fd_secp256r1_fp_t x[1], y[1];
55 0 : fd_secp256r1_uint256_frombytes( x, in, big_endian );
56 0 : fd_secp256r1_uint256_frombytes( y, in+32, big_endian );
57 :
58 0 : if( FD_UNLIKELY( fd_uint256_is_zero( x ) & fd_uint256_is_zero( y ) ) ) {
59 0 : memset( r, 0, 64 );
60 0 : return r;
61 0 : }
62 0 : if( FD_UNLIKELY( fd_uint256_cmp( x, fd_secp256r1_const_p )>=0 ) ) return NULL;
63 0 : if( FD_UNLIKELY( fd_uint256_cmp( y, fd_secp256r1_const_p )>=0 ) ) return NULL;
64 :
65 0 : fd_secp256r1_fp_tomont( x, x );
66 0 : fd_secp256r1_fp_tomont( y, y );
67 0 : if( FD_UNLIKELY( !fd_secp256r1_point_on_curve( x, y ) ) ) return NULL;
68 :
69 0 : memcpy( r, x->limbs, 32 );
70 0 : memcpy( r+4, y->limbs, 32 );
71 0 : return r;
72 0 : }
73 :
74 : /* Encodes affine-Montgomery (x, y) as x || y. (0, 0) encodes to 64
75 : zero bytes. */
76 : static uchar *
77 : fd_secp256r1_affine_tobytes( uchar out[ 64 ],
78 : ulong const a[ 8 ],
79 0 : int big_endian ) {
80 0 : fd_secp256r1_fp_t x[1], y[1];
81 0 : memcpy( x->limbs, a, 32 );
82 0 : memcpy( y->limbs, a+4, 32 );
83 0 : fd_secp256r1_fp_demont( x, x );
84 0 : fd_secp256r1_fp_demont( y, y );
85 0 : fd_secp256r1_uint256_tobytes( out, x, big_endian );
86 0 : fd_secp256r1_uint256_tobytes( out+32, y, big_endian );
87 0 : return out;
88 0 : }
89 :
90 : static inline fd_secp256r1_point_t *
91 : fd_secp256r1_point_from_affine( fd_secp256r1_point_t * r,
92 0 : ulong const a[ 8 ] ) {
93 0 : memcpy( r->x->limbs, a, 32 );
94 0 : memcpy( r->y->limbs, a+4, 32 );
95 0 : if( FD_UNLIKELY( fd_uint256_is_zero( r->x ) & fd_uint256_is_zero( r->y ) ) ) {
96 0 : fd_secp256r1_point_set_inf( r );
97 0 : } else {
98 0 : fd_secp256r1_fp_set( r->z, fd_secp256r1_const_one_mont );
99 0 : }
100 0 : return r;
101 0 : }
102 :
103 : static inline uchar *
104 : fd_secp256r1_point_tobytes_syscall( uchar out[ 64 ],
105 : fd_secp256r1_point_t const * a,
106 0 : int big_endian ) {
107 0 : ulong aff[ 8 ];
108 0 : fd_secp256r1_point_toaffine_mont( aff, a );
109 0 : return fd_secp256r1_affine_tobytes( out, aff, big_endian );
110 0 : }
111 :
112 : int
113 : fd_secp256r1_validate_syscall( uchar const _a[ 64 ],
114 0 : int big_endian ) {
115 0 : ulong a[ 8 ];
116 0 : return !!fd_secp256r1_affine_frombytes( a, _a, big_endian );
117 0 : }
118 :
119 : int
120 : fd_secp256r1_decompress_syscall( uchar _r[ 64 ],
121 : uchar const _a[ 33 ],
122 0 : int big_endian ) {
123 : /* fd_secp256r1_point_frombytes expects big endian x */
124 0 : uchar be[ 33 ];
125 0 : if( !big_endian ) {
126 0 : be[ 0 ] = _a[ 0 ];
127 0 : for( ulong i=0UL; i<32UL; i++ ) be[ 1UL+i ] = _a[ 32UL-i ];
128 0 : _a = be;
129 0 : }
130 :
131 0 : fd_secp256r1_point_t a[1];
132 0 : if( FD_UNLIKELY( !fd_secp256r1_point_frombytes( a, _a ) ) ) {
133 0 : return -1;
134 0 : }
135 :
136 0 : fd_secp256r1_point_tobytes_syscall( _r, a, big_endian );
137 0 : return 0;
138 0 : }
139 :
140 : int
141 : fd_secp256r1_add_syscall( uchar _r[ 64 ],
142 : uchar const _a[ 64 ],
143 : uchar const _b[ 64 ],
144 0 : int big_endian ) {
145 0 : ulong a[ 8 ], b[ 8 ];
146 0 : if( FD_UNLIKELY( !fd_secp256r1_affine_frombytes( a, _a, big_endian ) ) ) {
147 0 : return -1;
148 0 : }
149 0 : if( FD_UNLIKELY( !fd_secp256r1_affine_frombytes( b, _b, big_endian ) ) ) {
150 0 : return -1;
151 0 : }
152 :
153 0 : fd_secp256r1_point_t r[1];
154 0 : fd_secp256r1_point_from_affine( r, a );
155 0 : fd_secp256r1_point_add_mixed( r, r, b );
156 :
157 0 : fd_secp256r1_point_tobytes_syscall( _r, r, big_endian );
158 0 : return 0;
159 0 : }
160 :
161 : int
162 : fd_secp256r1_sub_syscall( uchar _r[ 64 ],
163 : uchar const _a[ 64 ],
164 : uchar const _b[ 64 ],
165 0 : int big_endian ) {
166 0 : ulong a[ 8 ], b[ 8 ];
167 0 : if( FD_UNLIKELY( !fd_secp256r1_affine_frombytes( a, _a, big_endian ) ) ) {
168 0 : return -1;
169 0 : }
170 0 : if( FD_UNLIKELY( !fd_secp256r1_affine_frombytes( b, _b, big_endian ) ) ) {
171 0 : return -1;
172 0 : }
173 :
174 : /* -b, it works also with b=0 */
175 0 : fd_secp256r1_fp_t y[1];
176 0 : memcpy( y->limbs, b+4, 32 );
177 0 : fd_secp256r1_fp_neg( y, y );
178 0 : memcpy( b+4, y->limbs, 32 );
179 :
180 0 : fd_secp256r1_point_t r[1];
181 0 : fd_secp256r1_point_from_affine( r, a );
182 0 : fd_secp256r1_point_add_mixed( r, r, b );
183 :
184 0 : fd_secp256r1_point_tobytes_syscall( _r, r, big_endian );
185 0 : return 0;
186 0 : }
187 :
188 : int
189 : fd_secp256r1_mul_syscall( uchar _r[ 64 ],
190 : uchar const _n[ 32 ],
191 : uchar const _a[ 64 ],
192 0 : int big_endian ) {
193 0 : fd_secp256r1_scalar_t n[1];
194 0 : ulong a[ 8 ];
195 0 : if( FD_UNLIKELY( !fd_secp256r1_scalar_frombytes_syscall( n, _n, big_endian ) ) ) {
196 0 : return -1;
197 0 : }
198 0 : if( FD_UNLIKELY( !fd_secp256r1_affine_frombytes( a, _a, big_endian ) ) ) {
199 0 : return -1;
200 0 : }
201 :
202 0 : fd_secp256r1_point_t p[1], r[1];
203 0 : fd_secp256r1_point_from_affine( p, a );
204 0 : fd_secp256r1_point_scalarmul( r, n->limbs, p );
205 :
206 0 : fd_secp256r1_point_tobytes_syscall( _r, r, big_endian );
207 0 : return 0;
208 0 : }
209 :
210 : /* Points per MSM batch, bounds the stack: 32*16*64B = 32kB of tables. */
211 0 : #define FD_SECP256R1_MSM_BATCH_SZ 32UL
212 :
213 : /* tbl[k] = k*P for k in [0,16), affine-Montgomery, (0,0) for infinity.
214 : Entries are computed in Jacobian and normalized with one inversion. */
215 : static void
216 : fd_secp256r1_msm_table( ulong tbl[ 16 ][ 8 ],
217 0 : ulong const p[ 8 ] ) {
218 0 : fd_secp256r1_point_t jac[ 16 ];
219 0 : fd_secp256r1_point_from_affine( jac+1, p );
220 0 : if( FD_UNLIKELY( fd_secp256r1_point_is_inf( jac+1 ) ) ) {
221 0 : memset( tbl, 0, 16*64 );
222 0 : return;
223 0 : }
224 0 : for( ulong k=2UL; k<16UL; k++ ) {
225 0 : if( k&1UL ) fd_secp256r1_point_add_mixed( jac+k, jac+k-1, p );
226 0 : else fd_secp256r1_point_double( jac+k, jac+(k>>1) );
227 0 : }
228 :
229 : /* P has prime order > 16, so no entry in [1,16) is infinity. */
230 0 : fd_secp256r1_fp_t acc[ 16 ], inv[1], zinv[1], zinv2[1], t[1];
231 0 : fd_secp256r1_fp_set( acc, fd_secp256r1_const_one_mont );
232 0 : for( ulong k=1UL; k<16UL; k++ ) fd_secp256r1_fp_mul( acc+k, acc+k-1, jac[k].z );
233 0 : fd_secp256r1_fp_inv( inv, acc+15 );
234 0 : for( ulong k=15UL; k; k-- ) {
235 0 : fd_secp256r1_fp_mul( zinv, inv, acc+k-1 );
236 0 : fd_secp256r1_fp_mul( inv, inv, jac[k].z );
237 0 : fd_secp256r1_fp_sqr( zinv2, zinv );
238 0 : fd_secp256r1_fp_mul( t, jac[k].x, zinv2 ); memcpy( tbl[k], t->limbs, 32 );
239 0 : fd_secp256r1_fp_mul( t, zinv2, zinv );
240 0 : fd_secp256r1_fp_mul( t, t, jac[k].y ); memcpy( tbl[k]+4, t->limbs, 32 );
241 0 : }
242 0 : memset( tbl[0], 0, 64 );
243 0 : }
244 :
245 : /* Straus with 4-bit windows, variable time: inputs are public. */
246 : int
247 : fd_secp256r1_msm_syscall( uchar _r[ 64 ],
248 : uchar const _n[], /* 32*cnt */
249 : uchar const _a[], /* 64*cnt */
250 : ulong cnt,
251 0 : int big_endian ) {
252 0 : fd_secp256r1_point_t r[1];
253 0 : fd_secp256r1_point_set_inf( r );
254 :
255 0 : for( ulong off=0UL; off<cnt; off+=FD_SECP256R1_MSM_BATCH_SZ ) {
256 0 : ulong bcnt = fd_ulong_min( cnt-off, FD_SECP256R1_MSM_BATCH_SZ );
257 0 : fd_secp256r1_scalar_t n[ FD_SECP256R1_MSM_BATCH_SZ ];
258 0 : ulong tbl[ FD_SECP256R1_MSM_BATCH_SZ ][ 16 ][ 8 ];
259 :
260 0 : for( ulong i=0UL; i<bcnt; i++ ) {
261 0 : ulong a[ 8 ];
262 0 : if( FD_UNLIKELY( !fd_secp256r1_scalar_frombytes_syscall( n+i, _n+32UL*(off+i), big_endian ) ) ) {
263 0 : return -1;
264 0 : }
265 0 : if( FD_UNLIKELY( !fd_secp256r1_affine_frombytes( a, _a+64UL*(off+i), big_endian ) ) ) {
266 0 : return -1;
267 0 : }
268 0 : fd_secp256r1_msm_table( tbl[i], a );
269 0 : }
270 :
271 0 : fd_secp256r1_point_t acc[1];
272 0 : fd_secp256r1_point_set_inf( acc );
273 0 : for( ulong w=64UL; w; w-- ) { /* nibbles, most significant first */
274 0 : if( FD_LIKELY( !fd_secp256r1_point_is_inf( acc ) ) ) {
275 0 : fd_secp256r1_point_double( acc, acc );
276 0 : fd_secp256r1_point_double( acc, acc );
277 0 : fd_secp256r1_point_double( acc, acc );
278 0 : fd_secp256r1_point_double( acc, acc );
279 0 : }
280 0 : for( ulong i=0UL; i<bcnt; i++ ) {
281 0 : ulong d = ( n[i].limbs[ (w-1UL)>>4 ] >> ( 4UL*((w-1UL)&15UL) ) ) & 15UL;
282 0 : if( d ) fd_secp256r1_point_add_mixed( acc, acc, tbl[i][d] );
283 0 : }
284 0 : }
285 0 : fd_secp256r1_point_add( r, r, acc );
286 0 : }
287 :
288 0 : fd_secp256r1_point_tobytes_syscall( _r, r, big_endian );
289 0 : return 0;
290 0 : }
|
