TinyECCK: Efficient Elliptic CurveCryptography Implementation over GF (2m) on8-bit MICAz MoteSeog Chung Seo1, Dong-Guk Han2, Seokhie Hong1Graduate School of Information Management and Security,Korea University,{seosc, hsh}@cist.korea.ac.kr1Electronics and Telecommunications Research Institute,[email protected]. In this paper, we revisit a generally accepted opinion: im-plementing Elliptic Curve Cryptosystem (ECC) over GF (2m) on sensormotes using small word size is not appropriate because XOR multiplica-tion over GF (2m) is not efficiently supported by current low-powered mi-cropro cessors. Although there are some implementations over GF (2m) onsensor motes, their performances are not satisfactory enough to be usedfor wireless sensor networks (WSNs). We have found that a field multipli-cation over GF (2m) are involved in a numb er of redundant memory ac-cesses and its inefficiency is originated from this problem. Moreover, thefield reduction process also requires many redundant memory accesses.Therefore, we propose some techniques for reducing unnecessary memoryaccesses. With the proposed strategies, the running time of field multi-plication and reduction over GF (2163) can be decreased by 21.1% and24.7%, respectively. These savings noticeably decrease execution timessp ent in Elliptic Curve Digital Signature Algorithm (ECDSA) operations(signing and verification) by around 15% ∼ 19%. We present TinyECCK(Tiny Elliptic Curve Cryptosystem with Koblitz curve – a kind of TinyOSpackage supporting elliptic curve operations) which is the fastest ECCimplementation over GF (2m) on 8-bit sensor motes using ATmega128Las far as we know. Through comparisons with existing software imple-mentations of ECC built in C or hybrid of C and inline assembly onsensor motes, we show that TinyECCK outperforms them in terms ofrunning time, code size and supporting services. Furthermore, we showthat a field multiplication over GF (2m) can be faster than that overGF (p) on 8-bit ATmega128L processor by comparing TinyECCK withTinyECC, a well-known ECC implementation over GF (p). TinyECCKwith sect163k1 can compute a scalar multiplication within 1.14 secs ona MICAz mote at the expense of 5,592-byte of ROM and 618-byte ofRAM. Furthermore, it can also generate a signature and verify it in 1.37and 2.32 secs with 13,748-byte of ROM and 1,004-byte of RAM.2 Seog Chung Seo et al.1 IntroductionMany researchers have tried to apply the public-key cryptosystem, especiallyECC to wireless sensor networks to overcome the limitations of the symmetric-key based protocols at pairwise key setup and broadcast authentication phases.They concluded that employing ECC is viable in WSNs: Their implementationshave been shown reasonable performances in running time and code size [1, 8,10, 15]. Until now, implementations giving relatively satisfactory p erformanceare all based on GF (p) [1, 8, 15]. On the other hand, the implementations overGF (2m) result in disappointing performance [4, 7, 9, 10]. Some literatures [1, 8,10, 15] imputed the poor performances to insufficient support of field arithmeticoperations over GF (2m), especially field multiplication, of current low-poweredmicroprocessors that work in small word size, thus the implementation of ECCover GF (2m) would lead to lower performances. This paper revisits this opinionand shows that the field multiplication in GF (2m) can be faster than that inGF (p). There are following misunderstandings about the implementation of ECCover GF (2m) on sensor motes:Inefficient field multiplication: The field multiplication which is one of the mostfrequent operations in the elliptic curve operation in GF (2m) is regarded as beingless efficient than that in GF (p) on low-powered and small word-sized devicessince it requires partial XOR multiplications which are not efficiently supportedby current microprocessors at instruction level.1Heavy memory requirement for ECDSA: ECDSA implementations over GF (2m)require not only field arithmetic over GF (2m) but also field arithmetic overGF (p) for generating and verifying digital signatures. Thus, it may be thoughtthat the code size of ECDSA over GF (2m) is larger than that over GF (p). Actu-ally, most of existing works over GF (2m) only implement Elliptic Curve Diffie-Hellman (ECDH) protocol in their motes. However, the code size of optimizedimplementation of ECDSA over GF (2m) is comparable to that over GF (p).Our implementation, TinyECCK, achieves optimized code size for ECDSA andoutperforms TinyECC known as the most efficient software implementation ofECDSA over GF (p) on sensor motes.The contributions of this paper are described as follows.1. Showing field multiplication over GF (2m) can be faster than that over GF(p):We have found that the field multiplication and reduction over GF (2m) areinvolved in many redundant memory accesses. In fact, most of the intermedi-ate results of consecutive XOR multiplications during a field multiplicationover GF (2m) are stored at the same memory destination and same valuesare loaded several times. We present some techniques to eliminate much ofredundant memory accesses at field multiplication and reduction phases. Asthe result of applying the proposed techniques, the execution times of fieldmultiplication and reduction over GF (2163) are saved as much as 21.1% and1Partial XOR multiplication: The XOR operations of partial products in the fieldmultiplication over GF (2m). There is no carries in XOR multiplications.TinyECCK 324.7%, respectively. At this time, the running time of the proposed multipli-cation method is faster than the optimized field multiplication over GF (p)by 7.4%.2. Fastest software implementation of ECC over GF (2m): TinyECCK outper-forms existing all software implementations of ECC over GF (2m). Further-more, TinyECCK is the fastest among the software implementations builtin C or mixture of C and inline assembly over both GF (p) and GF (2m) onATmega128L processors.3. Efficient implementation of Koblitz curve over GF (2m) on 8-bit ATmega128Lprocessor : TinyECCK implements elliptic curve operations on Koblitz curvefor fast scalar multiplications. Because the point doubling operation in theKoblitz curve can be replaced by some trivial field squarings, the perfor-mance can be much improved compared with ordinary curves over GF (2m).2 Related WorkThere have been several implementations of ECC over both GF (2m) and GF (p)on sensor motes. They have tried to prove the feasibility of ECC