Line data    Source code

       1             : #include "../fd_curve25519.h"
       2             : 
       3             : /*
       4             :  * Add
       5             :  */
       6             : 
       7             : /* fd_ed25519_point_add_with_opts computes r = a + b, and returns r.
       8             : 
       9             :    https://eprint.iacr.org/2008/522
      10             :    Sec 4.2, 4-Processor Montgomery addition and doubling.
      11             : 
      12             :    This implementation includes several optional optimizations
      13             :    that are used for speeding up scalar multiplication:
      14             : 
      15             :    - b_Z_is_one, if b->Z == 1 (affine, or decompressed), we can skip 1mul
      16             : 
      17             :    - b_is_precomputed, since the scalar mul loop typically accumulates
      18             :      points from a table, we can pre-compute kT into the table points and
      19             :      therefore skip 1mul in during the loop.
      20             : 
      21             :    - skip_last_mul, since dbl can be computed with just (X, Y, Z)
      22             :      and doesn't need T, we can skip the last 4 mul and selectively
      23             :      compute (X, Y, Z) or (X, Y, Z, T) during the scalar mul loop.
      24             :  */
      25             : FD_25519_INLINE fd_ed25519_point_t *
      26             : fd_ed25519_point_add_with_opts( fd_ed25519_point_t *       r,
      27             :                                 fd_ed25519_point_t const * a,
      28             :                                 fd_ed25519_point_t const * b,
      29             :                                 int const b_Z_is_one,
      30             :                                 int const b_is_precomputed,
      31    28190958 :                                 int const skip_last_mul ) {
      32    28190958 :   fd_f25519_t r1[1], r2[1], r3[1], r4[1];
      33    28190958 :   fd_f25519_t r5[1], r6[1], r7[1], r8[1];
      34    28190958 :   fd_f25519_t t[1];
      35    28190958 :   fd_f25519_t const *r2p = r2, *r4p = r4;
      36             : 
      37    28190958 :   fd_f25519_sub_nr( r1, a->Y, a->X );
      38    28190958 :   fd_f25519_add_nr( r3, a->Y, a->X );
      39             : 
      40    28190958 : #if CURVE25519_PRECOMP_XY
      41    28190958 :   if (b_is_precomputed) {
      42    26165948 :     r2p = b->X;
      43    26165948 :     r4p = b->Y;
      44    26165948 :   } else {
      45     2025010 :     fd_f25519_sub_nr( r2, b->Y, b->X );
      46     2025010 :     fd_f25519_add_nr( r4, b->Y, b->X );
      47     2025010 :   }
      48             : #else
      49             :     fd_f25519_sub_nr( r2, b->Y, b->X );
      50             :     fd_f25519_add_nr( r4, b->Y, b->X );
      51             : #endif
      52             : 
      53             :   /* if b->Z == 1, save 1mul */
      54    28190958 :   if( b_Z_is_one ) {
      55     9606065 :     fd_f25519_mul3( r5, r1,   r2p,
      56     9606065 :                     r6, r3,   r4p,
      57     9606065 :                     r7, a->T, b->T );
      58     9606065 :     fd_f25519_add( r8, a->Z, a->Z );
      59    18584893 :   } else {
      60    18584893 :     fd_f25519_add_nr( t, a->Z, a->Z );
      61    18584893 :     fd_f25519_mul4( r5, r1,   r2p,
      62    18584893 :                     r6, r3,   r4p,
      63    18584893 :                     r7, a->T, b->T,
      64    18584893 :                     r8, t, b->Z );
      65    18584893 :   } /* b_Z_is_one */
      66             : 
      67             :   /* if b->T actually contains k*b->T, save 1mul */
      68    28190958 :   if( !b_is_precomputed ) {
      69     2025010 :     fd_f25519_mul( r7, r7, fd_f25519_k );
      70     2025010 :   }
      71             : 
      72             :   /* skip last mul step, and use fd_ed25519_point_add_final_mul
      73             :      or fd_ed25519_point_add_final_mul_projective instead. */
      74    28190958 :   if( skip_last_mul ) {
      75             :     /* store r1, r2, r3, r4 resp. in X, Y, Z, T */
      76    26165948 :     fd_f25519_sub_nr( r->X, r6, r5 );
      77    26165948 :     fd_f25519_sub_nr( r->Y, r8, r7 );
      78    26165948 :     fd_f25519_add_nr( r->Z, r8, r7 );
      79    26165948 :     fd_f25519_add_nr( r->T, r6, r5 );
      80    26165948 :   } else {
      81     2025010 :     fd_f25519_sub_nr( r1, r6, r5 );
      82     2025010 :     fd_f25519_sub_nr( r2, r8, r7 );
      83     2025010 :     fd_f25519_add_nr( r3, r8, r7 );
      84     2025010 :     fd_f25519_add_nr( r4, r6, r5 );
      85             : 
      86     2025010 :     fd_f25519_mul4( r->X, r1, r2,
      87     2025010 :                     r->Y, r3, r4,
      88     2025010 :                     r->Z, r2, r3,
      89     2025010 :                     r->T, r1, r4 );
      90     2025010 :   } /* skip_last_mul */
      91    28190958 :   return r;
      92    28190958 : }
      93             : 
      94             : /* fd_ed25519_point_add computes r = a + b, and returns r. */
      95             : fd_ed25519_point_t *
      96             : fd_ed25519_point_add( fd_ed25519_point_t *       r,
      97             :                       fd_ed25519_point_t const * a,
      98     2025010 :                       fd_ed25519_point_t const * b ) {
      99     2025010 :   return fd_ed25519_point_add_with_opts( r, a, b, 0, 0, 0 );
     100     2025010 : }
     101             : 
     102             : /*
     103             :  * Sub
     104             :  */
     105             : 
     106             : /* fd_ed25519_point_sub_with_opts computes r = a - b, and returns r.
     107             :    This is like fd_ed25519_point_add_with_opts, replacing:
     108             :    - b->X => -b->X
     109             :    - b->T => -b->T
     110             :    See fd_ed25519_point_add_with_opts for details.
     111             :  */
     112             : FD_25519_INLINE fd_ed25519_point_t *
     113             : fd_ed25519_point_sub_with_opts( fd_ed25519_point_t *       r,
     114             :                                 fd_ed25519_point_t const * a,
     115             :                                 fd_ed25519_point_t const * b,
     116             :                                 int const b_Z_is_one,
     117             :                                 int const b_is_precomputed,
     118    22059831 :                                 int const skip_last_mul ) {
     119    22059831 :   fd_f25519_t r1[1], r2[1], r3[1], r4[1];
     120    22059831 :   fd_f25519_t r5[1], r6[1], r7[1], r8[1];
     121    22059831 :   fd_f25519_t t[1];
     122    22059831 :   fd_f25519_t const *r2p = r2, *r4p = r4;
     123             : 
     124    22059831 :   fd_f25519_sub_nr( r1, a->Y, a->X );
     125    22059831 :   fd_f25519_add_nr( r3, a->Y, a->X );
     126             : 
     127    22059831 : #if CURVE25519_PRECOMP_XY
     128    22059831 :   if (b_is_precomputed) {
     129    20059609 :     r2p = b->Y;
     130    20059609 :     r4p = b->X;
     131    20059609 :   } else {
     132     2000222 :     fd_f25519_add_nr( r2, b->Y, b->X ); // _sub => _add (because of -b->X)
     133     2000222 :     fd_f25519_sub_nr( r4, b->Y, b->X ); // _add => _sub (because of -b->X)
     134     2000222 :   }
     135             : #else
     136             :     fd_f25519_add_nr( r2, b->Y, b->X ); // _sub => _add (because of -b->X)
     137             :     fd_f25519_sub_nr( r4, b->Y, b->X ); // _add => _sub (because of -b->X)
     138             : #endif
     139             : 
     140             :   /* if b->Z == 1, save 1mul */
     141    22059831 :   if( b_Z_is_one ) {
     142     7839488 :     fd_f25519_mul3( r5, r1,   r2p,
     143     7839488 :                     r6, r3,   r4p,
     144     7839488 :                     r7, a->T, b->T );
     145     7839488 :     fd_f25519_add( r8, a->Z, a->Z );
     146    14220343 :   } else {
     147    14220343 :     fd_f25519_add_nr( t, a->Z, a->Z );
     148    14220343 :     fd_f25519_mul4( r5, r1,   r2p,
     149    14220343 :                     r6, r3,   r4p,
     150    14220343 :                     r7, a->T, b->T,
     151    14220343 :                     r8, t, b->Z );
     152    14220343 :   } /* b_Z_is_one */
     153             : 
     154             :   /* if b->T actually contains k*b->T, save 1mul */
     155    22059831 :   if( !b_is_precomputed ) {
     156     2000222 :     fd_f25519_mul( r7, r7, fd_f25519_k );
     157     2000222 :   }
     158             : 
     159             :   /* skip last mul step, and use fd_ed25519_point_add_final_mul
     160             :      or fd_ed25519_point_add_final_mul_projective instead. */
     161    22059831 :   if( skip_last_mul ) {
     162             :     /* store r1, r2, r3, r4 resp. in X, Y, Z, T */
     163    20059609 :     fd_f25519_sub_nr( r->X, r6, r5 );
     164    20059609 :     fd_f25519_add_nr( r->Y, r8, r7 ); // _sub => _add (because of -b->T => -r7)
     165    20059609 :     fd_f25519_sub_nr( r->Z, r8, r7 ); // _add => _sub (because of -b->T => -r7)
     166    20059609 :     fd_f25519_add_nr( r->T, r6, r5 );
     167    20059609 :   } else {
     168     2000222 :     fd_f25519_sub_nr( r1, r6, r5 );
     169     2000222 :     fd_f25519_add_nr( r2, r8, r7 );   // _sub => _add (because of -b->T => -r7)
     170     2000222 :     fd_f25519_sub_nr( r3, r8, r7 );   // _add => _sub (because of -b->T => -r7)
     171     2000222 :     fd_f25519_add_nr( r4, r6, r5 );
     172             : 
     173     2000222 :     fd_f25519_mul4( r->X, r1, r2,
     174     2000222 :                     r->Y, r3, r4,
     175     2000222 :                     r->Z, r2, r3,
     176     2000222 :                     r->T, r1, r4 );
     177     2000222 :   } /* skip_last_mul */
     178    22059831 :   return r;
     179    22059831 : }
     180             : 
     181             : /* fd_ed25519_point_sub computes r = a - b, and returns r. */
     182             : fd_ed25519_point_t *
     183             : fd_ed25519_point_sub( fd_ed25519_point_t *       r,
     184             :                       fd_ed25519_point_t const * a,
     185     2000222 :                       fd_ed25519_point_t const * b ) {
     186     2000222 :   return fd_ed25519_point_sub_with_opts( r, a, b, 0, 0, 0 );
     187     2000222 : }
     188             : 
     189             : /*
     190             :  * Dbl
     191             :  */
     192             : 
     193             : fd_ed25519_point_t *
     194             : fd_ed25519_point_dbl( fd_ed25519_point_t *       r,
     195           0 :                       fd_ed25519_point_t const * a ) {
     196           0 :   fd_ed25519_point_t t[1];
     197             :   /* Dedicated dbl
     198             :      https://eprint.iacr.org/2008/522
     199             :      Sec 4.4.
     200             :      This uses sqr instead of mul. */
     201           0 :   fd_ed25519_partial_dbl( t, a );
     202           0 :   return fd_ed25519_point_add_final_mul( r, t );
     203           0 : }
     204             : 
     205             : /*
     206             :  * Ser/de
     207             :  */
     208             : 
     209             : int
     210             : fd_ed25519_point_frombytes_2x( fd_ed25519_point_t * r1,
     211             :                                uchar const          buf1[ 32 ],
     212             :                                fd_ed25519_point_t * r2,
     213      608568 :                                uchar const          buf2[ 32 ] ) {
     214      608568 :   fd_ed25519_point_t * res = NULL;
     215      608568 :   res = fd_ed25519_point_frombytes( r1, buf1 );
     216      608568 :   if( res == NULL ) {
     217       80268 :     return 1;
     218       80268 :   }
     219      528300 :   res = fd_ed25519_point_frombytes( r2, buf2 );
     220      528300 :   if( res == NULL ) {
     221        8818 :     return 2;
     222        8818 :   }
     223      519482 :   return 0;
     224      528300 : }
     225             : 
     226             : /*
     227             :   Affine (only for init(), can be slow)
     228             : */
     229             : fd_ed25519_point_t *
     230             : fd_curve25519_affine_frombytes( fd_ed25519_point_t * r,
     231             :                                 uchar const          x[ 32 ],
     232           2 :                                 uchar const          y[ 32 ] ) {
     233           2 :   fd_f25519_frombytes( r->X, x );
     234           2 :   fd_f25519_frombytes( r->Y, y );
     235           2 :   fd_f25519_set( r->Z, fd_f25519_one );
     236           2 :   fd_f25519_mul( r->T, r->X, r->Y );
     237           2 :   return r;
     238           2 : }
     239             : 
     240             : fd_ed25519_point_t *
     241           0 : fd_curve25519_into_affine( fd_ed25519_point_t * r ) {
     242           0 :   fd_f25519_t invz[1];
     243           0 :   fd_f25519_inv( invz, r->Z );
     244           0 :   fd_f25519_mul( r->X, r->X, invz );
     245           0 :   fd_f25519_mul( r->Y, r->Y, invz );
     246           0 :   fd_f25519_set( r->Z, fd_f25519_one );
     247           0 :   fd_f25519_mul( r->T, r->X, r->Y );
     248           0 :   return r;
     249           0 : }