Line data    Source code

       1             : #include "fd_f25519.h"
       2             : #include "../hex/fd_hex.h"
       3             : 
       4             : #if FD_HAS_AVX512
       5             : #include "avx512/fd_f25519.c"
       6             : #else
       7             : #include "ref/fd_f25519.c"
       8             : #endif
       9             : 
      10             : void
      11             : fd_f25519_debug( char const * name,
      12           0 :                  fd_f25519_t const * a ) {
      13           0 :   char *
      14           0 :   fd_hex_encode( char *       FD_RESTRICT dst,
      15           0 :                  void const * FD_RESTRICT src,
      16           0 :                  ulong                    sz );
      17           0 :   uchar out[ 32 ];
      18           0 :   char buf[ 65 ] = { 0 };
      19           0 :   fd_f25519_tobytes( out, a );
      20           0 :   fd_hex_encode( buf, out, 32UL );
      21           0 :   FD_LOG_WARNING(( "%s: %s", name, buf ));
      22           0 :   FD_LOG_HEXDUMP_WARNING(( name, a, sizeof(fd_f25519_t) ));
      23           0 : }
      24             : 
      25             : /* fd_f25519_pow22523 computes r = a^(2^252-3), and returns r. */
      26             : fd_f25519_t *
      27             : fd_f25519_pow22523( fd_f25519_t *       r,
      28     2122812 :                     fd_f25519_t const * a ) {
      29     2122812 :   fd_f25519_t t0[1];
      30     2122812 :   fd_f25519_t t1[1];
      31     2122812 :   fd_f25519_t t2[1];
      32             : 
      33     2122812 :   fd_f25519_sqr( t0, a      );
      34     2122812 :   fd_f25519_sqr( t1, t0     );
      35     4245624 :   for( int i=1; i<  2; i++ ) fd_f25519_sqr( t1, t1 );
      36             : 
      37     2122812 :   fd_f25519_mul( t1, a,  t1 );
      38     2122812 :   fd_f25519_mul( t0, t0, t1 );
      39     2122812 :   fd_f25519_sqr( t0, t0     );
      40     2122812 :   fd_f25519_mul( t0, t1, t0 );
      41     2122812 :   fd_f25519_sqr( t1, t0     );
      42    10614060 :   for( int i=1; i<  5; i++ ) fd_f25519_sqr( t1, t1 );
      43             : 
      44     2122812 :   fd_f25519_mul( t0, t1, t0 );
      45     2122812 :   fd_f25519_sqr( t1, t0     );
      46    21228120 :   for( int i=1; i< 10; i++ ) fd_f25519_sqr( t1, t1 );
      47             : 
      48     2122812 :   fd_f25519_mul( t1, t1, t0 );
      49     2122812 :   fd_f25519_sqr( t2, t1     );
      50    42456240 :   for( int i=1; i< 20; i++ ) fd_f25519_sqr( t2, t2 );
      51             : 
      52     2122812 :   fd_f25519_mul( t1, t2, t1 );
      53     2122812 :   fd_f25519_sqr( t1, t1     );
      54    21228120 :   for( int i=1; i< 10; i++ ) fd_f25519_sqr( t1, t1 );
      55             : 
      56     2122812 :   fd_f25519_mul( t0, t1, t0 );
      57     2122812 :   fd_f25519_sqr( t1, t0     );
      58   106140600 :   for( int i=1; i< 50; i++ ) fd_f25519_sqr( t1, t1 );
      59             : 
      60     2122812 :   fd_f25519_mul( t1, t1, t0 );
      61     2122812 :   fd_f25519_sqr( t2, t1     );
      62   212281200 :   for( int i=1; i<100; i++ ) fd_f25519_sqr( t2, t2 );
      63             : 
      64     2122812 :   fd_f25519_mul( t1, t2, t1 );
      65     2122812 :   fd_f25519_sqr( t1, t1     );
      66   106140600 :   for( int i=1; i< 50; i++ ) fd_f25519_sqr( t1, t1 );
      67             : 
      68     2122812 :   fd_f25519_mul( t0, t1, t0 );
      69     2122812 :   fd_f25519_sqr( t0, t0     );
      70     4245624 :   for( int i=1; i<  2; i++ ) fd_f25519_sqr( t0, t0 );
      71             : 
      72     2122812 :   fd_f25519_mul(r, t0, a  );
      73     2122812 :   return r;
      74     2122812 : }
      75             : 
      76             : /* fd_f25519_inv computes r = 1/a, and returns r. */
      77             : fd_f25519_t *
      78             : fd_f25519_inv( fd_f25519_t *       r,
      79     1936569 :                fd_f25519_t const * a ) {
      80     1936569 :   fd_f25519_t t0[1];
      81     1936569 :   fd_f25519_t t1[1];
      82     1936569 :   fd_f25519_t t2[1];
      83     1936569 :   fd_f25519_t t3[1];
      84             : 
      85             :   /* Compute z**-1 = z**(2**255 - 19 - 2) with the exponent as
      86             :      2**255 - 21 = (2**5) * (2**250 - 1) + 11. */
      87             : 
      88     1936569 :   fd_f25519_sqr( t0,  a     );                        /* t0 = z**2 */
      89     1936569 :   fd_f25519_sqr( t1, t0     );
      90     1936569 :   fd_f25519_sqr( t1, t1     );                        /* t1 = t0**(2**2) = z**8 */
      91     1936569 :   fd_f25519_mul( t1,  a, t1 );                        /* t1 = z * t1 = z**9 */
      92     1936569 :   fd_f25519_mul( t0, t0, t1 );                        /* t0 = t0 * t1 = z**11 -- stash t0 away for the end. */
      93     1936569 :   fd_f25519_sqr( t2, t0     );                        /* t2 = t0**2 = z**22 */
      94     1936569 :   fd_f25519_mul( t1, t1, t2 );                        /* t1 = t1 * t2 = z**(2**5 - 1) */
      95     1936569 :   fd_f25519_sqr( t2, t1     );
      96     9682845 :   for( int i=1; i<  5; i++ ) fd_f25519_sqr( t2, t2 ); /* t2 = t1**(2**5) = z**((2**5) * (2**5 - 1)) */
      97     1936569 :   fd_f25519_mul( t1, t2, t1 );                        /* t1 = t1 * t2 = z**((2**5 + 1) * (2**5 - 1)) = z**(2**10 - 1) */
      98     1936569 :   fd_f25519_sqr( t2, t1     );
      99    19365690 :   for( int i=1; i< 10; i++ ) fd_f25519_sqr( t2, t2 );
     100     1936569 :   fd_f25519_mul( t2, t2, t1 );                        /* t2 = z**(2**20 - 1) */
     101     1936569 :   fd_f25519_sqr( t3, t2     );
     102    38731380 :   for( int i=1; i< 20; i++ ) fd_f25519_sqr( t3, t3 );
     103     1936569 :   fd_f25519_mul( t2, t3, t2 );                        /* t2 = z**(2**40 - 1) */
     104    21302259 :   for( int i=0; i< 10; i++ ) fd_f25519_sqr( t2, t2 ); /* t2 = z**(2**10) * (2**40 - 1) */
     105     1936569 :   fd_f25519_mul( t1, t2, t1 );                        /* t1 = z**(2**50 - 1) */
     106     1936569 :   fd_f25519_sqr( t2, t1     );
     107    96828450 :   for( int i=1; i< 50; i++ ) fd_f25519_sqr( t2, t2 );
     108     1936569 :   fd_f25519_mul( t2, t2, t1 );                        /* t2 = z**(2**100 - 1) */
     109     1936569 :   fd_f25519_sqr( t3, t2     );
     110   193656900 :   for( int i=1; i<100; i++ ) fd_f25519_sqr( t3, t3 );
     111     1936569 :   fd_f25519_mul( t2, t3, t2 );                        /* t2 = z**(2**200 - 1) */
     112     1936569 :   fd_f25519_sqr( t2, t2     );
     113    96828450 :   for( int i=1; i< 50; i++ ) fd_f25519_sqr( t2, t2 ); /* t2 = z**((2**50) * (2**200 - 1) */
     114     1936569 :   fd_f25519_mul( t1, t2, t1 );                        /* t1 = z**(2**250 - 1) */
     115     1936569 :   fd_f25519_sqr( t1, t1     );
     116     9682845 :   for( int i=1; i<  5; i++ ) fd_f25519_sqr( t1, t1 ); /* t1 = z**((2**5) * (2**250 - 1)) */
     117     1936569 :   return fd_f25519_mul( r, t1, t0 );                  /* Recall t0 = z**11; out = z**(2**255 - 21) */
     118     1936569 : }
     119             : 
     120             : /* fd_f25519_sqrt_ratio computes r = (u * v^3) * (u * v^7)^((p-5)/8),
     121             :    returns 0 on success, 1 on failure. */
     122             : int
     123             : fd_f25519_sqrt_ratio( fd_f25519_t *       r,
     124             :                       fd_f25519_t const * u,
     125     1822812 :                       fd_f25519_t const * v ) {
     126             :   /* r = (u * v^3) * (u * v^7)^((p-5)/8) */
     127     1822812 :   fd_f25519_t  v2[1]; fd_f25519_sqr(  v2, v      );
     128     1822812 :   fd_f25519_t  v3[1]; fd_f25519_mul(  v3, v2, v  );
     129     1822812 :   fd_f25519_t uv3[1]; fd_f25519_mul( uv3, u,  v3 );
     130     1822812 :   fd_f25519_t  v6[1]; fd_f25519_sqr(  v6, v3     );
     131     1822812 :   fd_f25519_t  v7[1]; fd_f25519_mul(  v7, v6, v  );
     132     1822812 :   fd_f25519_t uv7[1]; fd_f25519_mul( uv7, u,  v7 );
     133     1822812 :   fd_f25519_pow22523( r, uv7    );
     134     1822812 :   fd_f25519_mul     ( r, r, uv3 );
     135             : 
     136             :   /* check = v * r^2 */
     137     1822812 :   fd_f25519_t check[1];
     138     1822812 :   fd_f25519_sqr( check, r        );
     139     1822812 :   fd_f25519_mul( check, check, v );
     140             : 
     141             :   /* (correct_sign_sqrt)    check == u
     142             :      (flipped_sign_sqrt)    check == !u
     143             :      (flipped_sign_sqrt_i)  check == (!u * SQRT_M1) */
     144     1822812 :   fd_f25519_t u_neg[1];        fd_f25519_neg( u_neg,        u );
     145     1822812 :   fd_f25519_t u_neg_sqrtm1[1]; fd_f25519_mul( u_neg_sqrtm1, u_neg, fd_f25519_sqrtm1 );
     146     1822812 :   int correct_sign_sqrt   = fd_f25519_eq( check, u );
     147     1822812 :   int flipped_sign_sqrt   = fd_f25519_eq( check, u_neg );
     148     1822812 :   int flipped_sign_sqrt_i = fd_f25519_eq( check, u_neg_sqrtm1 );
     149             : 
     150             :   /* r_prime = SQRT_M1 * r */
     151     1822812 :   fd_f25519_t r_prime[1];
     152     1822812 :   fd_f25519_mul( r_prime, r, fd_f25519_sqrtm1 );
     153             : 
     154             :   /* r = CT_SELECT(r_prime IF flipped_sign_sqrt | flipped_sign_sqrt_i ELSE r) */
     155     1822812 :   fd_f25519_if( r, flipped_sign_sqrt|flipped_sign_sqrt_i, r_prime, r );
     156     1822812 :   fd_f25519_abs( r, r );
     157     1822812 :   return correct_sign_sqrt|flipped_sign_sqrt;
     158     1822812 : }