Re: [Cfrg] 25519 naming

Andrey Jivsov <crypto@brainhub.org> Tue, 02 September 2014 18:05 UTC

Return-Path: <crypto@brainhub.org>
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 754AC1A0537 for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 11:05:48 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Level:
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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 xVUhnJ1NCOY9 for <cfrg@ietfa.amsl.com>; Tue, 2 Sep 2014 11:05:46 -0700 (PDT)
Received: from qmta01.emeryville.ca.mail.comcast.net (qmta01.emeryville.ca.mail.comcast.net [IPv6:2001:558:fe2d:43:76:96:30:16]) by ietfa.amsl.com (Postfix) with ESMTP id 8BD491A0706 for <cfrg@irtf.org>; Tue, 2 Sep 2014 11:05:46 -0700 (PDT)
Received: from omta06.emeryville.ca.mail.comcast.net ([76.96.30.51]) by qmta01.emeryville.ca.mail.comcast.net with comcast id mHgQ1o00816AWCUA1J5mXL; Tue, 02 Sep 2014 18:05:46 +0000
Received: from [IPv6:::1] ([71.202.164.227]) by omta06.emeryville.ca.mail.comcast.net with comcast id mJ5k1o00P4uhcbK8SJ5l8h; Tue, 02 Sep 2014 18:05:45 +0000
Message-ID: <540606F8.9070504@brainhub.org>
Date: Tue, 02 Sep 2014 11:05:44 -0700
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.7.0
MIME-Version: 1.0
To: Robert Ransom <rransom.8774@gmail.com>
References: <20140825234305.7799.qmail@cr.yp.to> <54057D6B.9090405@brainhub.org> <CABqy+sraBmpngJu-qkDE0MbS4j8jhQ_qfTO8kaVCwMjq+-1kZg@mail.gmail.com>
In-Reply-To: <CABqy+sraBmpngJu-qkDE0MbS4j8jhQ_qfTO8kaVCwMjq+-1kZg@mail.gmail.com>
Content-Type: text/plain; charset="UTF-8"; format="flowed"
Content-Transfer-Encoding: 7bit
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=comcast.net; s=q20140121; t=1409681146; bh=QaA/FHoYm7r9sev3NeLxQKOkT0eAlhfEB4n0r6GcJ7I=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=LAm+mz4G32z6pFCBIRVDuua4lXPqosx4A/N2W9lQ3f1iKM4HphD7DdXGatFoZIqeE 7AOdZKd7890MHiM6/GJ6swC8ZThBB0LzCTaKkRkBz85noEwmJEDCmOS4f54R2RhpIW MjfkmaQIZHXJtBN0S82kWtol1F1ENjGrird+2DM6YEnVF36BXt+GEm0AU3DPfFms3V uLehc9iPp3XWuJPu6krqGF+HygUpNFeEsW/5bvO3XbNNrnJ4dO/DDAlATiUtE1EOuF yW3j/15VteWpcoSUxnaAYvzPVtvOvFlYa1Iomc5RYpgfrHNnvN9LtvrfFKIFd+8P1m CoZ/GlX7O14RA==
Archived-At: http://mailarchive.ietf.org/arch/msg/cfrg/vSM78waYxEa7OEr3uVCvu2v6EKY
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] 25519 naming
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: Tue, 02 Sep 2014 18:05:48 -0000

On 09/02/2014 01:28 AM, Robert Ransom wrote:
> On 9/2/14, Andrey Jivsov <crypto@brainhub.org> wrote:
>
>> X25519 performs 9 F(p) multiplications and squares per each bit of a
>> scalar, for the total of 2295 F(p) operations, not counting additions.
>> Plus there are also 265 operation for an inversion.
>>
>> According to the above, conversion from -1-twisted Edwards coordinates to
>> X25519 unfortunately involves a F(p) inversion.
>>
>>      265/2560 ~= 10%
>>
>> The problem with fixing canonical coordinates seems to be the 10% penalty in
>> conversion from Edwards coordinates to Montgomery due to F(p) inversion.  I
>> wonder if it is possible to not perform the inversion by starting with z!=1
>> in the Montgomery formula?
> That would cost an extra 1M per scalar bit.  1I to rescale the input
> point is *always* faster.

Doesn't an inverse require at least 1M (multiply or square) per scalar 
bit as well? Or, are you saying that because more of these Ms in the 
inverse are squares, this provides a small benefit?

>> This would give us fixed-base optimization and dual key use that comes with
>> Edwards formula and the speed of Montgomery for variable-base ECDH.
> A Montgomery-form x coordinate (or its reciprocal) provides that.
> That's why I've been arguing for a point format based on the
> Montgomery-form x coordinate for so long, even though no one seems to
> be listening.

I am interested, especially in a detailed write up.

Without an efficient conversion between coordinates, the point format 
will likely determine the method of the scalar operation.

...