From fca74d4bc3569506a6659880a89aa009dc11f552 Mon Sep 17 00:00:00 2001 From: wukong Date: Mon, 23 Nov 2015 17:48:48 +0100 Subject: moon-abe cleanup Change-Id: Ie1259856db03f0b9e80de3e967ec6bd1f03191b3 --- moon-abe/pbc-0.5.14/doc/Makefile | 49 ---- moon-abe/pbc-0.5.14/doc/basics.txt | 58 ---- moon-abe/pbc-0.5.14/doc/bundle.txt | 119 -------- moon-abe/pbc-0.5.14/doc/contributors.txt | 35 --- moon-abe/pbc-0.5.14/doc/custom-nochunks.xsl | 22 -- moon-abe/pbc-0.5.14/doc/custom-pretty.xsl | 32 --- moon-abe/pbc-0.5.14/doc/custom.xsl | 24 -- moon-abe/pbc-0.5.14/doc/default.css | 71 ----- moon-abe/pbc-0.5.14/doc/elementfns.txt | 111 -------- moon-abe/pbc-0.5.14/doc/extract | 67 ----- moon-abe/pbc-0.5.14/doc/find_selflink.js | 37 --- moon-abe/pbc-0.5.14/doc/index.txt | 13 - moon-abe/pbc-0.5.14/doc/internal.txt | 428 ---------------------------- moon-abe/pbc-0.5.14/doc/macros.ad | 9 - moon-abe/pbc-0.5.14/doc/makeover | 50 ---- moon-abe/pbc-0.5.14/doc/miscfns.txt | 43 --- moon-abe/pbc-0.5.14/doc/pairingfns.txt | 69 ----- moon-abe/pbc-0.5.14/doc/paramfns.txt | 37 --- moon-abe/pbc-0.5.14/doc/preface.txt | 18 -- moon-abe/pbc-0.5.14/doc/pretty.css | 97 ------- moon-abe/pbc-0.5.14/doc/quickstart.txt | 69 ----- moon-abe/pbc-0.5.14/doc/security.txt | 45 --- moon-abe/pbc-0.5.14/doc/sigex.txt | 155 ---------- 23 files changed, 1658 deletions(-) delete mode 100644 moon-abe/pbc-0.5.14/doc/Makefile delete mode 100644 moon-abe/pbc-0.5.14/doc/basics.txt delete mode 100644 moon-abe/pbc-0.5.14/doc/bundle.txt delete mode 100644 moon-abe/pbc-0.5.14/doc/contributors.txt delete mode 100644 moon-abe/pbc-0.5.14/doc/custom-nochunks.xsl delete mode 100644 moon-abe/pbc-0.5.14/doc/custom-pretty.xsl delete mode 100644 moon-abe/pbc-0.5.14/doc/custom.xsl delete mode 100644 moon-abe/pbc-0.5.14/doc/default.css delete mode 100644 moon-abe/pbc-0.5.14/doc/elementfns.txt delete mode 100644 moon-abe/pbc-0.5.14/doc/extract delete mode 100644 moon-abe/pbc-0.5.14/doc/find_selflink.js delete mode 100644 moon-abe/pbc-0.5.14/doc/index.txt delete mode 100644 moon-abe/pbc-0.5.14/doc/internal.txt delete mode 100644 moon-abe/pbc-0.5.14/doc/macros.ad delete mode 100644 moon-abe/pbc-0.5.14/doc/makeover delete mode 100644 moon-abe/pbc-0.5.14/doc/miscfns.txt delete mode 100644 moon-abe/pbc-0.5.14/doc/pairingfns.txt delete mode 100644 moon-abe/pbc-0.5.14/doc/paramfns.txt delete mode 100644 moon-abe/pbc-0.5.14/doc/preface.txt delete mode 100644 moon-abe/pbc-0.5.14/doc/pretty.css delete mode 100644 moon-abe/pbc-0.5.14/doc/quickstart.txt delete mode 100644 moon-abe/pbc-0.5.14/doc/security.txt delete mode 100644 moon-abe/pbc-0.5.14/doc/sigex.txt (limited to 'moon-abe/pbc-0.5.14/doc') diff --git a/moon-abe/pbc-0.5.14/doc/Makefile b/moon-abe/pbc-0.5.14/doc/Makefile deleted file mode 100644 index 0fdaa41c..00000000 --- a/moon-abe/pbc-0.5.14/doc/Makefile +++ /dev/null @@ -1,49 +0,0 @@ -.PHONY: target clean sync gendoc - -target: $(TARGETS) - -TARGETS:=manual.html manual.txt manual.pdf manual/index.html chunked/index.html - -TXTFILES:=preface.txt quickstart.txt basics.txt sigex.txt \ - pairingfns.txt elementfns.txt paramfns.txt miscfns.txt \ - bundle.txt internal.txt security.txt contributors.txt - -GENFILES:=gen/*.txt - -gendoc $(GENFILES) : ../*/*.h extract - -rm $(GENFILES) - -mkdir gen - cat `grep -l '\/\*@manual' ../*/*.h` | ./extract - for a in gen/*.*.txt; do b=$${a%.*.txt}.txt; cat $$a $$b > tmp; mv tmp $$b ; rm $$a; done - -manual.xml: $(TXTFILES) $(GENFILES) - ( for FILE in $(TXTFILES) ; do cat $$FILE ; echo ; done ) | asciidoc -f macros.ad -d book -b docbook - > $@ - -chunked/index.html : manual.xml custom.xsl - xmlto -o chunked -m custom.xsl html manual.xml - -index.html : index.txt - asciidoc -s $^ - -manual/index.html: manual.xml custom-pretty.xsl pretty.css index.html - xmlto -m custom-pretty.xsl -o manual html manual.xml - sed -i 's/xmlns:fo[^ ]*//g' manual/*.html - -ls manual/*.html | xargs -n 1 tidy -utf8 -m -i -q - ./makeover - cp find_selflink.js pretty.css manual/ - -manual.html : manual.xml custom-nochunks.xsl - xmlto -m custom-nochunks.xsl html-nochunks manual.xml - -tidy -utf8 -imq $@ - -manual.txt : manual.html - html2text -nobs -style pretty manual.html > manual.txt - -manual.pdf: manual.xml - docbook2pdf manual.xml - -clean: - -rm -rf manual.xml manual.html manual chunked index.html - -sync: $(TARGETS) - rsync -r manual manual.html manual.txt chunked manual.pdf blynn@xenon.stanford.edu:pbc/ diff --git a/moon-abe/pbc-0.5.14/doc/basics.txt b/moon-abe/pbc-0.5.14/doc/basics.txt deleted file mode 100644 index c9549f72..00000000 --- a/moon-abe/pbc-0.5.14/doc/basics.txt +++ /dev/null @@ -1,58 +0,0 @@ -=== Basics === - -Programs using the PBC library should include the file `pbc.h`: - - #include - -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 deleted file mode 100644 index 13256d83..00000000 --- a/moon-abe/pbc-0.5.14/doc/bundle.txt +++ /dev/null @@ -1,119 +0,0 @@ -[[bundlechap]] -== Bundled programs == - -Several binaries and curve parameters are bundled with the PBC library, -such as <>. - -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 deleted file mode 100644 index aa67c91f..00000000 --- a/moon-abe/pbc-0.5.14/doc/contributors.txt +++ /dev/null @@ -1,35 +0,0 @@ -== 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 deleted file mode 100644 index 49256ede..00000000 --- a/moon-abe/pbc-0.5.14/doc/custom-nochunks.xsl +++ /dev/null @@ -1,22 +0,0 @@ - - - - - - - - - - diff --git a/moon-abe/pbc-0.5.14/doc/custom-pretty.xsl b/moon-abe/pbc-0.5.14/doc/custom-pretty.xsl deleted file mode 100644 index ab619ef6..00000000 --- a/moon-abe/pbc-0.5.14/doc/custom-pretty.xsl +++ /dev/null @@ -1,32 +0,0 @@ - - - - - -ul - - - - - - - - - - - - - - diff --git a/moon-abe/pbc-0.5.14/doc/custom.xsl b/moon-abe/pbc-0.5.14/doc/custom.xsl deleted file mode 100644 index 8fcac646..00000000 --- a/moon-abe/pbc-0.5.14/doc/custom.xsl +++ /dev/null @@ -1,24 +0,0 @@ - - - - - - - - - - - diff --git a/moon-abe/pbc-0.5.14/doc/default.css b/moon-abe/pbc-0.5.14/doc/default.css deleted file mode 100644 index b386f84d..00000000 --- a/moon-abe/pbc-0.5.14/doc/default.css +++ /dev/null @@ -1,71 +0,0 @@ -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 deleted file mode 100644 index cadf78b0..00000000 --- a/moon-abe/pbc-0.5.14/doc/elementfns.txt +++ /dev/null @@ -1,111 +0,0 @@ -== 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 - -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 <> 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 deleted file mode 100644 index 77a6a69a..00000000 --- a/moon-abe/pbc-0.5.14/doc/extract +++ /dev/null @@ -1,67 +0,0 @@ -#!/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 deleted file mode 100644 index db436db7..00000000 --- a/moon-abe/pbc-0.5.14/doc/find_selflink.js +++ /dev/null @@ -1,37 +0,0 @@ -// 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; jfield = 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 deleted file mode 100644 index 0b108e2b..00000000 --- a/moon-abe/pbc-0.5.14/doc/macros.ad +++ /dev/null @@ -1,9 +0,0 @@ -[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 deleted file mode 100644 index 39b807c1..00000000 --- a/moon-abe/pbc-0.5.14/doc/makeover +++ /dev/null @@ -1,50 +0,0 @@ -#!/bin/bash -gawk ' -/
/ { - print $0 - getline #TODO: check this is the
")) { - print $0 - getline - } - print "" - 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 '/ -} ' -i $a - sed '/^<\/body/i ' -i $a - fi -done - -gawk ' -/
","") -} -{ print } -' < manual/index.html | sed '/ -r index.html -a
-} ' > 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 deleted file mode 100644 index 5ea07a67..00000000 --- a/moon-abe/pbc-0.5.14/doc/miscfns.txt +++ /dev/null @@ -1,43 +0,0 @@ -== 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 deleted file mode 100644 index 4ea4bf13..00000000 --- a/moon-abe/pbc-0.5.14/doc/pairingfns.txt +++ /dev/null @@ -1,69 +0,0 @@ -== 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 -<>). 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 <>). - -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 deleted file mode 100644 index 74b1abff..00000000 --- a/moon-abe/pbc-0.5.14/doc/paramfns.txt +++ /dev/null @@ -1,37 +0,0 @@ -[[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 deleted file mode 100644 index ec8a3373..00000000 --- a/moon-abe/pbc-0.5.14/doc/preface.txt +++ /dev/null @@ -1,18 +0,0 @@ -= 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 deleted file mode 100644 index 69502083..00000000 --- a/moon-abe/pbc-0.5.14/doc/pretty.css +++ /dev/null @@ -1,97 +0,0 @@ -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 deleted file mode 100644 index 2f94e46e..00000000 --- a/moon-abe/pbc-0.5.14/doc/quickstart.txt +++ /dev/null @@ -1,69 +0,0 @@ -== 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 <> 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 deleted file mode 100644 index c59cf4ba..00000000 --- a/moon-abe/pbc-0.5.14/doc/security.txt +++ /dev/null @@ -1,45 +0,0 @@ -== 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 deleted file mode 100644 index dcfc8d5e..00000000 --- a/moon-abe/pbc-0.5.14/doc/sigex.txt +++ /dev/null @@ -1,155 +0,0 @@ -== 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 - -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"); - } -} -.... -- cgit 1.2.3-korg