Subject: Re: [Cfrg] Progress on curve recommendations for TLS WG

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 8 Aug 2014 17:15:06 +0300

On Sun, Jul 27, 2014 at 08:04:45PM +0000, Paterson, Kenny wrote:

> - Do the current proposals (Curve25519 and friends, and the NUMS curves)
> provide an adequate degree of rigidity that is likely to satisfy the
> widest set of commentators? Or should we be thinking about generating
> fresh curves using a public process having verifiably random inputs? What
> would the likely impact be on performance?

I split the question to two parts: Prime and parameters

a) Prime

Picking prime randomly has _devastating_ impact on performance. Nobody will
seriously use the curve. This is THE reason why Brainpool is not used much
in the wild.

If one picks prime for performance (the prime is the dominant factor in
performance), there are very few primes that perform well[1].

This would force high degree of rigridity if performance is a major goal.

b) Parameters

While bad parameters aren't devastating for performance, badly picked ones
are still significantly slower (e.g. loses that ~0.75M advantage from small
parameter on addition or Montgomery step).

With parameters, random choice is not wise, given that there are very few
(I think 4 or 2 depending on bitlength[2][3]) rational choices for
deterministic curve per prime. It would be very hard to reach similar
rigidity via random process.

[1] The "contestants" all seem to be (pseudo) Mersennes with small c and
Solinas trinomials. I think some have tried to develop metrics to measure
the effectiveness of various primes.

[2] Complete Edwards (minimal |d|) vs. Complete Montgomery (minimal |a24|),
q < 2^n vs. q > 2^n.

[3] I think that shrinks to 2 on higher bitlengths, since using windowing
on Edwards curve becomes faster than using Montgomery ladder on Montgomery
curve.

-Ilari

---

From: Robert Ransom <[email-masked]>
Date: Fri, 8 Aug 2014 07:40:17 -0700

> [2] Complete Edwards (minimal |d|) vs. Complete Montgomery (minimal |a24|),

There is no trade-off between efficiency in Edwards form and
efficiency in Montgomery form -- a curve with small-integer Edwards d
has its Montgomery (A+2)/4 as the reciprocal of a small integer, which
is as efficient as having (A+2)/4 be a small integer itself.  *ALL*
new curves should be specified with small-integer Edwards d.  (I've
repeated this already recently, and included a link to formulas in
that message.)

The remaining less-than-perfectly rigid aspects that I know of in
selecting a deterministic curve parameter, given the coordinate-field
order p, are:

* cofactors (For p = 3 mod 4, do you settle for curve and twist having
cofactor 8 (as Curve3617 does), or insist on the minimal cofactor 4
(as Microsoft does; note that E-521 also has cofactor 4)?  For p = 5
mod 8, where either the curve or twist must have cofactor 8, do you
operate on the one with cofactor 8 (as Curve25519 does) or the one
with cofactor 4?)

* group size (For p = 3 mod 4, do you operate on the group with
smaller order (as Curve3617 and E-521 do, perhaps by accident, and as
the MSR curves do), or operate on the group with larger order (I don't
think anyone does this)?  For p = 5 mod 8, do you insist that both
groups have order greater than the power of 2 closest to p/8 (as
Curve25519 does, in order to make key generation hard to screw up)?)

