-rw-r--r-- 2481 high-ctidh-20210504/validate.c
#include <string.h> #include <assert.h> #include "csidh.h" #include "primes.h" // XXX: use affine initial P to save time in xMUL static int validate_rec(proj *P, proj const *A, long long lower, long long upper, uintbig *order, int *criticaltestdone) { proj Q; proj A24; xA24(&A24,A); assert(lower < upper); if (upper - lower == 1) { // now P is [(p+1) / l_lower] times the original random point if (fp_iszero(&P->z)) return 0; if (*criticaltestdone != 1) { // is original point times p+1 the identity? test this via first l that we see xMUL_dac(&Q, &A24, 1, P, primes_dac[lower], primes_daclen[lower], primes_daclen[lower]); if (!fp_iszero(&Q.z)) return -1; *criticaltestdone = 1; } uintbig_mul3_64(order, order, primes[lower]); uintbig tmp; if (uintbig_sub3(&tmp, &uintbig_four_sqrt_p, order)) return 1; return 0; } long long mid = lower + (upper - lower + 1) / 2; Q = *P; for (long long i = lower; i < mid; ++i) xMUL_dac(&Q,&A24,1,&Q,primes_dac[i],primes_daclen[i],primes_daclen[i]); int result = validate_rec(&Q, A, mid, upper, order, criticaltestdone); if (result) return result; Q = *P; for (long long i = mid; i < upper; ++i) xMUL_dac(&Q,&A24,1,&Q,primes_dac[i],primes_daclen[i],primes_daclen[i]); return validate_rec(&Q, A, lower, mid, order, criticaltestdone); } int validate_cutofforder_v2(uintbig *order,const fp *P,const fp *A) { const proj Aproj = {*A,fp_1}; proj Pproj = {*P,fp_1}; proj A24; int criticaltestdone = 0; xA24(&A24,&Aproj); /* maximal 2-power in p+1 */ xDBL(&Pproj,&Pproj,&A24,1); xDBL(&Pproj,&Pproj,&A24,1); *order = uintbig_1; return validate_rec(&Pproj,&Aproj,0,primes_num,order,&criticaltestdone); } // output: true if key is valid // output: false if key is invalid bool validate(public_key const *in) { uintbig tmp; if (!uintbig_sub3(&tmp,&in->A.x,&uintbig_p)) return false; // A >= p, invalid fp tmp2 = fp_2; if (!memcmp(&in->A,&tmp2,sizeof(fp))) return false; // A = 2, invalid fp_add2(&tmp2,&in->A); if (fp_iszero(&tmp2)) return false; // A = -2, invalid for (;;) { fp P; fp_random(&P); uintbig tmp; switch(validate_cutofforder_v2(&tmp,&P,&in->A)) { case 1: return true; case -1: return false; } // case 0: P didn't have big enough order to prove supersingularity } }