field.c

这是一个C的源代码

    element_invert(e0, e0);
    element_mul(r, a, e0);
    element_clear(e0);
}

static void zero_to_mpz(mpz_t z, element_ptr a)
{
    UNUSED_VAR(a);
    mpz_set_ui(z, 0);
}

static void zero_set_mpz(element_ptr a, mpz_t z)
{
    UNUSED_VAR(z);
    element_set0(a);
}

static void zero_random(element_ptr a)
{
    element_set0(a);
}

static void generic_set_si(element_ptr a, long int si)
{
    mpz_t z;
    mpz_init(z);
    mpz_set_si(z, si);
    element_set_mpz(a, z);
    mpz_clear(z);
}

static void generic_sub(element_ptr c, element_ptr a, element_ptr b)
{
    if (c != a) {
	element_neg(c, b);
	element_add(c, c, a);
    } else {
	element_t tmp;
	element_init(tmp, a->field);
	element_neg(tmp, b);
	element_add(c, tmp, a);
	element_clear(tmp);
    }
}

static void generic_div(element_ptr c, element_ptr a, element_ptr b)
{
    if (c != a) {
	element_invert(c, b);
	element_mul(c, c, a);
    } else {
	element_t tmp;
	element_init(tmp, a->field);
	element_invert(tmp, b);
	element_mul(c, tmp, a);
	element_clear(tmp);
    }
}

static void generic_add_ui(element_ptr c, element_ptr a, unsigned long int b)
{
    element_t e;
    mpz_t z;
    element_init(e, c->field);
    mpz_init(z);
    mpz_set_ui(z, b);
    element_set_mpz(e, z);
    element_add(c, a, e);
    mpz_clear(z);
    element_clear(e);
}

static int generic_cmp(element_ptr a, element_ptr b)
{
    int result;
    unsigned char *buf1, *buf2;
    int len;
    if (a == b) return 0;
    len = element_length_in_bytes(a);
    if (len != element_length_in_bytes(b)) return 1;
    buf1 = pbc_malloc(len);
    buf2 = pbc_malloc(len);
    element_to_bytes(buf1, a);
    element_to_bytes(buf2, b);
    result = memcmp(buf1, buf2, len);
    pbc_free(buf1);
    pbc_free(buf2);
    return result;
}

static int generic_is0(element_ptr a)
{
    int result;
    element_t b;
    element_init(b, a->field);
    result = element_cmp(a, b);
    element_clear(b);
    return result;
}

static int generic_is1(element_ptr a)
{
    int result;
    element_t b;
    element_init(b, a->field);
    element_set1(b);
    result = element_cmp(a, b);
    element_clear(b);
    return result;
}

static void generic_out_info(FILE *out, field_ptr f)
{
    element_fprintf(out, "field %p unknown\n", f);
    element_fprintf(out, "order = %Zd\n", f->order);
}

int default_element_snprint(char *s, size_t n, element_t e)
{
    UNUSED_VAR(e);
    if (n == 1) {
	s[0] = '0';
    } else if (n >= 2) {
	s[0] = '?';
	s[1] = '\0';
    }
    return 1;
}

int default_element_set_str(element_t e, char *s, int base)
{
    UNUSED_VAR(s);
    UNUSED_VAR(base);
    element_set0(e);
    return 0;
}

static void warn_field_clear(field_ptr f)
{
    fprintf(stderr, "field %p has no clear function\n", f);
}

void field_out_info(FILE *out, field_ptr f)
{
    f->out_info(out, f);
}

