Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base

Andrey Jivsov <crypto@brainhub.org> Wed, 21 January 2015 09:04 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 500D11A0AF8 for <cfrg@ietfa.amsl.com>; Wed, 21 Jan 2015 01:04:17 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.501
X-Spam-Level:
X-Spam-Status: No, score=-0.501 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, 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 AHPwxFQ0MxQm for <cfrg@ietfa.amsl.com>; Wed, 21 Jan 2015 01:04:14 -0800 (PST)
Received: from resqmta-po-04v.sys.comcast.net (resqmta-po-04v.sys.comcast.net [IPv6:2001:558:fe16:19:96:114:154:163]) (using TLSv1.2 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id C96491A07BC for <cfrg@irtf.org>; Wed, 21 Jan 2015 01:04:14 -0800 (PST)
Received: from resomta-po-14v.sys.comcast.net ([96.114.154.238]) by resqmta-po-04v.sys.comcast.net with comcast id iZ4E1p00258ss0Y01Z4EQ6; Wed, 21 Jan 2015 09:04:14 +0000
Received: from [192.168.1.2] ([71.202.164.227]) by resomta-po-14v.sys.comcast.net with comcast id iZ4C1p00F4uhcbK01Z4DEo; Wed, 21 Jan 2015 09:04:14 +0000
Message-ID: <54BF6B8C.2020707@brainhub.org>
Date: Wed, 21 Jan 2015 01:04:12 -0800
From: Andrey Jivsov <crypto@brainhub.org>
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.3.0
MIME-Version: 1.0
To: Watson Ladd <watsonbladd@gmail.com>, Andrey Jivsov <crypto@brainhub.org>
References: <54AA4AB9.70505@brainhub.org> <54B315CA.6040900@brainhub.org> <88805D27-3B08-421D-B62A-2FC61AC5851A@shiftleft.org> <CACsn0c=qxBXCkr7hCtzgY9U+5_N8hY=jShU7g=hUbqkrUMYxNw@mail.gmail.com> <3C94ED57-5089-4A6D-9CC6-2DCD452C7BCF@shiftleft.org> <CACsn0ck6q9nxioS7q66MkB6M+YmaGj=Nmqop1LQ-DuG0q78GaQ@mail.gmail.com> <54BCAE24.6020408@brainhub.org> <CACsn0ckb6t_bsAocYnBhiqRkaJ3HExF4QNDf83riQqc=uHdQ0A@mail.gmail.com>
In-Reply-To: <CACsn0ckb6t_bsAocYnBhiqRkaJ3HExF4QNDf83riQqc=uHdQ0A@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=1421831054; bh=R/dR6zOwnVqEEUZtvWUh19PGa72zNIQbeOSX9Zvi9oE=; h=Received:Received:Message-ID:Date:From:MIME-Version:To:Subject: Content-Type; b=vYEeaw8cYeOcCL2b98vWr+oYi3NHKRKvQWg8pB6+hfSxPAzNVfyOzB/JGKNhsaqvA qO7LHbhesAApDGmLasr5lZOQVi/0ONVbovkbG3MAEhMTQLS12E8oKXwQgjMi8to4TQ baEsMlhoh3l9cUXWt1Xtehwrf4ANwqkMDyIQLYcQwGCIz9b5fZ6m1T3Z55lyVcItpG secUzFqBb/qHrP7LMQlj1VZ2ZaJ6+3fTQx+n2QLiZfB54lUvPXujlR76GLu4sPycce P9fIIzydyJBZVhn6Lhl95Cid2dhSfOkTNgPCBfO4QlI/DuOxjrqsJBBaQIAqSEQsIl q0q4roBAIX4ag==
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/2oXKY1V4wVYNbAlRL2_L7pF8RJw>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] On relative performance of Edwards v.s. Montgomery Curve25519, variable base
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: Wed, 21 Jan 2015 09:04:17 -0000

On 01/19/2015 04:20 PM, Watson Ladd wrote:
> And once again, the Montgomery ladder is extremely small in codesize,
> one the field operations are implemented. Or is there some other
> benefit I don't understand you are thinking of?

The benefits of using extended twisted Edwards coordinates would be:

* An order of magnitude faster key generation (this is a part of 
signature generation or ECDH ephemeral key generation)
* Ability to add points (needed for signatures and many other protocols)
* The same code can do what Montgomery ladder does (variable case 
scalarmult) at the same speed.

It plausible that a library that needs more then ECDH variable base 
scalarmult would implement the above operations without the Montgomery 
ladder.

However, if there there is a penalty to recover 'y', that unified 
implementation is less likely to happen.