e_param.c

这是一个C的源代码

	element_sub(b, Bx, Ax);
	element_sub(a, Ay, By);
	element_mul(c, Ax, By);
	element_mul(e0, Ay, Bx);
	element_sub(c, c, e0);

	element_mul(e0, a, numx);
	element_mul(e1, b, numy);
	element_add(e0, e0, e1);
	element_add(e0, e0, c);
	element_mul(e, e, e0);

	element_mul(e0, a, denomx);
	element_mul(e1, b, denomy);
	element_add(e0, e0, e1);
	element_add(e0, e0, c);
	element_mul(edenom, edenom, e0);
    }

    element_init(a, res->field);
    element_init(b, res->field);
    element_init(c, res->field);
    element_init(e0, res->field);
    element_init(e1, res->field);

    element_init(v, res->field);
    element_init(vd, res->field);
    element_init(v1, res->field);
    element_init(vd1, res->field);
    element_init(Z, P->field);
    element_init(Z1, P->field);

    element_set(Z, P);
    Zx = curve_x_coord(Z);
    Zy = curve_y_coord(Z);

    element_set1(v);
    element_set1(vd);
    element_set1(v1);
    element_set1(vd1);

    n = p->exp1;
    for (i=0; i<n; i++) {
	element_square(v, v);
	element_square(vd, vd);
	do_tangent(v, vd);
	element_double(Z, Z);
	do_vertical(vd, v, Zx);
    }
    if (p->sign1 < 0) {
	element_set(v1, vd);
	element_set(vd1, v);
	do_vertical(vd1, v1, Zx);
	element_neg(Z1, Z);
    } else {
	element_set(v1, v);
	element_set(vd1, vd);
	element_set(Z1, Z);
    }
    n = p->exp2;
    for (; i<n; i++) {
	element_square(v, v);
	element_square(vd, vd);
	do_tangent(v, vd);
	element_double(Z, Z);
	do_vertical(vd, v, Zx);
    }
    element_mul(v, v, v1);
    element_mul(vd, vd, vd1);
    do_line(v, vd, Z, Z1);
    element_add(Z, Z, Z1);
    do_vertical(vd, v, Zx);

    if (p->sign0 > 0) {
	do_vertical(v, vd, Px);
    }

    element_invert(vd, vd);
    element_mul(res, v, vd);

    element_clear(v);
    element_clear(vd);
    element_clear(v1);
    element_clear(vd1);
    element_clear(Z);
    element_clear(Z1);
    element_clear(a);
    element_clear(b);
    element_clear(c);
    element_clear(e0);
    element_clear(e1);
}

static void (*e_miller_fn)(element_t res, element_t P,
	element_ptr QR, element_ptr R,
	e_pairing_data_ptr p);

static void e_pairing(element_ptr out, element_ptr in1, element_ptr in2,
	pairing_t pairing)
{
    e_pairing_data_ptr p = pairing->data;
    element_ptr Q = in2;
    element_t QR;
    element_init(QR, p->Eq);
    element_add(QR, Q, p->R);
    e_miller_fn(out, in1, QR, p->R, p);
    element_pow_mpz(out, out, pairing->phikonr);
    element_clear(QR);
}

static void e_pairing_ellnet(element_ptr out, element_ptr in1, element_ptr in2,
	pairing_t pairing)
