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

Mike Hamburg <mike@shiftleft.org> Wed, 28 October 2020 20:17 UTC

Return-Path: <mike@shiftleft.org>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1BFDD3A09F1 for <cfrg@ietfa.amsl.com>; Wed, 28 Oct 2020 13:17:49 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.306
X-Spam-Level:
X-Spam-Status: No, score=-1.306 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RDNS_NONE=0.793, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=shiftleft.org
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id rMQbr635m1_c for <cfrg@ietfa.amsl.com>; Wed, 28 Oct 2020 13:17:47 -0700 (PDT)
Received: from astral.shiftleft.org (unknown [54.219.126.124]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id A2E6D3A09EC for <cfrg@irtf.org>; Wed, 28 Oct 2020 13:17:47 -0700 (PDT)
Received: from [192.168.12.174] (unknown [95.83.226.208]) (Authenticated sender: mike) by astral.shiftleft.org (Postfix) with ESMTPSA id 17CFCBB8F0; Wed, 28 Oct 2020 20:17:45 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=shiftleft.org; s=sldo; t=1603916266; bh=58CJnhMalWcUb9NsbEQ3dJBhP0ghXzHU3niGo//HMQU=; h=Subject:From:In-Reply-To:Date:Cc:References:To:From; b=JC+IpRVhNZ0Rf1CaNoAM1CUq4sc8yU/DshJIT+vGMv0/kDV6OQ+WFnEBOJE3KO4GV FemsDbsM0o9IbjKEmKrb7UUOk6oZ1I8g8/TiSu3pBSgW4ze1M5eO/xpnnno6J7g16z 0xfixaconPfuCco3N8JneZx/scGTg8gR/+iPn3tA=
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.120.23.2.4\))
From: Mike Hamburg <mike@shiftleft.org>
In-Reply-To: <6f5bddd5-04c8-45bf-87b1-7bb1e852666f@www.fastmail.com>
Date: Wed, 28 Oct 2020 20:17:43 +0000
Cc: cfrg@irtf.org
Content-Transfer-Encoding: quoted-printable
Message-Id: <817BB671-266A-41F1-89E8-4BB740B61B93@shiftleft.org>
References: <6f5bddd5-04c8-45bf-87b1-7bb1e852666f@www.fastmail.com>
To: Michael D'Errico <mike-list@pobox.com>
X-Mailer: Apple Mail (2.3608.120.23.2.4)
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/02fR6-fuYFe--MzS6v9-KVUl3mM>
Subject: Re: [Cfrg] Using Diffie-Hellman With a Non-prime Modulus
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 28 Oct 2020 20:17:49 -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 <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