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

From: Andrey Jivsov <[email-masked]>
Date: Mon, 05 Jan 2015 00:26:33 -0800

I timed the EdDSA using the code recommended in 
http://www.ietf.org/mail-archive/web/cfrg/current/msg05034.html

To my surprise the performance of the verification v.s. variable base 
ECDH are about the same on a (non-Haswell) i5-3550 CPU @ 3.30GHz CPU ( 
the same I used before in prior reports).

git clone https://github.com/brainhub/curve25519-donna.git
$ make speed-curve25519-donna-c64 && ./speed-curve25519-donna-c64
71 us, 14063.8 op/s, 234115 cycles/op

git clone https://github.com/floodyberry/ed25519-donna && cd ed25519-donna
$ gcc ed25519.c -m64 -O3 -c  && gcc test.c ed25519.o -l crypto -o _ && ./_
61965 ticks/public key generation
65268 ticks/signature
223425 ticks/signature verification
60219 ticks/curve25519 basepoint scalarmult
failed to generate expected result
want: 
51,e7,68,e0,f7,a1,88,45,de,a1,cb,d9,37,d4,78,53,1b,95,db,be,66,59,29,3b,94,51,2f,bc,0d,66,ba,3f,
got : 
a9,62,ab,6a,f7,93,6c,52,a6,4e,68,34,04,1c,db,6b,47,7d,5e,f8,14,c0,fc,5c,1d,99,98,1b,b5,c5,05,53,
diff: f8,85,c3,8a, 
,32,e4,17,78,ef,a3,ed,33,c8,a3,38,5c,e8,85,46,72,99,d5,67,89,c8,b7,a7,b8,a3,bf,6c,

110063 ticks/verification (batch)

(I commented out exit(1) in test.c due to tests failing and added 
"batch" above).

I then changed the ge25519_double_scalarmult_vartime, which is doing 
"[s1]p1 + [s2]basepoint" to only do [s1]p1, making sure that the piece 
that takes window values from the precomputed static const 
ge25519_double_scalarmult_vartime is disabled.

This resulted in:
...
202080 ticks/signature verification
...

We have ECDH performance: 234115,  a relevant portion of signature 
verification: 202080.

This shows that the performance of Montgomery ladder v.s. Edwards 
variable base scalar multiplication for p ~= 2^256 is about 15% faster. 
The table for the window values is only 40*4*2^3=1280 bytes. This is 
with 64-bit C code in both cases.

I was expecting that a Montgomery ladder will be faster. Which brings 
the question how much faster should we expect Montgomery ladder to be 
for p ~= 2^256 x86 or other architecture? I don't see it on x86 in my 
quick tests.

Also, I saw a remark in 
https://www.ietf.org/mail-archive/web/cfrg/current/msg05712.html "At the 
128-bit security level the ladder can be faster. At the > 200-bit+ 
security levels the ladder is slower."

---

From: Mike Hamburg <[email-masked]>
Date: Mon, 05 Jan 2015 01:35:15 -0800

On 01/05/2015 12:26 AM, Andrey Jivsov wrote:
> https://www.ietf.org/mail-archive/web/cfrg/current/msg05712.html "At 
> the 128-bit security level the ladder can be faster. At the > 200-bit+ 
Hi Andrey,

I don't know about Donna, but I have fairly comprehensive benchmarks on 
a 252-bit curve (Ed252-MontgomeryStation) and the Goldilocks curves.

Ed252 runs a shared secret computation in 133k cycles on my 3.6GHz 
i7-4790 machine (TB off, HT off).  The microbenchmark breaks this down 
as 120k cycles of constant-time Montgomery laddering, about 13k cycles 
compression, and about 1300 cycles unaccounted.

Constant-time windowed Edwards would replace the ladder with 126k 
cycles.  Variable-time wNAF Edwards takes 112k cycles. So variable-time 
Edwards is 7% faster, and constant-time Edwards is 5% slower, than the 
Montgomery ladder, not counting the final compression.  But the 
Montgomery ladder takes compressed points as input.  Decompression takes 
13.4k  cycles to Edwards, or about 11% of the ladder.  So if you're 
operating on compressed points throughout, the Montgomery ladder is 
about 16% faster (and the whole ECDH about 14-15% faster) than 
constant-time Edwards.

For Ed448, it's a little closer.  The Montgomery ladder and compression 
take 529kcy, and the Edwards consttime window and compression (but not 
decompression) take 540kcy.  The compression function itself is about 
48kcy for either, and decompression is 49kcy.  So with no decompression, 
Montgomery is 2% faster, and with decompression it's 11% faster.

However, replace that Edwards with a fixed-window with cache-vulnerable 
indexing, and it goes down to 503kcy.  Replace it with wNAF and it goes 
down to 490kcy.  At that point it's still slower than the Montgomery 
ladder on compressed points, but only by 2%.

This ratio should be affected by the S/M/m ratio of the field 
arithmetic, the speed of constant-time lookup and condswap, and the size 
of the scalars.  Montgomery does more S,m, and Edwards does more M, 
except that the decompression is also S heavy.  As the curve gets 
larger, the windows can get larger which favors Edwards.  But Edwards 
also burns some 7-8% of its time on constant-time lookups on Ed448, and 
that's with AVX2 to speed them up.

Microsoft's benchmarks on Ed-384-mers, and even some of my earlier Ed448 
numbers disagree with the Ed448 data above.  My earlier numbers were 
about 6% less favorable to Montgomery, and Microsoft's numbers were 
about 10-15% less favorable to Montgomery.  I don't know why my latest 
tests are more favorable to Montgomery than my earlier ones; it may be 
machine or compiler-dependent, or it may have been caused by source 
changes since then.  I tried to hash out the discrepancy between my 
numbers and Microsoft's with Patrick Longa Pierola, but that's as close 
as we got.

So, for larger primes, the Montgomery ladder is probably slightly faster 
than Edwards when operating on compressed points, and slower or the same 
otherwise.

Cheers,
-- Mike

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 05 Jan 2015 12:07:24 -0800

Thank you, Mike, this is helpful. This brings a few thoughts, below.

On 01/05/2015 01:35 AM, Mike Hamburg wrote:
> Microsoft's benchmarks on Ed-384-mers, and even some of my earlier 
> Ed448 numbers disagree with the Ed448 data above.  My earlier numbers 
> were about 6% less favorable to Montgomery, and Microsoft's numbers 
> were about 10-15% less favorable to Montgomery.  ...
My tests seem to confirm this that Montgomery is 10-15% less favourable 
as well.

