当前位置:首页 >> >> Public-key cryptography on the top of a needle

Public-key cryptography on the top of a needle


Public-Key Cryptography on the Top of a Needle
Lejla Batina, Nele Mentens, Kazuo Sakiyama, Bart Preneel, Ingrid Verbauwhede
Katholieke Universiteit Leuven, ESAT/SCD-COSIC, Belgium Kasteelpark Arenberg 10, B-3001 Leuven-Heverlee, Belgium Email: {lbatina, nmentens, ksakiyam}@esat.kuleuven.be

Abstract— This work describes the smallest known hardware implementation for Elliptic/Hyperelliptic Curve Cryptography (ECC/HECC). We propose two solutions for Publickey Cryptography (PKC), which are based on arithmetic on elliptic/hyperelliptic curves. One solution relies on ECC over binary ?elds F2n where n is a composite number of the form 2p (p is a prime) and another on HECC on curves of genus 2 over F2p . This implies the same arithmetic unit for both cases which supports arithmetic in a ?eld F2p . Our best solution that still results in a feasible performance features less than 5 kgates with an average power consumption smaller than 10 ?W .

I. I NTRODUCTION The ?eld of embedded systems is growing at a rapid rate, as devices such as mobile phones, PDAs, smart cards and more recently RFID tags, sensor nodes and key immobilizers have become unavoidable in our everyday life. Hence, the distinguishing characteristics of embedded security can be divided into two categories: resource-limitation and physical accessibility. The former one speci?es severe resource constraints on the security architecture in terms of memory, computational capacity, and energy for embedded devices. The most challenging tasks for embedded security are implementations of Public-key Cryptography (PKC). RFID tags are small wireless devices for pervasive computing. Despite their rigorous constraints featuring extremely low budget for power and die size they also give rise to serious security and privacy issues. Typical security services include authentication, key management and encryption. Although some experts are a priori giving up on public key solutions, assuming it being too expensive and too power hungry, there exists a line of research exploring the limits of compact public key implementations for low-cost applications such as RFIDs and sensor networks. In our previous work we investigated standardized low cost solutions for Elliptic Curve Cryptography (ECC) processors supporting security algorithms and protocols for RFID [1]. Namely, in standards it is mainly recommended to use ECC over a ?eld F2p , where p is a prime. In this work we describe a new solution based on Hyperelliptic Curve Cryptography (HECC) and on ECC over composite ?elds. HECC has some advantages over ECC because of the possibility to work in a smaller ?eld e.g. for HECC (in the case of genus 2 curves) one can work in the ?eld F2n whilst obtaining the same level of security as for ECC over ?elds of bit-lengths that are twice as large. The same holds for ECC over composite ?elds. This property allows for more compact ALU than in the case of ECC.
1-4244-0921-7/07 $25.00 ? 2007 IEEE.

We revisit the algorithms for HECC and ECC over composite ?elds and optimize them on the number of registers, resulting in an area-optimized solution. Our results show that the arithmetic unit for those two cases is smaller than the one for standardized ECC, but memory requirements are slightly bigger. Using RAM for storage, which would result in smaller number of gates than register ?les, one could have a feasible low cost solution using all kinds of curve-based cryptography. The paper is organized as follows. Section II lists some related work. In Sect. III we give some background information on curve-based cryptography and supporting arithmetic. In Sect. IV we elaborate on a suitable selection of parameters and algorithms and in Sect. V we outline our architecture and describe our hardware implementation. Our results are discussed in Sect. VI. Section VII concludes the paper. II. R ELATED W ORK As related previous work we mention implementations of Public-key cryptosystems for resource constrained environments such as RFID tags and sensor networks. Gaubatz et al. [5] investigated ECC implementations for wireless sensor networks. The architecture of the ECC processor occupied an area of 18 720 gates and consumed less than 400 ?W of power at 500 kHz. The ?eld used was a prime ?eld of order ≈ 2100 . PKC processors for RFID tags include the results of Wolkerstorfer [12] and Kumar and Paar [8]. Wolkerstorfer [12] showed that ECC based PKC is feasible on RFID-tags by implementing the ECDSA on a small IC. The chip has an area complexity of around 23 000 gates and it features a latency of 6.67 ms for one point multiplication at 68.5 M Hz. However, it can be used for both types of ?elds e.g. F2191 and Fp192 . The results of Kumar and Paar [8] include an area complexity of almost 12 kgates and a latency of 18 ms for one point multiplication over F2131 at 13.56 M Hz. The operating frequency is in both cases too high for those applications and therefore the results cannot be properly evaluated. Namely, with such a high frequency the power consumed becomes too large, which has the most crucial impact on the feasibility of the implementations. Our previous work described in [1] considers an ECC processor over a range of ?elds varying from F2131 till F2163 . The best solution features 6718 gates for arithmetic and control unit (data memory not included) in 0.13 ?m CMOS technology over the ?eld F2131 , which provides a reasonable level of security for the time being. In this case the consumed power is less than 15 ?W when operating frequency

