/* IBE library routines, see ibe.h for usage * Ben Lynn *//*Copyright (C) 2001 Benjamin Lynn (blynn@cs.stanford.edu)See LICENSE for license*/#include <assert.h>#include <stdio.h>#include <stdlib.h>#include <time.h>#include <string.h>#include "curve.h"#include "version.h"#include "benchmark.h"#include "ibe.h"#include "crypto.h"#include "mm.h"void preprocessed_key_init(preprocessed_key_t pk, params_t params){    miller_cache_init(pk->mc, params->curve);}void preprocessed_key_clear(preprocessed_key_t pk){    miller_cache_clear(pk->mc);}int mympz_sizeinbytes(mpz_t x){    int i, n;    n = mpz_sizeinbase(x, 2);    i = n >> 3;    if (n % 8) i++;    return i;}void mympz_out_raw(mpz_t x, unsigned char *c, int n){    unsigned long l;    mpz_t z;    int i = n - 1;    mpz_init_set(z, x);    while(i >= 0) {	l = mpz_get_ui(z);	c[i] = (unsigned char) l;	mpz_tdiv_q_2exp(z, z, 8);	i--;    }    mpz_clear(z);}void mympz_inp_raw(mpz_t z, const unsigned char* c, int n){    int i = 0;    mpz_set_ui(z, 0);    while(i < n) {	mpz_mul_2exp(z, z, 8);	mpz_add_ui(z, z, c[i]);	i++;    }}static void mympz_from_hash(mpz_t x, mpz_t limit, byte_string_t hash)//let z = number represented in c//x = z || 1 || z || 2 || z || 3 ...//until there are enough bits//should be rewritten more efficiently?{    mpz_t z;    int countlen;    mpz_t count;    int i = 0, j;    int bits = mpz_sizeinbase(limit, 2);    int zbits;    char *c = hash->data;    int len = hash->len;    mpz_init(z);    mpz_init(count);    mpz_set_ui(count, 1);    mympz_inp_raw(z, c, len);    zbits = mpz_sizeinbase(z, 2);    mpz_set_ui(x, 0);    do {	for (j=0; j<zbits; j++) {	    if (mpz_tstbit(z, j)) {		mpz_setbit(x, i);	    }	    i++;	}	bits -= zbits;	if (bits <= 0) break;	countlen = mpz_sizeinbase(count, 2);	for (j=0; j<countlen; j++) {	    if (mpz_tstbit(count, j)) {		mpz_setbit(x, i);	    }	    i++;	}	bits -= countlen;	mpz_add_ui(count, count, 1);    } while (bits > 0);    /*    printf("hash: ");    mpz_out_str(NULL, 0, x);    printf("\n");    */    while (mpz_cmp(x, limit) > 0) {	mpz_clrbit(x, mpz_sizeinbase(x, 2) - 1);    }    mpz_clear(z);    mpz_clear(count);}void byte_string_set_mpz(byte_string_t bs, mpz_t x){    int i = mympz_sizeinbytes(x);    byte_string_init(bs, i);    mympz_out_raw(x, bs->data, i);}void byte_string_set_fp2(byte_string_t bs, fp2_t x){    byte_string_t bs1, bs2;    byte_string_set_mpz(bs1, x->a);    byte_string_set_mpz(bs2, x->b);    byte_string_join(bs, bs1, bs2);    byte_string_clear(bs1);    byte_string_clear(bs2);}void byte_string_set_point(byte_string_t bs, point_t P){    byte_string_t bs1, bs2;    byte_string_set_fp2(bs1, P->x);    byte_string_set_fp2(bs2, P->y);    byte_string_join(bs, bs1, bs2);    byte_string_clear(bs1);    byte_string_clear(bs2);}void mympz_set_byte_string(mpz_t z, byte_string_t bs){    mympz_inp_raw(z, bs->data, bs->len);}void fp2_set_byte_string(fp2_t x, byte_string_t bs){    byte_string_t bs1, bs2;    byte_string_split(bs1, bs2, bs);    mympz_set_byte_string(x->a, bs1);    mympz_set_byte_string(x->b, bs2);    byte_string_clear(bs1);    byte_string_clear(bs2);}void point_set_byte_string(point_t P, byte_string_t bs){    byte_string_t bs1, bs2;    byte_string_split(bs1, bs2, bs);    fp2_set_byte_string(P->x, bs1);    fp2_set_byte_string(P->y, bs2);    byte_string_clear(bs1);    byte_string_clear(bs2);}static void point_Phi(point_t PhiP, point_t P, params_t params){    fp2_mul(PhiP->x, P->x, params->zeta, params->p);    fp2_set(PhiP->y, P->y);}static void point_make_order_q(point_t P, params_t params)//P = ((p + 1)/q)P //so it has order q{    point_mul(P, params->p1onq, P, params->curve);}static void initpq(params_t params)//calculate system parameters that can be determined from p and q//also initialize the elliptic curve library so points can be used{    mpz_init(params->p1onq);    mpz_add_ui(params->p1onq, params->p, 1);    mpz_divexact(params->p1onq, params->p1onq, params->q);    //initialize the elliptic curve library    curve_init(params->curve, params->p, params->q);    fp2_init(params->zeta);    fp2_set_cbrt_unity(params->zeta, params->p);}void hash_G(mpz_t h, byte_string_t bs, params_t params)//hash a byte_string to an element of Z_p{    byte_string_t md_value;    crypto_hash(md_value, bs);    mympz_from_hash(h, params->p, md_value);    byte_string_clear(md_value);}void hash_H(byte_string_t md_value, fp2_t x, params_t params)//hash a point of E/F_p^2 to a byte_string{    byte_string_t bs;    byte_string_set_fp2(bs, x);    crypto_hash(md_value, bs);    byte_string_clear(bs);}static void map_byte_string_to_point(point_t d,	byte_string_t bs, params_t params)//converts byte_string into a point of order q on E/F_p{    int i;    fp2_t x, y;    bm_put(bm_get_time(), "mtp0");    fp2_init(x);    fp2_init(y);    //first use G function to choose x coordinate    hash_G(y->a, bs, params);    mpz_set_ui(x->b, 0);    mpz_set_ui(y->b, 0);    bm_put(bm_get_time(), "mtp1");    for (i=1;;i++) {	x_from_y(x->a, y->a, params->curve);	//we now have a point d	fp2_set(d->x, x);	fp2_set(d->y, y);	//make it order q	point_make_order_q(d, params);	if (!d->infinity) break;	//unlikely case: pick first available point	mpz_set_ui(y->a, i);    }    bm_put(bm_get_time(), "mtp2");    /*    printf("mapped to ");    point_out_str(NULL, 0, d);    printf("\n");    */    fp2_clear(x);    fp2_clear(y);}static void map_to_point(point_t d, const char *id, params_t params)//converts id into a point of order q on E/F_p{    byte_string_t bsid;    byte_string_set(bsid, id);    map_byte_string_to_point(d, bsid, params);    byte_string_clear(bsid);}void IBE_init(void)//NOT THREAD-SAFE. May add contexts here eventually...{    crypto_init();}void IBE_clear(void)/* Free memory used by library */{    crypto_clear();}void params_robust_clear(params_t params){    int i;    for (i=0; i<params->sharen; i++) {	point_clear(params->robustP[i]);	mpz_clear(params->robustx[i]);    }    free(params->robustP);    free(params->robustx);    params->sharet = params->sharen = 0;}void params_clear(params_t params){    curve_clear(params->curve);    mpz_clear(params->p1onq);    fp2_clear(params->zeta);    miller_cache_clear(params->Ppub_mc);    if (params->sharen) params_robust_clear(params);    mpz_clear(params->p);    mpz_clear(params->q);    point_clear(params->P);    point_clear(params->Ppub);    point_clear(params->PhiPpub);    free(params->version);    free(params->id);}void IBE_setup(params_t params, byte_string_t master, int k, int qk, char *id)/* generate system parameters * k = number of bits in p (should be at least 512) * qk = number of bits in q (size of subgroup, 160 is typical) * id = system ID */{    mpz_t p, q, r;    mpz_t x;    point_ptr P;    int solinasa, solinasb;    int kqk = k - qk - 4; //lose 4 bits since 12 is a 4-bit no.    unsigned int seed;    mpz_init(p); mpz_init(q); mpz_init(r); mpz_init(x);    //find random k-bit prime p such that    //p = 2 mod 3 and q = (p+1)/12r is prime as well for some r    //now also want q to be a Solinas prime    //we use rand() to help us find one: should be ok    crypto_rand_bytes((unsigned char *) &seed, sizeof(int));    srand(seed);    for(;;) {	//once q was just a random qk-bit prime	//now it must be a Solinas one	mpz_set_ui(q, 0);	solinasa = qk - 1;	mpz_setbit(q, solinasa);	mpz_set_ui(r, 0);	solinasb = rand() % qk;	mpz_setbit(r, solinasb);	if (rand() % 2) {	    mpz_add(q, q, r);	} else {	    mpz_sub(q, q, r);	    solinasb = -solinasb;	}	mpz_set_ui(r, 1);	if (rand() % 2) {	    mpz_add(q, q, r);	} else {	    mpz_sub(q, q, r);	    solinasa = -solinasa;	}	if (!mpz_probab_prime_p(q, 10)) continue;	mympz_randomb(r, kqk);	//p = q * r	mpz_mul(p, q, r);	//r = (((p << 1) + p) << 2) (= 12p)	mpz_mul_2exp(r, p, 1);	mpz_add(r, r, p);	mpz_mul_2exp(r, r, 2);	//p = r - 1	mpz_set_ui(p, 1);	mpz_sub(p, r, p);	if (mpz_probab_prime_p(p, 10)) break;    }    //pick master key x from F_q    mympz_randomm(x, q);    byte_string_set_mpz(master, x);    mpz_init(params->p);    mpz_init(params->q);    mpz_set(params->p, p);    mpz_set(params->q, q);    initpq(params);    //pick random point P of order q from E/F_p    point_init(params->P);    P = params->P;    do {	point_random(P, params->curve);	point_make_order_q(P, params);    } while (P->infinity);    point_init(params->Ppub);    point_mul(params->Ppub, x, P, params->curve);    point_mul_preprocess(P, params->curve);    miller_cache_init(params->Ppub_mc, params->curve);    tate_preprocess(params->Ppub_mc, params->Ppub, params->curve);    point_init(params->PhiPpub);    point_Phi(params->PhiPpub, params->Ppub, params);    params->id = (char *) malloc(strlen(id) + 1);    strcpy(params->id, id);    params->sharet = params->sharen = 0;    params->version = (char *) malloc(strlen(IBE_VERSION) + 1);    strcpy(params->version, IBE_VERSION);    mpz_clear(p); mpz_clear(q); mpz_clear(r); mpz_clear(x);}void IBE_extract_byte_string(byte_string_t bs, byte_string_t master,	byte_string_t id, params_t params)//for testing purposes{    point_t key;    mpz_t x;    mpz_init(x);    point_init(key);    map_byte_string_to_point(key, id, params);    mympz_set_byte_string(x, master);    point_mul(key, x, key, params->curve);    byte_string_set_point(bs, key);    point_clear(key);    mpz_clear(x);}void IBE_extract(byte_string_t bs,	byte_string_t master, const char *id, params_t params)//same as above, char * version{    byte_string_t bsid;    byte_string_set(bsid, id);    IBE_extract_byte_string(bs, master, bsid, params);    byte_string_clear(bsid);}void IBE_extract_share_byte_string(byte_string_t share, byte_string_t mshare,	byte_string_t id, params_t params)//extract a private key share from an ID and master share{    mpz_t y;    int i;    byte_string_t bs1, bs2;    point_t yd;    point_t d;    point_init(yd);    point_init(d);    mpz_init(y);    byte_string_split(bs1, bs2, mshare);    i = int_from_byte_string(bs1);    mympz_set_byte_string(y, bs2);    byte_string_clear(bs1);    byte_string_clear(bs2);    map_byte_string_to_point(d, id, params);    point_mul(yd, y, d, params->curve);    byte_string_set_int(bs1, i);    byte_string_set_point(bs2, yd);    byte_string_join(share, bs1, bs2);    byte_string_clear(bs1);    byte_string_clear(bs2);    point_clear(yd);    point_clear(d);    mpz_clear(y);}void IBE_extract_share(byte_string_t share,	byte_string_t mshare, const char *id, params_t params)//same as above except takes in char * instead of byte_string{    byte_string_t bsid;    byte_string_set(bsid, id);    IBE_extract_share_byte_string(share, mshare, bsid, params);    byte_string_clear(bsid);}int IBE_combine(byte_string_t key, byte_string_t *kshare, params_t params)//reconstruct a key from key shares, or a certificate from certificate shares{    int i, j;    int indexi, indexj;    point_t yP;    mpz_t num, denom;    mpz_t z;    point_t d;    byte_string_t bs1, bs2;    int *index;    index = (int *) alloca(params->sharet * sizeof(int));    for (i=0; i<params->sharet; i++) {	byte_string_split(bs1, bs2, kshare[i]);	byte_string_clear(bs2);	index[i] = int_from_byte_string(bs1);	byte_string_clear(bs1);	for (j=0; j<i; j++) {	    if (index[i] == index[j]) {		return 0;	    }	}    }    point_init(yP);    mpz_init(z);    mpz_init(num); mpz_init(denom);    point_init(d);    point_set_O(d);    for (i=0; i<params->sharet; i++) {	byte_string_split(bs1, bs2, kshare[i]);	indexi = index[i];	byte_string_clear(bs1);	point_set_byte_string(yP, bs2);	byte_string_clear(bs2);	mpz_set_ui(num, 1);	mpz_set_ui(denom, 1);	for (j=0; j<params->sharet; j++) {	    if (j != i) {		indexj = index[j];		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);	point_mul(yP, z, yP, params->curve);	point_add(d, d, yP, params->curve);    }    byte_string_set_point(key, d);    point_clear(yP);    mpz_clear(z);    mpz_clear(num); mpz_clear(denom);    point_clear(d);    return 1;}void IBE_get_shared_secret_preprocess(preprocessed_key_t pk,	byte_string_t key, params_t params){    point_t Q;    point_init(Q);    point_set_byte_string(Q, key);    tate_preprocess(pk->mc, Q, params->curve);    point_clear(Q);}void IBE_get_shared_secret_postprocess(byte_string_t s,	char *id, preprocessed_key_t pk, params_t params){    point_t Qid;    fp2_t gid;    fp2_init(gid);    point_init(Qid);    map_to_point(Qid, id, params);    //calculate gid = e(Q_id, Phi(P_pub))    point_Phi(Qid, Qid, params);    tate_postprocess(gid, pk->mc, Qid, params->curve);    hash_H(s, gid, params);    fp2_clear(gid);    point_clear(Qid);}void IBE_KEM_encrypt_array(byte_string_t *s, byte_string_t U,	char **idarray, int count, params_t params){    int i;    mpz_t r;    fp2_t gidr;    point_t Qid;    point_t rP;    if (count <= 0) return;    //r is random in F_q    mpz_init(r);    mympz_randomm(r, params->q);    bm_put(bm_get_time(), "rP0");    //U = rP    point_init(rP);    //point_mul(rP, r, params->P);