Protocol. Computer Networks 51(15), 4322“4337 (2007)

[17] Mills, D.L.: Network Time Protocol (Version 3) Speci¬cation, Implementation and

Analysis. RFC 1305 ( March 1992)

[18] Montoro, M.: Cain & Abel, http://www.oxid.it/cain.html

[19] Perrig, A., Canetti, R., Tygar, J.D., Song, D.: The TESLA Broadcast Authenti-

cation Protocol. RSA CryptoBytes 5(2), 2“13 (2002)

[20] Plummer, D.C.: Ethernet Address Resolution Protocol: Or converting network

protocol addresses to 48.bit Ethernet address for transmission on Ethernet hard-

ware. RFC 826 (November 1982)

[21] NT Kernel Resources: WinpkFilter, http://www.ntkernel.com

[22] Test TCP (TTCP) - Benchmarking Tool for Measuring TCP and UDP Perfor-

mance, http://www.pcausa.com/Utilities/pcattcp.htm

[23] Vyncke, E., Paggen, C.: LAN Switch Security. Cisco Press (2007)

[24] Ylonen, T., Lonvick, C.: The Secure Shell (SSH) Protocol Architecture. RFC 4251

(January 2006)

Faster Multi-exponentiation through Caching:

Accelerating (EC)DSA Signature Veri¬cation

Bodo M¨ller1, and Andy Rupp2

o

1

bmoeller@acm.org

2

Horst G¨rtz Institute for IT Security

o

arupp@crypto.rub.de

Abstract. When verifying digital signatures, achieving a high through-

put can be crucial. We present a technique that is useful for ECDSA

and DSA signatures. It assumes that common domain parameters are

used (which is typical of ECDSA) and that at least some signers recur

(as in many application scenarios). We can achieve noticeable speedups

in very di¬erent environments”from highly restricted ones where mem-

ory is very scarce to larger machines without severe memory restrictions.

Requirements for the target platform are very small for a bene¬cial appli-

cation of our technique. This makes it attractive for embedded systems,

where ECDSA is a signature scheme of choice.

É

More generally, what we consider is the task of computing power prod-

e

ucts 1¤i¤k gi i (“multi-exponentiation”) where base elements g2 , . . ., gk

are ¬xed while g1 is variable between multi-exponentiations but may re-

peat, and where the exponents are bounded (e.g., in a ¬nite group). We

present a new technique that entails two di¬erent ways of computing

such a product. The ¬rst way applies to the ¬rst occurrence of any g1

where, besides obtaining the actual result, we create a cache entry based

on g1 , investing very little memory or time overhead. The second way

applies to any multi-exponentiation once such a cache entry exists for

the g1 in question and provides for a signi¬cant speed-up.

Keywords: E¬cient implementation, elliptic curve cryptography, ex-

ponentiation, ECDSA, DSA, embedded cryptography.

1 Introduction

Consider a scenario where we repeatedly have to verify ECDSA signatures [1],

trying to keep the computational delay small for each veri¬cation. A time-

consuming step in ECDSA signature veri¬cation is computing a linear com-

bination u1 G + u2 Q of elliptic curve points G and Q, where G is speci¬ed by

domain parameters (i.e., ¬xed) and where Q constitutes the signer™s public key,

with integers u1 and u2 in the interval 0, ord(G)’1 both depending on the spe-

ci¬c signature. The same group with the same point G will typically be shared

Work done while the author was with the Horst G¨rtz Institute for IT Security.

o

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 39“56, 2008.

c Springer-Verlag Berlin Heidelberg 2008

40 B. M¨ller and A. Rupp

o

by many signers since elliptic curve domain parameters are often taken from

(intersecting) standards such as [19, Appendix 6], [1, Annex J], and [6] (with

domain parameter speci¬cations NIST P-192 aka prime192v1 aka secp192r1

and NIST P-256 aka prime256v1 aka secp256r1 common to all three of these).

