Re: [Cfrg] Hardware requirements for elliptic curves

Torsten Schuetze <> Thu, 11 September 2014 18:13 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 4F0ED1A00E7 for <>; Thu, 11 Sep 2014 11:13:15 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -3.552
X-Spam-Status: No, score=-3.552 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-1.652, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id uhWj13rceNBk for <>; Thu, 11 Sep 2014 11:13:13 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher DHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id A09231A9106 for <>; Thu, 11 Sep 2014 11:06:36 -0700 (PDT)
Received: from [] ([]) by (mrgmx103) with ESMTPSA (Nemesis) id 0MSuYT-1XtG1P1kmL-00RncV; Thu, 11 Sep 2014 20:06:34 +0200
Message-ID: <>
Date: Thu, 11 Sep 2014 20:06:51 +0200
From: Torsten Schuetze <>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:31.0) Gecko/20100101 Thunderbird/31.1.1
MIME-Version: 1.0
To:, Mike Hamburg <>
In-Reply-To: <>
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: 8bit
X-Provags-ID: V03:K0:PjB9JPTsS/y02iAzbnw2yOTpn2gudO+fXCvj34ucCJY0d/XgY15 tVwlSgjLZ6m8BC6Vso9aUPdokoRi6ldhHTJ6uhxvB1SESfeymAk7Tyzm8z7GNptZiP7fO2T rVVQmpwBE8wuZoWDjEl+tHesz8GaFt+QtPCwn9aWSo97YsdJApfZ9imhChsD5Kemw2yVY9S fB0QnVUp/kQXpl39X8OMg==
X-UI-Out-Filterresults: notjunk:1;
Subject: Re: [Cfrg] Hardware requirements for 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: Thu, 11 Sep 2014 18:13:15 -0000

On Sep 11, 2014 09:22:53 -0700 Mike Hamburg <mike at>

>> On Sep 11, 2014, at 7:58, Andy Lutomirski <luto at> wrote:
>> Can anyone explain why "random" primes are better for blinding?
>> --Andy
> With an unstructured prime, adding a small random multiple of p or
> the group order q will change every bit of the addend.  With a
> sparse prime, it will not.  This makes blinding a less effective
> countermeasure when p is sparse.

Mike, thanks for explaining.

> Torsten, thanks for the description of smart card hardware and
> concerns. It was very educational. I expected something looking
> more like a specialized CPU, where a sparse prime reduction unit
> could be bolted on easily.

The only thing I know in this direction are FPGA proposals like
Güneysu:Paar:2008 CHES 2008 'Ultra High Performance ECC over NIST
Primes on Commercial FPGAs' and even Sasdrich:Güneysu:2014 ARC 2014
'Efficient ECC using Curve25519' which both use the specific DSPs on
the FPGAs.

These are both great papers with very good performance results. But
they show what I mean with flexibility: it is not easily possible to
use 'random' or unstructured primes or even use the original primes
with enough blinding (because the blinding disturbs the structure).

Some years ago, I was looking for a general GF(p) crypto coprocessor
on a FPGA (Car2X standardization, like IEEE 1609.2, but without NIST
primes). The only thing I came up with was Nele Mentens Phd, 2007
(Montgomery multiplication, coarsely integrated operand scanning) and
the CHES 2010 paper by N. Guillermin (RNS). Unfortunately, I could not
find direct comparisons of, say, Brainpool and NIST curves on these

> You should keep in mind, though, that the curves being proposed are
> designed for security against local side channels as well as global
> ones. The submitted implementations are designed not to leak against
> an adversary who can see all memory addresses accessed and
> instructions executed, even without blinding.

It all depends on the adversarial model.

> That's a lot easier than power and fault defense, but we're not
> slacking on the software side either.

But you surely know from your company background Cryptography
Research that electromagnetic attacks in a template like fashion are
currently the most advanced attacks. And I don't see that one can
solve this issue without heavy blinding.