Re: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression)

Rene Struik <rstruik.ext@gmail.com> Wed, 12 December 2012 19:23 UTC

Return-Path: <rstruik.ext@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 8D3A221E804E for <cfrg@ietfa.amsl.com>; Wed, 12 Dec 2012 11:23:22 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.599
X-Spam-Level:
X-Spam-Status: No, score=-3.599 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, RCVD_IN_DNSWL_LOW=-1]
Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id PgbmhhRVnIZe for <cfrg@ietfa.amsl.com>; Wed, 12 Dec 2012 11:23:21 -0800 (PST)
Received: from mail-ia0-f182.google.com (mail-ia0-f182.google.com [209.85.210.182]) by ietfa.amsl.com (Postfix) with ESMTP id E9C9621F8754 for <cfrg@irtf.org>; Wed, 12 Dec 2012 11:23:16 -0800 (PST)
Received: by mail-ia0-f182.google.com with SMTP id x2so1272124iad.13 for <cfrg@irtf.org>; Wed, 12 Dec 2012 11:23:07 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:date:from:user-agent:mime-version:to:cc:subject :references:in-reply-to:content-type:content-transfer-encoding; bh=bLF5wp8re59uYAV9+TpJcAsa8fmxN8q1+e2rAMoDcE8=; b=s9jA1GLmGpWEwgCdT3Gn0HnjXlLF5v3jM9wbMGyF2YYTyHrhXIj4+B70oSPyc8AN8g hP+OEJ0mizMoLxeHJR8BMQ/KAFEHItSpjdoWBeLZwDzygNEVmjm3jZD3ncyepJ8+sEOl ElqV6KvywgroNhkyXXYYHrUtHGXh3vl2U255SueG1d/gCqbEdX213bc6kAZNboLbiHnm ePtBc4ziKa9AnG+CvHi2PczZeYK+jtcGiCNiYrY6v7WDrsrT5ZnAUTNU5UpHNftubLY+ C+aHfjAu4sYAw0Y5WPS4+o8iErKayNxt5Poi7614k3ORGuAtgn8I5TTcBzIThwDZKTpB Zx9w==
Received: by 10.43.130.131 with SMTP id hm3mr1728001icc.25.1355340187690; Wed, 12 Dec 2012 11:23:07 -0800 (PST)
Received: from [192.168.1.103] (CPE0013100e2c51-CM001cea35caa6.cpe.net.cable.rogers.com. [99.231.4.27]) by mx.google.com with ESMTPS id gz10sm12808741igc.9.2012.12.12.11.23.06 (version=TLSv1/SSLv3 cipher=OTHER); Wed, 12 Dec 2012 11:23:07 -0800 (PST)
Message-ID: <50C8D991.5080809@gmail.com>
Date: Wed, 12 Dec 2012 14:22:57 -0500
From: Rene Struik <rstruik.ext@gmail.com>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/17.0 Thunderbird/17.0
MIME-Version: 1.0
To: Andrey Jivsov <openpgp@brainhub.org>
References: <E1TiZ2u-0004cU-P0@login01.fos.auckland.ac.nz> <50C7C3AC.7010405@brainhub.org> <50C891E7.4000009@gmail.com> <A113ACFD9DF8B04F96395BDEACB340421E67CA@xmb-rcd-x04.cisco.com> <50C8D4D1.8050805@brainhub.org>
In-Reply-To: <50C8D4D1.8050805@brainhub.org>
Content-Type: text/plain; charset="ISO-8859-1"; format="flowed"
Content-Transfer-Encoding: 7bit
Cc: Peter Gutmann <pgut001@cs.auckland.ac.nz>, "cfrg@irtf.org" <cfrg@irtf.org>, "saag@ietf.org" <saag@ietf.org>, "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
Subject: Re: [Cfrg] [saag] A proposal for compact representation of an elliptic curve point (ECC point compression)
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.12
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: Wed, 12 Dec 2012 19:23:23 -0000

Hi Andrey:

I just wanted to understand the problem one tries to solve. My simple 
suggestion was aimed at realizing the same effect.

[I had a short offline exchange with Scott Fluhrer on this, including on 
the ECDSA verification angle - summarized by the sentence below]

In most common implementations, ECDSA signature verification cost is 
roughly the same, no matter whether one know the y-coordinate of the 
signature verification key or not.

Given this, it seems that for ECDSA signature verification and ECDH the 
argument for yet another construct seems to be somewhat weak: my simple 
suggestion would also work, does not require new formatting, or 
transition periods (and, to my knowledge, does not read on any 
"nontechnical issues").