void field_init(field_ptr f)
{
    //should be called by each field_init_*
    f->nqr = NULL;
    mpz_init(f->order);

    //this should later be set
    f->field_clear = warn_field_clear;

    //and this to something more helpful
    f->out_info = generic_out_info;

    //many of these can usually be optimized for particular fields
    //provided for developer's convenience
    f->halve = generic_halve;
    f->doub = generic_double;
    f->square = generic_square;
    f->mul_mpz = generic_mul_mpz;
    f->mul_si = generic_mul_si;
    f->cmp = generic_cmp;
    f->sub = generic_sub;
    f->div = generic_div;
    f->add_ui = generic_add_ui;

    //default: converts all elements to integer 0
    //reads all integers as 0
    //random always outputs 0
    f->to_mpz = zero_to_mpz;
    f->set_mpz = zero_set_mpz;
    f->random = zero_random;
    f->set_si = generic_set_si;
    f->is1 = generic_is1;
    f->is0 = generic_is0;

    //these are fast, thanks to Hovav
    f->pow_mpz = generic_pow_mpz;

    f->pp_init = default_element_pp_init;
    f->pp_clear = default_element_pp_clear;
    f->pp_pow = default_element_pp_pow;
    f->snprint = default_element_snprint;
    f->set_str = default_element_set_str;
}

void field_clear(field_ptr f)
{
    if (f->nqr) {
	element_clear(f->nqr);
	pbc_free(f->nqr);
    }
    mpz_clear(f->order);
    f->field_clear(f);
}

void pbc_mpz_out_raw_n(unsigned char *data, int n, mpz_t z)
{
    size_t count;
    if (mpz_sgn(z)) {
	count = (mpz_sizeinbase(z, 2) + 7) / 8;
	mpz_export(&data[n - count], NULL, 1, 1, 1, 0, z);
	memset(data, 0, n - count);
    } else {
	memset(data, 0, n);
    }
}

//for short hashes H, do
//  buf = H || 0 || H || 1 || H || ...
//before calling mpz_import
void pbc_mpz_from_hash(mpz_t z, mpz_t limit,
	unsigned char *data, unsigned int len)
{
    size_t i = 0, n, count = (mpz_sizeinbase(limit, 2) + 7) / 8;
    unsigned char buf[count];
    unsigned char counter = 0;
    int done = 0;
    for(;;) {
	if (len >= count - i) {
	    n = count - i;
	    done = 1;
	} else n = len;
	memcpy(buf + i, data, n);
	i += n;
	if (done) break;
	buf[i] = counter;
	counter++;
	i++;
	if (i == count) break;
    }
    assert(i == count);
    mpz_import(z, count, 1, 1, 1, 0, buf);
    while (mpz_cmp(z, limit) > 0) {
	mpz_tdiv_q_2exp(z, z, 1);
    }
}

// g, h in some group of order r
// finds x such that g^x = h
// will hang if no such x exists
// x in some field_t that set_mpz makes sense for
void brute_force_dlog(element_t x, element_t g, element_t h)
{
    element_t g0;
    mpz_t count;

    mpz_init(count);
    element_init_same_as(g0, g);

    element_set(g0, g);
    mpz_set_ui(count, 1);
    while (element_cmp(g0, h)) {
	element_mul(g0, g0, g);
//element_printf("g0^%Zd = %B\n", count, g0);
	mpz_add_ui(count, count, 1);
    }
    element_set_mpz(x, count);
    mpz_clear(count);
    element_clear(g0);
}

