 Exponentiation

One of the most important arithmetic operations for public-key cryptography is exponentiation. The RSA scheme (§8.2) requires exponentiation in Z,„ for some positive integer m, whereas Diffie-Heilman key agreement (§12.6.1) and the ElGamal encryption scheme (§8.4) use exponentiation in Zp for some large prime p. As pointed out in §8.4.2, ElGamal encryption can be generalized to any finite cyclic group. This section discusses methods for computing the exponential ge, where the base g is an element of a finite group G (§2.5.1) and the exponent e is a non-negative integer. A reader uncomfortable with the setting of a general group may consider G to be Z*n; that is, read ge as mod m.

An efficient method for multiplying two elements in the group G is essential to performing efficient exponentiation. The most naive way to compute ge is to do e - 1 multiplications in the group G. For cryptographic applications, the order of the group G typically exceeds 2160 elements, and may exceed 21024. Most choices of e are large enough that it would be infeasible to compute ge using e - 1 successive multiplications by g.

There are two ways to reduce the time required to do exponentiation. One way is to decrease the time to multiply two elements in the group; the other is to reduce the number of multiplications used to compute ge. Ideally, one would do both.

This section considers three types of exponentiation algorithms.

• 1. basic techniques for exponentiation. Arbitrary choices of the base g and exponent e are allowed.
• 2. fixed-exponent exponentiation algorithms. The exponent e is fixed and arbitrary choices of the base д are allowed. RSA encryption and decryption schemes benefit from such algorithms.
• 3. fixed-base exponentiation algorithms. The base д is fixed and arbitrary choices of the exponent e are allowed. ElGamal encryption and signatures schemes and Diffie- Hellman key agreement protocols benefit from such algorithms.

Techniques for general exponentiation

This section includes general-purpose exponentiation algorithms referred to as repeated square-and-multiply algorithms.

(i) Basic binary and k-ary exponentiation

Algorithm 14.76 is simply Algorithm 2.143 restated in terms of an arbitrary finite abelian group G with identity element 1.

14.76 Algorithm Right-to-left binary exponentiation

INPUT: an element дG and integer e > 1.

OUTPUT: ge.

• 1. At—1, S-tg.
• 2. While e ф 0 do the following:
• 2.1 If e is odd then At-A • S.
• 2.2 et—|_e/2j.
• 2.3 Ife^OthenS^S-S.
• 3. Retum(A).
• 14.77 Example (right-to-left binary exponentiation) The following table displays the values of A, e, and 5 during each iteration of Algorithm 14.76 for computing 283. □
 A 1 9 У3 У3 У11 У27 У27 92? 927 y283 e 283 141 70 35 17 8 4 2 1 0 s 9 У2 У4 У* y1(i У32 y64 912S 9256 -

14.78 Note (computational efficiency of Algorithm 14.76) Let t + 1 be the bitlength of the binary representation of e, and let wt(e) be the number of l’s in this representation. Algorithm 14.76 performs t squarings and wt(e) - 1 multiplications. If e is randomly selected in the range 0 < e < |6'| = n, then about [lg n squarings and |([lg n + 1) multiplications can be expected. (The assignment 1 • x is not counted as a multiplication, nor is the operation 1 • 1 counted as a squaring.) If squaring is approximately as costly as an arbitrary multiplication (cf. Note 14.18), then the expected amount of work is roughly | |_lg nj multiplications.

Algorithm 14.76 computes A • 5 whenever e is odd. For some choices of g, A ■ g can be computed more efficiently than A • 5 for arbitrary' S. Algorithm 14.79 is a left-to-right binary exponentiation which replaces the operation A • S (for arbitrary S) by the operation A • g (for fixed g).

14.79 Algorithm Left-to-right binary exponentiation

INPUT: gG and a positive integer e = (etet_i • • • eieo)2- OUTPUT: ge.

• 1. A<-1.
• 2. For i from t down to 0 do the following:
• 2.1 A<-A-A.
• 2.2 If e; = 1, then A*-A g.
• 3. Returned).
• 14.80 Example (left-to-right binary exponentiation) The following table displays the values of A during each iteration of Algorithm 14.79 for computing o283. Note that t = 8 and 283 = (100011011)2. □
 г 8 7 6 5 4 3 2 1 0 et 1 0 0 0 1 1 0 1 l A 9 2 94 S8 917 935 970 gUl 5283

