Python interface to some OpenSSL BIGNUM routines

v1.05 - 25 Feb 2019

Provides python methods bignum.generate_prime(), bignum.is_prime(), and bignum.mod_inverse() which invoke openssl BN_generate_prime_ex(), BN_is_prime_ex(), and BN_mod_inverse() respectively.

Background: Although Python supports arbitrary size integers, including basic arithmetic operations and modular exponentiation, it does not have any built-in methods to generate or test prime numbers, or to perform modular inverse. Noting that Python's hashlib is mainly an interface to the OpenSSL hash functions, so it is already linked with that library, it makes sense to take advantage of other existing routines from there. This also serves as a demonstration of using both the Python and OpenSSL C APIs.

bignum.tar.gz - download

src/ - browse files

Requires python3 and openssl development libraries: Ubuntu# apt-get install python3-dev libssl-dev; Centos# yum install python36-devel openssl-devel


Docs:

bignum.generate_prime( nbits, safe=False, add=None, rem=1, cb=None, cb_arg=None)

Return a random prime.

If safe is true, it will be a safe prime (i.e. a prime p so that (p-1)/2 is also prime).

If add is specified, the prime will fulfill the condition p % add == rem.

If the callback cb is specified it will be called after generating the i'th potential prime number with arguments (0,i,cb_arg); while the number is being tested for primality, it will be called as from is_prime(); if safe is true it will be called when a prime has been found with arguments (2,i,cb_arg).

bignum.is_prime( p, nchecks=0, cb=None, cb_arg=None)

Test if a number is prime.

With nchecks=0 a number of iterations is used that yields a false positive rate of at most 2**-80 for random input.

If the callback cb is specified it will be called after the j'th iteration with arguments (1,j,cb_arg).

bignum.mod_inverse( a, n)

Returns the inverse of a modulo n.

Example: inverting the coefficient from java.util.Random::next()
% python3 -q
>>> import bignum
>>> a=0x5DEECE66D; a
25214903917
>>> m=1<<48; m
281474976710656
>>> ai=bignum.mod_inverse(a,m); ai
246154705703781
>>> hex(ai)
'0xdfe05bcb1365'
>>> ai*a
6206767253038249778610177
>>> ai*a % m
1
>>>
See test.py for more examples.
References:

Extending Python with C or C++

Python/C API Reference Manual

OpenSSL BN_generate_prime()

OpenSSL BN_mod_inverse()

Related:

gmpy2 - GMP/MPIR, MPFR, and MPC interface to Python 2.6+ and 3.x