From 30211642cbdee771ad4e0d8515719985e5c0c36a Mon Sep 17 00:00:00 2001
From: Benedict <benedict@0xb8000.de>
Date: Sun, 20 Nov 2016 00:43:27 +0100
Subject: task39: implemented own modular multiplicative invserse for bignum

---
 lib/lib5.c | 63 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--
 lib/lib5.h |  2 ++
 2 files changed, 63 insertions(+), 2 deletions(-)

(limited to 'lib')

diff --git a/lib/lib5.c b/lib/lib5.c
index 89b781a..2f45c29 100644
--- a/lib/lib5.c
+++ b/lib/lib5.c
@@ -239,6 +239,18 @@ void extended_euclid_algo(int a, int b, struct extended_euclid *e)
 	return;
 }
 
+int modular_multiplicative_inverse(int number, int _modulo)
+{
+	struct extended_euclid tmp;
+	extended_euclid_algo(number, _modulo, &tmp);
+	// only has a inverse iff gcd = 1
+	if ( tmp.d != 1)
+		return INT_MIN;
+
+	// mod works not fine for negytive numbers in c
+	return modulo(tmp.s, _modulo);
+}
+
 int rsa_encrypt(int message, struct rsa_key *public)
 {
 	return modulo((message^public->exponent), public->modulo);
@@ -265,6 +277,52 @@ int rsa_decrypt_bignum(BIGNUM *message, BIGNUM *res, struct rsa_key_bignum *priv
 	return BN_mod_exp(res, message, private->exponent, private->modulo, ctx);
 }
 
+void extended_euclid_algo_bignum(BIGNUM *a, BIGNUM *b, struct extended_euclid_bignum *e)
+{
+	struct extended_euclid_bignum tmp;
+
+	if (BN_is_zero(b)) {
+		BN_copy(e->d, a);
+		BN_one(e->s);
+		BN_zero(e->t);
+		return;
+	}
+	tmp.d = BN_new();
+	tmp.s = BN_new();
+	tmp.t = BN_new();
+
+	BIGNUM *mod = BN_new();
+	BN_mod(mod, a, b, ctx);
+
+	extended_euclid_algo_bignum(b, mod, &tmp);
+	BN_copy(e->d, tmp.d);
+	BN_copy(e->s, tmp.t);
+	BN_div(mod, NULL, a, b, ctx);
+	BN_mul(mod, mod, tmp.t, ctx);
+	BN_sub(e->t, tmp.s, mod);
+	
+	
+	BN_free(mod);
+	BN_free(tmp.d);
+	BN_free(tmp.s);
+	BN_free(tmp.t);
+	return;
+}
+
+int modular_multiplicative_inverse_bignum_my(BIGNUM *res, BIGNUM *number, BIGNUM *modulo)
+{
+	struct extended_euclid_bignum tmp;
+	tmp.d = BN_new();
+	tmp.s = BN_new();
+	tmp.t = BN_new();
+	extended_euclid_algo_bignum(number, modulo, &tmp);
+	// only has a invese iff gcd = 1
+	if (!BN_is_one(tmp.d))
+		return -1;
+
+	return BN_nnmod(res, tmp.s, modulo, ctx);
+}
+
 int rsa_generate_key_bignum(struct rsa_key_bignum *public, struct rsa_key_bignum *private)
 {
 	// RSA with bignum
@@ -301,8 +359,9 @@ 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_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;
diff --git a/lib/lib5.h b/lib/lib5.h
index dbfd901..587e3e1 100644
--- a/lib/lib5.h
+++ b/lib/lib5.h
@@ -63,4 +63,6 @@ int modulo(int a, int b);
 void extended_euclid_algo(int a, int b, struct extended_euclid *e);
 int rsa_generate_key_bignum(struct rsa_key_bignum *public, struct rsa_key_bignum *private);
 int free_rsa_key_bignum(struct rsa_key_bignum *t);
+int modular_multiplicative_inverse_bignum_my(BIGNUM *res, BIGNUM *number, BIGNUM *modulo);
+int modular_multiplicative_inverse(int number, int _modulo);
 #endif
-- 
cgit v1.2.3-70-g09d2