diff options
author | 2015-09-04 07:35:06 +0000 | |
---|---|---|
committer | 2015-09-04 07:35:06 +0000 | |
commit | ca6aa8198d2335f8c326c3dd4d26bf5899064214 (patch) | |
tree | 6274a2d971fc0cac0896efe8583927d0190e3d20 /moon-abe/pbc-0.5.14/ecc/f_param.c | |
parent | 92fd2dbfb672d7b2b1cdfd5dd5cf89f7716b3e12 (diff) | |
parent | 3baeb11a8fbcfcdbc31976d421f17b85503b3ecd (diff) |
Merge "init attribute-based encryption"
Diffstat (limited to 'moon-abe/pbc-0.5.14/ecc/f_param.c')
-rw-r--r-- | moon-abe/pbc-0.5.14/ecc/f_param.c | 599 |
1 files changed, 599 insertions, 0 deletions
diff --git a/moon-abe/pbc-0.5.14/ecc/f_param.c b/moon-abe/pbc-0.5.14/ecc/f_param.c new file mode 100644 index 00000000..2477ace1 --- /dev/null +++ b/moon-abe/pbc-0.5.14/ecc/f_param.c @@ -0,0 +1,599 @@ +#include <stdarg.h> +#include <stdio.h> +#include <stdint.h> // for intptr_t +#include <stdlib.h> +#include <gmp.h> +#include "pbc_utils.h" +#include "pbc_field.h" +#include "pbc_fp.h" +#include "pbc_fieldquadratic.h" +#include "pbc_param.h" +#include "pbc_pairing.h" +#include "pbc_poly.h" +#include "pbc_curve.h" +#include "pbc_memory.h" +#include "pbc_f_param.h" +#include "ecc/param.h" + +struct f_param_s { + mpz_t q; // Curve defined over F_q. + mpz_t r; // The order of the curve. + mpz_t b; // E: y^2 = x^3 + b + mpz_t beta; //beta is a quadratic nonresidue in Fq + //we use F_q^2 = F_q[sqrt(beta)] + mpz_t alpha0, alpha1; + //the polynomial x^6 + alpha0 + alpha1 sqrt(beta) + //is irreducible over F_q^2[x], so + //we can extend F_q^2 to F_q^12 using the + //sixth root of -(alpha0 + alpha1 sqrt(beta)) +}; +typedef struct f_param_s f_param_t[1]; +typedef struct f_param_s *f_param_ptr; + +// TODO: we never use phikonr so don't bother computing it, +// but one day other routines might need it +struct f_pairing_data_s { + field_t Fq, Fq2, Fq2x, Fq12; + field_t Eq, Etwist; + element_t negalpha; + element_t negalphainv; + mpz_t tateexp; + + //for tate exponentiation speedup: + //x^{q^k} for various k + element_t xpowq2, xpowq6, xpowq8; +}; +typedef struct f_pairing_data_s f_pairing_data_t[1]; +typedef struct f_pairing_data_s *f_pairing_data_ptr; + +static void f_clear(void *data) { + f_param_ptr fp = data; + mpz_clear(fp->q); + mpz_clear(fp->r); + mpz_clear(fp->b); + mpz_clear(fp->beta); + mpz_clear(fp->alpha0); + mpz_clear(fp->alpha1); + pbc_free(data); +} + +static void f_out_str(FILE *stream, void *data) { + f_param_ptr p = data; + param_out_type(stream, "f"); + param_out_mpz(stream, "q", p->q); + param_out_mpz(stream, "r", p->r); + param_out_mpz(stream, "b", p->b); + param_out_mpz(stream, "beta", p->beta); + param_out_mpz(stream, "alpha0", p->alpha0); + param_out_mpz(stream, "alpha1", p->alpha1); +} + +static void tryminusx(mpz_ptr q, mpz_ptr x) { + //36x4 - 36x3 + 24x2 - 6x + 1 + //= ((36(x - 1)x + 24)x - 6)x + 1 + mpz_sub_ui(q, x, 1); + mpz_mul(q, q, x); + mpz_mul_ui(q, q, 36); + mpz_add_ui(q, q, 24); + mpz_mul(q, q, x); + mpz_sub_ui(q, q, 6); + mpz_mul(q, q, x); + mpz_add_ui(q, q, 1); +} + +static void tryplusx(mpz_ptr q, mpz_ptr x) { + //36x4 + 36x3 + 24x2 + 6x + 1 + //= ((36(x + 1)x + 24)x + 6)x + 1 + mpz_add_ui(q, x, 1); + mpz_mul(q, q, x); + mpz_mul_ui(q, q, 36); + mpz_add_ui(q, q, 24); + mpz_mul(q, q, x); + mpz_add_ui(q, q, 6); + mpz_mul(q, q, x); + mpz_add_ui(q, q, 1); +} + +static void cc_miller_no_denom(element_t res, mpz_t q, element_t P, + element_ptr Qx, element_ptr Qy, element_t negalpha) { + int m; + element_t v; + element_t Z; + element_t a, b, c; + element_t t0; + element_t e0, e1; + element_ptr Zx, Zy; + const element_ptr Px = curve_x_coord(P); + const element_ptr Py = curve_y_coord(P); + + #define do_term(i, j, k, flag) { \ + element_ptr e2; \ + e2 = element_item(e0, i); \ + element_mul(e1, element_item(v, j), Qx); \ + if (flag == 1) element_mul(e1, e1, negalpha); \ + element_mul(element_x(e1), element_x(e1), a); \ + element_mul(element_y(e1), element_y(e1), a); \ + element_mul(e2, element_item(v, k), Qy); \ + element_mul(element_x(e2), element_x(e2), b); \ + element_mul(element_y(e2), element_y(e2), b); \ + element_add(e2, e2, e1); \ + if (flag == 2) element_mul(e2, e2, negalpha); \ + element_mul(element_x(e1), element_x(element_item(v, i)), c); \ + element_mul(element_y(e1), element_y(element_item(v, i)), c); \ + element_add(e2, e2, e1); \ + } + + // a, b, c lie in Fq + // Qx, Qy lie in Fq^2 + // Qx is coefficient of x^4 + // Qy is coefficient of x^3 + // + // computes v *= (a Qx x^4 + b Qy x^3 + c) + // + // recall x^6 = -alpha thus + // x^4 (u0 + u1 x^1 + ... + u5 x^5) = + // u0 x^4 + u1 x^5 + // - alpha u2 - alpha u3 x - alpha u4 x^2 - alpha u5 x^3 + // and + // x^4 (u0 + u1 x^1 + ... + u5 x^5) = + // u0 x^3 + u1 x^4 + u2 x^5 + // - alpha u3 - alpha u4 x - alpha u5 x^2 + #define f_miller_evalfn() { \ + do_term(0, 2, 3, 2); \ + do_term(1, 3, 4, 2); \ + do_term(2, 4, 5, 2); \ + do_term(3, 5, 0, 1); \ + do_term(4, 0, 1, 0); \ + do_term(5, 1, 2, 0); \ + element_set(v, e0); \ + } + /* + element_ptr e1; + + e1 = element_item(e0, 4); + + element_mul(element_x(e1), element_x(Qx), a); + element_mul(element_y(e1), element_y(Qx), a); + + e1 = element_item(e0, 3); + + element_mul(element_x(e1), element_x(Qy), b); + element_mul(element_y(e1), element_y(Qy), b); + + element_set(element_x(element_item(e0, 0)), c); + + element_mul(v, v, e0); + */ + + //a = -3 Zx^2 since cc->a is 0 for D = 3 + //b = 2 * Zy + //c = -(2 Zy^2 + a Zx); + #define do_tangent() { \ + element_square(a, Zx); \ + element_mul_si(a, a, 3); \ + 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); \ + \ + f_miller_evalfn(); \ + } + + //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 + #define do_line() { \ + 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); \ + \ + f_miller_evalfn(); \ + } + + 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(e1, Qx->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; + + //TODO: sliding NAF + 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); + element_clear(e1); + #undef do_term + #undef f_miller_evalfn + #undef do_tangent + #undef do_line +} + +static void f_tateexp(element_t out) { + element_t x, y, epow; + f_pairing_data_ptr p = out->field->pairing->data; + element_init(x, p->Fq12); + element_init(y, p->Fq12); + element_init(epow, p->Fq2); + + #define qpower(e1, e) { \ + element_set(element_item(e1, 0), element_item(out, 0)); \ + element_mul(element_item(e1, 1), element_item(out, 1), e); \ + element_square(epow, e); \ + element_mul(element_item(e1, 2), element_item(out, 2), epow); \ + element_mul(epow, epow, e); \ + element_mul(element_item(e1, 3), element_item(out, 3), epow); \ + element_mul(epow, epow, e); \ + element_mul(element_item(e1, 4), element_item(out, 4), epow); \ + element_mul(epow, epow, e); \ + element_mul(element_item(e1, 5), element_item(out, 5), epow); \ + } + + qpower(y, p->xpowq8); + qpower(x, p->xpowq6); + element_mul(y, y, x); + qpower(x, p->xpowq2); + element_mul(x, x, out); + element_invert(x, x); + element_mul(out, y, x); + + element_clear(epow); + element_clear(x); + element_clear(y); + element_pow_mpz(out, out, p->tateexp); + #undef qpower +} + +static void f_finalpow(element_t out) { + f_tateexp(out->data); +} + +static void f_pairing(element_ptr out, element_ptr in1, element_ptr in2, + pairing_t pairing) { + element_ptr Qbase = in2; + element_t x, y; + f_pairing_data_ptr p = pairing->data; + + element_init(x, p->Fq2); + element_init(y, p->Fq2); + //map from twist: (x, y) --> (v^-2 x, v^-3 y) + //where v is the sixth root used to construct the twist + //i.e. v^6 = -alpha + //thus v^-2 = -alpha^-1 v^4 + //and v^-3 = -alpha^-1 v^3 + element_mul(x, curve_x_coord(Qbase), p->negalphainv); + element_mul(y, curve_y_coord(Qbase), p->negalphainv); + + cc_miller_no_denom(out, pairing->r, in1, x, y, p->negalpha); + + element_clear(x); + element_clear(y); + + f_tateexp(out); +} + +static void f_pairing_clear(pairing_t pairing) { + field_clear(pairing->GT); + f_pairing_data_ptr p = pairing->data; + element_clear(p->negalpha); + element_clear(p->negalphainv); + mpz_clear(p->tateexp); + element_clear(p->xpowq2); + element_clear(p->xpowq6); + element_clear(p->xpowq8); + field_clear(p->Etwist); + field_clear(p->Eq); + + field_clear(p->Fq12); + field_clear(p->Fq2x); + field_clear(p->Fq2); + field_clear(p->Fq); + pbc_free(p); + + mpz_clear(pairing->r); + field_clear(pairing->Zr); +} + +static void f_init_pairing(pairing_t pairing, void *data) { + f_param_ptr param = data; + f_pairing_data_ptr p; + element_t irred; + element_t e0, e1, e2; + p = pairing->data = pbc_malloc(sizeof(f_pairing_data_t)); + mpz_init(pairing->r); + mpz_set(pairing->r, param->r); + field_init_fp(pairing->Zr, pairing->r); + field_init_fp(p->Fq, param->q); + p->Fq->nqr = pbc_malloc(sizeof(element_t)); + element_init(p->Fq->nqr, p->Fq); + element_set_mpz(p->Fq->nqr, param->beta); + field_init_quadratic(p->Fq2, p->Fq); + field_init_poly(p->Fq2x, p->Fq2); + element_init(irred, p->Fq2x); + // Call poly_set_coeff1() first so we can use element_item() for the other + // coefficients. + poly_set_coeff1(irred, 6); + + element_init(p->negalpha, p->Fq2); + element_init(p->negalphainv, p->Fq2); + element_set_mpz(element_x(p->negalpha), param->alpha0); + element_set_mpz(element_y(p->negalpha), param->alpha1); + + element_set(element_item(irred, 0), p->negalpha); + field_init_polymod(p->Fq12, irred); + element_neg(p->negalpha, p->negalpha); + element_invert(p->negalphainv, p->negalpha); + element_clear(irred); + + element_init(e0, p->Fq); + element_init(e1, p->Fq); + element_init(e2, p->Fq2); + + // Initialize the curve Y^2 = X^3 + b. + element_set_mpz(e1, param->b); + field_init_curve_ab(p->Eq, e0, e1, pairing->r, NULL); + + // Initialize the curve Y^2 = X^3 - alpha0 b - alpha1 sqrt(beta) b. + element_set_mpz(e0, param->alpha0); + element_neg(e0, e0); + element_mul(element_x(e2), e0, e1); + element_set_mpz(e0, param->alpha1); + element_neg(e0, e0); + element_mul(element_y(e2), e0, e1); + element_clear(e0); + element_init(e0, p->Fq2); + field_init_curve_ab(p->Etwist, e0, e2, pairing->r, NULL); + element_clear(e0); + element_clear(e1); + element_clear(e2); + + mpz_t ndonr; + mpz_init(ndonr); + // ndonr temporarily holds the trace. + mpz_sub(ndonr, param->q, param->r); + mpz_add_ui(ndonr, ndonr, 1); + // TODO: We can use a smaller quotient_cmp, but I have to figure out + // BN curves again. + pbc_mpz_curve_order_extn(ndonr, param->q, ndonr, 12); + mpz_divexact(ndonr, ndonr, param->r); + mpz_divexact(ndonr, ndonr, param->r); + field_curve_set_quotient_cmp(p->Etwist, ndonr); + mpz_clear(ndonr); + + pairing->G1 = p->Eq; + pairing->G2 = p->Etwist; + pairing_GT_init(pairing, p->Fq12); + pairing->finalpow = f_finalpow; + pairing->map = f_pairing; + pairing->clear_func = f_pairing_clear; + + mpz_init(p->tateexp); + /* unoptimized tate exponent + mpz_pow_ui(p->tateexp, param->q, 12); + mpz_sub_ui(p->tateexp, p->tateexp, 1); + mpz_divexact(p->tateexp, p->tateexp, param->r); + */ + mpz_ptr z = p->tateexp; + mpz_mul(z, param->q, param->q); + mpz_sub_ui(z, z, 1); + mpz_mul(z, z, param->q); + mpz_mul(z, z, param->q); + mpz_add_ui(z, z, 1); + mpz_divexact(z, z, param->r); + + element_init(p->xpowq2, p->Fq2); + element_init(p->xpowq6, p->Fq2); + element_init(p->xpowq8, p->Fq2); + element_t xpowq; + element_init(xpowq, p->Fq12); + + //there are smarter ways since we know q = 1 mod 6 + //and that x^6 = -alpha + //but this is fast enough + element_set1(element_item(xpowq, 1)); + element_pow_mpz(xpowq, xpowq, param->q); + element_pow_mpz(xpowq, xpowq, param->q); + element_set(p->xpowq2, element_item(xpowq, 1)); + + element_pow_mpz(xpowq, xpowq, param->q); + element_pow_mpz(xpowq, xpowq, param->q); + element_pow_mpz(xpowq, xpowq, param->q); + element_pow_mpz(xpowq, xpowq, param->q); + element_set(p->xpowq6, element_item(xpowq, 1)); + + element_pow_mpz(xpowq, xpowq, param->q); + element_pow_mpz(xpowq, xpowq, param->q); + element_set(p->xpowq8, element_item(xpowq, 1)); + + element_clear(xpowq); +} + +static void f_init(pbc_param_ptr p) { + static pbc_param_interface_t interface = {{ + f_clear, + f_init_pairing, + f_out_str, + }}; + p->api = interface; + f_param_ptr fp = p->data = pbc_malloc(sizeof(*fp)); + mpz_init(fp->q); + mpz_init(fp->r); + mpz_init(fp->b); + mpz_init(fp->beta); + mpz_init(fp->alpha0); + mpz_init(fp->alpha1); +} + +// Public interface: + +int pbc_param_init_f(pbc_param_ptr par, struct symtab_s *tab) { + f_init(par); + f_param_ptr p = par->data; + + int err = 0; + err += lookup_mpz(p->q, tab, "q"); + err += lookup_mpz(p->r, tab, "r"); + err += lookup_mpz(p->b, tab, "b"); + err += lookup_mpz(p->beta, tab, "beta"); + err += lookup_mpz(p->alpha0, tab, "alpha0"); + err += lookup_mpz(p->alpha1, tab, "alpha1"); + return err; +} + +void pbc_param_init_f_gen(pbc_param_t p, int bits) { + f_init(p); + f_param_ptr fp = p->data; + //36 is a 6-bit number + int xbit = (bits - 6) / 4; + //TODO: use binary search to find smallest appropriate x + mpz_t x, t; + mpz_ptr q = fp->q; + mpz_ptr r = fp->r; + mpz_ptr b = fp->b; + field_t Fq, Fq2, Fq2x; + element_t e1; + element_t f; + field_t c; + element_t P; + + mpz_init(x); + mpz_init(t); + mpz_setbit(x, xbit); + for (;;) { + mpz_mul(t, x, x); + mpz_mul_ui(t, t, 6); + mpz_add_ui(t, t, 1); + tryminusx(q, x); + mpz_sub(r, q, t); + mpz_add_ui(r, r, 1); + if (mpz_probab_prime_p(q, 10) && mpz_probab_prime_p(r, 10)) break; + + tryplusx(q, x); + mpz_sub(r, q, t); + mpz_add_ui(r, r, 1); + if (mpz_probab_prime_p(q, 10) && mpz_probab_prime_p(r, 10)) break; + + mpz_add_ui(x, x, 1); + } + + field_init_fp(Fq, q); + element_init(e1, Fq); + + for (;;) { + element_random(e1); + field_init_curve_b(c, e1, r, NULL); + element_init(P, c); + + element_random(P); + + element_mul_mpz(P, P, r); + if (element_is0(P)) break; + element_clear(P); + field_clear(c); + } + element_to_mpz(b, e1); + element_clear(e1); + field_init_quadratic(Fq2, Fq); + element_to_mpz(fp->beta, field_get_nqr(Fq)); + field_init_poly(Fq2x, Fq2); + element_init(f, Fq2x); + + // Find an irreducible polynomial of the form f = x^6 + alpha. + // Call poly_set_coeff1() first so we can use element_item() for the other + // coefficients. + poly_set_coeff1(f, 6); + for (;;) { + element_random(element_item(f, 0)); + if (poly_is_irred(f)) break; + } + + //extend F_q^2 using f = x^6 + alpha + //see if sextic twist contains a subgroup of order r + //if not, it's the wrong twist: replace alpha with alpha^5 + { + field_t ctest; + element_t Ptest; + mpz_t z0, z1; + mpz_init(z0); + mpz_init(z1); + element_init(e1, Fq2); + element_set_mpz(e1, fp->b); + element_mul(e1, e1, element_item(f, 0)); + element_neg(e1, e1); + + field_init_curve_b(ctest, e1, r, NULL); + element_init(Ptest, ctest); + element_random(Ptest); + + //I'm not sure what the #E'(F_q^2) is, but + //it definitely divides n_12 = #E(F_q^12). It contains a + //subgroup of order r if and only if + //(n_12 / r^2)P != O for some (in fact most) P in E'(F_q^6) + mpz_pow_ui(z0, q, 12); + mpz_add_ui(z0, z0, 1); + pbc_mpz_trace_n(z1, q, t, 12); + mpz_sub(z1, z0, z1); + mpz_mul(z0, r, r); + mpz_divexact(z1, z1, z0); + + element_mul_mpz(Ptest, Ptest, z1); + if (element_is0(Ptest)) { + mpz_set_ui(z0, 5); + element_pow_mpz(element_item(f, 0), element_item(f, 0), z0); + } + element_clear(e1); + element_clear(Ptest); + field_clear(ctest); + mpz_clear(z0); + mpz_clear(z1); + } + + element_to_mpz(fp->alpha0, element_x(element_item(f, 0))); + element_to_mpz(fp->alpha1, element_y(element_item(f, 0))); + + element_clear(f); + + field_clear(Fq2x); + field_clear(Fq2); + field_clear(Fq); + + mpz_clear(t); + mpz_clear(x); +} |