Re: [Cfrg] Prime 630*(427!+1)+1 for classic DH?

"Anna (Amy) Johnston" <> Thu, 06 April 2017 03:37 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id EE0971201F2 for <>; Wed, 5 Apr 2017 20:37:14 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.005
X-Spam-Status: No, score=-1.005 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, PLING_QUERY=0.994, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id JECIBG3Vsu_v for <>; Wed, 5 Apr 2017 20:37:13 -0700 (PDT)
Received: from ( [IPv6:2607:f8b0:400e:c05::243]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id A4707124D37 for <>; Wed, 5 Apr 2017 20:37:13 -0700 (PDT)
Received: by with SMTP id 79so5336342pgf.0 for <>; Wed, 05 Apr 2017 20:37:13 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=PYkAHIw/Wq68teAk6SnzCvdsot6C7YvaixxgGkDvYk4=; b=ecqg5MwY2/f7TQ8sHIQxGL//egg73hR68VjgUbnCaDLYjPnUEcIbzd+PDLlPQ9BJLc rbXysTyQLCHRnzq2V+pZ+qrtzAYPj7NGMfi1Le5zcvg7tSlknDIjNJ/871hPMiaL0jvD jhRYNoAu2mTaIsuK4Fwj2D0tqL53zDc2oQFlzxGl83go/884LcAkpb1qTPpz3pPSA6lh YfOf3kjgWFGOPRKJV4hgJTcvYLnHht4H4SNNuNzuS2VgkYTgGnQZh/YtvPD3Fl9OB0tb KXTQYq+wuHIAlL9jPssxRL4zG3mZXIRjBRnAxEP0qnZhQ0bD4MwTqGkCgBT0o07M/rPy I5/w==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=PYkAHIw/Wq68teAk6SnzCvdsot6C7YvaixxgGkDvYk4=; b=emXVlR4feTVquDOIc+f9sRHrocENaJoRR+hVMxKqc61X8tQ8iY5c5/zvffrKYB4/se mOyzlS0ACwxZIn23OUPSnOLk0UMpSBrpjEujVuMyecJJe4jsjN6feADhVIS0qJXc/EtA trVURMM9G9KFmJc8N95l+sDH+Tm6+9ljN4JmRUyP+Y9WyyrMJfjlbkqG3N74c59FMCWK RxlQjH9+S0seyPVKd9dtibuym185OiuftTy3jRVZkMQ5mf3J0ylVKDB9R5v+eO+CQ86l zUtCaW0yxmnBViG1WSfI8cF8DWm9ieU7fI4AWFjVUMaQ2IeECNfuwVlUjLyUsDm62le+ 53bw==
X-Gm-Message-State: AFeK/H0yikJ0pUh3id8Re9jtC3Z7Ozp8/efPT8jUAUUk647lrenqGv5PqDIUEHW9wsdYCw==
X-Received: by with SMTP id c1mr40686600pld.181.1491449833250; Wed, 05 Apr 2017 20:37:13 -0700 (PDT)
Received: from ?IPv6:2601:1c2:4f03:b950:d5dc:97f4:cdf3:d6dc? ([2601:1c2:4f03:b950:d5dc:97f4:cdf3:d6dc]) by with ESMTPSA id a77sm378683pfl.91.2017. (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 05 Apr 2017 20:37:12 -0700 (PDT)
Content-Type: text/plain; charset="us-ascii"
Mime-Version: 1.0 (1.0)
From: "Anna (Amy) Johnston" <>
X-Mailer: iPad Mail (14E277)
In-Reply-To: <>
Date: Wed, 05 Apr 2017 20:37:11 -0700
Cc: Greg Rose <>, "" <>
Content-Transfer-Encoding: quoted-printable
Message-Id: <>
References: <> <> <> <> <>
To: Travis Finkenauer <>
Archived-At: <>
Subject: Re: [Cfrg] Prime 630*(427!+1)+1 for classic DH?
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 06 Apr 2017 03:37:15 -0000

With a prime like this (and with the knowledge that q is prime), a better way (non-probabilistic) is to use Pocklington's theorem.  Two exponentiations with the right base and you've proved primality.  q can also be checked for primality with Pocklington's, but it takes a larger number of much smaller exponentiations.

The SNFS reduces the computation cost of the sieve, but as larger base fields become the norm (at least 2048 bits), the linear algebra, not the sieve will be the problem (see iacr e-print 2017/067, page 8, as well as other discrete logarithm records in the past -- all shift work away from the linear algebra to the sieve).  This means that back doors are not as big a concern.

If sieving attacks are the main concern, then regularly changing  the primes used would be a bigger boost to security.  Fixed primes, uses everywhere, mean that the huge cost of the sieve and solving the system of equations have an even bigger payoff.  Changing primes regularly minimizes an attackers gain from any possible sieve attack -- SNFS, more general, or other index calculus attacks which may be developed. 

Pocklington's theorem is not only an efficient test for this prime, but is a way to efficiently (if q is at least 1/2 the bits, then 2 exponentiations) test primality, but also quickly verify primality AND produces an element of order q (the same two exponentiations).
A. Johnston
Sent from my iPad

> On Apr 5, 2017, at 18:54, Travis Finkenauer <> wrote:
> sympy.ntheory.isprime