Re: [Cfrg] Complexity of the Microsoft curve proposal

Craig Costello <> Tue, 14 October 2014 23:54 UTC

Return-Path: <>
Received: from localhost ( []) by (Postfix) with ESMTP id 0D12A1A005F for <>; Tue, 14 Oct 2014 16:54:38 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.901
X-Spam-Status: No, score=-1.901 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id J-fC7je9fM6l for <>; Tue, 14 Oct 2014 16:54:35 -0700 (PDT)
Received: from ( [IPv6:2a01:111:f400:fc10::1:774]) (using TLSv1 with cipher ECDHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id E02C61A0060 for <>; Tue, 14 Oct 2014 16:54:34 -0700 (PDT)
Received: from ( by ( with Microsoft SMTP Server (TLS) id 15.0.1049.19; Tue, 14 Oct 2014 23:54:11 +0000
Received: from ([]) by ([]) with mapi id 15.00.1049.012; Tue, 14 Oct 2014 23:54:11 +0000
From: Craig Costello <>
To: "" <>
Thread-Topic: Re: [Cfrg] Complexity of the Microsoft curve proposal
Thread-Index: Ac/oCgRJQ9masmK0T320ahMLKTrEgw==
Date: Tue, 14 Oct 2014 23:54:11 +0000
Message-ID: <>
Accept-Language: en-US
Content-Language: en-US
x-ms-exchange-transport-fromentityheader: Hosted
x-originating-ip: [2001:4898:80e0:ee43::2]
x-microsoft-antispam: BCL:0;PCL:0;RULEID:;SRVR:DM2PR03MB495;
x-forefront-prvs: 03648EFF89
x-forefront-antispam-report: SFV:NSPM; SFS:(10019020)(199003)(189002)(243025005)(76482002)(20776003)(92566001)(19580395003)(19300405004)(19625215002)(64706001)(31966008)(33646002)(110136001)(87936001)(15202345003)(101416001)(122556002)(40100003)(74316001)(15975445006)(16236675004)(120916001)(19617315012)(2656002)(85852003)(21056001)(99396003)(1411001)(4396001)(106356001)(107046002)(2351001)(85306004)(2501002)(105586002)(108616004)(54356999)(86362001)(50986999)(97736003)(95666004)(46102003)(80022003)(99286002)(76576001)(24736002)(3826002); DIR:OUT; SFP:1102; SCL:1; SRVR:DM2PR03MB495;; FPR:; MLV:sfv; PTR:InfoNoRecords; A:1; MX:1; LANG:en;
Content-Type: multipart/alternative; boundary="_000_075fdb98d04b42d08e39dbc706cc21faDM2PR03MB495namprd03pro_"
MIME-Version: 1.0
Cc: "" <>
Subject: Re: [Cfrg] Complexity of the Microsoft curve proposal
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: Tue, 14 Oct 2014 23:54:38 -0000

Hi Watson,

To elaborate a little on what Mike said, when p == 3 mod 4, defining searches for twist-secure curves that minimize the absolute value of the Montgomery constant automatically minimize the absolute value of the constant on the isogenous (complete) Edwards curve and the absolute value of the constant on the isogenous twisted Edwards curve. So regardless of whether our curves are implemented using Edwards coordinates, twisted Edwards coordinates, or Montgomery coordinates, the corresponding curve constant will be small (see Section 2 of or Section 3.3 of to see that there is no problem here).

On the other hand, I'm not sure if this happens when p == 1 mod 4: for example, the Edwards version of Curve25519 has a curve constant that's a fraction of small numbers, which the implementation documented in ends up treating as a generic (large) field element.

All other things being equal, I therefore think that switching between coordinates (if desired) slightly favors p == 3 mod 4. Furthermore, in this case, if the curve is defined as an a=1 (complete) Edwards curve, implementers then have the option of staying in Edwards form at the expense of 1 field multiplication per addition operation (like the implementation of Curve41417 in does) or of using Mike's isogeny trick for enhanced performance:

In any case, this is (as you say) about the coordinates, not the curve. However, changing coordinates can change the corresponding curve constant, but when p == 3 mod 4 small constants will remain small irrespective of the coordinate system.