internal.xml

这是一个C的源代码

<chapter>
<title>PBC Internals</title>
<para>
Algebraic structures are represented in the
<type>field_t</type> data type, which mostly contains pointers to functions
written to perform operations such as addition and multiplication
on elements of that particular group, ring or field:
</para>
<programlisting>
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];
</programlisting>
<para>
The name
<type>algebraic_structure_t</type> is arguably more accurate,
but far too cumbersome.
If my naming choice causes discomfort, it may
help if groups and rings are simply viewed as fields where certain things
don't work!
</para>
<para>
The last two lines of the above code excerpt show how GMP, and PBC, define
data types: they are actually arrays of length one so that when
a variable is declared, space is automatically allocated for it.
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.
</para>
<para>
Each <type>element_t</type> contains a field named <parameter>field</parameter>
to such a <type>field_t</type> variable. The only other field
is <parameter>data</parameter>, which stores any data needed for the
implementation of the particular algebraic structure the element resides in.
</para>
<programlisting>
struct element_s {
    struct field_s *field;
    void *data;
};
</programlisting>
<para>
When an <type>element_t</type> variable is initialized,
<parameter>field</parameter> 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:
</para>
<programlisting>
void element_init(element_t e, field_ptr f)
{
    e->field = f;
    f->init(e);
}
</programlisting>
<para>
Thus when a call to one of the <command>element_</command> functions,
the <parameter>field</parameter> pointer is followed to see which
version of the function should be called, so that for example modular
addition is performed if the input element is an element of a finite field,
while polynomial addition is performed for elements of a polynomial ring
and so on.
</para>
<programlisting>
void element_add(element_t n, element_t a, element_t b)
{
    n->field->add(n, a, b);
}
</programlisting>
<section>
<title>Justifying the Design</title>
<para>
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,
but the results are undefined and the library will mostly cause a crash.
</para>
<para>
However I settled on having a catch-all
<quote>glorified <type>void *</type></quote> <type>element_t</type>
because I wanted to
</para>
<itemizedlist>
  <listitem>
<para>
extend a field an arbitrary number of times
(though in practice, currently I only need to extend a field twice at most),
</para>
  </listitem>
  <listitem>
<para>
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
</para>
  </listitem>
  <listitem>
<para>
interchange different implementations of the same algebraic structure.
For example, this was useful when I was comparing
Montgomery representation versus a naive implementation of modular arithmetic.
</para>
  </listitem>
</itemizedlist>
<para>
I could have separate data types to distinguish between
groups, rings and fields. It is important to
label them differently in mathematics, but here it makes more sense
to lump them together under the same heading, and just treat some kinds
as handicapped.
Distinct data types may lead to a false sense of security.
For example fields of prime order with different moduli would still
fall under the same data type, with unpleasant results if their elements
are mistakenly mixed.
</para>
<para>
I have vague plans to add flags to
<type>field_t</type>
describing the capabilities of a particular <type>field_t</type>.
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.
</para>
<para>
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.
</para>
<para>
An alternative was to simply use <type>void *</type> instead of <type>element_t</type>
and require the programmer to pass the field as a parameter,
e.g. <userinput>element_add(a, b, c, F_13)</userinput>, 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 <parameter>field</parameter> pointer in
<type>struct element_s</type>, even if one ignores the
more serious problem that runtime type checking is considerably harder,
if not impossible.
</para>
<para>
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 <userinput>a = (b + c) * d</userinput> and
outputs the assembly-like <command>element_</command> equivalents.)
</para>
<para>
A minor point: The
<ulink url="http://www.gnu.org/software/libc/manual/html_node/Reserved-Names.html">GNU libc manual</ulink>
states that data types ending in <type>_t</type>
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 I hear ending
data types with <type>_t</type> is common practice.
</para>
</section>
<section>
<title>Internal Randomness</title>
<para>
Some algorithms require a quadratic nonresidue in a given field. 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 <parameter>nqr</parameter> field and
instead have it as part of the <parameter>data</parameter> field in
struct field_s?]
</para>
<para>
In <filename>fieldquadratic.c</filename>, 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.
</para>
<para>
To construct the same field the same way every time, one must
record the quadratic nonresidue generated from one run, and call
<command>field_set_nqr()</command> 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.
</para>
<para>
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.
</para>
<para>
This happens behind the scenes in PBC.
</para>
</section>
<section><title>Type A Internals</title>
<para>
Type A pairings are constructed on
the curve y^2 = x^3 + x over the field F_q for some prime q.
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.
</para>
<para>
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 &lt; b &lt; a.
</para>
<para>
Also, 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).
</para>
<para>
<function>a_param</function> struct fields:
</para>
<literallayout>
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)
</literallayout>
</section>
<section><title>Type D Internals</title>
<para>
These are ordinary curves of with embedding degree 6, whose orders are prime
or a prime multiplied by a small constant. These are constructed using the
method due to MNT.
</para>
<para>
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.
</para>
<para>
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.
</para>
<literallayout>
c_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 is given by y^2 = x^3 + ax + b
b
nk  # of points in E(F_q^k)
hk  nk = hk * r * r
</literallayout>
</section>
<section><title>Type E Internals</title>
<para>
The CM (Complex Multiplication) method of constructing elliptic curves
starts with the Diophantine equation
</para>
<literallayout>
    DV^2 = 4q - t^2
