Re: Pentanomial better than trinomial


"Sebastian Gottschalk" <seppi@xxxxxxxxx> wrote in message news:56qk52F2aacvuU1@xxxxxxxxxxxxxxxx
Michael Scott wrote:

For example consider GF(2^233). For elliptic curves over this popular field
(two of the NIST standard elliptic curves use this field), the standards
recommend the trinomial

x^233+x^74+1

From "Guide to Elliptic Curve Cryptography", by Hankerson, Menezes and
Vanstone, Algorithm 2.42, the main loop of the optimal reduction algorithm
looks like this on a 32-bit computer

1. for i from 15 downto 8 do
1.1 T=C[i]
1.2 C[i-8]^=(T<<23);
1.3 C[i-7]^=(T>>9);
1.4 C[i-5]^=(T<<1);
1.5 C[i-4]^=(T>>31);
<rest omitted>

However using the pentanomial

x^233+x^201+x^105+x^9+1

The algorithm becomes

1. for i from 15 downto 8 do
1.1 T=C[i]
1.2 C[i-8]^=(T<<23);
1.3 C[i-7]^=(T>>9)^T;
1.4 C[i-4]^=T;
1.5 C[i-1]^=T;
<rest omitted>

Which requires one extra XOR, but 2 less shifts per iteration.

Means: It's slower. Shifts are essentially free, but the XOR bites hard.
With 4 pipelines and register renaming, each loop takes 2 cycles, whereas
your variant takes 3 cycles. If common processors would issue a 3-operand
XOR, it would still by 2 cycles.

With only 2 pipelines, both variants take 4 cycles. For just 1 pipeline,
your variant would indeed by faster by 7 vs 8 cycles.

Furthermore since all the exponents (201,105 and 9) are in this case odd, this
pentanomial is ideal for fast square roots in this field.

Now that is a better idea. Any more analysis of the typical ratio of
reductions vs. square roots and the costs?

There is a recent paper on eprint by Avanzi which discusses this

http://eprint.iacr.org/2007/103

Does anyone know the criteria used to choose the irreducible polynomials used in the standards and by NIST? I had assumed that they were chosen to be optimal in some sense but apparently not.

From X9.62-1998 "Public Key Cryptography For The Financial Services
Industry":-

"Table C-3 in Annex C lists an irreducible pentanomial of degree m over F2 for each m, 160 < m < 2000, for which an irreducible trinomial of degree m does not exist. For each such m, the table lists the triple (k1, k2, k3) for which (i) x^m + x^k3 + x^k2+ x^k1 + 1 is irreducible over F2; (ii) k1 is as small as possible; (iii) for this particular value of k1, k2 is as small as possible; and (iv) for these particular values of k1 and k2, k3 is as small as possible."

Is this choice basically arbitrary, or was there some reason for it?

In the reduction algorithm (above) each element of C[i] is written to and read from just once - one can unroll the loop to achieve this, so the work associated with memory accesses in an invariant. Its the number of XORs and shifts which count. The cost is therefore architecture dependent - on an ARM processor with its barrel shifter, shifts are (as you say) free. On a Pentium they are not, and on some smaller processors shifts depend on the amount of the shift and are thus potentially much more expensive than XORs. The cost also depends on the word-size.

Consider the NIST pentanomial for GF(2^283) on a 32-bit processor, x^283+x^12+x^7+x^5+1. Per iteration its cost is 8 XORs and 8 shifts. Using for example the pentanomial x^283+x^119+x^91+x^59+1 the cost is 6 XORs and 4 shifts, which has got to be faster any way you look at it - nearly twice as fast on some architectures.

Some sources (for example "Guide to Elliptic Curve Cryptography"), state that it is advantageous if "the middle terms" of the pentanomial are "close to eachother". I don't get this. In my GF(2^233) example above the middle terms (201, 105 and 9) are not at all close.


Mike

.

Relevant Pages

  • Re: Pentanomial better than trinomial
    ... shifts are free. ... For this type of algorithm there is a lot of "Instruction Level Parallelism" and a good compiler could probably schedule instructions so as to avoid having to pay a price for any dependencies. ... So I would maintain that XORs and shifts would cost the same in this setting. ...
    (sci.crypt)
  • Re: AAA, etc.
    ... of a fixed size shift and a few bit shifts. ... Depending on silicon costs and required speed it might even be ... My doc's say 3 cycles just to clear the latches, ... Clearing latches or 4 or 8-bit portions of them is ...
    (alt.lang.asm)
  • Re: a new very fast hash algorithm (160 bits), with a technique of "overlapping sums"
    ... > the AMD processors have real ALUs....]. ... Rotates and shifts have the same latency on Northwood (4 cycles). ... Get your facts straight, Tom :-) ...
    (sci.crypt)