I hope this helps.

Best regards, Rene


On 12/12/2012 2:02 PM, Andrey Jivsov wrote:
> I have the same comment as Scott, but I am not sure exactly what Rene 
> means.
>
> I will assume that Rene says that because there are two y for each x, 
> one can calculate the corresponding y or p-y and choose one at random.
>
> The format I proposed indeed fits very well with the feature of the 
> ECDH-based  protocol that Scott refers to (which covers ECC encryption 
> and key agreement). As the draft shows, one simply drops the y 
> coordinate to obtain the compact representation, while there are no 
> extra steps for ECDH key generation (because ECDH keys are not 
> sensitive to maintaining the "right" y).
>
> The extra key generation step is only needed for ECDSA keys.
>
> On 12/12/2012 08:52 AM, Scott Fluhrer (sfluhrer) wrote:
>>
>>
>>> -----Original Message-----
>>> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of
>>> Rene Struik
>>> Sent: Wednesday, December 12, 2012 9:17 AM
>>> To: Andrey Jivsov
>>> Cc: cfrg@irtf.org; saag@ietf.org; Peter Gutmann
>>> Subject: Re: [Cfrg] [saag] A proposal for compact representation of an
>>> elliptic curve point (ECC point compression)
>>>
>>> Hi Andrey:
>>>
>>> One can already implement the x-coordinate only representation of an
>>> elliptic curve point simply by converting the affine representation 
>>> into
>>> compressed representation and randomizing the compression "bit". The
>>> reverse operation then yields the point or its inverse (which have 
>>> the same
>>> x-coordinate).
>>>
>>> To my knowledge, this does not require any changes to data 
>>> formatting (nor
>>> additional bytes).
>>
>> That randomization of the y-component works fine for ECDH (at least, 
>> if you use only the x-component of the shared secret); however, it 
>> doesn't work for ECDSA public keys.
>>
>>>
>>> Best regards,
>>>
>>> Rene
>>>
>>> On 12/11/2012 6:37 PM, Andrey Jivsov wrote:
>>>> On 12/11/2012 03:15 PM, Peter Gutmann wrote:
>>>>> Andrey Jivsov <openpgp@brainhub.org> writes:
>>>>>
>>>>>> I thought that it would be useful for the Internet community to have
>>>>>> an IETF document that describes how to encode an ECC point.
>>>>>
>>>>> Maybe I'm missing something here, but wouldn't this just consist of:
>>>>>
>>>>> -- Snip --
>>>>>
>>>>> See [1].
>>>>>
>>>>> [1] X9.62-2005, "Public Key Cryptography for the Financial Services
>>>>> Industry:
>>>>> The Elliptic Curve Digital Signature Standard (ECDSA)", November, 
>>>>> 2005.
>>>>>
>>>>> -- Snip --
>>>>>
>>>>> That's what every existing RFC that uses ECC seems to be using.
>>>>>
>>>>> Peter.
>>>>>
>>>>
>>>> Hello Peter.
>>>>
>>>> "X9.62-2005" in the search engine lends me on a page that asks for
>>>> $100. I think http://www.secg.org/collateral/sec1_final.pdf [SEC1] is
>>>> more popular as a reference (assuming they are identical regarding the
>>>> point compression method).
>>>>
>>>> I claim that what I submitted is better in many respects than SEC1.
>>>>
>>>> Let me expand on one of the benefits not covered in the spec. It's
>>>> very likely that an employee of a commercial company thinking about
>>>> using [SEC1] compression with any ECC method would get an order from
>>>> the legal department to stay away from compression. The fact that
>>>> somebody on the Internet posted something to the contrary has little
>>>> weight for them. My contribution is an attempt towards a compact
>>>> representation that is actually usable in practice. It's the most
>>>> direct extension to the 1985 idea by [Miller] (see my document for
>>>> details).
>>>>
>>>> Thank you.
>>>>
>>>> _______________________________________________
>>>> saag mailing list
>>>> saag@ietf.org
>>>> https://www.ietf.org/mailman/listinfo/saag
>>>
>>>
>>> -- 
>>> email: rstruik.ext@gmail.com | Skype: rstruik
>>> cell: +1 (647) 867-5658 | US: +1 (415) 690-7363
>>>
>>> _______________________________________________
>>> Cfrg mailing list
>>> Cfrg@irtf.org
>>> http://www.irtf.org/mailman/listinfo/cfrg
>


-- 
email: rstruik.ext@gmail.com | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363