1831

is 200 kHz. We compare the previous implementations with our new results in Section VI in more detail. III. M ATHEMATICAL BACKGROUND In general, ECC relies on a group structure induced on an elliptic curve. A set of points on an elliptic curve together with the point at in?nity, denoted ∞, and with point addition as binary operation has the structure of an abelian group. Here we consider ?nite ?elds of characteristic two. A non-supersingular elliptic curve E over F2n is de?ned as the set of solutions (x, y) ∈ F2n × F2n of the equation: y 2 + xy = x3 + ax2 + b where a, b ∈ F2n , b = 0, together with ∞. Hyperelliptic Curve Cryptography (HECC) was proposed in 1988 by Koblitz [7] as a generalization of ECC. More details can be found in [2], [10]. The scalar multiplication i.e. operation k ? P (where k is an integer and P a point or divisor on EC/HEC respectively) is the basic operation for all ECC/HECC protocols. At the next (lower) level are the group operations i.e. point/divisor addition and doubling. The lowest level consists of ?nite ?eld operations such as addition, subtraction, multiplication and inversion required to perform the group operations. The scalar multiplication is easily performed via repeated group operations. The basic scheme is called double-and-add or the binary method [2]. Elliptic curves can be viewed as a special case of hyperelliptic curves i.e. an elliptic curve is a hyperelliptic curve of genus g = 1. Here we consider a hyperelliptic curve C of genus g = 2 over GF(2n ), which is de?ned by an equation of the form: C : y 2 + h(x)y = f (x) in GF(2n )[x, y] , where h(x) ∈ GF(2n )[x] is a polynomial of degree at most g and f (x) is a monic polynomial of degree 2g + 1. For genus 2 curves, in the general case the following equation is used: y 2 +(h2 x2 +h1 x+h0 )y = x5 +f4 x4 +f3 x3 +f2 x2 +f1 x+f0 . For ECC over a composite ?eld we consider F22·p as a ?eld of quadratic extension over F2p , so we can write F22·p = F2p [x]/(f (x)), where deg(f ) = 2. In this case each element from the ?eld F22·p is represented as c = c1 t + c0 where c0 , c1 ∈ F2p , and all operations in this ?eld can be done by means of operations in F2p . In [4], the Weil descent attack is introduced against EC de?ned over binary ?elds of composite degree n = k · m. This work put some doubt on security of composite ?eld implementations of EC in general. However, further investigations have shown that composite ?elds with degree n = 2 · p (i.e., extension of degree two), where p is prime, remain secure against Weil Descent attacks and its variants. IV. A LGORITHMS S ELECTION AND O PTIMIZATIONS For the ECC point multiplication we chose the method of Montgomery [11] that maintains the relationship P2 ? P1 as invariant. It uses a representation where computations are performed on the x-coordinate only in af?ne coordinates (or on the X and Z coordinates in projective representation). That fact allows us to save registers which is one of the main criteria for obtaining a compact solution.