>
> So, for larger primes, the Montgomery ladder is probably slightly 
> faster than Edwards when operating on compressed points, and slower or 
> the same otherwise. 

A common assumption is that we need point compression in ECDH, from 
which it follows that Montgomery representation is a wash for p ~ 2^256.

However, for the sake of technical argument let's leave aside the weight 
assigned to "widespread existing practice" and:
* assume that the curve is specified in Edwards form, e.g. as in 
http://www.ietf.org/id/draft-black-rpgecc-01.txt
* assume that the point is sent uncompressed.

This is fine for authenticated keys, e.g. because these will be 
distributed in X.509 certificates, DNS records, etc. Point validation is 
cheaper than decompression in other cases, and this is is how it's 
presently done on the Internet. Optional point compression is also 
well-understood.

* The fixed-base scalar multiplication is very fast, e.g. 15 times 
faster with 5.24 Mb of pre-computed static tables for the 13 bit window.

This is beneficial for protocols or implementation that cannot reuse an 
ephemeral EC key. E.g. a command-line application launched to encrypt 
data, a browser launched with open tabs, etc.

Given that the calculation of a client ECDH share is so fast relatively 
to an ECDH shared secret point calculation, an implementation may as 
well always calculate it fresh. This reduces complexity and fits many 
APIs. This is because there is no need to to maintain a "state" with 
reused ephemeral share.

* The same F(p) and ECC code can be used for signing and ECDH. Also, a 
small d in the Edwards equation is used.

Down the road, something like EdDSA+ECDH, uncompressed points in Edwards 
form, looks like the fastest alternative. Essentially this enables the 
system design with a single ECC primitive that does x*P for same field 
size, which is very fast when P=G, the base point.

* Traditional ECC assumed that one can add points. This may affect 
adoption of the new curve.

This is the case for NIST P-256. It may be desirable to sign with an 
ECDH key, e.g. for proof of key possession, without a special protocol.

* Curves that allow point addition offer space/speed tradeoff option 
through the window size, and other methods.

Unfortunately, the conversion between representations costs ~10% due to 
F(p) inverse. Decompression costs about the same. We also know that the 
performance difference between Montgomery/Edwards operations is in the 
similar range. Therefore, selection of the format on the wire determines 
the implementation. If we are sending a Montgomery x, we are committing 
to Montgomery ladder implementation. Is this justified?

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 5 Jan 2015 13:45:26 -0800

> On Jan 5, 2015, at 12:07 PM, Andrey Jivsov <[email-masked]> wrote:
> 

You’re welcome.

>> Microsoft's benchmarks on Ed-384-mers, and even some of my earlier Ed448 numbers disagree with the Ed448 data above.  My earlier numbers were about 6% less favorable to Montgomery, and Microsoft's numbers were about 10-15% less favorable to Montgomery.  ...
> My tests seem to confirm this that Montgomery is 10-15% less favourable as well.

But it looks to me like you compared a constant-time Montgomery implementation to a variable-time Edwards one.

>> So, for larger primes, the Montgomery ladder is probably slightly faster than Edwards when operating on compressed points, and slower or the same otherwise. 
> 
> A common assumption is that we need point compression in ECDH, from which it follows that Montgomery representation is a wash for p ~ 2^256.
> 
> However, for the sake of technical argument let's leave aside the weight assigned to "widespread existing practice" and:
> * assume that the curve is specified in Edwards form, e.g. as in http://www.ietf.org/id/draft-black-rpgecc-01.txt
> This is fine for authenticated keys, e.g. because these will be distributed in X.509 certificates, DNS records, etc. Point validation is cheaper than decompression in other cases, and this is is how it's presently done on the Internet. Optional point compression is also well-understood.

Sure, this is an OK option.  I prefer always-compressed for reasons which have come up before, but optional compression is reasonable.

> * The fixed-base scalar multiplication is very fast, e.g. 15 times faster with 5.24 Mb of pre-computed static tables for the 13 bit window.

Most designers don't do this, because it’s vulnerable to timing attacks and can have caching problems (important for anything other than benchmarks).  More common values are somewhere between 3kiB and 20kiB, with constant-time table lookups, yielding about a 3x performance improvement instead of 15x.

> This is beneficial for protocols or implementation that cannot reuse an ephemeral EC key. E.g. a command-line application launched to encrypt data, a browser launched with open tabs, etc.
> 
> Given that the calculation of a client ECDH share is so fast relatively to an ECDH shared secret point calculation, an implementation may as well always calculate it fresh. This reduces complexity and fits many APIs. This is because there is no need to to maintain a "state" with reused ephemeral share.
> 
> * The same F(p) and ECC code can be used for signing and ECDH. Also, a small d in the Edwards equation is used.

Implementations which compress points and/or use the ladder will share F(p) code.  The small d in the Edwards equation can be used in either the isomorphic curve (as Robert Ransom and I found) or the isogenous one (a la Microsoft).  If an implementor wants to use the Edwards code for Montgomery-x ECDH as well, it costs no more than with any other point compression scheme.

> Down the road, something like EdDSA+ECDH, uncompressed points in Edwards form, looks like the fastest alternative. Essentially this enables the system design with a single ECC primitive that does x*P for same field size, which is very fast when P=G, the base point.

Faster than compressed, yes.  Better, though… maybe?  Speaking of faster, most verifies will use double-scalar multiply because it’s faster, and they usually have different code between signing/ECDH and verification for side-channel reasons.

> * Traditional ECC assumed that one can add points. This may affect adoption of the new curve.
> 
> This is the case for NIST P-256. It may be desirable to sign with an ECDH key, e.g. for proof of key possession, without a special protocol.
> 
> * Curves that allow point addition offer space/speed tradeoff option through the window size, and other methods.
> 
> Unfortunately, the conversion between representations costs ~10% due to F(p) inverse. Decompression costs about the same. We also know that the performance difference between Montgomery/Edwards operations is in the similar range. Therefore, selection of the format on the wire determines the implementation. If we are sending a Montgomery x, we are committing to Montgomery ladder implementation. Is this justified?

Exactly what features are possible or desirable in a point encoding — and at what cost in complexity and generality — is an interesting question.

