def gen_key():
while True:
p = getPrime(k/2)
if gcd(e, p-1) == 1:
break
q_t = getPrime(k/2)
n_t = p * q_t
t = get_bit(n_t, k/16, 1)
y = get_bit(n_t, 5*k/8, 0)
p4 = get_bit(p, 5*k/16, 1)
u = pi_b(p4, 1)
n = bytes_to_long(long_to_bytes(t) + long_to_bytes(u) + long_to_bytes(y))
q = n / p
if q % 2 == 0:
q += 1
while True:
if isPrime(q) and gcd(e, q-1) == 1:
break
m = getPrime(k/16) + 1
q ^= m
return (p, q, e)
python类isPrime()的实例源码
def test_isPrime(self):
"""Util.number.isPrime"""
self.assertEqual(number.isPrime(-3), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(-2), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(1), False) # Regression test: isPrime(1) caused some versions of PyCrypto to crash.
self.assertEqual(number.isPrime(2), True)
self.assertEqual(number.isPrime(3), True)
self.assertEqual(number.isPrime(4), False)
self.assertEqual(number.isPrime(2L**1279-1), True)
self.assertEqual(number.isPrime(-(2L**1279-1)), False) # Regression test: negative numbers should not be prime
# test some known gmp pseudo-primes taken from
# http://www.trnicely.net/misc/mpzspsp.html
for composite in (43 * 127 * 211, 61 * 151 * 211, 15259 * 30517,
346141L * 692281L, 1007119L * 2014237L, 3589477L * 7178953L,
4859419L * 9718837L, 2730439L * 5460877L,
245127919L * 490255837L, 963939391L * 1927878781L,
4186358431L * 8372716861L, 1576820467L * 3153640933L):
self.assertEqual(number.isPrime(long(composite)), False)
def test_isPrime(self):
"""Util.number.isPrime"""
self.assertEqual(number.isPrime(-3), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(-2), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(1), False) # Regression test: isPrime(1) caused some versions of PyCrypto to crash.
self.assertEqual(number.isPrime(2), True)
self.assertEqual(number.isPrime(3), True)
self.assertEqual(number.isPrime(4), False)
self.assertEqual(number.isPrime(2L**1279-1), True)
self.assertEqual(number.isPrime(-(2L**1279-1)), False) # Regression test: negative numbers should not be prime
# test some known gmp pseudo-primes taken from
# http://www.trnicely.net/misc/mpzspsp.html
for composite in (43 * 127 * 211, 61 * 151 * 211, 15259 * 30517,
346141L * 692281L, 1007119L * 2014237L, 3589477L * 7178953L,
4859419L * 9718837L, 2730439L * 5460877L,
245127919L * 490255837L, 963939391L * 1927878781L,
4186358431L * 8372716861L, 1576820467L * 3153640933L):
self.assertEqual(number.isPrime(long(composite)), False)
def _generate_prime(bits, rng):
"primtive attempt at prime generation"
hbyte_mask = pow(2, bits % 8) - 1
while True:
# loop catches the case where we increment n into a higher bit-range
x = rng.read((bits+7) // 8)
if hbyte_mask > 0:
x = chr(ord(x[0]) & hbyte_mask) + x[1:]
n = util.inflate_long(x, 1)
n |= 1
n |= (1 << (bits - 1))
while not number.isPrime(n):
n += 2
if util.bit_length(n) == bits:
break
return n
def test_isPrime(self):
"""Util.number.isPrime"""
self.assertEqual(number.isPrime(-3), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(-2), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(1), False) # Regression test: isPrime(1) caused some versions of PyCrypto to crash.
self.assertEqual(number.isPrime(2), True)
self.assertEqual(number.isPrime(3), True)
self.assertEqual(number.isPrime(4), False)
self.assertEqual(number.isPrime(2L**1279-1), True)
self.assertEqual(number.isPrime(-(2L**1279-1)), False) # Regression test: negative numbers should not be prime
# test some known gmp pseudo-primes taken from
# http://www.trnicely.net/misc/mpzspsp.html
for composite in (43 * 127 * 211, 61 * 151 * 211, 15259 * 30517,
346141L * 692281L, 1007119L * 2014237L, 3589477L * 7178953L,
4859419L * 9718837L, 2730439L * 5460877L,
245127919L * 490255837L, 963939391L * 1927878781L,
4186358431L * 8372716861L, 1576820467L * 3153640933L):
self.assertEqual(number.isPrime(long(composite)), False)
def test_isPrime(self):
"""Util.number.isPrime"""
self.assertEqual(number.isPrime(-3), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(-2), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(1), False) # Regression test: isPrime(1) caused some versions of PyCrypto to crash.
self.assertEqual(number.isPrime(2), True)
self.assertEqual(number.isPrime(3), True)
self.assertEqual(number.isPrime(4), False)
self.assertEqual(number.isPrime(2L**1279-1), True)
self.assertEqual(number.isPrime(-(2L**1279-1)), False) # Regression test: negative numbers should not be prime
# test some known gmp pseudo-primes taken from
# http://www.trnicely.net/misc/mpzspsp.html
for composite in (43 * 127 * 211, 61 * 151 * 211, 15259 * 30517,
346141L * 692281L, 1007119L * 2014237L, 3589477L * 7178953L,
4859419L * 9718837L, 2730439L * 5460877L,
245127919L * 490255837L, 963939391L * 1927878781L,
4186358431L * 8372716861L, 1576820467L * 3153640933L):
self.assertEqual(number.isPrime(long(composite)), False)
def test_isPrime(self):
"""Util.number.isPrime"""
self.assertEqual(number.isPrime(-3), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(-2), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(1), False) # Regression test: isPrime(1) caused some versions of PyCrypto to crash.
self.assertEqual(number.isPrime(2), True)
self.assertEqual(number.isPrime(3), True)
self.assertEqual(number.isPrime(4), False)
self.assertEqual(number.isPrime(2L**1279-1), True)
self.assertEqual(number.isPrime(-(2L**1279-1)), False) # Regression test: negative numbers should not be prime
# test some known gmp pseudo-primes taken from
# http://www.trnicely.net/misc/mpzspsp.html
for composite in (43 * 127 * 211, 61 * 151 * 211, 15259 * 30517,
346141L * 692281L, 1007119L * 2014237L, 3589477L * 7178953L,
4859419L * 9718837L, 2730439L * 5460877L,
245127919L * 490255837L, 963939391L * 1927878781L,
4186358431L * 8372716861L, 1576820467L * 3153640933L):
self.assertEqual(number.isPrime(long(composite)), False)
def test_isPrime(self):
"""Util.number.isPrime"""
self.assertEqual(number.isPrime(-3), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(-2), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(1), False) # Regression test: isPrime(1) caused some versions of PyCrypto to crash.
self.assertEqual(number.isPrime(2), True)
self.assertEqual(number.isPrime(3), True)
self.assertEqual(number.isPrime(4), False)
self.assertEqual(number.isPrime(2L**1279-1), True)
self.assertEqual(number.isPrime(-(2L**1279-1)), False) # Regression test: negative numbers should not be prime
# test some known gmp pseudo-primes taken from
# http://www.trnicely.net/misc/mpzspsp.html
for composite in (43 * 127 * 211, 61 * 151 * 211, 15259 * 30517,
346141L * 692281L, 1007119L * 2014237L, 3589477L * 7178953L,
4859419L * 9718837L, 2730439L * 5460877L,
245127919L * 490255837L, 963939391L * 1927878781L,
4186358431L * 8372716861L, 1576820467L * 3153640933L):
self.assertEqual(number.isPrime(long(composite)), False)
def test_isPrime(self):
"""Util.number.isPrime"""
self.assertEqual(number.isPrime(-3), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(-2), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(1), False) # Regression test: isPrime(1) caused some versions of PyCrypto to crash.
self.assertEqual(number.isPrime(2), True)
self.assertEqual(number.isPrime(3), True)
self.assertEqual(number.isPrime(4), False)
self.assertEqual(number.isPrime(2**1279-1), True)
self.assertEqual(number.isPrime(-(2**1279-1)), False) # Regression test: negative numbers should not be prime
# test some known gmp pseudo-primes taken from
# http://www.trnicely.net/misc/mpzspsp.html
for composite in (43 * 127 * 211, 61 * 151 * 211, 15259 * 30517,
346141 * 692281, 1007119 * 2014237, 3589477 * 7178953,
4859419 * 9718837, 2730439 * 5460877,
245127919 * 490255837, 963939391 * 1927878781,
4186358431 * 8372716861, 1576820467 * 3153640933):
self.assertEqual(number.isPrime(int(composite)), False)
def test_isPrime(self):
"""Util.number.isPrime"""
self.assertEqual(number.isPrime(-3), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(-2), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(1), False) # Regression test: isPrime(1) caused some versions of PyCrypto to crash.
self.assertEqual(number.isPrime(2), True)
self.assertEqual(number.isPrime(3), True)
self.assertEqual(number.isPrime(4), False)
self.assertEqual(number.isPrime(2L**1279-1), True)
self.assertEqual(number.isPrime(-(2L**1279-1)), False) # Regression test: negative numbers should not be prime
# test some known gmp pseudo-primes taken from
# http://www.trnicely.net/misc/mpzspsp.html
for composite in (43 * 127 * 211, 61 * 151 * 211, 15259 * 30517,
346141L * 692281L, 1007119L * 2014237L, 3589477L * 7178953L,
4859419L * 9718837L, 2730439L * 5460877L,
245127919L * 490255837L, 963939391L * 1927878781L,
4186358431L * 8372716861L, 1576820467L * 3153640933L):
self.assertEqual(number.isPrime(long(composite)), False)
def test_isPrime(self):
"""Util.number.isPrime"""
self.assertEqual(number.isPrime(-3), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(-2), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(1), False) # Regression test: isPrime(1) caused some versions of PyCrypto to crash.
self.assertEqual(number.isPrime(2), True)
self.assertEqual(number.isPrime(3), True)
self.assertEqual(number.isPrime(4), False)
self.assertEqual(number.isPrime(2L**1279-1), True)
self.assertEqual(number.isPrime(-(2L**1279-1)), False) # Regression test: negative numbers should not be prime
# test some known gmp pseudo-primes taken from
# http://www.trnicely.net/misc/mpzspsp.html
for composite in (43 * 127 * 211, 61 * 151 * 211, 15259 * 30517,
346141L * 692281L, 1007119L * 2014237L, 3589477L * 7178953L,
4859419L * 9718837L, 2730439L * 5460877L,
245127919L * 490255837L, 963939391L * 1927878781L,
4186358431L * 8372716861L, 1576820467L * 3153640933L):
self.assertEqual(number.isPrime(long(composite)), False)
def test_isPrime(self):
"""Util.number.isPrime"""
self.assertEqual(number.isPrime(-3), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(-2), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(1), False) # Regression test: isPrime(1) caused some versions of PyCrypto to crash.
self.assertEqual(number.isPrime(2), True)
self.assertEqual(number.isPrime(3), True)
self.assertEqual(number.isPrime(4), False)
self.assertEqual(number.isPrime(2L**1279-1), True)
self.assertEqual(number.isPrime(-(2L**1279-1)), False) # Regression test: negative numbers should not be prime
# test some known gmp pseudo-primes taken from
# http://www.trnicely.net/misc/mpzspsp.html
for composite in (43 * 127 * 211, 61 * 151 * 211, 15259 * 30517,
346141L * 692281L, 1007119L * 2014237L, 3589477L * 7178953L,
4859419L * 9718837L, 2730439L * 5460877L,
245127919L * 490255837L, 963939391L * 1927878781L,
4186358431L * 8372716861L, 1576820467L * 3153640933L):
self.assertEqual(number.isPrime(long(composite)), False)
def test_isPrime(self):
"""Util.number.isPrime"""
self.assertEqual(number.isPrime(-3), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(-2), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(1), False) # Regression test: isPrime(1) caused some versions of PyCrypto to crash.
self.assertEqual(number.isPrime(2), True)
self.assertEqual(number.isPrime(3), True)
self.assertEqual(number.isPrime(4), False)
self.assertEqual(number.isPrime(2L**1279-1), True)
self.assertEqual(number.isPrime(-(2L**1279-1)), False) # Regression test: negative numbers should not be prime
# test some known gmp pseudo-primes taken from
# http://www.trnicely.net/misc/mpzspsp.html
for composite in (43 * 127 * 211, 61 * 151 * 211, 15259 * 30517,
346141L * 692281L, 1007119L * 2014237L, 3589477L * 7178953L,
4859419L * 9718837L, 2730439L * 5460877L,
245127919L * 490255837L, 963939391L * 1927878781L,
4186358431L * 8372716861L, 1576820467L * 3153640933L):
self.assertEqual(number.isPrime(long(composite)), False)
def test_isPrime(self):
"""Util.number.isPrime"""
self.assertEqual(number.isPrime(-3), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(-2), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(1), False) # Regression test: isPrime(1) caused some versions of PyCrypto to crash.
self.assertEqual(number.isPrime(2), True)
self.assertEqual(number.isPrime(3), True)
self.assertEqual(number.isPrime(4), False)
self.assertEqual(number.isPrime(2**1279-1), True)
self.assertEqual(number.isPrime(-(2**1279-1)), False) # Regression test: negative numbers should not be prime
# test some known gmp pseudo-primes taken from
# http://www.trnicely.net/misc/mpzspsp.html
for composite in (43 * 127 * 211, 61 * 151 * 211, 15259 * 30517,
346141 * 692281, 1007119 * 2014237, 3589477 * 7178953,
4859419 * 9718837, 2730439 * 5460877,
245127919 * 490255837, 963939391 * 1927878781,
4186358431 * 8372716861, 1576820467 * 3153640933):
self.assertEqual(number.isPrime(int(composite)), False)
def validate_cryptosystem(self):
from Crypto.Util.number import isPrime
pk = self.public_key
if pow(pk.g, pk.q, pk.p) != 1:
m = "g is not a generator, or q is not its order!"
raise AssertionError(m)
if not isPrime(pk.p):
m = "modulus not prime!"
raise AssertionError(m)
if not isPrime(pk.q):
m = "subgroup order not prime!"
raise AssertionError(m)
if 2*pk.q + 1 != pk.p:
m = "modulus not in the form 2*(prime subgroup order) + 2"
raise AssertionError(m)
return 1
def test_isPrime(self):
"""Util.number.isPrime"""
self.assertEqual(number.isPrime(-3), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(-2), False) # Regression test: negative numbers should not be prime
self.assertEqual(number.isPrime(1), False) # Regression test: isPrime(1) caused some versions of PyCrypto to crash.
self.assertEqual(number.isPrime(2), True)
self.assertEqual(number.isPrime(3), True)
self.assertEqual(number.isPrime(4), False)
self.assertEqual(number.isPrime(2**1279-1), True)
self.assertEqual(number.isPrime(-(2**1279-1)), False) # Regression test: negative numbers should not be prime
# test some known gmp pseudo-primes taken from
# http://www.trnicely.net/misc/mpzspsp.html
for composite in (43 * 127 * 211, 61 * 151 * 211, 15259 * 30517,
346141 * 692281, 1007119 * 2014237, 3589477 * 7178953,
4859419 * 9718837, 2730439 * 5460877,
245127919 * 490255837, 963939391 * 1927878781,
4186358431 * 8372716861, 1576820467 * 3153640933):
self.assertEqual(number.isPrime(int(composite)), False)
def GenPrimeWithOracle(spriv, L, e):
'''
Generate p
'''
T = L/2 + 64
T1 = L - T
PRF = random.Random()
PRF.seed(spriv)
while True:
u = PRF.randint(2**(T-1), 2**T)
l = getRandomNBitInteger(T1)
p1 = int_add(u, l)
if isPrime(p1):
return p1
def GetPrimes(spub, spriv):
p1 = GenPrimeWithOracle(spriv, k/2, e)
while True:
s0 = getRandomNBitInteger(o - m - 1)
s = int_add(s0, spub)
t = pi_sit_x(o, s)
r2 = getRandomNBitInteger(k-o)
nc = int_add(t, r2)
q1 = nc / p1
if isPrime(q1):
return (p1, q1)
def _is_safe_prime(p, probability=params.FALSE_PRIME_PROBABILITY):
"""
Test if the number p is a safe prime.
A safe prime is one of the form p = 2q + 1, where q is also a prime.
Arguments:
p::long -- Any integer.
probability::int -- The desired maximum probability that p
or q may be composite numbers and still be
declared prime by our (probabilistic)
primality test. (Actual probability is
lower, this is just a maximum provable bound)
Returns:
True if p is a safe prime
False otherwise
"""
# Get q (p must be odd)
if(p % 2 == 0):
return False
q = (p - 1)/2
# q first to shortcut the most common False case
return (number.isPrime(q, false_positive_prob=probability)
and
number.isPrime(p, false_positive_prob=probability))
def _is_safe_prime(p, probability=params.FALSE_PRIME_PROBABILITY):
"""
Test if the number p is a safe prime.
A safe prime is one of the form p = 2q + 1, where q is also a prime.
Arguments:
p::long -- Any integer.
probability::int -- The desired maximum probability that p
or q may be composite numbers and still be
declared prime by our (probabilistic)
primality test. (Actual probability is
lower, this is just a maximum provable bound)
Returns:
True if p is a safe prime
False otherwise
"""
# Get q (p must be odd)
if(p % 2 == 0):
return False
q = (p - 1)/2
# q first to shortcut the most common False case
return (number.isPrime(q, false_positive_prob=probability)
and
number.isPrime(p, false_positive_prob=probability))
def _generate_safe_prime(nbits, probability=params.FALSE_PRIME_PROBABILITY,
task_monitor=None):
"""
Generate a safe prime of size nbits.
A safe prime is one of the form p = 2q + 1, where q is also a prime.
The prime p used for ElGamal must be a safe prime, otherwise some
attacks that rely on factoring the order p - 1 of the cyclic group
Z_{p}^{*} may become feasible if p - 1 does not have a large prime
factor. (p = 2q + 1, means p - 1 = 2q, which has a large prime factor,
namely q)
Arguments:
nbits::int -- Bit size of the safe prime p to generate.
This private method assumes that the
nbits parameter has already been checked to satisfy
all necessary security conditions.
probability::int -- The desired maximum probability that p
or q may be composite numbers and still be
declared prime by our (probabilistic)
primality test. (Actual probability is
lower, this is just a maximum provable bound)
task_monitor::TaskMonitor -- A task monitor for the process.
Returns:
p::long -- A safe prime.
"""
found = False
# We generate (probable) primes q of size (nbits - 1)
# until p = 2*q + 1 is also a prime
while(not found):
if(task_monitor != None): task_monitor.tick()
q = number.getPrime(nbits - 1)
p = 2*q + 1
if(not number.isPrime(p, probability)):
continue
# Are we sure about q, though? (pycrypto may allow a higher
# probability of q being composite than what we might like)
if(not number.isPrime(q, probability)):
continue # pragma: no cover (Too rare to test for)
found = True
# DEBUG CHECK: The prime p must be of size n=nbits, that is, in
# [2**(n-1),2**n] (and q must be of size nbits - 1)
if(params.DEBUG):
assert 2**(nbits - 1) < p < 2**(nbits), \
"p is not an nbits prime."
assert 2**(nbits - 2) < q < 2**(nbits - 1), \
"q is not an (nbits - 1) prime"
return p
def _generate_safe_prime(nbits, probability=params.FALSE_PRIME_PROBABILITY,
task_monitor=None):
"""
Generate a safe prime of size nbits.
A safe prime is one of the form p = 2q + 1, where q is also a prime.
The prime p used for ElGamal must be a safe prime, otherwise some
attacks that rely on factoring the order p - 1 of the cyclic group
Z_{p}^{*} may become feasible if p - 1 does not have a large prime
factor. (p = 2q + 1, means p - 1 = 2q, which has a large prime factor,
namely q)
Arguments:
nbits::int -- Bit size of the safe prime p to generate.
This private method assumes that the
nbits parameter has already been checked to satisfy
all necessary security conditions.
probability::int -- The desired maximum probability that p
or q may be composite numbers and still be
declared prime by our (probabilistic)
primality test. (Actual probability is
lower, this is just a maximum provable bound)
task_monitor::TaskMonitor -- A task monitor for the process.
Returns:
p::long -- A safe prime.
"""
found = False
# We generate (probable) primes q of size (nbits - 1)
# until p = 2*q + 1 is also a prime
while(not found):
if(task_monitor != None): task_monitor.tick()
q = number.getPrime(nbits - 1)
p = 2*q + 1
if(not number.isPrime(p, probability)):
continue
# Are we sure about q, though? (pycrypto may allow a higher
# probability of q being composite than what we might like)
if(not number.isPrime(q, probability)):
continue # pragma: no cover (Too rare to test for)
found = True
# DEBUG CHECK: The prime p must be of size n=nbits, that is, in
# [2**(n-1),2**n] (and q must be of size nbits - 1)
if(params.DEBUG):
assert 2**(nbits - 1) < p < 2**(nbits), \
"p is not an nbits prime."
assert 2**(nbits - 2) < q < 2**(nbits - 1), \
"q is not an (nbits - 1) prime"
return p
