Fast Scalar Multiplication
for ECC over GF(p) using
Division Chains
Colin D. Walter
Royal Holloway, UK
Colin.Walter@rhul.ac.uk

Supported by European Commission grant ICT-2007-216676 ECRYPT IIWISA 2010

Colin Walter (RHUL)

1/16

Outline• Motivation & History• Standard Exponentiation Algorithms• OP-Addition Chains• Division Chains• Base/Digit Selection• Implementation• Examples• Conclusion

WISA 2010

Colin Walter (RHUL)

2/16

Motivation• Faster Exponentiation• Better understanding of recoding choices• More widely applicable methods• Pairings with small characteristic, e.g. 3– The Frobenius AM means the usual weighting ofsquares & multiplies is inappropriate

WISA 2010

Colin Walter (RHUL)

3/16

History• Division Chains / Double Base Repn – Arith 13 (1997)– Resource constrained environments:– Division chains save execution space (CDW)– DBNS saves storage space (Dimitrov)• Composite ECC operations dP+Q (Montgomery et al)– Reduced field operation count from shared values• Gebotys & Longa (PKC 2009)– Fixed algorithm for using 2P+Q, 3P and 5P.

WISA 2010

Colin Walter (RHUL)

4/16

Standard Methods
For resource-constrained environment:• Binary Square and Multiply~3/2 log2n ×ve operations for exponent n.

• Sliding Window~4/3 log2n ×ve operations for 2-bit window, digits ±1.

• NAF (non-adjacent form)
Same as for 2-bit sliding window.

• Division chains (case of no negative digits)~5/4 log2n with expensive pre-processing of exponent.
~7/5 log2n without effort
WISA 2010

Colin Walter (RHUL)

5/16

OP-Addition Chains• Wider range of operations than just adding.
Set OP of binary operators (λ,µ), representing λP+µQ.
An OP -addition chain is a sequence of quadruples(ai, bi, ki, pi) wherepi = (λλi,µµi) ∈ OP and ki = λiai + µibi
ai = ks , bi = kt for some s, t < i(a0,b0,k0,p0) = (1,0,1,(1,0))The standard addition chain has ai+bi = ki and starts (1,0,1)

WISA 2010

Colin Walter (RHUL)

6/16

Division Chains• Location aware chains – two locations.
Restricted to previous value and initial (table) value:(ki–1, 1, ki, pi) wherepi = (λi,µi) ∈ OP and ki = λiki–1 + µi
These are generated in reverse order:
From k = kn, choose pi = (λi,µi) where ki ≡ µi mod λi andcalculate ki–1 = (ki – µi) / λi .
• Hence the name “division” chain.
• If all λi = r are the same, this is the change a basealgorithm and µi are the digits of k base r.
WISA 2010

Colin Walter (RHUL)

7/16

Change of Basis• The rule ki–1 = (ki – µi)/λi producesk = (((µ1λ2 + µ2)λ3 +…+ µn –2)λn –1 + µn –1)λn + µn
• Rewrite this using bases ri and digits di :k = (((dn –1rn –2 + dn –2)rn –3 +…+ d2)r1 + d1)r0 + d0
• This recoding gives a left-to-right algorithm with tablevalues md and iterative stepm ← mri × mdi• When possible choose di = 0 to save a multiplication.

WISA 2010

Colin Walter (RHUL)

8/16

Example
23510 = (((((1)3 + 0)2 + 1)5 + 4)2 + 0)3 + 1• Pair (3,1)(235 – 1)/3= 78• Pair (2,0)(78 – 0)/2 = 39

• Pair (5,4)(39 – 4)/5 = 7• Pair (2,1)(7 – 1)/2= 3• Pair (3,0)(3 – 0)/3= 1• Pair (2,1)(1 – 1)/2= 0

There are usually several alternatives at each point.
• Set of possible bases is usually B = {2,3} or B = {2,3,5}.

WISA 2010

Colin Walter (RHUL)

9/16

Choosing the Chain• Assign a cost cd,r to each operation m ← mr × md .
– e.g. clock cycles if implementation is known,– else native word operations,– or ... field multns when in ECC, perhaps.

