summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/lib5.c207
-rw-r--r--lib/lib5.h13
2 files changed, 211 insertions, 9 deletions
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;
+}
+
diff --git a/lib/lib5.h b/lib/lib5.h
index 587e3e1..d78da21 100644
--- a/lib/lib5.h
+++ b/lib/lib5.h
@@ -4,7 +4,9 @@
#include <stdlib.h>
#include <stdint.h>
#include <gmp.h>
+#include <math.h>
#include <openssl/bn.h>
+#include<openssl/bio.h>
struct dh_param {
mpz_t A;
@@ -19,6 +21,7 @@ struct dh_param {
// global openssl context for auxaliry results
BN_CTX *ctx;
+BIO *out;
struct extended_euclid {
int d;
@@ -61,8 +64,18 @@ int rsa_decrpyt(int message, struct rsa_key *private);
int rsa_encrypt(int message, struct rsa_key *public);
int modulo(int a, int b);
void extended_euclid_algo(int a, int b, struct extended_euclid *e);
+void extended_euclid_algo_bignum(BIGNUM *a, BIGNUM *b, struct extended_euclid_bignum *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);
+int rsa_broadcast_cube(BIGNUM *res, BIGNUM **a, BIGNUM **n);
+int chinese_remainder_theorem_bignum(BIGNUM *solution, BIGNUM *sol_no_mod, BIGNUM **a, BIGNUM **n, int len);
+int check_co_prime_bignum(BIGNUM *a, BIGNUM *b);
+int check_co_prime_bignum(BIGNUM *a, BIGNUM *b);
+int __chinese_remainder_theorem_bignum(BIGNUM *solution, BIGNUM *sol_no_mod, BIGNUM **a, BIGNUM **n, int len);
+int check_co_prime(int a, int b);
+int __chinese_remainder_theorem(int *a, int *n, int len);
+int nth_root_bignum(BIGNUM *res, BIGNUM *number, BIGNUM *n);
+double nth_root_wr(double x, int n);
#endif
generated by cgit v1.2.3-70-g09d2 (git 2.52.0) at 2025-12-08 17:38:35 +0000