diff options
Diffstat (limited to 'crypto/bn/bn_gcd.c')
-rw-r--r-- | crypto/bn/bn_gcd.c | 31 |
1 files changed, 31 insertions, 0 deletions
diff --git a/crypto/bn/bn_gcd.c b/crypto/bn/bn_gcd.c index 91ad76a161..519bb4e951 100644 --- a/crypto/bn/bn_gcd.c +++ b/crypto/bn/bn_gcd.c @@ -534,6 +534,37 @@ BIGNUM *BN_mod_inverse(BIGNUM *in, return rv; } +/* + * The numbers a and b are coprime if the only positive integer that is a + * divisor of both of them is 1. + * i.e. gcd(a,b) = 1. + * + * Coprimes have the property: b has a multiplicative inverse modulo a + * i.e there is some value x such that bx = 1 (mod a). + * + * Testing the modulo inverse is currently much faster than the constant + * time version of BN_gcd(). + */ +int BN_are_coprime(BIGNUM *a, const BIGNUM *b, BN_CTX *ctx) +{ + int ret = 0; + BIGNUM *tmp; + + BN_CTX_start(ctx); + tmp = BN_CTX_get(ctx); + if (tmp == NULL) + goto end; + + ERR_set_mark(); + BN_set_flags(a, BN_FLG_CONSTTIME); + ret = (BN_mod_inverse(tmp, a, b, ctx) != NULL); + /* Clear any errors (an error is returned if there is no inverse) */ + ERR_pop_to_mark(); +end: + BN_CTX_end(ctx); + return ret; +} + /*- * This function is based on the constant-time GCD work by Bernstein and Yang: * https://eprint.iacr.org/2019/266 |