• Simplest cost is minmum length of addition chain for r,plus 1 if d ≠ 0 (i.e. the count of ×ve ops.)• Each digit/base choice affects remaining digits; the effecton cost diminishes with distance from the choice.
• Build search tree of next λ digits, say, and find cost,
including average cost c for remainder of k: for each digit,
cd,r – c log r• Pick first digit of cheapest choice, and repeat for rest of k.
WISA 2010

Colin Walter (RHUL)

10/16

Digit Choice (1)• Let πB = lcm {r ∈ B} for B = set of possible bases.
• If k ≡ k' mod πBλ then k, k' generate the same costs
for each of next λ base/digit choices.
• So next digit is determined by k mod πBλ & cost function c• Ideally maximize λ.
λ In practice consider k mod π
for one of the largest practical factors π of πBλ.
– If r = 2, say, is particularly cheap, preferentially increase thepower of 2 in π so choice of π reflects greater likelihood of 2.

• For each set of λ choices (r1,d1),...,(rλ,dλ) and ρ = r1r2...rλ ,(...((k – r1)/d1 – r2)/d2 ...– rλ)/dλ mod π/ρstill contains some infon which should be included in cost.
WISA 2010

Colin Walter (RHUL)

11/16

Digit Choice (2)• For cheapest (r1,d1),...,(rλ,dλ) for k mod π,choose (r1,d1) as the next digit/base pair for k.
This gives a recoding table mod π.
• The recoding is a Markov process. The states are residues
mod π. So asymptotic cost per key bit can be calculated.
(Monte Carlo simulation.)• During recoding, the residues ki mod π are not distributed
uniformly for random keys k. So costs for digit choices
may have been slightly inaccurate.
– Make local changes to the table, calculate new cost per bit,and update table if new average cost is cheaper.
WISA 2010

Colin Walter (RHUL)

12/16

Implementation• The table generally has good structure and can be easilytranslated into a simple set of rules, e.g.
if k ≡ 0 mod 2 then r = 2, d = 0
else if k ≡ 0 mod 5 then r = 5, d = 0
else ...

• There may be a few deeply nested, rarely occurring rules
which can be safely deleted without much effect.
• The result is a space and time efficient recoding scheme,
tailored to any required constrained environment.
• Including a base 3 or 5, say, as well as 2
makes it faster than binary algorithms
if the recoding process is cheap enough.
WISA 2010

Colin Walter (RHUL)

13/16

Example 1
Digits D = {0,±1,±3,...,±15}, bases B = {2,3}, OP = B×D, π = 2632
If k = 0 mod 9 and k ≠ 0 mod 4 thenr ← 3, d ← 0else if k = 0 mod 2 thenr ← 2, d ← 0else if k = 0 mod 3 and 18 < (k mod 64) < 46and ((k mod 64) – 32) ≠ 0 mod 3 thenr ← 3, d ← 0else r ← 2, d ← ((k+16) mod 32) – 16

• This is faster than the “record” algorithm in PKC 2009
(using Jacobi Quartic coordinates) but rather space hungry.
• About 1200 field multiplications for 160-bit key (~7.5 per bit).
WISA 2010

Colin Walter (RHUL)

14/16

Example 2
Digits D = {0,±1,±3,±5,±7}, bases B = {2,3}, OP = B×D, π = 2832
If k = 0 mod 9 and k ≠ 0 mod 4and (16 < (k mod 256) < 240) thenr ← 3, d ← 0else if k = 0 mod 2 thenr ← 2, d ← 0else if k = 0 mod 3 and 8 < (k mod 32) < 24and ((k mod 32) – 16) ≠ 0 mod 3 thenr ← 3, d ← 0else r ← 2, d ← ((k+8) mod 16) – 8• The pre-computed table has effectively just 4 elements.
• This is only ½% slower than Example 1• 2% faster than B = {2}; easily enough to cover the recoding.
WISA 2010

Colin Walter (RHUL)

15/16

Results & Conclusions• A technique for generating fast algorithms for scalarmultiplication in a wide variety of environments.
• Uses a multibase representation and can makeuse of efficient composite elliptic curve operations.
• Faster than binary-based methods,
but small recoding overhead.
• Can benefit from cheap Frobenius operation.
• Takes advantage of the available space resources.
• Unbeatable?
WISA 2010

Colin Walter (RHUL)

16/16