Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves

Andrey Jivsov <> Mon, 21 July 2014 02:32 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 6D9D91B2AC8 for <>; Sun, 20 Jul 2014 19:32:28 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.831
X-Spam-Status: No, score=-1.831 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_SORBS_WEB=0.77, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 4-lk0lyHIXmP for <>; Sun, 20 Jul 2014 19:32:27 -0700 (PDT)
Received: from ( []) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 157141B2ACE for <>; Sun, 20 Jul 2014 19:32:26 -0700 (PDT)
Received: by with SMTP id lx4so6369808iec.31 for <>; Sun, 20 Jul 2014 19:32:26 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20130820; h=x-gm-message-state:sender:message-id:date:from:user-agent :mime-version:to:subject:references:in-reply-to:content-type :content-transfer-encoding; bh=idmLUjBxSlly5khfdSHXE8yp7QvYkkR2Izq3PMAK85c=; b=Uewpy0KJYktdkYB6CEdInfuc6H0OWr/w+t4fxtQQZ/Jc8e98eoNSd3UNCGwVKz/ccm OcjIuWG0JYLdlRjboK9fQ/xLYBc+mHp7Cp1LDYe0zJeoYKbh0w7AHf6ETImdZNj3bN/c T6h+1MM6CJCObAtERezACJBMd4z0Vdxhr4r0+H1gLE4nnTif3lmLinSRAZe8q68Oz3bp uVvTZmCiYMIfw6kXOs/wJjJqwZ8QN7tUUPDTYRm/N4R8jkf91HugZazB+3AbEJ6EZnMd ir+hItpplAukkq0241xOqEhtdsgvkj6ljj3S3EAmg3DINa/fip44HjS6hVKdOXPG2aQP mong==
X-Gm-Message-State: ALoCoQlFs9nGL7YF7TmtWjGE5lqM84Zwxf2OfuadC6p6TTOFmjjC2hxRsbsR8evE6nHZ5OJSWb4I
X-Received: by with SMTP id m8mr4611034igx.39.1405909946343; Sun, 20 Jul 2014 19:32:26 -0700 (PDT)
Received: from [] ([]) by with ESMTPSA id lo3sm34103907igb.22.2014. for <> (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Sun, 20 Jul 2014 19:32:25 -0700 (PDT)
Sender: Andrey <>
Message-ID: <>
Date: Sun, 20 Jul 2014 22:32:24 -0400
From: Andrey Jivsov <>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.6.0
MIME-Version: 1.0
References: <>
In-Reply-To: <>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Subject: Re: [Cfrg] Formal request from TLS WG to CFRG for new elliptic curves
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 21 Jul 2014 02:32:28 -0000

>  s: Denotes the bit length, here s in {256,384,512}.
>  p: Denotes the prime number defining the base field.
>  c: A positive integer used in the representation of the prime
>          p = 2^s - c.

In light of the recent discussion, would an attempt to reach a consensus 
on the value of p first has a higher chance for success at this point?

Assuming we want a new p, some arguments for a fixed F(p) are:

* the specs like Curve25519 are "stacks of layers", which prescribe a 
Curve, co-factor multiplication, F(p) operations, and an integer format 
(fixing p seems as one of the the least controversial tasks among these 
* the performance advantage are mostly attributed to the F(p) operations 
(factor of n improvement in F(p) results in ~ n^2 curve performance)
* F(p) operations are platform-specific  (if there is assembler code 
used in the "stack", it will likely be restricted to the F(p))
* F(p) clarity will let hardware vendors focus on optimizations (and not 
worry about the entire stack)
* same F(p) doesn't prohibit multiple curves over it; ( fixing F(p) 
first and the curve or curves later will allow implementations to 
proceed sooner and enables a compromise )
* fixed F(p) allows greater flexibility to upgrade the curves (future 
curves will likely have hardware support available, sensitive code resused).
* fixed F(p) reduces the code size, increases interoperability 
(currently NUMS and Curve25519 are at odds here)

This narrow focus leads to these questions regarding the F(p):
* is a pseudo-Mersenne p an appropriate p for the new curves (the only 
cons to this so far is that such a p fixes the Curve's order to be close 
to 2^s; besides the trivial one that this makes the Pollard-rho faster)
* Curve25519 uses 255 instead of 256; however, CFRG can choose s=255 for 
128 bit security as well (citing "historic" reasons).

Should CFRG seek consensus on the above two questions first?