Re: [Newbie] Prime factorization question

From: Bill Unruh (unruh_at_string.physics.ubc.ca)
Date: 10/08/03 

Date: Wed, 8 Oct 2003 10:30:35 +0000 (UTC)

Mxsmanic <mxsmanic@hotmail.com> writes:

]Lorenzo Bolognini writes:

]> So they are known and sure they are prooven and certificated primes
]> (otherwise the cipher would be vulnerable to other attacks than plain
]> bruteforcing) and they are finite so the number of possible primes that may
]> generate the cipher is very much restricted...

]PGP selects prime numbers at random from the set of all prime numbers
]with appropriate lengths (n/2, where n is the desired length of the
]modulus). The number of primes at any given length is indeed finite,
]but it is very, very large for any modulus of the common sizes used in
]PGP (384 bits and up), and so there is no real risk of the same primes
]being selected for two different keys.

]The primality of the selected random numbers is not conclusively
]verified, but it is tested with an algorithm that provides a very high

While true, it now could be. There is a recent algorithm which can prove
conclusively that a number is prime or not.
PGP could now use that. It would make no difference.

]degree of certainty with respect to their primality (additionally, if p
]and q are not both prime, typically the encryption will fail in a fairly
]obvious way quite quickly).

]> well how many are they?

]For a 1024-bit modulus, you need two 512-bit primes. If I remember
]correctly, there are probably about 4 x 10^151 primes of that length or
]less. So even with a 1024-bit modulus, we will never run out of unique
]primes, and the possibility of getting two identical primes is, for all
]practical purposes, zero.

]I do wonder how many primes there are of _exactly_ n bits, but I'm not

The approximation (quite good) is 2^n/(nln(2))

]sure how to calculate or estimate that. Also, it's important that the
]primes be selected entirely at random.

Well, they are not. Primes which are far away from the next lower prime
are selected preferentially by the algoritm used. (Ie, if prime p_i is
the ith prime, then p_i is selected with a probability proportional to
p_i-p_(i-1). Thus a prime which is say 20 away from the next lower prime
will be selected with 10 times the probablility as one for which the
next lower prime is only 2 away.
However, I do not believe that anyone knows how to use this fact to aid
in the factoring.

Relevant Pages

  • Re: [Newbie] Prime factorization question
    ... Should I interpret this to mean that the decision to develop the modulus ... that is the product of something other than exactly two primes) ... and with far greater susceptibility to cracking through factorization. ... RSA is not completely sound, because it can still fail if one of the ...
    (sci.crypt)
  • Re: special DH prime
    ... represent the modulus as a polynomial with *much smaller* coefficients ... Primes with low Hamming weight are, on average, easier than general ... algorithms will react on special form moduli, ... than modular integers (otherwise I would have gone for elliptic curves) ...
    (sci.crypt)
  • Re: RSA moduli sizes
    ... bit RSA modulus be 1 we are effectively turning it into an -bit ... Since the best known factoring ... The sentence about "forcing the complexity as high ... two primes, uniformly at random, from a specified interval. ...
    (sci.crypt)
  • Re: [Newbie] Prime factorization question
    ... > generate the cipher is very much restricted... ... The number of primes at any given length is indeed finite, ... very large for any modulus of the common sizes used in ... The primality of the selected random numbers is not conclusively ...
    (sci.crypt)
  • Re: Algorithm For Ensuring p & q Sufficiently Large For n in RSA
    ... the product is indeed, say, 512 bits, for a 512-bit modulus. ... an N bits long product of two primes doesn't really contain N ... slightly more than 502.5 bits of entropy, so a 1024 bits long RSA ... the sieve of Eratosthenes or the sieve of Atkin. ...
    (sci.crypt)