Line data Source code
1 : #include "fd_curve25519.h"
2 : #include "../hex/fd_hex.h"
3 :
4 : /*
5 : * Secure implementations (const time + clean temp vars)
6 : */
7 : #include "fd_curve25519_secure.c"
8 :
9 : #if FD_HAS_AVX512
10 : #include "avx512/fd_curve25519.c"
11 : #else
12 : #include "ref/fd_curve25519.c"
13 : #endif
14 :
15 2074275 : #define WNAF_BIT_SZ 4
16 1843800 : #define WNAF_TBL_SZ (2*WNAF_BIT_SZ)
17 :
18 : /*
19 : * Ser/de
20 : */
21 :
22 : void
23 : fd_ed25519_debug( char const * name,
24 0 : fd_ed25519_point_t const * a ) {
25 0 : fd_f25519_t x[1], y[1], z[1], t[1];
26 0 : fd_ed25519_point_to( x, y, z, t, a );
27 0 : FD_LOG_WARNING(( "%s", name ));
28 0 : fd_f25519_debug( "x", x );
29 0 : fd_f25519_debug( "y", y );
30 0 : fd_f25519_debug( "z", z );
31 0 : fd_f25519_debug( "t", t );
32 0 : }
33 :
34 : fd_ed25519_point_t *
35 : fd_ed25519_point_frombytes( fd_ed25519_point_t * r,
36 37670 : uchar const buf[ 32 ] ) {
37 37670 : fd_f25519_t x[1], y[1], t[1];
38 37670 : fd_f25519_frombytes( y, buf );
39 37670 : uchar expected_x_sign = buf[31] >> 7;
40 :
41 37670 : fd_f25519_t u[1];
42 37670 : fd_f25519_t v[1];
43 37670 : fd_f25519_sqr( u, y );
44 37670 : fd_f25519_mul( v, u, fd_f25519_d );
45 37670 : fd_f25519_sub( u, u, fd_f25519_one ); /* u = y^2-1 */
46 37670 : fd_f25519_add( v, v, fd_f25519_one ); /* v = dy^2+1 */
47 :
48 37670 : int was_square = fd_f25519_sqrt_ratio( x, u, v );
49 37670 : if( FD_UNLIKELY( !was_square ) ) {
50 490 : return NULL;
51 490 : }
52 :
53 : /* Note: RFC 8032 Section 5.1.3 says "if x=0 and x_0=1, decoding
54 : fails", but Dalek does not enforce this — neg(0)==0 so it silently
55 : accepts the point. We match Dalek for compatibility.
56 : https://github.com/dalek-cryptography/curve25519-dalek/blob/curve25519-4.1.3/curve25519-dalek/src/edwards.rs#L194-L240
57 : https://github.com/dalek-cryptography/curve25519-dalek/blob/3.2.1/src/edwards.rs#L193-L209 */
58 37180 : if( fd_f25519_sgn(x)!=expected_x_sign ) { /* 50% prob */
59 21146 : fd_f25519_neg( x, x );
60 21146 : }
61 :
62 37180 : fd_f25519_mul( t, x, y );
63 37180 : fd_ed25519_point_from( r, x, y, fd_f25519_one, t );
64 :
65 37180 : return r;
66 37670 : }
67 :
68 : uchar *
69 : fd_ed25519_point_tobytes_batch8( uchar out[], /* 32*n */
70 : fd_ed25519_point_t const * pt, /* n */
71 42 : ulong n ) { /* in [1,8] */
72 42 : FD_TEST( 0UL<n && n<=8UL );
73 :
74 42 : fd_f25519_t x[8], y[8], z[8], t[1];
75 252 : for( ulong i=0UL; i<n; i++ ) fd_ed25519_point_to( &x[i], &y[i], &z[i], t, &pt[i] );
76 :
77 : /* batch inv */
78 :
79 42 : fd_f25519_t c[8], iz[8], u[1];
80 42 : c[0] = z[0];
81 210 : for( ulong i=1UL; i<n; i++ ) fd_f25519_mul( &c[i], &c[i-1], &z[i] );
82 42 : fd_f25519_inv( u, &c[n-1UL] );
83 210 : for( ulong i=n-1UL; i>0UL; i-- ) {
84 168 : fd_f25519_mul( &iz[i], u, &c[i-1] );
85 168 : fd_f25519_mul( u, u, &z[i] );
86 168 : }
87 42 : iz[0] = *u;
88 :
89 42 : ulong i=0UL;
90 138 : for( ; i+2UL<=n; i+=2UL ) fd_f25519_mul4( &x[i ], &x[i ], &iz[i ],
91 96 : &y[i ], &y[i ], &iz[i ],
92 96 : &x[i+1], &x[i+1], &iz[i+1],
93 96 : &y[i+1], &y[i+1], &iz[i+1] );
94 42 : if( i<n ) fd_f25519_mul2( &x[i], &x[i], &iz[i],
95 18 : &y[i], &y[i], &iz[i] );
96 :
97 252 : for( ulong j=0UL; j<n; j++ ) {
98 210 : fd_f25519_tobytes( out+32UL*j, &y[j] );
99 210 : out[ 32UL*j+31UL ] ^= (uchar)(fd_f25519_sgn( &x[j] ) << 7);
100 210 : }
101 42 : return out;
102 42 : }
103 :
104 : uchar *
105 : fd_ed25519_point_tobytes( uchar out[ 32 ],
106 210024 : fd_ed25519_point_t const * a ) {
107 : /* equivalent to: return fd_ed25519_point_tobytes_batch8( out, a, 1UL ) */
108 210024 : fd_f25519_t x[1], y[1], z[1], t[1];
109 210024 : fd_ed25519_point_to( x, y, z, t, a );
110 210024 : fd_f25519_inv( t, z );
111 210024 : fd_f25519_mul2( x, x, t,
112 210024 : y, y, t );
113 210024 : fd_f25519_tobytes( out, y );
114 210024 : out[31] ^= (uchar)(fd_f25519_sgn( x ) << 7);
115 210024 : return out;
116 210024 : }
117 :
118 : /*
119 : * Scalar multiplication
120 : */
121 :
122 : fd_ed25519_point_t *
123 : fd_ed25519_scalar_mul( fd_ed25519_point_t * r,
124 : uchar const n[ 32 ],
125 30024 : fd_ed25519_point_t const * a ) {
126 30024 : short nslide[256];
127 30024 : fd_curve25519_scalar_wnaf( nslide, n, WNAF_BIT_SZ );
128 :
129 30024 : fd_ed25519_point_t ai[WNAF_TBL_SZ]; /* A,3A,5A,7A,9A,11A,13A,15A */
130 30024 : fd_ed25519_point_t a2[1]; /* 2A (temp) */
131 30024 : fd_ed25519_point_t t[1];
132 :
133 : /* pre-computed table */
134 30024 : fd_ed25519_point_set( &ai[0], a );
135 30024 : fd_ed25519_point_dbln( a2, a, 1 ); // note: a is affine, we could save 1mul
136 30024 : fd_curve25519_into_precomputed( &ai[0] );
137 240192 : for( int i=1; i<WNAF_TBL_SZ; i++ ) {
138 210168 : fd_ed25519_point_add_with_opts( t, a2, &ai[i-1], i==1, 1, 1 );
139 210168 : fd_ed25519_point_add_final_mul( &ai[i], t );
140 : /* pre-compute kT, to save 1mul during the loop */
141 210168 : fd_curve25519_into_precomputed( &ai[i] );
142 210168 : }
143 :
144 : /* main dbl-and-add loop. note: last iter unrolled */
145 30024 : fd_ed25519_point_set_zero( r );
146 30024 : int i;
147 121686 : for( i=255; i>=0; i-- ) { if( nslide[i] ) break; }
148 7624506 : for( ; i>=0; i-- ) {
149 7594482 : fd_ed25519_partial_dbl( t, r );
150 7594482 : if( nslide[i] > 0 ) { fd_ed25519_point_add_final_mul( r, t ); fd_ed25519_point_add_with_opts( t, r, &ai[ nslide[i] / 2], nslide[i]==1, 1, 1 ); }
151 7294194 : else if( nslide[i] < 0 ) { fd_ed25519_point_add_final_mul( r, t ); fd_ed25519_point_sub_with_opts( t, r, &ai[(-nslide[i]) / 2], nslide[i]==-1, 1, 1 ); }
152 :
153 : /* ignore r->T because dbl doesn't need it, except in the last cycle */
154 7594482 : if (i == 0) {
155 30024 : fd_ed25519_point_add_final_mul( r, t ); // compute r->T
156 7564458 : } else {
157 7564458 : fd_ed25519_point_add_final_mul_projective( r, t ); // ignore r->T
158 7564458 : }
159 7594482 : }
160 30024 : return r;
161 30024 : }
162 :
163 : fd_ed25519_point_t *
164 : fd_ed25519_double_scalar_mul_base( fd_ed25519_point_t * r,
165 : uchar const n1[ 32 ],
166 : fd_ed25519_point_t const * a,
167 23319 : uchar const n2[ 32 ] ) {
168 :
169 23319 : short n1slide[256]; fd_curve25519_scalar_wnaf( n1slide, n1, WNAF_BIT_SZ );
170 23319 : short n2slide[256]; fd_curve25519_scalar_wnaf( n2slide, n2, 8 );
171 :
172 23319 : fd_ed25519_point_t ai[WNAF_TBL_SZ]; /* A,3A,5A,7A,9A,11A,13A,15A */
173 23319 : fd_ed25519_point_t a2[1]; /* 2A (temp) */
174 23319 : fd_ed25519_point_t t[1];
175 :
176 : /* pre-computed table */
177 23319 : fd_ed25519_point_set( &ai[0], a );
178 23319 : fd_ed25519_point_dbln( a2, a, 1 ); // note: a is affine, we could save 1mul
179 23319 : fd_curve25519_into_precomputed( &ai[0] );
180 186552 : for( int i=1; i<WNAF_TBL_SZ; i++ ) {
181 163233 : fd_ed25519_point_add_with_opts( t, a2, &ai[i-1], i==1, 1, 1 );
182 163233 : fd_ed25519_point_add_final_mul( &ai[i], t );
183 : /* pre-compute kT, to save 1mul during the loop */
184 163233 : fd_curve25519_into_precomputed( &ai[i] );
185 163233 : }
186 :
187 : /* main dbl-and-add loop */
188 23319 : fd_ed25519_point_set_zero( r );
189 :
190 23319 : int i;
191 141623 : for( i=255; i>=0; i-- ) { if( n1slide[i] || n2slide[i] ) break; }
192 5874679 : for( ; i>=0; i-- ) {
193 5851360 : fd_ed25519_partial_dbl( t, r );
194 5851360 : if( n1slide[i] > 0 ) { fd_ed25519_point_add_final_mul( r, t ); fd_ed25519_point_add_with_opts( t, r, &ai[ n1slide[i] / 2], n1slide[i]==1, 1, 1 ); }
195 5349233 : else if( n1slide[i] < 0 ) { fd_ed25519_point_add_final_mul( r, t ); fd_ed25519_point_sub_with_opts( t, r, &ai[(-n1slide[i]) / 2], n1slide[i]==-1, 1, 1 ); }
196 5851360 : if( n2slide[i] > 0 ) { fd_ed25519_point_add_final_mul( r, t ); fd_ed25519_point_add_with_opts( t, r, &fd_ed25519_base_point_wnaf_table[ n2slide[i] / 2], 1, 1, 1 ); }
197 5538000 : else if( n2slide[i] < 0 ) { fd_ed25519_point_add_final_mul( r, t ); fd_ed25519_point_sub_with_opts( t, r, &fd_ed25519_base_point_wnaf_table[(-n2slide[i]) / 2], 1, 1, 1 ); }
198 :
199 : /* ignore r->T because dbl doesn't need it, except in the last cycle */
200 5851360 : if (i == 0) {
201 23319 : fd_ed25519_point_add_final_mul( r, t ); // compute r->T
202 5828041 : } else {
203 5828041 : fd_ed25519_point_add_final_mul_projective( r, t ); // ignore r->T
204 5828041 : }
205 5851360 : }
206 23319 : return r;
207 23319 : }
208 :
209 :
210 : FD_25519_INLINE fd_ed25519_point_t *
211 : fd_ed25519_multi_scalar_mul_with_opts( fd_ed25519_point_t * r,
212 : uchar const n[], /* sz * 32 */
213 : fd_ed25519_point_t const a[], /* sz */
214 : ulong const sz,
215 5559 : ulong const base_sz ) {
216 5559 : short nslide[FD_BALLET_CURVE25519_MSM_BATCH_SZ][256];
217 5559 : fd_ed25519_point_t ai[FD_BALLET_CURVE25519_MSM_BATCH_SZ][WNAF_TBL_SZ]; /* A,3A,5A,7A,9A,11A,13A,15A */
218 5559 : fd_ed25519_point_t a2[1]; /* 2A (temp) */
219 5559 : fd_ed25519_point_t t[1]; /* temp */
220 :
221 5559 : if( base_sz ) {
222 0 : fd_curve25519_scalar_wnaf( nslide[0], &n[32*0], 8 );
223 0 : }
224 182691 : for( ulong j=base_sz; j<sz; j++ ) {
225 177132 : fd_curve25519_scalar_wnaf( nslide[j], &n[32*j], WNAF_BIT_SZ );
226 :
227 : /* pre-computed table */
228 177132 : fd_ed25519_point_set( &ai[j][0], &a[j] );
229 177132 : fd_ed25519_point_dbln( a2, &a[j], 1 ); // note: a is affine, we could save 1mul
230 177132 : fd_curve25519_into_precomputed( &ai[j][0] );
231 1417056 : for( int i=1; i<WNAF_TBL_SZ; i++ ) {
232 1239924 : fd_ed25519_point_add_with_opts( t, a2, &ai[j][i-1], i==1, 1, 1 );
233 1239924 : fd_ed25519_point_add_final_mul( &ai[j][i], t );
234 : /* pre-compute kT, to save 1mul during the loop */
235 1239924 : fd_curve25519_into_precomputed( &ai[j][i] );
236 1239924 : }
237 177132 : }
238 :
239 : /* main dbl-and-add loop */
240 5559 : fd_ed25519_point_set_zero( r );
241 1428663 : for( int i=255; i>=0; i-- ) {
242 1423104 : fd_ed25519_partial_dbl( t, r );
243 1423104 : if( base_sz ) {
244 0 : if( nslide[0][i] > 0 ) { fd_ed25519_point_add_final_mul( r, t ); fd_ed25519_point_add_with_opts( t, r, &fd_ed25519_base_point_wnaf_table[ nslide[0][i] / 2], 1, 1, 1 ); }
245 0 : else if( nslide[0][i] < 0 ) { fd_ed25519_point_add_final_mul( r, t ); fd_ed25519_point_sub_with_opts( t, r, &fd_ed25519_base_point_wnaf_table[(-nslide[0][i]) / 2], 1, 1, 1 ); }
246 0 : }
247 46768896 : for( ulong j=base_sz; j<sz; j++ ) {
248 45345792 : short n = nslide[j][i];
249 45345792 : if( n > 0 ) { fd_ed25519_point_add_final_mul( r, t ); fd_ed25519_point_add_with_opts( t, r, &ai[j][ n / 2], (n==1), 1, 1 ); }
250 41551481 : else if( n < 0 ) { fd_ed25519_point_add_final_mul( r, t ); fd_ed25519_point_sub_with_opts( t, r, &ai[j][(-n) / 2], (n==-1), 1, 1 ); }
251 45345792 : }
252 :
253 : /* ignore r->T because dbl doesn't need it, except in the last cycle */
254 1423104 : if (i == 0) {
255 5559 : fd_ed25519_point_add_final_mul( r, t ); // compute r->T
256 1417545 : } else {
257 1417545 : fd_ed25519_point_add_final_mul_projective( r, t ); // ignore r->T
258 1417545 : }
259 1423104 : }
260 5559 : return r;
261 5559 : }
262 :
263 : fd_ed25519_point_t *
264 : fd_ed25519_multi_scalar_mul( fd_ed25519_point_t * r,
265 : uchar const n[], /* sz * 32 */
266 : fd_ed25519_point_t const a[], /* sz */
267 1869 : ulong const sz ) {
268 :
269 1869 : fd_ed25519_point_t h[1];
270 1869 : fd_ed25519_point_set_zero( r );
271 :
272 7428 : for( ulong i=0; i<sz; i+=FD_BALLET_CURVE25519_MSM_BATCH_SZ ) {
273 5559 : ulong batch_sz = fd_ulong_min(sz-i, FD_BALLET_CURVE25519_MSM_BATCH_SZ);
274 :
275 5559 : fd_ed25519_multi_scalar_mul_with_opts( h, &n[ 32*i ], &a[ i ], batch_sz, 0 );
276 5559 : fd_ed25519_point_add( r, r, h );
277 5559 : }
278 :
279 1869 : return r;
280 1869 : }
281 :
282 : /*
283 : * Init
284 : */
285 :
286 : fd_ed25519_point_t *
287 : fd_curve25519_affine_add( fd_ed25519_point_t * r,
288 : fd_ed25519_point_t const * a,
289 0 : fd_ed25519_point_t const * b ) {
290 0 : fd_ed25519_point_add_with_opts( r, a, b, 1, 0, 0 );
291 0 : return fd_curve25519_into_affine( r );
292 0 : }
293 :
294 : fd_ed25519_point_t *
295 : fd_curve25519_affine_dbln( fd_ed25519_point_t * r,
296 : fd_ed25519_point_t const * a,
297 0 : int const n ) {
298 0 : fd_ed25519_point_dbln( r, a, n );
299 0 : return fd_curve25519_into_affine( r );
300 0 : }
|
