Re: [Newbie] Prime factorization question

From: Mxsmanic (mxsmanic_at_hotmail.com)
Date: 10/07/03 

Date: Tue, 07 Oct 2003 17:10:37 +0200

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
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
sure how to calculate or estimate that. Also, it's important that the
primes be selected entirely at random. 

-- 
Transpose hotmail and mxsmanic in my e-mail address to reach me directly.

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: 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)
  • Re: [Newbie] Prime factorization question
    ... ]> bruteforcing) and they are finite so the number of possible primes that may ... ]> generate the cipher is very much restricted... ... very large for any modulus of the common sizes used in ... Thus a prime which is say 20 away from the next lower prime ...
    (sci.crypt)