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

Michael D'Errico <mike-list@pobox.com> Wed, 28 October 2020 19:41 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 04DA73A0C00 for <cfrg@ietfa.amsl.com>; Wed, 28 Oct 2020 12:41:19 -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=AOADvBs/; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=BAyCp6e+
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 uoj57zXuYX-D for <cfrg@ietfa.amsl.com>; Wed, 28 Oct 2020 12:41:17 -0700 (PDT)
Received: from out2-smtp.messagingengine.com (out2-smtp.messagingengine.com [66.111.4.26]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id BC4923A0BFD for <cfrg@irtf.org>; Wed, 28 Oct 2020 12:41:17 -0700 (PDT)
Received: from compute4.internal (compute4.nyi.internal [10.202.2.44]) by mailout.nyi.internal (Postfix) with ESMTP id 7527C5C012E for <cfrg@irtf.org>; Wed, 28 Oct 2020 15:41:16 -0400 (EDT)
Received: from imap21 ([10.202.2.71]) by compute4.internal (MEProxy); Wed, 28 Oct 2020 15:41:16 -0400
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=pobox.com; h= mime-version:message-id:date:from:to:subject:content-type; s= fm1; bh=vG2EN5vCkOvcP5IIkQlRZiSP1mvfwukMIKW7DrZ71aw=; b=AOADvBs/ pjtMvIsBa2PHIX2PSKG25B8QskxZbZgcf/A0KsVoZ6o64rgvmaiNypRoYg+vVCXN 9Dr8PrG73RHnfirGw9FSxysO+Qj0jyLE8JMVH+rjoa/t+XSw2yOGiUf3AGNSzTW7 I+Pr9SH3DfgZZpDLiDGGC6s2kexhV7F4nPU+y1vCxbLoQ8K+VzBZNfzArL+u78Le cyY3LyXQ5YkA0aKY8mobAVy0ICeoYsYJCHd4EProerVGQhf39MZ7miphO9+bKAY4 4nJKeZmuZOaJKPOYHMsdrJ7SXK83rODWPZGdQCb8rY07GZrpxpaXPpvq63q4k26E IGrH0aHtLATBjw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-type:date:from:message-id :mime-version:subject:to:x-me-proxy:x-me-proxy:x-me-sender :x-me-sender:x-sasl-enc; s=fm1; bh=vG2EN5vCkOvcP5IIkQlRZiSP1mvfw ukMIKW7DrZ71aw=; b=BAyCp6e+cKDi2dwZQPRuI4TeK8vi2mDaD37Lm1Lm14npv euJVthplAPQXoxyK+lJtzdTb8JNjG7xWOEd1djWjgNVODDnX0DOfSxrOGOmR63NQ aQQ5H9mJJrPCyL+MiUMPGWSbdYpvlLze5towoF8MVVC3zKYA6DV/1x6nmJDpYJ1Z tpE1wLfHEUFZOTfkVwylu4IkCRAAJDauzO2NWYEqH9moiydgof9/zd2yOQ0gx9UE Y2TqPMRXw+7cI//Y7pxMd1A32Y+1urHkCpwx+T/BlTWRutSme2iBvzSrH3qa59HI daqI0Vl9sx77aV9RbCytNFeVB6yQcLAbg47mnsIdQ==
X-ME-Sender: <xms:W8mZX3qD8bl9TmH5Gb3ps4xNIUsezezMQXFjgOZrX5zd1xtft63uZw> <xme:W8mZXxqzYnD0dxJd2YomRqwcU7rYo4u_GgHcuM2XHB9cVdAK-jcmIfOExSBsmj6wG dYbHAtZqoT1Z0Oaow>
X-ME-Proxy-Cause: gggruggvucftvghtrhhoucdtuddrgedujedrledugdduvdehucetufdoteggodetrfdotf fvucfrrhhofhhilhgvmecuhfgrshhtofgrihhlpdfqfgfvpdfurfetoffkrfgpnffqhgen uceurghilhhouhhtmecufedttdenucenucfjughrpefofgggkfffhffvufgtsehttdertd erredtnecuhfhrohhmpedfofhitghhrggvlhcuffdkgfhrrhhitghofdcuoehmihhkvgdq lhhishhtsehpohgsohigrdgtohhmqeenucggtffrrghtthgvrhhnpeethffgtddvieetle ehueevheduhfdtudeuueeikeeiheehfeefvdfgudffkeelieenucevlhhushhtvghrufhi iigvpedtnecurfgrrhgrmhepmhgrihhlfhhrohhmpehmihhkvgdqlhhishhtsehpohgsoh igrdgtohhm
X-ME-Proxy: <xmx:W8mZX0P2RyaDJNR3pN2TtsiuaB8AjiTy0sR-akwofVwxMAISARuM9g> <xmx:W8mZX654i1iy0Glr3e9WvJ8IgUbCvN8dc0nLsLLwtFZqkhDwZYT51g> <xmx:W8mZX256emIpwiHe7VpOsDShfvtZbfvnKTeh2sb-5p6rVlL6AR--WA> <xmx:XMmZX4EjvUtlO_7XBfEUrdwehlMXSJjB-TedVRm6RKOJ7Sm62_7NKw>
Received: by mailuser.nyi.internal (Postfix, from userid 501) id C596566006F; Wed, 28 Oct 2020 15:41:05 -0400 (EDT)
X-Mailer: MessagingEngine.com Webmail Interface
User-Agent: Cyrus-JMAP/3.3.0-529-g69105b1-fm-20201021.003-g69105b13
Mime-Version: 1.0
Message-Id: <6f5bddd5-04c8-45bf-87b1-7bb1e852666f@www.fastmail.com>
Date: Wed, 28 Oct 2020 15:38:26 -0400
From: "Michael D'Errico" <mike-list@pobox.com>
To: cfrg@irtf.org
Content-Type: text/plain
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/GZFMRENUhG1tYfhwPXa-0HeLu8M>
Subject: [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 19:41:19 -0000

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