diff options
Diffstat (limited to 'moon-abe/pbc-0.5.14/doc/internal.txt')
| -rw-r--r-- | moon-abe/pbc-0.5.14/doc/internal.txt | 428 |
1 files changed, 0 insertions, 428 deletions
diff --git a/moon-abe/pbc-0.5.14/doc/internal.txt b/moon-abe/pbc-0.5.14/doc/internal.txt deleted file mode 100644 index b2f217e3..00000000 --- a/moon-abe/pbc-0.5.14/doc/internal.txt +++ /dev/null @@ -1,428 +0,0 @@ -== PBC internals == - -The source code is organized by subdirectories: - -*`include`*: Headers describing the official API. Headers in other places -are for internal use only. - -*`arith`*: Finite fields: modular arithmetic, polynomial rings, and polynomial -rings modulo a polynomial. Finite fields of low characteristic are unsupported. - -*`ecc`*: Elliptic curve generation, elliptic curve groups and pairings. One -source file is dedicated to each type of pairing, containing specialized -optimizations. Some of the code requires arbitrary precision complex numbers, -which also live here but should be moved elsewhere one day. - -*`misc`*: Dynamic arrays, symbol tables, benchmarking, logging, debugging, -other utilities. - -*`gen`*: Programs that generate pairing parameters and list Hilbert -polynomials. These were used to prepare the samples in the `param` directory. - -*`example`*: Example programs showing how to use the library. - -*`guru`*: Tests, experimental code. - -=== Groups, rings, fields === - -Algebraic structures are represented in the +field_t+ data type, which mostly -contains pointers to functions written to perform operations such as addition -and multiplication in that particular group, ring or field: - - struct field_s { - ... - void (*init)(element_ptr); - void (*clear)(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); - ... - }; - typedef struct field_s *field_ptr; - typedef struct field_s field_t[1]; - -The name +algebraic_structure_t+ is arguably more accurate, but far too -cumbersome. It may help if one views groups and rings as handicapped fields. - -The last two lines of the above code excerpt show how GMP and PBC define data -types: they are arrays of length one so that when a variable is -declared, space is automatically allocated for it on the stack. -Yet when used as a argument to a function, a pointer is passed, thus there is -no need to explicitly allocate and deallocate memory, nor reference and -dereference variables. - -Each +element_t+ contains a field named +field+ to such a +field_t+ variable. -The only other field is +data+, which stores any data needed for the -implementation of the particular algebraic structure the element resides in. - - struct element_s { - struct field_s *field; - void *data; - }; - -When an +element_t+ variable is initialized, +field+ is set appropriately, and -then the initialization specific to that field is called to complete the -initialization. Here, a line of code is worth a thousand words: - - void element_init(element_t e, field_ptr f) { - e->field = f; - f->init(e); - } - -Thus during a call to one of the `element_` functions, the +field+ pointer is -followed then the appropriate routine is executed. For example, modular addition -results when the input element is an element of a finite field, while -polynomial addition is performed for elements of a polynomial ring and so on. - - void element_add(element_t n, element_t a, element_t b) { - n->field->add(n, a, b); - } - -My design may seem dangerous because if a programmer inadvertently attempts -to add a polynomial and a point on an elliptic curve, say, the code -will compile without warnings since they have the same data type. - -However I settled on having a catch-all ``glorified +void *+'' +element_t+ -because I wanted to - -- extend a field an arbitrary number of times (though in practice, currently I - only need to extend a field twice at most), -- switch fields easily, so for example a program that benchmarks addition in - polynomial rings can be trivially modified to benchmark addition in a group, - and -- interchange different implementations of the same algebraic structure, for - example, compare Montgomery representation versus a naive implementation of - integer modulo rings. - -Additionally, defining `PBC_DEBUG` catches many type mismatches. - -In mathematics, groups, rings and fields should be distinguished, but for -implmentation, it is simplest lump them together under the same heading. -In any event, distinct data types may lead to a false sense of security. -Fields of prime order with different moduli would still fall under the same -data type, with unpleasant results if their elements are mistakenly mixed. - -I have vague plans to add flags to +field_t+ describing the capabilities of a -particular +field_t+. These flags would be set during initialization, and -would indicate for example whether one can invert every nonzero element, -whether there are one or two operations (that is, group versus ring), whether -the field is an integer mod ring, polynomial ring, or polynomial mod ring, and -so on. Once in place, more runtime checks can be performed to avoid illegal -inversion and similar problems. - -Another option is to introduce data types for each of the four pairing-related -algebraic structures, namely G1, G2, GT and Zr, as these are the only ones -needed for implementing pairing-based cryptosystems. - -An alternative was to simply use +void *+ instead of +element_t+ and require -the programmer to pass the field as a parameter, e.g. +element_add(a, b, c, -F_13)+, but I decided the added annoyance of having to type this extra variable -every time negated any benefits, such as obviating the need for the -+field+ pointer in +struct element_s+, even if one ignores -the more serious problem that runtime type checking is considerably harder, if -not impossible. - -I suppose one could write a preprocessor to convert one type of notation -to the other, but I would like the code to be standard C. (On the other hand, -as Hovav Shacham suggested, it may be nice to eventually have a converter that -takes human-friendly infix operator expressions like `a = (b + c) * -d` and outputs the assembly-like `element_` equivalents.) - -=== Internal randomness === - -Some algorithms require a quadratic nonresidue in a given field. These -are computed lazily: The first time a quadratic nonresidue is requested, one is -generated at random, using the same source of random bits as other PBC random -functions. [Which reminds me, should I get rid of the +nqr+ field and instead -have it as part of the +data+ field in struct field_s?] - -In `fieldquadratic.c`, a quadratic field extension is constructed with a square -root of this randomly generated quadratic nonresidue in the base field. Thus -for a nondeterminstic source of random bits, the same field may be constructed -differently on different runs. - -To construct the same field the same way every time, one must record the -quadratic nonresidue generated from one run, and call `field_set_nqr()` every -time this particular construction of a quadratic field extension is desired. -Another use for this function is to save time by setting the quadratic -nonresidue to some precomputed value. - -Similarly, for higher degree extensions, a random irreducible polynomial -may be chosen to construct it, but this must be recorded if the same -construction is later required. - -This happens behind the scenes in PBC. - -=== Type A internals === - -Type A pairings are constructed on the curve y^2^ = x^3^ + x over the field F_q -for some prime q = 3 mod 4. -Both G1 and G2 are the group of points E(F_q), so this -pairing is symmetric. It turns out #E(F_q) = q + 1 and -#E(F_q^2^) = (q + 1)^2^. Thus the embedding degree k is 2, -and hence GT is a subgroup of F_q^2. The order r is some prime -factor of q + 1. - -Write q + 1 = r * h. For efficiency, r is picked to be a Solinas prime, -that is, r has the form 2^a^ +- 2^b^ +- 1 for some integers 0 < b < a. - -Also, we choose q = -1 mod 12 so F_q^2^ can be implemented as F_q[i] -(where i = sqrt(-1)) and since q = -1 mod 3, cube roots in F_q -are easy to compute. This latter feature may be removed because I have -not found a use for it yet (in which case we only need q = -1 mod 4). - -+a_param+ struct fields: - - exp2, exp1, sign1, sign0, r: - r = 2^exp2 + sign1 * 2^exp1 + sign0 * 1 (Solinas prime) - q, h: - r * h = q + 1 - q is a prime, h is a multiple of 12 (thus q = -1 mod 12) - -Type A1 uses the same equation, but have different fields since the library -is given r and cannot choose it. - -+a1_param+ struct fields: - - p, n, l: - p + 1 = n * l - p is prime, same as the q in a_param, n is the order of the group. - -=== Type B internals === - -Unimplemented. Similar to type A. The curve y^2^ = x^3^ + 1 over the field F_q -for some prime q = 2 mod 3, which implies cube roots in F_q are easy to -compute, though we can achieve this for type A pairings by constraining q -appropriately. I recommend requiring q = 3 mod 4 as well, so that -1 is -a quadratic nonresidue. - -The lack of an x term simplifies some routines such as point doubling. - -It turns out we must choose between symmetry or efficiency due to the nature of -a certain optimization. - -=== Type C internals === - -Unimplemented. The supersingular curves y^2^ = x^3^ + 2x + 1 and -y^2^ = x^3^ + 2x - 1 over a field of characteristic 3. Discussed at length -by Boneh, Lynn, and Shacham, "Short signatures from the Weil pairing". -Many optimizations can be applied to speed up these pairings; see -Barreto et al., "Efficient algorithms for pairing-based cryptosystems", but -sadly, an attack due to Coppersmith makes these curves less attractive. - -=== Type D internals === - -These are ordinary curves of with embedding degree 6, whose orders are prime -or a prime multiplied by a small constant. - -A type D curve is defined over some field F_q and has order h * r where -r is a prime and h is a small constant. Over the field F_q^6^ its order is -a multiple of r^2^. - -Typically the order of the curve E is around 170 bits, as is F_q, the base -field, thus q^k^ is around the 1024-bit mark which is commonly considered -good enough. - -+d_param+ struct fields: - - q F_q is the base field - n # of points in E(F_q) - r large prime dividing n - h n = h * r - a E: y^2 = x^3 + ax + b - b - nk # of points in E(F_q^k) - hk nk = hk * r * r - coeff0 coefficients of a monic cubic irreducible over F_q - coeff1 - coeff2 - nqr quadratic nonresidue in F_q - -These were discovered by Miyaji, Nakabayashi and Takano, -"New explicit conditions of elliptic curve traces for FR-reduction". - -=== Type E Internals === - -The CM (Complex Multiplication) method of constructing elliptic curves -starts with the Diophantine equation - - DV^2 = 4q - t^2 - -If t = 2 and q = D r^2^ h^2^ + 1 for some prime r (which we choose to -be a Solinas prime) and some integer h, we find that this equation is easily -solved with V = 2rh. - -Thus it is easy to find a curve (over the field F_q) with order q - 1. -Note r^2^ divides q - 1, thus we have an embedding degree of 1. - -Hence all computations necessary for the pairing can be done in F_q alone. -There is never any need to extend F_q. - -As q is typically 1024 bits, group elements take a lot of space to represent. -Moreover, many optimizations do not apply to this type, resulting in a slower -pairing. - -+e_param+ struct fields: - - exp2, exp1, sign1, sign0, r: - r = 2^exp2 + sign1 * 2^exp1 + sign0 * 1 (Solinas prime) - q, h - q = h r^2 + 1 where r is prime, and h is 28 times a perfect square - a, b - E: y^2 = x^3 + ax + b - -=== Type F internals === - -Using carefully crafted polynomials, k = 12 pairings can be constructed. -Only 160 bits are needed to represent elements of one group, and 320 bits -for the other. - -Also, embedding degree k = 12 allows higher security short signatures. -(k = 6 curves cannot -be used to scale security from 160-bits to say 256-bits because finite -field attacks are subexponential.) - -+f_param+ struct fields: - - q: - The curve is defined over Fq - r: - The order of the curve. - b: - E: y^2= x^3 + b - beta: - A quadratic nonresidue in Fq: used in quadratic extension. - alpha0, alpha1: - x^6 + alpha0 + alpha1 sqrt(beta) is irreducible: used in sextic extension. - -Discovered by Barreto and Naehrig, "Pairing-friendly elliptic curves of prime order". - -=== Type G Internals === - -Another construction based on the CM method. - -+g_param+ struct fields: - - q, n, h, r: - h * r = n is the order of E(F_q) - a, b: - E: y^2 = x^3 + ax + b - nk: - #E(F_q^10) - hk: - hk * r^2 = nk - coeff: - array of coefficients of polynomial used for quintic extension. - nqr: - a quadratic nonresidue - -+g_param+ struct fields: - -Discovered by Freeman, "Constructing pairing-friendly elliptic curves with embedding degree 10." - -=== Type I Internals === - -Type I pairings is symmetric, constructed on a supersingular curve -y^2^ = x^3^ - x + 1 over a ternary extension field F_{3^m^}. -The embedding degree k is 6. -Both G1 and G2 are the group of points E(F_{3^m^}). -GT is a subgroup of F_{3^6*m^}. The group order is a prime number. - -parameters: - - m, t: - The ternary extension field is F(3)[x]/(x^m^ + x^t^ + 2). - n: - the order of G1 - n2: - n * n2 = number of points in E(F_{3^m^}) - -Introduced by Barreto et al, "Efficient Pairing Computation on Supersingular -Abelian Varieties", Designs, Codes and Cryptography, vol. 42, no. 3, pp. 239-271, -Mar. 2007. - -=== Testing functions === - -For testing, debugging, demonstrations and benchmarks. -Declared in +pbc_test.h+: - -include::gen/test.txt[] - -=== Dynamic arrays === - -The +darray_t+ data type manages an array of pointers of type +void \*+, -allocating more memory when necessary. -Declared in +pbc_darray.h+. - -include::gen/darray.txt[] - -=== Symbol tables === - -The +symtab_t+ data type manages symbol tables where the keys are strings of -type +char \*+ and the values are pointers of type +void \*+. - -At present, they are implemented inefficiently using dynamic arrays, but this -will change if the need arises. They are only used when reading a +pbc_param_t+ -from a string. Declared in +pbc_symtab.h+. - -include::gen/symtab.txt[] - -=== Religious stances === - -I chose C because: - -- GMP, which PBC requires and is also modeled on, is also written in C. -- PBC is intended to be a low-level portable cryptographic library. C is the - least common denominator. It should not be difficult to wrap PBC for other - languages. -- Despite its drawbacks (I would appreciate operator overloading and - genericity, and to a lesser extent garbage collection), I've found few - languages I like better. To quote Rob Pike, C is the desert island language. - (I also agree with his statement that OO languages conceptually provide - little extra over judicious use of function pointers in C.) - -With respect to indentation, I'm migrating the code to follow -http://google-styleguide.googlecode.com/svn/trunk/cppguide.xml[Google C++ -Style Guide] to avoid having to switch styles all the time. -The code was originally written using my old style: 4-space indent with 1TBS -(One True Brace Style). - -I'd like to have no library dependencies (except standard C libraries), -but then I'd have to write a large integer library. Furthermore, I'd have to -write it in assembly, and then port it. - -To avoid this, I use an existing library. I selected GMP because the library's -focus is on multiprecision arithmetic and nothing else, and it aims to be as -fast as possible on many platforms. Another important factor is that GMP is -released under a free license. - -On the other hand, GMP is written to deal with extremely large numbers, while I -mostly only need integers that are roughly between 160 and 2048 bits. It is -possible a library specializing in numbers of these sizes would be better for -PBC. - -I'm fond of GMP's method for eliminating the need for the +&+ and +*+ -operators most of the time by declaring a typedef on arrays of size 1. I try -to do the same with PBC for consistency, though this trick does have drawbacks. - -I would like to have GMP as the only library dependency, though I do not mind -using other libraries so long as they are optional. For example, one of the -test programs is much easier to use if compiled with the GNU readline library, -but by default compiles without it and is still functional. - -I dislike the C preprocessor. I like to place platform-specific code in -separate files and let the build system work out which one to use. Integer -constants can be defined with enum instead. I intend to minimize the number of -+#include+ statements in header files for PBC's internal use as much as -possible (they should be in the `.c` files instead), and later perhaps even -remove those annoying +#ifndef+ statements too. -I grudgingly accept some macros for PBC's debugging features. - -I liberally use nested functions, a GNU C extension. I find their expressiveness so indispensable that I'm willing to sacrifice portability for them. - -The -http://www.gnu.org/software/libc/manual/html_node/Reserved-Names.html[GNU libc manual] -states that data types ending in +_t+ should not be used because they are -reserved for future additions to C or POSIX. On the other hand, I want to stay -consistent with GMP, and ending data types with +_t+ is common practice. |