[Cfrg] Question about primes of special form and the NFS

Watson Ladd <watsonbladd@gmail.com> Sun, 30 March 2014 20:43 UTC

Return-Path: <watsonbladd@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1C38B1A07D7 for <cfrg@ietfa.amsl.com>; Sun, 30 Mar 2014 13:43:06 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2
X-Spam-Level:
X-Spam-Status: No, score=-2 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, SPF_PASS=-0.001] autolearn=ham
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 09FjvVY7Yopt for <cfrg@ietfa.amsl.com>; Sun, 30 Mar 2014 13:43:04 -0700 (PDT)
Received: from mail-yh0-x235.google.com (mail-yh0-x235.google.com [IPv6:2607:f8b0:4002:c01::235]) by ietfa.amsl.com (Postfix) with ESMTP id 4B4EA1A08DA for <cfrg@irtf.org>; Sun, 30 Mar 2014 13:43:04 -0700 (PDT)
Received: by mail-yh0-f53.google.com with SMTP id v1so6800017yhn.26 for <cfrg@irtf.org>; Sun, 30 Mar 2014 13:43:01 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=JwMAl/5EBf4PfiK9uXvvnU+ViYLmEBp01JFVQYyu7tc=; b=VlcZVYrcj6G+V3tesNuDCnbFCurQPgU3afOnUzOxzt36MSmznnFKk7CJ2AZhJ3Yb+W ZKhNsnNpVy5zwnbv1u9dN+j7PrJrpCqLItkG9U77gtaHGr8+R1hZ1y4xCB/FaBg090bb 36Zk4SECCYB3FB8YgVXwa1Guvpv49Ki0AQeCwZI+znMvcr0xjuYJ2UA+fc76d/nRTErW pkK1nuS3e8Cbe6l3HzRgDvltePChhhV9v3RfAGJ7AZPIqk0jHd8b89/eeRKnqdirsmeh t0sZqPH0s9IZnpN/Kl3E6bU6ku4jZcZ6EUf9z44bsRRl/ACvhce1LC+KGEVeUolNEXmN gscw==
MIME-Version: 1.0
X-Received: by 10.236.94.197 with SMTP id n45mr31006437yhf.46.1396212181194; Sun, 30 Mar 2014 13:43:01 -0700 (PDT)
Received: by 10.170.63.197 with HTTP; Sun, 30 Mar 2014 13:43:01 -0700 (PDT)
Date: Sun, 30 Mar 2014 13:43:01 -0700
Message-ID: <CACsn0c=seHgHNSRta5tCfbxUY2y1cqOOEPdfsDY7udi=h9P88w@mail.gmail.com>
From: Watson Ladd <watsonbladd@gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Content-Type: text/plain; charset="UTF-8"
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/bCX_9H6PdzP_TJ-Um9sj0DIrj6Y
Subject: [Cfrg] Question about primes of special form and the NFS
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Sun, 30 Mar 2014 20:43:06 -0000

Dear all,
draft-gillmor-tls-negotiated-dl-dhe-00 contains primes of the form
2^{b}-2^{b-64}+k*2^64-1 for b a multiple of 64 and k small, and
recommends them as DHE groups. This is to close a security hole in TLS
in which no set of DHE parameters exists, and no one realized they
can't be validated.

This is not as bad as primes of the form 2^b-small, for which the SNFS
applies trivially. However, I am worried that some of the speedups
might still happen. It's probably not possible, but I don't know the
state of the art in this area, and would appreciate any references
dealing with extensions of SNFS to numbers that aren't that special.

Sincerely,
Watson Ladd