14.81 Note (computational efficiency of Algorithm 14.79) Let t + 1 be the bitlength of the binary representation of e, and let wt(e) be the number of l’s in this representation. Algorithm 14.79 performs t + 1 squarings and wt(e) - 1 multiplications by g. The number of squarings and multiplications is the same as in Algorithm 14.76 but, in this algorithm, multiplication is always with the fixed value g. If g has a special structure, this multiplication may be substantially easier than multiplying two arbitrary elements. For example, a frequent operation in ElGamal public-key schemes is the computation of gk mod p, where g is a generator of Z* and p is a large prime number. The multiple-precision computation A ■ g can be done in linear time if g is chosen so that it can be represented by a single-precision integer (e.g., g = 2). If the radix b is sufficiently large, there is a high probability that such a generator exists.

Algorithm 14.82, sometimes referred to as the window method for exponentiation, is a generalization of Algorithm 14.79 which processes more than one bit of the exponent per iteration.

14.82 Algorithm Left-to-right fc-ary exponentiation

In Algorithm 14.83, Algorithm 14.82 is modified slightly to reduce the amount of pre- computation. The following notation is used: for each i, 0 < i < t, if е* ф 0, then write e, = 2h‘Ui where u, is odd; if e* = 0, then let /i; = 0 and щ = 0.

14.83 Algorithm Modified left-to-right A-ary exponentiation

INPUT: g and e = (etet_i • • • eie0)(,, where b = 2k for some к > 1. OUTPUT: ge.

• 1. Precomputation.
• 1.1 go<— 1, gi<—g, 92^ 92
• 1.2 For i from 1 to (2k 1 - 1) do: g2i+i<~92i-i92
• 2. Ai—1.
• 3. For г from t down to 0 do: A2^ h■9u,)2''' ■
• 4. Retum(A).
• 14.84 Remark (right-to-left k-ary exponentiation) Algorithm 14.82 is a generalization of Algorithm 14.79. In a similar manner, Algorithm 14.76 can be generalized to the A--ary case. However, the optimization given in Algorithm 14.83 is not possible for the generalized right-to-left /.--ary exponentiation method.
• (ii) Sliding-window exponentiation

Algorithm 14.85 also reduces the amount of precomputation compared to Algorithm 14.82 and, moreover, reduces the average number of multiplications performed (excluding squarings). к is called the window size.

14.85 Algorithm Sliding-window exponentiation

INPUT: g, e = (etet-i ■ ■ ■ eieo)2 with et = 1, and an integer к > 1.

OUTPUT: ge.

• 1. Precomputation.
• 11 9i^9, Э2<-д2-
• 1.2 For i from 1 to (2fc_1 - 1) do: g2i+i^92i-i92-
• 2. A<-1, i^t.
• 3. While i. > 0 do the following:
• 3.1 If e* = 0 then do: A<-A2, i<-i - 1.
• 3.2 Otherwise (е, ф 0), find the longest bitstring е*е;_! • • • e; such that i—l+l < k and e; = 1, and do the following:

A<-A2 ■ 9(eiei-,...e,-)2 - I-

4. Retum(rf).

 i A Longest bitstring 13 1 101 10 95 101 7 (5) V = 945 111 4 (з45)У = 367 - 3 (дж7)2 = д™ - 2 (734)2 = 91468 101 0 (91468)V = U749 -

Table 14.15: Sliding-window exponentiation with к = 3 and exponent e = (10110111100101)2.

• 14.87 Note (comparison of exponentiation algorithms) Let t + 1 be the bitlength of e, and let / + 1 be the number of k-bit words formed from e; that is, l = {t. + l)/fc] - 1 = [t/k. Table 14.16 summarizes the number of squarings and multiplications required by Algorithms 14.76, 14.79, 14.82, and 14.83. Analysis of the number of squarings and multiplications for Algorithm 14.85 is more difficult, although it is the recommended method.
• (i) (squarings for Algorithm 14.82) The number of squarings for Algorithm 14.82 is Ik. Observe that Ik = [t/kk = t - (t mod k). It follows that t — 1) < Ik < t and that Algorithm 14.82 can save up to к — 1 squarings over Algorithms 14.76 and 14.79. An optimal value for к in Algorithm 14.82 will depend on t.
• (ii) (squarings for Algorithm 14.83) The number of squarings for Algorithm 14.83 is lk+ h[ whereO < hi mod k. Since t — (к — 1) < Ik < lk + hi < lk + (t mod k) = t or t - (к - 1) < lk + Ы < t, the number of squarings for this algorithm has the same bounds as Algorithm 14.82.
 Algorithm Precomputation squarings Multiplications sq mult worst case average case 14.76 0 0 t t tf 2 14.79 0 0 t t tj 2 14.82 1 2fc -3 t - (к - 1) < Ik < t l-l l(2k - l)/2k 14.83 1 2Л'-1 - 1 t — (к — 1) < Ik + hi < t l-l l{2k - l)/2k

Table 14.16: Number of squarings (sq) and multiplications (mult) for exponentiation algorithms.

(iii) Simultaneous multiple exponentiation

There are a number of situations which require computation of the product of several exponentials with distinct bases and distinct exponents (for example, verification of ElGa- mal signatures; see Note 14.91). Rather than computing each exponential separately, Algorithm 14.88 presents a method to do them simultaneously.

Let eo, ei,... , e^_ i be positive integers each of bitlength tsome of the high-order bits of some of the exponents might be 0, but there is at least one e,- whose high-order bit is 1. Form a к x t array EA (called the exponent array) whose rows are the binary representations of the exponents e,, 0 < i < к — 1. Let I, be the non-negative integer whose binary representation is the jth column, 1 < j < t, of EA, where low-order bits are at the top of the column.

14.88 Algorithm Simultaneous multiple exponentiation

INPUT: group elements go,9i____,9k-1 and non-negative t-bit integers eo, ei,... еь-i-

OUTPUT: po°9i‘''' 9kk-i ■

