diff options
| -rw-r--r-- | lib/lib5.c | 207 | ||||
| -rw-r--r-- | lib/lib5.h | 13 | ||||
| -rw-r--r-- | set5/task40.c | 72 |
3 files changed, 283 insertions, 9 deletions
@@ -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; +} + @@ -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 diff --git a/set5/task40.c b/set5/task40.c new file mode 100644 index 0000000..42ce66e --- /dev/null +++ b/set5/task40.c @@ -0,0 +1,72 @@ +#include "../lib/lib.h" +#include "../lib/lib2.h" +#include "../lib/lib3.h" +#include "../lib/lib4.h" +#include "../lib/lib5.h" + +int main() +{ + int i; + struct rsa_key_bignum private[3]; + struct rsa_key_bignum public[3]; + BIGNUM *res = BN_new(); + BIGNUM *encrypted[3]; + BIGNUM *decrypted = BN_new(); + BIGNUM *ab[3]; + BIGNUM *nb[3]; + BIGNUM *solution_no_mod = BN_new(); + + out = BIO_new(BIO_s_file()); + BIO_set_fp(out, stdout, BIO_NOCLOSE); + + ctx = BN_CTX_new(); + + printf("encrypt the following message with three different keys:\n"); + unsigned char *mess = "All you need is love! Love is all you need"; + printf("%s\n", mess); + + for(i=0;i<2;i++) { + rsa_generate_key_bignum(&public[i], &private[i]); + do { + rsa_generate_key_bignum(&public[i+1], &private[i+1]); + } while (!BN_cmp(private[i].exponent, private[i+1].exponent)); + } + + printf("private keys:\n"); + for(i=0;i<3;i++) { + BN_print(out, private[i].exponent); + printf("\n"); + } + + BIGNUM *message = BN_bin2bn(mess, strlen(mess), NULL); + printf("message as BN:\n"); + BN_print(out, message); + printf("\nencrypted rsa messages:\n"); + for(i=0;i<3;i++) { + encrypted[i] = BN_new(); + if(!rsa_encrypt_bignum(message, encrypted[i], &public[i])) + die("could not rsa encrypt message"); + + BN_print(out, encrypted[i]); + printf("\n"); + } + + for(i=0;i<3;i++) { + ab[i] = BN_new(); + nb[i] = BN_new(); + BN_copy(ab[i], encrypted[i]); + BN_copy(nb[i], public[i].modulo); + } + + BIGNUM *n_3 = BN_new(); + BN_set_word(n_3, 3); + + rsa_broadcast_cube(res, ab, nb); + printf("\nrsa broadcast cube is\n"); + BN_print(out, res); + printf("\noriginal message is:\n"); + BN_print(out, message); + unsigned char *__dec = malloc(1000); + BN_bn2bin(res, __dec); + printf("\ndecrypted text with rsa broadcast attack: %s\n", __dec); +} |