-rw-r--r-- 1978 high-ctidh-20210504/elligator.c
#include "crypto_declassify.h"
#include "elligator.h"
void elligator(proj *plus,proj *minus,const proj *A)
{
for (;;) {
fp u; fp_random(&u);
long long reject = fp_iszero(&u);
crypto_declassify(&reject,sizeof reject);
if (reject) continue; /* bad RNG outputs 0 */
fp u2; fp_sq2(&u2,&u);
fp D; fp_sub3(&D,&u2,&fp_1);
reject = fp_iszero(&D);
crypto_declassify(&reject,sizeof reject);
if (reject) continue; /* bad RNG outputs +-1 */
fp M; fp_mul3(&M,&A->x,&u2); /* M = u^2 A->x */
fp T; fp_mul3(&T,&A->x,&M); /* T = u^2 A->x^2 */
long long control = fp_iszero(&A->x);
fp P = A->x;
fp_cmov(&P,&fp_1,control); /* P = 1 if A->x = 0 else A->x */
fp_cmov(&M,&fp_1,control); /* M = 1 if A->x = 0 else u^2 A->x */
fp_cmov(&T,&fp_1,control); /* T = 1 if A->x = 0 */
fp_mul2(&D,&A->z); /* D = (u^2-1) A->z */
fp D2; fp_sq2(&D2,&D); /* D2 = (u^2-1)^2 A->z^2 */
fp_add2(&T,&D2); /* T = 1 + (u^2-1)^2 A->z^2 if A->x = 0, else u^2 A->x^2 + (u^2-1)^2 A->z^2 */
fp_mul2(&T,&D);
fp_mul2(&T,&P);
/* T = (u^2-1)A->z(1+(u^2-1)^2 A->z^2) if A->x = 0 */
/* else (u^2-1) A->z A->x(u^2 A->x^2 + (u^2-1)^2 A->z^2) */
/* plus point will be P/D = 1/(u^2-1)A->z if A->x = 0 else A/(u^2-1) */
/* and minus point will be -M/D = -1/(u^2-1)A->z if A->x = 0 else -u^2 A/(u^2-1) */
/* unless they're flipped, which is determined by T */
/* T = Az^4 (1-u^2)^4 ((P/D)^3+A(P/D)^2+(P/D)) */
/* so T squareness says whether P/D is on curve */
/* also says whether -M/D is not on curve: */
/* in all cases -M/D = -P/D-A */
/* so (-M/D)^3+A(-M/D)^2+(-M/D) = (-P/D-A)^3+A(-P/D-A)^2+(-P/D-A) */
/* = ((P/D)^3+A(P/D)^2+(P/D)) (-1-AD/P) */
/* and by construction -1-AD/P is a non-square */
/* since it's -1 if A=0, else -u^2 */
plus->x = P;
fp_neg2(&minus->x,&M);
fp_cswap(&plus->x,&minus->x,1-fp_sqrt(&T));
plus->z = D;
minus->z = D;
return;
}
}