diff options
Diffstat (limited to 'moon-abe/pbc-0.5.14/include')
25 files changed, 1750 insertions, 0 deletions
diff --git a/moon-abe/pbc-0.5.14/include/pbc.h b/moon-abe/pbc-0.5.14/include/pbc.h new file mode 100644 index 00000000..a963719b --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc.h @@ -0,0 +1,34 @@ +#ifndef __PBC_H__ +#define __PBC_H__ + +#include <stdarg.h> +#include <stdio.h> +#include <stdint.h> // for intptr_t +#include <stdlib.h> +#include <gmp.h> + +#if defined (__cplusplus) +extern "C" { +#endif + +#include "pbc_utils.h" +#include "pbc_field.h" +#include "pbc_param.h" +#include "pbc_pairing.h" +#include "pbc_curve.h" +#include "pbc_mnt.h" +#include "pbc_a1_param.h" +#include "pbc_a_param.h" +#include "pbc_d_param.h" +#include "pbc_e_param.h" +#include "pbc_f_param.h" +#include "pbc_g_param.h" +#include "pbc_i_param.h" +#include "pbc_random.h" +#include "pbc_memory.h" + +#if defined (__cplusplus) +} // extern "C" +#endif + +#endif //__PBC_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_a1_param.h b/moon-abe/pbc-0.5.14/include/pbc_a1_param.h new file mode 100644 index 00000000..74dd9b1d --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_a1_param.h @@ -0,0 +1,25 @@ +// requires +// * gmp.h +// * param.h +#ifndef __PBC_A1_PARAM_H__ +#define __PBC_A1_PARAM_H__ + +struct symtab_s; +int pbc_param_init_a1(pbc_param_ptr par, struct symtab_s *tab); + +/*@manual a1param +Generate type A1 pairing parameters and store them in 'p'. The group order +will be 'n'. The order of the base field is a few bits longer. To be secure, +generic discrete log algorithms must be infeasible in groups of order 'n', and +finite field discrete log algorithms must be infeasible in finite fields of +order roughly 'n'^2^. Additionally, 'n' should be hard to factorize. + +For example: 'n' a product of two primes, each at least 512 bits. + +The file `param/a1.param` contains sample parameters for a +type A1 pairing, but it is only for benchmarking: it is useless without +the factorization of +n+, the order of the group. +*/ +void pbc_param_init_a1_gen(pbc_param_t param, mpz_t n); + +#endif //__PBC_A1_PARAM_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_a_param.h b/moon-abe/pbc-0.5.14/include/pbc_a_param.h new file mode 100644 index 00000000..64d70468 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_a_param.h @@ -0,0 +1,25 @@ +// Type A pairing parameters. + +// Requires: +// * param.h +#ifndef __PBC_A_PARAM_H__ +#define __PBC_A_PARAM_H__ + +struct symtab_s; +int pbc_param_init_a(pbc_param_ptr par, struct symtab_s *tab); + +/*@manual aparam +Generate type A pairing parameters and store them in 'p', +where the group order r is 'rbits' long, and the order of the base field q +is 'qbits' long. Elements take 'qbits' to represent. + +To be secure, generic discrete log algorithms must be infeasible in groups of +order r, and finite field discrete log algorithms must be infeasible in finite +fields of order q^2, e.g. 'rbits' = 160, 'qbits' = 512. + +The file `param/a.param` contains parameters for a type A pairing suitable for +cryptographic use. +*/ +void pbc_param_init_a_gen(pbc_param_ptr par, int rbits, int qbits); + +#endif //__PBC_A_PARAM_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_curve.h b/moon-abe/pbc-0.5.14/include/pbc_curve.h new file mode 100644 index 00000000..9a86903d --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_curve.h @@ -0,0 +1,79 @@ +// A subgroup of the group of points on an elliptic curve. +// Also used to represent quotient groups. +// +// We use the field_t structure even though E(K) is a group. Addition and +// multiplication both refer to the group operation. + +// Requires: +// * stdio.h +// * gmp.h +// * field.h +#ifndef __PBC_CURVE_H__ +#define __PBC_CURVE_H__ + +// Some initialization functions take an order parameter. This is meant to +// be the order of the subgroup, but might actually be the order of the twist. +// Certain routines initialize a curve, test a random point to see if it has +// the correct order, and if not, immediately twist the curve so that it does. +// TODO: Move such code into curve.c, so 'order' is always accurate. + +// If cofac != NULL, then the field_t represents the subgroup of +// order = #E(K) / cofac. +// +// If not, and order = #E(K) then the field_t represents the entire E(K). +// +// Otherwise, if order is a factor of #E(K), then the field_t represents +// the quotient group of that order, namely E(K)/(#E(K)/order). No attempt is +// made to standardize the coset representative. This mode is useful for the +// Tate pairing (see thesis), where any coset representative of G2 suffices +// during the pairing computation. + +// Initialize a subgroup of points on the curve Y^2 = X^3 + b. +void field_init_curve_b(field_ptr f, element_ptr b, mpz_t order, mpz_t cofac); + +// Initialize a subgroup of points on the curve with the given j-invariant. +void field_init_curve_j(field_t f, element_ptr j, mpz_t order, mpz_t cofac); + +// Initialize a subgroup of points on the curve Y^2 = X^3 + a X + b. +void field_init_curve_ab(field_ptr f, element_ptr a, element_ptr b, mpz_t order, mpz_t cofac); + +// Reinitialize as the subgroup of points on the twist curve. +// Requires j-invariant of the original curve != 0, 1728. +// Mangles f, thus existing points of f become invalid. +// TODO: Refactor so we can remove this from the interface. +void field_reinit_curve_twist(field_t f); + +// Compute trace of Frobenius at q^n given trace at q. +void pbc_mpz_trace_n(mpz_t res, mpz_t q, mpz_t trace, int n); + +// 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); + +void field_init_curve_with_map(field_ptr cnew, field_ptr c, + field_ptr dstfield, fieldmap map); + +void field_init_curve_ab_map(field_t cnew, field_t c, + fieldmap map, field_ptr mapdest, + mpz_t ordernew, mpz_t cofacnew); + +void field_curve_use_random_solvefory(field_ptr f); + +void field_curve_set_quotient_cmp(field_ptr c, mpz_t quotient_cmp); + +#pragma GCC visibility push(hidden) +// Internal: + +element_ptr curve_x_coord(element_t e); +element_ptr curve_y_coord(element_t e); +element_ptr curve_a_coeff(element_t e); +element_ptr curve_b_coeff(element_t e); +element_ptr curve_field_a_coeff(field_t f); +element_ptr curve_field_b_coeff(field_t f); + +void curve_from_x(element_ptr e, element_t x); +void curve_set_si(element_t R, long int x, long int y); +void curve_set_gen_no_cofac(element_ptr a); + +#pragma GCC visibility pop + +#endif //__PBC_CURVE_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_d_param.h b/moon-abe/pbc-0.5.14/include/pbc_d_param.h new file mode 100644 index 00000000..41fcfc30 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_d_param.h @@ -0,0 +1,40 @@ +// Type D pairings, aka MNT curves. + +// Requires: +// * mnt.h +// * param.h +#ifndef __PBC_D_PARAM_H__ +#define __PBC_D_PARAM_H__ + +struct symtab_s; +int pbc_param_init_d(pbc_param_ptr par, struct symtab_s *tab); + +/*@manual dparam +Type D curves are generated using the complex multiplication (CM) method. This +function sets 'p' to a type D pairing parameters from CM parameters 'cm'. +Other library calls search for appropriate CM parameters and the results +can be passed to this function. + +To be secure, generic discrete log algorithms must be infeasible in groups of +order r, and finite field discrete log algorithms must be infeasible in finite +fields of order q^6^. For usual CM parameters, r is a few bits smaller than q. + +Using type D pairings allows elements of group G1 to be quite short, typically +170-bits. Because of a certain trick, elements of group G2 need only be 3 times +longer, that is, about 510 bits rather than 6 times long. They are not quite +as short as type F pairings, but much faster. + +I sometimes refer to a type D curve as a triplet of numbers: the discriminant, +the number of bits in the prime q, and the number of bits in the prime r. The +`gen/listmnt` program prints these numbers. + +Among the bundled type D curve parameters are the curves 9563-201-181, +62003-159-158 and 496659-224-224 which have shortened names `param/d201.param`, +`param/d159.param` and `param/d225.param` respectively. + +See `gen/listmnt.c` and `gen/gendparam.c` for how to generate type D pairing +parameters. +*/ +void pbc_param_init_d_gen(pbc_param_ptr p, pbc_cm_ptr cm); + +#endif //__PBC_D_PARAM_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_e_param.h b/moon-abe/pbc-0.5.14/include/pbc_e_param.h new file mode 100644 index 00000000..e59ebe82 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_e_param.h @@ -0,0 +1,29 @@ +// Type E pairings. + +// Requires: +// * param.h +#ifndef __PBC_E_PARAM_H__ +#define __PBC_E_PARAM_H__ + +struct symtab_s; +int pbc_param_init_e(pbc_param_ptr par, struct symtab_s *tab); + +/*@manual eparam +Generate type E pairing parameters and store them in 'p', +where the group order r is 'rbits' long, and the order of the base field q +is 'qbits' long. To be secure, generic discrete log algorithms must +be infeasible in groups of order r, and finite field discrete log algorithms +must be infeasible in finite fields of order q, +e.g. 'rbits' = 160, 'qbits' = 1024. + +This pairing is just a curiosity: it can be implemented entirely in a field of +prime order, that is, only arithmetic modulo a prime is needed and there is +never a need to extend a field. + +If discrete log in field extensions are found to be substantially easier to +solve than previously thought, or discrete log can be solved in elliptic curves +as easily as they can be in finite fields, this pairing type may become useful. +*/ +void pbc_param_init_e_gen(pbc_param_t p, int rbits, int qbits); + +#endif //__PBC_E_PARAM_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_f_param.h b/moon-abe/pbc-0.5.14/include/pbc_f_param.h new file mode 100644 index 00000000..5c484a98 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_f_param.h @@ -0,0 +1,27 @@ +// Type F pairings. + +// Requires: +// * param.h +#ifndef __PBC_F_PARAM_H__ +#define __PBC_F_PARAM_H__ + +struct symtab_s; +int pbc_param_init_f(pbc_param_ptr par, struct symtab_s *tab); + +/*@manual fparam +Generate type F pairing parameters and store them in 'p'. +Both the group order r and the order of the base field q will be roughly +'bits'-bit numbers. +To be secure, generic discrete log algorithms must +be infeasible in groups of order r, and finite field discrete log algorithms +must be infeasible in finite fields of order q^12, e.g. 'bits' = 160. + +Type F should be used when the top priority is to minimize bandwidth (e.g. +short signatures). The current implementation makes them slow. + +If finite field discrete log algorithms improve further, type D pairings will +have to use larger fields, but type F can still remain short, up to a point. +*/ +void pbc_param_init_f_gen(pbc_param_t p, int bits); + +#endif //__PBC_F_PARAM_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_field.h b/moon-abe/pbc-0.5.14/include/pbc_field.h new file mode 100644 index 00000000..5bcb8c83 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_field.h @@ -0,0 +1,694 @@ +/* + * field_t: represents fields, rings and groups. + * element_t: represents an element of a field_t. + */ + +// Requires: +// * stdarg.h +// * stdio.h +// * gmp.h +// * utils.h +#ifndef __PBC_FIELD_H__ +#define __PBC_FIELD_H__ + +struct field_s; + +struct element_s { + struct field_s *field; + void *data; +}; +typedef struct element_s *element_ptr; +typedef struct element_s element_t[1]; + +struct element_pp_s { + struct field_s *field; + void *data; +}; +typedef struct element_pp_s element_pp_t[1]; +typedef struct element_pp_s *element_pp_ptr; + +void pbc_assert(int expr, char *msg, const char *func); +void pbc_assert_match2(element_ptr a, element_ptr b, const char *func); +void pbc_assert_match3(element_ptr a, element_ptr b, element_ptr c, + const char *func); + +struct multiz_s; +typedef struct multiz_s *multiz; + +struct pairing_s; +struct field_s { + void (*field_clear)(struct field_s *f); + void (*init)(element_ptr); + void (*clear)(element_ptr); + + void (*set_mpz)(element_ptr, mpz_ptr); + void (*set_multiz)(element_ptr, multiz); + void (*set)(element_ptr, element_ptr); + void (*set0)(element_ptr); + void (*set1)(element_ptr); + int (*set_str)(element_ptr e, const char *s, int base); + size_t(*out_str)(FILE *stream, int base, element_ptr); + void (*add)(element_ptr, element_ptr, element_ptr); + void (*sub)(element_ptr, element_ptr, element_ptr); + void (*mul)(element_ptr, element_ptr, element_ptr); + + int (*is_sqr)(element_ptr); + void (*sqrt)(element_ptr, element_ptr); + + // Defaults exist for these functions. + int (*item_count)(element_ptr); + element_ptr (*item)(element_ptr, int); + element_ptr (*get_x)(element_ptr); + element_ptr (*get_y)(element_ptr); + void (*set_si)(element_ptr, signed long int); + void (*add_ui)(element_ptr, element_ptr, unsigned long int); + void (*mul_mpz)(element_ptr, element_ptr, mpz_ptr); + void (*mul_si)(element_ptr, element_ptr, signed long int); + void (*div)(element_ptr, element_ptr, element_ptr); + void (*doub)(element_ptr, element_ptr); // Can't call it "double"! + void (*multi_doub)(element_ptr*, element_ptr*, int n); + void (*multi_add)(element_ptr*, element_ptr*, element_ptr*, int n); + void (*halve)(element_ptr, element_ptr); + void (*square)(element_ptr, element_ptr); + + void (*cubic) (element_ptr, element_ptr); + void (*pow_mpz)(element_ptr, element_ptr, mpz_ptr); + void (*invert)(element_ptr, element_ptr); + void (*neg)(element_ptr, element_ptr); + void (*random)(element_ptr); + void (*from_hash)(element_ptr, void *data, int len); + int (*is1)(element_ptr); + int (*is0)(element_ptr); + int (*sign)(element_ptr); // satisfies sign(x) = -sign(-x) + int (*cmp)(element_ptr, element_ptr); + int (*to_bytes)(unsigned char *data, element_ptr); + int (*from_bytes)(element_ptr, unsigned char *data); + int (*length_in_bytes)(element_ptr); + int fixed_length_in_bytes; // length of an element in bytes; -1 for variable + int (*snprint)(char *s, size_t n, element_ptr e); + void (*to_mpz)(mpz_ptr, element_ptr); + void (*out_info)(FILE *, struct field_s *); + void (*pp_init)(element_pp_t p, element_t in); + void (*pp_clear)(element_pp_t p); + void (*pp_pow)(element_t out, mpz_ptr power, element_pp_t p); + + struct pairing_s *pairing; + + mpz_t order; // 0 for infinite order + element_ptr nqr; // nonquadratic residue + + char *name; + void *data; +}; +typedef struct field_s *field_ptr; +typedef struct field_s field_t[1]; + +typedef void (*fieldmap) (element_t dst, element_t src); + +void field_out_info(FILE* out, field_ptr f); + +/*@manual internal +Initialize 'e' to be an element of the algebraic structure 'f' +and set it to be the zero element. +*/ +static inline void element_init(element_t e, field_ptr f) { + e->field = f; + f->init(e); +} + +element_ptr element_new(field_ptr f); +void element_free(element_ptr e); + +/*@manual einit +Initialize 'e' to be an element of the algebraic structure that 'e2' +lies in. +*/ +static inline void element_init_same_as(element_t e, element_t e2) { + element_init(e, e2->field); +} + +/*@manual einit +Free the space occupied by 'e'. Call this when +the variable 'e' is no longer needed. +*/ +static inline void element_clear(element_t e) { + e->field->clear(e); +} + +/*@manual eio +Output 'e' on 'stream' in base 'base'. The base must be between +2 and 36. +*/ +static inline size_t element_out_str(FILE * stream, int base, element_t e) { + return e->field->out_str(stream, base, e); +} + +/*@manual eio +*/ +int element_printf(const char *format, ...); + +/*@manual eio +*/ +int element_fprintf(FILE * stream, const char *format, ...); + +/*@manual eio +*/ +int element_snprintf(char *buf, size_t size, const char *fmt, ...); + +/*@manual eio +Same as printf family +except also has the 'B' conversion specifier for types +of *element_t*, and 'Y', 'Z' conversion specifiers for ++mpz_t+. For example if 'e' is of type ++element_t+ then + + element_printf("%B\n", e); + +will print the value of 'e' in a human-readable form on standard output. +*/ +int element_vsnprintf(char *buf, size_t size, const char *fmt, va_list ap); + +/*@manual eio +Convert an element to a human-friendly string. +Behaves as *snprintf* but only on one element at a time. +*/ +static inline int element_snprint(char *s, size_t n, element_t e) { + return e->field->snprint(s, n, e); +} + +static inline void element_set_multiz(element_t e, multiz m) { + e->field->set_multiz(e, m); +} + +/*@manual eio +Set the element 'e' from 's', a null-terminated C string in base 'base'. +Whitespace is ignored. Points have the form "['x,y']" or "'O'", +while polynomials have the form "['a0,...,an']". +Returns number of characters read (unlike GMP's mpz_set_str). +A return code of zero means PBC could not find a well-formed string +describing an element. +*/ +static inline int element_set_str(element_t e, const char *s, int base) { + return e->field->set_str(e, s, base); +} + +/*@manual eassign +Set 'e' to zero. +*/ +static inline void element_set0(element_t e) { + e->field->set0(e); +} + +/*@manual eassign +Set 'e' to one. +*/ +static inline void element_set1(element_t e) { + e->field->set1(e); +} + +/*@manual eassign +Set 'e' to 'i'. +*/ +static inline void element_set_si(element_t e, signed long int i) { + e->field->set_si(e, i); +} + +/*@manual eassign +Set 'e' to 'z'. +*/ +static inline void element_set_mpz(element_t e, mpz_t z) { + e->field->set_mpz(e, z); +} + +/*@manual eassign +Set 'e' to 'a'. +*/ +static inline void element_set(element_t e, element_t a) { + PBC_ASSERT_MATCH2(e, a); + e->field->set(e, a); +} + +static inline void element_add_ui(element_t n, element_t a, + unsigned long int b) { + n->field->add_ui(n, a, b); +} + +/*@manual econvert +Converts 'e' to a GMP integer 'z' +if such an operation makes sense +*/ +static inline void element_to_mpz(mpz_t z, element_t e) { + e->field->to_mpz(z, e); +} + +static inline long element_to_si(element_t e) { + mpz_t z; + mpz_init(z); + e->field->to_mpz(z, e); + long res = mpz_get_si(z); + mpz_clear(z); + return res; +} + +/*@manual econvert +Generate an element 'e' deterministically from +the 'len' bytes stored in the buffer 'data'. +*/ +static inline void element_from_hash(element_t e, void *data, int len) { + e->field->from_hash(e, data, len); +} + +/*@manual earith +Set 'n' to 'a' + 'b'. +*/ +static inline void element_add(element_t n, element_t a, element_t b) { + PBC_ASSERT_MATCH3(n, a, b); + n->field->add(n, a, b); +} + +/*@manual earith +Set 'n' to 'a' - 'b'. +*/ +static inline void element_sub(element_t n, element_t a, element_t b) { + PBC_ASSERT_MATCH3(n, a, b); + n->field->sub(n, a, b); +} + +/*@manual earith +Set 'n' = 'a' 'b'. +*/ +static inline void element_mul(element_t n, element_t a, element_t b) { + PBC_ASSERT_MATCH3(n, a, b); + n->field->mul(n, a, b); +} + +static inline void element_cubic(element_t n, element_t a) { + PBC_ASSERT_MATCH2(n, a); + n->field->cubic(n, a); +} + +/*@manual earith +*/ +static inline void element_mul_mpz(element_t n, element_t a, mpz_t z) { + PBC_ASSERT_MATCH2(n, a); + n->field->mul_mpz(n, a, z); +} + +/*@manual earith +Set 'n' = 'a' 'z', that is 'a' + 'a' + ... + 'a' where there are 'z' 'a'#'s#. +*/ +static inline void element_mul_si(element_t n, element_t a, + signed long int z) { + PBC_ASSERT_MATCH2(n, a); + n->field->mul_si(n, a, z); +} + +/*@manual earith +'z' must be an element of a integer mod ring (i.e. *Z*~n~ for some n). +Set 'c' = 'a' 'z', that is 'a' + 'a' + ... + 'a' +where there are 'z' 'a''s. +*/ +static inline void element_mul_zn(element_t c, element_t a, element_t z) { + mpz_t z0; + PBC_ASSERT_MATCH2(c, a); + //TODO: check z->field is Zn + mpz_init(z0); + element_to_mpz(z0, z); + element_mul_mpz(c, a, z0); + mpz_clear(z0); +} + +/*@manual earith +Set 'n' = 'a' / 'b'. +*/ +static inline void element_div(element_t n, element_t a, element_t b) { + PBC_ASSERT_MATCH3(n, a, b); + n->field->div(n, a, b); +} + +/*@manual earith +Set 'n' = 'a' + 'a'. +*/ +static inline void element_double(element_t n, element_t a) { + PBC_ASSERT_MATCH2(n, a); + n->field->doub(n, a); +} + +// Set n_i = a_i + a_i for all i at one time. +// Uses multi_doub(), which only elliptic curves have at the moment. +void element_multi_double(element_t n[], element_t a[], int m); + +// Set n_i =a_i + b_i for all i at one time. +// Uses multi_add(), which only elliptic curves have at the moment. +void element_multi_add(element_t n[], element_t a[],element_t b[], int m); + +/*@manual earith +Set 'n' = 'a/2' +*/ +static inline void element_halve(element_t n, element_t a) { + PBC_ASSERT_MATCH2(n, a); + n->field->halve(n, a); +} + +/*@manual earith +Set 'n' = 'a'^2^ +*/ +static inline void element_square(element_t n, element_t a) { + PBC_ASSERT_MATCH2(n, a); + n->field->square(n, a); +} + +/*@manual epow +Set 'x' = 'a'^'n'^, that is +'a' times 'a' times ... times 'a' where there are 'n' 'a'#'s#. +*/ +static inline void element_pow_mpz(element_t x, element_t a, mpz_t n) { + PBC_ASSERT_MATCH2(x, a); + x->field->pow_mpz(x, a, n); +} + +/*@manual epow +Set 'x' = 'a'^'n'^, where 'n' is an element of a ring *Z*~N~ +for some 'N' (typically the order of the algebraic structure 'x' lies in). +*/ +static inline void element_pow_zn(element_t x, element_t a, element_t n) { + mpz_t z; + PBC_ASSERT_MATCH2(x, a); + mpz_init(z); + element_to_mpz(z, n); + element_pow_mpz(x, a, z); + mpz_clear(z); +} + +/*@manual earith +Set 'n' = -'a'. +*/ +static inline void element_neg(element_t n, element_t a) { + PBC_ASSERT_MATCH2(n, a); + n->field->neg(n, a); +} + +/*@manual earith +Set 'n' to the inverse of 'a'. +*/ +static inline void element_invert(element_t n, element_t a) { + PBC_ASSERT_MATCH2(n, a); + n->field->invert(n, a); +} + +/*@manual erandom +If the 'e' lies in a finite algebraic structure, +assigns a uniformly random element to 'e'. +*/ +static inline void element_random(element_t e) { + e->field->random(e); +} + +/*@manual ecmp +Returns true if 'n' is 1. +*/ +static inline int element_is1(element_t n) { + return n->field->is1(n); +} + +/*@manual ecmp +Returns true if 'n' is 0. +*/ +static inline int element_is0(element_t n) { + return n->field->is0(n); +} + +/*@manual ecmp +Returns 0 if 'a' and 'b' are the same, nonzero otherwise. +*/ +static inline int element_cmp(element_t a, element_t b) { + PBC_ASSERT_MATCH2(a, b); + return a->field->cmp(a, b); +} + +/*@manual ecmp +Returns nonzero if 'a' is a perfect square (quadratic residue), +zero otherwise. +*/ +static inline int element_is_sqr(element_t a) { + return a->field->is_sqr(a); +} + +/*@manual ecmp +*/ +static inline int element_sgn(element_t a) { + return a->field->sign(a); +} + +/*@manual ecmp +If 'a' is zero, returns 0. For nozero 'a' the behaviour depends on +the algebraic structure, but has the property that +element_sgn('a') = -element_sgn(-'a') +and +element_sgn('a') = 0 implies 'a' = 0 with overwhelming probability. +*/ +static inline int element_sign(element_t a) { + return a->field->sign(a); +} + +static inline void element_sqrt(element_t a, element_t b) { + PBC_ASSERT_MATCH2(a, b); + a->field->sqrt(a, b); +} + +/*@manual etrade +Returns the length in bytes the element 'e' will take to represent +*/ +static inline int element_length_in_bytes(element_t e) { + if (e->field->fixed_length_in_bytes < 0) { + return e->field->length_in_bytes(e); + } else { + return e->field->fixed_length_in_bytes; + } +} + +/*@manual etrade +Converts 'e' to byte, writing the result in the buffer 'data'. +The number of bytes it will write can be determined from calling +*element_length_in_bytes()*. Returns number of bytes written. +*/ +static inline int element_to_bytes(unsigned char *data, element_t e) { + return e->field->to_bytes(data, e); +} + +/*@manual etrade +Reads 'e' from the buffer 'data', and returns the number of bytes read. +*/ +static inline int element_from_bytes(element_t e, unsigned char *data) { + return e->field->from_bytes(e, data); +} + +/*@manual epow +Sets 'x' = 'a1'^'n1'^ 'a2'^'n2'^, and is generally faster than +performing two separate exponentiations. +*/ +void element_pow2_mpz(element_t x, element_t a1, mpz_t n1, element_t a2, + mpz_t n2); +/*@manual epow +Also sets 'x' = 'a1'^'n1'^ 'a2'^'n2'^, +but 'n1', 'n2' must be elements of a ring *Z*~n~ for some integer n. +*/ +static inline void element_pow2_zn(element_t x, element_t a1, element_t n1, + element_t a2, element_t n2) { + mpz_t z1, z2; + mpz_init(z1); + mpz_init(z2); + element_to_mpz(z1, n1); + element_to_mpz(z2, n2); + element_pow2_mpz(x, a1, z1, a2, z2); + mpz_clear(z1); + mpz_clear(z2); +} + +/*@manual epow +Sets 'x' = 'a1'^'n1'^ 'a2'^'n2'^ 'a3'^'n3'^, +generally faster than performing three separate exponentiations. +*/ +void element_pow3_mpz(element_t x, element_t a1, mpz_t n1, + element_t a2, mpz_t n2, element_t a3, mpz_t n3); + +/*@manual epow +Also sets 'x' = 'a1'^'n1'^ 'a2'^'n2'^ 'a3'^'n3'^, +but 'n1', 'n2', 'n3' must be elements of a ring *Z*~n~ for some integer n. +*/ +static inline void element_pow3_zn(element_t x, element_t a1, element_t n1, + element_t a2, element_t n2, + element_t a3, element_t n3) { + mpz_t z1, z2, z3; + mpz_init(z1); + mpz_init(z2); + mpz_init(z3); + element_to_mpz(z1, n1); + element_to_mpz(z2, n2); + element_to_mpz(z3, n3); + element_pow3_mpz(x, a1, z1, a2, z2, a3, z3); + mpz_clear(z1); + mpz_clear(z2); + mpz_clear(z3); +} + +void field_clear(field_ptr f); + +element_ptr field_get_nqr(field_ptr f); +void field_set_nqr(field_ptr f, element_t nqr); +void field_gen_nqr(field_ptr f); + +void field_init(field_ptr f); + +static inline int mpz_is0(mpz_t z) { + return !mpz_sgn(z); + //return !mpz_cmp_ui(z, 0); +} + +/*@manual etrade +Assumes 'e' is a point on an elliptic curve. +Writes the x-coordinate of 'e' to the buffer 'data' +*/ +int element_to_bytes_x_only(unsigned char *data, element_t e); +/*@manual etrade +Assumes 'e' is a point on an elliptic curve. +Sets 'e' to a point with +x-coordinate represented by the buffer 'data'. This is not unique. +For each 'x'-coordinate, there exist two different points, at least +for the elliptic curves in PBC. (They are inverses of each other.) +*/ +int element_from_bytes_x_only(element_t e, unsigned char *data); +/*@manual etrade +Assumes 'e' is a point on an elliptic curve. +Returns the length in bytes needed to hold the x-coordinate of 'e'. +*/ +int element_length_in_bytes_x_only(element_t e); + +/*@manual etrade +If possible, outputs a compressed form of the element 'e' to +the buffer of bytes 'data'. +Currently only implemented for points on an elliptic curve. +*/ +int element_to_bytes_compressed(unsigned char *data, element_t e); + +/*@manual etrade +Sets element 'e' to the element in compressed form in the buffer of bytes +'data'. +Currently only implemented for points on an elliptic curve. +*/ +int element_from_bytes_compressed(element_t e, unsigned char *data); + +/*@manual etrade +Returns the number of bytes needed to hold 'e' in compressed form. +Currently only implemented for points on an elliptic curve. +*/ +int element_length_in_bytes_compressed(element_t e); + +/*@manual epow +Prepare to exponentiate an element 'in', and store preprocessing information +in 'p'. +*/ +static inline void element_pp_init(element_pp_t p, element_t in) { + p->field = in->field; + in->field->pp_init(p, in); +} + +/*@manual epow +Clear 'p'. Should be called after 'p' is no longer needed. +*/ +static inline void element_pp_clear(element_pp_t p) { + p->field->pp_clear(p); +} + +/*@manual epow +Raise 'in' to 'power' and store the result in 'out', where 'in' +is a previously preprocessed element, that is, the second argument +passed to a previous *element_pp_init* call. +*/ +static inline void element_pp_pow(element_t out, mpz_ptr power, + element_pp_t p) { + p->field->pp_pow(out, power, p); +} + +/*@manual epow +Same except 'power' is an element of *Z*~n~ for some integer n. +*/ +static inline void element_pp_pow_zn(element_t out, element_t power, + element_pp_t p) { + mpz_t z; + mpz_init(z); + element_to_mpz(z, power); + element_pp_pow(out, z, p); + mpz_clear(z); +} + +void pbc_mpz_out_raw_n(unsigned char *data, int n, mpz_t z); +void pbc_mpz_from_hash(mpz_t z, mpz_t limit, + unsigned char *data, unsigned int len); + +/*@manual etrade +For points, returns the number of coordinates. +For polynomials, returns the number of coefficients. +Otherwise returns zero. +*/ +static inline int element_item_count(element_t e) { + return e->field->item_count(e); +} + +/*@manual etrade +For points, returns 'n'#th# coordinate. +For polynomials, returns coefficient of 'x^n^'. +Otherwise returns NULL. +The element the return value points to may be modified. +*/ +static inline element_ptr element_item(element_t e, int i) { + // TODO: Document the following: + // For polynomials, never zero the leading coefficient, e.g. never write: + // element_set0(element_item(f, poly_degree(f))); + // Use poly_set_coeff0() to zero the leading coefficient. + return e->field->item(e, i); +} + +// Returns the field containing the items. +// Returns NULL if there are no items. +static inline field_ptr element_item_field(element_t e) { + if (!element_item_count(e)) return NULL; + return element_item(e, 0)->field; +} + +/*@manual etrade +Equivalent to `element_item(a, 0)`. +*/ +static inline element_ptr element_x(element_ptr a) { + return a->field->get_x(a); +} +/*@manual etrade +Equivalent to `element_item(a, 1)`. +*/ +static inline element_ptr element_y(element_ptr a) { + return a->field->get_y(a); +} + +/*@manual epow +Computes 'x' such that 'g^x^ = h' by brute force, where +'x' lies in a field where `element_set_mpz()` makes sense. +*/ +void element_dlog_brute_force(element_t x, element_t g, element_t h); + +/*@manual epow +Computes 'x' such that 'g^x^ = h' using Pollard rho method, where +'x' lies in a field where `element_set_mpz()` makes sense. +*/ +void element_dlog_pollard_rho(element_t x, element_t g, element_t h); + +// Trial division up to a given limit. If limit == NULL, then there is no limit. +// Call the callback for each factor found, abort and return 1 if the callback +// returns nonzero, otherwise return 0. +int pbc_trial_divide(int (*fun)(mpz_t factor, + unsigned int multiplicity, + void *scope_ptr), + void *scope_ptr, + mpz_t n, + mpz_ptr limit); + +#endif // __PBC_FIELD_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_fieldquadratic.h b/moon-abe/pbc-0.5.14/include/pbc_fieldquadratic.h new file mode 100644 index 00000000..5a2111b3 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_fieldquadratic.h @@ -0,0 +1,23 @@ +/* + * Quadratic field extensions. + */ + +//requires +// * field.h +#ifndef __PBC_FIELDQUADRATIC_H__ +#define __PBC_FIELDQUADRATIC_H__ + +// Initialize L as K[sqrt(a)], where a is a quadratic nonresidue of K. We +// automatically randomly generate a if necessary (see field_get_nqr() in +// field.c). +void field_init_quadratic(field_ptr L, field_ptr K); + +// Initialize L as K[i], where i = sqrt(-1). Faster than the generic version. +// Requires -1 to be a quadratic nonresidue in K. +void field_init_fi(field_ptr L, field_ptr K); + +// Naturally map an element from a field K to K[a]. +void element_field_to_quadratic(element_ptr out, element_ptr in); +void element_field_to_fi(element_ptr a, element_ptr b); + +#endif //__PBC_FIELDQUADRATIC_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_fp.h b/moon-abe/pbc-0.5.14/include/pbc_fp.h new file mode 100644 index 00000000..3410cee1 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_fp.h @@ -0,0 +1,26 @@ +/* There does not appear to be a succint name for rings of type Z/nZ. + * Sage calls it integer mod ring. + * NTL calls it ZZ_p. + * I'll call it fp, as it's the quickest to type. + * "zn" might be better since it can also handle composite numbers. + */ +// Requires: +// * field.h +// * gmp.h +#ifndef __PBC_FP_H__ +#define __PBC_FP_H__ + +void field_init_naive_fp(field_ptr f, mpz_t prime); +void field_init_tiny_fp(field_ptr f, mpz_t prime); +void field_init_fast_fp(field_ptr f, mpz_t prime); +void field_init_faster_fp(field_ptr f, mpz_t prime); +void field_init_mont_fp(field_ptr f, mpz_t prime); + +void pbc_tweak_use_fp(char *s); + +void element_tonelli(element_ptr x, element_ptr a); + +void field_init_fp(field_ptr f, mpz_t prime); + +int pbc_mpz_set_str(mpz_t z, const char *s, int base); +#endif //__PBC_FP_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_g_param.h b/moon-abe/pbc-0.5.14/include/pbc_g_param.h new file mode 100644 index 00000000..0b7bf45d --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_g_param.h @@ -0,0 +1,28 @@ +// Type G pairings. + +// Requires: +// * mnt.h +// * param.h +#ifndef __PBC_G_PARAM_H__ +#define __PBC_G_PARAM_H__ + +struct symtab_s; +int pbc_param_init_g(pbc_param_ptr par, struct symtab_s *tab); + +/*@manual gparam +Type G curves are generated using the complex multiplication (CM) method. This +function sets 'p' to a type G pairing parameters from CM parameters 'cm'. +They have embedding degree 10. + +To be secure, generic discrete log algorithms must be infeasible in groups of +order r, and finite field discrete log algorithms must be infeasible in finite +fields of order q^6^. For usual CM parameters, r is a few bits smaller than q. + +They are quite slow at the moment so for now type F is a better choice. + +The file `param/g149.param` contains parameters for a +type G pairing with 149-bit group and field sizes. +*/ +void pbc_param_init_g_gen(pbc_param_t p, pbc_cm_ptr cm); + +#endif //__PBC_G_PARAM_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_hilbert.h b/moon-abe/pbc-0.5.14/include/pbc_hilbert.h new file mode 100644 index 00000000..64bdf9c1 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_hilbert.h @@ -0,0 +1,13 @@ +// Requires: +// * gmp.h +#ifndef __PBC_HILBERT_H__ +#define __PBC_HILBERT_H__ + +// Allocate an array of mpz_t and fill it with the coefficients of the Hilbert +// polynomial H_D(x). Returns the size of array. +size_t pbc_hilbert(mpz_t **arr, int D); + +// Free an array allocated by `pbc_hilbert()`. +void pbc_hilbert_free(mpz_t *arr, size_t n); + +#endif //__PBC_HILBERT_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_i_param.h b/moon-abe/pbc-0.5.14/include/pbc_i_param.h new file mode 100644 index 00000000..3f0dde58 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_i_param.h @@ -0,0 +1,23 @@ +// Eta_T pairing over ternary extension field +// +// Requires: +// * pbc_param.h +#ifndef __PBC_I_PARAM_H__ +#define __PBC_I_PARAM_H__ + +struct symtab_s; +int pbc_param_init_i(pbc_param_ptr par, struct symtab_s *); + +/*@manual aparam +Generate type I pairing parameters and store them in 'p', +where the group order is at least 2^'group_size'. + +To be as secure as 64 bit symmetric encryption, 'group_size' may be 150. +To get 128 bit symmetric secure level, 'group_size' may be 696. + +The file `param/i.param` contains parameters for a type I pairing suitable for +cryptographic use. +*/ +void pbc_param_init_i_gen(pbc_param_ptr par, int group_size); + +#endif //__PBC_I_PARAM_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_memory.h b/moon-abe/pbc-0.5.14/include/pbc_memory.h new file mode 100644 index 00000000..4c71a2e0 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_memory.h @@ -0,0 +1,24 @@ +// Requires: +// * stdlib.h +#ifndef __PBC_MEMORY_H__ +#define __PBC_MEMORY_H__ + +// Memory allocation functions used by PBC. +extern void *(*pbc_malloc)(size_t); +extern void *(*pbc_realloc)(void *, size_t); +extern void (*pbc_free)(void *); + +void *pbc_calloc(size_t, size_t); + +/*@manual alloc +Set custom allocation functions. The parameters must be function pointers to +drop-in replacements for malloc, realloc and free, except that malloc and +realloc should terminate the program on failure: they must not return in this +case. +*/ +void pbc_set_memory_functions(void *(*malloc_fn)(size_t), + void *(*realloc_fn)(void *, size_t), void (*free_fn)(void *)); + +char *pbc_strdup(const char *s); + +#endif //__PBC_MEMORY_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_mnt.h b/moon-abe/pbc-0.5.14/include/pbc_mnt.h new file mode 100644 index 00000000..82e4993b --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_mnt.h @@ -0,0 +1,49 @@ +//requires +// * gmp.h +#ifndef __PBC_MNT_H__ +#define __PBC_MNT_H__ + +struct pbc_cm_s { + mpz_t q; //curve defined over F_q + mpz_t n; //has order n (= q - t + 1) in F_q (and r^2 in F_q^k) + mpz_t h; //h * r = n, r is prime + mpz_t r; + int D; //discrminant needed to find j-invariant + int k; //embedding degree +}; + +typedef struct pbc_cm_s *pbc_cm_ptr; +typedef struct pbc_cm_s pbc_cm_t[1]; + +/*@manual cminfo +Initializes 'cm'. +*/ +void pbc_cm_init(pbc_cm_t cm); +/*@manual cminfo +Clears 'cm'. +*/ +void pbc_cm_clear(pbc_cm_t cm); + +/*@manual cminfo +For a given discriminant D, searches for type D pairings suitable for +cryptography (MNT curves of embedding degree 6). +The group order is at most 'bitlimit' bits. For each set of CM parameters +found, call 'callback' with +pbc_cm_t+ and given +void *+. If the callback +returns nonzero, stops search and returns that value. +Otherwise returns 0. +*/ +int pbc_cm_search_d(int (*callback)(pbc_cm_ptr, void *), void *data, + unsigned int D, unsigned int bitlimit); + +/*@manual cminfo +For a given discriminant D, searches for type G pairings suitable for +cryptography (Freeman curve). +The group order is at most 'bitlimit' bits. For each set of CM parameters +found, call 'callback' with +pbc_cm_t+ and given +void *+. If the callback +returns nonzero, stops search and returns that value. +Otherwise returns 0. +*/ +int pbc_cm_search_g(int (*callback)(pbc_cm_ptr, void *), void *data, + unsigned int D, unsigned int bitlimit); + +#endif //__PBC_MNT_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_multiz.h b/moon-abe/pbc-0.5.14/include/pbc_multiz.h new file mode 100644 index 00000000..17657779 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_multiz.h @@ -0,0 +1,20 @@ +// Multinomnials with integer coefficients. + +//requires +// * field.h + +#ifndef __PBC_FIELDMULTI_H__ +#define __PBC_FIELDMULTI_H__ + +void field_init_multiz(field_ptr f); + +element_ptr multiz_new_list(element_ptr e); +void multiz_append(element_ptr l, element_ptr m); + +void multiz_to_mpz(mpz_ptr z, multiz ep); +int multiz_is_z(multiz m); +multiz multiz_at(multiz m, int i); +int multiz_count(multiz m); +int multiz_is0(multiz m); + +#endif //__PBC_FIELDMULTI_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_pairing.h b/moon-abe/pbc-0.5.14/include/pbc_pairing.h new file mode 100644 index 00000000..1f127fb1 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_pairing.h @@ -0,0 +1,280 @@ +// Requires: +// * stdio.h +// * gmp.h +// * utils.h +// * field.h +// * param.h +#ifndef __PBC_PAIRING_H__ +#define __PBC_PAIRING_H__ + +struct pairing_pp_s { + struct pairing_s *pairing; + void *data; +}; +typedef struct pairing_pp_s pairing_pp_t[1]; +typedef struct pairing_pp_s *pairing_pp_ptr; + +struct pairing_s { + mpz_t r; // order of G1, G2, GT + field_t Zr; // the field Z_r + field_ptr G1, G2; + field_t GT; // group of rth roots of unity + + mpz_t phikonr; + // Phi_k(q)/r where Phi_k is the kth cyclotomic polynomial, + // q as in F_q, is the base field + + void (*phi)(element_ptr out, element_ptr in, struct pairing_s *pairing); //isomorphism G2 --> G1 + void (*map)(element_ptr out, element_ptr in1, element_ptr in2, + struct pairing_s *p); + void (*prod_pairings)(element_ptr out, element_t in1[], element_t in2[], int n_prod, + struct pairing_s *p); //calculate a product of pairings at one time. + // is_almost coddh returns true given (g, g^x, h, h^x) or (g, g^x, h, h^-x) + // order is important: a, b are from G1, c, d are from G2 + int (*is_almost_coddh)(element_ptr a, element_ptr b, + element_ptr c, element_ptr d, + struct pairing_s *p); + void (*clear_func)(struct pairing_s *); + void (*pp_init)(pairing_pp_t p, element_t in1, struct pairing_s *); + void (*pp_clear)(pairing_pp_t p); + void (*pp_apply)(element_t out, element_t in2, pairing_pp_t p); + void (*finalpow)(element_t e); + void (*option_set)(struct pairing_s *, char *key, char *value); + void *data; +}; + +typedef struct pairing_s pairing_t[1]; +typedef struct pairing_s *pairing_ptr; + +// TODO: The 'pairing' argument is redundant. +/*@manual pairing_apply +Get ready to perform a pairing whose first input is 'in1', +and store the results of time-saving precomputation in 'p'. +*/ +static inline void pairing_pp_init(pairing_pp_t p, element_t in1, pairing_t pairing) { + if (element_is0(in1)) { + p->pairing = NULL; + return; + } + p->pairing = pairing; + pairing->pp_init(p, in1, pairing); +} + +/*@manual pairing_apply +Clear 'p'. This should be called after 'p' is no longer needed. +*/ +static inline void pairing_pp_clear(pairing_pp_t p) { + if (!p->pairing) { + // happens when p was initialized with identity + return; + } + p->pairing->pp_clear(p); +} + +/*@manual pairing_apply +Compute a pairing using 'in2' and the preprocessed information stored in 'p' +and store the output in 'out'. The inputs to the pairing are the element +previously used to initialize 'p' and the element 'in2'. +*/ +static inline void pairing_pp_apply(element_t out, element_t in2, pairing_pp_t p) { + if (!p->pairing) { + element_set0(out); + return; + } + if (element_is0(in2)) { + element_set0(out); + return; + } + p->pairing->pp_apply((element_ptr) out->data, in2, p); +} + +/*@manual pairing_init +Initialize pairing from parameters in a ASCIIZ string 'str' +Returns 0 on success, 1 on failure. +*/ +int pairing_init_set_str(pairing_t pairing, const char *s); + +/*@manual pairing_init +Same, but read at most 'len' bytes. +If 'len' is 0, it behaves as the previous function. +Returns 0 on success, 1 on failure. +*/ +int pairing_init_set_buf(pairing_t pairing, const char *s, size_t len); + +/*@manual pairing_init +Initialize a pairing with pairing parameters 'p'. +*/ +void pairing_init_pbc_param(struct pairing_s *pairing, pbc_param_ptr p); + +/*@manual pairing_init +Free the space occupied by 'pairing'. Call +whenever a +pairing_t+ variable is no longer needed. +Only call this after all elements associated with 'pairing' +have been cleared, as they need information stored in the 'pairing' +structure. +*/ +void pairing_clear(pairing_t pairing); + +static inline void pairing_apply(element_t out, element_t in1, element_t in2, + pairing_t pairing) { + PBC_ASSERT(pairing->GT == out->field, "pairing output mismatch"); + PBC_ASSERT(pairing->G1 == in1->field, "pairing 1st input mismatch"); + PBC_ASSERT(pairing->G2 == in2->field, "pairing 2nd input mismatch"); + if (element_is0(in1)) { + element_set0(out); + return; + } + if (element_is0(in2)) { + element_set0(out); + return; + } + // TODO: 'out' is an element of a multiplicative subgroup, but the + // pairing routine expects it to be an element of the full group, hence + // the 'out->data'. I should make this clearer. + pairing->map((element_ptr) out->data, in1, in2, pairing); +} + +/*@manual pairing_apply +Computes a pairing: 'out' = 'e'('in1', 'in2'), +where 'in1', 'in2', 'out' must be in the groups G1, G2, GT. +*/ +static inline void element_pairing(element_t out, element_t in1, element_t in2) { + pairing_ptr pairing = out->field->pairing; + PBC_ASSERT(pairing != NULL, "pairing output mismatch"); + pairing_apply(out, in1, in2, pairing); +} + +/*@manual pairing_apply +Computes the product of pairings, that is +'out' = 'e'('in1'[0], 'in2'[0]) ... 'e'('in1'[n-1], 'in2'[n-1]). +The arrays 'in1', 'in2' must have at least 'n' elements belonging to +the groups G1, G2 respectively, and 'out' must belong to the group GT. +*/ +static inline void element_prod_pairing( + element_t out, element_t in1[], element_t in2[], int n) { + pairing_ptr pairing = out->field->pairing; + int i; + PBC_ASSERT(pairing->GT == out->field, "pairing output mismatch"); + for(i = 0; i < n; i++) { + PBC_ASSERT(pairing->G1 == in1[i]->field, "pairing 1st input mismatch"); + PBC_ASSERT(pairing->G2 == in2[i]->field, "pairing 2nd input mismatch"); + if (element_is0(in1[i])) { + element_set0(out); + return; + } + if (element_is0(in2[i])) { + element_set0(out); + return; + } + } + pairing->prod_pairings((element_ptr) out->data, in1, in2, n, pairing); +} + +/*@manual pairing_op +Returns true if G1 and G2 are the same group. +*/ +static inline int pairing_is_symmetric(pairing_t pairing) { + return pairing->G1 == pairing->G2; +} + +/*@manual pairing_op +Returns the length in bytes needed to represent an element of G1. +*/ +static inline int pairing_length_in_bytes_G1(pairing_t pairing) { + return pairing->G1->fixed_length_in_bytes; +} + +/*@manual pairing_op +Returns the length in bytes needed to represent the x-coordinate of +an element of G1. +*/ +static inline int pairing_length_in_bytes_x_only_G1(pairing_t pairing) { + return pairing->G1->fixed_length_in_bytes / 2; +} + +/*@manual pairing_op +Returns the length in bytes needed to represent a compressed form of +an element of G1. There is some overhead in decompressing. +*/ +static inline int pairing_length_in_bytes_compressed_G1(pairing_t pairing) { + return pairing->G1->fixed_length_in_bytes / 2 + 1; +} + +/*@manual pairing_op +Returns the length in bytes needed to represent an element of G2. +*/ +static inline int pairing_length_in_bytes_G2(pairing_t pairing) { + return pairing->G2->fixed_length_in_bytes; +} + +/*@manual pairing_op +Returns the length in bytes needed to represent a compressed form of +an element of G2. There is some overhead in decompressing. +*/ +static inline int pairing_length_in_bytes_compressed_G2(pairing_t pairing) { + return pairing->G2->fixed_length_in_bytes / 2 + 1; +} + +/*@manual pairing_op +Returns the length in bytes needed to represent the x-coordinate of +an element of G2. +*/ +static inline int pairing_length_in_bytes_x_only_G2(pairing_t pairing) { + return pairing->G2->fixed_length_in_bytes / 2; +} + +/*@manual pairing_op +Returns the length in bytes needed to represent an element of GT. +*/ +static inline int pairing_length_in_bytes_GT(pairing_t pairing) { + return pairing->GT->fixed_length_in_bytes; +} + +/*@manual pairing_op +Returns the length in bytes needed to represent an element of Zr. +*/ +static inline int pairing_length_in_bytes_Zr(pairing_t pairing) { + return pairing->Zr->fixed_length_in_bytes; +} + +static inline int is_almost_coddh(element_t a, element_t b, + element_t c, element_t d, pairing_t pairing) { + return pairing->is_almost_coddh(a, b, c, d, pairing); +} + +/*@manual einit.1 +*/ +static inline void element_init_G1(element_t e, pairing_t pairing) { + element_init(e, pairing->G1); +} + +/*@manual einit.1 +*/ +static inline void element_init_G2(element_t e, pairing_t pairing) { + element_init(e, pairing->G2); +} + +/*@manual einit.1 +Initialize 'e' to be an element of the group G1, G2 or GT of 'pairing'. +*/ +static inline void element_init_GT(element_t e, pairing_t pairing) { + element_init(e, pairing->GT); +} + +/*@manual einit.1 +Initialize 'e' to be an element of the ring Z_r of 'pairing'. +r is the order of the groups G1, G2 and GT that are involved in the pairing. +*/ +static inline void element_init_Zr(element_t e, pairing_t pairing) { + element_init(e, pairing->Zr); +} + +static inline void pairing_option_set(pairing_t pairing, char *key, char *value) { + pairing->option_set(pairing, key, value); +} + +// Initialize GT = group of rth roots of unity in f. +// Requires pairing->r has been set. +void pairing_GT_init(pairing_ptr pairing, field_t f); + +#endif //__PBC_PAIRING_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_param.h b/moon-abe/pbc-0.5.14/include/pbc_param.h new file mode 100644 index 00000000..143ab73c --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_param.h @@ -0,0 +1,49 @@ +// Requires: +// * gmp.h +#ifndef __PBC_PARAM_H__ +#define __PBC_PARAM_H__ + +struct pairing_s; +struct pbc_param_interface_s { + void (*clear)(void *); + void (*init_pairing)(struct pairing_s *, void *); + void (*out_str)(FILE *stream, void *data); +}; +typedef struct pbc_param_interface_s pbc_param_interface_t[1]; +typedef struct pbc_param_interface_s *pbc_param_interface_ptr; + +struct pbc_param_s { + pbc_param_interface_ptr api; + void *data; +}; +typedef struct pbc_param_s *pbc_param_ptr; +typedef struct pbc_param_s pbc_param_t[1]; + +/*@manual param +Initializes pairing parameters from the string 's'. +Returns 0 if successful, 1 otherwise. +*/ +int pbc_param_init_set_str(pbc_param_t par, const char *s); + +/*@manual param +Same, but read at most 'len' bytes. +If 'len' is 0, it behaves as the previous function. +Returns 0 if successful, 1 otherwise. +*/ +int pbc_param_init_set_buf(pbc_param_t par, const char *s, size_t len); + +/*@manual param +Write pairing parameters to ''stream'' in a text format. +*/ +static inline void pbc_param_out_str(FILE *stream, pbc_param_ptr p) { + p->api->out_str(stream, p->data); +} + +/*@manual param +Clear 'p'. Call after 'p' is no longer needed. +*/ +static inline void pbc_param_clear(pbc_param_ptr p) { + p->api->clear(p->data); +} + +#endif //__PBC_PARAM_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_poly.h b/moon-abe/pbc-0.5.14/include/pbc_poly.h new file mode 100644 index 00000000..bca8e108 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_poly.h @@ -0,0 +1,57 @@ +// Polynomial rings R[x], and polynomial rings modulo polynomials, +// i.e. R[x]_{f(x)}. + +// Requires: +// * gmp.h +// * field.h +#ifndef __PBC_POLY_H__ +#define __PBC_POLY_H__ + +// Initializes a polynomial ring. +void field_init_poly(field_ptr f, field_ptr base_field); + +// Initializes a polynomial modulo ring. +// Requires poly to be monic. +void field_init_polymod(field_ptr f, element_ptr poly); + +#pragma GCC visibility push(hidden) +// Internal library functions: + +// Returns deg f. +static inline int poly_degree(element_ptr f) { + return element_item_count(f) - 1; +} + +// Returns base field of f (where the coefficients live). +field_ptr poly_base_field(element_t f); + +// Sets the coefficient of x^n to 0. +void poly_set_coeff0(element_ptr f, int n); + +// Sets the coefficient of x^n to 1. +void poly_set_coeff1(element_ptr f, int n); + +// Sets the coefficient of x^n to a. +void poly_set_coeff(element_ptr f, element_ptr a, int n); + +// Sets f = x. +void poly_setx(element_ptr f); +void poly_const_mul(element_ptr res, element_ptr a, element_ptr poly); + +// Returns 0 when a root exists and sets root to one of the roots. +int poly_findroot(element_ptr root, element_ptr poly); + +// Returns 1 if polynomial is irreducible, 0 otherwise. +// Requires the polynomial to be monic. +int poly_is_irred(element_ptr f); +void poly_random_monic(element_ptr f, int deg); + +void element_field_to_poly(element_t poly, element_t constant); +void element_field_to_polymod(element_ptr f, element_ptr a); + +void polymod_const_mul(element_ptr res, element_ptr a, element_ptr e); +int polymod_field_degree(field_t f); + +#pragma GCC visibility pop + +#endif //__PBC_POLY_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_random.h b/moon-abe/pbc-0.5.14/include/pbc_random.h new file mode 100644 index 00000000..df688b9a --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_random.h @@ -0,0 +1,32 @@ +// Requires: +// * gmp.h +#ifndef __PBC_RANDOM_H__ +#define __PBC_RANDOM_H__ + +/*@manual pbcrandom +Sets 'filename' as a source of random bytes. For example, +on Linux one might use `/dev/random`. +*/ +void pbc_random_set_file(char *filename); + +/*@manual pbcrandom +Uses a determinstic random number generator, seeded with 'seed'. +*/ +void pbc_random_set_deterministic(unsigned int seed); + +/*@manual pbcrandom +Uses given function as a random number generator. +*/ +void pbc_random_set_function(void (*fun)(mpz_t, mpz_t, void *), void *data); + +/*@manual pbcrandom +Selects a random 'z' that is less than 'limit'. +*/ +void pbc_mpz_random(mpz_t z, mpz_t limit); + +/*@manual pbcrandom +Selects a random 'bits'-bit integer 'z'. +*/ +void pbc_mpz_randomb(mpz_t z, unsigned int bits); + +#endif //__PBC_RANDOM_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_singular.h b/moon-abe/pbc-0.5.14/include/pbc_singular.h new file mode 100644 index 00000000..afa6156f --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_singular.h @@ -0,0 +1,11 @@ +//requires +// * stdio.h +// * gmp.h +// * field.h +#ifndef __PBC_SINGULAR_H__ +#define __PBC_SINGULAR_H__ + +void field_init_curve_singular_with_node(field_t c, field_t field); +void pairing_init_singular_with_node(pairing_t pairing, mpz_t q); + +#endif //__PBC_SINGULAR_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_ternary_extension_field.h b/moon-abe/pbc-0.5.14/include/pbc_ternary_extension_field.h new file mode 100644 index 00000000..8effc16a --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_ternary_extension_field.h @@ -0,0 +1,22 @@ +// some ternary extension fields, +// including $GF(3^m) = GF(3)[x]/(x^m + x^t + 2)$, +// $GF(3^{2*m}) = GF(3^m)[x]/(x^2 + 1)$, +// $GF(3^{3*m}) = GF(3^m)[x]/(x^3 - x - 1)$, +// and $GF(3^{6*m}) = GF(3^{2*m})[x]/(x^3 - x - 1)$ +// +// Requires: +// * pbc_field.h + +#ifndef __PBC_TERNARY_EXTENSION_FIELD_H__ +#define __PBC_TERNARY_EXTENSION_FIELD_H__ + +/* initialize $f$ as $GF(3)[x]/(x^m + x^t + 2)$ */ +void field_init_gf3m(field_t f, unsigned m, unsigned t); + +/* initialize $f$ as $base_field[x]/(x^2 + 1)$ */ +void field_init_gf32m(field_t f, field_t base_field); + +/* initialize $f$ as $base_field[x]/(x^3 - x - 1)$ */ +void field_init_gf33m(field_t f, field_t base_field); + +#endif //__PBC_TERNARY_EXTENSION_FIELD_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_test.h b/moon-abe/pbc-0.5.14/include/pbc_test.h new file mode 100644 index 00000000..35d6f754 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_test.h @@ -0,0 +1,42 @@ +// Useful for tests. + +#ifndef __PBC_TEST_H__ +#define __PBC_TEST_H__ + +/*@manual test +Initializes pairing from file specified as first argument, or from standard +input if there is no first argument. +*/ +static inline void pbc_demo_pairing_init(pairing_t pairing, int argc, char **argv) { + char s[16384]; + FILE *fp = stdin; + + if (argc > 1) { + fp = fopen(argv[1], "r"); + if (!fp) pbc_die("error opening %s", argv[1]); + } + size_t count = fread(s, 1, 16384, fp); + if (!count) pbc_die("input error"); + fclose(fp); + + if (pairing_init_set_buf(pairing, s, count)) pbc_die("pairing init failed"); +} + +/*@manual test +Returns seconds elapsed since the first call to this function. +Returns 0 the first time. +*/ +double pbc_get_time(void); + +/*@manual test +Macro: if `condition` evaluates to 0 then print an error. +*/ +#define EXPECT(condition) \ + if (condition); else pbc_err_count++, fprintf(stderr, "\n*** FAIL ***\n %s:%d: %s\n\n", __FILE__, __LINE__, #condition) + +/*@manual test +Total number of failed EXPECT checks. +*/ +int pbc_err_count; + +#endif //__PBC_TEST_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_utils.h b/moon-abe/pbc-0.5.14/include/pbc_utils.h new file mode 100644 index 00000000..62c02b07 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_utils.h @@ -0,0 +1,86 @@ +#ifndef __PBC_UTILS_H__ +#define __PBC_UTILS_H__ + +#ifdef PBC_DEBUG + +/*@manual debug +Macro: if `expr` evaluates to 0, print `msg` and exit. +*/ +#define PBC_ASSERT(expr, msg) \ + (pbc_assert(expr, msg, __func__)) + +/*@manual debug +Macro: if elements `a` and `b` are from different fields then exit. +*/ +#define PBC_ASSERT_MATCH2(a, b) \ + (pbc_assert_match2(a, b, __func__)) + +/*@manual debug +Macro: if elements `a`, `b` and `c` are from different fields then exit. +*/ +#define PBC_ASSERT_MATCH3(a, b, c) \ + (pbc_assert_match3(a, b, c, __func__)) + +#else + +#define PBC_ASSERT(expr, msg) ((void) (0)) +#define PBC_ASSERT_MATCH2(a, b) ((void) (0)) +#define PBC_ASSERT_MATCH3(a, b, c) ((void) (0)) + +#endif + +// die, warn and info based on Git code. + +/*@manual log +By default error messages are printed to standard error. +Call `pbc_set_msg_to_stderr(0)` to suppress messages. +*/ +int pbc_set_msg_to_stderr(int i); + +/*@manual log +Reports error message and exits with code 128. +*/ +void pbc_die(const char *err, ...) + __attribute__((__noreturn__)) + __attribute__((format (printf, 1, 2))); + +/*@manual log +Reports informational message. +*/ +void pbc_info(const char *err, ...) + __attribute__((format (printf, 1, 2))); + +/*@manual log +Reports warning message. +*/ +void pbc_warn(const char *err, ...) + __attribute__((format (printf, 1, 2))); + +/*@manual log +Reports error message. +*/ +void pbc_error(const char *err, ...) + __attribute__((format (printf, 1, 2))); + +#ifndef UNUSED_VAR +#if defined(__GNUC__) +// We could use __attribute__((unused)) instead. +#define UNUSED_VAR(a) (void) a +#else +// From the ACE project: http://www.cs.wustl.edu/~schmidt/ACE.html +// silences warnings, and generates no code for many compilers +// See ACE_wrappers/ace/ace/config-macros.h:391 +// +// Not anymore: gcc no longer likes it -blynn +#define UNUSED_VAR(a) do { /* nothing */ } while (&a == 0) +#endif +#endif + +// For storing small integers in void * +// C99 standard introduced the intptr_t and uintptr_t types, +// guaranteed to be able to hold pointers +static inline void *int_to_voidp(intptr_t i) { + return (void *) i; +} + +#endif //__PBC_UTILS_H__ diff --git a/moon-abe/pbc-0.5.14/include/pbc_z.h b/moon-abe/pbc-0.5.14/include/pbc_z.h new file mode 100644 index 00000000..2ec54af3 --- /dev/null +++ b/moon-abe/pbc-0.5.14/include/pbc_z.h @@ -0,0 +1,12 @@ +// ring of integers Z +// wrappers around GMP's mpz_t + +//requires +// * field.h + +#ifndef __PBC_FIELDMPZ_H__ +#define __PBC_FIELDMPZ_H__ + +void field_init_z(field_ptr f); + +#endif //__PBC_FIELDMPZ_H__ |