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

Michael D'Errico <mike-list@pobox.com> Thu, 29 October 2020 21:16 UTC

Return-Path: <mike-list@pobox.com>
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 8DBC43A0115 for <cfrg@ietfa.amsl.com>; Thu, 29 Oct 2020 14:16:10 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
X-Spam-Status: No, score=-2.098 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, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=pobox.com header.b=N8Y16JbR; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=SpTldeva
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 QDLwt2ciUb1A for <cfrg@ietfa.amsl.com>; Thu, 29 Oct 2020 14:16:07 -0700 (PDT)
Received: from out5-smtp.messagingengine.com (out5-smtp.messagingengine.com [66.111.4.29]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 53D9C3A0045 for <cfrg@irtf.org>; Thu, 29 Oct 2020 14:16:06 -0700 (PDT)
Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 644705C0135 for <cfrg@irtf.org>; Thu, 29 Oct 2020 17:16:05 -0400 (EDT)
Received: from imap21 ([10.202.2.71]) by compute4.internal (MEProxy); Thu, 29 Oct 2020 17:16:05 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pobox.com; h= mime-version:message-id:in-reply-to:references:date:from:to :subject:content-type:content-transfer-encoding; s=fm1; bh=XgXbb VrpinyJRB6i54t1nyMiUXKXCb6cij9LOLFDmtw=; b=N8Y16JbRvmNY8ZEnnh4Qi alew35tgnZ/IvogDHQcOUayitoaE72Dtn8SBXYGzQpVEcyV2KlSQGHsClsfe+ah8 TOCuCio1/YTaJbx+dFXn9sTozTOI+vn4AkGHwMxQp+b8ErxafduXsg3ni3T9yPZp MDsszmcHMbdXxHnzwvF1SKx1sm7VQ6ZJi23cZjzeMu9O2qhugtkN1HVAwg8v19X3 Sx+KG0B9iDFyFvuz+Ib03dHDyC/GnUeu+KGmTNuvuxmDLgOGknC3YU8sA9tXW1De pjBWfgih131Bot1ggapxoqOzbaiegeSoJXpzexzwI0/c/EBQxTcVzCwS6Ql/rpqS A==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-proxy:x-me-proxy:x-me-sender:x-me-sender :x-sasl-enc; s=fm1; bh=XgXbbVrpinyJRB6i54t1nyMiUXKXCb6cij9LOLFDm tw=; b=SpTldevaPKqXIZOllmpvOJDex/BmMMyAf1QkWdkVhhAt6fsobRp8Wvc/3 vu9B4GvF9aekgnmr0By05I53L4j9EG87R9x/ezIFl7bEqOhK9L4nfX/yQuzNHzwg pj255bh5SPfHkQJdSGU2Yz5ZLgzFbNIKeHkDSdfpYZha1HZUbWKalnsuHuUlrHfa L2eksNI74dHdOfsAoCRp16Z4f5UVfQFcqRgahzF0M2SnItYDBQ/S4eVnxnx3/mrE +EJNvKgtn7qO5mpjXM/DekBceMU0LnfhfcenhZLRKKokRYzzMUMqYDmfn8v9edjD GjvmXnLAu9+CAZrF+YiiUbtHELp4g==
X-ME-Sender: <xms:FTGbX6H1nCz3fxx9R9FyHCg-b1HwL9iGsL5R6YRu7OEh4wfy4qNSyg> <xme:FTGbX7VX5VkUn1sdA41NnE1uNz7-qymQWNhKbTMVYMqz2VhN3PdiWybBJvKrdt5Y6 HXe6wbtJk_Crm7QTw>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrleefgddugeehucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfgjfhffhffvufgtgfesth hqredtreerjeenucfhrhhomhepfdfoihgthhgrvghlucffkdfgrhhrihgtohdfuceomhhi khgvqdhlihhsthesphhosghogidrtghomheqnecuggftrfgrthhtvghrnhepudettdekge elteevueefueehjeeluddvheehudduteehffefheekueeuuefgffeunecuvehluhhsthgv rhfuihiivgeptdenucfrrghrrghmpehmrghilhhfrhhomhepmhhikhgvqdhlihhsthesph hosghogidrtghomh
X-ME-Proxy: <xmx:FTGbX0JOrxsdRnK_bKJKYTU8_JeGGxoEBU5h9-MFAxmFbQ3YCJo4fA> <xmx:FTGbX0EKr-86e0Ko1MMmb7-Rl6nVY0_JKCnOmt831ULPQm-f8XO6IQ> <xmx:FTGbXwWI7V43r76aGWhhxg7f4_TP6Diyem17-9MeyQrLNo3KVqQzhQ> <xmx:FTGbX4gTYEgYvofvHOLjMwA8ZjNsA2H-b5Eanc46bxF8gbIXe2XMQQ>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id C88DB660069; Thu, 29 Oct 2020 17:15:54 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.3.0-530-g8da6958-fm-20201021.003-g69105b13-v35
Mime-Version: 1.0
Message-Id: <7b0d0e0c-bb1d-46e3-b513-2a9327d21bd2@www.fastmail.com>
In-Reply-To: <817BB671-266A-41F1-89E8-4BB740B61B93@shiftleft.org>
References: <6f5bddd5-04c8-45bf-87b1-7bb1e852666f@www.fastmail.com> <817BB671-266A-41F1-89E8-4BB740B61B93@shiftleft.org>
Date: Thu, 29 Oct 2020 17:14:49 -0400
From: "Michael D'Errico" <mike-list@pobox.com>
To: cfrg@irtf.org
Content-Type: text/plain;charset=utf-8
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/q2YQYb6ljNhT8qQxMCk7b66TGHU>
Subject: Re: [CFRG] [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: Thu, 29 Oct 2020 21:16:11 -0000

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:
> 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 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