As starting point for our optimizations we use the formulae of Lopez and Dahab [9]. The original formulas in [9] require 2 intermediate registers in normal ECC if the point operations are performed sequentially. In our case we eliminated one more intermediate register, which added a few more steps to the original algorithms. However, mapping this algorithm to the corresponding one suitable for composite ?elds requires some additional intermediate registers as we translate the ?eld arithmetic to the arithmetic in the sub?eld as shown in Table I.
TABLE I BASIC OPERATIONS IN F(2p )2 EXPRESSED IN OPERATIONS IN F2p . Operation in F(2p )2 F2p Addition 2ADD Multiplication 3MUL+4ADD

From the formulae for point operations for projective coordinates [2] it is evident that we need to implement only multiplications and additions. Squaring is considered as a special case of multiplication in order to minimize the area and inversion is avoided by use of projective coordinates. We assume that conversion to af?ne coordinates can be computed at the reader’s side. Note also that, if necessary, the one inversion that is required can be calculated by use of multiplications. In this way the area remains almost intact and some small control logic has to be added. For our HECC implementation we used so-called type II curves [3], which are de?ned by h2 = 0, h1 = 1. As a starting point for divisor operations we used formulae from [6]. Those curves allow for faster doublings than for a general curve, while security remains intact. However, we optimized the formulae on the number of intermediate variables which resulted in a small increase in number of multiplications. In this way, we can perform a trade-off between area and performance. V. C URVE - BASED P ROCESSORS FOR LOW- COST
APPLICATIONS

Our solution for a curve-based processor is shown in Fig. 1. The architecture consists of the following blocks: a control unit (FSM), a modular arithmetic unit (MALU), and some memory (RAM and ROM). In ROM the ECC/HECC parameters and some constants used in algorithms are stored. On the other hand, RAM contains all input and output variables and therefore it communicates with both, the ROM and the MALU. The FSMs control the scalar multiplication k ? P and the point/divisor operations. In addition, the controller commands the MALU which performs ?eld operations. When the START nk ?1 signal is set, the bits of k = i=0 ki 2i , ki = {0, 1}, nk = log2 k , are evaluated from MSB to LSB. The control consists of a number of simple state machines and a counter and its area cost is small. The datapath of the MALU is an MSB-?rst bit-serial F2n multiplier with digit size d. This arithmetic unit computes A(x)B(x) mod P (x) where A(x) = ai xi , B(x) = bi xi

1832

Control

ECC over GF((283)2) FSM Scalar Mult.

Key Reg.

ROM (Curve parameters, Initial Point) RAM (Intermediate Variables) 83

Point Add. over a composite field

Point Dbl. over a composite field

MALU

Fig. 4 and Fig. 5 for ECC and HECC respectively. The power estimates were made assuming the operating frequency of 200 kHz. With this frequency the power stays between 8 and 16 ?W which is assumed to be acceptable for these applications.

Control

HECC over GF (283) FSM Scalar Mult.

Key Reg.

ROM (Curve parameters, Initial Point) RAM (Intermediate Variables) 83

Divisor Add.

Divisor Dbl.

MALU

50000 40000

Area [um ]

2

Fig. 1.

Architecture of our curve-based procesoor.

30000 20000 10000 4 0 67 71 79 Field le ngt h 1 83 2 8

and P (x) = pi xi . Modular addition is also supported by the same hardware logic. This operation requires additional multiplexors and XORs. However the cost of this solution is much cheaper compared to the case of having a separate modular adder. This type of hardware sharing is very important for such low-cost applications. The proposed datapath is scalable in the digit size d which can be determined arbitrary by exploring the best combination of performance and cost. Details of the MALU are given in [1]. VI. R ESULTS Now we give the results for area complexity, power consumption and the latency in the case of ECC/HECC scalar multiplication. The designs were synthesized by Synopsys Design Vision using a 0.13 ?m CMOS library. We rely on the arithmetic in binary ?elds F2p where p varies from bitsize 67 till 83. The results of the area complexity for various architectures with respect to the choice of ?elds and the size of d for the MALU are given in Table II. The results for the complete architecture in gates are given in Table III.
TABLE II T HE AREA COMPLEXITY OF MALU IN GATES . Field size 67 71 79 83 d=1 2295 2426 2705 2844 d=2 2551 2694 2953 3154 d=4 3041 3201 3558 3739 d=6 3574 3709 4157 4328 d=8 4056 4217 4676 4956

