Re: [Cfrg] A big, big Elliptic Curve

Tanja Lange <> Mon, 11 April 2016 03:21 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id DBB1512DB2D for <>; Sun, 10 Apr 2016 20:21:59 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -4.2
X-Spam-Status: No, score=-4.2 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id l4ews4ZaOjUg for <>; Sun, 10 Apr 2016 20:21:58 -0700 (PDT)
Received: from ( []) by (Postfix) with SMTP id 918FB12DFF9 for <>; Sun, 10 Apr 2016 20:21:57 -0700 (PDT)
Received: (qmail 22928 invoked from network); 11 Apr 2016 03:22:20 -0000
Received: from (HELO ( by with SMTP; 11 Apr 2016 03:22:20 -0000
Received: (qmail 11524 invoked by uid 1004); 11 Apr 2016 03:22:20 -0000
Date: Mon, 11 Apr 2016 05:22:20 +0200
From: Tanja Lange <>
To: Phillip Hallam-Baker <>
Message-ID: <>
References: <>
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <>
User-Agent: Mutt/1.5.21 (2010-09-15)
Archived-At: <>
Cc: "" <>
Subject: Re: [Cfrg] A big, big Elliptic Curve
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 11 Apr 2016 03:22:00 -0000

> As mentioned in the meeting, QC attacks don't use the same algorithms
> as conventional attacks and so the difficulty of breaking Curve 25519
> is considerably less than breaking RSA2048.

Could you point me to sources for this? There is an old paper by
Proos and Zalka which has claims like this, but more recent work
by Roetteler and Steinwandt properly considers reversibility and 
ends up taking longer (time & qubits) for a 160 bit curve than 
1024 bit RSA. They did detailed work for binary curves and last
I talked to them were looking into odd characteristic. The jury
is still out for larger curves and larger RSA but between a
256-bit curve DLP and a 2048 RSA; I'd be surprised if RSA was 

> Interpreting the NSA advice is error prone. But the straight reading
> would be 'we think it more likely that a quantum computer will be
> built that can break current ECC schemes before someone works out how
> to break RSA 3096.
If I take them at face value they basically say: Don't complain 
if we ask you to upgrade to new crypto soon; here, as a concession 
you may continue using the old stuff as long as it is not super 

I'd rather not speculate about their intention and whether those 
are in our interest or not.