diff options
| -rw-r--r-- | lib/lib5.c | 63 | ||||
| -rw-r--r-- | lib/lib5.h | 2 | ||||
| -rw-r--r-- | set5/task39.c | 96 |
3 files changed, 83 insertions, 78 deletions
@@ -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; @@ -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 diff --git a/set5/task39.c b/set5/task39.c index 9b4ad92..42c675c 100644 --- a/set5/task39.c +++ b/set5/task39.c @@ -8,76 +8,41 @@ #include<openssl/bn.h> #include<openssl/bio.h> -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); -} -/* - * TODO do it iterative, maybe stack it not big enough -void extended_euclid_algo_bignum(BIGNUM *a, BIGNUM *b, struct extended_euclid_bignum *e) -{ - struct extended_euclid_bignum tmp; - tmp.d = BN_new(); - tmp.s = BN_new(); - tmp.t = BN_new(); - if (BN_is_zero(b)) { - e->d=a; - BN_one(e->s); - BN_zero(e->t); - } - 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.s, ctx); - BN_sub(e->t, tmp.s, mod); - //BN_copy(e->t, ); - - BN_free(mod); - BN_free(tmp.d); - BN_free(tmp.s); - BN_free(tmp.t); - printf("durchlauf von extended_euclid durch\n"); - return; -} -int modular_multiplicative_inverse_bignum(BIGNUM *res, BIGNUM *number, BIGNUM *modulo) +int main_littlenum() { -// - 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; + int message = 65; + int p = 5, q = 11; + int n = p * q; + int et = (p-1) * (q-1); + int e = 3; - return BN_mod(res, tmp.s, modulo, ctx); + // does not work, nums are above INT_MAX + int d = modular_multiplicative_inverse(e, et); + // public key is [e, n], private key is [d, n] + struct rsa_key public = { .exponent = e, .modulo = n }; + struct rsa_key private = { .exponent = d, .modulo = n }; + printf("public key is: %i, %i\n", public.exponent, public.modulo); + printf("private key is: %i, %i\n", private.exponent, private.modulo); + int ciphertext = rsa_encrypt(message, &public); + printf("encrpyt %i: %i\n", message, ciphertext); + int dec_message = rsa_decrpyt(ciphertext, &private); + printf("decrypt %i: %i\n", ciphertext, dec_message); + return 0; } -*/ #define BN_DEBUG int main() { + struct rsa_key_bignum private, public; // debugging: printing BN's BIO *out = BIO_new(BIO_s_file()); BIO_set_fp(out, stdout, BIO_NOCLOSE); ctx = BN_CTX_new(); - + rsa_generate_key_bignum(&private, &public); printf("message:\n"); @@ -110,24 +75,3 @@ int main() free(public.exponent); } -int main_littlenum() -{ - int message = 65; - int p = 5, q = 11; - int n = p * q; - int et = (p-1) * (q-1); - int e = 3; - - // does not work, nums are above INT_MAX - int d = modular_multiplicative_inverse(e, et); - // public key is [e, n], private key is [d, n] - struct rsa_key public = { .exponent = e, .modulo = n }; - struct rsa_key private = { .exponent = d, .modulo = n }; - printf("public key is: %i, %i\n", public.exponent, public.modulo); - printf("private key is: %i, %i\n", private.exponent, private.modulo); - int ciphertext = rsa_encrypt(message, &public); - printf("encrpyt %i: %i\n", message, ciphertext); - int dec_message = rsa_decrpyt(ciphertext, &private); - printf("decrypt %i: %i\n", ciphertext, dec_message); - return 0; -} |