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 8779887 : #define WNAF_BIT_SZ 4
16 7804344 : #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 1130502 : uchar const buf[ 32 ] ) {
25 1130502 : fd_f25519_t x[1], y[1], t[1];
26 1130502 : fd_f25519_frombytes( y, buf );
27 1130502 : uchar expected_x_sign = buf[31] >> 7;
28 :
29 1130502 : fd_f25519_t u[1];
30 1130502 : fd_f25519_t v[1];
31 1130502 : fd_f25519_sqr( u, y );
32 1130502 : fd_f25519_mul( v, u, fd_f25519_d );
33 1130502 : fd_f25519_sub( u, u, fd_f25519_one ); /* u = y^2-1 */
34 1130502 : fd_f25519_add( v, v, fd_f25519_one ); /* v = dy^2+1 */
35 :
36 1130502 : int was_square = fd_f25519_sqrt_ratio( x, u, v );
37 1130502 : if( FD_UNLIKELY( !was_square ) ) {
38 89065 : return NULL;
39 89065 : }
40 :
41 1041437 : if( fd_f25519_sgn(x)!=expected_x_sign ) { /* 50% prob */
42 631724 : fd_f25519_neg( x, x );
43 631724 : }
44 :
45 1041437 : fd_f25519_mul( t, x, y );
46 1041437 : fd_ed25519_point_from( r, x, y, fd_f25519_one, t );
47 :
48 1041437 : return r;
49 1130502 : }
50 :
51 : uchar *
52 : fd_ed25519_point_tobytes( uchar out[ 32 ],
53 1759962 : fd_ed25519_point_t const * a ) {
54 1759962 : fd_f25519_t x[1], y[1], z[1], t[1];
55 1759962 : fd_ed25519_point_to( x, y, z, t, a );
56 1759962 : fd_f25519_inv( t, z );
57 1759962 : fd_f25519_mul2( x, x, t,
58 1759962 : y, y, t );
59 1759962 : fd_f25519_tobytes( out, y );
60 1759962 : out[31] ^= (uchar)(fd_f25519_sgn( x ) << 7);
61 1759962 : return out;
62 1759962 : }
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 30021 : fd_ed25519_point_t const * a ) {
72 30021 : short nslide[256];
73 30021 : fd_curve25519_scalar_wnaf( nslide, n, WNAF_BIT_SZ );
74 :
75 30021 : fd_ed25519_point_t ai[WNAF_TBL_SZ]; /* A,3A,5A,7A,9A,11A,13A,15A */
76 30021 : fd_ed25519_point_t a2[1]; /* 2A (temp) */
77 30021 : fd_ed25519_point_t t[1];
78 :
79 : /* pre-computed table */
80 30021 : fd_ed25519_point_set( &ai[0], a );
81 30021 : fd_ed25519_point_dbln( a2, a, 1 ); // note: a is affine, we could save 1mul
82 30021 : fd_curve25519_into_precomputed( &ai[0] );
83 240168 : for( int i=1; i<WNAF_TBL_SZ; i++ ) {
84 210147 : fd_ed25519_point_add_with_opts( t, a2, &ai[i-1], i==1, 1, 1 );
85 210147 : fd_ed25519_point_add_final_mul( &ai[i], t );
86 : /* pre-compute kT, to save 1mul during the loop */
87 210147 : fd_curve25519_into_precomputed( &ai[i] );
88 210147 : }
89 :
90 : /* main dbl-and-add loop. note: last iter unrolled */
91 30021 : fd_ed25519_point_set_zero( r );
92 30021 : int i;
93 121608 : for( i=255; i>=0; i-- ) { if( nslide[i] ) break; }
94 7623810 : for( ; i>=0; i-- ) {
95 7593789 : fd_ed25519_partial_dbl( t, r );
96 7593789 : 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 7293507 : 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 7593789 : if (i == 0) {
101 30021 : fd_ed25519_point_add_final_mul( r, t ); // compute r->T
102 7563768 : } else {
103 7563768 : fd_ed25519_point_add_final_mul_projective( r, t ); // ignore r->T
104 7563768 : }
105 7593789 : }
106 30021 : return r;
107 30021 : }
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 768483 : uchar const n2[ 32 ] ) {
114 :
115 768483 : short n1slide[256]; fd_curve25519_scalar_wnaf( n1slide, n1, WNAF_BIT_SZ );
116 768483 : short n2slide[256]; fd_curve25519_scalar_wnaf( n2slide, n2, 8 );
117 :
118 768483 : fd_ed25519_point_t ai[WNAF_TBL_SZ]; /* A,3A,5A,7A,9A,11A,13A,15A */
119 768483 : fd_ed25519_point_t a2[1]; /* 2A (temp) */
120 768483 : fd_ed25519_point_t t[1];
121 :
122 : /* pre-computed table */
123 768483 : fd_ed25519_point_set( &ai[0], a );
124 768483 : fd_ed25519_point_dbln( a2, a, 1 ); // note: a is affine, we could save 1mul
125 768483 : fd_curve25519_into_precomputed( &ai[0] );
126 6147864 : for( int i=1; i<WNAF_TBL_SZ; i++ ) {
127 5379381 : fd_ed25519_point_add_with_opts( t, a2, &ai[i-1], i==1, 1, 1 );
128 5379381 : fd_ed25519_point_add_final_mul( &ai[i], t );
129 : /* pre-compute kT, to save 1mul during the loop */
130 5379381 : fd_curve25519_into_precomputed( &ai[i] );
131 5379381 : }
132 :
133 : /* main dbl-and-add loop */
134 768483 : fd_ed25519_point_set_zero( r );
135 :
136 768483 : int i;
137 4777780 : for( i=255; i>=0; i-- ) { if( n1slide[i] || n2slide[i] ) break; }
138 193490834 : for( ; i>=0; i-- ) {
139 192722351 : fd_ed25519_partial_dbl( t, r );
140 192722351 : 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 175956870 : 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 192722351 : 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 182583025 : 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 192722351 : if (i == 0) {
147 768483 : fd_ed25519_point_add_final_mul( r, t ); // compute r->T
148 191953868 : } else {
149 191953868 : fd_ed25519_point_add_final_mul_projective( r, t ); // ignore r->T
150 191953868 : }
151 192722351 : }
152 768483 : return r;
153 768483 : }
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 5544 : ulong const base_sz ) {
162 5544 : short nslide[FD_BALLET_CURVE25519_MSM_BATCH_SZ][256];
163 5544 : fd_ed25519_point_t ai[FD_BALLET_CURVE25519_MSM_BATCH_SZ][WNAF_TBL_SZ]; /* A,3A,5A,7A,9A,11A,13A,15A */
164 5544 : fd_ed25519_point_t a2[1]; /* 2A (temp) */
165 5544 : fd_ed25519_point_t t[1]; /* temp */
166 :
167 5544 : if( base_sz ) {
168 0 : fd_curve25519_scalar_wnaf( nslide[0], &n[32*0], 8 );
169 0 : }
170 182583 : for( ulong j=base_sz; j<sz; j++ ) {
171 177039 : fd_curve25519_scalar_wnaf( nslide[j], &n[32*j], WNAF_BIT_SZ );
172 :
173 : /* pre-computed table */
174 177039 : fd_ed25519_point_set( &ai[j][0], &a[j] );
175 177039 : fd_ed25519_point_dbln( a2, &a[j], 1 ); // note: a is affine, we could save 1mul
176 177039 : fd_curve25519_into_precomputed( &ai[j][0] );
177 1416312 : for( int i=1; i<WNAF_TBL_SZ; i++ ) {
178 1239273 : fd_ed25519_point_add_with_opts( t, a2, &ai[j][i-1], i==1, 1, 1 );
179 1239273 : fd_ed25519_point_add_final_mul( &ai[j][i], t );
180 : /* pre-compute kT, to save 1mul during the loop */
181 1239273 : fd_curve25519_into_precomputed( &ai[j][i] );
182 1239273 : }
183 177039 : }
184 :
185 : /* main dbl-and-add loop */
186 5544 : fd_ed25519_point_set_zero( r );
187 1424808 : for( int i=255; i>=0; i-- ) {
188 1419264 : fd_ed25519_partial_dbl( t, r );
189 1419264 : 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 46741248 : for( ulong j=base_sz; j<sz; j++ ) {
194 45321984 : short n = nslide[j][i];
195 45321984 : 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 41529461 : 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 45321984 : }
198 :
199 : /* ignore r->T because dbl doesn't need it, except in the last cycle */
200 1419264 : if (i == 0) {
201 5544 : fd_ed25519_point_add_final_mul( r, t ); // compute r->T
202 1413720 : } else {
203 1413720 : fd_ed25519_point_add_final_mul_projective( r, t ); // ignore r->T
204 1413720 : }
205 1419264 : }
206 5544 : return r;
207 5544 : }
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 1854 : ulong const sz ) {
214 :
215 1854 : fd_ed25519_point_t h[1];
216 1854 : fd_ed25519_point_set_zero( r );
217 :
218 7398 : for( ulong i=0; i<sz; i+=FD_BALLET_CURVE25519_MSM_BATCH_SZ ) {
219 5544 : ulong batch_sz = fd_ulong_min(sz-i, FD_BALLET_CURVE25519_MSM_BATCH_SZ);
220 :
221 5544 : fd_ed25519_multi_scalar_mul_with_opts( h, &n[ 32*i ], &a[ i ], batch_sz, 0 );
222 5544 : fd_ed25519_point_add( r, r, h );
223 5544 : }
224 :
225 1854 : return r;
226 1854 : }
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 : }
|