// x in Z_r, g, h in some group of order r
// finds x such that g^x = h
void pollard_rho(element_t x, element_t g, element_t h)
//see Blake, Seroussi and Smart
//only one snark for this implementation
{
    int i, s = 20;
    field_ptr Zr = x->field, G = g->field;
    element_t asum;
    element_t bsum;
    element_t a[s];
    element_t b[s];
    element_t m[s];
    element_t g0, snark;
    darray_t hole;
    int interval = 5;
    mpz_t counter;
    int found = 0;

    struct snapshot_s {
	element_t a;
	element_t b;
	element_t snark;
    };
    typedef struct snapshot_s *snapshot_ptr;

    void record(void)
    {
	snapshot_ptr ss = pbc_malloc(sizeof(struct snapshot_s));
	element_init_same_as(ss->a, asum);
	element_init_same_as(ss->b, bsum);
	element_init_same_as(ss->snark, snark);
	element_set(ss->a, asum);
	element_set(ss->b, bsum);
	element_set(ss->snark, snark);
	darray_append(hole, ss);
element_printf("snark %Zd: %B\n", counter, snark);
    }

    mpz_init(counter);
    element_init(g0, G);
    element_init(snark, G);
    element_init(asum, Zr);
    element_init(bsum, Zr);
    darray_init(hole);
    //set up multipliers
    for (i=0; i<s; i++) {
	element_init(a[i], Zr);
	element_init(b[i], Zr);
	element_init(m[i], G);
	element_random(a[i]);
	element_random(b[i]);
	element_pow_zn(g0, g, a[i]);
	element_pow_zn(m[i], h, b[i]);
	element_mul(m[i], m[i], g0);
    }

    element_random(asum);
    element_random(bsum);
    element_pow_zn(g0, g, asum);
    element_pow_zn(snark, h, bsum);
    element_mul(snark, snark, g0);

    record();
    for (;;) {
	int len = element_length_in_bytes(snark);
	unsigned char *buf = pbc_malloc(len);
	unsigned char hash = 0;

	element_to_bytes(buf, snark);
	for (i=0; i<len; i++) {
	    hash += buf[i];
	}
	i = hash % s;
	pbc_free(buf);

	element_mul(snark, snark, m[i]);
	element_add(asum, asum, a[i]);
	element_add(bsum, bsum, b[i]);

	for (i=0; i<hole->count; i++) {
	    snapshot_ptr ss = hole->item[i];
	    if (!element_cmp(snark, ss->snark)) {
		element_sub(bsum, bsum, ss->b);
		element_sub(asum, ss->a, asum);
		//answer is x such that x * bsum = asum
		//complications arise if gcd(bsum, r) > 1
		//which can happen if r is not prime
		if (!mpz_probab_prime_p(Zr->order, 10)) {
		    mpz_t za, zb, zd, zm;

		    mpz_init(za);
		    mpz_init(zb);
		    mpz_init(zd);
		    mpz_init(zm);

		    element_to_mpz(za, asum);
		    element_to_mpz(zb, bsum);
		    mpz_gcd(zd, zb, Zr->order);
		    mpz_divexact(zm, Zr->order, zd);
		    mpz_divexact(zb, zb, zd);
		    //if zd does not divide za there is no solution
		    mpz_divexact(za, za, zd);
		    mpz_invert(zb, zb, zm);
		    mpz_mul(zb, za, zb);
		    mpz_mod(zb, zb, zm);
		    do {
			element_pow_mpz(g0, g, zb);
			if (!element_cmp(g0, h)) {
			    element_set_mpz(x, zb);
			    break;
			}
			mpz_add(zb, zb, zm);
			mpz_sub_ui(zd, zd, 1);
		    } while (mpz_sgn(zd));
		    mpz_clear(zm);
		    mpz_clear(za);
		    mpz_clear(zb);
		    mpz_clear(zd);
		} else {
		    element_div(x, asum, bsum);
		}
		found = 1;
		break;
	    }
	}
	if (found) break;

	mpz_add_ui(counter, counter, 1);
	if (mpz_tstbit(counter, interval)) {
	    record();
	    interval++;
	}
    }

    for (i=0; i<s; i++) {
	element_clear(a[i]);
	element_clear(b[i]);
	element_clear(m[i]);
    }
    element_clear(g0);
    element_clear(snark);
    for (i=0; i<hole->count; i++) {
	snapshot_ptr ss = hole->item[i];
	element_clear(ss->a);
	element_clear(ss->b);
	element_clear(ss->snark);
	pbc_free(ss);
    }
    darray_clear(hole);
    element_clear(asum);
    element_clear(bsum);
    mpz_clear(counter);
}