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 9177597 : #define WNAF_BIT_SZ 4
16 8157864 : #define WNAF_TBL_SZ (2*WNAF_BIT_SZ)
17 :
18 : /*
19 : * Ser/de
20 : */
21 :
22 : fd_ed25519_point_t *
23 : fd_ed25519_point_frombytes( fd_ed25519_point_t * r,
24 1138245 : uchar const buf[ 32 ] ) {
25 1138245 : fd_f25519_t x[1], y[1], t[1];
26 1138245 : fd_f25519_frombytes( y, buf );
27 1138245 : uchar expected_x_sign = buf[31] >> 7;
28 :
29 1138245 : fd_f25519_t u[1];
30 1138245 : fd_f25519_t v[1];
31 1138245 : fd_f25519_sqr( u, y );
32 1138245 : fd_f25519_mul( v, u, fd_f25519_d );
33 1138245 : fd_f25519_sub( u, u, fd_f25519_one ); /* u = y^2-1 */
34 1138245 : fd_f25519_add( v, v, fd_f25519_one ); /* v = dy^2+1 */
35 :
36 1138245 : int was_square = fd_f25519_sqrt_ratio( x, u, v );
37 1138245 : if( FD_UNLIKELY( !was_square ) ) {
38 89902 : return NULL;
39 89902 : }
40 :
41 1048343 : if( fd_f25519_sgn(x)!=expected_x_sign ) { /* 50% prob */
42 636272 : fd_f25519_neg( x, x );
43 636272 : }
44 :
45 1048343 : fd_f25519_mul( t, x, y );
46 1048343 : fd_ed25519_point_from( r, x, y, fd_f25519_one, t );
47 :
48 1048343 : return r;
49 1138245 : }
50 :
51 : uchar *
52 : fd_ed25519_point_tobytes( uchar out[ 32 ],
53 1760001 : fd_ed25519_point_t const * a ) {
54 1760001 : fd_f25519_t x[1], y[1], z[1], t[1];
55 1760001 : fd_ed25519_point_to( x, y, z, t, a );
56 1760001 : fd_f25519_inv( t, z );
57 1760001 : fd_f25519_mul2( x, x, t,
58 1760001 : y, y, t );
59 1760001 : fd_f25519_tobytes( out, y );
60 1760001 : out[31] ^= (uchar)(fd_f25519_sgn( x ) << 7);
61 1760001 : return out;
62 1760001 : }
63 :
64 : /*
65 : * Scalar multiplication
66 : */
67 :
68 : fd_ed25519_point_t *
69 : fd_ed25519_scalar_mul( fd_ed25519_point_t * r,
70 : uchar const n[ 32 ],
71 30072 : fd_ed25519_point_t const * a ) {
72 30072 : short nslide[256];
73 30072 : fd_curve25519_scalar_wnaf( nslide, n, WNAF_BIT_SZ );
74 :
75 30072 : fd_ed25519_point_t ai[WNAF_TBL_SZ]; /* A,3A,5A,7A,9A,11A,13A,15A */
76 30072 : fd_ed25519_point_t a2[1]; /* 2A (temp) */
77 30072 : fd_ed25519_point_t t[1];
78 :
79 : /* pre-computed table */
80 30072 : fd_ed25519_point_set( &ai[0], a );
81 30072 : fd_ed25519_point_dbln( a2, a, 1 ); // note: a is affine, we could save 1mul
82 30072 : fd_curve25519_into_precomputed( &ai[0] );
83 240576 : for( int i=1; i<WNAF_TBL_SZ; i++ ) {
84 210504 : fd_ed25519_point_add_with_opts( t, a2, &ai[i-1], i==1, 1, 1 );
85 210504 : fd_ed25519_point_add_final_mul( &ai[i], t );
86 : /* pre-compute kT, to save 1mul during the loop */
87 210504 : fd_curve25519_into_precomputed( &ai[i] );
88 210504 : }
89 :
90 : /* main dbl-and-add loop. note: last iter unrolled */
91 30072 : fd_ed25519_point_set_zero( r );
92 30072 : int i;
93 124959 : for( i=255; i>=0; i-- ) { if( nslide[i] ) break; }
94 7633617 : for( ; i>=0; i-- ) {
95 7603545 : fd_ed25519_partial_dbl( t, r );
96 7603545 : 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 ); }
97 7302399 : 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 ); }
98 :
99 : /* ignore r->T because dbl doesn't need it, except in the last cycle */
100 7603545 : if (i == 0) {
101 30066 : fd_ed25519_point_add_final_mul( r, t ); // compute r->T
102 7573479 : } else {
103 7573479 : fd_ed25519_point_add_final_mul_projective( r, t ); // ignore r->T
104 7573479 : }
105 7603545 : }
106 30072 : return r;
107 30072 : }
108 :
109 : fd_ed25519_point_t *
110 : fd_ed25519_double_scalar_mul_base( fd_ed25519_point_t * r,
111 : uchar const n1[ 32 ],
112 : fd_ed25519_point_t const * a,
113 770805 : uchar const n2[ 32 ] ) {
114 :
115 770805 : short n1slide[256]; fd_curve25519_scalar_wnaf( n1slide, n1, WNAF_BIT_SZ );
116 770805 : short n2slide[256]; fd_curve25519_scalar_wnaf( n2slide, n2, 8 );
117 :
118 770805 : fd_ed25519_point_t ai[WNAF_TBL_SZ]; /* A,3A,5A,7A,9A,11A,13A,15A */
119 770805 : fd_ed25519_point_t a2[1]; /* 2A (temp) */
120 770805 : fd_ed25519_point_t t[1];
121 :
122 : /* pre-computed table */
123 770805 : fd_ed25519_point_set( &ai[0], a );
124 770805 : fd_ed25519_point_dbln( a2, a, 1 ); // note: a is affine, we could save 1mul
125 770805 : fd_curve25519_into_precomputed( &ai[0] );
126 6166440 : for( int i=1; i<WNAF_TBL_SZ; i++ ) {
127 5395635 : fd_ed25519_point_add_with_opts( t, a2, &ai[i-1], i==1, 1, 1 );
128 5395635 : fd_ed25519_point_add_final_mul( &ai[i], t );
129 : /* pre-compute kT, to save 1mul during the loop */
130 5395635 : fd_curve25519_into_precomputed( &ai[i] );
131 5395635 : }
132 :
133 : /* main dbl-and-add loop */
134 770805 : fd_ed25519_point_set_zero( r );
135 :
136 770805 : int i;
137 4788912 : for( i=255; i>=0; i-- ) { if( n1slide[i] || n2slide[i] ) break; }
138 194078778 : for( ; i>=0; i-- ) {
139 193307973 : fd_ed25519_partial_dbl( t, r );
140 193307973 : 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 ); }
141 176501281 : 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 ); }
142 193307973 : 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 ); }
143 183141677 : 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 ); }
144 :
145 : /* ignore r->T because dbl doesn't need it, except in the last cycle */
146 193307973 : if (i == 0) {
147 770805 : fd_ed25519_point_add_final_mul( r, t ); // compute r->T
148 192537168 : } else {
149 192537168 : fd_ed25519_point_add_final_mul_projective( r, t ); // ignore r->T
150 192537168 : }
151 193307973 : }
152 770805 : return r;
153 770805 : }
154 :
155 :
156 : FD_25519_INLINE fd_ed25519_point_t *
157 : fd_ed25519_multi_scalar_mul_with_opts( fd_ed25519_point_t * r,
158 : uchar const n[], /* sz * 32 */
159 : fd_ed25519_point_t const a[], /* sz */
160 : ulong const sz,
161 7155 : ulong const base_sz ) {
162 7155 : short nslide[FD_BALLET_CURVE25519_MSM_BATCH_SZ][256];
163 7155 : fd_ed25519_point_t ai[FD_BALLET_CURVE25519_MSM_BATCH_SZ][WNAF_TBL_SZ]; /* A,3A,5A,7A,9A,11A,13A,15A */
164 7155 : fd_ed25519_point_t a2[1]; /* 2A (temp) */
165 7155 : fd_ed25519_point_t t[1]; /* temp */
166 :
167 7155 : if( base_sz ) {
168 0 : fd_curve25519_scalar_wnaf( nslide[0], &n[32*0], 8 );
169 0 : }
170 226011 : for( ulong j=base_sz; j<sz; j++ ) {
171 218856 : fd_curve25519_scalar_wnaf( nslide[j], &n[32*j], WNAF_BIT_SZ );
172 :
173 : /* pre-computed table */
174 218856 : fd_ed25519_point_set( &ai[j][0], &a[j] );
175 218856 : fd_ed25519_point_dbln( a2, &a[j], 1 ); // note: a is affine, we could save 1mul
176 218856 : fd_curve25519_into_precomputed( &ai[j][0] );
177 1750848 : for( int i=1; i<WNAF_TBL_SZ; i++ ) {
178 1531992 : fd_ed25519_point_add_with_opts( t, a2, &ai[j][i-1], i==1, 1, 1 );
179 1531992 : fd_ed25519_point_add_final_mul( &ai[j][i], t );
180 : /* pre-compute kT, to save 1mul during the loop */
181 1531992 : fd_curve25519_into_precomputed( &ai[j][i] );
182 1531992 : }
183 218856 : }
184 :
185 : /* main dbl-and-add loop */
186 7155 : fd_ed25519_point_set_zero( r );
187 1838835 : for( int i=255; i>=0; i-- ) {
188 1831680 : fd_ed25519_partial_dbl( t, r );
189 1831680 : if( base_sz ) {
190 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 ); }
191 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 ); }
192 0 : }
193 57858816 : for( ulong j=base_sz; j<sz; j++ ) {
194 56027136 : short n = nslide[j][i];
195 56027136 : 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 ); }
196 51324938 : 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 ); }
197 56027136 : }
198 :
199 : /* ignore r->T because dbl doesn't need it, except in the last cycle */
200 1831680 : if (i == 0) {
201 7155 : fd_ed25519_point_add_final_mul( r, t ); // compute r->T
202 1824525 : } else {
203 1824525 : fd_ed25519_point_add_final_mul_projective( r, t ); // ignore r->T
204 1824525 : }
205 1831680 : }
206 7155 : return r;
207 7155 : }
208 :
209 : fd_ed25519_point_t *
210 : fd_ed25519_multi_scalar_mul( fd_ed25519_point_t * r,
211 : uchar const n[], /* sz * 32 */
212 : fd_ed25519_point_t const a[], /* sz */
213 2361 : ulong const sz ) {
214 :
215 2361 : fd_ed25519_point_t h[1];
216 2361 : fd_ed25519_point_set_zero( r );
217 :
218 9516 : for( ulong i=0; i<sz; i+=FD_BALLET_CURVE25519_MSM_BATCH_SZ ) {
219 7155 : ulong batch_sz = fd_ulong_min(sz-i, FD_BALLET_CURVE25519_MSM_BATCH_SZ);
220 :
221 7155 : fd_ed25519_multi_scalar_mul_with_opts( h, &n[ 32*i ], &a[ i ], batch_sz, 0 );
222 7155 : fd_ed25519_point_add( r, r, h );
223 7155 : }
224 :
225 2361 : return r;
226 2361 : }
227 :
228 : fd_ed25519_point_t *
229 : fd_ed25519_multi_scalar_mul_base( fd_ed25519_point_t * r,
230 : uchar const n[], /* sz * 32 */
231 : fd_ed25519_point_t const a[], /* sz */
232 0 : ulong const sz ) {
233 0 : if (sz > FD_BALLET_CURVE25519_MSM_BATCH_SZ) {
234 0 : return NULL;
235 0 : }
236 0 : return fd_ed25519_multi_scalar_mul_with_opts( r, n, a, sz, 1 );
237 0 : }
238 :
239 : /*
240 : * Init
241 : */
242 :
243 : fd_ed25519_point_t *
244 : fd_curve25519_affine_add( fd_ed25519_point_t * r,
245 : fd_ed25519_point_t const * a,
246 0 : fd_ed25519_point_t const * b ) {
247 0 : fd_ed25519_point_add_with_opts( r, a, b, 1, 0, 0 );
248 0 : return fd_curve25519_into_affine( r );
249 0 : }
250 :
251 : fd_ed25519_point_t *
252 : fd_curve25519_affine_dbln( fd_ed25519_point_t * r,
253 : fd_ed25519_point_t const * a,
254 0 : int const n ) {
255 0 : fd_ed25519_point_dbln( r, a, n );
256 0 : return fd_curve25519_into_affine( r );
257 0 : }
|
