curve.c

这是一个C的源代码

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>
#include "pbc_field.h"
#include "pbc_darray.h"
#include "pbc_poly.h"
#include "pbc_curve.h"
#include "pbc_memory.h"
#include "pbc_utils.h"
#include "pbc_random.h"

struct point_s {
    int inf_flag;
    element_t x;
    element_t y;
};
typedef struct point_s *point_ptr;
typedef struct point_s point_t[1];

struct curve_data_s {
    field_ptr field;
    element_t a, b;
    element_t gen;
    element_t gen_no_cofac;
    mpz_ptr cofac;
};
typedef struct curve_data_s curve_data_t[1];
typedef struct curve_data_s *curve_data_ptr;

static void curve_init(element_ptr e)
{
    curve_data_ptr cdp = e->field->data;
    e->data = pbc_malloc(sizeof(point_t));
    point_ptr p = e->data;
    element_init(p->x, cdp->field);
    element_init(p->y, cdp->field);
    p->inf_flag = 1;
}

static void curve_clear(element_ptr e)
{
    point_ptr p = e->data;
    element_clear(p->x);
    element_clear(p->y);
    pbc_free(e->data);
}

static int curve_is_valid_point(element_ptr e)
{
    element_t t0, t1;
    int result;
    curve_data_ptr cdp = e->field->data;
    point_ptr p = e->data;

    if (p->inf_flag) return 1;

    element_init(t0, cdp->field);
    element_init(t1, cdp->field);
    element_square(t0, p->x);
    element_add(t0, t0, cdp->a);
    element_mul(t0, t0, p->x);
    element_add(t0, t0, cdp->b);
    element_square(t1, p->y);
    result = !element_cmp(t0, t1);

    element_clear(t0);
    element_clear(t1);
    return result;
}

static void curve_invert(element_ptr c, element_ptr a)
{
    point_ptr r = c->data, p = a->data;

    if (p->inf_flag) {
	r->inf_flag = 1;
	return;
    }
    r->inf_flag = 0;
    element_set(r->x, p->x);
    element_neg(r->y, p->y);
}

static void curve_set(element_ptr c, element_ptr a)
{
    point_ptr r = c->data, p = a->data;
    if (p->inf_flag) {
	r->inf_flag = 1;
	return;
    }
    r->inf_flag = 0;
    element_set(r->x, p->x);
    element_set(r->y, p->y);
}

static inline void double_no_check(point_ptr r, point_ptr p, element_ptr a)
{
    element_t lambda, e0, e1;
    field_ptr f = r->x->field;

    element_init(lambda, f);
    element_init(e0, f);
    element_init(e1, f);

    //lambda = (3x^2 + a) / 2y
    element_square(lambda, p->x);
    element_mul_si(lambda, lambda, 3);
    element_add(lambda, lambda, a);

    element_double(e0, p->y);

    element_invert(e0, e0);
    element_mul(lambda, lambda, e0);
    //x1 = lambda^2 - 2x
    //element_add(e1, p->x, p->x);
    element_double(e1, p->x);
    element_square(e0, lambda);
    element_sub(e0, e0, e1);
    //y1 = (x - x1)lambda - y
    element_sub(e1, p->x, e0);
    element_mul(e1, e1, lambda);
    element_sub(e1, e1, p->y);

    element_set(r->x, e0);
    element_set(r->y, e1);
    r->inf_flag = 0;

    element_clear(lambda);
    element_clear(e0);
    element_clear(e1);
    return;
}

static void curve_double(element_ptr c, element_ptr a)
{
    curve_data_ptr cdp = a->field->data;
    point_ptr r = c->data, p = a->data;
    if (p->inf_flag) {
	r->inf_flag = 1;
	return;
    }
    if (element_is0(p->y)) {
	r->inf_flag = 1;
	return;
    }
    double_no_check(r, p, cdp->a);
}

static void curve_mul(element_ptr c, element_ptr a, element_ptr b)
{
    curve_data_ptr cdp = a->field->data;
    point_ptr r = c->data, p = a->data, q = b->data;

    if (p->inf_flag) {
	curve_set(c, b);
	return;
    }
    if (q->inf_flag) {
	curve_set(c, a);
	return;
    }
    if (!element_cmp(p->x, q->x)) {
	if (!element_cmp(p->y, q->y)) {
	    if (element_is0(p->y)) {
		r->inf_flag = 1;
		return;
	    } else {
		double_no_check(r, p, cdp->a);
		return;
	    }
	}
	//points are inverses of each other
	r->inf_flag = 1;
	return;
    } else {
	element_t lambda, e0, e1;

	element_init(lambda, cdp->field);
	element_init(e0, cdp->field);
	element_init(e1, cdp->field);

	//lambda = (y2-y1)/(x2-x1)
	element_sub(e0, q->x, p->x);
	element_invert(e0, e0);
	element_sub(lambda, q->y, p->y);
	element_mul(lambda, lambda, e0);
	//x3 = lambda^2 - x1 - x2
	element_square(e0, lambda);
	element_sub(e0, e0, p->x);
	element_sub(e0, e0, q->x);
	//y3 = (x1-x3)lambda - y1
	element_sub(e1, p->x, e0);
	element_mul(e1, e1, lambda);
	element_sub(e1, e1, p->y);

	element_set(r->x, e0);
	element_set(r->y, e1);
        r->inf_flag = 0;

	element_clear(lambda);
	element_clear(e0);
	element_clear(e1);
    }
}

