a_param.c

这是一个C的源代码

    pairing->map = a_pairing_proj;

    field_init_fp(p->Fq, param->q);
    element_init(a, p->Fq);
    element_init(b, p->Fq);
    element_set1(a);
    element_set0(b);
    field_init_curve_ab(p->Eq, a, b, pairing->r, param->h);
    element_clear(a);
    element_clear(b);

    field_init_fi(p->Fq2, p->Fq);

    //k=2, hence phi_k(q) = q + 1, phikonr = (q+1)/r
    mpz_init(pairing->phikonr);
    mpz_set(pairing->phikonr, param->h);

    pairing->G1 = p->Eq;
    pairing->G2 = pairing->G1;
    pairing->phi = phi_identity;
    pairing->GT = p->Fq2;
    pairing->clear_func = a_pairing_clear;
    pairing->option_set = a_pairing_option_set;
    pairing->pp_init = a_pairing_pp_init;
    pairing->pp_clear = a_pairing_pp_clear;
    pairing->pp_apply = a_pairing_pp_apply;
}

struct a1_pairing_data_s {
    field_t Fp, Fp2, Ep;
};
typedef struct a1_pairing_data_s a1_pairing_data_t[1];
typedef struct a1_pairing_data_s *a1_pairing_data_ptr;

void a1_param_init(a1_param_t param)
{
    mpz_init(param->p);
    mpz_init(param->n);
}

void a1_param_clear(a1_param_t param)
{
    mpz_clear(param->p);
    mpz_clear(param->n);
}

void a1_param_out_str(FILE *stream, a1_param_ptr p)
{
    param_out_type(stream, "a1");
    param_out_mpz(stream, "p", p->p);
    param_out_mpz(stream, "n", p->n);
    param_out_int(stream, "l", p->l);
}

void a1_param_inp_generic (a1_param_ptr p, fetch_ops_t fops, void *ctx)
{
    assert (fops);
    assert (ctx);
    symtab_t tab;

    symtab_init(tab);
    param_read_generic (tab, fops, ctx);

    lookup_mpz(p->p, tab, "p");
    lookup_mpz(p->n, tab, "n");
    p->l = lookup_int(tab, "l");

    param_clear_tab(tab);
    symtab_clear(tab);
}

void a1_param_gen(a1_param_t param, mpz_t order)
{
    //if order is even, ideally check all even l, not just multiples of 4
    //but I don't see a good reason for having an even order
    unsigned int l = 4;
    mpz_t n;
    mpz_ptr p = param->p;
    mpz_init(n);
    mpz_mul_ui(n, order, 4);
    mpz_sub_ui(p, n, 1);
    for (;;) {
	if (mpz_probab_prime_p(p, 20)) {
	    break;
	}
	mpz_add(p, p, n);
	l += 4;
    }
    param->l = l;
    mpz_set(param->n, order);
    mpz_clear(n);
}

struct pp2_coeff_s {
    element_t cx2;
    element_t cy2;
    element_t cxy;
    element_t cx;
    element_t cy;
    element_t c;
};
typedef struct pp2_coeff_s pp2_coeff_t[1];
typedef struct pp2_coeff_s *pp2_coeff_ptr;

static void pp2_coeff_set(pp2_coeff_ptr p,
	element_t cx2, element_t cy2, element_t cxy,
	element_t cx, element_t cy, element_t c)
{
    element_init(p->cx2, cx2->field);
    element_init(p->cy2, cy2->field);
    element_init(p->cxy, cxy->field);
    element_init(p->cx, cx->field);
    element_init(p->cy, cy->field);
    element_init(p->c, c->field);
    element_set(p->cx2, cx2);
    element_set(p->cy2, cy2);
    element_set(p->cxy, cxy);
    element_set(p->cx, cx);
    element_set(p->cy, cy);
    element_set(p->c, c);
}

static void a1_pairing_pp_clear(pairing_pp_t p)
{
    void **pp = p->data;
    while (*pp) {
	pbc_free(*pp);
	pp++;
    }
    pbc_free(p->data);
}