The point format in the experimental Goldilocks software (and in Ed252) allows adding points, because it transmits sign information.  I used the same format is used for laddered ECDH and for signatures.  It is suitable for both the Montgomery ladder and Edwards windowed implementations.  Furthermore, it reduces the curve’s cofactor to 2 (see also my post on reducing the cofactor to 1), and allows the Montgomery ladder to reject twist points.  It costs about the same as an ordinary point compression/decompression system, but it is slightly more complex and not batchable either for compression or decompression.

Others have also advocated a simpler format with similar properties, such as (Montgomery x, low bit of Edwards x).  This doesn’t reduce the cofactor, but it’s easier to describe and it allows compression to be batched.

Cheers,
— Mike

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 05 Jan 2015 15:07:54 -0800

> But it looks to me like you compared a constant-time Montgomery implementation to a variable-time Edwards one.

The method uses window exponentiation-style scalar multiplication with 
doubling for each bit. The data-dependent decisions are done for 
additions, which are additional ~ 50% of these. The fix may lower the 
performance gap, but I think it will be within these 15%.

> Most designers don't do this, because it’s vulnerable to timing attacks and can have caching problems (important for anything other than benchmarks).  More common values are somewhere between 3kiB…
The openssl does this for in ECDSA P-256 code with w=7. My comments are 
regarding the generalization of this code for w=13, which means you are 
doing 20 ECC additions for the entire P-256 fixed-base scalar 
multiplication. At this rate the memory access is what slows you down, 
and things like unneeded inverse in ECDSA v.s. EdDSA.

It may not be necessary to have side-channel protected code that 
generates one-time ECDH pair, otherwise, one can add cache line SC 
protection.

> Implementations which compress points and/or use the ladder will share F(p) code.  The small d in the Edwards equation can be used in either the isomorphic curve (as Robert Ransom and I found) or t…

I put some of this here 
http://www.ietf.org/mail-archive/web/cfrg/current/msg05113.html

However, "free" assumes that you use compression. Removing compression 
gives you 10% performance gain, if you don't need to do conversions to 
isogenous curves.

Is it worth to subject the X.509 cert verifiers to the 10% penalty for 
32 byte saving?

> Faster than compressed, yes.  Better, though… maybe?  Speaking of faster, most verifies will use double-scalar multiply because it’s faster, and they usually have different code between signing/ECD…
"Batching" is a good thing. When x * basepoint is just a few additions, 
the main benefit of doing double scalar multiply is probably due to 
"simultaneous inverse" (single conversion to affine v.s. twice). TLS 1.3 
enables additional "batching" between ECDH and signature. These cases 
can be handled by a single x*P primitive with a n-point export function.

> Others have also advocated a simpler format with similar properties, such as (Montgomery x, low bit of Edwards x).  This doesn’t reduce the cofactor, but it’s easier to describe and it allows compr…

As a side note, I see difficulties in implementing batching in practice. 
I think, realistically, it's an engineering challenge to batch ECC 
operations for parallel TLS streams. A realistic pattern for batching is 
something like double scalar multiplication that are guaranteed to occur 
at the protocol level. Therefore, the 10% hit due to extra inverse is, 
unfortunately, might not be easy to lower to below 5% (and that's when 
you are lucky e.g. when the cert and DH group match)

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 5 Jan 2015 16:04:42 -0800

> On Jan 5, 2015, at 3:07 PM, Andrey Jivsov <[email-masked]> wrote:
> The method uses window exponentiation-style scalar multiplication with doubling for each bit. The data-dependent decisions are done for additions, which are additional ~ 50% of these. The fix may lower the performance gap, but I think it will be within these 15%.

The difference is about 15% in my code.

> The openssl does this for in ECDSA P-256 code with w=7. My comments are regarding the generalization of this code for w=13, which means you are doing 20 ECC additions for the entire P-256 fixed-base scalar multiplication. At this rate the memory access is what slows you down, and things like unneeded inverse in ECDSA v.s. EdDSA.

2^13 >> 2^7.

> It may not be necessary to have side-channel protected code that generates one-time ECDH pair, otherwise, one can add cache line SC protection.

Partial SC protection can be very tricky to analyze.  I don’t know what you mean by “cache line SC protection”.  A cache line may not even hold 2^13 bits.

The same fixed-base code is likely to be used for both ECDH ephemeral keygen, and for signing.  This sort of leak in signing code could be disastrous.

> However, "free" assumes that you use compression. Removing compression gives you 10% performance gain, if you don't need to do conversions to isogenous curves.
> 
> Is it worth to subject the X.509 cert verifiers to the 10% penalty for 32 byte saving?

Maybe.  We’re talking maybe a 50µs difference on a 1GHz Cortex-A9 phone.  While you can send 32 bytes in 50µs over a 5Mbit LTE link, I don’t know which will use more power.  On a laptop, it’s about 5µs (on one core), which equates to a 50Mbit link.  Obviously not all points will be sent over slow links, but the point is that the actual performance penalty is on the same order as the space savings.

Also, converting to an isogenous curve will be done in projective form in practice, so it’s “free”.

> "Batching" is a good thing. When x * basepoint is just a few additions, the main benefit of doing double scalar multiply is probably due to "simultaneous inverse" (single conversion to affine v.s. twice). TLS 1.3 enables additional "batching" between ECDH and signature. These cases can be handled by a single x*P primitive with a n-point export function.

I don’t mean batching, I mean Straus’ algorithm (aka Shamir’s trick) for linear combinations, as used within a single ECDSA verify.

Cheers,
— Mike

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 5 Jan 2015 16:07:42 -0800

> On Jan 5, 2015, at 4:04 PM, Michael Hamburg <[email-masked]> wrote:
> 
> 
>> On Jan 5, 2015, at 3:07 PM, Andrey Jivsov <[email-masked] <mailto:[email-masked]>> wrote:

Sorry, I meant 12%.

— Mike

---

From: Watson Ladd <[email-masked]>
Date: Mon, 5 Jan 2015 23:28:11 -0500

> Thank you, Mike, this is helpful. This brings a few thoughts, below.
<snip>
>
>
> Unfortunately, the conversion between representations costs ~10% due to F(p)
> inverse. Decompression costs about the same. We also know that the
> similar range. Therefore, selection of the format on the wire determines the
> implementation. If we are sending a Montgomery x, we are committing to
> Montgomery ladder implementation. Is this justified?

Yes. Despite claims earlier in your email that certification stops the
problem, invalid point attacks are a real threat. In RFC 4492,
ECDH_ECDSA authentication of servers to clients involves one signed
point and one unsigned point, the unsigned point being sent by the
client.  An attacker can extract the private key relatively quickly
from a vulnerable implementation, which do exist: I've found some, and
I believe Kenny Patterson has a student or two working on finding more
now, as well as attacking other protocols. RFC 6090 doesn't mention
the need for point validation, for instance.

