RSA: Should the generation of random data used for primes include zero When generating random data that is later tested for primality, should the random data include the value 0x0?

I would have thought that primes that do not include zero's are a subset of the set of primes that do - and therefore make keys generated with no zero's easier to brute force?

However my colleges are of the opinion that having zero in the prime data makes the key operations consume less time / and or power, and thus make these keys more vulnerable to a DPA / timing based attack. They have also seen open source code that removes zeros from the random data. 

Which is more of a concern? Attack, or a subset of primes?
When generating random data that is later tested for primality, should the random data include the value 0x0?


I'm reading this as: should the hexadecimal expression of the primes include the hexadecimal digit 0?

With hight likelihood yes. But that needs not/should not be tested. Common wisdom is that except for the few high-order bits (constrained by range considerations) and the low-order bit (which is set), all bit sequences much shorter than the prime itself should be random-like, thus about 1/16 of hexadecimal digits other than the low-order and high-order are expected to contain the hexadecimal digit 0x0.


  (Aren't) keys generated with no zero's easier to brute force?


Not sizably. Indeed, preventing the hexadecimal digit 0x0 to appear would reduces the possible primes. However, there remains so many that trying to factor an RSA public modulus by enumerating the candidate primes (roughly $2^{510\cdot15/16}/\log(2^{512})&gt;2^{469}$ for 512-bit primes suitable for 1024-bit keys of FIPS&nbsp;186-4 format) remains  hopeless anyway. And we know no efficient factorization algorithm that can take advantage of the special form of these primes.


  (..) my colleagues are of the opinion that having zero in the prime data makes the key operations consume less time / and or power, and thus make these keys more vulnerable to a DPA / timing based attack. They have also seen open source code that removes zeros from the random data.


To my knowledge, there is no evidence that accidentally having zeroes in the hexadecimal expression of the primes has sizable chance to enable a DPA / timing based attack. Arguments: long sequences of zeroes will be statistically rare; if there's data-dependent timing variation or potential for DPA attack in an implementation, that must be mitigated anyway; we could make the same argument for 0xF; on the contrary, knowing that there are not zero could conceivably speed-up some side-channel attack.

I do not know an open source RSA key generation code purposely weeding out primes with an excess of zeroes. And I'm reasonably confident that no public standard (from ANSI, BSI, ETSI, IEC, IETF, ISO, NIST, or the company formerly known as RSA security) asks for that. Do the person(s) with this recollection also remember what open source code does that, so that said recollection can be cross-checked, and perhaps a rationale found from comments or a reference?