def calculate_keys(p, q, nbits):
'''Calculates an encryption and a decryption key given p and q, and
returns them as a tuple (e, d)
'''
phi_n = (p - 1) * (q - 1)
# A very common choice for e is 65537
e = 65537
try:
d = rsa.common.inverse(e, phi_n)
except ValueError:
raise ValueError("e (%d) and phi_n (%d) are not relatively prime" %
(e, phi_n))
if (e * d) % phi_n != 1:
raise ValueError("e (%d) and d (%d) are not mult. inv. modulo "
"phi_n (%d)" % (e, d, phi_n))
return (e, d)
python类prime()的实例源码
def calculate_keys(p, q, nbits):
'''Calculates an encryption and a decryption key given p and q, and
returns them as a tuple (e, d)
'''
phi_n = (p - 1) * (q - 1)
# A very common choice for e is 65537
e = 65537
try:
d = rsa.common.inverse(e, phi_n)
except ValueError:
raise ValueError("e (%d) and phi_n (%d) are not relatively prime" %
(e, phi_n))
if (e * d) % phi_n != 1:
raise ValueError("e (%d) and d (%d) are not mult. inv. modulo "
"phi_n (%d)" % (e, d, phi_n))
return (e, d)
def calculate_keys(p, q, nbits):
'''Calculates an encryption and a decryption key given p and q, and
returns them as a tuple (e, d)
'''
phi_n = (p - 1) * (q - 1)
# A very common choice for e is 65537
e = 65537
try:
d = rsa.common.inverse(e, phi_n)
except ValueError:
raise ValueError("e (%d) and phi_n (%d) are not relatively prime" %
(e, phi_n))
if (e * d) % phi_n != 1:
raise ValueError("e (%d) and d (%d) are not mult. inv. modulo "
"phi_n (%d)" % (e, d, phi_n))
return (e, d)
def calculate_keys(p, q, nbits):
'''Calculates an encryption and a decryption key given p and q, and
returns them as a tuple (e, d)
'''
phi_n = (p - 1) * (q - 1)
# A very common choice for e is 65537
e = 65537
try:
d = rsa.common.inverse(e, phi_n)
except ValueError:
raise ValueError("e (%d) and phi_n (%d) are not relatively prime" %
(e, phi_n))
if (e * d) % phi_n != 1:
raise ValueError("e (%d) and d (%d) are not mult. inv. modulo "
"phi_n (%d)" % (e, d, phi_n))
return (e, d)
def test_is_prime(self):
"""Test some common primes."""
# Test some trivial numbers
self.assertFalse(rsa.prime.is_prime(-1))
self.assertFalse(rsa.prime.is_prime(0))
self.assertFalse(rsa.prime.is_prime(1))
self.assertTrue(rsa.prime.is_prime(2))
self.assertFalse(rsa.prime.is_prime(42))
self.assertTrue(rsa.prime.is_prime(41))
# Test some slightly larger numbers
self.assertEqual(
[907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997],
[x for x in range(901, 1000) if rsa.prime.is_prime(x)]
)
# Test around the 50th millionth known prime.
self.assertTrue(rsa.prime.is_prime(982451653))
self.assertFalse(rsa.prime.is_prime(982451653 * 961748941))
def test_mersenne_primes(self):
"""Tests first known Mersenne primes.
Mersenne primes are prime numbers that can be written in the form
`Mn = 2**n - 1` for some integer `n`. For the list of known Mersenne
primes, see:
https://en.wikipedia.org/wiki/Mersenne_prime#List_of_known_Mersenne_primes
"""
# List of known Mersenne exponents.
known_mersenne_exponents = [
2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279,
2203, 2281, 4423,
]
# Test Mersenne primes.
for exp in known_mersenne_exponents:
self.assertTrue(rsa.prime.is_prime(2**exp - 1))
def calculate_keys(p, q, nbits):
'''Calculates an encryption and a decryption key given p and q, and
returns them as a tuple (e, d)
'''
phi_n = (p - 1) * (q - 1)
# A very common choice for e is 65537
e = 65537
try:
d = rsa.common.inverse(e, phi_n)
except ValueError:
raise ValueError("e (%d) and phi_n (%d) are not relatively prime" %
(e, phi_n))
if (e * d) % phi_n != 1:
raise ValueError("e (%d) and d (%d) are not mult. inv. modulo "
"phi_n (%d)" % (e, d, phi_n))
return (e, d)
def test_is_prime(self):
"""Test some common primes."""
# Test some trivial numbers
self.assertFalse(rsa.prime.is_prime(-1))
self.assertFalse(rsa.prime.is_prime(0))
self.assertFalse(rsa.prime.is_prime(1))
self.assertTrue(rsa.prime.is_prime(2))
self.assertFalse(rsa.prime.is_prime(42))
self.assertTrue(rsa.prime.is_prime(41))
# Test some slightly larger numbers
self.assertEqual(
[907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997],
[x for x in range(901, 1000) if rsa.prime.is_prime(x)]
)
# Test around the 50th millionth known prime.
self.assertTrue(rsa.prime.is_prime(982451653))
self.assertFalse(rsa.prime.is_prime(982451653 * 961748941))
def gen_keys(nbits, getprime_func, accurate=True):
'''Generate RSA keys of nbits bits. Returns (p, q, e, d).
Note: this can take a long time, depending on the key size.
:param nbits: the total number of bits in ``p`` and ``q``. Both ``p`` and
``q`` will use ``nbits/2`` bits.
:param getprime_func: either :py:func:`rsa.prime.getprime` or a function
with similar signature.
'''
(p, q) = find_p_q(nbits // 2, getprime_func, accurate)
(e, d) = calculate_keys(p, q, nbits // 2)
return (p, q, e, d)
def _find_prime(nbits, pipe):
while True:
integer = rsa.randnum.read_random_int(nbits)
# Make sure it's odd
integer |= 1
# Test for primeness
if rsa.prime.is_prime(integer):
pipe.send(integer)
return
def getprime(nbits, poolsize):
'''Returns a prime number that can be stored in 'nbits' bits.
Works in multiple threads at the same time.
>>> p = getprime(128, 3)
>>> rsa.prime.is_prime(p-1)
False
>>> rsa.prime.is_prime(p)
True
>>> rsa.prime.is_prime(p+1)
False
>>> from rsa import common
>>> common.bit_size(p) == 128
True
'''
(pipe_recv, pipe_send) = mp.Pipe(duplex=False)
# Create processes
procs = [mp.Process(target=_find_prime, args=(nbits, pipe_send))
for _ in range(poolsize)]
[p.start() for p in procs]
result = pipe_recv.recv()
[p.terminate() for p in procs]
return result
def calculate_keys_custom_exponent(p, q, exponent):
"""Calculates an encryption and a decryption key given p, q and an exponent,
and returns them as a tuple (e, d)
:param p: the first large prime
:param q: the second large prime
:param exponent: the exponent for the key; only change this if you know
what you're doing, as the exponent influences how difficult your
private key can be cracked. A very common choice for e is 65537.
:type exponent: int
"""
phi_n = (p - 1) * (q - 1)
try:
d = rsa.common.inverse(exponent, phi_n)
except ValueError:
raise ValueError("e (%d) and phi_n (%d) are not relatively prime" %
(exponent, phi_n))
if (exponent * d) % phi_n != 1:
raise ValueError("e (%d) and d (%d) are not mult. inv. modulo "
"phi_n (%d)" % (exponent, d, phi_n))
return exponent, d
def calculate_keys(p, q):
"""Calculates an encryption and a decryption key given p and q, and
returns them as a tuple (e, d)
:param p: the first large prime
:param q: the second large prime
:return: tuple (e, d) with the encryption and decryption exponents.
"""
return calculate_keys_custom_exponent(p, q, DEFAULT_EXPONENT)
def gen_keys(nbits, getprime_func, accurate=True, exponent=DEFAULT_EXPONENT):
"""Generate RSA keys of nbits bits. Returns (p, q, e, d).
Note: this can take a long time, depending on the key size.
:param nbits: the total number of bits in ``p`` and ``q``. Both ``p`` and
``q`` will use ``nbits/2`` bits.
:param getprime_func: either :py:func:`rsa.prime.getprime` or a function
with similar signature.
:param exponent: the exponent for the key; only change this if you know
what you're doing, as the exponent influences how difficult your
private key can be cracked. A very common choice for e is 65537.
:type exponent: int
"""
# Regenerate p and q values, until calculate_keys doesn't raise a
# ValueError.
while True:
(p, q) = find_p_q(nbits // 2, getprime_func, accurate)
try:
(e, d) = calculate_keys_custom_exponent(p, q, exponent=exponent)
break
except ValueError:
pass
return p, q, e, d
def _find_prime(nbits, pipe):
while True:
integer = rsa.randnum.read_random_odd_int(nbits)
# Test for primeness
if rsa.prime.is_prime(integer):
pipe.send(integer)
return
def gen_keys(nbits, getprime_func, accurate=True):
'''Generate RSA keys of nbits bits. Returns (p, q, e, d).
Note: this can take a long time, depending on the key size.
:param nbits: the total number of bits in ``p`` and ``q``. Both ``p`` and
``q`` will use ``nbits/2`` bits.
:param getprime_func: either :py:func:`rsa.prime.getprime` or a function
with similar signature.
'''
(p, q) = find_p_q(nbits // 2, getprime_func, accurate)
(e, d) = calculate_keys(p, q, nbits // 2)
return (p, q, e, d)
def _find_prime(nbits, pipe):
while True:
integer = rsa.randnum.read_random_int(nbits)
# Make sure it's odd
integer |= 1
# Test for primeness
if rsa.prime.is_prime(integer):
pipe.send(integer)
return
def getprime(nbits, poolsize):
'''Returns a prime number that can be stored in 'nbits' bits.
Works in multiple threads at the same time.
>>> p = getprime(128, 3)
>>> rsa.prime.is_prime(p-1)
False
>>> rsa.prime.is_prime(p)
True
>>> rsa.prime.is_prime(p+1)
False
>>> from rsa import common
>>> common.bit_size(p) == 128
True
'''
(pipe_recv, pipe_send) = mp.Pipe(duplex=False)
# Create processes
procs = [mp.Process(target=_find_prime, args=(nbits, pipe_send))
for _ in range(poolsize)]
[p.start() for p in procs]
result = pipe_recv.recv()
[p.terminate() for p in procs]
return result
def calculate_keys_custom_exponent(p, q, exponent):
"""Calculates an encryption and a decryption key given p, q and an exponent,
and returns them as a tuple (e, d)
:param p: the first large prime
:param q: the second large prime
:param exponent: the exponent for the key; only change this if you know
what you're doing, as the exponent influences how difficult your
private key can be cracked. A very common choice for e is 65537.
:type exponent: int
"""
phi_n = (p - 1) * (q - 1)
try:
d = rsa.common.inverse(exponent, phi_n)
except ValueError:
raise ValueError("e (%d) and phi_n (%d) are not relatively prime" %
(exponent, phi_n))
if (exponent * d) % phi_n != 1:
raise ValueError("e (%d) and d (%d) are not mult. inv. modulo "
"phi_n (%d)" % (exponent, d, phi_n))
return exponent, d
def calculate_keys(p, q):
"""Calculates an encryption and a decryption key given p and q, and
returns them as a tuple (e, d)
:param p: the first large prime
:param q: the second large prime
:return: tuple (e, d) with the encryption and decryption exponents.
"""
return calculate_keys_custom_exponent(p, q, DEFAULT_EXPONENT)
def gen_keys(nbits, getprime_func, accurate=True, exponent=DEFAULT_EXPONENT):
"""Generate RSA keys of nbits bits. Returns (p, q, e, d).
Note: this can take a long time, depending on the key size.
:param nbits: the total number of bits in ``p`` and ``q``. Both ``p`` and
``q`` will use ``nbits/2`` bits.
:param getprime_func: either :py:func:`rsa.prime.getprime` or a function
with similar signature.
:param exponent: the exponent for the key; only change this if you know
what you're doing, as the exponent influences how difficult your
private key can be cracked. A very common choice for e is 65537.
:type exponent: int
"""
# Regenerate p and q values, until calculate_keys doesn't raise a
# ValueError.
while True:
(p, q) = find_p_q(nbits // 2, getprime_func, accurate)
try:
(e, d) = calculate_keys_custom_exponent(p, q, exponent=exponent)
break
except ValueError:
pass
return p, q, e, d
def _find_prime(nbits, pipe):
while True:
integer = rsa.randnum.read_random_odd_int(nbits)
# Test for primeness
if rsa.prime.is_prime(integer):
pipe.send(integer)
return
def calculate_keys_custom_exponent(p, q, exponent):
"""Calculates an encryption and a decryption key given p, q and an exponent,
and returns them as a tuple (e, d)
:param p: the first large prime
:param q: the second large prime
:param exponent: the exponent for the key; only change this if you know
what you're doing, as the exponent influences how difficult your
private key can be cracked. A very common choice for e is 65537.
:type exponent: int
"""
phi_n = (p - 1) * (q - 1)
try:
d = rsa.common.inverse(exponent, phi_n)
except ValueError:
raise ValueError("e (%d) and phi_n (%d) are not relatively prime" %
(exponent, phi_n))
if (exponent * d) % phi_n != 1:
raise ValueError("e (%d) and d (%d) are not mult. inv. modulo "
"phi_n (%d)" % (exponent, d, phi_n))
return exponent, d
def calculate_keys(p, q):
"""Calculates an encryption and a decryption key given p and q, and
returns them as a tuple (e, d)
:param p: the first large prime
:param q: the second large prime
:return: tuple (e, d) with the encryption and decryption exponents.
"""
return calculate_keys_custom_exponent(p, q, DEFAULT_EXPONENT)
def gen_keys(nbits, getprime_func, accurate=True, exponent=DEFAULT_EXPONENT):
"""Generate RSA keys of nbits bits. Returns (p, q, e, d).
Note: this can take a long time, depending on the key size.
:param nbits: the total number of bits in ``p`` and ``q``. Both ``p`` and
``q`` will use ``nbits/2`` bits.
:param getprime_func: either :py:func:`rsa.prime.getprime` or a function
with similar signature.
:param exponent: the exponent for the key; only change this if you know
what you're doing, as the exponent influences how difficult your
private key can be cracked. A very common choice for e is 65537.
:type exponent: int
"""
# Regenerate p and q values, until calculate_keys doesn't raise a
# ValueError.
while True:
(p, q) = find_p_q(nbits // 2, getprime_func, accurate)
try:
(e, d) = calculate_keys_custom_exponent(p, q, exponent=exponent)
break
except ValueError:
pass
return p, q, e, d
def _find_prime(nbits, pipe):
while True:
integer = rsa.randnum.read_random_odd_int(nbits)
# Test for primeness
if rsa.prime.is_prime(integer):
pipe.send(integer)
return
def calculate_keys_custom_exponent(p, q, exponent):
"""Calculates an encryption and a decryption key given p, q and an exponent,
and returns them as a tuple (e, d)
:param p: the first large prime
:param q: the second large prime
:param exponent: the exponent for the key; only change this if you know
what you're doing, as the exponent influences how difficult your
private key can be cracked. A very common choice for e is 65537.
:type exponent: int
"""
phi_n = (p - 1) * (q - 1)
try:
d = rsa.common.inverse(exponent, phi_n)
except ValueError:
raise ValueError("e (%d) and phi_n (%d) are not relatively prime" %
(exponent, phi_n))
if (exponent * d) % phi_n != 1:
raise ValueError("e (%d) and d (%d) are not mult. inv. modulo "
"phi_n (%d)" % (exponent, d, phi_n))
return exponent, d
def calculate_keys(p, q):
"""Calculates an encryption and a decryption key given p and q, and
returns them as a tuple (e, d)
:param p: the first large prime
:param q: the second large prime
:return: tuple (e, d) with the encryption and decryption exponents.
"""
return calculate_keys_custom_exponent(p, q, DEFAULT_EXPONENT)
def gen_keys(nbits, getprime_func, accurate=True, exponent=DEFAULT_EXPONENT):
"""Generate RSA keys of nbits bits. Returns (p, q, e, d).
Note: this can take a long time, depending on the key size.
:param nbits: the total number of bits in ``p`` and ``q``. Both ``p`` and
``q`` will use ``nbits/2`` bits.
:param getprime_func: either :py:func:`rsa.prime.getprime` or a function
with similar signature.
:param exponent: the exponent for the key; only change this if you know
what you're doing, as the exponent influences how difficult your
private key can be cracked. A very common choice for e is 65537.
:type exponent: int
"""
# Regenerate p and q values, until calculate_keys doesn't raise a
# ValueError.
while True:
(p, q) = find_p_q(nbits // 2, getprime_func, accurate)
try:
(e, d) = calculate_keys_custom_exponent(p, q, exponent=exponent)
break
except ValueError:
pass
return p, q, e, d
def _find_prime(nbits, pipe):
while True:
integer = rsa.randnum.read_random_odd_int(nbits)
# Test for primeness
if rsa.prime.is_prime(integer):
pipe.send(integer)
return
