On Tue 2015-05-26 14:02:07 -0400, Hubert Kario wrote:
> On Tuesday 26 May 2015 13:43:13 Daniel Kahn Gillmor wrote:
>> On Tue 2015-05-26 12:57:05 -0400, Hubert Kario wrote:
>> > creating composites that will pass even 100000 rounds of Miller-Rabin is
>> > relatively simple....
>> > (assuming the values for M-R tests are picked randomly)
>>
>> Can you point me to the algorithms for doing that?
>
> OEIS A014233
Hm, this is a sequence, but not an algorithm. It looks to me like it is
not exhaustive, just a list of those integers which are known to have
the stated property ("Smallest odd number for which Miller-Rabin
primality test on bases <= n-th prime does not reveal compositeness").
Taking the final integer in that sequence (a(11)) fails even the default
25-round M-R test in gmp:
>>> k = gmpy2.mpz(3825123056546413051)
>>> gmpy2.is_prime(k)
False
>>>
Indeed, the arxiv suggests that in 2012 people were still writing proofs
about a(11) for this sequence:
http://arxiv.org/abs/1207.0063
but i see no evidence that an algorithm for generating a(n) where n is
arbitrarily large exists. Does such a thing exist?
> yes, using ECPP and distributing proof with the prime (or just placing it on
> the project website) is a reasonable minimum, that still leaves out the
> possibility of a backdoor if the initial seed value is random
it sounds like we're heading into the same territory as the ECDH curve
selection discussion -- the theory you're suggesting is that some
safe-prime moduli could themselves have a backdoor that we don't know
about. Am i understanding you correctly?
I've been talking with several cryptographers for the last year about
finite-field DH (FFDH) and i haven't heard any suggestion that any of
them think there is likely to be such a class of backdoored moduli.
> yes, it would basically exclude the chance that the primes are backdoored,
> there's still the chance for the values to be composites
>
> for values to be used on this many machines, I'd say we should have primality
> proofs, not just M-R "guess"
Does anyone have a pointer to any decent free software for generating
and verifying primality proofs?
--dkg
Attachment:
signature.asc
Description: PGP signature
_______________________________________________ openssh-unix-dev mailing list openssh-unix-dev@xxxxxxxxxxx https://lists.mindrot.org/mailman/listinfo/openssh-unix-dev