Point compression doesn't solve this issue: there is a presentation by
Adrian Antipa, Dan Brown, Alfred Menezes, Rene Struik, and Scott
Vanstone at PKCS 2003 which demonstrates attacks even when point
compression is mandatory. DJB has also found a patent on point
validation, which may mean we have a problem. (This is why RFC 6090
doesn't mention point validation: the relevant patent is US7215773)

That's why NUMS switched to x-coordinate only Montgomery: the security
issues associated with invalid point attacks go away. The Montgomery
ladder is so simple that adding it to an Edwards form implementation
adds very little complexity. The architectural issues being claimed
are in my view irrelevant: most protocol implementations are able to
integrate RSA and ECC, which are radically different: an x-coordinate
only key exchange isn't much harder to integrate, and if it was,
people wouldn't be doing it.

The consequences of these attacks are losing one's private key, and
telling implementors to check inputs isn't stopping them.

Sincerely,
Watson Ladd

>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 05 Jan 2015 22:03:37 -0800

On 01/05/2015 04:04 PM, Michael Hamburg wrote:
>> The openssl does this for in ECDSA P-256 code with w=7. My comments
>> are regarding the generalization of this code for w=13, which means
>> you are doing 20 ECC additions for the entire P-256 fixed-base scalar

Understood, but diverse implementations would be free to choose any the 
most suitable value of w for the same format on the wire.

Contrast this with Montgomery coordinate on the wire, which can be 
viewed as an implementation with fixed w=1 (but fewer F(p) per w).

> Partial SC protection can be very tricky to analyze.  I don’t know what
> you mean by “cache line SC protection”.  A cache line may not even hold
> 2^13 bits.

As a side note, I think that only 2^w / (256/w) need be protected.  W.g. 
for w=13 there are 20 sub-tables Ti, where Ti is always accesses in step 
i=[0,19]. The access within each Ti may need side channel protection, if 
this fits a threat model. These Tis are public, read-only tables that 
can be shared between processes and can reside in ROM.

>
> The same fixed-base code is likely to be used for both ECDH ephemeral
> keygen, and for signing.  This sort of leak in signing code could be
> disastrous.

Shouldn't it be possible to get a value T[i] from a public table T with 
a private i in a secure fashion?

In the worst case an implementation can use Montgomery ladder internally 
if this is the most suitable option.

> Maybe.  We’re talking maybe a 50µs difference on a 1GHz Cortex-A9 phone.
>   While you can send 32 bytes in 50µs over a 5Mbit LTE link, I don’t
> know which will use more power.  On a laptop, it’s about 5µs (on one
> core), which equates to a 50Mbit link.  Obviously not all points will be
> sent over slow links, but the point is that the actual performance
> penalty is on the same order as the space savings.
>

Thinking more about it, here is an interesting observation (probably 
that's what you meant).

Let's say that the wire coordinates are twisted Edwards (x,y).

The implementation that wants to use the t.Edwards curve will use (x,y) 
directly, validating the point as needed first.

An implementation that wants to use Montgomery ladder will do

   X = -(y+1)
   Z =   y-1

and proceed with the currently written X25519 code, other than it will 
use initial Z=y-1 v.s. Z=1. An interesting fact is that the (x,y) can be 
compressed as (y) and this will work without decompression penalty with 
a Montgomery ladder.

This is significant because doing it as in Adam's draft doesn't seem to 
avoid 10% penalty in some cases, specifically, if an implementation uses 
Edwards formula I think one needs to obtain Y for Montgomery X first, 
which involves a square root. This makes sense because Edwards 
calculation needs both (x,y), while Montgomery formula -- only X (and, 
even better, X happen to depend only on y).

This is largely from 
http://www.ietf.org/mail-archive/web/cfrg/current/msg05113.html, which 
relies on http://eprint.iacr.org/2008/013.pdf .

This means that the format on the wire is

   compressed:   t.Edwards (y)
   uncompressed: t.Edwards (x,y)

and the conversion to Montgomery is indeed free.

...

---

From: Andrey Jivsov <[email-masked]>
Date: Mon, 05 Jan 2015 22:18:06 -0800

On 01/05/2015 08:28 PM, Watson Ladd wrote:
> Despite claims earlier in your email that certification stops the
> problem, invalid point attacks are a real threat.

I didn't mean to say it this way. Implementations have plenty of chances 
to do this wrong. One should not overestimate what this group can do, 
for example, about preventing an application from hardcoding an 
"ephemeral" ECDH key pair into the source code.

The point validation is a part of the group of tests that can be 
legitimately not claimed on the FIPS 140-2 validation. This is in 
ECDSAVS, sec 6.3 
http://csrc.nist.gov/groups/STM/cavp/documents/dss2/ecdsa2vs.pdf

Interesting about validation patents. I try not to read them. Checking 
that (x,y) satisfies some f(x,y)=0 seems to have prior art.

---

From: Mike Hamburg <[email-masked]>
Date: Tue, 06 Jan 2015 00:09:47 -0800

On 1/5/2015 10:03 PM, Andrey Jivsov wrote:
> Understood, but diverse implementations would be free to choose any 
> the most suitable value of w for the same format on the wire.
>
You can use an Edwards fixed-window method to generate ephemerals in 
Montgomery-x wire format.  Ed25519-donna already does this.

> As a side note, I think that only 2^w / (256/w) need be protected. 
> W.g. for w=13 there are 20 sub-tables Ti, where Ti is always accesses 
> in step i=[0,19]. The access within each Ti may need side channel 
> protection, if this fits a threat model. These Tis are public, 
> read-only tables that can be shared between processes and can reside 
> in ROM.
Sure, but protecting 2^13 (or 2^12) points per comb is not going to come 
cheap.  In my measurements the highest speed was about w=5 or 6.

As a side note of my own, all the cool kids are using combs for 
fixed-point scalarmuls these days.  They provide a better tradeoff of 
performance to table size.  The only issue is that one '907 patent, 
which I'm pretty sure doesn't apply to my combs... but MS hasn't gotten 
back to the list on that yet.
> Shouldn't it be possible to get a value T[i] from a public table T 
> with a private i in a secure fashion?
>
> In the worst case an implementation can use Montgomery ladder 
> internally if this is the most suitable option.
Yeah, vs timing attacks you can use vectorized AND/OR/mux/whatever to do 
it.  Vs power attacks you might just have to go back to direct RAM 
access, blind a lot and hope it's enough.

> The implementation that wants to use the t.Edwards curve will use 
> (x,y) directly, validating the point as needed first.
>
> use initial Z=y-1 v.s. Z=1. An interesting fact is that the (x,y) can 
> be compressed as (y) and this will work without decompression penalty 
> with a Montgomery ladder.
It's cheaper to divide by Z up front (+~256S) than to multiply by both Z 
and X at each step (+~256M).  There is also an Edwards curve y-only 
ladder but it's significantly more of a pain than the ladder on 
Montgomery curves.
> This is significant because doing it as in Adam's draft doesn't seem 
> to avoid 10% penalty in some cases, specifically, if an implementation 
> uses Edwards formula I think one needs to obtain Y for Montgomery X 
> first, which involves a square root. This makes sense because Edwards 
I actually meant the opposite.  Sending Montgomery (x,y) or similar is 
easier because the Edwards math won't be hurt as much by a projective 
input point -- it's like 1-2% instead of 10%.  Though that does mean you 
can't encode the identity anymore.

Cheers,
-- Mike

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 11 Jan 2015 16:31:06 -0800

Counting multiplications (M) and squares (S) in F(p), ECC formulas use 
at least 5% more operations v.s. Montgomery.

The lowest non-Montgomery count is reached with twisted Edwards, signed 
window, w=5, which yields 6%/5.5% more M/S.

I pasted my notes below.

It's possible that my initial results in this thread are due to the 
difference in F(p) operations between the two implementations.

See also http://www.ietf.org/mail-archive/web/cfrg/current/msg05857.html

Thanks to Mike and Watson for pointers and comments.

-----------------------------------------------------------------
Montgomery method:
-----------------------------------------------------------------

 From http://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html (8.2M for 
differential addition and doubling) with Z1=1: 5M+4S.

256*(5*M+4*S)=1275*M + 1020*S
Inverse: 11*M + 245*S

(also checked curve25519-donna-c64.c)

Total: 1285*M + 1265*S

-----------------------------------------------------------------
t.Edwards window method:
-----------------------------------------------------------------

Write the windows size as w and n-bit E(F(p)) curve (e.g. n=255). 
2^(w-1) signed elements need to be calculated.

The half of 2^(w-1) is filled with doubles, half with additions

2^(w-2) additions, 2^(w-2) doubles, z!=1

addition: 10M+1S
double: 3M+4S
from http://hyperelliptic.org/EFD/g1p/auto-twisted-projective.html

Window filling:
2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S)

For windowed scalar multiplication there are w(ceil(n/w)-1) doubles and 
ceil(255/w)-1 additions

w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)

The formula is 2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S) + 
w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)

w=3: 1622*M + 1102*S
w=4: 1438*M + 1091*S
w=5: 1354*M + 1090*S
w=6: 1384*M + 1130*S

Inverse: 11*M + 245*S

Total (w=5) with inverse:
1354*M + 1090*S +11*M + 245*S = 1365*M + 1335*S

So we have

Montgomery (M):     1285*M + 1265*S
t.Edwards w=5 (tE): 1365*M + 1335*S
( tE needs 6% more M, 5.5% more S )

Unifying S+M, this is:

for S=M cost:
M: 2550*M
tE: 2700*M

for S=0.625M cost:
M: 2075M
E: 2200M

Watson's estimate is:
Montgomery: 2491M
t.Edwards w=5: 2714M

-----------------------------------------------------------------
"Jacobian coordinates with a4=0 for short Weierstrass curves", window method
-----------------------------------------------------------------
http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-0.html

doubling: 2M+5S
addition:  11M+5S

2^(w-2)*(11*M+5*S) + 2^(w-2)*(2*M+5*S) + 
w*(ceil(n/w)-1)*(2*M+5*S)+(ceil(n/w)-1)*(11*M+5*S) + 11*M + 245*S

w=5: 1165*M + 1825*S

for S=M cost
2990*M

for S=0.625M cost
2305*M

-----------------------------------------------------------------
variable curve size n, window method
-----------------------------------------------------------------

Hand-waive (extrapolate from Curve25519) the inverse as
0.95*n*S+0.05*n*M

Montgomery:
(n+1)*(5*M+4*S)+0.95*n*S+0.05*n*M

t.Edwards:
F=2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S) + 
w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)+ 0.95*n*S+0.05*n*M

n=384:
M: 1944*M + 1904*S
w=5:
tE: 2023*M + 2000*S
w=6:
tE: 1991*M + 2019*S

n=255, w=5  (compare to the actual, above):
M: 1292*M + 1266*S
tE: 1366*M + 1332*S

n=400:
M: 2025*M + 1984*S
w=5:
tE: 2099*M + 2079*S
w=6:
tE: 2076*M + 2110.*S
w=7:
tE: 2203*M + 2193*S

n=512:
M: 2590*M + 2538*S
w=5:
tE: 2679*M + 2668*S
w=6:
tE: 2613*M + 2691*S

-----------------------------------------------------------------
Comb method
-----------------------------------------------------------------
The method is described here: http://eprint.iacr.org/2005/222.pdf, but 
always add O:

precomp: (w-1)*ceil(n/w)(3M+4S) + ((2^w)-w-1)*(10M+1S)
mult: (ceil(n/w)-1)*(3M+4S+10M+1S)
inverse (n=255): 11*M + 245*S

total: (w-1)*ceil(n/w)*(3*M+4*S) + ((2^(w-1))-w-1)*(10*M+S) + 
(ceil(n/w)-1)*(3*M+4*S+10*M+S)+11*M + 245*S

n=255:
w=3:
1653*M + 1349*S
w=4:
1516*M + 1339*S
w=5:
1533*M + 1337*S
w=6:
1772*M + 1372*S

---

From: Michael Hamburg <[email-masked]>
Date: Sun, 11 Jan 2015 18:52:14 -0800

Thanks for your analysis!  However, please note that with lazy extended homogeneous coordinates on a twisted Edwards curve with a=-1, the cost of an Edwards addition to an accumulator is 8M and not 10M+1S, and the cost of a doubling is still 3M+4S, perhaps with an additional 1M to convert from this form to a suitable one for the window table.

Furthermore, the multiplication by a constant in the Montgomery curve is not negligible, but neither is the cost of a constant-time lookup in the Edwards window table.

Cheers,
— Mike

> On Jan 11, 2015, at 4:31 PM, Andrey Jivsov <[email-masked]> wrote:
> 
> Counting multiplications (M) and squares (S) in F(p), ECC formulas use at least 5% more operations v.s. Montgomery.
> 
> The lowest non-Montgomery count is reached with twisted Edwards, signed window, w=5, which yields 6%/5.5% more M/S.
> 
> I pasted my notes below.
> 
> It's possible that my initial results in this thread are due to the difference in F(p) operations between the two implementations.
> 
> From http://hyperelliptic.org/EFD/g1p/auto-montgom-xz.html (8.2M for differential addition and doubling) with Z1=1: 5M+4S.
> 
> Write the windows size as w and n-bit E(F(p)) curve (e.g. n=255). 2^(w-1) signed elements need to be calculated.
> 
> For windowed scalar multiplication there are w(ceil(n/w)-1) doubles and ceil(255/w)-1 additions
> 
> The formula is 2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)
> 
> w=3: 1622*M + 1102*S
> w=4: 1438*M + 1091*S
> w=5: 1354*M + 1090*S
> w=6: 1384*M + 1130*S
> 
> Inverse: 11*M + 245*S
> 
> 2^(w-2)*(11*M+5*S) + 2^(w-2)*(2*M+5*S) + w*(ceil(n/w)-1)*(2*M+5*S)+(ceil(n/w)-1)*(11*M+5*S) + 11*M + 245*S
> 
> w=5: 1165*M + 1825*S
> 
> for S=M cost
> 2990*M
> 
> for S=0.625M cost
> 2305*M
> 
> F=2^(w-2)*(10*M+S) + 2^(w-2)*(3*M+4*S) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S)+ 0.95*n*S+0.05*n*M
> 
> n=384:
> M: 1944*M + 1904*S
> w=5:
> tE: 2023*M + 2000*S
> w=6:
> tE: 1991*M + 2019*S
> 
> The method is described here: http://eprint.iacr.org/2005/222.pdf, but always add O:
> 
> total: (w-1)*ceil(n/w)*(3*M+4*S) + ((2^(w-1))-w-1)*(10*M+S) + (ceil(n/w)-1)*(3*M+4*S+10*M+S)+11*M + 245*S
> 
> n=255:
> w=3:
> 1653*M + 1349*S
> w=4:
> 1516*M + 1339*S
> w=5:
> 1533*M + 1337*S
> w=6:
> 1772*M + 1372*S
>

---

From: Peter Dettman <[email-masked]>
Date: Mon, 12 Jan 2015 12:25:50 +0700

[NOTE: I realise GLV curves are not on the table in the current curve 
selection process; this is just a response to the presented numbers, not 
advocacy]

The state-of-the-art precomputation for Weierstrass window method uses 
co-z arithmetic at a cost of ~(5M+2S)/point as set out in 
https://eprint.iacr.org/2008/051. In that paper it's shown how to 
convert the table to affine with a single inversion and total cost of 
~(9M+2S)/point + 1I, observing that the full Montgomery trick is not 
needed because the Z coordinates form a multiplicative chain already. 
However, based on the same observation, it is straightforward to bring 
all precomputed points to a common Z coordinate, avoid the inversion, 
and proceed to calculate on an isomorphic curve where those points are 
affine (by dropping the Z coordinate and setting a4' = Z^4.a4). A single 
multiplication is needed to bring the result point back to the original 
curve.

For a4=0, the isomorphism doesn't affect the formulae, so in the 
windowing, doubling costs (2M+5S), (mixed) addition costs (7M+4S). Also, 
a4=0 is chosen to allow use of a fast endomorphism, so numbers should 
really reflect its usage. It reduces the doublings by half, and (for 
secp256k1) adds an extra 1M per precomputed point (and doubles storage, 
but not lookup costs). Splitting the scalar costs a few multiplications.

So, slightly more roughly than above:
2^(w-1)*(10M + 2S) + (n/2)*(2M + 5S) + (n/w)*(7M + 4S) + (15M+255S) 
<--[Actual cost of inversion in a secp256k1 implementation]

n=256,w=5: 795*M + 1135*S (S=M: 1930*M, S=0.625M: 1505*M).

Regards,
Pete Dettman

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 11 Jan 2015 22:35:58 -0800

> Thanks for your analysis!  However, please note that with lazy extended homogeneous coordinates on a twisted Edwards curve with a=-1, the cost of an Edwards addition to an accumulator is 8M and not…
You are welcome. I would appreciate a pointer to the method.

> Furthermore, the multiplication by a constant in the Montgomery curve is not negligible, but neither is the cost of a constant-time lookup in the Edwards window table.

Right, I was ignoring additions and multiplication by a constant.

Assuming M/4 for a24 (e.g. 4-limb F(p) operations) and full M for d in 
t.Edwards (corresponding to the 37095705...283555 in 
draft-agl-cfrgcurve-00):

M: n*(5*M+4*S+M/4)+11*M + 245*S=1350*M + 1265*S
tE: 2^(w-2)*(10*M+S+M) + 2^(w-2)*(3*M+4*S) + 
w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S+M)+11*M + 245*S=1423*M + 
1335*S

5.4%, 5.5% (M, S). Montgomery is better.

With small curve constants (A, d), M/4 for the multiplication by these 
constants:
M: currently optimal, same 1350*M + 1265*S
tE: 2^(w-2)*(10*M+S+M/4) + 2^(w-2)*(3*M+4*S) + 
w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S+M/4)+11*M + 245*S=1380*M 
+ 1335*S

2.2%, 5.5%. Montgomery is better.

---

From: Michael Hamburg <[email-masked]>
Date: Sun, 11 Jan 2015 22:52:41 -0800

> On Jan 11, 2015, at 10:35 PM, Andrey Jivsov <[email-masked]> wrote:
> 

For the method with lookahead, Hüseyin Hışıl, thesis, http://eprints.qut.edu.au/33233/1/H%C3%BCseyin_Hi%C5%9Fil_Thesis.pdf

For the method with a 5-element accumulator,
https://eprint.iacr.org/2012/309

This is also used in the Goldilocks code.

> Assuming M/4 for a24 (e.g. 4-limb F(p) operations) and full M for d in t.Edwards (corresponding to the 37095705...283555 in draft-agl-cfrgcurve-00):
> 
> tE: 2^(w-2)*(10*M+S+M) + 2^(w-2)*(3*M+4*S) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S+M)+11*M + 245*S=1423*M + 1335*S

