Re: [Cfrg] Using Diffie-Hellman With a Non-prime Modulus

Hello Mike,

If you do DH mod p*q, then this can be attacked by solving discrete
log mod p and mod q, and then using the Chinese Remainder
Theorem.  Mod p^n isn’t any better, and GF(p^n) kinda works but is
much weaker due to Joux et al’s recent work.  So you won’t get
extra security this way.

So overall, there’s no reason to do the math mod pq unless it's
somehow faster than mod p, and even then you would use mod
p as the wire format, not mod pq.  In particular, it’s strictly better
to do DH mod p instead of mod p^n.

I’ve looked into using pq for the purposes of faster arithmetic for
elliptic curves or postquantum crypto, but I didn’t find a case where
it was clearly worthwhile. It’s also generally not great for DH, because
the kinds of p that would be fast enough for this to be plausibly
worthwhile are the same types where the special number field sieve
poses a risk.

You could also use math mod pq where p and q are secret, but
I’m not sure why you’d do that for DH.

Cheers,
— Mike

> On Oct 28, 2020, at 7:38 PM, Michael D'Errico <mike-list@pobox.com> wrote:
> 
> Hi,
> 
> Can someone please point me to a reference showing
> how to use Diffie-Hellman where the modulus is not 
> a prime number?  Preferably one readable by laymen.
> 
> The reason for this is I'm considering looking for 
> a modulus M which is not prime, but where M is the 
> number between some pair of Twin Primes, and also 
> maybe where M is a prime times a power of two.
> 
> I found at least one of these: 786431,786433 is a 
> twin prime pair with midpoint 3*2^18.
> 
> I'd hope to find an M whose odd prime factor is 
> very large.
> 
> Thanks,
> 
> Mike
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg