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

From: "Michael D'Errico" <[email-masked]>
Date: Wed, 28 Oct 2020 15:38:26 -0400

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

---

From: Mike Hamburg <[email-masked]>
Date: Wed, 28 Oct 2020 20:17:43 +0000

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 <[email-masked]> wrote:
> 
> Hi,
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: "Michael D'Errico" <[email-masked]>
Date: Thu, 29 Oct 2020 17:14:49 -0400

Hi Mike,

Thanks for providing your insight into this problem
and your conclusions.

I'm trying to answer the question: "How do we pick the
best modulus M for use with Diffie-Hellman?"  So my
interest in this is more academic; I'm not necessarily
concerned with speed of computation, at least not now.

It may be true that M+1 is more important than M itself.

This conjecture comes about because of the previous
thread I started here, and the fact that while addition
modulo M is cyclic with period M, exponentiation modulo
M is cyclic with period M-1 (Fermat's little theorem),
so maybe we've introduced an off-by-one error in our
use of DH.

The idea I presented below is to have M+1 be prime
instead of M, and then figure out how to choose M such
that Diffie-Hellman still works, and is not easy to
mess up.  M-1 also seems important, so finding an M
sandwiched between a pair of twin primes might be a
good idea.

So I'd still appreciate a pointer to a reference which
explains the procedure and caveats associated with using
a composite modulus in Diffie-Hellman, if you know of
any.

Thank you,

Mike

On Wed, Oct 28, 2020, at 16:17, Mike Hamburg wrote:
> p as the wire format, not mod pq.  In particular, it’s strictly
> better to do DH mod p instead of mod p^n.
> 
> 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.
> 
>> On Oct 28, 2020, at 7:38 PM, Michael D'Errico wrote:
>> 
>> Hi,
>>

---

From: "Scott Fluhrer (sfluhrer)" <[email-masked]>
Date: Thu, 29 Oct 2020 22:16:23 +0000

> -----Original Message-----
> From: CFRG <[email-masked]> On Behalf Of Michael D'Errico
> Sent: Thursday, October 29, 2020 5:15 PM
> To: [email-masked]
> Subject: Re: [CFRG] [Cfrg] Using Diffie-Hellman With a Non-prime Modulus
> 
> Hi Mike,
> 
> Thanks for providing your insight into this problem and your conclusions.
> 
> I'm trying to answer the question: "How do we pick the best modulus M for
> use with Diffie-Hellman?"  So my interest in this is more academic; I'm not
> necessarily concerned with speed of computation, at least not now.
> 
> This conjecture comes about because of the previous thread I started here,
> and the fact that while addition modulo M is cyclic with period M,
> exponentiation modulo M is cyclic with period M-1 (Fermat's little theorem),
> so maybe we've introduced an off-by-one error in our use of DH.

It's not true in general that exponentiation modulo M is cyclic with period M-1.  It is true if M is prime; however you are considering composite M, hence Fermat does not apply.

> 
> The idea I presented below is to have M+1 be prime instead of M, and then
> figure out how to choose M such that Diffie-Hellman still works, and is not
> easy to mess up.  M-1 also seems important, so finding an M sandwiched
> between a pair of twin primes might be a good idea.
> 
> So I'd still appreciate a pointer to a reference which explains the procedure
> and caveats associated with using a composite modulus in Diffie-Hellman, if
> you know of any.

Mike Hamburg already outlined the issues for M with public factorization. For M with a secret factorization, there are a number of ways for us to hide a backdoor in the DH operation, for example, https://eprint.iacr.org/2016/644.pdf (not the best, IMHO, just the first reference I found) - hence, good luck in getting anyone to trust that you didn't...

> > 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.
> >
> > 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.
> >
> > 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
> >
> >> 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
> [email-masked]

---

From: Michael D'Errico <[email-masked]>
Date: Thu, 29 Oct 2020 22:28:46 -0400

> It's not true in general that exponentiation modulo M is cyclic with period M-1.  It is true if M is prime; however you are considering composite M, hence Fermat does not apply.

My point exactly.  All the current published groups
have a prime modulus M, which might be problematic
due to Fermat.  This leads me to consider non-prime
moduli as a possible improvement.

> Mike Hamburg already outlined the issues for M with public factorization. For M with a secret factorization, there are a number of ways for us to hide a backdoor in the DH operation, for example, h…

I'm not doing anything in secret.  It's all here on
this mailing list.  Sure, one part of the threat
model of the Internet is that the standards writers
are sabotaging the very standards we're relying on.
I've no doubt that this has occurred and is occurring
now.  If I can't figure out a way to objectively show
that my results are better than the current groups
then I won't pursue it further.  I've no stake in
this other than trying to make the Internet better.

Thank you for providing a reference.

Mike