//in1, in2 are from E(F_q), out from F_q^2
//uses elliptic nets (see Stange)
{
    const element_ptr a = curve_a_coeff(in1);
    const element_ptr b = curve_b_coeff(in1);

    element_ptr x = curve_x_coord(in1);
    element_ptr y = curve_y_coord(in1);

    element_ptr x2 = curve_x_coord(in2);
    element_ptr y2 = curve_y_coord(in2);

    //notation: cmi means c_{k-i}, ci means c_{k+i}
    element_t cm3, cm2, cm1, c0, c1, c2, c3, c4;
    element_t dm1, d0, d1;
    element_t A, B, C;

    element_init_same_as(cm3, x);
    element_init_same_as(cm2, x);
    element_init_same_as(cm1, x);
    element_init_same_as(c0, x);
    element_init_same_as(c1, x);
    element_init_same_as(c2, x);
    element_init_same_as(c3, x);
    element_init_same_as(c4, x);
    element_init_same_as(C, x);

    element_init_same_as(dm1, out);
    element_init_same_as(d0, out);
    element_init_same_as(d1, out);
    element_init_same_as(A, x);
    element_init_same_as(B, out);

    // c1 = 2y
    // cm3 = -2y
    element_double(c1, y);
    element_neg(cm3, c1);

    //use c0, cm1, cm2, C, c4 as temp variables for now
    //compute c3, c2
    element_square(cm2, x);
    element_square(C, cm2);
    element_mul(cm1, b, x);
    element_double(cm1, cm1);
    element_square(c4, a);

    element_mul(c2, cm1, cm2);
    element_double(c2, c2);
    element_mul(c0, a, C);
    element_add(c2, c2, c0);
    element_mul(c0, c4, cm2);
    element_sub(c2, c2, c0);
    element_double(c0, c2);
    element_double(c0, c0);
    element_add(c2, c2, c0);

    element_mul(c0, cm1, a);
    element_square(c3, b);
    element_double(c3, c3);
    element_double(c3, c3);
    element_add(c0, c0, c3);
    element_double(c0, c0);
    element_mul(c3, a, c4);
    element_add(c0, c0, c3);
    element_sub(c2, c2, c0);
    element_mul(c0, cm2, C);
    element_add(c3, c0, c2);
    element_mul(c3, c3, c1);
    element_double(c3, c3);

    element_mul(c0, a, cm2);
    element_add(c0, c0, cm1);
    element_double(c0, c0);
    element_add(c0, c0, C);
    element_double(c2, c0);
    element_add(c0, c0, c2);
    element_sub(c2, c0, c4);

    // c0 = 1
    // cm2 = -1
    element_set1(c0);
    element_neg(cm2, c0);

    // c4 = c_5 = c_2^3 c_4 - c_3^3 = c1^3 c3 - c2^3
    element_square(C, c1);
    element_mul(c4, C, c1);
    element_mul(c4, c4, c3);
    element_square(C, c2);
    element_mul(C, C, c2);
    element_sub(c4, c4, C);

    //compute A, B, d1 (which is d_2 since k = 1)
    element_sub(A, x, x2);
    element_double(C, x);
    element_add(C, C, x2);
    element_square(cm1, A);
    element_mul(cm1, C, cm1);
    element_add(d1, y, y2);
    element_square(d1, d1);
    element_sub(B, cm1, d1);
    element_invert(B, B);
    element_invert(A, A);

    element_sub(d1, y, y2);
    element_mul(d1, d1, A);
    element_square(d1, d1);
    element_sub(d1, C, d1);

    // cm1 = 0
    // C = (2y)^-1
    element_set0(cm1);
    element_invert(C, c1);

    element_set1(dm1);
    element_set1(d0);

    element_t sm2, sm1;
    element_t s0, s1, s2, s3;
    element_t tm2, tm1;
    element_t t0, t1, t2, t3;
    element_t e0, e1;
    element_t u, v;

    element_init_same_as(sm2, x);
    element_init_same_as(sm1, x);
    element_init_same_as(s0, x);
    element_init_same_as(s1, x);
    element_init_same_as(s2, x);
    element_init_same_as(s3, x);

    element_init_same_as(tm2, x);
    element_init_same_as(tm1, x);
    element_init_same_as(t0, x);
    element_init_same_as(t1, x);
    element_init_same_as(t2, x);
    element_init_same_as(t3, x);

    element_init_same_as(e0, x);
    element_init_same_as(e1, x);

    element_init_same_as(u, d0);
    element_init_same_as(v, d0);

    int m = mpz_sizeinbase(pairing->r, 2) - 2;
    for (;;) {
	element_square(sm2, cm2);
	element_square(sm1, cm1);
	element_square(s0, c0);
	element_square(s1, c1);
	element_square(s2, c2);
	element_square(s3, c3);

	element_mul(tm2, cm3, cm1);
	element_mul(tm1, cm2, c0);
	element_mul(t0, cm1, c1);
	element_mul(t1, c0, c2);
	element_mul(t2, c1, c3);
	element_mul(t3, c2, c4);

	element_square(u, d0);
	element_mul(v, dm1, d1);

	if (mpz_tstbit(pairing->r, m)) {
	    //double-and-add
	    element_mul(e0, t0, sm2);
	    element_mul(e1, tm2, s0);
	    element_sub(cm3, e0, e1);
	    element_mul(cm3, cm3, C);

	    element_mul(e0, t0, sm1);
	    element_mul(e1, tm1, s0);
	    element_sub(cm2, e0, e1);

	    element_mul(e0, t1, sm1);
	    element_mul(e1, tm1, s1);
	    element_sub(cm1, e0, e1);
	    element_mul(cm1, cm1, C);

	    element_mul(e0, t1, s0);
	    element_mul(e1, t0, s1);
	    element_sub(c0, e0, e1);

	    element_mul(e0, t2, s0);
	    element_mul(e1, t0, s2);
	    element_sub(c1, e0, e1);
	    element_mul(c1, c1, C);

	    element_mul(e0, t2, s1);
	    element_mul(e1, t1, s2);
	    element_sub(c2, e0, e1);

	    element_mul(e0, t3, s1);
	    element_mul(e1, t1, s3);
	    element_sub(c3, e0, e1);
	    element_mul(c3, c3, C);

	    element_mul(e0, t3, s2);
	    element_mul(e1, t2, s3);
	    element_sub(c4, e0, e1);

	    element_mul(out, u, t0);
	    element_mul(dm1, v, s0);
	    element_sub(dm1, dm1, out);

	    element_mul(out, u, t1);
	    element_mul(d0, v, s1);
	    element_sub(d0, d0, out);
	    element_mul(d0, d0, A);

	    element_mul(out, u, t2);
	    element_mul(d1, v, s2);
	    element_sub(d1, d1, out);
	    element_mul(d1, d1, B);
	} else {
	    //double
	    element_mul(e0, tm1, sm2);
	    element_mul(e1, tm2, sm1);
	    element_sub(cm3, e0, e1);

	    element_mul(e0, t0, sm2);
	    element_mul(e1, tm2, s0);
	    element_sub(cm2, e0, e1);
	    element_mul(cm2, cm2, C);

	    element_mul(e0, t0, sm1);
	    element_mul(e1, tm1, s0);
	    element_sub(cm1, e0, e1);

	    element_mul(e0, t1, sm1);
	    element_mul(e1, tm1, s1);
	    element_sub(c0, e0, e1);
	    element_mul(c0, c0, C);

	    element_mul(e0, t1, s0);
	    element_mul(e1, t0, s1);
	    element_sub(c1, e0, e1);

	    element_mul(e0, t2, s0);
	    element_mul(e1, t0, s2);
	    element_sub(c2, e0, e1);
	    element_mul(c2, c2, C);

	    element_mul(e0, t2, s1);
	    element_mul(e1, t1, s2);
	    element_sub(c3, e0, e1);

	    element_mul(e0, t3, s1);
	    element_mul(e1, t1, s3);
	    element_sub(c4, e0, e1);
	    element_mul(c4, c4, C);

	    element_mul(out, u, tm1);
	    element_mul(dm1, v, sm1);
	    element_sub(dm1, dm1, out);

	    element_mul(out, u, t0);
	    element_mul(d0, v, s0);
	    element_sub(d0, d0, out);

	    element_mul(out, u, t1);
	    element_mul(d1, v, s1);
	    element_sub(d1, d1, out);
	    element_mul(d1, d1, A);
	}
	if (!m) break;
	m--;
    }
    element_invert(c1, c1);
    element_mul(d1, d1, c1);

    element_pow_mpz(out, d1, pairing->phikonr);

    element_clear(dm1);
    element_clear(d0);
    element_clear(d1);

    element_clear(cm3);
    element_clear(cm2);
    element_clear(cm1);
    element_clear(c0);
    element_clear(c1);
    element_clear(c2);
    element_clear(c3);
    element_clear(c4);

    element_clear(sm2);
    element_clear(sm1);
    element_clear(s0);
    element_clear(s1);
    element_clear(s2);
    element_clear(s3);

    element_clear(tm2);
    element_clear(tm1);
    element_clear(t0);
    element_clear(t1);
    element_clear(t2);
    element_clear(t3);

    element_clear(e0);
    element_clear(e1);
    element_clear(A);
    element_clear(B);
    element_clear(C);
    element_clear(u);
    element_clear(v);
}