Also, we usually can expect some signers and thus their Q values to recur. For

instance, consider public-key infrastructures:

“ A verifying party will encounter end-entity certi¬cates signed by possibly

very many di¬erent intermediate certi¬cation authorities. When a new cer-

ti¬cation authority appears for the ¬rst time, the verifying party does not

yet know how popular this particular certi¬cation authority is, i.e. if it has

signed many or just very few end-entity certi¬cates.

“ The same applies to signatures on documents, such as the ECDSA signa-

tures stored on the new digital “e-passports”. When verifying a passport for

airport immigration procedures, then quite possibly the next passenger in

line may be using a passport signed by the same agency. On the other hand,

the current passenger could be the only one from this particular country for

days.

Thus, for a given G, we have to compute linear combinations u1 G + u2 Q where

Q sometimes is “new” and sometimes is “old” (has been seen before); but

when a new Q appears, we generally do not know if and how frequently it will

reappear.

There are well-known techniques to compute u1 G + u2 Q much faster than by

computing both u1 G and u2 Q individually, and this can be done yet faster if G

and Q are both ¬xed and a one-time precomputation depending on these points

has been done. Performing such precomputation whenever a “new” Q shows up

may pay out if Q turns out to repeat, so that G and Q are ¬xed for a number

of linear combinations. However, this is an investment of resources that would

be lost if this particular Q does in fact not repeat.

We present a new technique that nearly avoids this drawback, provided that

space for permanently ¬xed precomputation depending on G only is not severely

limited. The ¬rst occurrence of some point Q in a computation u1 G + u2 Q

will incur very little penalty in terms of memory or time, and yet will leave

behind useful precomputed data that can be cached to speed up subsequent

linear combination computations involving the same G and Q.

While the ECDSA scenario best illustrates the practical use of our technique1 ,

the approach is in fact not restricted to the ECDSA or DSA case but may be

1

Another approach to speed up ECDSA signature veri¬cation is due to Antipa

et al. [2,24]. It works best for a slightly modi¬ed variant of the original signature

scheme, dubbed ECDSA— , but under appropriate circumstances, it can be useful for

the veri¬cation of standard ECDSA signatures. Where it makes sense to use the

technique from [2,24], our technique may be preferable depending on the expected

proportion of “old” to “new” Q values. In fact, we can get some of the bene¬t of

[2,24] for any “new” Q and all of the bene¬t of our technique for any “old” Q by

using a combination of both techniques in the case of a “new” Q, using speci¬c

imbalanced-scalar parameterizations within [2,24]. We omit further details on this.

Faster Multi-exponentiation through Caching 41

applied in more general settings: It is suitable for any abelian group or (more

generally) abelian semigroup with an identity element, henceforth written mul-

tiplicatively so that what we just described as linear combinations now turns

into power products. Computing power products sometimes is called multi-

exponentiation since it is a generalization of computing powers (exponentiation).

The computational task that we will consider is computing power products of

the form

e

gi i

1¤i¤k

where base elements g2 , . . ., gk are ¬xed once and for all, whereas g1 is variable

between multi-exponentiations and may repeat, while all exponents ei are as-

sumed to be ephemeral. We will assume that the exponents are positive and

at most bits long. (An appropriate value of is usually implied by the group

order. A negative exponent for a group can be handled through inversion of the

base element, or by reduction of the exponent modulo o where o is some multiple

of the order of the base element, such as the group order.) For our technique

to work as intended, we also assume that the exponent to variable base g1 is

not pathologically short (i.e., its length not just a fraction of ); rare statisti-

cal outliers are no problem. Besides ECDSA signature veri¬cation, this setting

also covers DSA signature veri¬cation [19]; however, it only applies when using

common domain parameters, which is much more customary for ECDSA.

Concerning the implementation platform, we only need to make very mild

assumptions that are, in particular, commonly satis¬ed by embedded systems:

We assume that at least read-only memory is not severely limited, so that pre-