ed25519/amd64-51-30k/ge25519_unpackneg.c

   1 #include "fe25519.h"
   2 #include "ge25519.h"
   3
   4 /* d */
   5 static const fe25519 ecd = {{929955233495203, 466365720129213, 1662059464998953, 2033849074728123, 1442794654840575}};
   6 /* sqrt(-1) */
   7 static const fe25519 sqrtm1 = {{1718705420411056, 234908883556509, 2233514472574048, 2117202627021982, 765476049583133}};
   8
   9 /* return 0 on success, -1 otherwise */
  10 int ge25519_unpackneg_vartime(ge25519_p3 *r, const unsigned char p[32])
  11 {
  12   fe25519 t, chk, num, den, den2, den4, den6;
  13   unsigned char par = p[31] >> 7;
  14
  15   fe25519_setint(&r->z,1);
  16   fe25519_unpack(&r->y, p);
  17   fe25519_square(&num, &r->y); /* x = y^2 */
  18   fe25519_mul(&den, &num, &ecd); /* den = dy^2 */
  19   fe25519_sub(&num, &num, &r->z); /* x = y^2-1 */
  20   fe25519_add(&den, &r->z, &den); /* den = dy^2+1 */
  21
  22   /* Computation of sqrt(num/den)
  23      1.: computation of num^((p-5)/8)*den^((7p-35)/8) = (num*den^7)^((p-5)/8)
  24   */
  25   fe25519_square(&den2, &den);
  26   fe25519_square(&den4, &den2);
  27   fe25519_mul(&den6, &den4, &den2);
  28   fe25519_mul(&t, &den6, &num);
  29   fe25519_mul(&t, &t, &den);
  30
  31   fe25519_pow2523(&t, &t);
  32   /* 2. computation of r->x = t * num * den^3
  33   */
  34   fe25519_mul(&t, &t, &num);
  35   fe25519_mul(&t, &t, &den);
  36   fe25519_mul(&t, &t, &den);
  37   fe25519_mul(&r->x, &t, &den);
  38
  39   /* 3. Check whether sqrt computation gave correct result, multiply by sqrt(-1) if not:
  40   */
  41   fe25519_square(&chk, &r->x);
  42   fe25519_mul(&chk, &chk, &den);
  43   if (!fe25519_iseq_vartime(&chk, &num))
  44     fe25519_mul(&r->x, &r->x, &sqrtm1);
  45
  46   /* 4. Now we have one of the two square roots, except if input was not a square
  47   */
  48   fe25519_square(&chk, &r->x);
  49   fe25519_mul(&chk, &chk, &den);
  50   if (!fe25519_iseq_vartime(&chk, &num))
  51     return -1;
  52
  53   /* 5. Choose the desired square root according to parity:
  54   */
  55   if(fe25519_getparity(&r->x) != (1-par))
  56     fe25519_neg(&r->x, &r->x);
  57
  58   fe25519_mul(&r->t, &r->x, &r->y);
  59   return 0;
  60 }