static void a1_pairing_pp_init(pairing_pp_t p, element_ptr in1, pairing_t pairing)
{
    int m;
    element_ptr Px = curve_x_coord(in1);
    element_ptr Py = curve_y_coord(in1);
    a1_pairing_data_ptr a1info = pairing->data;
    p->data = pbc_malloc(sizeof(void *) * mpz_sizeinbase(pairing->r, 2));
    void **pp = p->data;
    element_t V;
    element_t a, b, c;
    element_t a2, b2, c2;
    element_t e0, e1, e2;
    element_ptr Vx, Vy;

    void do_tangent(void) {
	compute_abc_tangent(a, b, c, Vx, Vy, e0);
    }

    void do_line(void) {
	compute_abc_line(a2, b2, c2, Vx, Vy, Px, Py, e0);
    }

    element_init(V, a1info->Ep);
    element_set(V, in1);
    Vx = curve_x_coord(V);
    Vy = curve_y_coord(V);

    element_init(a, a1info->Fp);
    element_init(b, a1info->Fp);
    element_init(c, a1info->Fp);
    element_init(e0, a1info->Fp);
    element_init(e1, a1info->Fp);
    element_init(e2, a1info->Fp);
    element_init(a2, a1info->Fp);
    element_init(b2, a1info->Fp);
    element_init(c2, a1info->Fp);

    m = mpz_sizeinbase(pairing->r, 2) - 2;

    for(;;) {
	do_tangent();
	if (!m) break;
	element_double(V, V);

	if (mpz_tstbit(pairing->r, m)) {
	    do_line();
	    element_add(V, V, in1);
	    //preprocess two at once
	    //e0 = coeff of x
	    element_mul(e0, a, c2);
	    element_mul(e1, a2, c);
	    element_add(e0, e0, e1);

	    //e1 = coeff of y
	    element_mul(e1, b2, c);
	    element_mul(e2, b, c2);
	    element_add(e1, e1, e2);

	    //c = constant term
	    element_mul(c, c, c2);

	    //c2 = coeff of xy
	    element_mul(c2, a, b2);
	    element_mul(e2, a2, b);
	    element_add(c2, c2, e2);

	    //a = coeff of x^2
	    element_mul(a, a, a2);

	    //b = coeff of y^2
	    element_mul(b, b, b2);

	    *pp = pbc_malloc(sizeof(pp2_coeff_t));
	    pp2_coeff_set(*pp, a, b, c2, e0, e1, c);
	} else {
	    *pp = pbc_malloc(sizeof(pp_coeff_t));
	    pp_coeff_set(*pp, a, b, c);
	}
	pp++;
	m--;
    }
    *pp = pbc_malloc(sizeof(pp_coeff_t));
    pp_coeff_set(*pp, a, b, c);
    pp++;
    *pp = NULL;

    element_clear(a2);
    element_clear(b2);
    element_clear(c2);
    element_clear(e2);
    element_clear(e1);
    element_clear(e0);
    element_clear(a);
    element_clear(b);
    element_clear(c);
    element_clear(V);
}

static void a1_pairing_pp_apply(element_ptr out, element_ptr in2, pairing_pp_t p)
{
    void **pp = p->data;
    a1_pairing_data_ptr a1info = p->pairing->data;
    element_t f, f0;
    element_t e0, e1;
    int m;
    element_ptr Qx = curve_x_coord(in2);
    element_ptr Qy = curve_y_coord(in2);
    element_t Qx2, Qy2, Qxy;

    void do_tangent(void) {
	pp_coeff_ptr ppp = *pp;
	a_miller_evalfn(f0, ppp->a, ppp->b, ppp->c, Qx, Qy);
    }

    void do_line(void) {
	pp2_coeff_ptr ppp = *pp;
	//we'll map Q via (x,y) --> (-x, iy)
	//hence  Qx^2 = x^2, Qy^2 = -y^2, Qx Qy = -ixy
	//where x = Q'x, y = Q'y

	// Re = cx2 x^2 - cy2 y^2 - cx x + c
	// Im = -cxy xy + cy y
	element_mul(e0, ppp->cx2, Qx2);
	element_mul(e1, ppp->cy2, Qy2);
	element_sub(e0, e0, e1);
	element_mul(e1, ppp->cx, Qx);
	element_sub(e0, e0, e1);
	element_add(fi_re(f0), e0, ppp->c);

	element_mul(e0, ppp->cy, Qy);
	element_mul(e1, ppp->cxy, Qxy);
	element_sub(fi_im(f0), e0, e1);
    }
    element_init(f, out->field);
    element_init(f0, out->field);

    element_set1(f);

    element_init(e0, a1info->Fp);
    element_init(e1, a1info->Fp);
    element_init(Qx2, a1info->Fp);
    element_init(Qy2, a1info->Fp);
    element_init(Qxy, a1info->Fp);

    element_square(Qx2, Qx);
    element_square(Qy2, Qy);
    element_mul(Qxy, Qx, Qy);

    m = mpz_sizeinbase(p->pairing->r, 2) - 2;

    while (m > 0) {
	if (mpz_tstbit(p->pairing->r, m)) {
	    do_line();
	} else {
	    do_tangent();
	}
	element_mul(f, f, f0);
	pp++;
	m--;
	element_square(f, f);
    }
    do_tangent();
    element_mul(f, f, f0);

    //Tate exponentiation
    //simpler but slower:
    //element_pow_mpz(out, f, p->tateexp);
    //use this trick instead:
    element_invert(f0, f);
    element_neg(fi_im(f), fi_im(f));
    element_mul(f, f, f0);
    element_pow_mpz(out, f, p->pairing->phikonr);

    /* We could use this instead but p->h is small so this does not help much
    a_tateexp(out, f, f0, p->h);
    */

    element_clear(Qx2);
    element_clear(Qy2);
    element_clear(Qxy);
    element_clear(f);
    element_clear(f0);
    element_clear(e1);
    element_clear(e0);
}

