From 544153a8ffa6d68385712ab0a7c6315399346909 Mon Sep 17 00:00:00 2001
From: Benedict <benedict@0xb8000.de>
Date: Tue, 29 Nov 2016 22:24:26 +0100
Subject: completed challenge 40, set 5

---
 lib/lib5.c | 207 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 198 insertions(+), 9 deletions(-)

(limited to 'lib/lib5.c')

diff --git a/lib/lib5.c b/lib/lib5.c
index 2f45c29..722cc46 100644
--- a/lib/lib5.c
+++ b/lib/lib5.c
@@ -331,10 +331,10 @@ int rsa_generate_key_bignum(struct rsa_key_bignum *public, struct rsa_key_bignum
 	// well should check here for error but asusme infinte memory here
 	BIGNUM *q = BN_new();
 
-	if (!BN_generate_prime_ex(p, 256, 1, NULL, NULL, NULL) ||
-		!BN_generate_prime_ex(q, 256, 1, NULL, NULL, NULL))
-		die("error generating prime");
-
+	BN_generate_prime_ex(p, 256, 1, NULL, NULL, NULL);
+	do {
+		BN_generate_prime_ex(q, 256, 1, NULL, NULL, NULL);
+	} while (!BN_cmp(p, q));
 	BIGNUM *n = BN_new();
 
 	if(!BN_mul(n,p,q,ctx))
@@ -358,14 +358,17 @@ int rsa_generate_key_bignum(struct rsa_key_bignum *public, struct rsa_key_bignum
 
 	BIGNUM *e = BN_new();
 	BN_set_word(e, 3);
-
 	//BIGNUM *d = BN_mod_inverse(NULL, e, et, ctx);
 	BIGNUM *d = BN_new();
 	modular_multiplicative_inverse_bignum_my(d, e, et);
-	public->exponent = e;
-	public->modulo = n;
-	private->exponent = d;
-	private->modulo = n;
+	public->exponent = BN_new();
+	public->modulo = BN_new();
+	private->exponent = BN_new();
+	private->modulo = BN_new();
+	public->exponent = BN_dup(e);
+	BN_copy(public->modulo, n);
+	BN_copy(private->exponent, d);
+	BN_copy(private->modulo, n);
 
 }
 
@@ -375,3 +378,189 @@ int free_rsa_key_bignum(struct rsa_key_bignum *t)
 	BN_free(t->modulo);
 }
 
