diff options
Diffstat (limited to 'moon-abe/pbc-0.5.14/doc')
22 files changed, 1609 insertions, 0 deletions
diff --git a/moon-abe/pbc-0.5.14/doc/basics.txt b/moon-abe/pbc-0.5.14/doc/basics.txt new file mode 100644 index 00000000..c9549f72 --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/basics.txt @@ -0,0 +1,58 @@ +=== Basics === + +Programs using the PBC library should include the file `pbc.h`: + + #include <pbc.h> + +and linked against the PBC library and the GMP library, e.g. + + $ gcc program.c -L. -lpbc -lgmp + +The file `pbc.h` already includes `gmp.h`. + +PBC follows GMP in several respects: + +* Output arguments generally precede input arguments. +* The same variable can be used as input and output in one call. +* Before a variable may be used it must be initialized exactly once. +When no longer needed it must be cleared. For efficiency, unnecessary +initializating and clearing should be avoided. +* PBC variables ending with +_t+ behave the same as +GMP variables in function calls: effectively as call-by references. +In other words, as in GMP, if a function that modifies an input variable, +that variable remains modified when control return is returned to the caller. +* Like GMP, variables automatically allocate memory when needed. +By default, +malloc()+ and friends are called but this can be changed. +* PBC functions are mostly reentrant. + +Since the PBC library is built on top of GMP, the GMP types +are available. PBC types are similar to GMP types. +The following example is paraphrased from an example in the GMP +manual, and shows how to declare the PBC data type +element_t+. + + element_t sum; + struct foo { element_t x, y; }; + element_t vec[20]; + +GMP has the +mpz_t+ type for integers, +mpq_t+ for rationals and so on. +In contrast, PBC uses the +element_t+ data type for elements of different +algebraic structures, such as elliptic curve groups, polynomial rings and +finite fields. Functions assume their inputs come from appropriate algebraic +structures. + +PBC data types and functions can be categorized as follows. The first two alone +suffice for a range of applications. + + - +element_t+: elements of an algebraic structure. + - +pairing_t+: pairings where elements belong; can initialize from sample + pairing parameters bundled with PBC in the +param+ subdirectory. + - +pbc_param_t+: used to generate pairing parameters. + - +pbc_cm_t+: parameters for constructing curves via the CM method; sometimes + required by +pbc_param_t+. + - +field_t+: algebraic structures: groups, rings and fields; used internally + by +pairing_t+. + - a few miscellaneous functions, such as ones controlling how random bits are + generated. + +Functions operating on a given data type usually have the same prefix, e.g. +those involving +element_t+ objects begin with +element_+. diff --git a/moon-abe/pbc-0.5.14/doc/bundle.txt b/moon-abe/pbc-0.5.14/doc/bundle.txt new file mode 100644 index 00000000..13256d83 --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/bundle.txt @@ -0,0 +1,119 @@ +[[bundlechap]] +== Bundled programs == + +Several binaries and curve parameters are bundled with the PBC library, +such as <<pbcintro, the `pbc` program>>. + +The `param` subdirectory contains pairing parameters one might use in +a real cryptosystem. Many of the test programs read the parameters +from files such as these on standard input, for example: + + $ benchmark/benchmark < param/c159.param + $ example/bls < param/e.param + +[[pbcref]] +=== Pairing-based calculator === + +The `pbc` subdirectory contains the pairing-based calculator, `pbc`, +which is loosely based on `bc`, a well-known arbitrary precision +calculator. + +See `pairing_test.pbc` for an example script. Some differences: the assignment +operator is `:=`, and newlines are ordinary whitespace and not statement +terminators. + +If started with the `-y` option, the syntax is compatible with `bc`: newlines +are treated as statement terminators and `=` is assignment. Additionally, +`pbc` displays a prompt. This mode may be easier for beginners. + +Initially, the variables G1, G2, GT and Zr are represent groups associated with +a particular A pairing. + +An element is represented with a tree of integers, such as `[[1,2], 3]`, or +`4`. + +Assignments such as `variable := expression;` return the value of the variable. + +The arithmetic operators `+, -, /, *, ^` have the standard precedence. +The C comparison operators and ternary operator are available. + +Each statement should be terminated by a semicolon. + +Comments are the same as in (original) C, or begin with "#" and end at a +newline. + +Some of the pbc functions: + ++init_pairing_A()+:: +Set the variables G1, G2, GT and Zr to the groups in a particular A pairing: ++ + init_pairing_A(); ++ +Other sample pairings can be used by replacing `A` with one of `D, E, F, G`. + ++rnd(+'G'+)+:: +Returns a random element of an algebraic structure 'G', e.g: ++ + g := rnd(Zr); ++ +Synonym: `random`. + ++pairing(+'g, h'+)+:: +Returns the pairing applied to 'g' and 'h'. +The element 'g' must be an element of G1 and 'h' of G2, e.g: ++ + pairing(rnd(G1), rnd(G2)); + +'G'+(+'g'+)+:: +Maps an element 'g' to element of the field 'G', e.g: ++ + Zr(123); + GT([456, 789]); + +=== Parameter generation === + +Programs that generate pairing parameters are located in the `gen` +subdirectory. Some of the programs are already functional enough to be used to +find parameters for real applications. I need to write more documentation +first; for now, read the source! + +*listmnt*:: + Searches for discriminants D that lead to MNT curves with subgroups + of prime order. + +*genaparam*, *gena1param*, *gendparam*, *geneparam*, *genfparam*, *gengparam*:: + Prints parameters for a curve suitable for computing pairings of a given type. + The output can be fed to some of the other test programs. The programs + `gendparam` and `gengparam` should be given a discriminant as the first + argument. + +*hilbertpoly*:: + Prints the Hilbert polynomial for a given range of discriminants. Computing + the Hilbert polynomial is an intermediate step when generating type D + parameters. + +=== Example cryptosystems === + +In the `example` subdirectory there are various programs that read curve +parameters on standard input and perform computations that would be required in +a typical implementation of a pairing-based cryptosystem. Sample schemes +include: + +- Boneh-Lynn-Shacham short signatures +- Hess identity-based signatures +- Joux tripartite Diffie-Hellman +- Paterson identity-based signatures +- Yuan-Li identity-based authenticated key agreement +- Zhang-Kim identity-based blind/ring signatures +- Zhang-Safavi-Naini-Susilo signatures + +More work would be required to turn these programs into real applications. + +=== Benchmarks === + +I use the programs in the `benchmark` subdirectory to measure running times of +pairings, and also RSA decryptions. + +The `benchmark` program takes pairing parameters on standard input and reports +the average running time of the pairing over 10 runs, while `timersa` estimates +the time required to perform one 1024-bit RSA decryption. diff --git a/moon-abe/pbc-0.5.14/doc/contributors.txt b/moon-abe/pbc-0.5.14/doc/contributors.txt new file mode 100644 index 00000000..aa67c91f --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/contributors.txt @@ -0,0 +1,35 @@ +== Appendix A: Contributors == + +Ben Lynn wrote the original PBC library and documentation and is still +maintaining and developing it. + +Hovav Shacham wrote the multiexponentiation, sliding windows and preprocessed +exponentiation routines, Makefile improvements, and other enhancements. +He also helps administer the mailing list. + + +Joseph Cooley wrote the GNU build system files, +tested the library on Mac OS X, and added miscellaneous improvements. +Among other things, +pairings can be read from memory buffer and +most compile-time warnings were removed. + + +Rob Figueiredo and Roger Khazan wrote changes which allow the PBC library +to be compiled on Windows (via mingw). + + +Dmitry Kosolapov sent in manual corrections, and wrote +several cryptosystem demos. + + +John Bethencourt sent in many helpful patches, e.g. fixes that allow PBC to +work on 64-bit platforms. + + +Paul Miller reported bugs, manual corrections and also wrote +the Gentoo portage overlay for PBC. + + +If you're not mentioned here but should be, please let me know! +(blynn at cs dot stanford dot edu). diff --git a/moon-abe/pbc-0.5.14/doc/custom-nochunks.xsl b/moon-abe/pbc-0.5.14/doc/custom-nochunks.xsl new file mode 100644 index 00000000..49256ede --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/custom-nochunks.xsl @@ -0,0 +1,22 @@ +<?xml version='1.0'?> +<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" + xmlns:fo="http://www.w3.org/1999/XSL/Format" + version="1.0"> +<xsl:param name="html.stylesheet" select="'default.css'"/> +<xsl:param name="generate.toc" select="'book toc'"/> +<xsl:output method="html" encoding="UTF-8" indent="no" +doctype-public="-//W3C//DTD HTML 4.01 Transitional//EN" +/> +<xsl:template name="user.footer.navigation"> +<script type="text/javascript"> +var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www."); +document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E")); +</script> +<script type="text/javascript"> +try{ +var pageTracker = _gat._getTracker("UA-1901330-5"); +pageTracker._trackPageview(); +} catch(err) {} +</script> +</xsl:template> +</xsl:stylesheet> diff --git a/moon-abe/pbc-0.5.14/doc/custom-pretty.xsl b/moon-abe/pbc-0.5.14/doc/custom-pretty.xsl new file mode 100644 index 00000000..ab619ef6 --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/custom-pretty.xsl @@ -0,0 +1,32 @@ +<?xml version='1.0'?> +<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" + xmlns:fo="http://www.w3.org/1999/XSL/Format" + version="1.0"> +<xsl:param name="chunk.section.depth" select="1"></xsl:param> +<xsl:param name="chunk.first.sections" select="1"></xsl:param> +<xsl:param name="css.decoration" select="0"></xsl:param> +<xsl:param name="toc.list.type">ul</xsl:param> +<xsl:param name="chunker.output.encoding" select="'UTF-8'"></xsl:param> +<xsl:param name="chunker.output.doctype-public" select="'-//W3C//DTD HTML 4.01 Transitional//EN'"></xsl:param> +<!-- use tidy instead +<xsl:param name="chunker.output.indent" select="'yes'"></xsl:param> +--> +<xsl:param name="suppress.navigation" select="1"></xsl:param> +<xsl:param name="generate.toc" select="'book toc'"/> +<xsl:param name="html.stylesheet" select="'pretty.css'"/> + +<xsl:template name="user.footer.navigation"> +<script type="text/javascript" src="find_selflink.js"></script> +<script type="text/javascript"> +var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www."); +document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E")); +</script> +<script type="text/javascript"> +try{ +var pageTracker = _gat._getTracker("UA-1901330-5"); +pageTracker._trackPageview(); +} catch(err) {} +</script> +</xsl:template> + +</xsl:stylesheet> diff --git a/moon-abe/pbc-0.5.14/doc/custom.xsl b/moon-abe/pbc-0.5.14/doc/custom.xsl new file mode 100644 index 00000000..8fcac646 --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/custom.xsl @@ -0,0 +1,24 @@ +<?xml version='1.0'?> +<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" + xmlns:fo="http://www.w3.org/1999/XSL/Format" + version="1.0"> +<!-- +To chunk by chapter only: +<xsl:param name="chunk.section.depth" select="0"></xsl:param> +--> +<xsl:param name="chunker.output.encoding" select="'UTF-8'"></xsl:param> +<xsl:param name="chunker.output.doctype-public" select="'-//W3C//DTD HTML 4.01 Transitional//EN'"></xsl:param> + +<xsl:template name="user.footer.navigation"> +<script type="text/javascript"> +var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www."); +document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E")); +</script> +<script type="text/javascript"> +try{ +var pageTracker = _gat._getTracker("UA-1901330-5"); +pageTracker._trackPageview(); +} catch(err) {} +</script> +</xsl:template> +</xsl:stylesheet> diff --git a/moon-abe/pbc-0.5.14/doc/default.css b/moon-abe/pbc-0.5.14/doc/default.css new file mode 100644 index 00000000..b386f84d --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/default.css @@ -0,0 +1,71 @@ +body { + font-size: 90%; + font-family: verdana, arial, sans-serif; +} + +tt, code, pre, .type { + font-family: andale mono, courier new, courier, monospace; + font-size: 90%; +} + +.author { + display : none; +} + +.copyright { + display : none; +} + +div.TOC { + float: left; + width: 13em; + font-size: 90%; + + border: 1px solid #aaaaaa; + background-color: #f9f9f9; + padding: 0.17em; +} + +hr { + display: none; +} + +div.chapter, div.preface { + border-left: 13em solid white; + padding-left: 1em; +} + +h1.title { + border: 1px solid #aaaaaa; + background-color: #f9f9f9; + padding: 0.17em; +} + +div.chapter h1, div.preface h1 { + padding-top: 0.5em; + padding-bottom: 0.17em; + margin: 0; + font-weight: normal; + border-bottom: 1px solid #aaaaaa; +} + +h2 { + padding-top: 0.5em; + padding-bottom: 0.17em; + margin: 0; + font-weight: normal; + border-bottom: 1px solid #aaaaaa; +} + +.programlisting, .screen { + margin: 0; + border: 1px solid #aaaaaa; + background-color: #f9f9f9; + padding: 0.17em; + margin: 1em; + margin-right: 3em; +} + +.parameter { + font-style: italic; +} diff --git a/moon-abe/pbc-0.5.14/doc/elementfns.txt b/moon-abe/pbc-0.5.14/doc/elementfns.txt new file mode 100644 index 00000000..cadf78b0 --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/elementfns.txt @@ -0,0 +1,111 @@ +== Element functions == + +Elements of groups, rings and fields are stored in the +element_t+ data type. +Variables of this type must be initialized before use, and should be cleared +after they are no longer needed. + +The +element_+ functions must be used with caution. Just as division by zero +does not make sense for integers, some operations may not make sense for +particular elements. For example, in a ring, one cannot in general invert +elements. + +Another caveat is that many of these functions assume their arguments come from +the same ring, group or field. No implicit type casting is performed. + +For debug builds, turn on run-time checks by defining `PBC_DEBUG` before +including `pbc.h`: + + #define PBC_DEBUG + #include <pbc.h> + +Also, when `PBC_DEBUG` is defined, the following macros are active. +Normally they are replaced with empty statements. + +include::gen/debug.txt[] + +=== Initializing elements === + +When an element is initialized it is associated with an algebraic structure, +such as a particular finite field or elliptic curve group. + +We use G1 and G2 to denote the input groups to the pairing, and GT for the +output group. All have order r, and Zr means the ring of integers modulo r. +G1 is the smaller group (the group of points over the base field). With +symmetric pairings, G1 = G2. + +include::gen/einit.txt[] + +=== Assigning elements === + +These functions assign values to elements. When integers are assigned, +they are mapped to algebraic structures canonically if it makes sense +(e.g. rings and fields). + +include::gen/eassign.txt[] + +=== Converting elements === + +include::gen/econvert.txt[] + +=== Element arithmetic === + +Unless otherwise stated, all +element_t+ arguments to these functions must have +been initialized to be from the same algebraic structure. When one of these +functions expects its arguments to be from particular algebraic structures, +this is reflected in the name of the function. + +The addition and multiplication functions perform addition and multiplication +operations in rings and fields. For groups of points on an ellitpic curve, such +as the G1 and G2 groups associated with pairings, both addition and +multiplication represent the group operation (and similarly both 0 and 1 +represent the identity element). It is recommended that programs choose and +one convention and stick with it to avoid confusion. + +In contrast, the GT group is currently +implemented as a subgroup of a finite field, so only multiplicative operations +should be used for GT. + +include::gen/earith.txt[] + +=== Exponentiating elements === + +Exponentiation and multiexponentiation functions. If it is known in advance +that a particular element will be exponentiated several times in the future, +time can be saved in the long run by first calling the preprocessing function: + + element_pp_t g_pp; + element_pp_init(g_pp, g); + element_pp_pow(h, pow1, g_pp); // h = g^pow1 + element_pp_pow(h, pow2, g_pp); // h = g^pow2 + element_pp_pow(h, pow3, g_pp); // h = g^pow3 + element_pp_clear(g_pp); + +include::gen/epow.txt[] + +=== Comparing elements === + +These functions compare elements from the same algebraic structure. + +include::gen/ecmp.txt[] + +=== Element I/O === + +Functions for producing human-readable outputs for elements. +Converting elements to and from bytes are discussed later. + +include::gen/eio.txt[] + +=== Random elements === + +Only works for finite algebraic structures. Effect on polynomial rings, fields +of characteristic zero, etc. undefined. + +See <<randomref>> for how PBC gets random bits. + +include::gen/erandom.txt[] + +=== Element import/export === + +Functions for serializing and deserializing elements. + +include::gen/etrade.txt[] diff --git a/moon-abe/pbc-0.5.14/doc/extract b/moon-abe/pbc-0.5.14/doc/extract new file mode 100644 index 00000000..77a6a69a --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/extract @@ -0,0 +1,67 @@ +#!/usr/bin/gawk -f +# Extract GMP-style documentation from source using AsciiDoc format. +# Fragile: +# - requires function definition/declaration to end with ")\n" or ");" or ") {" +# - does not play nice with function pointer parameters + +# Look for the magic string "/*@manual " +/^\/\*@manual / { + outfile = "gen/" gensub(".*manual ", "", 1) ".txt" + print "Writing to " outfile + n = 0 + getline + # Stop at the line "*/". + while ($0 != "*/") { + a[n] = $0 + n++ + getline + } + +# Simple version with no markup: +# do { +# getline +# print +# } while (!match($0, ";") && !match($0, "{")) + +# Mark up bits of the function declaration with AsciiDoc, e.g: +# "int main(int argc, char *argv[]);" should become +# "int *main*('int argc', 'char *argv[]');" +# Also suppress "static inline". + getline + +# Handle variable declarations. + if (!match($0, "\\(")) { + s = gensub("([^ ]*);", "*\\1*", 1) # Bold variable name. +# Handle macro declarations. + } else if (match($0, "^#define")) { + s = gensub("^#define *(.*[^ ]) *\\\\$", "*\\1*", 1) +# Otherwise it's a function. + } else { + + sub("static inline ", "") + s = gensub("(\\w*)\\(", " *\\1*(", 1) # Bold function name. + s = gensub("\\((.*$)", "('\\1", 1, s) # First parameter. + gsub(", *", "', '", s) # Separating commas. + gsub("_ptr", "_t", s) +# Handle multi-line function declarations. + while (!match(s, ");") && !match(s, ") *$") && !match(s, ") *{")) { + getline + gsub("^ *", "") # Remove leading whitespace. + gsub(", *", "', '") # Commas again. + gsub("_ptr", "_t") + s = s $0 + } + s = gensub("(.*)\\)", "\\1')", 1, s) # Last parameter + gsub("_ptr", "_t", s) + gsub(")[^)]*$", ")", s); + } + + print s "\n" > outfile + if (n > 0) { + print "____" > outfile + for(i = 0; i < n; i++) { + print a[i] > outfile + } + print "____" > outfile + } +} diff --git a/moon-abe/pbc-0.5.14/doc/find_selflink.js b/moon-abe/pbc-0.5.14/doc/find_selflink.js new file mode 100644 index 00000000..db436db7 --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/find_selflink.js @@ -0,0 +1,37 @@ +// From my own website(!) +//TODO: only do this for links in the table of contents menu + +function find_selflink() { + var a = document.links; + var i = 0; + while (i < a.length) { + if (a[i].href == document.URL) { + var c; + var j; + var s_new = document.createElement("span"); + s_new.className = "currentlink"; + c = a[i].childNodes; + for (j=0; j<c.length; j++) { + s_new.appendChild(c[j]); + } + a[i].parentNode.replaceChild(s_new, a[i]); + } else { + i++; + } + + /* + if (a[i].href == document.URL) { + a[i].className = "currentlink"; + if (0) { + var s_new = document.createElement("span"); + s_new.className = "currentlink"; + s_new.appendChild(a[i]); + a[i].parentNode.replaceChild(s_new, a[i]); + } + } + i++; + */ + } +} + +find_selflink(); diff --git a/moon-abe/pbc-0.5.14/doc/index.txt b/moon-abe/pbc-0.5.14/doc/index.txt new file mode 100644 index 00000000..ccf0b503 --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/index.txt @@ -0,0 +1,13 @@ +== PBC library manual == + +Other editions: + +- link:../chunked/[Chunked HTML]: One HTML file per section, with no attempts + to make it easier to read. + +- link:../manual.html[Single HTML]: One big HTML file. I attemped to improve + its appearance. + +- link:../manual.pdf[PDF file]: Portable Document Format. + +- link:../manual.txt[text file] diff --git a/moon-abe/pbc-0.5.14/doc/internal.txt b/moon-abe/pbc-0.5.14/doc/internal.txt new file mode 100644 index 00000000..b2f217e3 --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/internal.txt @@ -0,0 +1,428 @@ +== 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. diff --git a/moon-abe/pbc-0.5.14/doc/macros.ad b/moon-abe/pbc-0.5.14/doc/macros.ad new file mode 100644 index 00000000..0b108e2b --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/macros.ad @@ -0,0 +1,9 @@ +[miscellaneous] +newline=\n + +[blockdef-passthrough] +delimiter=^@{4,}$ +subs=none + +[replacements] +sigma=σ diff --git a/moon-abe/pbc-0.5.14/doc/makeover b/moon-abe/pbc-0.5.14/doc/makeover new file mode 100644 index 00000000..39b807c1 --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/makeover @@ -0,0 +1,50 @@ +#!/bin/bash +gawk ' +/<div class="toc">/ { + print $0 + getline #TODO: check this is the <ul> line + print $0 + print "<li><a href=\".\">PBC Library Manual</a></li>" + getline + while (!match($0, "</div>")) { + print $0 + getline + } + print "</div>" + exit +} +' < manual/index.html > toc.tmp +for a in manual/*.html +do + if [ $a != "manual/index.html" ] + then +#add " - PBC" to titles of all pages + sed '/<\/title>/ s/<\/title>/ - PBC&/' -i $a + sed '/<body/{n; r toc.tmp +a <div class="content"> +} ' -i $a + sed '/^<\/body/i </div>' -i $a + fi +done + +gawk ' +/<div class="book"/ { + i = 0 + for(;;) { + getline + if (match($0, "<div")) i++; + else if (match($0, "</div")) { + i--; + if (i < 0) break; + } + } + sub("</div>","") +} +{ print } +' < manual/index.html | sed '/<body/{n; r toc.tmp +a <div class="content"> +r index.html +a </div> +} ' > tmp.tmp +mv tmp.tmp manual/index.html +rm toc.tmp diff --git a/moon-abe/pbc-0.5.14/doc/miscfns.txt b/moon-abe/pbc-0.5.14/doc/miscfns.txt new file mode 100644 index 00000000..5ea07a67 --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/miscfns.txt @@ -0,0 +1,43 @@ +== Other functions == + +Random number generation, memory allocation, logging. + +[[randomref]] +=== Random bits === + +The first time PBC is asked to generate a random number, +the library will try to open the file `/dev/urandom` as a +source of random bits. If this fails, PBC falls back to a deterministic +random number generator (which is of course completely useless for +cryptography). + +It is possible to change the file used for random bits. Also, explicitly +selecting the deterministic random number generator will +suppress the warning. + +On Windows, by default, PBC uses the Microsoft Crypto API to generate random +bits. + +include::gen/pbcrandom.txt[] + +=== Custom allocation === + +Like GMP, PBC can be instructed to use custom memory allocation functions. +This must be done before any memory allocation is performed, +usually at the beginning of a program before any other PBC functions have +been called. + +Also like GMP, the PBC wrappers around +malloc+ +and +realloc+ will print a message on standard error +and terminate program execution if the calls fail. +Replacements for these functions should act similarly. + +However, unlike GMP, PBC does not pass the number of bytes previously allocated +along with the pointer in calls to +realloc+ and ++free+. + +include::gen/alloc.txt[] + +=== Logging === + +include::gen/log.txt[] diff --git a/moon-abe/pbc-0.5.14/doc/pairingfns.txt b/moon-abe/pbc-0.5.14/doc/pairingfns.txt new file mode 100644 index 00000000..4ea4bf13 --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/pairingfns.txt @@ -0,0 +1,69 @@ +== Pairing functions == + +An application should first initialize a pairing object. This causes PBC +to setup curves, groups and other mathematical miscellany. After that, +elements can be initialized and manipulated for cryptographic operations. + +Parameters for various pairings are included with the PBC library distribution +in the `param` subdirectory, and some are suitable for cryptographic use. Some +programs in the `gen` subdirectory may be used to generate parameters (see +<<bundlechap>>). Also, see the PBC website for many more +pairing parameters. + +Pairings involve three groups of prime order. The PBC library calls them G1, +G2, and GT, and calls the order r. The pairing is a bilinear map that takes two +elements as input, one from G1 and one from G2, and outputs an element of GT. + +The elements of G2 are at least as long as G1; G1 is guaranteed to be the +shorter of the two. Sometimes G1 and G2 are the same group (i.e. the pairing +is symmetric) so their elements can be mixed freely. In this case the ++pairing_is_symmetric+ function returns 1. + +Bilinear pairings are stored in the data type +pairing_t+. Functions that +operate on them start with +pairing_+. + +=== Initializing pairings === + +To initialize a pairing from an ASCIIZ string: + + pairing_t pairing; + pairing_init_set_str(pairing, s); // Where s is a char *. + +The string 's' holds _pairing parameters_ in a text format. The +param+ +subdirectory contains several examples. + +Alternatively, call: + + pairing_t pairing; + pairing_init_pbc_param(pairing, param); + +where 'param' is an initialized `pbc_param_t` (see <<paramchap>>). + +include::gen/pairing_init.txt[] + +=== Applying pairings === + +The function `pairing_apply` can be called to apply a bilinear map. The order +of the inputs is important. The first, which holds the output, must be from the +group GT. The second must be from G1, the third from G2, and the fourth must be +the +pairing_t+ variable that relates them. + +In some applications, the programmer may know that many pairings with the same +G1 input will be computed. If so, preprocessing should be used to avoid +repeating many calculations saving time in the long run. A variable of type ++pairing_pp_t+ should be declared, initialized with the fixed G1 element, and +then used to compute pairings: + + pairing_pp_t pp; + pairing_pp_init(pp, x, pairing); // x is some element of G1 + pairing_pp_apply(r1, y1, pp); // r1 = e(x, y1) + pairing_pp_apply(r2, y2, pp); // r2 = e(x, y2) + pairing_pp_clear(pp); // don't need pp anymore + +Never mix and match G1, G2, and GT groups from different pairings. + +include::gen/pairing_apply.txt[] + +=== Other pairing functions === + +include::gen/pairing_op.txt[] diff --git a/moon-abe/pbc-0.5.14/doc/paramfns.txt b/moon-abe/pbc-0.5.14/doc/paramfns.txt new file mode 100644 index 00000000..74b1abff --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/paramfns.txt @@ -0,0 +1,37 @@ +[[paramchap]] +== Param functions == + +Pairings are initialized from _pairing parameters_, which are objects of type +`pbc_param_t`. Some applications can ignore this data type because +`pairing_init_set_str()` handles it behind the scenes: it reads a string as a +`pbc_param_t`, then initializes a pairing with these parameters. + +include::gen/param.txt[] + +[[paramgenchap]] +=== Param generation === + +These were used to prepare the sample parameters in the +param+ subdirectory. + +We label the pairing families with capital letters roughly in the order of +discovery, so we can refer to them easily. Type A is fastest. Type D is a good +choice when elements should be short but is slower. Type F has even shorter +elements but is slower still. The speed differences are hardware-dependent, and +also change when preprocessing is used. Type B and C are unimplemented. + +The +pbc_cm_t+ data type holds CM parameters that are used to generate type D +and G curves. + +include::gen/cminfo.txt[] + +include::gen/aparam.txt[] + +include::gen/a1param.txt[] + +include::gen/dparam.txt[] + +include::gen/eparam.txt[] + +include::gen/fparam.txt[] + +include::gen/gparam.txt[] diff --git a/moon-abe/pbc-0.5.14/doc/preface.txt b/moon-abe/pbc-0.5.14/doc/preface.txt new file mode 100644 index 00000000..ec8a3373 --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/preface.txt @@ -0,0 +1,18 @@ += PBC Library Manual 0.5.14 = +Ben Lynn +2006 + +== Preface == + +The PBC library is a free portable C library allowing the rapid prototyping of +pairing-based cryptosystems. It provides an abstract interface to a cyclic +group with a bilinear pairing, insulating the programmer from mathematical +details. Knowledge of elliptic curves is optional. + +The PBC library is built on top of the GMP library, and the PBC API is strongly +influenced by the GMP API. Accordingly, this manual tries to imitate the look +and feel of the GMP manual. + +The PBC library homepage: http://crypto.stanford.edu/pbc/[http://crypto.stanford.edu/pbc/] + +The GMP library homepage: http://www.swox.com/gmp/[http://www.swox.com/gmp/] diff --git a/moon-abe/pbc-0.5.14/doc/pretty.css b/moon-abe/pbc-0.5.14/doc/pretty.css new file mode 100644 index 00000000..69502083 --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/pretty.css @@ -0,0 +1,97 @@ +body { + font-size: 90%; + font-family: verdana, arial, sans-serif; +} + +tt, code, pre, .type { + font-family: andale mono, courier new, courier, monospace; + font-size: 90%; +} + +/* Based on http://phrogz.net/CSS/columns3.html */ +div.toc { + float: left; + margin: 0; + padding: 0; + padding-top: 0.5em; + border: 0; + width: 13em; + + background-color: #f9f9f9; + margin-right:1em; +} + +div.content { + margin: 0; + padding: 0; + + /* won't match if font is smaller in toc */ + border-left: 13em solid #f9f9f9; + padding-left: 1em; +} + +div.content:after { + content:' '; + clear:both; + display:block; + height:0; + overflow:hidden +} + +div.footer { + clear:left; +} + +div.toc ul { + list-style: none; + padding: 0; + margin: 0; +} + +div.toc li ul a, li ul span.currentlink +{ + font-weight: normal; + font-size: 90%; + padding-left: 2em; +} + +div.toc a, span.currentlink{ + display:block; + text-decoration: none; + padding-left: 0.5em; + color: #0000aa; +} + +span.currentlink { + text-decoration: none; + background-color: #aaaaf9; +} + +div.toc a:visited { + color: #0000aa; +} + +div.toc a:hover { + background-color: #f9f9aa; +} + +.literallayout { + margin: 0; + border: 1px solid #aaaaaa; + background-color: #f9f9f9; + padding: 0.17em; + margin: 1em; + margin-right: 3em; +} + +h1, h2, h3, h4, h5, h6 { + padding-bottom: 0.17em; + margin: 0; + font-weight: normal; + color: black; + border-bottom: 1px solid #aaaaaa; +} + +h3, h4, h5, h6 { + border-bottom: 0; +} diff --git a/moon-abe/pbc-0.5.14/doc/quickstart.txt b/moon-abe/pbc-0.5.14/doc/quickstart.txt new file mode 100644 index 00000000..2f94e46e --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/quickstart.txt @@ -0,0 +1,69 @@ +== Installing PBC == + +The PBC library needs http://www.swox.com/gmp/[the GMP library]. + +This build system has been tested and works on Linux and Mac OS X with a +fink installation. + + $ ./configure + $ make + $ make install + +On Windows, the configure command requires a couple of options: + + $ ./configure -disable-static -enable-shared + +By default the library is installed in `/usr/local/lib`. On some systems, this +may not be in the library path. One way to fix this is to edit +`/etc/ld.so.conf` and run `ldconfig`. + +=== Simple Makefile === + +For speed and simplicity, I use `simple.make` during development. +Naturally it is less portable. + + $ make -f simple.make + +PBC uses some GNU C extensions such as nested functions. + +[[pbcintro]] +=== Quick start === + +We shall use the following notation. For our purposes, the pairing is a +bilinear map from two cyclic groups, G1 and G2 to a third group GT, where each +group has prime order r. + +Run `pbc/pbc` and type: + + g := rnd(G1); + g; + +The first line generates a random element g of the group G1, +while the second prints out the value of g. (The syntax was influenced +by `bc`, an arbitrary precision calculator.) +Next, enter: + + h := rnd(G2); + h; + +This assigns h to a random element of the group G2. Actually, the default +pairing `pbc` uses is symmetric so G1 and G2 are in fact the same group, but in +general they are distinct. To compute the pairing applied to g and h, type: + + pairing(g,h); + +The order of both g and h is r. Let's generate two random numbers between +1 and r: + + a := rnd(Zr); + b := rnd(Zr); + +By bilinearity, the resulting output of both of these lines should be +identical: + + pairing(g^a,h^b); + pairing(g,h)^(a*b); + +This program has <<pbcref, other features>> but the commands shown here should +be enough to quickly and interactively experiment with many pairing-based +cryptosystems using real numbers. diff --git a/moon-abe/pbc-0.5.14/doc/security.txt b/moon-abe/pbc-0.5.14/doc/security.txt new file mode 100644 index 00000000..c59cf4ba --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/security.txt @@ -0,0 +1,45 @@ +== Security issues == + +Potential problems for the paranoid. + +*Truncated hashes* + +For points on an elliptic curve over the base field, +element_from_hash()+ +will truncate the input hash until it can represent an x-coordinate in that +field. (PBC then computes a corresponding y-coordinate.) Ideally the hash +length should be smaller than size of the base field and also the size of the +elliptic curve group. + +Hashing to elements in field extensions does not take advantage of the fact +that the extension has more elements than the base field. I intend to rewrite +the code so that for a degree n extension code, PBC splits the hash into n +parts and determine each polynomial coefficient from one ofthe pieces. At the +moment every coefficient is the same and depends on the whole hash. + +This is harmless for the base field, because all the pairing types implemented +so far use an integer mod ring as the base field, rather than an extension of +some low characteristic field. + +*Zeroed memory* + +Unlike OpenSSL, there are no functions to zero memory locations used in +sensitive computations. To some extent, one can use +element_random()+ to +overwrite data. + +*PRNG determinism* + +On platforms without `/dev/urandom` PBC falls back on a deterministic +pseudo-random number generator, except on Windows where it attempts to +use the Microsoft Crypto API. + +Also, `/dev/urandom` differs from `/dev/random`. A quote from its manpage: + +____ +A read from the /dev/urandom device will not block waiting for more +entropy. As a result, if there is not sufficient entropy in the +entropy pool, the returned values are theoretically vulnerable to a +cryptographic attack on the algorithms used by the driver. Knowledge +of how to do this is not available in the current non-classified literature, +but it is theoretically possible that such an attack may exist. +If this is a concern in your application, use /dev/random instead. +____ diff --git a/moon-abe/pbc-0.5.14/doc/sigex.txt b/moon-abe/pbc-0.5.14/doc/sigex.txt new file mode 100644 index 00000000..dcfc8d5e --- /dev/null +++ b/moon-abe/pbc-0.5.14/doc/sigex.txt @@ -0,0 +1,155 @@ +== Tutorial == + +This chapter walks through how one might implement the +Boneh-Lynn-Shacham (BLS) signature scheme using the PBC library. +It is based on the file `example/bls.c`. + +We have three groups 'G1', 'G2', 'GT' of prime order 'r', and a bilinear map +'e' that takes an element from 'G1' and an element from 'G2', and outputs an +element of 'GT'. We publish these along with the system parameter 'g', which is +a randomly chosen element of 'G2'. + +Alice wishes to sign a message. She generates her public and private keys as +follows. Her private key is a random element 'x' of 'Zr', and her corresponding +public key is 'g'^'x'^. + +To sign a message, Alice hashes the message to some element +'h' of 'G1', and then outputs the signature 'h'^'x'^. + +To verify a signature sigma, Bob checks that +'e'('h','g'^'x'^) = 'e'(sigma, 'g'). + +We now translate the above to C code using the PBC library. + +=== BLS signatures === + +First we include `pbc/pbc.h`: + + #include <pbc.h> + +Next we initialize a pairing: + + pairing_t pairing; + char param[1024]; + size_t count = fread(param, 1, 1024, stdin); + if (!count) pbc_die("input error"); + pairing_init_set_buf(pairing, param, count); + +Later we give pairing parameters to our program on standard input. Any file in +the `param` subdirectory will suffice, for example: + + $ bls < param/a.param + +We shall need several +element_t+ variables to hold the system parameters, keys +and other quantities. We declare them and initialize them, +.... +element_t g, h; +element_t public_key, secret_key; +element_t sig; +element_t temp1, temp2; + +element_init_G2(g, pairing); +element_init_G2(public_key, pairing); +element_init_G1(h, pairing); +element_init_G1(sig, pairing); +element_init_GT(temp1, pairing); +element_init_GT(temp2, pairing); +element_init_Zr(secret_key, pairing); +.... +generate system parameters, + + element_random(g); + +generate a private key, + + element_random(secret_key); + +and the corresponding public key. + + element_pow_zn(public_key, g, secret_key); + +When given a message to sign, we first compute its hash, using some standard +hash algorithm. Many libraries can do this, and this operation does not +involve pairings, so PBC does not provide functions for this step. For this +example, and our message has already been hashed, possibly using another +library. + +Say the message hash is "ABCDEF" (a 48-bit hash). We map these bytes to an +element h of G1, + + element_from_hash(h, "ABCDEF", 6); + +then sign it: + + element_pow_zn(sig, h, secret_key); + +To verify this signature, we compare the +outputs of the pairing applied to the signature and system parameter, +and the pairing applied to the message hash and public key. +If the pairing outputs match then the signature is valid. + +.... +pairing_apply(temp1, sig, g, pairing); +pairing_apply(temp2, h, public_key, pairing); +if (!element_cmp(temp1, temp2)) { + printf("signature verifies\n"); +} else { + printf("signature does not verify\n"); +} +.... + +=== Import/export === + +To be useful, at some stage the signature must be converted +to bytes for storage or transmission: + + int n = pairing_length_in_bytes_compressed_G1(pairing); + // Alternatively: + // int n = element_length_in_bytes_compressed(sig); + unsigned char *data = malloc(n); + element_to_bytes_compressed(data, sig); + +On the other end, the signature must be decompressed: + + element_from_bytes_compressed(sig, data); + +Eliding +_compressed+ in the above code +will also work but the buffer 'data' will be roughly twice as large. + +We can save more space by using the 'x'-coordinate of the signature only + + int n = pairing_length_in_bytes_x_only_G1(pairing); + // Alternative: + // int n = element_length_in_bytes_x_only(sig); + unsigned char *data = malloc(n); + element_to_bytes_compressed(data, sig); + +but then there is a complication during verification since two different +points have the same 'x'-coordinate. One way to solve this problem is to +guess one point and try to verify. If that fails, we try the other. +It can be shown that the pairing outputs of the two points are inverses +of each other, avoiding the need to compute a pairing the second time. +(In fact, there are even better ways to handle this.) +.... +int n = pairing_length_in_bytes_x_only_G1(pairing); +//int n = element_length_in_bytes_x_only(sig); +unsigned char *data = malloc(n); + +element_to_bytes_x_only(data, sig); + +element_from_bytes_x_only(sig, data) + +pairing_apply(temp1, sig, g, pairing); +pairing_apply(temp2, h, public_key, pairing); + +if (!element_cmp(temp1, temp2)) { + printf("signature verifies on first guess\n"); +} else { + element_invert(temp1, temp1); + if (!element_cmp(temp1, temp2)) { + printf("signature verifies on second guess\n"); + } else { + printf("signature does not verify\n"); + } +} +.... |