[dns-operations] a maximum of about 16K possible DNSSEC keytags?
Jérôme Plût
jerome.plut at ssi.gouv.fr
Thu Dec 3 08:38:06 UTC 2015
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
More information about the dns-operations
mailing list