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?

  • 1
    Can you provide some examples of the primes you are concerned about? Do you mean with no zeros appearing in the decimal representation, or hexadecimal representation, or what? – Ella Rose Oct 30 at 2:17
  • 3
    There are currently 50 known primes that do not include any zero bits; are your colleges suggesting that we limit the primes used in RSA to that list? – poncho Oct 30 at 2:26
  • not zero in prime data, in the private exponents during the modular multiplication can cause side-channel attacks that can be prevented. Your question needs improvising. – kelalaka Oct 30 at 6:05
  • @poncho you could only really use the first 14 to stick with 1024 bit Mersenne primes and you'd have to pad with.... oh wait. – daniel Oct 30 at 11:28

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})>2^{469}$ for 512-bit primes suitable for 1024-bit keys of FIPS 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?

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?

If you mean by brute force factorization, keeping a list of prime and test them, I should say why only 0x0, this contains 4 zeros, then 0x87 and 0x42 are containing 4 zeroes, too. Even 0x81 containing 6 consecutive zeroes. The fastest factoring algorithms are not concentrated on this.

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 the open source code that removes zeros from the random data.

DPA attacks and timing attack are performed on the private key $d$ of RSA, not on the primes $p$ and $q$. For example; in a standard implementation od repeated squaring algorithm, 0 means only squaring and 1 means square and multiply, see in this picture.

A timing attack can be executed on this to reveal the bits of the private key $d$, see Kocher's paper. As noted by Frigue's The practical implementations are using CRT based RSA calculations to speed up around 4-times. In this case, the attacks must try to extract $d_p$ and $d_q$ from the calculations. The attacks are not considering there are consecutive 0's or 1's. They just look for the difference between 0 and 1 in the private key.

Which is more of a concern? Attack, or a subset of primes?

Let me clear here; Side Channel attack are important and some primes but not as in your case;

For example;

  • Primes factor of $p-1$ and $p+1$

    • FIPS 186-4 recommendation; $p−1$ and $p+1$ should have a suitably large prime factor for 512-bit, see Table 1 for more details.
    • A small set of weak primes;

    $p$ is a weak prime, that is, $p$ can be expressed as a $p = u_0 + M_1u_1 + \ldots + M_ku_k$ for some $k$ integers $M_1,\ldots, M_k$ and $k + 2$ suitably small parameters $a, u_0, \ldots, u+k$) can have faster attacks.

  • A timing attacks, or in general Side-Channel attacks can steal very easily the private key. Countermasures are required as;

    • RSA blinding; Let $r$ be a random value, such that $0 < r < N$. $$(r^e C)^d r^{-1} \equiv r^{ed−1} C^d \pmod N$$ Since $ ed \equiv 1 \bmod \lambda (N)$ and $r^{ed−1} \equiv 1 \pmod N$. With the random $r$ the private key has transferred into another form to prevent the timing attack.
  • 1
    The particular class of weak primes that the linked article considers is small enough that it practically is disregarded when choosing the primes randomly. AFAIK the only (marginally) practiced precaution is ensuring $p-1$ and $p+1$ have a suitably large prime factor (as required by FIPS 186-4 for 512-bit primes), and then that's useful only when generating many keys and an adversary is content with breaking a random key, rather than breaking a particular key; or/and perhaps for multiprime RSA. – fgrieu Oct 30 at 9:42
  • 1
    First bullet needs an extra opening parenthesis. "Cahnnel"-> Channel. "blending"->blinding. "$\pmod C$"->$\pmod N$. "Since $N=pq$" is not very helpful as a justification, since $p$ and $q$ appear nowhere else in the surrounding expressions. It seems that it should rather be invoked that $e\,d\equiv1\pmod{\lambda(N)}$; or/and $\gcd(N,r)=1$, either with high likelihood or by choice of $r$. – fgrieu Oct 30 at 9:45

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.