* multiplicative embedding degree (Exactly how large, or how close to
maximal, do you insist that the curve's embedding degree be?)

There may be a few others.

Robert Ransom

---

From: Johannes Merkle <[email-masked]>
Date: Fri, 15 Aug 2014 13:26:31 +0200

Ilari Liusvaara wrote on 08.08.2014 16:15:
> Picking prime randomly has _devastating_ impact on performance. 

I do not mean to doubt that statement, I'm just looking for hard numbers: Do you have any reference for a proper
analysis supporting that? I mean something beyond "oh, that's common sense".
-- 
Johannes

---

From: Mike Hamburg <[email-masked]>
Date: Fri, 15 Aug 2014 14:28:46 -0700

> analysis supporting that? I mean something beyond "oh, that's common sense".
So, I don't have a proper reference, but in my experience the performance ratio is slightly more than 2, and probably creeps towards 2.5 or 3 as the number of bits increases towards 512.

An n-digit multiply with no reduction algorithm costs n^2 muls, schoolbook.  A Montgomery reduction costs n^2+n additional multiplies, for a total of 2n^2 + n.  There may also be a conditional subtract, depending on the modulus.  A special prime still requires some reduction, and Montgomery ends up being slightly less than twice as expensive as schoolbook.

Supporting numbers: a few years ago I implemented 252-bit special-Montgomery primes on Sandy Bridge (mod the special prime, reduction isn't free but costs n=4 mulaccs), and a multiply took about 55 cycles, vs about 100 cycles for a 252-bit general prime.  The algorithms were the same, and both implementations were written in assembly.  This is what you'd have predicted from the above guesses, since (n^2 + n) / (2n^2 + n) = 20 / 36 = 55.555...%.

Squaring costed about 10 cycles less in either case, for a flat ratio of 90:45 = 2:1.  This is because Montgomery reduction does not go any faster when you square, which takes n(n+1)/2 multiplies schoolbook style, but 3x that with a Montgomery reduction.  These asymptotics are not even close to true with n=4, though.

As p increases, the ratio will get worse.  The reduction mod the special prime is a smaller fraction of the total work, and squaring gets closer to asymptotic.  Montgomery reduction does not improve as much with Karatsuba multiplication.  Karatsuba may cut the cost of the multiplication by 25% or more at 384 or 512 bits, but it’s rather tricky to combine with a general Montgomery reduction efficiently.  Furthermore, if you try to do this, the state will be larger and may spill out of the register file.  For example, my 448-bit NEON code exactly uses the entire register file with no spilling; anything extra would add significant cost.

Exactly 64n-bit aligned primes will be slightly worse when randomized, because numbers need to be reduced more often.

Finally, powering ladders like inverse or square root are denser and therefore slower with a random prime  A powering ladder for a special prime usually has a multiply density of around 5%, but for a random prime it is likely to be 20%.  Inversion is about 10% of a variable-base and 25% of a fixed-base scalarmul, so this effect is unlikely to exceed 5% of the total time.

In combination, these will push the ratio to ~2x at 256 bits, and higher for longer numbers, but probably not so high as 3x even at 500 bits (but maybe at 512 or 521 bits).  Not having implemented both a large random and a large special prime together on the same platform, I’m not sure exactly what the ratio will be.

Cheers,
-- Mike

---

From: Andrey Jivsov <[email-masked]>
Date: Fri, 15 Aug 2014 15:52:53 -0700

Here is a simple sketch how the prime affects the mop operations.

Comparing multiplication of 2 n-limb numbers with the reduction mod 
n-limb number p:

* in case of a random prime, we have n^2 multiplies. This gives 2n 
number, n higher limbs of which will need to be reduced. To accomplish 
this we multiply p by each of n high limbs, for the total n^2. We have 
2n^2 multiplies

* in case of p=2^k-C, we have the same n^2 multiplies, but the reduction 
results in only n multiplies of high limbs by C. We have n^2 + n

So this is (n^2 + n) / 2n^2 ~= 1/2 (pseudo-Mersenne primes have ~50% 
fewer limb multiplies for multiply+reduce)

This estimate underestimates  the reduction that takes place for the 
general p. One needs an additional n divisions (of a limp by the highest 
limb of p) in denominator, which gives the Mike Hamburg's quantity 
exactly (which uses the Montgomery reduction method). I didn't count 
additions/subtractions.

On 08/15/2014 02:28 PM, Mike Hamburg wrote:
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: Michael Hamburg <[email-masked]>
Date: Fri, 15 Aug 2014 17:55:27 -0700

I have some more data.  Summary: “devastating” is probably between 1.8 and 3.1.

Mod 2^521-1, you can do a multiply in 167 Haswell cycles using a variant of 3-way Chung-Hasan which is specific to that prime.  (Ordinary Karatsuba is no good because the prime has 9 limbs.)  Schoolbook takes 222 cycles with only minor benefits from the prime’s shape.  Maybe a better implementor can get better numbers than mine; this is a rough try in C++ with asm intrinsics for widening multiply.

I don’t have an implementation on hand of a random prime at that level.  Suppose that for a random prime that size you can do an almost-as-good version of Chung-Hasan in 180 cycles, but then you need to fall back to a digit-serial Montgomery reduction which approximates the schoolbook method.  This includes some of the inter-digit reduction twice, so maybe 222 is 10% too high.  Then the ratio is (180 + 222 * 90%) / 167 ~ 2.3.  A random 512-bit prime also requires this amount of time if you use 9 limbs; with 8 limbs it’s again about the same or maybe slightly worse (see below).

For comparison, based on the Microsoft data, their prime 2^512 - 569 takes about 255 Sandy Bridge cycles per mul.  This is written in assembly language using the schoolbook method.  This corresponds to about 212 Haswell cycles, since the going rate is about 20%.  So it’s 5% faster than my P-521 schoolbook, but in assembly vs C++/intrinsics.  The ratio with my above estimate for a random prime (using a completely different implementation) is 1.8.  Schoolbook Montgomery for a random prime using Microsoft’s implementation techniques should have a ratio of about (2n^2 + n) / (n^2 + n) ~ 1.9 with n=8 limbs.

This assumes a random prime vs special one at the “>= 256-bit WF” level, but if tweaking the levels is allowed, the ratio is even more.  A 480-bit special prime, Ridinghood, takes 122 Haswell cycles for a multiply (same as 448-bit Goldilocks).  That’s a ratio of 3.1 vs the above estimate for a 512-bit random prime.  If you scale the numbers to take the shorter length (480 vs 512) into account, the “efficiency ratio” is about 2.8.

The Ridinghood numbers reflect better tuning than the 521-bit tests, but probably not as much tuning as the Microsoft implementation.  My tests are in C with asm intrinsics.  The difference is maybe 10% vs the C++ above, so figure that a ratio of 2.8 (efficiency ratio 2.5) is probably more fair.

This doesn’t take into account the ratio of multiplication, squaring, and addition / subtraction.

> On Aug 15, 2014, at 3:52 PM, Andrey Jivsov <[email-masked]> wrote:
> 
> Comparing multiplication of 2 n-limb numbers with the reduction mod n-limb number p:
> 
> * in case of a random prime, we have n^2 multiplies. This gives 2n number, n higher limbs of which will need to be reduced. To accomplish this we multiply p by each of n high limbs, for the total n^2. We have 2n^2 multiplies
> 
> * in case of p=2^k-C, we have the same n^2 multiplies, but the reduction results in only n multiplies of high limbs by C. We have n^2 + n
> 
> So this is (n^2 + n) / 2n^2 ~= 1/2 (pseudo-Mersenne primes have ~50% fewer limb multiplies for multiply+reduce)
> 
> 
> This estimate underestimates  the reduction that takes place for the general p. One needs an additional n divisions (of a limp by the highest limb of p) in denominator, which gives the Mike Hamburg's quantity exactly (which uses the Montgomery reduction method). I didn't count additions/subtractions.

These divisions are actually multiplies, because you use either Montgomery or Barrett reduction.  So it’s (n^2 + n) / (2n^2 + n).

Cheers,
— Mike

---

From: Andrey Jivsov <[email-masked]>
Date: Sat, 16 Aug 2014 23:56:07 -0700

I looked at my implementation of modp reduction I did a few years ago 
for a fixed p. I used Barrett reduction.

At closer look I don't see why multiply+reduction mod p, for a random 
but fixed p, is 2n^2 + n. I got a corrected value for Barrett reduction 
below.

>> * in case of a random prime, we have n^2 multiplies. This gives 2n number, n higher limbs of which will need to be reduced. To accomplish this we multiply p by each of n high limbs, for the total…
Ignoring the fact that some operations in Barrett reduction involve +1, 
-1 of border limbs, Barrett has two multiplies with the following 
complexity:

* n^2 of n higher limbs (of the 2n-limb number we are reducing) by the 
n-limb precomputed quantity (b^2n)/p, where b is max limb value+1, e.g. 
b=2^64.
* it computes another quantity t*p mod b^(n+1), which is roughly n^2/2 
(while you estimate it as n).

The total then is ~ 2.5n^2 v.s. n^2+n for pseudo-Mersenne.

>> So this is (n^2 + n) / 2n^2 ~= 1/2 (pseudo-Mersenne primes have ~50% fewer limb multiplies for multiply+reduce)

(n^2+n)/2.5n^2 ~= 2/5,

pseudo-Mersenne primes use ~40% multiplies.

For 256-bit primes n is likely too low to observe this. n=4, n^2/2 = 8 and I ignored extra limbs.

---

From: Michael Hamburg <[email-masked]>
Date: Sun, 17 Aug 2014 01:20:14 -0700

> On Aug 16, 2014, at 11:56 PM, Andrey Jivsov <[email-masked]> wrote:
> 
> I looked at my implementation of modp reduction I did a few years ago for a fixed p. I used Barrett reduction.
> 
> At closer look I don't see why multiply+reduction mod p, for a random but fixed p, is 2n^2 + n. I got a corrected value for Barrett reduction below.

You can reduce one digit at a time.  Eg just cancel the top digit at a cost of one multiply to find the approximate factor plus n to multiply by p, then repeat.  It’s a little easier with Montgomery than with Barrett, since Montgomery always cancels the low digit out exactly.

This is why it’s a pain to reduce with Karatsuba, though.  I don’t know an easy way around it: you either reduce by several digits at a time and pay an extra cost like in your calculations, or you do one at a time but can’t use Karatsuba.

— Mike