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