1 #include "fe25519.h"
2 #include "ge25519.h"
3
4 /* d */
5 static const fe25519 ecd = {{0x75EB4DCA135978A3, 0x00700A4D4141D8AB, 0x8CC740797779E898, 0x52036CEE2B6FFE73}};
6 /* sqrt(-1) */
7 static const fe25519 sqrtm1 = {{0xC4EE1B274A0EA0B0, 0x2F431806AD2FE478, 0x2B4D00993DFBD7A7, 0x2B8324804FC1DF0B}};
8
9 /* return 0 on success, -1 otherwise */
ge25519_unpackneg_vartime(ge25519_p3 * r,const unsigned char p[32])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 }
61