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      716628 :                     fd_f25519_t const * a ) {
      29      716628 :   fd_f25519_t t0[1];
      30      716628 :   fd_f25519_t t1[1];
      31      716628 :   fd_f25519_t t2[1];
      32             : 
      33      716628 :   fd_f25519_sqr( t0, a      );
      34      716628 :   fd_f25519_sqr( t1, t0     );
      35     1433256 :   for( int i=1; i<  2; i++ ) fd_f25519_sqr( t1, t1 );
      36             : 
      37      716628 :   fd_f25519_mul( t1, a,  t1 );
      38      716628 :   fd_f25519_mul( t0, t0, t1 );
      39      716628 :   fd_f25519_sqr( t0, t0     );
      40      716628 :   fd_f25519_mul( t0, t1, t0 );
      41      716628 :   fd_f25519_sqr( t1, t0     );
      42     3583140 :   for( int i=1; i<  5; i++ ) fd_f25519_sqr( t1, t1 );
      43             : 
      44      716628 :   fd_f25519_mul( t0, t1, t0 );
      45      716628 :   fd_f25519_sqr( t1, t0     );
      46     7166280 :   for( int i=1; i< 10; i++ ) fd_f25519_sqr( t1, t1 );
      47             : 
      48      716628 :   fd_f25519_mul( t1, t1, t0 );
      49      716628 :   fd_f25519_sqr( t2, t1     );
      50    14332560 :   for( int i=1; i< 20; i++ ) fd_f25519_sqr( t2, t2 );
      51             : 
      52      716628 :   fd_f25519_mul( t1, t2, t1 );
      53      716628 :   fd_f25519_sqr( t1, t1     );
      54     7166280 :   for( int i=1; i< 10; i++ ) fd_f25519_sqr( t1, t1 );
      55             : 
      56      716628 :   fd_f25519_mul( t0, t1, t0 );
      57      716628 :   fd_f25519_sqr( t1, t0     );
      58    35831400 :   for( int i=1; i< 50; i++ ) fd_f25519_sqr( t1, t1 );
      59             : 
      60      716628 :   fd_f25519_mul( t1, t1, t0 );
      61      716628 :   fd_f25519_sqr( t2, t1     );
      62    71662800 :   for( int i=1; i<100; i++ ) fd_f25519_sqr( t2, t2 );
      63             : 
      64      716628 :   fd_f25519_mul( t1, t2, t1 );
      65      716628 :   fd_f25519_sqr( t1, t1     );
      66    35831400 :   for( int i=1; i< 50; i++ ) fd_f25519_sqr( t1, t1 );
      67             : 
      68      716628 :   fd_f25519_mul( t0, t1, t0 );
      69      716628 :   fd_f25519_sqr( t0, t0     );
      70     1433256 :   for( int i=1; i<  2; i++ ) fd_f25519_sqr( t0, t0 );
      71             : 
      72      716628 :   fd_f25519_mul(r, t0, a  );
      73      716628 :   return r;
      74      716628 : }
      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      202683 :                fd_f25519_t const * a ) {
      80      202683 :   fd_f25519_t t0[1];
      81      202683 :   fd_f25519_t t1[1];
      82      202683 :   fd_f25519_t t2[1];
      83      202683 :   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      202683 :   fd_f25519_sqr( t0,  a     );                        /* t0 = z**2 */
      89      202683 :   fd_f25519_sqr( t1, t0     );
      90      202683 :   fd_f25519_sqr( t1, t1     );                        /* t1 = t0**(2**2) = z**8 */
      91      202683 :   fd_f25519_mul( t1,  a, t1 );                        /* t1 = z * t1 = z**9 */
      92      202683 :   fd_f25519_mul( t0, t0, t1 );                        /* t0 = t0 * t1 = z**11 -- stash t0 away for the end. */
      93      202683 :   fd_f25519_sqr( t2, t0     );                        /* t2 = t0**2 = z**22 */
      94      202683 :   fd_f25519_mul( t1, t1, t2 );                        /* t1 = t1 * t2 = z**(2**5 - 1) */
      95      202683 :   fd_f25519_sqr( t2, t1     );
      96     1013415 :   for( int i=1; i<  5; i++ ) fd_f25519_sqr( t2, t2 ); /* t2 = t1**(2**5) = z**((2**5) * (2**5 - 1)) */
      97      202683 :   fd_f25519_mul( t1, t2, t1 );                        /* t1 = t1 * t2 = z**((2**5 + 1) * (2**5 - 1)) = z**(2**10 - 1) */
      98      202683 :   fd_f25519_sqr( t2, t1     );
      99     2026830 :   for( int i=1; i< 10; i++ ) fd_f25519_sqr( t2, t2 );
     100      202683 :   fd_f25519_mul( t2, t2, t1 );                        /* t2 = z**(2**20 - 1) */
     101      202683 :   fd_f25519_sqr( t3, t2     );
     102     4053660 :   for( int i=1; i< 20; i++ ) fd_f25519_sqr( t3, t3 );
     103      202683 :   fd_f25519_mul( t2, t3, t2 );                        /* t2 = z**(2**40 - 1) */
     104     2229513 :   for( int i=0; i< 10; i++ ) fd_f25519_sqr( t2, t2 ); /* t2 = z**(2**10) * (2**40 - 1) */
     105      202683 :   fd_f25519_mul( t1, t2, t1 );                        /* t1 = z**(2**50 - 1) */
     106      202683 :   fd_f25519_sqr( t2, t1     );
     107    10134150 :   for( int i=1; i< 50; i++ ) fd_f25519_sqr( t2, t2 );
     108      202683 :   fd_f25519_mul( t2, t2, t1 );                        /* t2 = z**(2**100 - 1) */
     109      202683 :   fd_f25519_sqr( t3, t2     );
     110    20268300 :   for( int i=1; i<100; i++ ) fd_f25519_sqr( t3, t3 );
     111      202683 :   fd_f25519_mul( t2, t3, t2 );                        /* t2 = z**(2**200 - 1) */
     112      202683 :   fd_f25519_sqr( t2, t2     );
     113    10134150 :   for( int i=1; i< 50; i++ ) fd_f25519_sqr( t2, t2 ); /* t2 = z**((2**50) * (2**200 - 1) */
     114      202683 :   fd_f25519_mul( t1, t2, t1 );                        /* t1 = z**(2**250 - 1) */
     115      202683 :   fd_f25519_sqr( t1, t1     );
     116     1013415 :   for( int i=1; i<  5; i++ ) fd_f25519_sqr( t1, t1 ); /* t1 = z**((2**5) * (2**250 - 1)) */
     117      202683 :   return fd_f25519_mul( r, t1, t0 );                  /* Recall t0 = z**11; out = z**(2**255 - 21) */
     118      202683 : }
     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      716628 :                       fd_f25519_t const * v ) {
     126             :   /* r = (u * v^3) * (u * v^7)^((p-5)/8) */
     127      716628 :   fd_f25519_t  v2[1]; fd_f25519_sqr(  v2, v      );
     128      716628 :   fd_f25519_t  v3[1]; fd_f25519_mul(  v3, v2, v  );
     129      716628 :   fd_f25519_t uv3[1]; fd_f25519_mul( uv3, u,  v3 );
     130      716628 :   fd_f25519_t  v6[1]; fd_f25519_sqr(  v6, v3     );
     131      716628 :   fd_f25519_t  v7[1]; fd_f25519_mul(  v7, v6, v  );
     132      716628 :   fd_f25519_t uv7[1]; fd_f25519_mul( uv7, u,  v7 );
     133      716628 :   fd_f25519_pow22523( r, uv7    );
     134      716628 :   fd_f25519_mul     ( r, r, uv3 );
     135             : 
     136             :   /* check = v * r^2 */
     137      716628 :   fd_f25519_t check[1];
     138      716628 :   fd_f25519_sqr( check, r        );
     139      716628 :   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      716628 :   fd_f25519_t u_neg[1];        fd_f25519_neg( u_neg,        u );
     145      716628 :   fd_f25519_t u_neg_sqrtm1[1]; fd_f25519_mul( u_neg_sqrtm1, u_neg, fd_f25519_sqrtm1 );
     146      716628 :   int correct_sign_sqrt   = fd_f25519_eq( check, u );
     147      716628 :   int flipped_sign_sqrt   = fd_f25519_eq( check, u_neg );
     148      716628 :   int flipped_sign_sqrt_i = fd_f25519_eq( check, u_neg_sqrtm1 );
     149             : 
     150             :   /* r_prime = SQRT_M1 * r */
     151      716628 :   fd_f25519_t r_prime[1];
     152      716628 :   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      716628 :   fd_f25519_if( r, flipped_sign_sqrt|flipped_sign_sqrt_i, r_prime, r );
     156      716628 :   fd_f25519_abs( r, r );
     157      716628 :   return correct_sign_sqrt|flipped_sign_sqrt;
     158      716628 : }