Fig. 2.

Results for area complexity in ?m2 (ECC-comp).

25 20

Power [uW]

15 10 8 5 4 0 67 79 Field le ngt h 71 1 83 2 6

Fig. 3.

Results for the power consumed (ECC-comp).

TABLE III T HE COMPLETE AREA COMPLEXITY IN GATES . Field size ECC: 67 HECC: 67 ECC: 71 HECC: 71 ECC: 79 HECC: 79 ECC: 83 HECC: 83 d=1 4345 5893 4523 6073 4884 6436 5071 6622 d=2 4600 6147 4787 6337 5180 6729 5375 6930 d=4 5089 6635 5293 6845 5740 7290 5971 7513 d=6 5612 7166 5801 7352 6340 7894 6558 8112 d=8 6103 7652 6309 7861 6864 8413 7193 8747

The graphical representations of our results for area in ?m2 and for the total power consumed are shown in Fig. 2, Fig. 3,

Next we give the numbers for the performance. For the point multiplication we used Montgomery ladder and for divisor scalar multiplication the binary method. We calculate the total number of cycles for each ?eld operation by use of the following formulae for ?eld operations. The total number of cycles for one ?eld multiplication is n + 3 where n and d d are the bit size of an arbitrary element from the ?eld in which we are working and the bit size respectively. On the other hand, one ?eld addition takes 4 cycles. The number of cycles required for one point multiplication in the case of ECC over a composite ?eld F22p is: (p ? 1)[36( p + 324]. For HECC d over F2p we get the following number of cycles for one scalar multiplication: (p ? 1)[115( p + 621]. d The results for the total number of cycles of one point multiplication for ECC are given in Table IV. To calculate the time for one point multiplication we need an operating frequency. However, the frequency that can be used is strictly in?uenced by the total power. We assumed an operating frequency of 200 kHz in order to estimate the actual timing as our power results showed to be reasonable for RFID applications. We get

1833

Dig

it s

ize

Dig

it s

ize

6

50000 40000

Area [um ]

30000 20000 10000 4 0 67 71 2 1 83 8

do not include RAM. The amount of storage that is required for our implementation is to store 13n and 28n bits for ECC and HECC respectively, where n is the number of bits of elements in a sub?eld. We can conclude that our architecture presents the smallest known curve-based crypto processor for low-cost applications. VII. C ONCLUSIONS This work presents architectures for low-cost applications of curve-based cryptography for RFID tags. Several solutions for various ?eld sizes are given. Our results show that PKC for RFIDs is an option but further investigations are necessary with respect to the memory requirements and more precise power estimates. ACKNOWLEDGMENTS Lejla Batina, Nele Mentens and Kazuo Sakiyama are funded by FWO projects (G.0450.04, G.0475.05) and FP6 project SESOC. This research has been also partially supported by the EU IST FP6 project ECRYPT and by IBBT, and K.U. Leuven (OT). R EFERENCES
8 6 2

2

Field le ngth

79

Fig. 4.

Results for area complexity in ?m2 (HECC).

25 20

Power [uW]

15 10 5

[1] L. Batina, N. Mentens, K. Sakiyama, B. Preneel, and I. Verbauwhede. Low-cost Elliptic Curve Cryptography for wireless sensor networks. In L. Buttyan, V. Gligor, and D. Westhoff, editors, In Proceedings of Third 67 1 71 79 Field le European Workshop on Security and Privacy in Ad hoc and Sensor 83 ngth Networks, volume 4357 of LNCS, pages 6–17. Springer-Verlag, 2006. [2] I. Blake, G. Seroussi, and N. P. Smart. Elliptic Curves in Cryptography. London Mathematical Society Lecture Note Series. Cambridge University Press, 1999. Fig. 5. Results for the power consumed (HECC). [3] B. Byramjee and S. Duquesne. Classi?cation of genus 2 curves over F2n and optimization of their arithmetic. Cryptology ePrint Archive: TABLE IV Report 2004/107. T HE NUMBER OF CYCLES REQUIRED FOR ONE POINT MULTIPLICATION [4] G. Frey. How to disguise an elliptic curve (Weil descent). Presentation given at the 2nd Elliptic Curve Cryptography Workshop (ECC ’98). FOR ECC. Slides available at http://www.cacr.math.uwaterloo.ca/, September 14-16, 1998. Field size d=1 d=2 d=4 d=8 ¨ u [5] G. Gaubatz, J.-P. Kaps, E. Ozt¨ rk, and B. Sunar. State of the Art in Ultra67 180 576 102 168 61 766 42 768 Low Power Public Key Cryptography for Wireless Sensor Networks. 71 201 600 113 400 68 040 45 360 In 2nd IEEE International Workshop on Pervasive Computing and 79 244 296 137 592 81 432 53 352 Communication Security (PerSec 2005), Kauai Island, Hawaii, March 83 271 584 150552 88 560 59 040 2005. [6] A. Hodjat, L. Batina, D. Hwang, and I. Verbauwhede. HW/SW Codesign of a Hyperelliptic Curve Cryptosystem using a ?Code Instruction Set Coprocessor. Elsevier Science Integration the VLSI Journal, 40(1):45–51, 2006. 210 ms for the best case of ECC over F267?2 (d = 8) and 546 [7] N. Koblitz. A family of Jacobians suitable for Discrete Log Cryptosys67 and d = 8). Our results ms for the best case of HECC (F2 tems. In S. Goldwasser, editor, Advances in Cryptology: Proceedings of are compared with other related work in Table V. CRYPTO’88, number 403 in Lecture Notes in Computer Science, pages 94–99. Springer-Verlag, 1988. [8] S. Kumar and C. Paar. Are standards compliant elliptic curve cryptosysTABLE V tems feasible on RFID? In Proceedings of Workshop on RFID Security, page 19, Graz, Austria, July 2006. C OMPARISON WITH OTHER RELATED WORK . [9] J. L? pez and R. Dahab. Fast multiplication on elliptic curves over o GF(2m ). In C. K. Koc and C. Paar, editors, Proceedings of 1st ? ? International Workshop on Cryptographic Hardware and Embedded Ref. bits A [gates] Tech. [?m] f [kHz] t [ms] P [?W ] Systems (CHES), volume 1717 of Lecture Notes in Computer Science, [8] 131 11 969.93 0.35 13 560 18 pages 316–327. Springer-Verlag, 1999. [5] 100 18 720 0.13 500 410.45 < 400 [10] A. Menezes, Y.-H. Wu, and R. Zuccherato. An Elementary Introduction [12] 192 23 000 0.35 68 500 9.89 n.a. to Hyperelliptic Curves - Appendix, pages 155–178. Springer-Verlag, [1] 131 8104 0.13 500 115 < 30 1998. N. Koblitz: Algebraic Aspects of Cryptography. ECC 134 6103 0.13 200 210 < 13 HECC 134 7652 0.13 200 546 < 17 [11] P. Montgomery. Speeding the Pollard and Elliptic Curve Methods of Factorization. Mathematics of Computation, Vol. 48:243–264, 1987. [12] J. Wolkerstorfer. Scaling ECC Hardware to a Minimum. In ECRYPT workshop - Cryptographic Advances in Secure Hardware - CRASH 2005, September 6-7 2005. invited talk. We underline again that our results for the area complexity
Dig
0

it s

4

ize

Dig

it s

ize

6

1834


赞助商链接
更多相关文档:

2011年12月A级试题及详解答案

the meeting room. D. He's away on business. ...Part Ⅲ Reading Comprehension The key to any ..., is like going through the eye of a needle....

THE DARNING-NEEDLE

Laser Needle Guide for t... 8页 免费 Public-key cryptography ... 4页 ..."Now I am going on a journey," said the needle, as she floated away ...

11.-Lady-in-the-Dark

stopped at the top of the steps and pulled her...on a plate on the door he could read “Mrs....was still playing with a long knitting needle. ...

信息安全英语复习范围(附目录)

公钥加密 (学生翻译)Public key cryptography is a form of cryptography which ...Depending on the packet and the criteria, the firewall can drop the ...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com