point_mul_postprocess(rP, r, params->curve);    bm_put(bm_get_time(), "rP1");    fp2_init(gidr);    byte_string_set_point(U, rP);    point_clear(rP);    point_init(Qid);    for (i=0; i<count; i++) {	const char *id = idarray[i];	//XXX:set up a cache to avoid these expensive ops	map_to_point(Qid, id, params);	point_Phi(Qid, Qid, params);		//calculate gidr = e(Q_id, Phi(P_pub))^r	//tate_pairing(gidr, Qid, PhiPpub);	tate_postprocess(gidr, params->Ppub_mc, Qid, params->curve);	bm_put(bm_get_time(), "gidr0");	fp2_pow(gidr, gidr, r, params->p);	bm_put(bm_get_time(), "gidr1");	hash_H(s[i], gidr, params);    }    point_clear(Qid);    mpz_clear(r);    fp2_clear(gidr);}void IBE_KEM_encrypt(byte_string_t secret,	byte_string_t U, char *id, params_t params){    byte_string_t s[1];    IBE_KEM_encrypt_array(s, U, &id, 1, params);    byte_string_assign(secret, s[0]);}void IBE_KEM_decrypt(byte_string_t s,	byte_string_t U, byte_string_t key, params_t params){    point_t xQ, rP;    fp2_t res;    fp2_init(res);    point_init(xQ);    point_init(rP);    point_set_byte_string(xQ, key);    point_set_byte_string(rP, U);    point_Phi(rP, rP, params);    tate_pairing(res, xQ, rP, params->curve);    hash_H(s, res, params);    fp2_clear(res);    point_clear(xQ);    point_clear(rP);}void IBE_get_shared_secret(byte_string_t s,	char *id, byte_string_t key, params_t params){    point_t Qid;    fp2_t gid;    point_t Q;    point_init(Q);    fp2_init(gid);    point_init(Qid);    map_to_point(Qid, id, params);    //calculate gid = e(Q, Phi(Q_id))    point_set_byte_string(Q, key);    point_Phi(Qid, Qid, params);    tate_pairing(gid, Q, Qid, params->curve);    hash_H(s, gid, params);    fp2_clear(gid);    point_clear(Q);    point_clear(Qid);}char* IBE_version(params_t params){    return params->version;}char* IBE_system(params_t params){    return params->id;}int IBE_threshold(params_t params){    return params->sharet;}void IBE_split_master(byte_string_t *mshare,	byte_string_t master, int t, int n, params_t params)//split the master key into n pieces//t of them are required to generate a key{    mpz_t poly[t];    mpz_t *x;    mpz_t y[n];    mpz_t z;    mpz_t r;    int i, j;    byte_string_t bs1, bs2;    //start with random polynomial with degree <= t-2    //(in F_q)    //whose constant term = master    mpz_init(r);    mpz_init(poly[0]);    mympz_set_byte_string(poly[0], master);    for (i=1; i<t; i++) {	mpz_init(poly[i]);	mympz_randomm(r, params->q);	mpz_set(poly[i], r);    }    mpz_init(z);    if (0) {	printf("secret poly: ");	for (i=0; i<t; i++) {	    printf(" ");	    mpz_out_str(NULL, 0, poly[i]);	}	printf("\n");    }    params->robustx = (mpz_t *) malloc(n * sizeof(mpz_t));    params->robustP = (point_t *) malloc(n * sizeof(point_t));    params->sharet = t;    params->sharen = n;    x = params->robustx;    for (i=0; i<n; i++) {	mympz_randomm(r, params->q);	mpz_init(x[i]);	mpz_set(x[i], r);	//Horner's rule	mpz_set_ui(z, 0);	for (j=t-1; j>=0; j--) {	    mpz_mul(z, z, x[i]);	    mpz_add(z, z, poly[j]);	    mpz_mod(z, z, params->q);	}	mpz_init_set(y[i], z);	byte_string_set_int(bs1, i);	byte_string_set_mpz(bs2, z);	byte_string_join(mshare[i], bs1, bs2);	byte_string_clear(bs1);	byte_string_clear(bs2);    }    for (i=0; i<n; i++) {	point_init(params->robustP[i]);	point_mul(params->robustP[i], y[i], params->Ppub, params->curve);    }    for (i=0; i<t; i++) {	mpz_clear(poly[i]);    }    for (i=0; i<n; i++) {	mpz_clear(y[i]);    }    mpz_clear(z);    mpz_clear(r);}int IBE_construct_master(byte_string_t master,	byte_string_t *mshare, params_t params)//reconstruct the master from master shares//(shouldn't normally be used since they should never be in one place){    int i, j;    int indexi, indexj;    int t = params->sharet;    mpz_t x;    mpz_t y;    mpz_t z;    mpz_t num, denom;    byte_string_t bs1, bs2;    mpz_init(x);    mpz_init(y);    mpz_init(z);    mpz_init(num);    mpz_init(denom);    mpz_set_ui(x, 0);    for (i=0; i<t; i++) {	mpz_set_ui(num, 1);	mpz_set_ui(denom, 1);	byte_string_split(bs1, bs2, mshare[i]);	indexi = int_from_byte_string(bs1);	byte_string_clear(bs1);	mympz_set_byte_string(y, bs2);	byte_string_clear(bs2);	for (j=0; j<t; j++) {	    if (j != i) {		byte_string_split(bs1, bs2, mshare[j]);		indexj = int_from_byte_string(bs1);		byte_string_clear(bs1);		byte_string_clear(bs2);		mpz_mul(num, num, params->robustx[indexj]);		mpz_mod(num, num, params->q);		mpz_sub(z, params->robustx[indexj], params->robustx[indexi]);		mpz_mul(denom, denom, z);		mpz_mod(denom, denom, params->q);	    }	}	mpz_invert(denom, denom, params->q);	mpz_mul(z, num, denom);	mpz_mod(z, z, params->q);	mpz_mul(z, z, y);	mpz_mod(z, z, params->q);	mpz_add(x, x, z);	if (mpz_cmp(x, params->q) >= 0) {	    mpz_sub(x, x, params->q);	}    }    byte_string_set_mpz(master, x);    mpz_clear(x);    mpz_clear(y);    mpz_clear(z);    mpz_clear(num);    mpz_clear(denom);    return 1;}int IBE_serialize_params(byte_string_t bs, params_t params)//put system parameters into a byte_string{    int i, j;    byte_string_t *bsa;    i = 0;    bsa = (byte_string_t *) alloca(sizeof(byte_string_t)	    * (2 * params->sharen + 20));    byte_string_set(bsa[i++], params->version);    byte_string_set(bsa[i++], params->id);    byte_string_set_mpz(bsa[i++], params->p);    byte_string_set_mpz(bsa[i++], params->q);    byte_string_set_point(bsa[i++], params->P);    byte_string_set_point(bsa[i++], params->Ppub);    byte_string_set_int(bsa[i++], params->sharet);    byte_string_set_int(bsa[i++], params->sharen);    for (j=0; j<params->sharen; j++) {	byte_string_set_mpz(bsa[i++], params->robustx[j]);	byte_string_set_point(bsa[i++], params->robustP[j]);    }    byte_string_encode_array(bs, bsa, i);    for (j=0; j<i; j++) {	byte_string_clear(bsa[j]);    }    return 1;}int IBE_deserialize_params(params_t params, byte_string_t bs)//get system parameters from a byte_string{    byte_string_t *bsa;    int n;    int i, j;    byte_string_decode_array(&bsa, &n, bs);    //TODO: check n is big enough    i = 0;    params->version = charstar_from_byte_string(bsa[i++]);    params->id = charstar_from_byte_string(bsa[i++]);    mpz_init(params->p);    mpz_init(params->q);    mympz_set_byte_string(params->p, bsa[i++]);    mympz_set_byte_string(params->q, bsa[i++]);    initpq(params);        point_init(params->P);    point_init(params->Ppub);    point_set_byte_string(params->P, bsa[i++]);    point_set_byte_string(params->Ppub, bsa[i++]);    point_init(params->PhiPpub);    point_Phi(params->PhiPpub, params->Ppub, params);    params->sharet = int_from_byte_string(bsa[i++]);    params->sharen = int_from_byte_string(bsa[i++]);    params->robustx = (mpz_t *) malloc(params->sharen * sizeof(mpz_t));    params->robustP = (point_t *) malloc(params->sharen * sizeof(point_t));    for (j=0; j<params->sharen; j++) {	mpz_init(params->robustx[j]);	mympz_set_byte_string(params->robustx[j], bsa[i++]);	//TODO: check it's different from others	point_init(params->robustP[j]);	point_set_byte_string(params->robustP[j], bsa[i++]);    }    point_mul_preprocess(params->P, params->curve);    miller_cache_init(params->Ppub_mc, params->curve);    tate_preprocess(params->Ppub_mc, params->Ppub, params->curve);    for(i=0; i<n; i++) {	byte_string_clear(bsa[i]);    }    free(bsa);    return 1;}void params_out(FILE *outfp, params_t params){    fprintf(outfp, "IBE version: %s\n", params->version);    fprintf(outfp, "system ID: %s\n", params->id);    fprintf(outfp, "p = ");    mpz_out_str(outfp, 0, params->p);    fprintf(outfp, "\n");    fprintf(outfp, "q = ");    mpz_out_str(outfp, 0, params->q);    fprintf(outfp, "\n");    fprintf(outfp, "P = ");    point_out_str(outfp, 0, params->P);    fprintf(outfp, "\n");    fprintf(outfp, "Ppub = ");    point_out_str(outfp, 0, params->Ppub);    fprintf(outfp, "\n");    fprintf(outfp, "share t/n = %d/%d\n", params->sharet, params->sharen);}void BLS_keygen(byte_string_t private, byte_string_t public, params_t params){    mpz_t x;    point_t xP;    //pick random private key x in F_q    mpz_init(x);    mympz_randomm(x, params->q);    byte_string_set_mpz(private, x);    //public = x params->P    point_init(xP);    point_mul(xP, x, params->P, params->curve);    byte_string_set_point(public, xP);    mpz_clear(x);    point_clear(xP);}void BLS_sign(byte_string_t sig,	byte_string_t message, byte_string_t key, params_t params){    mpz_t x;    point_t P, xP;    point_init(P);    //hash message to point    map_byte_string_to_point(P, message, params);    //multiply it by key    mpz_init(x);    mympz_set_byte_string(x, key);    point_init(xP);    point_mul(xP, x, P, params->curve);    //xP is the signature    byte_string_set_point(sig, xP);    mpz_clear(x);    point_clear(P);    point_clear(xP);}int is_DDH_tuple(point_t P, point_t aP, point_t bP, point_t cP, params_t params){    int result;    fp2_t a, b;    point_t PhicP, PhibP;    fp2_init(a); fp2_init(b);    point_init(PhibP); point_init(PhicP);    point_Phi(PhicP, cP, params);    point_Phi(PhibP, bP, params);    tate_pairing(a, P, PhicP, params->curve);    tate_pairing(b, aP, PhibP, params->curve);    result = fp2_equal(a, b);    point_clear(PhibP);    point_clear(PhicP);    fp2_clear(a); fp2_clear(b);    return result;}int BLS_verify(byte_string_t sig,	byte_string_t message, byte_string_t pubkey, params_t params){    int result;    point_t P, xP;    point_t Q, xQ;    point_init(P);    point_init(xP);    point_init(Q);    point_init(xQ);    //hash message to point Q    map_byte_string_to_point(Q, message, params);    //sig should be xP    point_set_byte_string(xQ, sig);    //pubkey is xP    point_set_byte_string(xP, pubkey);    point_set(P, params->P);    //verify P, xP, Q, xQ is DDH    result = is_DDH_tuple(P, xP, Q, xQ, params);    point_clear(P);    point_clear(xP);    point_clear(Q);    point_clear(xQ);    return result;}//using certificates and BLS we can do identity-based signaturesvoid IBE_keygen(byte_string_t privkey, byte_string_t pubkey, params_t params){    BLS_keygen(privkey, pubkey, params);}void IBE_certify_share(byte_string_t share, byte_string_t mshare,	byte_string_t public, const char *id, params_t params){    byte_string_t H;    byte_string_t bsid;    byte_string_set(bsid, id);    crypto_va_hash(H, 2, public, bsid);    byte_string_clear(bsid);    IBE_extract_share_byte_string(share, mshare, H, params);    byte_string_clear(H);}void IBE_certify(byte_string_t cert, byte_string_t master,	byte_string_t public, const char *id, params_t params){    byte_string_t H;    byte_string_t bsid;    byte_string_set(bsid, id);    crypto_va_hash(H, 2, public, bsid);    byte_string_clear(bsid);    IBE_extract_byte_string(cert, master, H, params);    byte_string_clear(H);}void IBE_sign(byte_string_t sig, byte_string_t message, byte_string_t private,	byte_string_t cert, params_t params){    mpz_t x;    point_t P, xP, C;    point_init(P);    point_init(xP);    point_init(C);    //hash message to point    map_byte_string_to_point(P, message, params);    //multiply it by key    mpz_init(x);    mympz_set_byte_string(x, private);    point_mul(xP, x, P, params->curve);    point_set_byte_string(C, cert);    //signature = BLS signature + certificate    point_add(C, C, xP, params->curve);    byte_string_set_point(sig, C);    mpz_clear(x);    point_clear(P);    point_clear(xP);    point_clear(C);}int IBE_verify(byte_string_t sig, byte_string_t message, byte_string_t public,	const char *id, params_t params){    int result;    point_t P, Q;    fp2_t f1, f2, f3;    byte_string_t H;    byte_string_t bsid;    fp2_init(f1); fp2_init(f2); fp2_init(f3);    //compute LHS of equation = e(P, sig)    point_init(P);    point_set(P, params->P);    point_init(Q);    point_set_byte_string(Q, sig);    point_Phi(Q, Q, params);    tate_pairing(f1, P, Q, params->curve);    //compute first factor on RHS = e(public key, message)    point_set_byte_string(P, public);    map_byte_string_to_point(Q, message, params);    point_Phi(Q, Q, params);    tate_pairing(f2, P, Q, params->curve);    //compute second factor on RHS = e(server public key, cert plaintext)    byte_string_set(bsid, id);    crypto_va_hash(H, 2, public, bsid);    map_byte_string_to_point(Q, H, params);    byte_string_clear(bsid);    byte_string_clear(H);    point_Phi(Q, Q, params);    tate_pairing(f3, params->Ppub, Q, params->curve);    fp2_mul(f2, f2, f3, params->p);    if (!fp2_equal(f1, f2)) {	result = 0;    } else result = 1;    point_clear(P); point_clear(Q);    fp2_clear(f1); fp2_clear(f2); fp2_clear(f3);    return result;}int IBE_hide_key_array(byte_string_t U, byte_string_t *V,	char **id, int idcount, byte_string_t K, params_t params){    int i;    byte_string_t *secret;    bm_put(bm_get_time(), "enc0");    secret = (byte_string_t *) alloca(sizeof(byte_string_t) * idcount);    IBE_KEM_encrypt_array(secret, U, id, idcount, params);    for (i=0; i<idcount; i++) {	if (1 != crypto_encrypt(V[i], K, secret[i])) {	    //error: crypto_encrypt failed	    for (i--; i>=0; i--) {		byte_string_clear(V[i]);	    }	    for (i=0; i<idcount; i++) {		byte_string_clear(secret[i]);	    }	    return 0;	}    }    for (i=0; i<idcount; i++) {	byte_string_clear(secret[i]);    }    bm_put(bm_get_time(), "enc1");    bm_report_encrypt();    return 1;}int IBE_hide_key(byte_string_t U, byte_string_t V,	char *id, byte_string_t K, params_t params){    byte_string_t bs[1];    int result;    result = IBE_hide_key_array(U, bs, &id, 1, K, params);    byte_string_assign(V, bs[0]);    return result;}int IBE_reveal_key(byte_string_t K,	byte_string_t U, byte_string_t V, byte_string_t privkey, params_t params){    int result = 1;    byte_string_t secret;    IBE_KEM_decrypt(secret, U, privkey, params);    if (1 != crypto_decrypt(K, V, secret)) {	fprintf(stderr, "WARNING: INVALID CIPHERTEXT!\n");	result = 0;    }    byte_string_clear(secret);    return result;}