static void a1_pairing(element_ptr out, element_ptr in1, element_ptr in2,
	pairing_t pairing)
//in1, in2 are from E(F_q), out from F_q^2
{
    a1_pairing_data_ptr p = pairing->data;
    element_t V;
    element_t f, f0;
    element_t a, b, c;
    element_t e0;
    int m;
    element_ptr Px = curve_x_coord(in1);
    element_ptr Py = curve_y_coord(in1);
    element_ptr Qx = curve_x_coord(in2);
    element_ptr Qy = curve_y_coord(in2);
    element_ptr Vx;
    element_ptr Vy;

    void do_tangent(void) {
	compute_abc_tangent(a, b, c, Vx, Vy, e0);
	a_miller_evalfn(f0, a, b, c, Qx, Qy);
	element_mul(f, f, f0);
    }

    void do_line(void) {
	compute_abc_line(a, b, c, Vx, Vy, Px, Py, e0);
	a_miller_evalfn(f0, a, b, c, Qx, Qy);
	element_mul(f, f, f0);
    }

    element_init(V, p->Ep);
    element_set(V, in1);
    Vx = curve_x_coord(V);
    Vy = curve_y_coord(V);

    element_init(f, p->Fp2);
    element_init(f0, p->Fp2);
    element_set1(f);
    element_init(a, p->Fp);
    element_init(b, p->Fp);
    element_init(c, p->Fp);
    element_init(e0, p->Fp);

    m = mpz_sizeinbase(pairing->r, 2) - 2;

    //TODO: sliding NAF
    for(;;) {
	do_tangent();
	if (!m) break;

	element_double(V, V);
	if (mpz_tstbit(pairing->r, m)) {
	    do_line();
	    element_add(V, V, in1);
	}

	m--;
	element_square(f, f);
    }

    //Tate exponentiation
    //simpler but slower:
    //element_pow_mpz(out, f, p->tateexp);
    //use this trick instead:
    element_invert(f0, f);
    element_neg(fi_im(f), fi_im(f));
    element_mul(f, f, f0);
    element_pow_mpz(out, f, pairing->phikonr);

    /* We could use this instead but p->h is small so this does not help much
    a_tateexp(out, f, f0, p->h);
    */

    element_clear(f);
    element_clear(f0);
    element_clear(V);
    element_clear(a);
    element_clear(b);
    element_clear(c);
    element_clear(e0);
}

void a1_pairing_clear(pairing_t pairing)
{
    a1_pairing_data_ptr p = pairing->data;
    field_clear(p->Ep);
    field_clear(p->Fp2);
    field_clear(p->Fp);
    pbc_free(p);

    mpz_clear(pairing->phikonr);
    mpz_clear(pairing->r);
    field_clear(pairing->Zr);
}

static void a1_pairing_option_set(pairing_t pairing, char *key, char *value)
{
    if (!strcmp(key, "method")) {
	if (!strcmp(value, "miller") || !strcmp(value, "miller-affine")) {
	    pairing->map = a1_pairing;
	    pairing->pp_init = a1_pairing_pp_init;
	    pairing->pp_clear = a1_pairing_pp_clear;
	    pairing->pp_apply = a1_pairing_pp_apply;
	} else if (!strcmp(value, "shipsey-stange")) {
	    pairing->map = a_pairing_ellnet;
	    pairing->pp_init = a_pairing_ellnet_pp_init;
	    pairing->pp_clear = a_pairing_ellnet_pp_clear;
	    pairing->pp_apply = a_pairing_ellnet_pp_apply;
	}
    }
}

void pairing_init_a1_param(pairing_t pairing, a1_param_t param)
{
    element_t a, b;
    mpz_init(pairing->r);
    mpz_set(pairing->r, param->n);
    field_init_fp(pairing->Zr, pairing->r);

    a1_pairing_data_ptr p;

    p =	pairing->data = pbc_malloc(sizeof(a1_pairing_data_t));

    //k=2, hence phi_k(q) = q + 1, phikonr = (q+1)/r
    mpz_init(pairing->phikonr);
    mpz_set_ui(pairing->phikonr, param->l);

    field_init_fp(p->Fp, param->p);
    element_init(a, p->Fp);
    element_init(b, p->Fp);
    element_set1(a);
    element_set0(b);
    field_init_curve_ab(p->Ep, a, b, pairing->r, pairing->phikonr);

    //turns out to be faster:
    field_curve_use_random_solvefory(p->Ep);

    element_clear(a);
    element_clear(b);
    field_init_fi(p->Fp2, p->Fp);

    pairing->G1 = pbc_malloc(sizeof(field_t));
    pairing->G2 = pairing->G1 = p->Ep;
    pairing->GT = p->Fp2;

    pairing->map = a1_pairing;
    pairing->phi = phi_identity;

    pairing->clear_func = a1_pairing_clear;

    pairing->pp_init = a1_pairing_pp_init;
    pairing->pp_clear = a1_pairing_pp_clear;
    pairing->pp_apply = a1_pairing_pp_apply;
    pairing->option_set = a1_pairing_option_set;
}