static int curve_cmp(element_ptr a, element_ptr b)
{
    if (a == b) {
	return 0;
    } else {
	point_ptr p = a->data;
	point_ptr q = b->data;
	if (p->inf_flag) {
	    return q->inf_flag;
	}
	return element_cmp(p->x, q->x) || element_cmp(p->y, q->y);
    }
}

static void curve_set1(element_ptr x)
{
    point_ptr p = x->data;
    p->inf_flag = 1;
}

static int curve_is1(element_ptr x)
{
    point_ptr p = x->data;
    return p->inf_flag;
}

static void curve_random_no_cofac_solvefory(element_ptr a)
{
    //TODO: with 0.5 probability negate y-coord
    curve_data_ptr cdp = a->field->data;
    point_ptr p = a->data;
    element_t t;

    element_init(t, cdp->field);
    p->inf_flag = 0;
    do {
	element_random(p->x);
	element_square(t, p->x);
	element_add(t, t, cdp->a);
	element_mul(t, t, p->x);
	element_add(t, t, cdp->b);
    } while (!element_is_sqr(t));
    element_sqrt(p->y, t);
    element_clear(t);
}

static void curve_random_solvefory(element_ptr a)
{
    curve_data_ptr cdp = a->field->data;
    curve_random_no_cofac_solvefory(a);
    if (cdp->cofac) element_mul_mpz(a, a, cdp->cofac);
}

static void curve_random_pointmul(element_ptr a)
{
    curve_data_ptr cdp = a->field->data;
    mpz_t x;
    mpz_init(x);

    pbc_mpz_random(x, a->field->order);
    element_mul_mpz(a, cdp->gen, x);
    mpz_clear(x);
}

void field_curve_use_random_solvefory(field_ptr f)
{
    f->random = curve_random_solvefory;
}

void curve_set_gen_no_cofac(element_ptr a)
{
    curve_data_ptr cdp = a->field->data;
    element_set(a, cdp->gen_no_cofac);
}

static int curve_sign(element_ptr e)
{
    point_ptr p = e->data;
    if (p->inf_flag) return 0;
    return element_sign(p->y);
}

static void curve_from_hash(element_t a, void *data, int len)
{
    //TODO: don't find a hash by the 255th try = freeze!
    void *datacopy;
    element_t t, t1;
    point_ptr p = a->data;
    curve_data_ptr cdp = a->field->data;

    datacopy = pbc_malloc(len);
    memcpy(datacopy, data, len);

    element_init(t, cdp->field);
    element_init(t1, cdp->field);
    p->inf_flag = 0;
    for(;;) {
	element_from_hash(p->x, datacopy, len);
	element_square(t, p->x);
	element_add(t, t, cdp->a);
	element_mul(t, t, p->x);
	element_add(t, t, cdp->b);
	if (element_is_sqr(t)) break;
	((char *) datacopy)[0]++;
    }
    element_sqrt(p->y, t);
    if (element_sgn(p->y) < 0) element_neg(p->y, p->y);

    if (cdp->cofac) element_mul_mpz(a, a, cdp->cofac);

    element_clear(t);
    element_clear(t1);
    pbc_free(datacopy);
}

static size_t curve_out_str(FILE *stream, int base, element_ptr a)
{
    point_ptr p = a->data;
    size_t result, status;
    if (p->inf_flag) {
	if (EOF == fputc('O', stream)) return 0;
	return 1;
    }
    if (EOF == fputc('[', stream)) return 0;
    result = element_out_str(stream, base, p->x);
    if (!result) return 0;
    if (EOF == fputs(", ", stream)) return 0;
    status = element_out_str(stream, base, p->y);
    if (!status) return 0;
    if (EOF == fputc(']', stream)) return 0;
    return result + status + 4;
}

static int curve_snprint(char *s, size_t n, element_ptr a)
{
    point_ptr p = a->data;
    size_t result = 0, left;
    int status;

    void clip_sub(void)
    {
	result += status;
	left = result >= n ? 0 : n - result;
    }

    if (p->inf_flag) {
	status = snprintf(s, n, "O");
	if (status < 0) return status;
	return 1;
    }

    status = snprintf(s, n, "[");
    if (status < 0) return status;
    clip_sub();
    status = element_snprint(s + result, left, p->x);
    if (status < 0) return status;
    clip_sub();
    status = snprintf(s + result, left, ", ");
    if (status < 0) return status;
    clip_sub();
    status = element_snprint(s + result, left, p->y);
    if (status < 0) return status;
    clip_sub();
    status = snprintf(s + result, left, "]");
    if (status < 0) return status;
    return result + status;
}

static int curve_set_str(element_ptr e, char *s, int base)
{
    point_ptr p = e->data;
    char *cp = s;
    element_set0(e);
    while (*cp && isspace(*cp)) cp++;
    if (*cp == 'O') {
	return cp - s + 1;
    }
    p->inf_flag = 0;
    if (*cp != '[') return 0;