static void phi_identity(element_ptr out, element_ptr in, pairing_ptr pairing)
{
    (void) pairing;
    element_set(out, in);
}

static void e_pairing_option_set(pairing_t pairing, char *key, char *value)
{
    //TODO: this affects every type E pairing!
    UNUSED_VAR(pairing);
    if (!strcmp(key, "method")) {
	if (!strcmp(value, "miller")) {
	    pairing->map = e_pairing;
	    e_miller_fn = e_miller_proj;
	} else if (!strcmp(value, "miller-affine")) {
	    pairing->map = e_pairing;
	    e_miller_fn = e_miller_affine;
	} else if (!strcmp(value, "shipsey-stange")) {
	    pairing->map = e_pairing_ellnet;
	}
    }
}

void e_pairing_clear(pairing_t pairing)
{
    e_pairing_data_ptr p = pairing->data;
    field_clear(p->Fq);
    field_clear(p->Eq);
    element_clear(p->R);
    pbc_free(p);

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

void pairing_init_e_param(pairing_t pairing, e_param_t param)
{
    e_pairing_data_ptr p;
    element_t a, b;

    mpz_init(pairing->r);
    mpz_set(pairing->r, param->r);
    field_init_fp(pairing->Zr, pairing->r);
    pairing->map = e_pairing;
    e_miller_fn = e_miller_proj;

    p =	pairing->data = pbc_malloc(sizeof(e_pairing_data_t));
    p->exp2 = param->exp2;
    p->exp1 = param->exp1;
    p->sign1 = param->sign1;
    p->sign0 = param->sign0;
    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);

    //k=1, hence phikonr = (p-1)/r
    mpz_init(pairing->phikonr);
    mpz_sub_ui(pairing->phikonr, p->Fq->order, 1);
    mpz_divexact(pairing->phikonr, pairing->phikonr, pairing->r);

    pairing->G2 = pairing->G1 = p->Eq;

    pairing->GT = p->Fq;
    pairing->phi = phi_identity;
    pairing->option_set = e_pairing_option_set;
    pairing->clear_func = e_pairing_clear;

    element_init(p->R, p->Eq);
    curve_set_gen_no_cofac(p->R);

    element_clear(a);
    element_clear(b);
}