aboutsummaryrefslogtreecommitdiffstats
path: root/moon-abe/pbc-0.5.14/arith/dlog.c
diff options
context:
space:
mode:
authorWuKong <rebirthmonkey@gmail.com>2015-09-04 09:25:34 +0200
committerWuKong <rebirthmonkey@gmail.com>2015-09-04 09:25:34 +0200
commit3baeb11a8fbcfcdbc31976d421f17b85503b3ecd (patch)
tree04891d88c1127148f1b390b5a24414e85b270aee /moon-abe/pbc-0.5.14/arith/dlog.c
parent67c5b73910f5fc437429c356978081b252a59480 (diff)
init attribute-based encryption
Change-Id: Iba1a3d722110abf747a0fba366f3ebc911d25b25
Diffstat (limited to 'moon-abe/pbc-0.5.14/arith/dlog.c')
-rw-r--r--moon-abe/pbc-0.5.14/arith/dlog.c187
1 files changed, 187 insertions, 0 deletions
diff --git a/moon-abe/pbc-0.5.14/arith/dlog.c b/moon-abe/pbc-0.5.14/arith/dlog.c
new file mode 100644
index 00000000..f77df1b7
--- /dev/null
+++ b/moon-abe/pbc-0.5.14/arith/dlog.c
@@ -0,0 +1,187 @@
+// Brute force and Pollard rho discrete log algorithms.
+
+#include <stdarg.h>
+#include <stdint.h> // for intptr_t
+#include <stdio.h>
+#include <gmp.h>
+#include "pbc_utils.h"
+#include "pbc_field.h"
+#include "pbc_memory.h"
+#include "misc/darray.h"
+
+struct snapshot_s {
+ element_t a;
+ element_t b;
+ element_t snark;
+};
+typedef struct snapshot_s *snapshot_ptr;
+
+static void record(element_t asum, element_t bsum, element_t snark,
+ darray_t hole, mpz_t counter) {
+ snapshot_ptr ss = pbc_malloc(sizeof(struct snapshot_s));
+ element_init_same_as(ss->a, asum);
+ element_init_same_as(ss->b, bsum);
+ element_init_same_as(ss->snark, snark);
+ element_set(ss->a, asum);
+ element_set(ss->b, bsum);
+ element_set(ss->snark, snark);
+ darray_append(hole, ss);
+ element_printf("snark %Zd: %B\n", counter, snark);
+}
+
+// g, h in some group of order r
+// finds x such that g^x = h
+// will hang if no such x exists
+// x in some field_t that set_mpz makes sense for
+void element_dlog_brute_force(element_t x, element_t g, element_t h) {
+ element_t g0;
+ mpz_t count;
+
+ mpz_init(count);
+ element_init_same_as(g0, g);
+
+ element_set(g0, g);
+ mpz_set_ui(count, 1);
+ while (element_cmp(g0, h)) {
+ element_mul(g0, g0, g);
+//element_printf("g0^%Zd = %B\n", count, g0);
+ mpz_add_ui(count, count, 1);
+ }
+ element_set_mpz(x, count);
+ mpz_clear(count);
+ element_clear(g0);
+}
+
+// x in Z_r, g, h in some group of order r
+// finds x such that g^x = h
+void element_dlog_pollard_rho(element_t x, element_t g, element_t h) {
+// see Blake, Seroussi and Smart
+// only one snark for this implementation
+ int i, s = 20;
+ field_ptr Zr = x->field, G = g->field;
+ element_t asum;
+ element_t bsum;
+ element_t a[s];
+ element_t b[s];
+ element_t m[s];
+ element_t g0, snark;
+ darray_t hole;
+ int interval = 5;
+ mpz_t counter;
+ int found = 0;
+
+ mpz_init(counter);
+ element_init(g0, G);
+ element_init(snark, G);
+ element_init(asum, Zr);
+ element_init(bsum, Zr);
+ darray_init(hole);
+ //set up multipliers
+ for (i = 0; i < s; i++) {
+ element_init(a[i], Zr);
+ element_init(b[i], Zr);
+ element_init(m[i], G);
+ element_random(a[i]);
+ element_random(b[i]);
+ element_pow_zn(g0, g, a[i]);
+ element_pow_zn(m[i], h, b[i]);
+ element_mul(m[i], m[i], g0);
+ }
+
+ element_random(asum);
+ element_random(bsum);
+ element_pow_zn(g0, g, asum);
+ element_pow_zn(snark, h, bsum);
+ element_mul(snark, snark, g0);
+
+ record(asum, bsum, snark, hole, counter);
+ for (;;) {
+ int len = element_length_in_bytes(snark);
+ unsigned char *buf = pbc_malloc(len);
+ unsigned char hash = 0;
+
+ element_to_bytes(buf, snark);
+ for (i = 0; i < len; i++) {
+ hash += buf[i];
+ }
+ i = hash % s;
+ pbc_free(buf);
+
+ element_mul(snark, snark, m[i]);
+ element_add(asum, asum, a[i]);
+ element_add(bsum, bsum, b[i]);
+
+ for (i = 0; i < hole->count; i++) {
+ snapshot_ptr ss = hole->item[i];
+ if (!element_cmp(snark, ss->snark)) {
+ element_sub(bsum, bsum, ss->b);
+ element_sub(asum, ss->a, asum);
+ //answer is x such that x * bsum = asum
+ //complications arise if gcd(bsum, r) > 1
+ //which can happen if r is not prime
+ if (!mpz_probab_prime_p(Zr->order, 10)) {
+ mpz_t za, zb, zd, zm;
+
+ mpz_init(za);
+ mpz_init(zb);
+ mpz_init(zd);
+ mpz_init(zm);
+
+ element_to_mpz(za, asum);
+ element_to_mpz(zb, bsum);
+ mpz_gcd(zd, zb, Zr->order);
+ mpz_divexact(zm, Zr->order, zd);
+ mpz_divexact(zb, zb, zd);
+ //if zd does not divide za there is no solution
+ mpz_divexact(za, za, zd);
+ mpz_invert(zb, zb, zm);
+ mpz_mul(zb, za, zb);
+ mpz_mod(zb, zb, zm);
+ do {
+ element_pow_mpz(g0, g, zb);
+ if (!element_cmp(g0, h)) {
+ element_set_mpz(x, zb);
+ break;
+ }
+ mpz_add(zb, zb, zm);
+ mpz_sub_ui(zd, zd, 1);
+ } while (mpz_sgn(zd));
+ mpz_clear(zm);
+ mpz_clear(za);
+ mpz_clear(zb);
+ mpz_clear(zd);
+ } else {
+ element_div(x, asum, bsum);
+ }
+ found = 1;
+ break;
+ }
+ }
+ if (found) break;
+
+ mpz_add_ui(counter, counter, 1);
+ if (mpz_tstbit(counter, interval)) {
+ record(asum, bsum, snark, hole, counter);
+ interval++;
+ }
+ }
+
+ for (i = 0; i < s; i++) {
+ element_clear(a[i]);
+ element_clear(b[i]);
+ element_clear(m[i]);
+ }
+ element_clear(g0);
+ element_clear(snark);
+ for (i = 0; i < hole->count; i++) {
+ snapshot_ptr ss = hole->item[i];
+ element_clear(ss->a);
+ element_clear(ss->b);
+ element_clear(ss->snark);
+ pbc_free(ss);
+ }
+ darray_clear(hole);
+ element_clear(asum);
+ element_clear(bsum);
+ mpz_clear(counter);
+}