Merge "init attribute-based encryption"

1 files changed, 987 insertions, 0 deletions

diff --git a/moon-abe/pbc-0.5.14/ecc/curve.c b/moon-abe/pbc-0.5.14/ecc/curve.c
new file mode 100644
index 00000000..3bc1f020
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/ecc/curve.c
@@ -0,0 +1,987 @@
+#include <ctype.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdint.h> // for intptr_t
+#include <stdlib.h>
+#include <string.h>
+#include <gmp.h>
+#include "pbc_utils.h"
+#include "pbc_field.h"
+#include "pbc_multiz.h"
+#include "pbc_poly.h"
+#include "pbc_curve.h"
+#include "pbc_memory.h"
+#include "pbc_random.h"
+#include "misc/darray.h"
+
+// Per-field data.
+typedef struct {
+  field_ptr field; // The field where the curve is defined.
+  element_t a, b;  // The curve is E: Y^2 = X^3 + a X + b.
+  // cofac == NULL means we're using the whole group of points.
+  // otherwise we're working in the subgroup of order #E / cofac,
+  // where #E is the number of points in E.
+  mpz_ptr cofac;
+  // A generator of E.
+  element_t gen_no_cofac;
+  // A generator of the subgroup.
+  element_t gen;
+  // A non-NULL quotient_cmp means we are working with the quotient group of
+  // order #E / quotient_cmp, and the points are actually coset
+  // representatives. Thus for a comparison, we must multiply by quotient_cmp
+  // before comparing.
+  mpz_ptr quotient_cmp;
+} *curve_data_ptr;
+
+// Per-element data. Elements of this group are points on the elliptic curve.
+typedef struct {
+  int inf_flag;    // inf_flag == 1 means O, the point at infinity.
+  element_t x, y;  // Otherwise we have the finite point (x, y).
+} *point_ptr;
+
+static void curve_init(element_ptr e) {
+  curve_data_ptr cdp = e->field->data;
+  point_ptr p = e->data = pbc_malloc(sizeof(*p));
+  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);
+  }
+}
+
+//compute c_i=a_i+a_i at one time.
+static void multi_double(element_ptr c[], element_ptr a[], int n) {
+  int i;
+  element_t* table = pbc_malloc(sizeof(element_t)*n);  //a big problem?
+  element_t e0, e1, e2;
+  point_ptr q, r;
+  curve_data_ptr cdp = a[0]->field->data;
+
+  q=a[0]->data;
+  element_init(e0,q->y->field);
+  element_init(e1,q->y->field);
+  element_init(e2,q->y->field);
+
+  for(i=0; i<n; i++){
+    q=a[i]->data; r=c[i]->data;
+    element_init(table[i],q->y->field);
+
+    if (q->inf_flag) {
+      r->inf_flag = 1;
+      continue;
+    }
+    if (element_is0(q->y)) {
+      r->inf_flag = 1;
+      continue;
+    }
+  }
+  //to compute 1/2y multi. see Cohen's GTM139 Algorithm 10.3.4
+  for(i=0; i<n; i++){
+    q=a[i]->data;
+    element_double(table[i],q->y);
+    if(i>0) element_mul(table[i],table[i],table[i-1]);
+  }
+  element_invert(e2,table[n-1]); //ONLY ONE inv is required now.
+  for(i=n-1; i>0; i--){
+    q=a[i]->data;
+    element_mul(table[i],table[i-1],e2);
+    element_mul(e2,e2,q->y);
+    element_double(e2,e2); //e2=e2*2y_j
+  }
+  element_set(table[0],e2); //e2 no longer used.
+
+  for(i=0; i<n; i++){
+    q=a[i]->data;
+    r=c[i]->data;
+    if(r->inf_flag) continue;
+
+    //e2=lambda = (3x^2 + a) / 2y
+    element_square(e2, q->x);
+    element_mul_si(e2, e2, 3);
+    element_add(e2, e2, cdp->a);
+
+    element_mul(e2, e2, table[i]); //Recall that table[i]=1/2y_i
+    //x1 = lambda^2 - 2x
+    element_double(e1, q->x);
+    element_square(e0, e2);
+    element_sub(e0, e0, e1);
+    //y1 = (x - x1)lambda - y
+    element_sub(e1, q->x, e0);
+    element_mul(e1, e1, e2);
+    element_sub(e1, e1, q->y);
+    element_set(r->x, e0);
+    element_set(r->y, e1);
+    r->inf_flag = 0;
+  }
+
+  element_clear(e0);
+  element_clear(e1);
+  element_clear(e2);
+  for(i=0; i<n; i++){
+    element_clear(table[i]);
+  }
+  pbc_free(table);
+}
+
+//compute c_i=a_i+b_i at one time.
+static void multi_add(element_ptr c[], element_ptr a[], element_ptr b[], int n){
+  int i;
+  element_t* table = pbc_malloc(sizeof(element_t)*n);  //a big problem?
+  point_ptr p, q, r;
+  element_t e0, e1, e2;
+  curve_data_ptr cdp = a[0]->field->data;
+
+  p = a[0]->data;
+  q = b[0]->data;
+  element_init(e0, p->x->field);
+  element_init(e1, p->x->field);
+  element_init(e2, p->x->field);
+
+  element_init(table[0], p->x->field);
+  element_sub(table[0], q->x, p->x);
+  for(i=1; i<n; i++){
+    p = a[i]->data;
+    q = b[i]->data;
+    element_init(table[i], p->x->field);
+    element_sub(table[i], q->x, p->x);
+    element_mul(table[i], table[i], table[i-1]);
+  }
+  element_invert(e2, table[n-1]);
+  for(i=n-1; i>0; i--){
+    p = a[i]->data;
+    q = b[i]->data;
+    element_mul(table[i], table[i-1], e2);
+    element_sub(e1, q->x, p->x);
+    element_mul(e2,e2,e1); //e2=e2*(x2_j-x1_j)
+  }
+  element_set(table[0],e2); //e2 no longer used.
+
+  for(i=0; i<n; i++){
+    p = a[i]->data;
+    q = b[i]->data;
+    r = c[i]->data;
+    if (p->inf_flag) {
+      curve_set(c[i], b[i]);
+      continue;
+    }
+    if (q->inf_flag) {
+      curve_set(c[i], a[i]);
+      continue;
+    }
+    if (!element_cmp(p->x, q->x)) { //a[i]=b[i]
+      if (!element_cmp(p->y, q->y)) {
+        if (element_is0(p->y)) {
+          r->inf_flag = 1;
+          continue;
+        } else {
+          double_no_check(r, p, cdp->a);
+          continue;
+        }
+      }
+      //points are inverses of each other
+      r->inf_flag = 1;
+      continue;
+    } else {
+      //lambda = (y2-y1)/(x2-x1)
+      element_sub(e2, q->y, p->y);
+      element_mul(e2, e2, table[i]);
+      //x3 = lambda^2 - x1 - x2
+      element_square(e0, e2);
+      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, e2);
+      element_sub(e1, e1, p->y);
+      element_set(r->x, e0);
+      element_set(r->y, e1);
+      r->inf_flag = 0;
+    }
+  }
+  element_clear(e0);
+  element_clear(e1);
+  element_clear(e2);
+  for(i=0; i<n; i++){
+    element_clear(table[i]);
+  }
+  pbc_free(table);
+}
+
+
+static inline int point_cmp(point_ptr p, point_ptr q) {
+  if (p->inf_flag || q->inf_flag) {
+    return !(p->inf_flag && q->inf_flag);
+  }
+  return element_cmp(p->x, q->x) || element_cmp(p->y, q->y);
+}
+
+static int curve_cmp(element_ptr a, element_ptr b) {
+  if (a == b) {
+    return 0;
+  } else {
+    // If we're working with a quotient group we must account for different
+    // representatives of the same coset.
+    curve_data_ptr cdp = a->field->data;
+    if (cdp->quotient_cmp) {
+      element_t e;
+      element_init_same_as(e, a);
+      element_div(e, a, b);
+      element_pow_mpz(e, e, cdp->quotient_cmp);
+      int result = !element_is1(e);
+      element_clear(e);
+      return result;
+    }
+    return point_cmp(a->data, b->data);
+  }
+}
+
+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) {
+  element_t t, t1;
+  point_ptr p = a->data;
+  curve_data_ptr cdp = a->field->data;
+
+  element_init(t, cdp->field);
+  element_init(t1, cdp->field);
+  p->inf_flag = 0;
+  element_from_hash(p->x, data, len);
+  for(;;) {
+    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;
+    // Compute x <- x^2 + 1 and try again.
+    element_square(p->x, p->x);
+    element_set1(t);
+    element_add(p->x, p->x, t);
+  }
+  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);
+}
+
+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;
+
+  #define clip_sub() {                   \
+    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;
+  #undef clip_sub
+}
+
+static void curve_set_multiz(element_ptr a, multiz m) {
+  if (multiz_is_z(m)) {
+    if (multiz_is0(m)) {
+      element_set0(a);
+      return;
+    }
+    pbc_warn("bad multiz");
+    return;
+  } else {
+    if (multiz_count(m) < 2) {
+      pbc_warn("multiz has too few coefficients");
+      return;
+    }
+    point_ptr p = a->data;
+    p->inf_flag = 0;
+    element_set_multiz(p->x, multiz_at(m, 0));
+    element_set_multiz(p->y, multiz_at(m, 1));
+  }
+}
+
+static int curve_set_str(element_ptr e, const char *s, int base) {
+  point_ptr p = e->data;
+  const 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;
+  cp++;
+  cp += element_set_str(p->x, cp, base);
+  while (*cp && isspace(*cp)) cp++;
+  if (*cp != ',') return 0;
+  cp++;
+  cp += element_set_str(p->y, cp, base);
+  if (*cp != ']') return 0;
+
+  if (!curve_is_valid_point(e)) {
+    element_set0(e);
+    return 0;
+  }
+  return cp - s + 1;
+}
+
+static void field_clear_curve(field_t f) {
+  curve_data_ptr cdp;
+  cdp = f->data;
+  element_clear(cdp->gen);
+  element_clear(cdp->gen_no_cofac);
+  if (cdp->cofac) {
+    mpz_clear(cdp->cofac);
+    pbc_free(cdp->cofac);
+  }
+  if (cdp->quotient_cmp) {
+    mpz_clear(cdp->quotient_cmp);
+    pbc_free(cdp->quotient_cmp);
+  }
+  element_clear(cdp->a);
+  element_clear(cdp->b);
+  pbc_free(cdp);
+}
+
+static int curve_length_in_bytes(element_ptr x) {
+  point_ptr p = x->data;
+  return element_length_in_bytes(p->x) + element_length_in_bytes(p->y);
+}
+
+static int curve_to_bytes(unsigned char *data, element_t e) {
+  point_ptr P = e->data;
+  int len;
+  len = element_to_bytes(data, P->x);
+  len += element_to_bytes(data + len, P->y);
+  return len;
+}
+
+static int curve_from_bytes(element_t e, unsigned char *data) {
+  point_ptr P = e->data;
+  int len;
+
+  P->inf_flag = 0;
+  len = element_from_bytes(P->x, data);
+  len += element_from_bytes(P->y, data + len);
+  //if point does not lie on curve, set it to O
+  if (!curve_is_valid_point(e)) {
+    element_set0(e);
+  }
+  return len;
+}
+
+static void curve_out_info(FILE *out, field_t f) {
+  int len;
+  fprintf(out, "elliptic curve");
+  if ((len = f->fixed_length_in_bytes)) {
+    fprintf(out, ", bits per coord = %d", len * 8 / 2);
+  } else {
+    fprintf(out, "variable-length");
+  }
+}
+
+static int odd_curve_is_sqr(element_ptr e) {
+  UNUSED_VAR(e);
+  return 1;
+}
+
+//TODO: untested
+static int even_curve_is_sqr(element_ptr e) {
+  mpz_t z;
+  element_t e1;
+  int result;
+
+  mpz_init(z);
+  element_init(e1, e->field);
+  mpz_sub_ui(z, e->field->order, 1);
+  mpz_fdiv_q_2exp(z, z, 1);
+  element_pow_mpz(e1, e, z);
+  result = element_is1(e1);
+
+  mpz_clear(z);
+  element_clear(e1);
+  return result;
+}
+
+static int curve_item_count(element_ptr e) {
+  if (element_is0(e)) {
+    return 0;
+  }
+  return 2;
+}
+
+static element_ptr curve_item(element_ptr e, int i) {
+  if (element_is0(e)) return NULL;
+  point_ptr P = e->data;
+  switch(i) {
+    case 0:
+      return P->x;
+    case 1:
+      return P->y;
+    default:
+      return NULL;
+  }
+}
+
+static element_ptr curve_get_x(element_ptr e) {
+  point_ptr P = e->data;
+  return P->x;
+}
+
+static element_ptr curve_get_y(element_ptr e) {
+  point_ptr P = e->data;
+  return P->y;
+}
+
+void field_init_curve_ab(field_ptr f, element_ptr a, element_ptr b, mpz_t order, mpz_t cofac) {
+  /*
+  if (element_is0(a)) {
+    c->double_nocheck = cc_double_no_check_ais0;
+  } else {
+    c->double_nocheck = cc_double_no_check;
+  }
+  */
+  curve_data_ptr cdp;
+  field_init(f);
+  mpz_set(f->order, order);
+  cdp = f->data = pbc_malloc(sizeof(*cdp));
+  cdp->field = a->field;
+  element_init(cdp->a, cdp->field);
+  element_init(cdp->b, cdp->field);
+  element_set(cdp->a, a);
+  element_set(cdp->b, b);
+
+  f->init = curve_init;
+  f->clear = curve_clear;
+  f->neg = f->invert = curve_invert;
+  f->square = f->doub = curve_double;
+  f->multi_doub = multi_double;
+  f->add = f->mul = curve_mul;
+  f->multi_add = multi_add;
+  f->mul_mpz = element_pow_mpz;
+  f->cmp = curve_cmp;
+  f->set0 = f->set1 = curve_set1;
+  f->is0 = f->is1 = curve_is1;
+  f->sign = curve_sign;
+  f->set = curve_set;
+  f->random = curve_random_pointmul;
+  //f->random = curve_random_solvefory;
+  f->from_hash = curve_from_hash;
+  f->out_str = curve_out_str;
+  f->snprint = curve_snprint;
+  f->set_multiz = curve_set_multiz;
+  f->set_str = curve_set_str;
+  f->field_clear = field_clear_curve;
+  if (cdp->field->fixed_length_in_bytes < 0) {
+    f->length_in_bytes = curve_length_in_bytes;
+  } else {
+    f->fixed_length_in_bytes = 2 * cdp->field->fixed_length_in_bytes;
+  }
+  f->to_bytes = curve_to_bytes;
+  f->from_bytes = curve_from_bytes;
+  f->out_info = curve_out_info;
+  f->item_count = curve_item_count;
+  f->item = curve_item;
+  f->get_x = curve_get_x;
+  f->get_y = curve_get_y;
+
+  if (mpz_odd_p(order)) {
+    f->is_sqr = odd_curve_is_sqr;
+  } else {
+    f->is_sqr = even_curve_is_sqr;
+  }
+
+  element_init(cdp->gen_no_cofac, f);
+  element_init(cdp->gen, f);
+  curve_random_no_cofac_solvefory(cdp->gen_no_cofac);
+  if (cofac) {
+    cdp->cofac = pbc_malloc(sizeof(mpz_t));
+    mpz_init(cdp->cofac);
+    mpz_set(cdp->cofac, cofac);
+    element_mul_mpz(cdp->gen, cdp->gen_no_cofac, cofac);
+  } else{
+    cdp->cofac = NULL;
+    element_set(cdp->gen, cdp->gen_no_cofac);
+  }
+  cdp->quotient_cmp = NULL;
+}
+
+// Requires e to be a point on an elliptic curve.
+int element_to_bytes_compressed(unsigned char *data, element_ptr e) {
+  point_ptr P = e->data;
+  int len;
+  len = element_to_bytes(data, P->x);
+  if (element_sign(P->y) > 0) {
+    data[len] = 1;
+  } else {
+    data[len] = 0;
+  }
+  len++;
+  return len;
+}
+
+// Computes a point on the elliptic curve Y^2 = X^3 + a X + b given its
+// x-coordinate.
+// Requires a solution to exist.
+static void point_from_x(point_ptr p, element_t x, element_t a, element_t b) {
+  element_t t;
+
+  element_init(t, x->field);
+  p->inf_flag = 0;
+  element_square(t, x);
+  element_add(t, t, a);
+  element_mul(t, t, x);
+  element_add(t, t, b);
+  element_sqrt(p->y, t);
+  element_set(p->x, x);
+
+  element_clear(t);
+}
+
+void curve_from_x(element_ptr e, element_t x) {
+  curve_data_ptr cdp = e->field->data;
+  point_from_x(e->data, x, cdp->a, cdp->b);
+}
+
+// Requires e to be a point on an elliptic curve.
+int element_from_bytes_compressed(element_ptr e, unsigned char *data) {
+  curve_data_ptr cdp = e->field->data;
+  point_ptr P = e->data;
+  int len;
+  len = element_from_bytes(P->x, data);
+  point_from_x(P, P->x, cdp->a, cdp->b);
+
+  if (data[len]) {
+    if (element_sign(P->y) < 0) element_neg(P->y, P->y);
+  } else if (element_sign(P->y) > 0) {
+    element_neg(P->y, P->y);
+  }
+  len++;
+  return len;
+}
+
+int element_length_in_bytes_compressed(element_ptr e) {
+  point_ptr P = e->data;
+  return element_length_in_bytes(P->x) + 1;
+}
+
+// Requires e to be a point on an elliptic curve.
+int element_to_bytes_x_only(unsigned char *data, element_ptr e) {
+  point_ptr P = e->data;
+  int len;
+  len = element_to_bytes(data, P->x);
+  return len;
+}
+
+// Requires e to be a point on an elliptic curve.
+int element_from_bytes_x_only(element_ptr e, unsigned char *data) {
+  curve_data_ptr cdp = e->field->data;
+  point_ptr P = e->data;
+  int len;
+  len = element_from_bytes(P->x, data);
+  point_from_x(P, P->x, cdp->a, cdp->b);
+  return len;
+}
+
+int element_length_in_bytes_x_only(element_ptr e) {
+  point_ptr P = e->data;
+  return element_length_in_bytes(P->x);
+}
+
+inline element_ptr curve_x_coord(element_t e) {
+  return ((point_ptr) e->data)->x;
+}
+
+inline element_ptr curve_y_coord(element_t e) {
+  return ((point_ptr) e->data)->y;
+}
+
+inline element_ptr curve_a_coeff(element_t e) {
+  return ((curve_data_ptr) e->field->data)->a;
+}
+
+inline element_ptr curve_b_coeff(element_t e) {
+  return ((curve_data_ptr) e->field->data)->b;
+}
+
+inline element_ptr curve_field_a_coeff(field_t f) {
+  return ((curve_data_ptr) f->data)->a;
+}
+
+inline element_ptr curve_field_b_coeff(field_t f) {
+  return ((curve_data_ptr) f->data)->b;
+}
+
+void field_init_curve_ab_map(field_t cnew, field_t c,
+    fieldmap map, field_ptr mapdest,
+    mpz_t ordernew, mpz_t cofacnew) {
+  element_t a, b;
+  curve_data_ptr cdp = c->data;
+
+  element_init(a, mapdest);
+  element_init(b, mapdest);
+
+  map(a, cdp->a);
+  map(b, cdp->b);
+
+  field_init_curve_ab(cnew, a, b, ordernew, cofacnew);
+  element_clear(a);
+  element_clear(b);
+}
+
+// Existing points are invalidated as this mangles c.
+void field_reinit_curve_twist(field_ptr c) {
+  curve_data_ptr cdp = c->data;
+  element_ptr nqr = field_get_nqr(cdp->field);
+  element_mul(cdp->a, cdp->a, nqr);
+  element_mul(cdp->a, cdp->a, nqr);
+  element_mul(cdp->b, cdp->b, nqr);
+  element_mul(cdp->b, cdp->b, nqr);
+  element_mul(cdp->b, cdp->b, nqr);
+
+  // Recompute generators.
+  curve_random_no_cofac_solvefory(cdp->gen_no_cofac);
+  if (cdp->cofac) {
+    element_mul_mpz(cdp->gen, cdp->gen_no_cofac, cdp->cofac);
+  } else{
+    element_set(cdp->gen, cdp->gen_no_cofac);
+  }
+}
+
+// I could generalize this for all fields, but is there any point?
+void field_curve_set_quotient_cmp(field_ptr c, mpz_t quotient_cmp) {
+  curve_data_ptr cdp = c->data;
+  cdp->quotient_cmp = pbc_malloc(sizeof(mpz_t));
+  mpz_init(cdp->quotient_cmp);
+  mpz_set(cdp->quotient_cmp, quotient_cmp);
+}
+
+// Requires j != 0, 1728.
+void field_init_curve_j(field_ptr f, element_ptr j, mpz_t order, mpz_t cofac) {
+  element_t a, b;
+  element_init(a, j->field);
+  element_init(b, j->field);
+
+  element_set_si(a, 1728);
+  element_sub(a, a, j);
+  element_invert(a, a);
+  element_mul(a, a, j);
+
+  //b = 2 j / (1728 - j)
+  element_add(b, a, a);
+  //a = 3 j / (1728 - j)
+  element_add(a, a, b);
+  field_init_curve_ab(f, a, b, order, cofac);
+
+  element_clear(a);
+  element_clear(b);
+}
+
+void field_init_curve_b(field_ptr f, element_ptr b, mpz_t order, mpz_t cofac) {
+  element_t a;
+  element_init(a, b->field);
+  field_init_curve_ab(f, a, b, order, cofac);
+
+  element_clear(a);
+}
+
+// Compute trace of Frobenius at q^n given trace at q.
+// See p.105 of Blake, Seroussi and Smart.
+void pbc_mpz_trace_n(mpz_t res, mpz_t q, mpz_t trace, int n) {
+  int i;
+  mpz_t c0, c1, c2;
+  mpz_t t0;
+
+  mpz_init(c0);
+  mpz_init(c1);
+  mpz_init(c2);
+  mpz_init(t0);
+  mpz_set_ui(c2, 2);
+  mpz_set(c1, trace);
+  for (i=2; i<=n; i++) {
+    mpz_mul(c0, trace, c1);
+    mpz_mul(t0, q, c2);
+    mpz_sub(c0, c0, t0);
+    mpz_set(c2, c1);
+    mpz_set(c1, c0);
+  }
+  mpz_set(res, c1);
+  mpz_clear(t0);
+  mpz_clear(c2);
+  mpz_clear(c1);
+  mpz_clear(c0);
+}
+
+// Given q, t such that #E(F_q) = q - t + 1, compute #E(F_q^k).
+void pbc_mpz_curve_order_extn(mpz_t res, mpz_t q, mpz_t t, int k) {
+  mpz_t z;
+  mpz_t tk;
+  mpz_init(z);
+  mpz_init(tk);
+  mpz_pow_ui(z, q, k);
+  mpz_add_ui(z, z, 1);
+  pbc_mpz_trace_n(tk, q, t, k);
+  mpz_sub(z, z, tk);
+  mpz_set(res, z);
+  mpz_clear(z);
+  mpz_clear(tk);
+}
+
+void curve_set_si(element_t R, long int x, long int y) {
+  point_ptr p = R->data;
+  element_set_si(p->x, x);
+  element_set_si(p->y, y);
+  p->inf_flag = 0;
+}