ibe_lib.c

这是一个unix环境下实现基于身份的PKI系统源码

/* IBE library routines, see ibe.h for usage
 * Ben Lynn
 */

/*
Copyright (C) 2001 Benjamin Lynn ([e-mail])

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);