16 files changed, 802 insertions, 104 deletions

diff --git a/src/exhaustive/ansi.c b/src/exhaustive/ansi.c
index 762ffb7..d870d76 100644
--- a/src/exhaustive/ansi.c
+++ b/src/exhaustive/ansi.c
@@ -9,6 +9,7 @@
 #include "io/output.h"
 #include "util/bits.h"
 #include "util/memory.h"
+#include "util/str.h"
 
 static seed_t *ansi_new() {
 	seed_t *result = seed_new();
@@ -17,26 +18,8 @@ static seed_t *ansi_new() {
 }
 
 bool ansi_seed_valid(const char *hex_str) {
-	size_t len = strlen(hex_str);
-	if (len < 40) {
-		return false;
-	}
-	const char *str_start = hex_str;
-	if (hex_str[0] == '0' && (hex_str[1] == 'x' || hex_str[1] == 'X')) {
-		str_start = hex_str + 2;
-	}
-	while (*str_start != 0) {
-		char c = *str_start++;
-		if (!isxdigit(c)) return false;
-	}
-	return true;
-}
-
-static bits_t *seed_stoi(const char *cstr) {
-	const char *seed_str = cstr;
-	const char *prefix = strstr(cstr, "0x");
-	if (prefix != NULL) seed_str = prefix + 2;
-	return bits_from_hex(seed_str);
+	const char *seed = str_is_hex(hex_str);
+	return seed && strlen(seed) >= 40;
 }
 
 static void seed_hash(seed_t *seed) {
@@ -64,7 +47,7 @@ GENERATOR(ansi_gen_seed_random) {
 
 GENERATOR(ansi_gen_seed_argument) {
 	seed_t *seed = ansi_new();
-	seed->seed = seed_stoi(cfg->seed);
+	seed->seed = bits_from_hex(str_is_hex(cfg->seed));
 	seed_hash(seed);
 	seed_tsh(seed);
 	curve->seed = seed;
@@ -83,7 +66,7 @@ GENERATOR(ansi_gen_seed_input) {
 	}
 
 	seed_t *seed = ansi_new();
-	seed->seed = seed_stoi(cstr);
+	seed->seed = bits_from_hex(str_is_hex(cstr));
 	seed_hash(seed);
 	seed_tsh(seed);
 	curve->seed = seed;
diff --git a/src/exhaustive/brainpool.c b/src/exhaustive/brainpool.c
new file mode 100644
index 0000000..fdabd6f
--- /dev/null
+++ b/src/exhaustive/brainpool.c
@@ -0,0 +1,268 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+
+#include "brainpool.h"
+#include "gen/gens.h"
+#include "gen/point.h"
+#include "gen/seed.h"
+#include "io/output.h"
+#include "util/bits.h"
+#include "util/str.h"
+
+static seed_t *brainpool_new() {
+	seed_t *result = seed_new();
+	result->type = SEED_BRAINPOOL;
+	return result;
+}
+
+static void seed_wv(seed_t *seed) {
+	pari_sp ltop = avma;
+	GEN L = utoi(cfg->bits);
+	seed->brainpool.v = itou(gfloor(gdivgs(subis(L, 1), 160)));
+	seed->brainpool.w = itou(subis(subis(L, 160 * seed->brainpool.v), 1));
+	avma = ltop;
+}
+
+void brainpool_update_seed(bits_t *s) {
+	pari_sp ltop = avma;
+	GEN z = bits_to_i(s);
+	GEN t = Fp_add(z, gen_1, int2n(160));
+	bits_t *result = bits_from_i_len(t, 160);
+	avma = ltop;
+	bits_cpy(s, result);
+	bits_free(&result);
+}
+
+bits_t *brainpool_hash(const bits_t *s, long w, long v) {
+	pari_sp ltop = avma;
+	unsigned char h[20];
+	bits_sha1(s, h);
+	unsigned char hashout[20 * v];
+
+	GEN z = bits_to_i(s);
+	GEN m = int2n(160);
+	for (long i = 1; i <= v; ++i) {
+		bits_t *si = bits_from_i_len(Fp_add(z, stoi(i), m), 160);
+		bits_sha1(si, hashout + (20 * (i - 1)));
+		bits_free(&si);
+	}
+	bits_t *result = bits_from_raw(h, 20 * 8);
+	bits_shortenz(result, 20 * 8 - w);
+	bits_t *rest = bits_from_raw(hashout, (size_t)(20 * v * 8));
+	bits_concatz(result, rest, NULL);
+	bits_free(&rest);
+	avma = ltop;
+	return result;
+}
+
+bool brainpool_seed_valid(const char *hex_str) {
+	const char *seed = str_is_hex(hex_str);
+	return seed && strlen(seed) == 40;
+}
+
+GENERATOR(brainpool_gen_seed_random) {
+	seed_t *seed = brainpool_new();
+	seed->seed = bits_new_rand(160);
+	seed_wv(seed);
+	curve->seed = seed;
+	return 1;
+}
+
+GENERATOR(brainpool_gen_seed_argument) {
+	seed_t *seed = brainpool_new();
+	seed->seed = bits_from_hex(str_is_hex(cfg->seed));
+	seed_wv(seed);
+	curve->seed = seed;
+	return 1;
+}
+
+GENERATOR(brainpool_gen_seed_input) {
+	pari_sp ltop = avma;
+
+	GEN str = input_string("seed:");
+	const char *cstr = GSTR(str);
+	if (!brainpool_seed_valid(cstr)) {
+		fprintf(err, "SEED must be exactly 160 bits(40 hex characters).\n");
+		avma = ltop;
+		return 0;
+	}
+
+	seed_t *seed = brainpool_new();
+	seed->seed = bits_from_hex(str_is_hex(cstr));
+	seed_wv(seed);
+	curve->seed = seed;
+	return 1;
+}
+
+GENERATOR(brainpool_gen_field) {
+	pari_sp btop = avma;
+	seed_t *seed = curve->seed;
+	do {
+		if (seed->brainpool.update_seed) {
+			brainpool_update_seed(seed->seed);
+			seed->brainpool.update_seed = false;
+		}
+		bits_t *p_bits = brainpool_hash(seed->seed, seed->brainpool.w + 1,
+		                                seed->brainpool.v);
+		GEN c = bits_to_i(p_bits);
+		bits_free(&p_bits);
+		GEN p = c;
+		pari_sp bbtop = avma;
+		do {
+			if (p != c) {//yes, check ptr identity here
+				avma = bbtop;
+			}
+			p = nextprime(addii(p, gen_1));
+		} while (mod4(p) != 3);
+
+		GEN lower_bound = subii(int2u(cfg->bits - 1), gen_1);
+		GEN upper_bound = int2u(cfg->bits);
+		if (mpcmp(p, lower_bound) <= 0 || mpcmp(p, upper_bound) >= 0) {
+			brainpool_update_seed(seed->seed);
+			avma = btop;
+			continue;
+		}
+
+		if (!isprime(p)) {
+			brainpool_update_seed(seed->seed);
+			avma = btop;
+			continue;
+		}
+
+		curve->field = gcopy(p);
+		gerepileall(btop, 1, &curve->field);
+		break;
+	} while (true);
+
+	seed->brainpool.update_seed = true;
+	return 1;
+}
+
+GENERATOR(brainpool_gen_equation) {
+	// field is definitely prime
+	pari_sp btop = avma;
+	seed_t *seed = curve->seed;
+	do {
+		if (seed->brainpool.update_seed) {
+			brainpool_update_seed(seed->seed);
+			seed->brainpool.update_seed = false;
+		}
+
+		bits_t *a_bits =
+		    brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
+		GEN a = bits_to_i(a_bits);
+		bits_free(&a_bits);
+		GEN am = Fp_invsafe(a, curve->field);
+		if (am == NULL) {
+			brainpool_update_seed(seed->seed);
+			avma = btop;
+			continue;
+		}
+
+		GEN z;
+		z = Fp_sqrtn(Fp_muls(am, -3, curve->field), stoi(4), curve->field,
+		             NULL);
+		if (z == NULL) {
+			brainpool_update_seed(seed->seed);
+			avma = btop;
+			continue;
+		}
+		seed->brainpool.seed_a = bits_copy(seed->seed);
+
+		brainpool_update_seed(seed->seed);
+
+		bits_t *b_bits =
+		    brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
+		GEN b = bits_to_i(b_bits);
+		bits_free(&b_bits);
+		if (!Fp_issquare(b, curve->field)) {
+			brainpool_update_seed(seed->seed);
+			bits_free(&seed->brainpool.seed_a);
+			avma = btop;
+			continue;
+		}
+		seed->brainpool.seed_b = bits_copy(seed->seed);
+
+		GEN mod_a = gmodulo(a, curve->field);
+		GEN mod_b = gmodulo(b, curve->field);
+
+		if (gequal0(gmulsg(-16, gadd(gmulsg(4, gpowgs(mod_a, 3)),
+		                             gmulsg(27, gsqr(mod_b)))))) {
+			brainpool_update_seed(seed->seed);
+			bits_free(&seed->brainpool.seed_a);
+			bits_free(&seed->brainpool.seed_b);
+			avma = btop;
+			continue;
+		}
+
+		curve->a = mod_a;
+		curve->b = mod_b;
+		gerepileall(btop, 2, &curve->a, &curve->b);
+		break;
+	} while (true);
+
+	seed->brainpool.update_seed = true;
+	return 1;
+}
+
+GENERATOR(brainpool_gen_gens) {
+	pari_sp ltop = avma;
+	seed_t *seed = curve->seed;
+	brainpool_update_seed(seed->seed);
+
+	bits_t *k_bits =
+	    brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
+	GEN k = bits_to_i(k_bits);
+	bits_free(&k_bits);
+	GEN x = gen_0;
+	GEN Qy = ellordinate(curve->curve, x, 0);
+	while (glength(Qy) == 0) {
+		mpaddz(x, gen_1, x);
+		Qy = ellordinate(curve->curve, x, 0);
+	}
+
+	GEN P = NULL;
+	if (glength(Qy) == 1) {
+		P = mkvec2(x, gel(Qy, 1));
+	} else if (glength(Qy) == 2) {
+		if (random_bits(1)) {
+			P = mkvec2(x, gel(Qy, 1));
+		} else {
+			P = mkvec2(x, gel(Qy, 2));
+		}
+	} else {
+		avma = ltop;
+		return INT_MIN;
+	}
+
+	curve->generators = points_new(1);
+	point_t *G = point_new();
+	curve->generators[0] = G;
+	G->point = gerepilecopy(ltop, ellmul(curve->curve, P, k));
+	G->order = ellorder(curve->curve, G->point, NULL);
+	G->cofactor = divii(curve->order, G->order);
+
+	return 1;
+}
+
+CHECK(brainpool_check_gens) {
+	pari_sp ltop = avma;
+	point_t *G = curve->generators[0];
+	GEN min_degree = divis(subii(G->order, gen_1), 100);
+	if (mpcmp(min_degree, gens_get_embedding(curve->field, G->order)) >= 0) {
+		avma = ltop;
+		return -5;
+	}
+	avma = ltop;
+	return 1;
+}
+
+CHECK(brainpool_check_order) {
+	if (mpcmp(curve->order, curve->field) < 0) {
+		return 1;
+	} else {
+		return -4;
+	}
+}
\ No newline at end of file
diff --git a/src/exhaustive/brainpool.h b/src/exhaustive/brainpool.h
new file mode 100644
index 0000000..0b19fa3
--- /dev/null
+++ b/src/exhaustive/brainpool.h
@@ -0,0 +1,105 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+
+#ifndef ECGEN_BRAINPOOL_H
+#define ECGEN_BRAINPOOL_H
+
+#include "misc/types.h"
+
+/**
+ *
+ * @param s
+ */
+void brainpool_update_seed(bits_t *s);
+
+/**
+ *
+ * @param s
+ * @param w
+ * @param v
+ * @return
+ */
+bits_t *brainpool_hash(const bits_t *s, long w, long v);
+
+/**
+ * @brief
+ * @param hex_str
+ * @return
+ */
+bool brainpool_seed_valid(const char *hex_str);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+GENERATOR(brainpool_gen_seed_random);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+GENERATOR(brainpool_gen_seed_argument);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+GENERATOR(brainpool_gen_seed_input);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+GENERATOR(brainpool_gen_field);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+GENERATOR(brainpool_gen_equation);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+GENERATOR(brainpool_gen_gens);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+CHECK(brainpool_check_gens);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+CHECK(brainpool_check_order);
+
+#endif  // ECGEN_BRAINPOOL_H
diff --git a/src/exhaustive/brainpool_rfc.c b/src/exhaustive/brainpool_rfc.c
new file mode 100644
index 0000000..81529d2
--- /dev/null
+++ b/src/exhaustive/brainpool_rfc.c
@@ -0,0 +1,97 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+
+#include "brainpool_rfc.h"
+#include "brainpool.h"
+#include "util/bits.h"
+
+#define brainpool_delegate(func)            \
+	int ret = func(curve, args, state);     \
+	if (ret != 1) {                         \
+		return ret;                         \
+	}                                       \
+	curve->seed->type = SEED_BRAINPOOL_RFC; \
+	return 1;
+
+GENERATOR(brainpool_rfc_gen_seed_argument) {
+	brainpool_delegate(brainpool_gen_seed_argument);
+}
+
+GENERATOR(brainpool_rfc_gen_seed_random) {
+	brainpool_delegate(brainpool_gen_seed_random);
+}
+
+GENERATOR(brainpool_rfc_gen_seed_input) {
+	brainpool_delegate(brainpool_gen_seed_input);
+}
+
+#undef brainpool_delegate
+
+GENERATOR(brainpool_rfc_gen_equation) {
+	// field is definitely prime
+	pari_sp btop = avma;
+	seed_t *seed = curve->seed;
+	do {
+		if (seed->brainpool.update_seed) {
+			brainpool_update_seed(seed->seed);
+			seed->brainpool.update_seed = false;
+		}
+
+		bits_t *a_bits =
+		    brainpool_hash(seed->seed, seed->brainpool.w, seed->brainpool.v);
+		GEN a = bits_to_i(a_bits);
+		bits_free(&a_bits);
+		GEN am = Fp_invsafe(a, curve->field);
+		if (am == NULL) {
+			brainpool_update_seed(seed->seed);
+			avma = btop;
+			continue;
+		}
+		GEN z;
+		z = Fp_sqrtn(Fp_muls(am, -3, curve->field), stoi(4), curve->field,
+		             NULL);
+		if (z == NULL) {
+			brainpool_update_seed(seed->seed);
+			avma = btop;
+			continue;
+		}
+		seed->brainpool.seed_a = bits_copy(seed->seed);
+
+		GEN b = NULL;
+		pari_sp bbtop = avma;
+		do {
+			if (b != NULL) {
+				avma = bbtop;
+			}
+			brainpool_update_seed(seed->seed);
+			bits_t *b_bits = brainpool_hash(seed->seed, seed->brainpool.w,
+			                                seed->brainpool.v);
+			b = bits_to_i(b_bits);
+			bits_free(&b_bits);
+		} while (Fp_issquare(b, curve->field));
+
+		seed->brainpool.seed_b = bits_copy(seed->seed);
+
+		GEN mod_a = gmodulo(a, curve->field);
+		GEN mod_b = gmodulo(b, curve->field);
+
+		if (gequal0(gmulsg(-16, gadd(gmulsg(4, gpowgs(mod_a, 3)),
+		                             gmulsg(27, gsqr(mod_b)))))) {
+			brainpool_update_seed(seed->seed);
+			bits_free(&seed->brainpool.seed_a);
+			bits_free(&seed->brainpool.seed_b);
+			avma = btop;
+			continue;
+		}
+
+		curve->a = mod_a;
+		curve->b = mod_b;
+		gerepileall(btop, 2, &curve->a, &curve->b);
+		break;
+	} while (true);
+
+	seed->brainpool.update_seed = true;
+	return 1;
+}
diff --git a/src/exhaustive/brainpool_rfc.h b/src/exhaustive/brainpool_rfc.h
new file mode 100644
index 0000000..8a27410
--- /dev/null
+++ b/src/exhaustive/brainpool_rfc.h
@@ -0,0 +1,47 @@
+/*
+ * ecgen, tool for generating Elliptic curve domain parameters
+ * Copyright (C) 2017 J08nY
+ */
+
+#ifndef ECGEN_BRAINPOOL_RFC_H
+#define ECGEN_BRAINPOOL_RFC_H
+
+#include "misc/types.h"
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+GENERATOR(brainpool_rfc_gen_seed_argument);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+GENERATOR(brainpool_rfc_gen_seed_random);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+GENERATOR(brainpool_rfc_gen_seed_input);
+
+/**
+ * @brief
+ * @param curve
+ * @param args
+ * @param state
+ * @return
+ */
+GENERATOR(brainpool_rfc_gen_equation);
+
+#endif  // ECGEN_BRAINPOOL_RFC_H
diff --git a/src/exhaustive/exhaustive.c b/src/exhaustive/exhaustive.c
index ea1dc63..c5e9ffc 100644
--- a/src/exhaustive/exhaustive.c
+++ b/src/exhaustive/exhaustive.c
@@ -5,6 +5,8 @@
 #include "exhaustive.h"
 #include "anomalous.h"
 #include "ansi.h"
+#include "brainpool.h"
+#include "brainpool_rfc.h"
 #include "check.h"
 #include "gen/curve.h"
 #include "gen/equation.h"
@@ -38,6 +40,20 @@ void exhaustive_clear(exhaustive_t *setup) {
 
 static void exhaustive_ginit(gen_f *generators) {
 	if (cfg->seed_algo) {
+		if (cfg->prime) {
+			generators[OFFSET_ORDER] = &order_gen_prime;
+		} else if (cfg->cofactor) {
+			generators[OFFSET_ORDER] = &order_gen_smallfact;
+		} else {
+			generators[OFFSET_ORDER] = &order_gen_any;
+		}
+
+		if (cfg->unique) {
+			generators[OFFSET_GENERATORS] = &gens_gen_one;
+		} else {
+			generators[OFFSET_GENERATORS] = &gens_gen_any;
+		}
+
 		switch (cfg->seed_algo) {
 			case SEED_ANSI: {
 				// setup ANSI X9.62 generators
@@ -50,25 +66,52 @@ static void exhaustive_ginit(gen_f *generators) {
 						generators[OFFSET_SEED] = &ansi_gen_seed_input;
 					}
 				}
+				if (cfg->random) {
+					generators[OFFSET_FIELD] = &field_gen_random;
+				} else {
+					generators[OFFSET_FIELD] = &field_gen_input;
+				}
 				generators[OFFSET_A] = &gen_skip;
 				generators[OFFSET_B] = &ansi_gen_equation;
-			}
-			case SEED_BRAINPOOL:
-				break;
-			case SEED_BRAINPOOL_RFC:
-				break;
+			} break;
+			case SEED_BRAINPOOL: {
+				if (cfg->seed) {
+					generators[OFFSET_SEED] = &brainpool_gen_seed_argument;
+				} else {
+					if (cfg->random) {
+						generators[OFFSET_SEED] = &brainpool_gen_seed_random;
+					} else {
+						generators[OFFSET_SEED] = &brainpool_gen_seed_input;
+					}
+				}
+				generators[OFFSET_FIELD] = &brainpool_gen_field;
+				generators[OFFSET_A] = &gen_skip;
+				generators[OFFSET_B] = &brainpool_gen_equation;
+				generators[OFFSET_ORDER] = &order_gen_prime;
+				generators[OFFSET_GENERATORS] = &brainpool_gen_gens;
+			} break;
+			case SEED_BRAINPOOL_RFC: {
+				if (cfg->seed) {
+					generators[OFFSET_SEED] = &brainpool_rfc_gen_seed_argument;
+				} else {
+					if (cfg->random) {
+						generators[OFFSET_SEED] =
+						    &brainpool_rfc_gen_seed_random;
+					} else {
+						generators[OFFSET_SEED] = &brainpool_rfc_gen_seed_input;
+					}
+				}
+				generators[OFFSET_FIELD] = &brainpool_gen_field;
+				generators[OFFSET_A] = &gen_skip;
+				generators[OFFSET_B] = &brainpool_rfc_gen_equation;
+				generators[OFFSET_ORDER] = &order_gen_prime;
+				generators[OFFSET_GENERATORS] = &brainpool_gen_gens;
+			} break;
 			case SEED_FIPS:
 				break;
 			default:
 				break;
 		}
-		if (cfg->prime) {
-			generators[OFFSET_ORDER] = &order_gen_prime;
-		} else if (cfg->cofactor) {
-			generators[OFFSET_ORDER] = &order_gen_smallfact;
-		} else {
-			generators[OFFSET_ORDER] = &order_gen_any;
-		}
 	} else {
 		// setup normal generators
 		generators[OFFSET_SEED] = &gen_skip;
@@ -107,23 +150,23 @@ static void exhaustive_ginit(gen_f *generators) {
 		} else {
 			generators[OFFSET_ORDER] = &order_gen_any;
 		}
-	}
-	// setup common generators
-	generators[OFFSET_CURVE] = &curve_gen_any;
 
-	if (cfg->unique) {
-		generators[OFFSET_GENERATORS] = &gens_gen_one;
-	} else {
-		generators[OFFSET_GENERATORS] = &gens_gen_any;
-	}
+		if (cfg->method == METHOD_ANOMALOUS) {
+			generators[OFFSET_FIELD] = &anomalous_gen_field;
+		} else if (cfg->random) {
+			generators[OFFSET_FIELD] = &field_gen_random;
+		} else {
+			generators[OFFSET_FIELD] = &field_gen_input;
+		}
 
-	if (cfg->method == METHOD_ANOMALOUS) {
-		generators[OFFSET_FIELD] = &anomalous_gen_field;
-	} else if (cfg->random) {
-		generators[OFFSET_FIELD] = &field_gen_random;
-	} else {
-		generators[OFFSET_FIELD] = &field_gen_input;
+		if (cfg->unique) {
+			generators[OFFSET_GENERATORS] = &gens_gen_one;
+		} else {
+			generators[OFFSET_GENERATORS] = &gens_gen_any;
+		}
 	}
+	// setup common generators
+	generators[OFFSET_CURVE] = &curve_gen_any;
 
 	switch (cfg->points.type) {
 		case POINTS_RANDOM:
@@ -156,6 +199,25 @@ static void exhaustive_cinit(check_t **validators) {
 		check_t *hex_check = check_new(hex_check_param, NULL);
 		validators[OFFSET_POINTS] = hex_check;
 	}
+
+	if (cfg->method == METHOD_SEED) {
+		switch (cfg->seed_algo) {
+			case SEED_ANSI:
+				break;
+			case SEED_BRAINPOOL:
+			case SEED_BRAINPOOL_RFC: {
+				check_t *order_check = check_new(brainpool_check_order, NULL);
+				validators[OFFSET_ORDER] = order_check;
+				check_t *gens_check =
+				    check_new(gens_check_anomalous, brainpool_check_gens, NULL);
+				validators[OFFSET_GENERATORS] = gens_check;
+			} break;
+			case SEED_FIPS:
+				break;
+			default:
+				break;
+		}
+	}
 }
 
 static void exhaustive_ainit(arg_t **gen_argss, arg_t **check_argss) {
@@ -172,12 +234,14 @@ static void exhaustive_ainit(arg_t **gen_argss, arg_t **check_argss) {
 		gen_argss[OFFSET_FIELD] = field_arg;
 		gen_argss[OFFSET_B] = eq_arg;
 	}
+
 	if (cfg->points.type == POINTS_RANDOM) {
 		arg_t *points_arg = arg_new();
 		points_arg->args = &cfg->points.amount;
 		points_arg->nargs = 1;
 		gen_argss[OFFSET_POINTS] = points_arg;
 	}
+
 	if (cfg->cofactor) {
 		arg_t *order_arg = arg_new();
 		arg_t *gens_arg = arg_new();
@@ -245,6 +309,7 @@ int exhaustive_gen_retry(curve_t *curve, const exhaustive_t *setup,
 		}
 		timeout_stop();
 		if (diff > 0 && setup->validators && setup->validators[state]) {
+			pari_sp ctop = avma;
 			check_t *validator = setup->validators[state];
 			for (size_t i = 0; i < validator->nchecks; ++i) {
 				int new_diff =
@@ -254,6 +319,7 @@ int exhaustive_gen_retry(curve_t *curve, const exhaustive_t *setup,
 					break;
 				}
 			}
+			avma = ctop;
 		}
 
 		int new_state = state + diff;
diff --git a/src/gen/gens.c b/src/gen/gens.c
index 2cffbc4..04e7646 100644
--- a/src/gen/gens.c
+++ b/src/gen/gens.c
@@ -40,16 +40,27 @@ GENERATOR(gens_gen_one) {
 
 CHECK(gens_check_anomalous) {
 	if (cfg->field == FIELD_BINARY) return 1;
-	pari_sp ltop = avma;
 	for (size_t i = 0; i < curve->ngens; ++i) {
 		if (mpcmp(curve->field, curve->generators[i]->order) == 0) {
-			avma = ltop;
 			return -5;
 		}
 	}
 	return 1;
 }
 
+GEN gens_get_embedding(GEN prime, GEN order) {
+	pari_sp ltop = avma;
+	GEN degree = gen_0;
+	GEN power = gen_1;
+	GEN pm;
+	do {
+		degree = addii(degree, gen_1);
+		power = mulii(power, prime);
+		pm = subii(power, gen_1);
+	} while (!dvdii(pm, order));
+	return gerepilecopy(ltop, degree);
+}
+
 CHECK(gens_check_embedding) {
 	HAS_ARG(args);
 	if (cfg->field == FIELD_BINARY) return 1;
@@ -59,13 +70,8 @@ CHECK(gens_check_embedding) {
 	GEN mind = strtoi(min_degree);
 
 	for (size_t i = 0; i < curve->ngens; ++i) {
-		GEN power = gen_0;
-		GEN pm;
-		do {
-			power = addii(power, gen_1);
-			GEN ppow = powii(curve->field, power);
-			pm = subii(ppow, gen_1);
-		} while (!dvdii(pm, curve->generators[i]->order));
+		GEN power =
+		    gens_get_embedding(curve->field, curve->generators[i]->order);
 
 		if (mpcmp(power, mind) <= 0) {
 			avma = ltop;
diff --git a/src/gen/gens.h b/src/gen/gens.h
index 18c9815..11b349b 100644
--- a/src/gen/gens.h
+++ b/src/gen/gens.h
@@ -30,6 +30,7 @@ GENERATOR(gens_gen_any);
 GENERATOR(gens_gen_one);
 
 /**
+ * CHECK(check_f)
  *
  * @param curve
  * @param args
@@ -39,6 +40,18 @@ GENERATOR(gens_gen_one);
 CHECK(gens_check_anomalous);
 
 /**
+ * @brief Get the embedding degree of a subgroup of <code>order</code> in a
+ * power of F_prime.
+ *
+ * @param prime The order of the base field.
+ * @param order The order of the subgroup generator (in the curve group).
+ * @return The embedding degree 't' such that <code>order</code> divides
+ * 'prime^t - 1'.
+ */
+GEN gens_get_embedding(GEN prime, GEN order);
+
+/**
+ * CHECK(check_f)
  *
  * @param curve
  * @param args
diff --git a/src/gen/order.c b/src/gen/order.c
index 366c2cd..1c9e280 100644
--- a/src/gen/order.c
+++ b/src/gen/order.c
@@ -20,10 +20,12 @@ GENERATOR(order_gen_input) {
 }
 
 GENERATOR(order_gen_any) {
+	pari_sp ltop = avma;
 	GEN ord = ellff_get_card(curve->curve);
 	if (isclone(ord)) {
-		curve->order = gcopy(ord);
+		curve->order = gerepilecopy(ltop, ord);
 	} else {
+		avma = ltop;
 		curve->order = ord;
 	}
 	return 1;
@@ -36,7 +38,7 @@ GENERATOR(order_gen_sea) {
 		avma = ltop;
 		return -4;
 	} else {
-		curve->order = order;
+		curve->order = gerepilecopy(ltop, order);
 		obj_insert_shallow(curve->curve, 1, order);
 		return 1;
 	}
@@ -86,7 +88,7 @@ GENERATOR(order_gen_prime) {
 		avma = ltop;
 		return -4;
 	} else {
-		curve->order = order;
+		curve->order = gerepilecopy(ltop, order);
 		obj_insert_shallow(curve->curve, 1, curve->order);
 		return 1;
 	}
diff --git a/src/gen/seed.c b/src/gen/seed.c
index a13588e..ad56b18 100644
--- a/src/gen/seed.c
+++ b/src/gen/seed.c
@@ -4,6 +4,7 @@
  */
 
 #include "seed.h"
+#include <misc/types.h>
 #include "util/bits.h"
 #include "util/memory.h"
 
@@ -35,9 +36,7 @@ seed_t *seed_new_clone(const seed_t *src) {
 
 void seed_free(seed_t **seed) {
 	if (*seed) {
-		if ((*seed)->seed) {
-			bits_free(&(*seed)->seed);
-		}
+		bits_free(&(*seed)->seed);
 		if ((*seed)->hash20) {
 			try_free((*seed)->hash20);
 		}
@@ -45,8 +44,9 @@ void seed_free(seed_t **seed) {
 			case SEED_ANSI:
 				break;
 			case SEED_BRAINPOOL:
-				break;
 			case SEED_BRAINPOOL_RFC:
+				bits_free(&(*seed)->brainpool.seed_a);
+				bits_free(&(*seed)->brainpool.seed_b);
 				break;
 			case SEED_FIPS:
 				break;
diff --git a/src/io/cli.c b/src/io/cli.c
index 3c3dccd..702081b 100644
--- a/src/io/cli.c
+++ b/src/io/cli.c
@@ -6,6 +6,7 @@
 #include <misc/config.h>
 #include <string.h>
 #include "exhaustive/ansi.h"
+#include "exhaustive/brainpool.h"
 
 char cli_doc[] =
     "ecgen, tool for generating Elliptic curve domain parameters.\v(C) 2017 "
@@ -19,6 +20,7 @@ enum opt_keys {
 	OPT_COFACTOR = 'k',
 	OPT_RANDOM = 'r',
 	OPT_ANSI = 's',
+	OPT_BRAINPOOL = 'b',
 	OPT_INVALID = 'i',
 	OPT_ORDER = 'n',
 	OPT_KOBLITZ = 'K',
@@ -38,47 +40,50 @@ enum opt_keys {
 	OPT_ANOMALOUS,
 	OPT_GPGEN,
 	OPT_GPCHECK,
-	OPT_HEXCHECK
+	OPT_HEXCHECK,
+	OPT_BRAINPOOL_RFC
 };
 
 // clang-format off
 struct argp_option cli_options[] = {
-	{0,              0,             0,        0,                 "Field specification:",                                                                  1},
-	{"fp",           OPT_FP,        0,        0,                 "Prime field.",                                                                          1},
-	{"f2m",          OPT_F2M,       0,        0,                 "Binary field.",                                                                         1},
+		{0,               0,                 0,        0,                 "Field specification:",                                                                  1},
+		{"fp",            OPT_FP,            0,        0,                 "Prime field.",                                                                          1},
+		{"f2m",           OPT_F2M,           0,        0,                 "Binary field.",                                                                         1},
 
-	{0,              0,             0,        0,                 "Generation methods:",                                                                   2},
-	{"order",        OPT_ORDER,     "ORDER",  0,                 "Generate a curve with given order (using Complex Multiplication). **NOT IMPLEMENTED**", 2},
-	{"anomalous",    OPT_ANOMALOUS, 0,        0,                 "Generate an anomalous curve (of trace one, with field order equal to curve order).",    2},
-	{"ansi",         OPT_ANSI,      "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (ANSI X9.62 verifiable procedure).",     					  2},
-	{"invalid",      OPT_INVALID,   0,        0,                 "Generate a set of invalid curves, for a given curve (using Invalid curve algorithm).",  2},
+		{0,               0,                 0,        0,                 "Generation methods:",                                                                   2},
+		{"order",         OPT_ORDER,         "ORDER",  0,                 "Generate a curve with given order (using Complex Multiplication). **NOT IMPLEMENTED**", 2},
+		{"anomalous",     OPT_ANOMALOUS,     0,        0,                 "Generate an anomalous curve (of trace one, with field order equal to curve order).",    2},
+		{"ansi",          OPT_ANSI,          "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (ANSI X9.62 verifiable procedure).",                         2},
+		{"brainpool",     OPT_BRAINPOOL,     "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (Brainpool procedure).",                                     2},
+		{"brainpool-rfc", OPT_BRAINPOOL_RFC, "SEED", OPTION_ARG_OPTIONAL, "Generate a curve from SEED (Brainpool procedure, as per RFC 5639).",                    2},
+		{"invalid",       OPT_INVALID,       0,        0,                 "Generate a set of invalid curves, for a given curve (using Invalid curve algorithm).",  2},
 
-	{0,				 0, 			0, 		  0,				 "Generation options:",																	  3},
-	{"random",       OPT_RANDOM,    0,        0,                 "Generate a random curve (using Random approach).",                                      3},
-	{"prime",        OPT_PRIME,     0,        0,                 "Generate a curve with prime order.",                                                    3},
-	{"cofactor",     OPT_COFACTOR,  "BOUND",  0,                 "Generate a curve with cofactor up to BOUND.",                                           3},
-	{"koblitz",      OPT_KOBLITZ,   "A",     OPTION_ARG_OPTIONAL,"Generate a Koblitz curve (a in {0, 1}, b = 1).",                                        3},
-	{"unique",       OPT_UNIQUE,    0,        0,                 "Generate a curve with only one generator.",                                             3},
-	{"gp-gen",		 OPT_GPGEN,     "FUNC",   0,				 "Generate a curve param using a GP function. **NOT IMPLEMENTED**", 					  3},
-	{"gp-check",	 OPT_GPCHECK,   "FUNC",   0, 				 "Check a generated curve param using a GP function. **NOT IMPLEMENTED**",				  3},
-	{"hex-check",	 OPT_HEXCHECK,  "HEX",	  0,				 "Check a generated curve param hex expansion for the HEX string.",						  3},
-	{"points",       OPT_POINTS,    "TYPE",   0,                 "Generate points of given type (random/prime/all/nonprime/none).",                       3},
-	{"count",        OPT_COUNT,     "COUNT",  0,                 "Generate multiple curves.",                                                             3},
+		{0,               0,                 0,        0,                 "Generation options:",                                                                   3},
+		{"random",        OPT_RANDOM,        0,        0,                 "Generate a random curve (using Random approach).",                                      3},
+		{"prime",         OPT_PRIME,         0,        0,                 "Generate a curve with prime order.",                                                    3},
+		{"cofactor",      OPT_COFACTOR,      "BOUND",  0,                 "Generate a curve with cofactor up to BOUND.",                                           3},
+		{"koblitz",       OPT_KOBLITZ,       "A",    OPTION_ARG_OPTIONAL, "Generate a Koblitz curve (a in {0, 1}, b = 1).",                                        3},
+		{"unique",        OPT_UNIQUE,        0,        0,                 "Generate a curve with only one generator.",                                             3},
+		{"gp-gen",        OPT_GPGEN,         "FUNC",   0,                 "Generate a curve param using a GP function. **NOT IMPLEMENTED**",                       3},
+		{"gp-check",      OPT_GPCHECK,       "FUNC",   0,                 "Check a generated curve param using a GP function. **NOT IMPLEMENTED**",                3},
+		{"hex-check",     OPT_HEXCHECK,      "HEX",    0,                 "Check a generated curve param hex expansion for the HEX string.",                       3},
+		{"points",        OPT_POINTS,        "TYPE",   0,                 "Generate points of given type (random/prime/all/nonprime/none).",                       3},
+		{"count",         OPT_COUNT,         "COUNT",  0,                 "Generate multiple curves.",                                                             3},
 
-	{0,              0,             0,        0,                 "Input/Output options:",                                                                 4},
-	{"format",       OPT_FORMAT,    "FORMAT", 0,                 "Format to output in. One of {csv, json}, default is json.",                             4},
-	{"input",        OPT_INPUT,     "FILE",   0,                 "Input from file.",                                                                      4},
-	{"output",       OPT_OUTPUT,    "FILE",   0,                 "Output into file. Overwrites any existing file!",                                       4},
-	{"append",       OPT_APPEND,    0,        0,                 "Append to output file (don't overwrite).",                                              4},
-	{"verbose",      OPT_VERBOSE,   "FILE", OPTION_ARG_OPTIONAL, "Verbose logging (to stdout or file).",                                                  4},
+		{0,               0,                 0,        0,                 "Input/Output options:",                                                                 4},
+		{"format",        OPT_FORMAT,        "FORMAT", 0,                 "Format to output in. One of {csv, json}, default is json.",                             4},
+		{"input",         OPT_INPUT,         "FILE",   0,                 "Input from file.",                                                                      4},
+		{"output",        OPT_OUTPUT,        "FILE",   0,                 "Output into file. Overwrites any existing file!",                                       4},
+		{"append",        OPT_APPEND,        0,        0,                 "Append to output file (don't overwrite).",                                              4},
+		{"verbose",       OPT_VERBOSE,       "FILE", OPTION_ARG_OPTIONAL, "Verbose logging (to stdout or file).",                                                  4},
 
-	{0,              0,             0,        0,                 "Other:",                                                                                5},
-	{"data-dir",     OPT_DATADIR,   "DIR",    0,                 "Set PARI/GP data directory (containing seadata package).",                              5},
-	{"memory",       OPT_MEMORY,    "SIZE",   0,                 "Use PARI stack of SIZE (can have suffix k/m/g).",                                       5},
-	{"threads",      OPT_THREADS,   "NUM",    0,                 "Use NUM threads.",                                                                      5},
-	{"thread-stack", OPT_TSTACK,    "SIZE",   0,                 "Use PARI stack of SIZE (per thread, can have suffix k/m/g).",                           5},
-	{"timeout",      OPT_TIMEOUT,   "TIME",   0,                 "Timeout computation of a curve parameter after TIME (can have suffix s/m/h/d).",        5},
-	{0}
+		{0,               0,                 0,        0,                 "Other:",                                                                                5},
+		{"data-dir",      OPT_DATADIR,       "DIR",    0,                 "Set PARI/GP data directory (containing seadata package).",                              5},
+		{"memory",        OPT_MEMORY,        "SIZE",   0,                 "Use PARI stack of SIZE (can have suffix k/m/g).",                                       5},
+		{"threads",       OPT_THREADS,       "NUM",    0,                 "Use NUM threads.",                                                                      5},
+		{"thread-stack",  OPT_TSTACK,        "SIZE",   0,                 "Use PARI stack of SIZE (per thread, can have suffix k/m/g).",                           5},
+		{"timeout",       OPT_TIMEOUT,       "TIME",   0,                 "Timeout computation of a curve parameter after TIME (can have suffix s/m/h/d).",        5},
+		{0}
 };
 // clang-format on
 
@@ -130,13 +135,9 @@ static void cli_end(struct argp_state *state) {
 	// Only one gen method
 	switch (cfg->method) {
 		case METHOD_DEFAULT:
-			break;
 		case METHOD_CM:
-			break;
 		case METHOD_ANOMALOUS:
-			break;
 		case METHOD_SEED:
-			break;
 		case METHOD_INVALID:
 			break;
 		default:
@@ -146,6 +147,11 @@ static void cli_end(struct argp_state *state) {
 			break;
 	}
 
+	if (cfg->method == METHOD_SEED && cfg->seed_algo == SEED_BRAINPOOL &&
+	    cfg->field == FIELD_BINARY) {
+		argp_failure(state, 1, 0,
+		             "Brainpool algorithm only creates prime field curves.");
+	}
 	/*
 	// Invalid is not prime or seed by definition.
 	if (cfg->invalid &&
@@ -227,6 +233,30 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) {
 				cfg->seed = arg;
 			}
 			break;
+		case OPT_BRAINPOOL:
+			cfg->method |= METHOD_SEED;
+			cfg->seed_algo = SEED_BRAINPOOL;
+			if (arg) {
+				if (!brainpool_seed_valid(arg)) {
+					argp_failure(
+					    state, 1, 0,
+					    "SEED must be exactly 160 bits (40 hex characters).");
+				}
+				cfg->seed = arg;
+			}
+			break;
+		case OPT_BRAINPOOL_RFC:
+			cfg->method |= METHOD_SEED;
+			cfg->seed_algo = SEED_BRAINPOOL_RFC;
+			if (arg) {
+				if (!brainpool_seed_valid(arg)) {
+					argp_failure(
+					    state, 1, 0,
+					    "SEED must be exactly 160 bits (40 hex characters).");
+				}
+				cfg->seed = arg;
+			}
+			break;
 
 		/* Generation options */
 		case OPT_COUNT:
@@ -299,7 +329,6 @@ error_t cli_parse(int key, char *arg, struct argp_state *state) {
 			}
 			break;
 		}
-
 		/* IO options */
 		case OPT_FORMAT:
 			if (!strcmp(arg, "csv")) {
diff --git a/src/misc/types.h b/src/misc/types.h
index aecf207..76f8510 100644
--- a/src/misc/types.h
+++ b/src/misc/types.h
@@ -44,7 +44,11 @@ typedef struct {
 			GEN r;
 		} ansi;
 		struct {
-			bits_t *f;
+			bool update_seed;
+			long w;
+			long v;
+			bits_t *seed_a;
+			bits_t *seed_b;
 		} brainpool;
 	};
 } seed_t;
diff --git a/src/util/bits.c b/src/util/bits.c
index e5f28c1..a0a3795 100644
--- a/src/util/bits.c
+++ b/src/util/bits.c
@@ -4,6 +4,7 @@
  */
 
 #include "bits.h"
+#include <misc/types.h>
 #include <sha1/sha1.h>
 #include "util/memory.h"
 
@@ -16,6 +17,36 @@ bits_t *bits_new(size_t bit_len) {
 	return result;
 }
 
+bits_t *bits_new_rand(size_t bit_len) {
+	bits_t *result = bits_new(bit_len);
+	for (size_t i = 0; i < result->allocated; ++i) {
+		if (i == result->allocated - 1) {
+			size_t last_bits = bit_len % 8;
+			result->bits[i] = (unsigned char)random_bits(last_bits)
+			                  << (8 - last_bits);
+		} else {
+			result->bits[i] = (unsigned char)random_bits(8);
+		}
+	}
+	return result;
+}
+
+void bits_cpy(bits_t *dest, const bits_t *src) {
+	if (src->bitlen == 0) {
+		return;
+	}
+
+	if (src->allocated < dest->allocated) {
+		memset(dest->bits + src->allocated, 0,
+		       dest->allocated - src->allocated);
+	} else if (src->allocated > dest->allocated) {
+		dest->bits = try_realloc(dest->bits, src->allocated);
+	}
+	memcpy(dest->bits, src->bits, src->allocated);
+	dest->allocated = src->allocated;
+	dest->bitlen = src->bitlen;
+}
+
 bits_t *bits_copy(const bits_t *bits) {
 	bits_t *result = try_calloc(sizeof(bits_t));
 	result->bitlen = bits->bitlen;
@@ -49,6 +80,24 @@ bits_t *bits_from_i(GEN i) {
 	return result;
 }
 
+bits_t *bits_from_i_len(GEN i, size_t bit_len) {
+	pari_sp ltop = avma;
+	GEN bitvec = binary_zv(i);
+	size_t i_len = (size_t)glength(bitvec);
+	bits_t *result = bits_new(bit_len);
+	size_t offset = 0;
+	if (i_len < bit_len) {
+		offset = bit_len - i_len;
+	}
+	for (size_t j = 0; j < bit_len; ++j) {
+		if (j < i_len && gel(bitvec, j + 1) == (GEN)1) {
+			result->bits[(j + offset) / 8] |= 1 << (7 - ((j + offset) % 8));
+		}
+	}
+	avma = ltop;
+	return result;
+}
+
 bits_t *bits_from_hex(const char *hex_str) {
 	size_t nibble_len = strlen(hex_str);
 	bits_t *result = bits_new(nibble_len * 4);
@@ -102,7 +151,7 @@ GEN bits_to_i(const bits_t *bits) {
 		if (GET_BIT(bits->bits, i) != 0)
 			result = addii(result, int2n(bits->bitlen - i - 1));
 	}
-	return gerepileupto(ltop, result);
+	return gerepilecopy(ltop, result);
 }
 
 char *bits_to_hex(const bits_t *bits) {
diff --git a/src/util/bits.h b/src/util/bits.h
index 2766cc3..000d64f 100644
--- a/src/util/bits.h
+++ b/src/util/bits.h
@@ -29,12 +29,18 @@
 
 bits_t *bits_new(size_t bit_len);
 
+bits_t *bits_new_rand(size_t bit_len);
+
+void bits_cpy(bits_t *dest, const bits_t *src);
+
 bits_t *bits_copy(const bits_t *bits);
 
 void bits_free(bits_t **bits);
 
 bits_t *bits_from_i(GEN i);
 
+bits_t *bits_from_i_len(GEN i, size_t bitlen);
+
 bits_t *bits_from_hex(const char *hex_str);
 
 bits_t *bits_from_bin(const char *bin_str);
diff --git a/src/util/str.c b/src/util/str.c
index 933eb83..3f9f39c 100644
--- a/src/util/str.c
+++ b/src/util/str.c
@@ -3,9 +3,25 @@
  * Copyright (C) 2017 J08nY
  */
 #include "str.h"
+#include <ctype.h>
 #include <string.h>
 #include "util/memory.h"
 
+const char *str_is_hex(const char *hex_str) {
+	const char *str_start = hex_str;
+	if (strlen(hex_str) > 2) {
+		if (hex_str[0] == '0' && (hex_str[1] == 'x' || hex_str[1] == 'X')) {
+			str_start = hex_str + 2;
+		}
+	}
+	const char *s = str_start;
+	while (*s != 0) {
+		char c = *s++;
+		if (!isxdigit(c)) return NULL;
+	}
+	return str_start;
+}
+
 char *str_join(char *strings[], size_t len) {
 	size_t total = 0;
 	for (size_t i = 0; i < len; ++i) {
diff --git a/src/util/str.h b/src/util/str.h
index 2e14272..9b5709e 100644
--- a/src/util/str.h
+++ b/src/util/str.h
@@ -12,6 +12,13 @@
 
 /**
  * @brief
+ * @param hex_str
+ * @return
+ */
+const char *str_is_hex(const char *hex_str);
+
+/**
+ * @brief
  * @param strings
  * @param len
  * @return