ibe_lib.c

The Stanford IBE library is a C implementation of the Boneh-Franklin identity-based encryption sche

    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 signatures
void 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;
}