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
评论列表
文章目录
