[dns-operations] a maximum of about 16K possible DNSSEC keytags?

[Jérôme Plût]

On 12/02/15 18:41, Roy Arends wrote:
> Ah indeed. it seems that openssl avoids primes that are congruent to 1 modulo 3,
> so that will cause the available solution space to be reduced to 4*16*256 == 16384

To elaborate a bit on this, another colleague, Jean-René Reinhard, found the
last missing bit of explanation: OpenSSL generates only RSA primes, i.e. primes
of the form p=2p'+1 where p' is also prime. (Such primes give a high assurance
against factoring through methods of type (p-1)).

This implies in particular that p cannot be ≡ 1 (mod 3), or more generally (mod
l) for any other prime l. Running the probabilities on this, I obtain the
following distribution of probabilities for the modulus N = p.q:

N ≡ 1 (mod l) with probability 1/(l-2)
N ≡ other (mod l) with probability (l-3)/(l-2)^2   (for each "other").


Proof is left as an exercise :-), but numerical application follows:

N ≡ 1 (mod 3) with probability 1
N ≡ 1 (mod 5) with probability 1/3 ≈ 33%
  ≡ other (mod 5) with probability 2/9 ≈ 22%
N ≡ 1 (mod 17) with probability 1/15 ≈ 6.7%
  ≡ other (mod 17) with probability 14/225 ≈ 6.2%

I plotted the empirical distribution of these for the moduli values that Florian
sent me, and I am happy to announce that the empirical distribution seems to
match these expected values quite well.

-- 
	Jérôme Plût