diff options
Diffstat (limited to 'moon-abe/pbc-0.5.14/ecc/d_param.c')
| -rw-r--r-- | moon-abe/pbc-0.5.14/ecc/d_param.c | 1258 |
1 files changed, 0 insertions, 1258 deletions
diff --git a/moon-abe/pbc-0.5.14/ecc/d_param.c b/moon-abe/pbc-0.5.14/ecc/d_param.c deleted file mode 100644 index 8b7d6ac5..00000000 --- a/moon-abe/pbc-0.5.14/ecc/d_param.c +++ /dev/null @@ -1,1258 +0,0 @@ -// Type D pairings, aka MNT curves. - -#include <stdarg.h> -#include <stdio.h> -#include <stdint.h> // for intptr_t -#include <stdlib.h> -#include <string.h> -#include <gmp.h> -#include "pbc_utils.h" -#include "pbc_field.h" -#include "pbc_poly.h" -#include "pbc_hilbert.h" -#include "pbc_fp.h" -#include "pbc_fieldquadratic.h" -#include "pbc_mnt.h" -#include "pbc_curve.h" -#include "pbc_param.h" -#include "pbc_pairing.h" -#include "pbc_memory.h" -#include "pbc_d_param.h" -#include "ecc/param.h" - -struct d_param_s { - mpz_t q; // curve defined over F_q - mpz_t n; // has order n (= q - t + 1) in F_q - mpz_t h; // h * r = n, r is prime - mpz_t r; - mpz_t a, b; // curve equation is y^2 = x^3 + ax + b - int k; // embedding degree - mpz_t nk; // order of curve over F_q^k - mpz_t hk; // hk * r^2 = nk - mpz_t *coeff; // coefficients of polynomial used to extend F_q by k/2 - mpz_t nqr; // a quadratic nonresidue in F_q^d that lies in F_q -}; - -typedef struct d_param_s d_param_t[1]; -typedef struct d_param_s *d_param_ptr; - -// Per-pairing data. -typedef struct { - field_t Fq, Fqx, Fqd, Fqk; // The fields F_q, F_q[x], F_q^d, F_q^k. - field_t Eq, Etwist; // The curves E(F_q) and E'(F_q^d). - // Let v be the quadratic nonresidue used to construct F_q^k from F_q^d, - // namely Fqk = Fqd[sqrt(v)]. - element_t nqrinv, nqrinv2; // The constants v^-1 and v^-2. - mpz_t tateexp; // The Tate exponent, - // to standardize coset representatives. - int k; // The embedding degree, usually 6. - // Let x be the element used to build Fqd from Fq, i.e. Fqd = Fq[x]. - element_t xpowq, xpowq2; // x^q and x^{2q} in F_q^d. -} *pptr; - -static void d_clear(void *data) { - d_param_ptr param = data; - int d = param->k / 2; - int i; - mpz_clear(param->q); - mpz_clear(param->n); - mpz_clear(param->h); - mpz_clear(param->r); - mpz_clear(param->a); - mpz_clear(param->b); - mpz_clear(param->nk); - mpz_clear(param->hk); - mpz_clear(param->nqr); - for (i=0; i<d; i++) { - mpz_clear(param->coeff[i]); - } - pbc_free(param->coeff); - pbc_free(data); -} - -static void d_out_str(FILE *stream, void *data) { - d_param_ptr p = data; - int d = p->k / 2; - int i; - char s[8]; - param_out_type(stream, "d"); - param_out_mpz(stream, "q", p->q); - param_out_mpz(stream, "n", p->n); - param_out_mpz(stream, "h", p->h); - param_out_mpz(stream, "r", p->r); - param_out_mpz(stream, "a", p->a); - param_out_mpz(stream, "b", p->b); - param_out_int(stream, "k", p->k); - param_out_mpz(stream, "nk", p->nk); - param_out_mpz(stream, "hk", p->hk); - for (i=0; i<d; i++) { - sprintf(s, "coeff%d", i); - param_out_mpz(stream, s, p->coeff[i]); - } - param_out_mpz(stream, "nqr", p->nqr); -} - -// Define l = aX + bY + c where a, b, c are in Fq. -// Compute e0 = l(Q) specialized for the case when Q has the form -// (Qx, Qy * sqrt(v)) where Qx, Qy are in Fqd and v is the quadratic nonresidue -// used to construct the quadratic field extension Fqk of Fqd. -static inline void d_miller_evalfn(element_t e0, - element_t a, element_t b, element_t c, element_t Qx, element_t Qy) { - element_ptr re_out = element_x(e0); - element_ptr im_out = element_y(e0); - - int i; - int d = polymod_field_degree(re_out->field); - for (i = 0; i < d; i++) { - element_mul(element_item(re_out, i), element_item(Qx, i), a); - element_mul(element_item(im_out, i), element_item(Qy, i), b); - } - element_add(element_item(re_out, 0), element_item(re_out, 0), c); -} - -// Miller's algorithm, assuming we can ignore the denominator. We can do this -// with careful group selection when the embedding degree is even. See thesis. -// This version uses projective coordinates, which don't seem much faster. -static void cc_miller_no_denom_proj(element_t res, mpz_t q, element_t P, - element_ptr Qx, element_ptr Qy) { - int m; - element_t v; - element_t Z; - element_t a, b, c; - element_t t0, t1; - element_ptr t2 = a, t3 = b, t4 = c; - element_t e0; - element_t z, z2; - element_ptr Zx, Zy; - const element_ptr curve_a = curve_a_coeff(P); - const element_ptr Px = curve_x_coord(P); - const element_ptr Py = curve_y_coord(P); - - #define proj_double() { \ - /* t0 = 3x^2 + (curve_a) z^4 */ \ - element_square(t0, Zx); \ - /* element_mul_si(t0, t0, 3); */ \ - element_double(t1, t0); \ - element_add(t0, t0, t1); \ - element_square(t1, z2); \ - element_mul(t1, t1, curve_a); \ - element_add(t0, t0, t1); \ - \ - /* z_out = 2 y z */ \ - element_mul(z, Zy, z); \ - /* element_mul_si(z, z, 2); */ \ - element_double(z, z); \ - element_square(z2, z); \ - \ - /* t1 = 4 x y^2 */ \ - element_square(t2, Zy); \ - element_mul(t1, Zx, t2); \ - /* element_mul_si(t1, t1, 4); */ \ - element_double(t1, t1); \ - element_double(t1, t1); \ - \ - /* x_out = t0^2 - 2 t1 */ \ - /* element_mul_si(t3, t1, 2); */ \ - element_double(t3, t1); \ - element_square(Zx, t0); \ - element_sub(Zx, Zx, t3); \ - \ - /* t2 = 8y^4 */ \ - element_square(t2, t2); \ - /* element_mul_si(t2, t2, 8); */ \ - element_double(t2, t2); \ - element_double(t2, t2); \ - element_double(t2, t2); \ - \ - /* y_out = t0(t1 - x_out) - t2 */ \ - element_sub(t1, t1, Zx); \ - element_mul(t0, t0, t1); \ - element_sub(Zy, t0, t2); \ - } - - #define proj_mixin() { \ - /* t2 = Px z^2 */ \ - element_mul(t2, z2, Px); \ - \ - /* t3 = Zx - t2 */ \ - element_sub(t3, Zx, t2); \ - \ - /* t0 = Py z^3 */ \ - element_mul(t0, z2, Py); \ - element_mul(t0, t0, z); \ - \ - /* t1 = Zy - t0 */ \ - element_sub(t1, Zy, t0); \ - \ - /* e7 = Zx + t2, use t2 to double for e7 */ \ - element_add(t2, Zx, t2); \ - \ - /* e8 = Zy + t0, use t0 to double for e8 */ \ - element_add(t0, Zy, t0); \ - \ - /* z = z t3 */ \ - element_mul(z, z, t3); \ - element_square(z2, z); \ - \ - /* Zx = t1^2 - e7 t3^2 */ \ - /* t3 now holds t3^3, */ \ - /* t4 holds e7 t3^2. */ \ - element_square(t4, t3); \ - element_mul(t3, t4, t3); \ - element_square(Zx, t1); \ - element_mul(t4, t2, t4); \ - element_sub(Zx, Zx, t4); \ - \ - /* t4 = e7 t3^2 - 2 Zx */ \ - element_sub(t4, t4, Zx); \ - element_sub(t4, t4, Zx); \ - \ - /* Zy = (t4 t1 - e8 t3^3)/2 */ \ - element_mul(t4, t4, t1); \ - element_mul(t0, t0, t3); \ - element_sub(t4, t4, t0); \ - element_halve(Zy, t4); \ - } - - #define do_tangent() { \ - /* a = -(3x^2 + cca z^4) */ \ - /* b = 2 y z^3 */ \ - /* c = -(2 y^2 + x a) */ \ - /* a = z^2 a */ \ - element_square(a, z2); \ - element_mul(a, a, curve_a); \ - element_square(b, Zx); \ - /* element_mul_si(b, b, 3); */ \ - element_double(t0, b); \ - element_add(b, b, t0); \ - element_add(a, a, b); \ - element_neg(a, a); \ - \ - element_mul(b, z, z2); \ - element_mul(b, b, Zy); \ - element_mul_si(b, b, 2); \ - \ - element_mul(c, Zx, a); \ - element_mul(a, a, z2); \ - element_square(t0, Zy); \ - element_mul_si(t0, t0, 2); \ - element_add(c, c, t0); \ - element_neg(c, c); \ - \ - d_miller_evalfn(e0, a, b, c, Qx, Qy); \ - element_mul(v, v, e0); \ - } - - #define do_line() { \ - /* a = -(Py z^3 - Zy) */ \ - /* b = Px z^3 - Zx z */ \ - /* c = Zx z Py - Zy Px; */ \ - \ - element_mul(t0, Zx, z); \ - element_mul(t1, z2, z); \ - \ - element_mul(a, Py, t1); \ - element_sub(a, Zy, a); \ - \ - element_mul(b, Px, t1); \ - element_sub(b, b, t0); \ - \ - element_mul(t0, t0, Py); \ - element_mul(c, Zy, Px); \ - element_sub(c, t0, c); \ - \ - d_miller_evalfn(e0, a, b, c, Qx, Qy); \ - element_mul(v, v, e0); \ - } - - element_init(a, Px->field); - element_init(b, a->field); - element_init(c, a->field); - element_init(t0, a->field); - element_init(t1, a->field); - element_init(e0, res->field); - element_init(z, a->field); - element_init(z2, a->field); - element_set1(z); - element_set1(z2); - - element_init(v, res->field); - element_init(Z, P->field); - - element_set(Z, P); - Zx = curve_x_coord(Z); - Zy = curve_x_coord(Z); - - element_set1(v); - m = mpz_sizeinbase(q, 2) - 2; - - for(;;) { - do_tangent(); - if (!m) break; - proj_double(); - if (mpz_tstbit(q, m)) { - do_line(); - proj_mixin(); - } - m--; - element_square(v, v); - } - - element_set(res, v); - - element_clear(v); - element_clear(Z); - element_clear(a); - element_clear(b); - element_clear(c); - element_clear(t0); - element_clear(t1); - element_clear(e0); - element_clear(z); - element_clear(z2); - #undef proj_double - #undef proj_mixin - #undef do_tangent - #undef do_line -} - -// Same as above, but with affine coordinates. -static void cc_miller_no_denom_affine(element_t res, mpz_t q, element_t P, - element_ptr Qx, element_ptr Qy) { - int m; - element_t v; - element_t Z; - element_t a, b, c; - element_t t0; - element_t e0; - const element_ptr cca = curve_a_coeff(P); - const element_ptr Px = curve_x_coord(P); - const element_ptr Py = curve_y_coord(P); - element_ptr Zx, Zy; - - /* TODO: when exactly is this not needed? - void do_vertical() { - mapbase(e0, Z->x); - element_sub(e0, Qx, e0); - element_mul(v, v, e0); - } - */ - - #define do_tangent() { \ - /* a = -(3 Zx^2 + cc->a) */ \ - /* b = 2 * Zy */ \ - /* c = -(2 Zy^2 + a Zx); */ \ - \ - element_square(a, Zx); \ - element_mul_si(a, a, 3); \ - element_add(a, a, cca); \ - element_neg(a, a); \ - \ - element_add(b, Zy, Zy); \ - \ - element_mul(t0, b, Zy); \ - element_mul(c, a, Zx); \ - element_add(c, c, t0); \ - element_neg(c, c); \ - \ - d_miller_evalfn(e0, a, b, c, Qx, Qy); \ - element_mul(v, v, e0); \ - } - - #define do_line() { \ - /* a = -(B.y - A.y) / (B.x - A.x); */ \ - /* b = 1; */ \ - /* c = -(A.y + a * A.x); */ \ - /* but we multiply by B.x - A.x to avoid division. */ \ - \ - element_sub(b, Px, Zx); \ - element_sub(a, Zy, Py); \ - element_mul(t0, b, Zy); \ - element_mul(c, a, Zx); \ - element_add(c, c, t0); \ - element_neg(c, c); \ - \ - d_miller_evalfn(e0, a, b, c, Qx, Qy); \ - element_mul(v, v, e0); \ - } - - element_init(a, Px->field); - element_init(b, a->field); - element_init(c, a->field); - element_init(t0, a->field); - element_init(e0, res->field); - - element_init(v, res->field); - element_init(Z, P->field); - - element_set(Z, P); - Zx = curve_x_coord(Z); - Zy = curve_y_coord(Z); - - element_set1(v); - m = mpz_sizeinbase(q, 2) - 2; - - for(;;) { - do_tangent(); - - if (!m) break; - - element_double(Z, Z); - if (mpz_tstbit(q, m)) { - do_line(); - element_add(Z, Z, P); - } - m--; - element_square(v, v); - } - - element_set(res, v); - - element_clear(v); - element_clear(Z); - element_clear(a); - element_clear(b); - element_clear(c); - element_clear(t0); - element_clear(e0); - #undef do_tangent - #undef do_line -} - -static void (*cc_miller_no_denom_fn)(element_t res, mpz_t q, element_t P, - element_ptr Qx, element_ptr Qy); - -static void d_pairing_option_set(pairing_t pairing, char *key, char *value) { - UNUSED_VAR(pairing); - if (!strcmp(key, "method")) { - if (!strcmp(value, "miller")) { - cc_miller_no_denom_fn = cc_miller_no_denom_proj; - } else if (!strcmp(value, "miller-affine")) { - cc_miller_no_denom_fn = cc_miller_no_denom_affine; - } - } -} - -// Requires cofactor is even. TODO: This seems to contradict a comment below. -// Requires in != out. -// Mangles in. -static void lucas_even(element_ptr out, element_ptr in, mpz_t cofactor) { - if (element_is1(in)) { - element_set(out, in); - return; - } - element_t temp; - element_init_same_as(temp, out); - element_ptr in0 = element_x(in); - element_ptr in1 = element_y(in); - element_ptr v0 = element_x(out); - element_ptr v1 = element_y(out); - element_ptr t0 = element_x(temp); - element_ptr t1 = element_y(temp); - int j; - - element_set_si(t0, 2); - element_double(t1, in0); - - element_set(v0, t0); - element_set(v1, t1); - - j = mpz_sizeinbase(cofactor, 2) - 1; - for (;;) { - if (!j) { - element_mul(v1, v0, v1); - element_sub(v1, v1, t1); - element_square(v0, v0); - element_sub(v0, v0, t0); - break; - } - if (mpz_tstbit(cofactor, j)) { - element_mul(v0, v0, v1); - element_sub(v0, v0, t1); - element_square(v1, v1); - element_sub(v1, v1, t0); - } else { - element_mul(v1, v0, v1); - element_sub(v1, v1, t1); - element_square(v0, v0); - element_sub(v0, v0, t0); - } - j--; - } - - // Assume cofactor = (q^2 - q + 1) / r is odd - // thus v1 = V_k, v0 = V_{k-1} - // U = (P v1 - 2 v0) / (P^2 - 4) - - element_double(v0, v0); - element_mul(in0, t1, v1); - element_sub(in0, in0, v0); - - element_square(t1, t1); - element_sub(t1, t1, t0); - element_sub(t1, t1, t0); - - element_halve(v0, v1); - element_div(v1, in0, t1); - element_mul(v1, v1, in1); - - element_clear(temp); -} - -// The final powering, where we standardize the coset representative. -static void cc_tatepower(element_ptr out, element_ptr in, pairing_t pairing) { - pptr p = pairing->data; - #define qpower(sign) { \ - polymod_const_mul(e2, inre[1], p->xpowq); \ - element_set(e0re, e2); \ - polymod_const_mul(e2, inre[2], p->xpowq2); \ - element_add(e0re, e0re, e2); \ - element_add(e0re0, e0re0, inre[0]); \ - \ - if (sign > 0) { \ - polymod_const_mul(e2, inim[1], p->xpowq); \ - element_set(e0im, e2); \ - polymod_const_mul(e2, inim[2], p->xpowq2); \ - element_add(e0im, e0im, e2); \ - element_add(e0im0, e0im0, inim[0]); \ - } else { \ - polymod_const_mul(e2, inim[1], p->xpowq); \ - element_neg(e0im, e2); \ - polymod_const_mul(e2, inim[2], p->xpowq2); \ - element_sub(e0im, e0im, e2); \ - element_sub(e0im0, e0im0, inim[0]); \ - } \ - } - if (p->k == 6) { - // See thesis, section 6.9, "The Final Powering", which gives a formula - // for the first step of the final powering when Fq6 has been implemented - // as a quadratic extension on top of a cubic extension. - element_t e0, e2, e3; - element_init(e0, p->Fqk); - element_init(e2, p->Fqd); - element_init(e3, p->Fqk); - element_ptr e0re = element_x(e0); - element_ptr e0im = element_y(e0); - element_ptr e0re0 = ((element_t *) e0re->data)[0]; - element_ptr e0im0 = ((element_t *) e0im->data)[0]; - element_t *inre = element_x(in)->data; - element_t *inim = element_y(in)->data; - // Expressions in the formula are similar, hence the following function. - qpower(1); - element_set(e3, e0); - element_set(e0re, element_x(in)); - element_neg(e0im, element_y(in)); - element_mul(e3, e3, e0); - qpower(-1); - element_mul(e0, e0, in); - element_invert(e0, e0); - element_mul(in, e3, e0); - - element_set(e0, in); - // We use Lucas sequences to complete the final powering. - lucas_even(out, e0, pairing->phikonr); - - element_clear(e0); - element_clear(e2); - element_clear(e3); - } else { - element_pow_mpz(out, in, p->tateexp); - } - #undef qpower -} - -static void cc_finalpow(element_t e) { - cc_tatepower(e->data, e->data, e->field->pairing); -} - -static void cc_pairing(element_ptr out, element_ptr in1, element_ptr in2, - pairing_t pairing) { - element_ptr Qbase = in2; - element_t Qx, Qy; - pptr p = pairing->data; - - element_init(Qx, p->Fqd); - element_init(Qy, p->Fqd); - // Twist: (x, y) --> (v^-1 x, v^-(3/2) y) - // where v is the quadratic nonresidue used to construct the twist. - element_mul(Qx, curve_x_coord(Qbase), p->nqrinv); - // v^-3/2 = v^-2 * v^1/2 - element_mul(Qy, curve_y_coord(Qbase), p->nqrinv2); - cc_miller_no_denom_fn(out, pairing->r, in1, Qx, Qy); - cc_tatepower(out, out, pairing); - element_clear(Qx); - element_clear(Qy); -} - - -//do many millers at one time with affine coordinates. -static void cc_millers_no_denom_affine(element_t res, mpz_t q, element_t P[], - element_t Qx[], element_t Qy[], int n_prod) { - int m, i; - element_t v; - element_t a, b, c; - element_t t0; - element_t e0; - const element_ptr cca = curve_a_coeff(P[0]); - element_ptr Px, Py; - element_t* Z = pbc_malloc(sizeof(element_t)*n_prod); - element_ptr Zx, Zy; - - /* TODO: when exactly is this not needed? - void do_vertical() { - mapbase(e0, Z->x); - element_sub(e0, Qx, e0); - element_mul(v, v, e0); - } - */ - - #define do_tangents() { \ - /* a = -(3 Zx^2 + cc->a) */ \ - /* b = 2 * Zy */ \ - /* c = -(2 Zy^2 + a Zx); */ \ - for(i=0; i<n_prod; i++){ \ - Px = curve_x_coord(P[i]); \ - Py = curve_y_coord(P[i]); \ - Zx = curve_x_coord(Z[i]); \ - Zy = curve_y_coord(Z[i]); \ - \ - element_square(a, Zx); \ - element_mul_si(a, a, 3); \ - element_add(a, a, cca); \ - element_neg(a, a); \ - \ - element_add(b, Zy, Zy); \ - \ - element_mul(t0, b, Zy); \ - element_mul(c, a, Zx); \ - element_add(c, c, t0); \ - element_neg(c, c); \ - \ - d_miller_evalfn(e0, a, b, c, Qx[i], Qy[i]); \ - element_mul(v, v, e0); \ - } \ - } - - #define do_lines() { \ - /* a = -(B.y - A.y) / (B.x - A.x); */ \ - /* b = 1; */ \ - /* c = -(A.y + a * A.x); */ \ - /* but we multiply by B.x - A.x to avoid division. */ \ - for(i=0; i<n_prod; i++){ \ - Px = curve_x_coord(P[i]); \ - Py = curve_y_coord(P[i]); \ - Zx = curve_x_coord(Z[i]); \ - Zy = curve_y_coord(Z[i]); \ - \ - element_sub(b, Px, Zx); \ - element_sub(a, Zy, Py); \ - element_mul(t0, b, Zy); \ - element_mul(c, a, Zx); \ - element_add(c, c, t0); \ - element_neg(c, c); \ - \ - d_miller_evalfn(e0, a, b, c, Qx[i], Qy[i]); \ - element_mul(v, v, e0); \ - } \ - } - - Px= curve_x_coord(P[0]); //temporally used to initial a,b, c and etc. - element_init(a, Px->field); - element_init(b, a->field); - element_init(c, a->field); - element_init(t0, a->field); - element_init(e0, res->field); - - element_init(v, res->field); - for(i=0; i<n_prod; i++){ - element_init(Z[i], P[i]->field); - element_set(Z[i], P[i]); - } - - element_set1(v); - m = mpz_sizeinbase(q, 2) - 2; - - for(;;) { - do_tangents(); - - if (!m) break; - element_multi_double(Z, Z, n_prod); //Z_i=Z_i+Z_i for all i. - - if (mpz_tstbit(q, m)) { - do_lines(); - element_multi_add(Z, Z, P, n_prod); //Z_i=Z_i+P_i for all i. - } - m--; - element_square(v, v); - } - - element_set(res, v); - - element_clear(v); - for(i=0; i<n_prod; i++){ - element_clear(Z[i]); - } - pbc_free(Z); - element_clear(a); - element_clear(b); - element_clear(c); - element_clear(t0); - element_clear(e0); - #undef do_tangents - #undef do_lines -} - - -void cc_pairings_affine(element_ptr out, element_t in1[], element_t in2[], - int n_prod, pairing_t pairing) { - element_ptr Qbase; - element_t* Qx = pbc_malloc(sizeof(element_t)*n_prod); - element_t* Qy = pbc_malloc(sizeof(element_t)*n_prod); - pptr p = pairing->data; - int i; - for(i=0; i<n_prod; i++){ - element_init(Qx[i], p->Fqd); - element_init(Qy[i], p->Fqd); - Qbase = in2[i]; - // Twist: (x, y) --> (v^-1 x, v^-(3/2) y) - // where v is the quadratic nonresidue used to construct the twist. - element_mul(Qx[i], curve_x_coord(Qbase), p->nqrinv); - // v^-3/2 = v^-2 * v^1/2 - element_mul(Qy[i], curve_y_coord(Qbase), p->nqrinv2); - } - cc_millers_no_denom_affine(out, pairing->r, in1, Qx, Qy, n_prod); - cc_tatepower(out, out, pairing); - - for(i=0; i<n_prod; i++){ - element_clear(Qx[i]); - element_clear(Qy[i]); - } - pbc_free(Qx); - pbc_free(Qy); -} - - -static int cc_is_almost_coddh(element_ptr a, element_ptr b, - element_ptr c, element_ptr d, - pairing_t pairing) { - int res = 0; - element_t t0, t1, t2; - element_t cx, cy; - element_t dx, dy; - pptr p = pairing->data; - - element_init(cx, p->Fqd); - element_init(cy, p->Fqd); - element_init(dx, p->Fqd); - element_init(dy, p->Fqd); - - element_init(t0, p->Fqk); - element_init(t1, p->Fqk); - element_init(t2, p->Fqk); - // Twist: (x, y) --> (v^-1 x, v^-(3/2) y) - // where v is the quadratic nonresidue used to construct the twist. - element_mul(cx, curve_x_coord(c), p->nqrinv); - element_mul(dx, curve_x_coord(d), p->nqrinv); - // v^-3/2 = v^-2 * v^1/2 - element_mul(cy, curve_y_coord(c), p->nqrinv2); - element_mul(dy, curve_y_coord(d), p->nqrinv2); - - cc_miller_no_denom_fn(t0, pairing->r, a, dx, dy); - cc_miller_no_denom_fn(t1, pairing->r, b, cx, cy); - cc_tatepower(t0, t0, pairing); - cc_tatepower(t1, t1, pairing); - element_mul(t2, t0, t1); - if (element_is1(t2)) res = 1; // We were given g, g^x, h, h^-x. - else { - // Cheaply check the other case. - element_invert(t1, t1); - element_mul(t2, t0, t1); - if (element_is1(t2)) res = 1; // We were given g, g^x, h, h^x. - } - element_clear(cx); - element_clear(cy); - element_clear(dx); - element_clear(dy); - element_clear(t0); - element_clear(t1); - element_clear(t2); - return res; -} - -struct pp_coeff_s { - element_t a; - element_t b; - element_t c; -}; -typedef struct pp_coeff_s pp_coeff_t[1]; -typedef struct pp_coeff_s *pp_coeff_ptr; - -static void d_pairing_pp_init(pairing_pp_t p, element_ptr in1, pairing_t pairing) { - element_ptr P = in1; - const element_ptr Px = curve_x_coord(P); - const element_ptr Py = curve_y_coord(P); - element_t Z; - int m; - pptr info = pairing->data; - element_t t0; - element_t a, b, c; - field_ptr Fq = info->Fq; - pp_coeff_t *coeff; - mpz_ptr q = pairing->r; - pp_coeff_ptr pp; - const element_ptr cca = curve_a_coeff(P); - element_ptr Zx; - element_ptr Zy; - - #define store_abc() { \ - element_init(pp->a, Fq); \ - element_init(pp->b, Fq); \ - element_init(pp->c, Fq); \ - element_set(pp->a, a); \ - element_set(pp->b, b); \ - element_set(pp->c, c); \ - pp++; \ - } - - #define do_tangent() { \ - /* a = -slope_tangent(Z.x, Z.y); */ \ - /* b = 1; */ \ - /* c = -(Z.y + a * Z.x); */ \ - /* but we multiply by 2*Z.y to avoid division. */ \ - \ - /* a = -Zx * (3 Zx + twicea_2) - a_4; */ \ - /* Common curves: a2 = 0 (and cc->a is a_4), so */ \ - /* a = -(3 Zx^2 + cc->a) */ \ - /* b = 2 * Zy */ \ - /* c = -(2 Zy^2 + a Zx); */ \ - \ - element_square(a, Zx); \ - element_double(t0, a); \ - element_add(a, a, t0); \ - element_add(a, a, cca); \ - element_neg(a, a); \ - \ - element_add(b, Zy, Zy); \ - \ - element_mul(t0, b, Zy); \ - element_mul(c, a, Zx); \ - element_add(c, c, t0); \ - element_neg(c, c); \ - \ - store_abc(); \ - } - - #define do_line() { \ - /* a = -(B.y - A.y) / (B.x - A.x); */ \ - /* b = 1; */ \ - /* c = -(A.y + a * A.x); */ \ - /* but we'll multiply by B.x - A.x to avoid division */ \ - \ - element_sub(b, Px, Zx); \ - element_sub(a, Zy, Py); \ - element_mul(t0, b, Zy); \ - element_mul(c, a, Zx); \ - element_add(c, c, t0); \ - element_neg(c, c); \ - \ - store_abc(); \ - } - - element_init(Z, P->field); - element_set(Z, P); - Zx = curve_x_coord(Z); - Zy = curve_y_coord(Z); - - element_init(t0, Fq); - element_init(a, Fq); - element_init(b, Fq); - element_init(c, Fq); - - m = mpz_sizeinbase(q, 2) - 2; - p->data = pbc_malloc(sizeof(pp_coeff_t) * 2 * m); - coeff = (pp_coeff_t *) p->data; - pp = coeff[0]; - - for(;;) { - do_tangent(); - - if (!m) break; - - element_double(Z, Z); - if (mpz_tstbit(q, m)) { - do_line(); - element_add(Z, Z, P); - } - m--; - } - - element_clear(t0); - element_clear(a); - element_clear(b); - element_clear(c); - element_clear(Z); - #undef store_abc - #undef do_tangent - #undef do_line -} - -static void d_pairing_pp_clear(pairing_pp_t p) { - // TODO: Better to store a sentinel value in p->data? - mpz_ptr q = p->pairing->r; - int m = mpz_sizeinbase(q, 2) + mpz_popcount(q) - 3; - int i; - pp_coeff_t *coeff = (pp_coeff_t *) p->data; - pp_coeff_ptr pp; - for (i=0; i<m; i++) { - pp = coeff[i]; - element_clear(pp->a); - element_clear(pp->b); - element_clear(pp->c); - } - pbc_free(p->data); -} - -static void d_pairing_pp_apply(element_ptr out, element_ptr in2, - pairing_pp_t p) { - mpz_ptr q = p->pairing->r; - pptr info = p->pairing->data; - int m = mpz_sizeinbase(q, 2) - 2; - pp_coeff_t *coeff = (pp_coeff_t *) p->data; - pp_coeff_ptr pp = coeff[0]; - element_ptr Qbase = in2; - element_t e0; - element_t Qx, Qy; - element_t v; - element_init_same_as(e0, out); - element_init_same_as(v, out); - element_init(Qx, info->Fqd); - element_init(Qy, info->Fqd); - - // Twist: (x, y) --> (v^-1 x, v^-(3/2) y) - // where v is the quadratic nonresidue used to construct the twist - element_mul(Qx, curve_x_coord(Qbase), info->nqrinv); - // v^-3/2 = v^-2 * v^1/2 - element_mul(Qy, curve_y_coord(Qbase), info->nqrinv2); - - element_set1(out); - for(;;) { - d_miller_evalfn(e0, pp->a, pp->b, pp->c, Qx, Qy); - element_mul(out, out, e0); - pp++; - - if (!m) break; - - if (mpz_tstbit(q, m)) { - d_miller_evalfn(e0, pp->a, pp->b, pp->c, Qx, Qy); - element_mul(out, out, e0); - pp++; - } - m--; - element_square(out, out); - } - cc_tatepower(out, out, p->pairing); - - element_clear(e0); - element_clear(Qx); - element_clear(Qy); - element_clear(v); -} - -static void d_pairing_clear(pairing_t pairing) { - field_clear(pairing->GT); - pptr p = pairing->data; - - if (p->k == 6) { - element_clear(p->xpowq); - element_clear(p->xpowq2); - mpz_clear(pairing->phikonr); - } else { - mpz_clear(p->tateexp); - } - - field_clear(p->Etwist); - field_clear(p->Eq); - element_clear(p->nqrinv); - element_clear(p->nqrinv2); - field_clear(p->Fqk); - field_clear(p->Fqd); - field_clear(p->Fqx); - field_clear(p->Fq); - field_clear(pairing->Zr); - mpz_clear(pairing->r); - pbc_free(p); -} - -static void d_init_pairing(pairing_ptr pairing, void *data) { - d_param_ptr param = data; - pptr p; - element_t a, b; - element_t irred; - int d = param->k / 2; - int i; - - if (param->k % 2) pbc_die("k must be even"); - - mpz_init(pairing->r); - mpz_set(pairing->r, param->r); - field_init_fp(pairing->Zr, pairing->r); - pairing->map = cc_pairing; - pairing->prod_pairings = cc_pairings_affine; - pairing->is_almost_coddh = cc_is_almost_coddh; - - p = pairing->data = pbc_malloc(sizeof(*p)); - field_init_fp(p->Fq, param->q); - element_init(a, p->Fq); - element_init(b, p->Fq); - element_set_mpz(a, param->a); - element_set_mpz(b, param->b); - field_init_curve_ab(p->Eq, a, b, pairing->r, param->h); - - field_init_poly(p->Fqx, p->Fq); - element_init(irred, p->Fqx); - poly_set_coeff1(irred, d); - for (i = 0; i < d; i++) { - element_set_mpz(element_item(irred, i), param->coeff[i]); - } - - field_init_polymod(p->Fqd, irred); - element_clear(irred); - - p->Fqd->nqr = pbc_malloc(sizeof(element_t)); - element_init(p->Fqd->nqr, p->Fqd); - element_set_mpz(((element_t *) p->Fqd->nqr->data)[0], param->nqr); - - field_init_quadratic(p->Fqk, p->Fqd); - - // Compute constants involved in the final powering. - if (param->k == 6) { - mpz_ptr q = param->q; - mpz_ptr z = pairing->phikonr; - mpz_init(z); - mpz_mul(z, q, q); - mpz_sub(z, z, q); - mpz_add_ui(z, z, 1); - mpz_divexact(z, z, pairing->r); - - element_ptr e = p->xpowq; - element_init(e, p->Fqd); - element_set1(((element_t *) e->data)[1]); - element_pow_mpz(e, e, q); - - element_init(p->xpowq2, p->Fqd); - element_square(p->xpowq2, e); - } else { - mpz_init(p->tateexp); - mpz_sub_ui(p->tateexp, p->Fqk->order, 1); - mpz_divexact(p->tateexp, p->tateexp, pairing->r); - } - - field_init_curve_ab_map(p->Etwist, p->Eq, element_field_to_polymod, p->Fqd, pairing->r, NULL); - field_reinit_curve_twist(p->Etwist); - - mpz_t ndonr; - mpz_init(ndonr); - // ndonr temporarily holds the trace. - mpz_sub(ndonr, param->q, param->n); - mpz_add_ui(ndonr, ndonr, 1); - // Negate it because we want the trace of the twist. - mpz_neg(ndonr, ndonr); - pbc_mpz_curve_order_extn(ndonr, param->q, ndonr, d); - mpz_divexact(ndonr, ndonr, param->r); - field_curve_set_quotient_cmp(p->Etwist, ndonr); - mpz_clear(ndonr); - - element_init(p->nqrinv, p->Fqd); - element_invert(p->nqrinv, field_get_nqr(p->Fqd)); - element_init(p->nqrinv2, p->Fqd); - element_square(p->nqrinv2, p->nqrinv); - - pairing->G1 = p->Eq; - pairing->G2 = p->Etwist; - - p->k = param->k; - pairing_GT_init(pairing, p->Fqk); - pairing->finalpow = cc_finalpow; - - // By default use affine coordinates. - cc_miller_no_denom_fn = cc_miller_no_denom_affine; - pairing->option_set = d_pairing_option_set; - pairing->pp_init = d_pairing_pp_init; - pairing->pp_clear = d_pairing_pp_clear; - pairing->pp_apply = d_pairing_pp_apply; - - pairing->clear_func = d_pairing_clear; - - element_clear(a); - element_clear(b); -} - -// Computes a curve and sets fp to the field it is defined over using the -// complex multiplication method, where cm holds the appropriate information -// (e.g. discriminant, field order). -static void compute_cm_curve(d_param_ptr param, pbc_cm_ptr cm) { - element_t hp, root; - field_t fp, fpx; - field_t cc; - - field_init_fp(fp, cm->q); - field_init_poly(fpx, fp); - element_init(hp, fpx); - - mpz_t *coefflist; - int n = pbc_hilbert(&coefflist, cm->D); - - // Temporarily set the coefficient of x^{n-1} to 1 so hp has degree n - 1, - // allowing us to use poly_coeff(). - poly_set_coeff1(hp, n - 1); - int i; - for (i = 0; i < n; i++) { - element_set_mpz(element_item(hp, i), coefflist[i]); - } - pbc_hilbert_free(coefflist, n); - - // TODO: Remove x = 0, 1728 roots. - // TODO: What if there are no roots? - //printf("hp "); - //element_out_str(stdout, 0, hp); - //printf("\n"); - - element_init(root, fp); - poly_findroot(root, hp); - //printf("root = "); - //element_out_str(stdout, 0, root); - //printf("\n"); - element_clear(hp); - field_clear(fpx); - - // The root is the j-invariant of the desired curve. - field_init_curve_j(cc, root, cm->n, NULL); - element_clear(root); - - // We may need to twist it. - { - // Pick a random point P and twist the curve if it has the wrong order. - element_t P; - element_init(P, cc); - element_random(P); - element_mul_mpz(P, P, cm->n); - if (!element_is0(P)) field_reinit_curve_twist(cc); - element_clear(P); - } - - mpz_set(param->q, cm->q); - mpz_set(param->n, cm->n); - mpz_set(param->h, cm->h); - mpz_set(param->r, cm->r); - element_to_mpz(param->a, curve_field_a_coeff(cc)); - element_to_mpz(param->b, curve_field_b_coeff(cc)); - param->k = cm->k; - { - mpz_t z; - mpz_init(z); - // Compute order of curve in F_q^k. - // n = q - t + 1 hence t = q - n + 1 - mpz_sub(z, param->q, param->n); - mpz_add_ui(z, z, 1); - pbc_mpz_trace_n(z, param->q, z, param->k); - mpz_pow_ui(param->nk, param->q, param->k); - mpz_sub_ui(z, z, 1); - mpz_sub(param->nk, param->nk, z); - mpz_mul(z, param->r, param->r); - mpz_divexact(param->hk, param->nk, z); - mpz_clear(z); - } - field_clear(cc); - field_clear(fp); -} - -static void d_param_init(pbc_param_ptr p) { - static pbc_param_interface_t interface = {{ - d_clear, - d_init_pairing, - d_out_str, - }}; - p->api = interface; - d_param_ptr param = p->data = pbc_malloc(sizeof(*param)); - mpz_init(param->q); - mpz_init(param->n); - mpz_init(param->h); - mpz_init(param->r); - mpz_init(param->a); - mpz_init(param->b); - mpz_init(param->nk); - mpz_init(param->hk); - param->k = 0; - param->coeff = NULL; - mpz_init(param->nqr); -} - -// Public interface: - -int pbc_param_init_d(pbc_param_ptr par, struct symtab_s *tab) { - d_param_init(par); - d_param_ptr p = par->data; - char s[80]; - int i, d; - - int err = 0; - err += lookup_mpz(p->q, tab, "q"); - err += lookup_mpz(p->n, tab, "n"); - err += lookup_mpz(p->h, tab, "h"); - err += lookup_mpz(p->r, tab, "r"); - err += lookup_mpz(p->a, tab, "a"); - err += lookup_mpz(p->b, tab, "b"); - err += lookup_int(&p->k, tab, "k"); - err += lookup_mpz(p->nk, tab, "nk"); - err += lookup_mpz(p->hk, tab, "hk"); - err += lookup_mpz(p->nqr, tab, "nqr"); - - d = p->k / 2; - p->coeff = pbc_realloc(p->coeff, sizeof(mpz_t) * d); - for (i=0; i<d; i++) { - sprintf(s, "coeff%d", i); - mpz_init(p->coeff[i]); - err += lookup_mpz(p->coeff[i], tab, s); - } - return err; -} - -void pbc_param_init_d_gen(pbc_param_ptr p, pbc_cm_ptr cm) { - d_param_init(p); - d_param_ptr param = p->data; - field_t Fq, Fqx, Fqd; - element_t irred, nqr; - int d = cm->k / 2; - int i; - - compute_cm_curve(param, cm); - - field_init_fp(Fq, param->q); - field_init_poly(Fqx, Fq); - element_init(irred, Fqx); - do { - poly_random_monic(irred, d); - } while (!poly_is_irred(irred)); - field_init_polymod(Fqd, irred); - - // Find a quadratic nonresidue of Fqd lying in Fq. - element_init(nqr, Fqd); - do { - element_random(((element_t *) nqr->data)[0]); - } while (element_is_sqr(nqr)); - - param->coeff = pbc_realloc(param->coeff, sizeof(mpz_t) * d); - - for (i=0; i<d; i++) { - mpz_init(param->coeff[i]); - element_to_mpz(param->coeff[i], element_item(irred, i)); - } - element_to_mpz(param->nqr, ((element_t *) nqr->data)[0]); - - element_clear(nqr); - element_clear(irred); - - field_clear(Fqx); - field_clear(Fqd); - field_clear(Fq); -} |