diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/lib5.c | 63 | ||||
| -rw-r--r-- | lib/lib5.h | 2 |
2 files changed, 63 insertions, 2 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 |