LCOV - code coverage report
Current view: top level - ballet/ed25519 - fd_curve25519.c (source / functions) Hit Total Coverage
Test: cov.lcov Lines: 137 156 87.8 %
Date: 2025-02-18 12:28:12 Functions: 6 9 66.7 %

          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 : }

Generated by: LCOV version 1.14