> With small curve constants (A, d), M/4 for the multiplication by these constants:
> tE: 2^(w-2)*(10*M+S+M/4) + 2^(w-2)*(3*M+4*S) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(10*M+S+M/4)+11*M + 245*S=1380*M + 1335*S
> 

If a readd is 8M (or 7M for a mixed add, 1M+1m to convert to readd form) then:

2^(w-2)*((7+1+1/4)*M) + 2^(w-2)*(3*M+4*S + M+M/4) + w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(8*M)+11*M + 245*S = 1261*M + 1277*S

That’s -12%M, -4%S vs Montgomery.  But the constant-time lookups may nullify that gain.

Cheers,
— Mike

---

From: Watson Ladd <[email-masked]>
Date: Mon, 12 Jan 2015 07:28:10 -0800

> Furthermore, the multiplication by a constant in the Montgomery curve is not negligible, but neither is the cost of a constant-time lookup in the Edwards window table.

Yes, this is the fastest coordinate system. Inverted Edwards, which I
used for my calculation (but with a stupidly slow inversion routine)
speeds doubling but not additions significantly, compared to extended
homogeneous coordinates.

The table is filled with a cost of 8M for additions and 4M+4S for
doublings so 2^(w-2)*8M+2^(w-2)*(4M+4S). Then we proceed for
ceil(255/w)-1steps, each step consisting of (w-1) 3M+4S doublings, and
1 4M+4S doubling. Ergo the total cost becomes
2^(w-2)*(12M+4S)+(ceil(255/w)-1)*(w*(3M+4S)+1M).

Evaluating we get w=3 as the best choice, with 864 multiplications and
1016 squarings. Of course, it's possible I made a typo in the above.
Adding in the inversion at the end, gives 875*M+1261*S. The total
savings over Montgomery ladder with M=0.8S are about 20%.

But we're neglecting the square root, which seems to be the point of
contention. A square root is essentially an exponentiation to 2^252-2.
Writing down an obvious addition chain I get 376 squares and 14
multiplications. It's very possible, indeed likely, that this can be
tightened. If not, then the total work for this approach with
Montgomery x only is 889*M+1637*S, which with M=0.8S is 4% less.

Of course, the implementation described above is considerably more
complex than the montgomery ladder, and has to validate its inputs in
ways that are frequently forgotten. The addition formulas used aren't
marked as complete, only strongly unified, which introduces occasional
corner cases. If you actually care about the top performance possible
for variable-base multiplication without sacrificing security, then
try Kummer surfaces.

Sincerely,
Watson Ladd

---

From: Michael Hamburg <[email-masked]>
Date: Mon, 12 Jan 2015 09:59:42 -0800

> On Jan 12, 2015, at 7:28 AM, Watson Ladd <[email-masked]> wrote:

Don’t you need to do some additions at some point as well?  Or do the additions only cost 1M?

— Mike

---

From: Watson Ladd <[email-masked]>
Date: Mon, 12 Jan 2015 11:30:37 -0800

> Don’t you need to do some additions at some point as well?  Or do the

Doing the calculation correctly, it's effectively 9M for an addition
after a 3M+4S doubling. The best window is 5, with 1296*M + 1032*S,
and tossing in the inversion gives 1307*M + 1286*S, vs 1285*M + 1265*S
for Montgomery form. Note that here I'm neglecting the multiplications
by constants, which is why the speeds are coming out slightly
differently.

But the bottom line is that Montgomery ladder is competitive with the
best known alternative methods at 255 bits, in terms of operation
counts, and this difference can be wiped out by the need for side
channel protection: none of the various models are saying anything too
different.

Sincerely,
Watson Ladd

---

From: Kurt Roeckx <[email-masked]>
Date: Mon, 12 Jan 2015 22:46:43 +0100

On Mon, Jan 05, 2015 at 12:07:24PM -0800, Andrey Jivsov wrote:
> 
> A common assumption is that we need point compression in ECDH, from which it
> follows that Montgomery representation is a wash for p ~ 2^256.
[...]
> This is fine for authenticated keys, e.g. because these will be distributed
> in X.509 certificates, DNS records, etc.

It's my understanding that at least for TLS the consensus is to
drop ECDH in favour of ephemeral versions only.  As far as I know
it's also very uncommon to see it in X509 certificates.  Are there
going to be uses of static ECDH?

Kurt

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 18 Jan 2015 23:11:32 -0800

> by constants, which is why the speeds are coming out slightly

