Line data    Source code

       1             : #include "../fd_curve25519.h"
       2             : #include "./fd_r43x6_ge.h"
       3             : 
       4             : /*
       5             :  * Add
       6             :  */
       7             : 
       8             : /* fd_ed25519_point_add_with_opts computes r = a + b, and returns r.
       9             : 
      10             :    https://eprint.iacr.org/2008/522
      11             :    Sec 4.2, 4-Processor Montgomery addition and doubling.
      12             : 
      13             :    This implementation includes several optional optimizations
      14             :    that are used for speeding up scalar multiplication:
      15             : 
      16             :    - b_Z_is_one, if b->Z == 1 (affine, or decompressed), we can skip 1mul
      17             : 
      18             :    - b_is_precomputed, since the scalar mul loop typically accumulates
      19             :      points from a table, we can pre-compute kT into the table points and
      20             :      therefore skip 1mul in during the loop.
      21             : 
      22             :    - skip_last_mul, since dbl can be computed with just (X, Y, Z)
      23             :      and doesn't need T, we can skip the last 4 mul and selectively
      24             :      compute (X, Y, Z) or (X, Y, Z, T) during the scalar mul loop.
      25             :  */
      26             : FD_25519_INLINE fd_ed25519_point_t *
      27             : fd_ed25519_point_add_with_opts( fd_ed25519_point_t *       r,
      28             :                                 fd_ed25519_point_t const * a,
      29             :                                 fd_ed25519_point_t const * b,
      30             :                                 FD_PARAM_UNUSED int const b_Z_is_one,
      31             :                                 int const b_is_precomputed,
      32    15354188 :                                 FD_PARAM_UNUSED int const skip_last_mul ) {
      33             : 
      34    15354188 :   if( b_is_precomputed ) {
      35    13151913 :     fd_ed25519_point_t tmp[2];
      36    13151913 :     FD_R43X6_GE_ADD_TABLE_ALT( r->P, a->P, b->P, tmp[0].P, tmp[1].P );
      37    13151913 :   } else {
      38     2202275 :     FD_R43X6_GE_ADD( r->P, a->P, b->P );
      39     2202275 :   }
      40    15354188 :   return r;
      41    15354188 : }
      42             : 
      43             : /* fd_ed25519_point_add computes r = a + b, and returns r. */
      44             : fd_ed25519_point_t *
      45             : fd_ed25519_point_add( fd_ed25519_point_t *       r,
      46             :                       fd_ed25519_point_t const * a,
      47     1202163 :                       fd_ed25519_point_t const * b ) {
      48     1202163 :   return fd_ed25519_point_add_with_opts( r, a, b, 0, 0, 0 );
      49     1202163 : }
      50             : 
      51             : /* fd_ed25519_point_add_final_mul computes just the final mul step in point add.
      52             :    See fd_ed25519_point_add_with_opts. */
      53             : FD_25519_INLINE fd_ed25519_point_t *
      54             : fd_ed25519_point_add_final_mul( fd_ed25519_point_t * restrict r,
      55    13296075 :                                 fd_ed25519_point_t const *    a ) {
      56    13296075 :   fd_ed25519_point_set( r, a );
      57    13296075 :   return r;
      58    13296075 : }
      59             : 
      60             : /* fd_ed25519_point_add_final_mul_projective computes just the final mul step
      61             :    in point add, assuming the result is projective (X, Y, Z), i.e. ignoring T.
      62             :    This is useful because dbl only needs (X, Y, Z) in input, so we can save 1mul.
      63             :    See fd_ed25519_point_add_with_opts. */
      64             : FD_25519_INLINE fd_ed25519_point_t *
      65             : fd_ed25519_point_add_final_mul_projective( fd_ed25519_point_t * restrict r,
      66    22369944 :                                            fd_ed25519_point_t const *    a ) {
      67    22369944 :   fd_ed25519_point_set( r, a );
      68    22369944 :   return r;
      69    22369944 : }
      70             : 
      71             : /*
      72             :  * Sub
      73             :  */
      74             : 
      75             : /* fd_ed25519_point_sub sets r = -a. */
      76             : FD_25519_INLINE fd_ed25519_point_t *
      77             : fd_ed25519_point_neg_precomputed( fd_ed25519_point_t *       r,
      78     5945286 :                       fd_ed25519_point_t const * a ) {
      79             :   /* use p instead of zero to avoid mod reduction */
      80     5945286 :   FD_R43X6_QUAD_DECL( _p );
      81     5945286 :   _p03 = wwl( 8796093022189L, 8796093022189L, 8796093022189L, 8796093022189L, 8796093022207L, 8796093022207L, 8796093022207L, 8796093022207L );
      82     5945286 :   _p14 = wwl( 8796093022207L, 8796093022207L, 8796093022207L, 8796093022207L, 8796093022207L, 8796093022207L, 8796093022207L, 8796093022207L );
      83     5945286 :   _p25 = wwl( 8796093022207L, 8796093022207L, 8796093022207L, 8796093022207L, 1099511627775L, 1099511627775L, 1099511627775L, 1099511627775L );
      84     5945286 :   FD_R43X6_QUAD_LANE_SUB_FAST( r->P, a->P, 0,0,0,1, _p, a->P );
      85     5945286 :   FD_R43X6_QUAD_PERMUTE      ( r->P, 1,0,2,3, r->P );
      86     5945286 :   return r;
      87     5945286 : }
      88             : 
      89             : /* fd_ed25519_point_sub_with_opts computes r = a - b, and returns r.
      90             :    This is like fd_ed25519_point_add_with_opts, replacing:
      91             :    - b->X => -b->X
      92             :    - b->T => -b->T
      93             :    See fd_ed25519_point_add_with_opts for details.
      94             :  */
      95             : FD_25519_INLINE fd_ed25519_point_t *
      96             : fd_ed25519_point_sub_with_opts( fd_ed25519_point_t *       r,
      97             :                                 fd_ed25519_point_t const * a,
      98             :                                 fd_ed25519_point_t const * b,
      99             :                                 int const b_Z_is_one,
     100             :                                 int const b_is_precomputed,
     101     6945398 :                                 int const skip_last_mul ) {
     102             : 
     103     6945398 :   fd_ed25519_point_t neg[1];
     104     6945398 :   if (b_is_precomputed) {
     105     5945286 :     fd_ed25519_point_neg_precomputed( neg, b );
     106     5945286 :   } else {
     107     1000112 :     fd_ed25519_point_neg( neg, b );
     108     1000112 :   }
     109     6945398 :   return fd_ed25519_point_add_with_opts( r, a, neg, b_Z_is_one, b_is_precomputed, skip_last_mul );
     110     6945398 : }
     111             : 
     112             : /* fd_ed25519_point_sub computes r = a - b, and returns r. */
     113             : fd_ed25519_point_t *
     114             : fd_ed25519_point_sub( fd_ed25519_point_t *       r,
     115             :                       fd_ed25519_point_t const * a,
     116     1000112 :                       fd_ed25519_point_t const * b ) {
     117     1000112 :   return fd_ed25519_point_sub_with_opts( r, a, b, 0, 0, 0 );
     118     1000112 : }
     119             : 
     120             : /*
     121             :  * Dbl
     122             :  */
     123             : 
     124             : /* Dedicated dbl
     125             :    https://eprint.iacr.org/2008/522
     126             :    Sec 4.4.
     127             :    This uses sqr instead of mul.
     128             : 
     129             :    TODO: use the same iface with_opts?
     130             :   */
     131             : 
     132             : FD_25519_INLINE fd_ed25519_point_t *
     133             : fd_ed25519_partial_dbl( fd_ed25519_point_t *       r,
     134    22514106 :                         fd_ed25519_point_t const * a ) {
     135    22514106 :   FD_R43X6_GE_DBL( r->P, a->P );
     136    22514106 :   return r;
     137    22514106 : }
     138             : 
     139             : fd_ed25519_point_t *
     140             : fd_ed25519_point_dbl( fd_ed25519_point_t *       r,
     141           0 :                       fd_ed25519_point_t const * a ) {
     142           0 :   FD_R43X6_GE_DBL( r->P, a->P );
     143           0 :   return r;
     144           0 : }
     145             : 
     146             : /*
     147             :  * Ser/de
     148             :  */
     149             : 
     150             : int
     151             : fd_ed25519_point_frombytes_2x( fd_ed25519_point_t * r1,
     152             :                                uchar const          buf1[ 32 ],
     153             :                                fd_ed25519_point_t * r2,
     154      143881 :                                uchar const          buf2[ 32 ] ) {
     155             :   //TODO: consider unifying code with ref
     156      143881 :   return FD_R43X6_GE_DECODE2( r1->P, buf1, r2->P, buf2 );
     157      143881 : }
     158             : 
     159             : int
     160             : fd_ed25519_point_frombytes_1x( fd_ed25519_point_t * r,
     161      177747 :                                uchar const          buf[ 32 ] ) {
     162             :   /* fd_r43x6_ge_decode does the same sequence of operations as each
     163             :      lane of fd_r43x6_ge_decode2 */
     164      177747 :   return FD_R43X6_GE_DECODE( r->P, buf );
     165      177747 : }
     166             : 
     167             : void
     168             : fd_ed25519_point_decode_init( fd_ed25519_point_decode_t * st,
     169      110142 :                               uchar const                 buf[ 32 ] ) {
     170      110142 :   fd_r43x6_ge_decode_init( st, buf );
     171      110142 : }
     172             : 
     173             : void
     174             : fd_ed25519_point_decode_step( fd_ed25519_point_decode_t * st,
     175     7861492 :                               ulong                       n ) {
     176     7861492 :   fd_r43x6_ge_decode_step( st, n );
     177     7861492 : }
     178             : 
     179             : int
     180             : fd_ed25519_point_decode_fini( fd_ed25519_point_t *        r,
     181      110142 :                               fd_ed25519_point_decode_t * st ) {
     182      110142 :   FD_R43X6_QUAD_DECL( _P );
     183      110142 :   int err = fd_r43x6_ge_decode_fini( &_P03, &_P14, &_P25, st );
     184      110142 :   FD_R43X6_QUAD_MOV( r->P, _P );
     185      110142 :   return err;
     186      110142 : }
     187             : 
     188             : /*
     189             :   Affine (only for init(), can be slow)
     190             : */
     191             : fd_ed25519_point_t *
     192             : fd_curve25519_affine_frombytes( fd_ed25519_point_t * r,
     193             :                                 uchar const          _x[ 32 ],
     194           1 :                                 uchar const          _y[ 32 ] ) {
     195           1 :   fd_f25519_t x[1], y[1], z[1], t[1];
     196           1 :   fd_f25519_frombytes( x, _x );
     197           1 :   fd_f25519_frombytes( y, _y );
     198           1 :   fd_f25519_set( z, fd_f25519_one );
     199           1 :   fd_f25519_mul( t, x, y );
     200           1 :   FD_R43X6_QUAD_PACK( r->P, x->el, y->el, z->el, t->el );
     201           1 :   return r;
     202           1 : }
     203             : 
     204             : fd_ed25519_point_t *
     205        2500 : fd_curve25519_into_affine( fd_ed25519_point_t * r ) {
     206        2500 :   fd_f25519_t x[1], y[1], z[1], t[1];
     207        2500 :   FD_R43X6_QUAD_UNPACK( x->el, y->el, z->el, t->el, r->P );
     208        2500 :   fd_f25519_inv( z, z );
     209        2500 :   fd_f25519_mul( x, x, z );
     210        2500 :   fd_f25519_mul( y, y, z );
     211        2500 :   fd_f25519_set( z, fd_f25519_one );
     212        2500 :   fd_f25519_mul( t, x, y );
     213             :   FD_R43X6_QUAD_PACK( r->P, x->el, y->el, z->el, t->el );
     214        2500 :   return r;
     215        2500 : }