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 8782425 : #define WNAF_BIT_SZ 4
16 7806600 : #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 1131093 : uchar const buf[ 32 ] ) {
37 1131093 : fd_f25519_t x[1], y[1], t[1];
38 1131093 : fd_f25519_frombytes( y, buf );
39 1131093 : uchar expected_x_sign = buf[31] >> 7;
40 :
41 1131093 : fd_f25519_t u[1];
42 1131093 : fd_f25519_t v[1];
43 1131093 : fd_f25519_sqr( u, y );
44 1131093 : fd_f25519_mul( v, u, fd_f25519_d );
45 1131093 : fd_f25519_sub( u, u, fd_f25519_one ); /* u = y^2-1 */
46 1131093 : fd_f25519_add( v, v, fd_f25519_one ); /* v = dy^2+1 */
47 :
48 1131093 : int was_square = fd_f25519_sqrt_ratio( x, u, v );
49 1131093 : if( FD_UNLIKELY( !was_square ) ) {
50 89164 : return NULL;
51 89164 : }
52 :
53 1041929 : if( fd_f25519_sgn(x)!=expected_x_sign ) { /* 50% prob */
54 631966 : fd_f25519_neg( x, x );
55 631966 : }
56 :
57 1041929 : fd_f25519_mul( t, x, y );
58 1041929 : fd_ed25519_point_from( r, x, y, fd_f25519_one, t );
59 :
60 1041929 : return r;
61 1131093 : }
62 :
63 : uchar *
64 : fd_ed25519_point_tobytes( uchar out[ 32 ],
65 1709400 : fd_ed25519_point_t const * a ) {
66 1709400 : fd_f25519_t x[1], y[1], z[1], t[1];
67 1709400 : fd_ed25519_point_to( x, y, z, t, a );
68 1709400 : fd_f25519_inv( t, z );
69 1709400 : fd_f25519_mul2( x, x, t,
70 1709400 : y, y, t );
71 1709400 : fd_f25519_tobytes( out, y );
72 1709400 : out[31] ^= (uchar)(fd_f25519_sgn( x ) << 7);
73 1709400 : return out;
74 1709400 : }
75 :
76 : /*
77 : * Scalar multiplication
78 : */
79 :
80 : fd_ed25519_point_t *
81 : fd_ed25519_scalar_mul( fd_ed25519_point_t * r,
82 : uchar const n[ 32 ],
83 30024 : fd_ed25519_point_t const * a ) {
84 30024 : short nslide[256];
85 30024 : fd_curve25519_scalar_wnaf( nslide, n, WNAF_BIT_SZ );
86 :
87 30024 : fd_ed25519_point_t ai[WNAF_TBL_SZ]; /* A,3A,5A,7A,9A,11A,13A,15A */
88 30024 : fd_ed25519_point_t a2[1]; /* 2A (temp) */
89 30024 : fd_ed25519_point_t t[1];
90 :
91 : /* pre-computed table */
92 30024 : fd_ed25519_point_set( &ai[0], a );
93 30024 : fd_ed25519_point_dbln( a2, a, 1 ); // note: a is affine, we could save 1mul
94 30024 : fd_curve25519_into_precomputed( &ai[0] );
95 240192 : for( int i=1; i<WNAF_TBL_SZ; i++ ) {
96 210168 : fd_ed25519_point_add_with_opts( t, a2, &ai[i-1], i==1, 1, 1 );
97 210168 : fd_ed25519_point_add_final_mul( &ai[i], t );
98 : /* pre-compute kT, to save 1mul during the loop */
99 210168 : fd_curve25519_into_precomputed( &ai[i] );
100 210168 : }
101 :
102 : /* main dbl-and-add loop. note: last iter unrolled */
103 30024 : fd_ed25519_point_set_zero( r );
104 30024 : int i;
105 121686 : for( i=255; i>=0; i-- ) { if( nslide[i] ) break; }
106 7624506 : for( ; i>=0; i-- ) {
107 7594482 : fd_ed25519_partial_dbl( t, r );
108 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 ); }
109 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 ); }
110 :
111 : /* ignore r->T because dbl doesn't need it, except in the last cycle */
112 7594482 : if (i == 0) {
113 30024 : fd_ed25519_point_add_final_mul( r, t ); // compute r->T
114 7564458 : } else {
115 7564458 : fd_ed25519_point_add_final_mul_projective( r, t ); // ignore r->T
116 7564458 : }
117 7594482 : }
118 30024 : return r;
119 30024 : }
120 :
121 : fd_ed25519_point_t *
122 : fd_ed25519_double_scalar_mul_base( fd_ed25519_point_t * r,
123 : uchar const n1[ 32 ],
124 : fd_ed25519_point_t const * a,
125 768744 : uchar const n2[ 32 ] ) {
126 :
127 768744 : short n1slide[256]; fd_curve25519_scalar_wnaf( n1slide, n1, WNAF_BIT_SZ );
128 768744 : short n2slide[256]; fd_curve25519_scalar_wnaf( n2slide, n2, 8 );
129 :
130 768744 : fd_ed25519_point_t ai[WNAF_TBL_SZ]; /* A,3A,5A,7A,9A,11A,13A,15A */
131 768744 : fd_ed25519_point_t a2[1]; /* 2A (temp) */
132 768744 : fd_ed25519_point_t t[1];
133 :
134 : /* pre-computed table */
135 768744 : fd_ed25519_point_set( &ai[0], a );
136 768744 : fd_ed25519_point_dbln( a2, a, 1 ); // note: a is affine, we could save 1mul
137 768744 : fd_curve25519_into_precomputed( &ai[0] );
138 6149952 : for( int i=1; i<WNAF_TBL_SZ; i++ ) {
139 5381208 : fd_ed25519_point_add_with_opts( t, a2, &ai[i-1], i==1, 1, 1 );
140 5381208 : fd_ed25519_point_add_final_mul( &ai[i], t );
141 : /* pre-compute kT, to save 1mul during the loop */
142 5381208 : fd_curve25519_into_precomputed( &ai[i] );
143 5381208 : }
144 :
145 : /* main dbl-and-add loop */
146 768744 : fd_ed25519_point_set_zero( r );
147 :
148 768744 : int i;
149 4779277 : for( i=255; i>=0; i-- ) { if( n1slide[i] || n2slide[i] ) break; }
150 193556675 : for( ; i>=0; i-- ) {
151 192787931 : fd_ed25519_partial_dbl( t, r );
152 192787931 : 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 ); }
153 176016578 : 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 ); }
154 192787931 : 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 ); }
155 182644623 : 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 ); }
156 :
157 : /* ignore r->T because dbl doesn't need it, except in the last cycle */
158 192787931 : if (i == 0) {
159 768744 : fd_ed25519_point_add_final_mul( r, t ); // compute r->T
160 192019187 : } else {
161 192019187 : fd_ed25519_point_add_final_mul_projective( r, t ); // ignore r->T
162 192019187 : }
163 192787931 : }
164 768744 : return r;
165 768744 : }
166 :
167 :
168 : FD_25519_INLINE fd_ed25519_point_t *
169 : fd_ed25519_multi_scalar_mul_with_opts( fd_ed25519_point_t * r,
170 : uchar const n[], /* sz * 32 */
171 : fd_ed25519_point_t const a[], /* sz */
172 : ulong const sz,
173 5553 : ulong const base_sz ) {
174 5553 : short nslide[FD_BALLET_CURVE25519_MSM_BATCH_SZ][256];
175 5553 : fd_ed25519_point_t ai[FD_BALLET_CURVE25519_MSM_BATCH_SZ][WNAF_TBL_SZ]; /* A,3A,5A,7A,9A,11A,13A,15A */
176 5553 : fd_ed25519_point_t a2[1]; /* 2A (temp) */
177 5553 : fd_ed25519_point_t t[1]; /* temp */
178 :
179 5553 : if( base_sz ) {
180 0 : fd_curve25519_scalar_wnaf( nslide[0], &n[32*0], 8 );
181 0 : }
182 182610 : for( ulong j=base_sz; j<sz; j++ ) {
183 177057 : fd_curve25519_scalar_wnaf( nslide[j], &n[32*j], WNAF_BIT_SZ );
184 :
185 : /* pre-computed table */
186 177057 : fd_ed25519_point_set( &ai[j][0], &a[j] );
187 177057 : fd_ed25519_point_dbln( a2, &a[j], 1 ); // note: a is affine, we could save 1mul
188 177057 : fd_curve25519_into_precomputed( &ai[j][0] );
189 1416456 : for( int i=1; i<WNAF_TBL_SZ; i++ ) {
190 1239399 : fd_ed25519_point_add_with_opts( t, a2, &ai[j][i-1], i==1, 1, 1 );
191 1239399 : fd_ed25519_point_add_final_mul( &ai[j][i], t );
192 : /* pre-compute kT, to save 1mul during the loop */
193 1239399 : fd_curve25519_into_precomputed( &ai[j][i] );
194 1239399 : }
195 177057 : }
196 :
197 : /* main dbl-and-add loop */
198 5553 : fd_ed25519_point_set_zero( r );
199 1427121 : for( int i=255; i>=0; i-- ) {
200 1421568 : fd_ed25519_partial_dbl( t, r );
201 1421568 : if( base_sz ) {
202 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 ); }
203 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 ); }
204 0 : }
205 46748160 : for( ulong j=base_sz; j<sz; j++ ) {
206 45326592 : short n = nslide[j][i];
207 45326592 : 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 ); }
208 41533682 : 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 ); }
209 45326592 : }
210 :
211 : /* ignore r->T because dbl doesn't need it, except in the last cycle */
212 1421568 : if (i == 0) {
213 5553 : fd_ed25519_point_add_final_mul( r, t ); // compute r->T
214 1416015 : } else {
215 1416015 : fd_ed25519_point_add_final_mul_projective( r, t ); // ignore r->T
216 1416015 : }
217 1421568 : }
218 5553 : return r;
219 5553 : }
220 :
221 : fd_ed25519_point_t *
222 : fd_ed25519_multi_scalar_mul( fd_ed25519_point_t * r,
223 : uchar const n[], /* sz * 32 */
224 : fd_ed25519_point_t const a[], /* sz */
225 1863 : ulong const sz ) {
226 :
227 1863 : fd_ed25519_point_t h[1];
228 1863 : fd_ed25519_point_set_zero( r );
229 :
230 7416 : for( ulong i=0; i<sz; i+=FD_BALLET_CURVE25519_MSM_BATCH_SZ ) {
231 5553 : ulong batch_sz = fd_ulong_min(sz-i, FD_BALLET_CURVE25519_MSM_BATCH_SZ);
232 :
233 5553 : fd_ed25519_multi_scalar_mul_with_opts( h, &n[ 32*i ], &a[ i ], batch_sz, 0 );
234 5553 : fd_ed25519_point_add( r, r, h );
235 5553 : }
236 :
237 1863 : return r;
238 1863 : }
239 :
240 : fd_ed25519_point_t *
241 : fd_ed25519_multi_scalar_mul_base( fd_ed25519_point_t * r,
242 : uchar const n[], /* sz * 32 */
243 : fd_ed25519_point_t const a[], /* sz */
244 0 : ulong const sz ) {
245 0 : if (sz > FD_BALLET_CURVE25519_MSM_BATCH_SZ) {
246 0 : return NULL;
247 0 : }
248 0 : return fd_ed25519_multi_scalar_mul_with_opts( r, n, a, sz, 1 );
249 0 : }
250 :
251 : /*
252 : * Init
253 : */
254 :
255 : fd_ed25519_point_t *
256 : fd_curve25519_affine_add( fd_ed25519_point_t * r,
257 : fd_ed25519_point_t const * a,
258 0 : fd_ed25519_point_t const * b ) {
259 0 : fd_ed25519_point_add_with_opts( r, a, b, 1, 0, 0 );
260 0 : return fd_curve25519_into_affine( r );
261 0 : }
262 :
263 : fd_ed25519_point_t *
264 : fd_curve25519_affine_dbln( fd_ed25519_point_t * r,
265 : fd_ed25519_point_t const * a,
266 0 : int const n ) {
267 0 : fd_ed25519_point_dbln( r, a, n );
268 0 : return fd_curve25519_into_affine( r );
269 0 : }
|