• 1. Precomputation. For i from 0 to (2k - 1 ): Gj<- П^=о 9jJ w*iere * = (u--i • • • *0)2-
• 2. A<-1.
• 3. For i from 1 to t do the following: A<—A ■ A, A<—A ■ G/t.
• 4. Retum(A).
• 14.89 Example (simultaneous multiple exponentiation') I11 this example, 5o°5r°^24 is computed using Algorithm 14.88. Let eo = 30 = (11110)2, ei = 10 = (01010)2, and t = 24 = (11000)2. The 3x5 array EA is:
 1 1 1 1 0 0 1 0 1 0 1 1 0 0 0

The next table displays precomputed values from step 1 of Algorithm 14.88.

 г 0 1 2 3 4 5 6 7 Gi 1 90 9i 9o9i 92 9092 9i92 9o9i92

Finally, the value of A at the end of each iteration of step 3 is shown in the following table. Here, Ii = 5, /2 = 7, /3 = 1, /4 = 3, and /5 = 0.

 г 1 2 3 4 5 A 9092 go 9192 9o9i9-! .лв.-блг 9o 9i92 Л30ПШ„24 9о 9i 92

• 14.90 Note (.computational efficiency of Algorithm 14.88)
• (i) Algorithm 14.88 computes gffff ■ ■geffSi (where each e, is represented by t bits) by performing t - 1 squarings and at most (2k - 2) + t - 1 multiplications. The multiplication is trivial for any column consisting of all 0’s.
• (ii) Not all of the G;, 0 < i < 2k -1, need to be precomputed, but only for those i whose binary representation is a column of EA.
• 14.91 Note (EIGamal signature verification) The signature verification equation for the ElGa-

mal signature scheme (Algorithm 11.64) is ah(-m'> (a~a)r = rs (mod p) where pis a large prune, q a generator of Z*. aa is the public key, and (r, s) is a signature for message m. It would appear that three exponentiations and one multiplication are required to verify the equation. If t = fig p] and Algorithm 11.64 is applied, the number of squarings is 3(f — 1) and the number of multiplications is, on average, 3t/2. Hence, one would expect to perform about (9f - 4)/2 multiplications and squarings modulo p. Algorithm 14.88 can reduce the number of computations substantially if the verification equation is rewritten as a/dm)(c*-a)'>-'s = 1 (mod p). Taking go = a, g = a~a,g2 = r, and eo = h(m) mod (p — 1), ei = r mod (p — 1), = — s mod (p — 1) in Algorithm 14.88, the

expected number of multiplications and squarings is (t — 1) + (6 + (7EA will be non-zero and necessitate a non-trivial multiplication.) This is only about 25% more costly than a single exponentiation computed by Algorithm 14.79.

Algorithms 14.76 and 14.79 have been described in the setting of a multiplicative group. Algorithm 14.92 uses the methodology of Algorithm 14.79 to perform efficient multiplication in an additive group G. (For example, the group formed by the points on an elliptic curve over a finite field uses additive notation.) Multiplication in an additive group corresponds to exponentiation in a multiplicative group.

14.92 Algorithm Left-to-right binary multiplication in an additive group

INPUT: gG, where G is an additive group, and a positive integer e = (etet_i • • • eieo)2- OUTPUT: e • g.

• 1. 0.
• 2. For i from t down to 0 do the following:
• 2.1 A<-A + A.
• 2.2 If e* = 1 then A<—A + g.
• 3. Retum(A).
• 14.93 Note (the additive group Zm)
• (i) If G is the additive group Zm, then Algorithm 14.92 provides a method for doing modular multiplication. For example, if a, b € Zm, then a ■ b mod m can be computed using Algorithm 14.92 by taking д = a and e = 6, provided b is written in binary.
• (ii) If a, b e Zm, then a < m and b < m. The accumulator A in Algorithm 14.92 never contains an integer as large as 2m; hence, modular reduction of the value in the accumulator can be performed by a simple subtraction when A > ?n; thus no divisions are required.
• (iii) Algorithms 14.82 and 14.83 can also be used for modular multiplication. In the case of the additive group Zm, the tune required to do modular multiplication can be unproved at the expense of precomputing a table of residues modulo m. For a left-to- right /с-ary exponentiation scheme, the table will contain 2k - 1 residues modulo m.
• (v) Montgomery exponentiation

The introductory remarks to §14.3.2 outline an application of the Montgomery reduction method for exponentiation. Algorithm 14.94 below combines Algorithm 14.79 and Algorithm 14.36 to give a Montgomery’ exponentiation algorithm for computing xe mod m. Note the definition of m! requires that gcd(m, R) = 1. For integers и and v where 0 < u, v < in, define Mont (и, v) to be uvR~l mod in as computed by Algorithm 14.36.

14.94 Algorithm Montgomery exponentiation

INPUT: m = (mi-1 ■ ■ ■ mo)b, R = bl, m' = —m_1 mod b, e = (et ■ ■ ■ eo)2 with et = 1, and an integer x, 1 < x < m.

OUTPUT: xe mod m.

• 1. S+- Mont(:r, R2 mod in), A^R mod m. {R mod m and R2 mod m may be provided as inputs.)
• 2. For i from t down to 0 do the following:
• 2.1 A+- Mont(A, A).
• 2.2 If e; = 1 then A+- Mont(A, x).
• 3. A+- Mont(A, 1).
• 4. Retum(A).
• 14.95 Example {Montgomery exponentiation) Let x, m, and R be integers suitable as inputs to Algorithm 14.94. Let e = 11 = (1011)2; here, f = 3. The following table displays the values of A mod m at the end of each iteration of step 2, and after step 3. □
 i 3 2 1 0 Step 3 A mod m X xtR-1 x5R~4 xuR-10 Mont(A, 1) = x11 R~41 = я11
• 14.96 Note {computational efficiency of Montgomery' exponentiation)
• (i) Table 14.17 displays the average number of single-precision multiplications required for each step of Algorithm 14.94. The expected number of single-precision multiplications to compute xe mod m by Algorithm 14.94 is 31(1 + l)(f + 1).
• (ii) Each iteration of step 2 in Algorithm 14.94 applies Algorithm 14.36 at a cost of 21 (l+ 1) single-precision multiplications but no single-precision divisions. A similar algorithm for modular exponentiation based on classical modular multiplication (Algorithm 14.28) would similarly use 21(1 + 1) single-precision multiplications per iteration but also l single-precision divisions.
• (iii) Any of the other exponentiation algorithms discussed in §14.6.1 can be combined with Montgomery reduction to give other Montgomery exponentiation algorithms.
 Step 1 2 3 Number of Montgomery multiplications 1 2l 1 Number of single-precision multiplications 21(1 + 1) 3tl(l + 1) 1(1 + 1)

Table 14.17: Average number of single-precision multiplications per step of Algorithm 14.94.