For extended twisted Edwards coordinates (thanks, Mike) I get very 
similar result. I agree with your operation count (according to 
http://eprint.iacr.org/2008/522.pdf):

n=255; w=5; 2^(w-2)*(8*M) + 2^(w-2)*(4*M+4*S) + 
w*(ceil(n/w)-1)*(3*M+4*S)+(ceil(n/w)-1)*(9*M)+11*M + 245*S =
1307*M + 1277*S

v.s. Montgomery

n=255; n*(5*M+4*S+M/4)+11*M + 245*S=1350*M + 1265*S =
1350*M + 1265*S

I believe I properly accounted for constants (d in t.Ed is large, would 
costs D=M, a=-1 D=0). The table will include points in extended twisted 
Edwards coordinates. Interestingly, the d is not used in any calculation.

The extended twisted Edwards coordinates, despite having to deal with 
large d, are slightly better (~1.5%) with a simple window exponentiation 
method.

The comb method doesn't seem to be better.

> channel protection: none of the various models are saying anything too

Yes, looks like this, if my calculations are correct. The paper mentions 
additional "caching", though.

One argument remains, though. If you plan to do anything beyond ECDH, 
there is a benefit to have the same code that does ECDH, and, say, signing.

---

From: Watson Ladd <[email-masked]>
Date: Mon, 19 Jan 2015 16:20:59 -0800

<snip>
> For extended twisted Edwards coordinates (thanks, Mike) I get very similar
> result. I agree with your operation count (according to
> The extended twisted Edwards coordinates, despite having to deal with large
> d, are slightly better (~1.5%) with a simple window exponentiation method.
>

Combs are better for fixed base mults, not variable base: it takes too
long to do the precomputation.

> One argument remains, though. If you plan to do anything beyond ECDH, there
> is a benefit to have the same code that does ECDH, and, say, signing.

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?

Sincerely,
Watson Ladd

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 21 Jan 2015 01:04:12 -0800

> 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.

---

From: Watson Ladd <[email-masked]>
Date: Wed, 21 Jan 2015 17:39:20 -0800

On Wed, Jan 21, 2015 at 1:04 AM, Andrey Jivsov <[email-masked]> wrote:
> * An order of magnitude faster key generation (this is a part of signature
> generation or ECDH ephemeral key generation)

And the cost here is what? Note that your first bullet point is false:
the comb method on twisted Edwards can deliver a point on a Montgomery
curve, with minimal change in performance. I agree we would be using
twisted Edwards for signatures and protocols that require addition
(although Mike Hamburg has some ideas on safer point formats, based on
Jacobi quartics). But that doesn't mean we should use the same method
for ECDH: there are security advantages which your proposal doesn't
have.

Once again this got discussed extensively over the summer.

Sincerely,
Watson Ladd

---

From: Andrey Jivsov <[email-masked]>
Date: Sun, 25 Jan 2015 13:35:12 -0800

> Once again this got discussed extensively over the summer.

You are proposing to use a Montgomery ladder for second flight of ECDH 
(variable base). There is a benefit of simplicity of code here and 
protection against timing attacks for free, but not much of performance. 
This makes sense.

The first flight of ECDH (fixed-base) is too slow with same 
implementation used for variable base (or any key generation), and so 
you propose to use a discussed over the summer idea to have another type 
of Montgomery ladder (which I couldn't locate). It won't be as simple as 
the first Montgomery ladder and it will probably be more complex as a 
simple ~20 additions of points from a pre-computed read-only table.

This, however, still doesn't solve the problem of digital signatures and 
SPAKE, which need to add points.

For example, in https://tools.ietf.org/html/draft-ladd-spake2-01 each 
peer does 1 fixed-base, 2 variable-base, 2 addition. I would do this 
with a single implementation of a curve formula (e.g. using extended 
twisted Edward).

IMO a library like OpenSSL that anticipates to implement most of these 
algorithms *may* consider a single implementation that can add points 
with no performance loss.

---

From: Watson Ladd <[email-masked]>
Date: Sun, 25 Jan 2015 20:16:40 -0800

On Sun, Jan 25, 2015 at 1:35 PM, Andrey Jivsov <[email-masked]> wrote:
>>> signature
> The first flight of ECDH (fixed-base) is too slow with same implementation
> used for variable base (or any key generation), and so you propose to use a
> discussed over the summer idea to have another type of Montgomery ladder
> (which I couldn't locate). It won't be as simple as the first Montgomery
> ladder and it will probably be more complex as a simple ~20 additions of
> points from a pre-computed read-only table.

Let's look at actual performance numbers, and consider what the
algorithm actually is.

First performance http://bench.cr.yp.to/results-dh.html The Curve25519
implementation presented there outperforms a rather optimized P256
implementation even if we just use the Montgomery ladder for fixed
based exponentiation.

But we can do better via precomputation: what is the algorithm that
lets us do this? Well, we can compute the multiplication in Edwards
form and evaluate the isomorphism or isogeny to Montgomery form. This
was already spelled out January 6th, in Mike Hamburg's email.

Ah, but what if I need more speed? Well, Edwards form isn't faster for
variable time scalarmult. If you want the absolute fastest speed,
Kummer surfaces of genus 2 or GLV/GLS curves are standing by to take
your call.

> SPAKE, which need to add points.

So we have a different point format for them: again this is what is
being done in SSH right now. Why is this impossible?

>
> For example, in https://tools.ietf.org/html/draft-ladd-spake2-01 each peer
> does 1 fixed-base, 2 variable-base, 2 addition. I would do this with a
> single implementation of a curve formula (e.g. using extended twisted
> Edward).

You seem to be conflating curves, coordinates, and computations, and
then managed to ignore standard speedups Of course, the SPAKE2
protocol needs to preserve the sign of points, and so cannot work with
x-coordinate only Montgomery. But what is the actual cost of SPAKE2?
Firstly, the additions are minimal cost. Secondly, xG+yP is best
computed by an algorithm due to Strauss, and is much closer to 1.5
variable-base multiplications.

When using the comb method, the comb contains affine points, and the
formulas for mixed addition are significantly faster than general
addition. One could of course forgo this increased performance, but
its not clear why one would. Similarly, double-base scalarmult
requires a complete addition law, while for single base one can get by
with an incomplete one that is potentially faster. All these
optimizations are generally implemented and deployed today.

> algorithms *may* consider a single implementation that can add points with
> no performance loss.

But why is that implementation choice so valuable as to justify using
something other than x-coordinate Montgomery? It's not codesize,
except in the most constrained environments.

Sincerely,
Watson Ladd

---

From: Andrey Jivsov <[email-masked]>
Date: Wed, 28 Jan 2015 23:20:47 -0800

> implementation even if we just use the Montgomery ladder for fixed

Yes, but P256 is not a subject this this thread.

( For P256 v.s. Curve25519+Montgomery I timed that in
https://www.ietf.org/mail-archive/web/cfrg/current/msg05211.html and 
http://www.ietf.org/mail-archive/web/cfrg/current/msg05251.html : up to 
65% faster )

> was already spelled out January 6th, in Mike Hamburg's email.

I think this will have a ~10% performance penalty due to y missing.

There was no free way to recover y noted. E.g., if we start with 
Montgomery Z!=1, as Mike Hamburg observed, it is cheaper to perform an 
inverse first than to use ( X, Z!=1 ) in the Montgomery ladder formula 
(because squaring is faster than multiplication), and so on.

> Kummer surfaces of genus 2 or GLV/GLS curves are standing by to take

I wonder if this will be worth the benefit (in a single thread).

> being done in SSH right now. Why is this impossible?

There are benefits to have single implementation (that can add points).

However, regarding the wire format, it may be desirable for an 
encryption key to sign (think OpenPGP top-key only, proof of key 
possession, etc). Ignoring the "existing implementation practice", 
defining the Montgomery (x,y) as the point representation allows to do 
signatures, or encryption, and have single implementation, without 
performance penalty to recover y.

> variable-base multiplications.

Hm, 1.5 variable base multiplication doesn't seem appealing here, 
because xG is a factor of 10 faster than yP (for a reasonable 
precomputed table for ~256 bit F(p)) with EC formula that can add points).

> except in the most constrained environments.

It's system simplicity. One then needs to implement, tune, and debug a 
single implementation.

(Single) Montgomery ladder is an excellent implementation strategy for 
many applications. If these applications' needs are served by the 
Montgomery ladder -- they should use a Montgomery ladder.