</literallayout>
<para>
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.
</para>
<para>
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.
</para>
<para>
Hence all computations necessary for the pairing can be done in F_q alone.
There is never any need to extend F_q.
</para>
<para>
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.
</para>
<para>
TODO: describe fields
</para>
</section>
<section><title>Type F Internals</title>
<para>
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.
</para>
<para>
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.)
</para>
<para>
TODO: describe fields
</para>
</section>
<section><title>Source Code</title>
<para>
The source code is organized into several subdirectories.
</para>
<para>
All include files are in the <filename>include</filename> directory.
</para>
<para>
The <filename>arith</filename> directory contains code for implementing
finite fields of any characteristic greater than 3:
modular arithmetic, polynomial rings, and finally polynomial
rings modulo a polynomial. In future, finite fields of
low characteristic may be implemented.
</para>
<para>
The <filename>ecc</filename> directory contains code for arbitrary
precision complex numbers, curve generation (which depends on the former),
curve group operations and pairings. A separate source file is dedicated
to each type of pairing, containing optimizations tailored for
its pairing.
</para>
<para>
The <filename>misc</filename> directory contains code for dynamic arrays,
symbol tables, parsing, benchmarking, debugging and so on.
</para>
<para>
The <filename>test</filename> directory contains test programs. They
were used to generate the files in the <filename>param</filename> directory.
</para>
</section>
<section><title>Religious Stances</title>
<para>
Some decisions I made are more controversial. Nonetheless,
I would prefer submitted code to follow the conventions I picked.
</para>
<para>
I chose C for several reasons:
</para>
<orderedlist>
<listitem>
<para>
GMP, which PBC requires and is also modeled on, is also written in C.
</para>
</listitem>
<listitem>
<para>
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.
</para>
</listitem>
<listitem>
<para>
Despite its drawbacks (I could really use 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.)
</para>
</listitem>
</orderedlist>
<para>
I use the so-called One True Brace Style.
</para>
<para>
I'd like to have no library dependencies (except standard C libraries),
but then I'd have to write a large integer library. Not only that, it'd
have to be in assembly, and then I'd need to port it. To avoid this,
I use an existing library instead.
</para>
<para>
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.
</para>
<para>
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.
</para>
<para>
I'm fond of GMP's method for eliminating the need for the <code>&amp;</code>
and <code>*</code> 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.
</para>
<para>
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.
</para>
<para>
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
<code>#include</code> statements in header files for PBC's internal
use as much as possible
(they should be in the <filename>.c</filename> files instead), and later
perhaps even remove those annoying <code>#ifndef</code> statements too.
</para>
<para>
Unfortunately I do not know of an easy way to avoid the C preprocessor
for PBC's debugging features.
</para>
</section>
</chapter>