Re: [Cfrg] Curve selection revisited

[Andrey Jivsov <[e-mail]>]

On 07/25/2014 07:25 PM, Robert Ransom wrote:
> The exact value of c determines whether a portable or vectorized
> implementation can delay carries until after reduction.  For example,
> after curve25519-donna performs a multiply or squaring, each of 19
> 64-bit limbs has absolute value less than 14*2^54.  When
> freduce_degree reduces a field element to 10 limbs without carrying,
> the result has absolute value less than (c+1)*14*2^54  = 280*2^54, or a
> bit more than 2^62.  In the Microsoft field 2^255  - 765, or even 2^256
> - 189, this would not be possible.
>
> Carries between limbs can be performed more efficiently than in
> curve25519-donna -- curve25519-donna goes to extra effort to keep
> limbs signed.  In the Montgomery ladder, this optimization does not
> add any extra carry steps, because the Montgomery-ladder formulas
> never perform more than two add/subtract operations between a
> multiply/square operation.  With Edwards-curve operations, this
> optimization may require an additional carry step in the doubling
> formula.
>
> The exact value of s determines whether carries can be vectorized
> within a coordinate-field element.  For example, 2^251  - 9 can be
> represented using one 26-bit limb (in the least significant position)
> and 9 25-bit limbs, but this interferes with the vectorization
> strategy described in the neoncrypto paper (by Dr. Bernstein et al.).
> Since c=9 is so small, this can be worked around by representing
> coordinates modulo 2^252  - 18 instead, but this trick is rarely
> possible without running into the bound on c.

On 07/25/2014 07:25 PM, Robert Ransom wrote:
 > The exact value of c determines whether a portable or vectorized
 > implementation can delay carries until after reduction.  For example,
 > after curve25519-donna performs a multiply or squaring, each of 19
 > 64-bit limbs has absolute value less than 14*2^54.  When
 > freduce_degree reduces a field element to 10 limbs without carrying,
 > the result has absolute value less than (c+1)*14*2^54  = 280*2^54, or a
 > bit more than 2^62.  In the Microsoft field 2^255  - 765, or even 2^256
 > - 189, this would not be possible.
 >
 > Carries between limbs can be performed more efficiently than in
 > curve25519-donna -- curve25519-donna goes to extra effort to keep
 > limbs signed.  In the Montgomery ladder, this optimization does not
 > add any extra carry steps, because the Montgomery-ladder formulas
 > never perform more than two add/subtract operations between a
 > multiply/square operation.  With Edwards-curve operations, this
 > optimization may require an additional carry step in the doubling
 > formula.
 >
 > The exact value of s determines whether carries can be vectorized
 > within a coordinate-field element.  For example, 2^251  - 9 can be
 > represented using one 26-bit limb (in the least significant position)
 > and 9 25-bit limbs, but this interferes with the vectorization
 > strategy described in the neoncrypto paper (by Dr. Bernstein et al.).
 > Since c=9 is so small, this can be worked around by representing
 > coordinates modulo 2^252  - 18 instead, but this trick is rarely
 > possible without running into the bound on c.

The main argument for p = 2^255-19 v.s. p = 1^256-189 is that the C=19 
is smaller than C=189 and this helps to "manage" the carries.

Let's assume that an F(p) integer is represented as n limbs (words).

256 bit Montgomery curve will have on the order of (5 mul + 4 squares) 
and about the same number F(p) additions per one scalar bit.

Therefore, we can talk about one unreduced F(p) multiplication + F(p) 
reduction (where C plays its role) + F(p) addition. With this in mind 
the contribution of C can be estimated within this group.

F(p) multiplications (counting squares here as well) dominate the 
performance of EC operations:
* the result of the multiplication is 2*n limbs and the complexity of 
this operation is n^2 limb multiplications and O(n^2) additions.
* the 2*n limbs must be reduced (mod p) to n limbs immediately after 
multiplication
* there is on average ~1 addition/subtraction of n limbs per each 
multiplication due to EC formula

Each multiplication needs degree reduction and settling of accumulated 
carries before the next multiplication. One can only postpone settling 
of carries while he does additions (prior to the next multiplciation).

We have about n^2 limb additions, plus n limb additions due to EC 
formular, plus we must perform n additions of the form <some_limb>*C 
(for modp reduction).

Assuming n=10 limbs, the entire contribution of n <some_limb>*C is bound 
by ~10% of all the additions.

We are not talking about C=0, however, but rather about |C|=4 bits v.s. 
|C| = 8 bits difference.

A rough estimate here is 5% penalty.

One reason why I think this is a good estimate is that there may be a 
benefit of more fine-tuned control of carries. The highest accumulation 
of the carries happens in the inner limbs of the 2*n integer (imagine 
paper-and-pencil multiplication of two n-limb numbers: the stack is the 
highest in the middle). Therefore, if we have the need to control 
overflow within, say, multiplication, perhaps it's possible to 
accomplish this within a subset of n limbs.


( BTW, I don't see a clear argument why can't any F(p) be vectorized 
(some more efficiently than others). The vectorization using x86 SSE2 is 
known to speeds up RSA operations for generic F(p)s. )