+/**
+  * computes the nth root of number.
+  * Note that the computed root is always an integer
+  * does not work good for numbers which are not divisible by n :-(
+  **/ 
+int nth_root_bignum(BIGNUM *res, BIGNUM *number, BIGNUM *n)
+{
+	BIGNUM *n_1 = BN_new();
+	BIGNUM *r = BN_new();
+	BIGNUM *d = BN_new();
+	BIGNUM *zero = BN_new();
+	BN_zero(zero);
+	BN_set_word(r, 1);
+	BN_set_word(d, 1);
+	BN_sub(n_1, n, d);
+
+	do {
+		BN_exp(res, r, n_1, ctx);
+		BN_div(res, NULL, number, res, ctx);
+		BN_sub(res, res, r);
+		BN_div(d, NULL, res, n, ctx);
+		BN_add(r, r, d);
+	} while (BN_cmp(d, zero));
+
+	BN_copy(res, r);
+	BN_free(zero);
+	BN_free(r);
+	BN_free(d);
+	BN_free(n_1);
+}
+int rsa_broadcast_cube(BIGNUM *res, BIGNUM **a, BIGNUM **n)
+{
+	BIGNUM *tmp = BN_new();
+	BIGNUM *N= BN_new();
+	BIGNUM *N_ni = BN_new();
+	BIGNUM *sum = BN_new();
+	BIGNUM *n_3 = BN_new();
+
+	BN_set_word(n_3, 3);
+	BN_one(N);
+	BN_zero(sum);
+	int i;
+
+	for(i=0;i<3;i++)
+		BN_mul(N, N, n[i], ctx);
+
+	for(i=0;i<3;i++) {
+		BN_div(N_ni, NULL, N, n[i], ctx);
+		BN_mod_inverse(tmp, N_ni, n[i], ctx);
+		modular_multiplicative_inverse_bignum_my(tmp, N_ni, n[i]);
+		BN_mul(tmp, tmp, N_ni, ctx);
+		BN_mul(tmp, tmp, a[i], ctx);
+		BN_add(sum, sum, tmp);
+	}
+
+	BN_nnmod(sum, sum, N, ctx);
+	nth_root_bignum(res, sum, n_3);
+}
+
+int chinese_remainder_theorem_bignum(BIGNUM *solution, BIGNUM *sol_no_mod, BIGNUM **a, BIGNUM **n, int len)
+{
+	int i,j;
+
+	for(i=0;i<len;i++) {
+		for(j=i+1;j<len;j++) {
+			if(!check_co_prime_bignum(n[i], n[j]))
+				return -1;
+		}
+	}
+
+	__chinese_remainder_theorem_bignum(solution, sol_no_mod, a, n, len);
+}
+
+int check_co_prime_bignum(BIGNUM *a, BIGNUM *b)
+{
+	struct extended_euclid_bignum e;
+	e.d = BN_new();
+	e.s = BN_new();
+	e.t = BN_new();
+
+	BIGNUM *one = BN_new();
+	BN_one(one);
+	extended_euclid_algo_bignum(a, b, &e);
+	int ret = BN_cmp(e.d, one);
+	BN_free(one);
+	BN_free(e.d);
+	BN_free(e.s);
+	BN_free(e.t);
+	return (ret == 0);
+}
+
+int chinese_remainder_theorem(int *a, int *n, int len)
+{
+	// check if n[i] are pair-wise co-prime since it is a pre-condition
+	// for the chinese remainder theorem
+	int i, j;
+
+	for(i=0;i<len;i++) {
+		for(j=i+1;j<len;j++) {
+			if(!check_co_prime(n[i], n[j]))
+				return -1;
+		}
+	}
+
+	return __chinese_remainder_theorem(a, n, len);
+
+}
+int __chinese_remainder_theorem_bignum(BIGNUM *solution, BIGNUM *sol_no_mod, BIGNUM **a, BIGNUM **n, int len)
+{
+	BIGNUM *N = BN_new();
+	BIGNUM *N_ni = BN_new();
+	BIGNUM *tmp  = BN_new();
+	BN_one(N);
+	BN_zero(solution);
+	BN_zero(sol_no_mod);
+	int i;
+	struct extended_euclid_bignum e;
+	e.d = BN_new();
+	e.s = BN_new();
+	e.t = BN_new();
+
+	for(i=0;i<len;i++)
+		BN_mul(N, N, n[i], ctx);
+
+
+	for(i=0;i<len;i++) {
+		BN_div(N_ni, NULL, N, n[i], ctx);
+		extended_euclid_algo_bignum(n[i], N_ni, &e);
+		BN_mul(tmp, a[i], e.t, ctx);
+		BN_mul(tmp, tmp, N_ni, ctx);
+		BN_add(solution, solution, tmp);
+	}
+	BN_copy(sol_no_mod, solution);
+	BN_nnmod(solution, solution, N, ctx);
+	BN_free(N);
+	BN_free(N_ni);
+	BN_free(tmp);
+	BN_free(e.d);
+	BN_free(e.s);
+	BN_free(e.t);
+}
+
+int check_co_prime(int a, int b)
+{
+	struct extended_euclid e;
+	extended_euclid_algo(a, b, &e);
+	return (e.d == 1);
+}
+
+/** assumes that the system is sovleable with crt, aka. that the n_i are co-prime
+  *
+  **/
+int __chinese_remainder_theorem(int *a, int *n, int len)
+{
+	int N = 1;
+	int i = 0;
+	int solution = 0;
+	struct extended_euclid e;
+
+	for(i=0;i<len;i++)
+		N *= n[i];
+
+	for(i=0;i<len;i++) {
+		int N_ni = N / n[i];
+		extended_euclid_algo(n[i], N_ni, &e);
+		solution += a[i] * e.t * N_ni;
+	}
+
+	return modulo(solution, N);
+}
+
+
+#define NTH_ROOT_PRECISION 0.00001
+double nth_root_wr(double x, int n)
+{
+	double r = 1;
+	double d = 1;
+
+	do {
+		d = (x / pow(r, n - 1) - r) / n;
+		r += d;
+	}
+	while (d > NTH_ROOT_PRECISION || d < -NTH_ROOT_PRECISION);
+	return r;
+}
+
-- 
cgit v1.2.3-70-g09d2