Line data    Source code

       1             : #include "fd_ristretto255.h"
       2             : 
       3             : fd_ristretto255_point_t *
       4             : fd_ristretto255_point_frombytes( fd_ristretto255_point_t * h,
       5      307995 :                                  uchar const              buf[ 32 ] ) {
       6      307995 :   fd_f25519_t s[1];
       7      307995 :   fd_f25519_frombytes( s, buf );
       8             : 
       9      307995 :   uchar s_check[ 32 ];
      10      307995 :   fd_f25519_tobytes( s_check, s );
      11             : 
      12             :   /* we only accept canonical points */
      13      307995 :   if( FD_UNLIKELY( ( 0==fd_memeq( buf, s_check, 32UL ) )
      14      307995 :                  | ( buf[0] & 1 /*fd_f25519_sgn( s )*/ ) ) ) {
      15         114 :     return NULL;
      16         114 :   }
      17             : 
      18      307881 :   fd_f25519_t ss[1]; /* ss = s^2 */
      19      307881 :   fd_f25519_sqr( ss, s );
      20             : 
      21      307881 :   fd_f25519_t u1[1]; /* u1 = 1 - ss */
      22      307881 :   fd_f25519_t u2[1]; /* u2 = 1 + ss */
      23      307881 :   fd_f25519_sub( u1, fd_f25519_one, ss );
      24      307881 :   fd_f25519_add( u2, fd_f25519_one, ss );
      25             : 
      26      307881 :   fd_f25519_t u2sq[1]; /* u2_sqr = u2^2 */
      27      307881 :   fd_f25519_sqr( u2sq, u2 );
      28             : 
      29             :   /* v = -(D * u1^2) - u2_sqr */
      30             : 
      31      307881 :   fd_f25519_t v[1];
      32      307881 :   fd_f25519_sqr ( v, u1          );
      33      307881 :   fd_f25519_mul( v, v, fd_f25519_d );
      34      307881 :   fd_f25519_neg( v, v           );
      35      307881 :   fd_f25519_sub( v, v, u2sq     );
      36             : 
      37             :   /* (was_square, inv_sq) = SQRT_RATIO_M1(1, v * u2_sqr) */
      38             : 
      39      307881 :   fd_f25519_t tmp0[1];
      40      307881 :   fd_f25519_t tmp1[1];
      41      307881 :   fd_f25519_mul( tmp1, v, u2sq );
      42             : 
      43      307881 :   fd_f25519_t inv_sq[1];
      44      307881 :   int was_square = fd_f25519_inv_sqrt( inv_sq, tmp1 );
      45             : 
      46      307881 :   fd_f25519_t den_x[1];  /* den_x = inv_sq * u2 */
      47      307881 :   fd_f25519_t den_y[1];  /* den_y = inv_sq * den_x * v */
      48      307881 :   fd_f25519_mul( den_x, inv_sq, u2    );
      49      307881 :   fd_f25519_mul( den_y, inv_sq, den_x );
      50      307881 :   fd_f25519_mul( den_y, den_y,  v     );
      51             : 
      52             :   /* x = CT_ABS(2 * s * den_x) */
      53      307881 :   fd_f25519_set( tmp0, fd_f25519_two );
      54      307881 :   fd_f25519_mul( tmp0, tmp0, s     );
      55      307881 :   fd_f25519_mul( tmp0, tmp0, den_x );
      56      307881 :   fd_f25519_t x[1], y[1], t[1];
      57      307881 :   fd_f25519_abs( x, tmp0        );
      58             :   /* y = u1 * den_y */
      59      307881 :   fd_f25519_mul( y, u1, den_y   );
      60             :   /* z = 1 */
      61             :   /* t = x * y */
      62      307881 :   fd_f25519_mul( t, x, y  );
      63             : 
      64      307881 :   if( (!was_square )
      65      307881 :     | ( fd_f25519_sgn( t ) )
      66      307881 :     | ( fd_f25519_is_zero( y ) ) ) {
      67          78 :     return NULL;
      68          78 :   }
      69             : 
      70      307803 :   return fd_ed25519_point_from( h, x, y, fd_f25519_one, t );
      71      307881 : }
      72             : 
      73             : uchar *
      74             : fd_ristretto255_point_tobytes( uchar                           buf[ 32 ],
      75      300135 :                                fd_ristretto255_point_t const * h ) {
      76      300135 :   fd_f25519_t x[1], y[1], z[1], t[1];
      77      300135 :   fd_ed25519_point_to( x, y, z, t, h );
      78             : 
      79             :   // uchar out[32];
      80             :   /* u1 = (z0 + y0) * (z0 - y0) */
      81      300135 :   fd_f25519_t tmp0 [1]; fd_f25519_add( tmp0, z, y );
      82      300135 :   fd_f25519_t tmp1 [1]; fd_f25519_sub( tmp1, z, y );
      83      300135 :   fd_f25519_t u1   [1]; fd_f25519_mul( u1,   tmp0, tmp1 );
      84             : 
      85             :   /* u2 = (x0 * y0) */
      86      300135 :   fd_f25519_t u2   [1]; fd_f25519_mul( u2, x, y );
      87             : 
      88             :   /* invsqrt = SQRT_RATIO_M1(1, u1 * u2^2) */
      89      300135 :   fd_f25519_t u2_sq[1]; fd_f25519_sqr( u2_sq, u2 );
      90      300135 :   fd_f25519_mul( tmp1, u1, u2_sq );
      91      300135 :   fd_f25519_t inv_sqrt[1];
      92      300135 :   fd_f25519_inv_sqrt( inv_sqrt, tmp1 );
      93             : 
      94             :   // fd_f25519_tobytes( out, inv_sqrt );
      95             :   // FD_LOG_HEXDUMP_WARNING(( "inv_sqrt", out, 32 ));
      96             : 
      97             :   /* den1 = invsqrt * u1
      98             :      den2 = invsqrt * u2 */
      99      300135 :   fd_f25519_t den1[1]; fd_f25519_mul( den1, inv_sqrt, u1 );
     100      300135 :   fd_f25519_t den2[1]; fd_f25519_mul( den2, inv_sqrt, u2 );
     101             : 
     102             :   /* z_inv = den1 * den2 * t0 */
     103      300135 :   fd_f25519_t z_inv[1];
     104      300135 :   fd_f25519_mul( z_inv, den1,  den2 );
     105      300135 :   fd_f25519_mul( z_inv, z_inv, t );
     106             : 
     107             :   /* ix0 = x0 * SQRT_M1
     108             :      iy0 = y0 * SQRT_M1 */
     109      300135 :   fd_f25519_t ix0[1]; fd_f25519_mul( ix0, x, fd_f25519_sqrtm1 );
     110      300135 :   fd_f25519_t iy0[1]; fd_f25519_mul( iy0, y, fd_f25519_sqrtm1 );
     111             : 
     112             :   /* enchanted_denominator = den1 * INVSQRT_A_MINUS_D */
     113      300135 :   fd_f25519_t enchanted_denominator[1];
     114      300135 :   fd_f25519_mul( enchanted_denominator, den1, fd_f25519_invsqrt_a_minus_d );
     115             : 
     116             :   /* rotate = IS_NEGATIVE(t0 * z_inv) */
     117      300135 :   fd_f25519_t rotate_[1]; fd_f25519_mul( rotate_, t, z_inv );
     118      300135 :   int rotate = fd_f25519_sgn( rotate_ );
     119             :   // FD_LOG_HEXDUMP_WARNING(( "rotate", &rotate, 1 ));
     120             : 
     121             :   /* x = CT_SELECT(iy0 IF rotate ELSE x0)
     122             :      y = CT_SELECT(ix0 IF rotate ELSE y0) */
     123      300135 :   fd_f25519_if( x, rotate, iy0, x );
     124      300135 :   fd_f25519_if( y, rotate, ix0, y );
     125             : 
     126             :   // fd_f25519_tobytes( out, x );
     127             :   // FD_LOG_HEXDUMP_WARNING(( "x", out, 32 ));
     128             :   // fd_f25519_tobytes( out, y );
     129             :   // FD_LOG_HEXDUMP_WARNING(( "y", out, 32 ));
     130             : 
     131             :   /* z = z0 */
     132             :   /* den_inv = CT_SELECT(enchanted_denominator IF rotate ELSE den2) */
     133      300135 :   fd_f25519_t den_inv[1];
     134      300135 :   fd_f25519_if( den_inv, rotate, enchanted_denominator, den2 );
     135             :   // fd_f25519_tobytes( out, den_inv );
     136             :   // FD_LOG_HEXDUMP_WARNING(( "den_inv", out, 32 ));
     137             : 
     138             :   /* y = CT_NEG(y, IS_NEGATIVE(x * z_inv)) */
     139      300135 :   fd_f25519_t _isneg[1];
     140      300135 :   int isneg = fd_f25519_sgn( fd_f25519_mul( _isneg, x, z_inv ) );
     141      300135 :   fd_f25519_t y_neg[1]; fd_f25519_neg( y_neg, y );
     142      300135 :   fd_f25519_if( y, isneg, y_neg, y ); // this is not abs (condition is not sgn(y))
     143             : 
     144             :   /* s = CT_ABS(den_inv * (z - y)) */
     145      300135 :   fd_f25519_t s[1];
     146      300135 :   fd_f25519_sub( s, z, y       );
     147      300135 :   fd_f25519_mul( s, s, den_inv );
     148      300135 :   fd_f25519_abs( s, s );
     149             : 
     150      300135 :   fd_f25519_tobytes( buf, s );
     151      300135 :   return buf;
     152      300135 : }
     153             : 
     154             : /* Elligator2 map to ristretto group:
     155             :    https://ristretto.group/formulas/elligator.html
     156             :    This follows closely the golang implementation:
     157             :    https://github.com/gtank/ristretto255/blob/v0.1.2/ristretto255.go#L88 */
     158             : fd_ristretto255_point_t *
     159             : fd_ristretto255_map_to_curve( fd_ristretto255_point_t * h,
     160       90006 :                               uchar const               buf[ 32 ] ) {
     161             :   /* r = SQRT_M1 * t^2 */
     162       90006 :   fd_f25519_t r0[1];
     163       90006 :   fd_f25519_t r[1];
     164       90006 :   fd_f25519_frombytes( r0, buf );
     165       90006 :   fd_f25519_mul( r, fd_f25519_sqrtm1, fd_f25519_sqr( r, r0 ) );
     166             : 
     167             :   /* u = (r + 1) * ONE_MINUS_D_SQ */
     168       90006 :   fd_f25519_t u[1];
     169       90006 :   fd_f25519_add( u, r, fd_f25519_one );
     170       90006 :   fd_f25519_mul( u, u, fd_f25519_one_minus_d_sq ); //-> using mul2
     171             : 
     172             :   /* c = -1 */
     173       90006 :   fd_f25519_t c[1];
     174       90006 :   fd_f25519_set( c, fd_f25519_minus_one );
     175             : 
     176             :   /* v = (c - r*D) * (r + D) */
     177       90006 :   fd_f25519_t v[1], r_plus_d[1];
     178       90006 :   fd_f25519_add( r_plus_d, r, fd_f25519_d );
     179       90006 :   fd_f25519_mul( v, r, fd_f25519_d ); //-> using mul2
     180             :   // fd_f25519_mul2( v, r, fd_f25519_d,
     181             :   //                 u, u, fd_f25519_one_minus_d_sq );
     182       90006 :   fd_f25519_sub( v, c, v );
     183       90006 :   fd_f25519_mul( v, v, r_plus_d );
     184             : 
     185             :   /* (was_square, s) = SQRT_RATIO_M1(u, v) */
     186       90006 :   fd_f25519_t s[1];
     187       90006 :   uchar was_square = (uchar)fd_f25519_sqrt_ratio( s, u, v );
     188             : 
     189             :   /* s_prime = -CT_ABS(s*r0) */
     190       90006 :   fd_f25519_t s_prime[1];
     191       90006 :   fd_f25519_neg_abs( s_prime, fd_f25519_mul( s_prime, s, r0 ) );
     192             : 
     193             :         /* s = CT_SELECT(s IF was_square ELSE s_prime) */
     194       90006 :   fd_f25519_if( s, was_square, s, s_prime );
     195             :         /* c = CT_SELECT(c IF was_square ELSE r) */
     196       90006 :   fd_f25519_if( c, was_square, c, r );
     197             : 
     198             :   /* N = c * (r - 1) * D_MINUS_ONE_SQ - v */
     199       90006 :   fd_f25519_t n[1];
     200       90006 :   fd_f25519_mul( n, c, fd_f25519_sub( n, r, fd_f25519_one ) );
     201       90006 :   fd_f25519_sub( n, fd_f25519_mul( n, n, fd_f25519_d_minus_one_sq ), v );
     202             : 
     203             :   /* w0 = 2 * s * v
     204             :      w1 = N * SQRT_AD_MINUS_ONE
     205             :      w2 = 1 - s^2
     206             :      w3 = 1 + s^2 */
     207       90006 :   fd_f25519_t s2[1];
     208       90006 :   fd_f25519_sqr( s2, s );
     209       90006 :   fd_f25519_t w0[1], w1[1], w2[1], w3[1];
     210       90006 :   fd_f25519_mul2( w0,s,v, w1,n,fd_f25519_sqrt_ad_minus_one );
     211       90006 :   fd_f25519_add( w0, w0, w0 );
     212             :   // fd_f25519_mul( w1, n, sqrt_ad_minus_one );
     213       90006 :   fd_f25519_sub( w2, fd_f25519_one, s2 );
     214       90006 :   fd_f25519_add( w3, fd_f25519_one, s2 );
     215             : 
     216             :   // fd_f25519_mul( h->X, w0, w3 );
     217             :   // fd_f25519_mul( h->Y, w2, w1 );
     218             :   // fd_f25519_mul( h->Z, w1, w3 );
     219             :   // fd_f25519_mul( h->T, w0, w2 );
     220       90006 :   fd_f25519_t x[1], y[1], z[1], t[1];
     221       90006 :   fd_f25519_mul4( x,w0,w3, y,w2,w1, z,w1,w3, t,w0,w2 );
     222       90006 :   return fd_ed25519_point_from( h, x, y, z, t );
     223       90006 : }
     224             : 
     225             : fd_ristretto255_point_t *
     226             : fd_ristretto255_hash_to_curve( fd_ristretto255_point_t * h,
     227       30003 :                                uchar const               s[ 64 ] ) {
     228       30003 :   fd_ristretto255_point_t p1[1];
     229       30003 :   fd_ristretto255_point_t p2[1];
     230             : 
     231       30003 :   fd_ristretto255_map_to_curve( p1, s    );
     232       30003 :   fd_ristretto255_map_to_curve( p2, s+32 );
     233             : 
     234       30003 :   return fd_ristretto255_point_add(h, p1, p2);
     235       30003 : }