• 検索結果がありません。

楕円曲線暗号向け GF(2m) 上の Digit-Serial 乗算器の設計

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2021

シェア "楕円曲線暗号向け GF(2m) 上の Digit-Serial 乗算器の設計"

Copied!
6
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 6 ページ )

全文

(1)2007- s ldm-128 (5 >. IPSJ SIG Technical Reports. 2007/1/17. flfR ftJlftBt-tlRl ^ GF(2m) ±<D Digit-Serial. T 169-8555 JlaKf&3|PH§E:*A{R 3-4-1 Tel: 03-3209-3211(5716), Fax: 03-3204-4875. T 808-0135 SI^Wb^>NT|T*feEt>^t (0 2-7 Tel: 093-692-5017, Fax:093-692-5021. E-mail: [email protected]. GF(2m)fcl:j8tt5 digit-serial*#$£«, bit-serial ***i£!iU fflk<D*v ai:SrliJ?»Lfc#ffi'T?*>5. *M"ett, MSB(most significant bit) ^*^^^<-^lC, digit-serial. MSD(most significant digit) m^^$rS^-r5. *^fe(i MSB 5k%%k* digit ^>T X D S. 0K^ ROHM0.35/xm T^n ^T?3ISS Lfc***, GF(2163) 1^43 »t 5«RRf-*§-Mig£ 50MHz Kft^^ft 0.115ms *—*?— K. GF(2m), digit-serial mW$s, MSB (most significant bit) mW$s,. MSD (most significant digit). GF(2m) Digit-Serial Multiplier for Elliptic Curve Cryptosystem Ryuta NARAt, Shunitsu KOHARAt, Kazunori SHIMIZUtt, Nozomu TOGAWA*, Takeshi IKENAGA+t, Masao YANAGISAWAt, Satoshi GOTO+t, and Tatsuo OHTSUKlt f Dept. of Computer Science, Waseda University 3-4-1 Okubo, Shinjuku, Tokyo 169-8555, Japan. Tel: +81-3-3209-3211(5716), Fax: +81-3-3204-4875 ft Grad. School of IPS, Waseda University 2-7 Hibikino, Wakamatsu, Kitakyushu, Pukuoka 808-0135, Japan Tel: +81-93-692-5017, Fax: +81-93-692-5021. E-mail: [email protected] Abstract. Digit serial multiplier for GF{2rn) is an architecture that increases throughput at one cycle by extending. multiplicand bits of a bit serial multiplier. In this paper, we propose an MSD (most significant digit) multiplier,. which is one of the digit serial multiplier, based on an MSB (most significant bit) multiplier. By connecting D (digit. size) pieces of MSB multipliers in series, our implementation is simpler, lower area and less clock-cycles than tradi tional methods. Implementing elliptic curve cryptosystem (ECC) using the proposal multiplier with ROHM 0.35/zm. technology, we achieved operation times of 0.115ms for EC scalar multiplication in GF(2163) at 50HMz. Key words. GF(2m), digit-serial multiplier, most significant bit (MSB) multiplier , most significant digit (MSD). multiplier, elliptic curve cryptosystem, public key cryptosystem. -25-.

(2) 1.. £ 7L tf #. RSA Hgf-§-[8] 160 try ]-•?<&££&# RSA Bf^(D &&1024. ztb, rsa. Input: ^ = E^o1 ai2i'ai € C7F(2) Input: B = J^iZi BiZDi, where B{ is as in (1). GF(p) £ 2 <£>&*:#: GF(2m) #*>*. GF(2m) ttflUM* XOR. Output: S = A ■ Bmodf(z). f(z) = zm+ E^p1 c^,where a e GF(2) 1: 5*- 0. 2: for i = \m/D] - 1 to 0 do 2.1: S <r- A-Bi + S. 2.2: S <r-S-zD mod /(*) 3: Return(S). , bit-serial M^ m ^W -^^ tfc MSD. 2.. digit-serial. GF(2m) Oli A ir B t L,. 5 = A • £ mod /(*). digit-serial HIFtt bi m \fy hXlt' . digit. bit-serial T^^il XA [2]. £>6. bit-serial. , bit-serial. -<1V4?. frb&mtz, MSB ^^T/U-^y XASrBI 1 \Z. -fit digit-serial Tfrz* ]) X'A [3] , digit ©»tt d = \m/D]. -5 [10].. ^ Ji^: (1). IHfUt Redution SB^^ (1). tb bit-serial ^«t. bit-serial. £ L/c most signif. icant digit first (MSD). . MSB ^^^^ £> . MSB. o \Z. 1. h */y. ,. most. significant bit first (MSB). digit-serial. msd. 3.. Reduction. D t. . Reduction. . 2 |£-m digit-seria. -26-.

(3) Input: A = E^o1 «<*'.** € GF(2). Input: B = Eto B{zD\ where B» is as in (1) Output: S = A ■ £mod/(z). /(*) = zm + E^o1 cj^,where c» € GF(2) 1: 5<-0. 2: for i = [W^l - 1 to 0 do 2.1: for j = D - 1 to 0 do. 2.1.1: S <^ A-{Bi)j +S. 2.1.2: if(i == 0 and j == m%D) Return(S). 2.1.3: S^S-z mod /(z). HI 3. SH MSD-first 7^=*" ]) XA.. Redution m*#t> Reduction. 13 {C^|^ digit-serial. 2.1 (7) for ;U—^fflJift* MSB-first M^Il Reduction ^^^r digit f"^ X D r t tikMir >.. m=163, D=4 <D. S=AB mod Kx) HI 4. (GF(2163),D = 3).. &£ MSD-first. abed. abed. (a). (b). (-, m=163, L>=21,22,. cJ6 D=21. 5. XOR y- h <O^3t (a) T U-f M (b)2 #*§!.. 3.1. «9 It D \Ctt-tZ tit) Si(i e {0,1,.... to - 1}). Reduction. XOR ^-. Accumulator ffl-C*fiK$ <O A k D \?y b<DBi k. XOR y-. . Reduction ^^ Srt? 5 XOR y-. kD kftZ. ffi (to. 6. aibj I* AND Xft%-tZ>&, «#0i«li^V^t? AND yh 1 o^O^iJiT'^ti'. XOR y- Hit MSB ^JlS&afe^fc. yir«tt?fijgjitt digit f-^ x d \zttm lt«*p it t * 5 #, HI 5 \Z7Jk-t-3: 0 \z. XOR <DT isjm&t: 2 ^^tl^ tzbb XOR y-. *5. Accumulator IfUtt m 3 ^. msb. 4. NIST. ~fi [1] (fc. STARC90nm. -27-.

(4) X-♦♦♦.. 120000. 100000. 80000 }. 0. I 60000. 20. 80. 40. 100. 120. 140. 160. 180. digit size D. I. I 8. 40000. digit t^fX. 20000. 0. 0. 20. 40. 80. 100. 120. 140. 160. 180. digit sizeD. I 6. digit 1M X D. 5.. m. m. ROHM0.35/im "f o -fe ^ ffl 7 -f ^ 7 V. tz. 7^7*7!) f^fifett Synopsys Milky way X-2005.09, ifiiH^te: Synopsys Astro X-2005.09, DRC/LVS \M Mentor. Calibre te^tl^tlfelft Ltz. NIST^iH^^^*-^ [1] (C^^5. i^fd GF(2163) ±OtlRft^?rfflV>/c. ^^7 7—^^ (Q = kP). 50. 100. , digit. 150. digit size D. I 7. digit t^XD. io j^i-. * 4 ^ t. STARC90nm. DesignComplier W-2004.12-. Nph fe.. = *p) zm 0.115ms t?. digit. MSB JH@: MSB ^^. IrI±1-5*5. ,21 t'. ROHM0.35/im. -28-.

(5) -29-.

(6) *. *. it. [1]. /^^£? Standard Specifications for Public-Key Cryptography,. [2]. T. Beth and D. Gollmann, "Algorithm engineering for pub. IEEE Std. 1363-2000.. lic key algorithms." IEEE Journal on Selected Areas in Communications, vol. 7, pp. 458-465, 1989.. [3]. R.I. Hartley and K.K. Parhi, Digit-Serial Computation, Kluwer Academic Publishers, 1995.. [4]. N. Koblitz, "Elliptic Curve Cryptosystems," Math. Compu. [5]. S. Kumar, T. Wollinger and C. Paar, "Optimum Digit Serial. tation, vol. 48, pp. 203-209, 1987.. GF(2m) Multipliers for Curve-Based Cryptography," IEEE TRANSACTIONS ON COMPUTERS, vol. 55, no. 10, pp. 1306-1311, Oct. 2006.. [6]. J. Lopez and R. Dahab,. "Fast multiplication on ellip. tic curves over GF(2m) without precomputation,". Cryp. tographic Hardware and Embedded Systems - CHES'99, Springer-Verlag, Lecture Notes in Computer Science 1717, pp. 316-327, August, 1999.. [7]. V. Miller, "Uses of Elliptic Curves in Cryptography," Ad vances in Cryptology, Proc. CRYPTO '85, H.C. Williams, ed., pp. 417-426, 1986.. [8]. R.L. Rivest, A. Shamir and L. Adleman, "A Method for Ob taining Digital Signatures and Public-Key Cryptosystems," Comm. ACMt vol. 21, no. 2, pp. 120-126, Feb. 1978.. [9]. A. Satoh and K. Tfckano, "A Scalable Dual-Field EUiptic Curve Cryptographic Processor," IEEE TRANSACTIONS ON COMPUTERS, vol. 52, no. 4, pp. 449-460, April, 2003.. [10]. L. Song and K.K. Parhi, "Low Energy Digit-Serial/Parallel Finite Field Multipliers," J. VLSI Signal Processing, vol. 19, no. 2, pp. 149-166, June. 1998.. -30-.

(7)

参照

今ダウンロードする ( PDF - 6 ページ - 446.18 KB )

関連したドキュメント

The signs in elliptic nets

We also describe applications of this theorem in the study of the distribution of the signs in elliptic nets and generating elliptic nets using the denominators of the

Concentration phenomena in weakly coupled elliptic systems with critical growth*

Here we are interested in studying the weakly coupled system ( 1. 1 ) in the critical case. In particular we want to find solutions which concentrate in some points of in the sense

Journal of Inequalities in Pure and Applied Mathematics

A lemma of considerable generality is proved from which one can obtain inequali- ties of Popoviciu’s type involving norms in a Banach space and Gram determinants.. Key words

SEMILINEAR ELLIPTIC EQUATIONS IN BOUNDED DOMAINS

In many semilinear elliptic problems including small parameters (e.g., semilinear elliptic equations involving the critical exponent [10], stationary Cahn- Hilliard equation

Minimal Digit Sets for Parallel Addition in Non-Standard Numeration Systems

We study parallel algorithms for addition of numbers having finite representation in a positional numeration system defined by a base β in C and a finite digit set A of

Journal of Inequalities in Pure and Applied Mathematics

de la CAL, Using stochastic processes for studying Bernstein-type operators, Proceedings of the Second International Conference in Functional Analysis and Approximation The-

Journal of Inequalities in Pure and Applied Mathematics

[3] JI-CHANG KUANG, Applied Inequalities, 2nd edition, Hunan Education Press, Changsha, China, 1993J. FINK, Classical and New Inequalities in Analysis, Kluwer Academic

(joint work w/ I. Fesenko, Y. Hoshi, S. Mochizuki, and W. Porowski)

Goal of this joint work: Under certain conditions, we prove ( ∗ ) directly [i.e., without applying the theory of noncritical Belyi maps] to compute the constant “C(d, ϵ)”