A Reconfigurable Modular Arithmetic Unit for Public-key

A Reconfigurable Modular Arithmetic Unit for Public-key Cryptography Tao Chen*, Bin Yu, Jin-Hai Su, Zi-bin Dai, Jian-Guo Liu Institute of Electronic Technology, the PLA Information Engineering University, Zhengzhou 450004, P.R. China *Email: chentaoic@yahoo.com.cn Abstract This paper analyzes the reconfigurable design principles of public-key cryptography and the characteristics of modular arithmetic iteration process. According to the analysis results, a structure-adaptive reconfigurable modular arithmetic unit for Public-key cryptography is implemented, which architecture is able to support both RSA and ECC(Fp) algorithms security parameters dynamic arbitrary changing. Based on 0.18 micrometer standard cell-library, the area of the chip is only 42000ȝm2ˊSimulation results of post-synthesis indicate that the maximum operating clock frequency is 103.8 MHz, the 1024-bit RSA modular exponential operation period is about 45ms, and the 192-bit ECC(Fp) point multiplication period is 17ms on average. Key words: Public-key cryptography˗Reconfigurable computing˗Modular arithmetic˗RSA˗ECC˗ 1. Introduction Public-key cryptography is widely used in providing privacy, integrality and non-repudiation of information. Public-key cryptography is disunity in various security application fields, and both RSA[1] and elliptic curve cryptography (ECC) [2,3] are two most popular public-key cryptosystems now. The security of RSA depends on the difficulty of factoring large integer problem, and RSA can be used for both data encryption and digital signature; the security of ECC is based on the elliptic curve discrete logarithm problem (ECDLP), and ECC has quite security intensity that can satisfy practical demands with shorter key length. There are two kinds of ECC algorithms according to the difference of elliptic curve finite field selected, i.e. F(p) based on prime field and F(2m) based on characteristic value 2. The basic operation of both RSA and ECC(F(p)) algorithms are modular operation in integer field, and the parameters involved in are all large integers (such as 1024-bit for typical RSA and 192-bit for typical ECC in F(p)), so that much more time is required for implementing modular operation. Due to the unfitness structure in implementing these algorithms, it is hard to satisfy the demands of practical application based on general microprocessor; meanwhile problems such as the singularity of the customizing handling architecture, non-removable parameters, narrow application and high price of repeated design etc. will be introduced by specific hardware implementation. In order to satisfy various application security demands, a reconfigurable modular arithmetic unit (RMAU), based on reconfigurable computation idea[4], was proposed for adapting abroad to public-key cryptography in this paper. The RMAU can satisfy security parameters alterable demands of both RSA and ECC(F(p)) algorithms with better performance and in smaller area. 2. Public-Key Cryptography Reconfigurable Design Principles Research Analyzing the operations involved in RSA and ECC(Fp) level by level, we can see that the common operations of public-key cryptography algorithms can be divided into three levels from function: application operation layer, extended operation layer and basic operation layer. Application operation layer includes at least 4 kinds of cryptographic application operations: prime number filter, key generation, digital signature and identity certificate. These application operations can be implemented by many kinds of algorithms, but they can be translated into iteration scheduling of the operations on extended operation layer, especial for modular arithmetic operations (including modular exponentiation, modular multiplication and modular addition). Further analysis indicates that the extended operation layer includes 9 kinds of arithmetic operations: multiplication, square, division, extraction, modular addition, modular addition inversion, modular multiplication, modular exponentiation and modular multiplication inversion, in which the most core operations are modular exponentiation, modular multiplication, modular addition and modular addition inversion. (1) Modular exponentiation arithmetic operation To compute modular exponentiation arithmetic operation CDmod N given the integers C,D and N, we can scan the bits of D from the most significant to the least significant and schedule modular multiplication to execute operation C’=(Ch1)mod N when the first ‘1’ is 1-4244-1132-7/07/$25.00 © 2007 IEEE 850 scanned, and from then a modular multiplication schedule C’=(C’hC’)mod N is performed for each bit and continue to schedule a modular multiplication operation to perform C’=(C’hC)mod N only if the bit is ‘1’. (2) Modular multiplication arithmetic operation To compute modular multiplication arithmetic operation (AhB)mod N given the integers A,B and N, we can scan the bits of B from the most significant to the least significant and schedule modular addition to execute operation C=(Ah1)mod N when the first ‘1’ is scanned, and from then a modular addition schedule C'=(C+C)mod N is performed for each bit and continue to schedule a modular multiplication operation to perform C=(C+A)mod N only if the bit is ‘1’. (3) Modular addition arithmetic operation The modular addition arithmetic operation is to compute (A+B) mod N given the integers A,B and N, and usually A and B are nonnegative integers with A,BN. When the sizes of the operands A, B and N exceed that of basic arithmetic unit, using modular addition operation instruction controls iteration to implement large integer modular addition operation. (4) Modular addition inversion arithmetic operation To compute A-1 according to A+A-1mod N˙0. a) Compute T=N-A; b) If T<0, then compute T=T+N till T>0; c) Let A-1˙T. From the depicting of the modular operations process above, it can be seen that large number modular arithmetic operation can be unitarily implemented by large number modular addition operation such as modular exponentiation, modular multiplication, modular multiplication inversion, modular addition and modular addition inversion etc, and the core operations of modular addition are addition and subtraction on basic operation layer; moreover, other extended operations, such as multiplication, squaring, division and extraction etc., can be implemented similarly by scheduling basic addition/subtraction arithmetic operations. 3. RMAU Design 3.1 Design Idea On the one hand, the complex functions of public-key cryptography can be translated into iteration of a certain word-length modular arithmetic operation whose core operation is large number modular addition operation (A+B) mod N, so that the implementation can use similar program schedule method based on general microprocessor to ensure public-key cryptography to arbitrary choose security parameters, such as modulus length of RSA, field value of ECC(Fp) and so on; On the other hand , from the realization point of view, the basic processing unit usually uses 7 kinds of operand word-length standards that are 32-bit, 64-bit, 128-bit, 256-bit, 512-bit, 1024-bit and 2048-bit respectively. To select rational operand word-length and to design specially according to modular operation characteristic, it can be worked out that general microprocessor processes modular operation ability to be low due to limiting 32-bit word-length. Considering all the modular operations can be translated into extended operation whose core operation is large modular addition arithmetic, therefore, the agent structure of the RMAU is the large number modular addition circuit; The other modular operations of extended operation layer can use program schedule method to schedule basic modular addition circuit to realize computation; The application layer operation can schedule basic arithmetic instruction and extended operation program to realize; For the purpose of further balancing speed and resource, subtraction can be implemented by 128-bit subtracter through iteration scheduling. 3.2 Overall Framework The overall framework of RMAU is made up of two parts, one part is used for realizing basic large number modular arithmetic operation including two serial 128-bit reconfigurable basic arithmetic operation units; and the other part is used for the circuit function dynamic control including a input data multiplexer (MUX1~2) and output data multiplexer (MUX3). Figure 1 shows the overall framework of RMAU: MUX1 MUX2 128bit reconfigurable add/sub areithmetic unit 128bit reconfigurable subtractor areithmetic unit MUX3 A B CICO BO Output[127˖0] BI C Figure1. RMAU overall Framework 851 The two 128-bit basic arithmetic series unit is the core of RMAU. The first 128-bit adder/subtracter is designed for implementing addition/subtraction arithmetic within 128-bit operands while it supports iteration operation with 128-bit upwards standards operands; the second 128-bit single subtracter is used to implement subtraction arithmetic within 128-bit operands and supports multiple cycles iteration subtraction with 128-bit upwards standards operands. By the serial way, the operation (A+B) mod N can be implemented with not more than two classes 128-bit full adder combinational logic delay, and the output result has two possibility: A+B or A+B-N. The input data multiplexer (MUX1~2) are two dynamic controllable nodes for controlling data input. By applying different control signal to the two controllable nodes, it can be select to realize five functions as A+A, A+B, B+B, A-B and B-A; The output data multiplexer (MUX3) is another dynamic controllable node of RMAU in taking charge of output control for the modular operation result data A+B or A+B-N, and it is controlled by carry and borrow signal CO, BO together. For the core modular addition operation of large number modular arithmetic, this kind of two 128bit basic arithmetic unit cascade architecture builds a good relation between the large number modular arithmetic algorithm and the hardware circuit in primary. To meet others more complex function demands of public-key cryptography, a fine granularity basic arithmetic unit reconfigurable circuit architecture designing is in need. 3.3 Basic arithmetic unit reconfigurable design 128-bit adder/subtracter reconfigurable structure as Figure 2 shows, M U X 3 64bit add/sub unit CI M U X 2 32bit add/sub unit 32bit add/sub unit CI Output[127:64] CO128 /CI64D CI64S/ CI32D CI32S R EG 3 R EG 2 R EG 1 M U X 1 Output[63:32] Output[31:0] R3 R2 R1 R3 R2 A/S_3 A/S_2 A/S_1 A[127:64] A[63:32] A[31:0] B[127:64] B[63:32] B[31:0] CO 0 0 0 Figure 2. 128-bit add/sub reconfigurable unit The circuit core structures are made up of two 32-bit adder/subtracter, a 64-bit adder/subtracter and three carry/borrow registers. There are two kinds of classes and each class has three dynamic controllable nodes in this circuit. The first one is addition/subtraction mode switching nodes, which are controlled by signals A/S_1~3 administrating the adder/subtracter mode dynamic switch; The second one are mode data selecting nodes MUX1~3, which have the 128-bit adder/subtracter dynamically supported six kinds of standard basic operation modes such as 32-bit single/double, 64-bit single/double, 128-bit and extended 128-bit etc. The second class dynamic node detailed function designs as Table 1. Table 1 The detailed functions of class II Node Mode MUX1 output MUX2 output MUX3 output CI/BI R1 / / 32bit N 0 / / CI/BI R1 R2 / Double 32bit N 0 0 / CI/BI R2 CI32S / 64bit N 0 CI32S / CI/BI R2 CI32S R3 Double 64bit N 0 CI32S 0 CI/BI R3 CI32S CI64S128bit N 0 CI32S CI64S Extended 128bit CI/BI R3 CI32S CI64S REG1~3 are all designed as one-bit registers for carry or borrow signals automatic saving in every add/sub operation period, whether they join the modular operation are decided by dynamic control nodes MUX1~3: If not, the output data of MUX1~3 will be always 0, otherwise the input carry or borrow signal of MUX1~3 will be choose according to various algorithm functions. Moreover, REG1~3 are main judging conditions of modular operations results output, so that we can regard them as Symbol-Register by controlling them through specific instructions “clear” and “set” . If both two kinds of dynamic nodes worked together, especially with the help of carry and borrow registers, the basic arithmetic unit can accomplish 6 kinds of specification 22 basic add and subtract operations within 5 control information bits. Considering the 128-bit subtracter structure is similar to the 128-bit adder/subtracter, this paper will not depict it any more, at the same time, restricted by the content and the paper length, the specific instruction set of RMAU will be described in another paper. 4. Synthesis and Validation The reconfigurable modular arithmetic unit is implemented in 0.18-ȝm CMOS technology. They are described in Verilog HDL and synthesized by Synopsys 852 Design Compiler. The RMAU is synthesized under the condition that “TYPICAL” operating condition, “reference_area_10000” wire-load, 1.0ns clock constraint and ‘0’ max-area. The max frequency, critical path delay and the area are listed in table 2. Table 2. Performance of RMAU Frequency(MHz) Max Delay(ns) Area(ȝm2) 103.8 9.63 42168 The maximum operating clock frequency is 103.8MHz, according to post layout simulation. At this clock frequency, the 1024-bit RSA modular exponential operation period is about 45ms, and the 192-bit ECC(Fp) point multiplication operation consumes almost 17ms. In comparison with many other conventional implementations of Public-key cryptography, which are listed in table 3, the core circuit of our design contains only 4000 gates. The drawback of the multiplier approach is a significant increase in area consumption, and our architecture shows the least area consumption of modular scalar operations in both RSA and ECC prime fields, however, the modular adder architecture brings about much more clock cycles in processing modular operations unavoidably. Table3. Hardware Performance Comparison Reference Platform Architecture Frequency Kgates Mode Time 192bit ECC(Fp) 60 ms [5] 0.35-ȝm CMOS 32bit modular multiplier 25MHz 26 1024bit RSA 170 ms 192bit ECC(Fp) 1.44 ms [6] 0.13-ȝm CMOS 64bit multiplier 137.7MHz 117.5 160bit ECC(F2n) 0.19 ms 256bit mult 5.75ȝs [7] Virtex-II XC2V2000-6 two 259-bit carry-propagate adders in series 44.91MHz 5,267 slices 1033bit mult 23.07ȝs 192bit ECC(Fp) 17 ms Proposed 0.18-ȝm CMOS 128-bit Modular adder 103.8MHz 4 1024bit RSA 45 ms 5. Conclusions In this paper, to meet various security demands of public-key cryptosystem’s practical application, based on analyzing the characteristics of the large number modular operation for public-key cryptography, a large number modular arithmetic unit is proposed. The proposed architecture can realize 6 kinds of public-key cryptography basic operations, 9 kinds of extended operations and more than 4 kinds of application layer operations. Test verification results show that the design can support dynamic circuit reconfiguration with small area and good performance, which enables both RSA and ECC(Fp) algorithms security parameters dynamic arbitrary changing. References [1] R. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signature and public-key cryptosystem, Communications of the ACM, Vol.21, pp.120-126(1978). [2] N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation. Vol.48, pp.203-208 (1987). [3] V. S. Miller. Use of elliptic curves in cryptography, in CRYPTO’85, pp.417-426(1986). [4] G. Estrin et al, Parallel Processing in a Restructurable Computer System, IEEE Transactions on Electronic Computers, pp.747-755 (1963). [5] WU Xingjun et al, A Modular Processor for Multi Public-Key Cryptography, Microelectronics, Vol.35, No.5, pp.550-552(2005). [6] A. Satoh, K. Takano, A Scalable Dual-Field Elliptic Curve Cryptographic Processor, IEEE Transactions on Computers, Vol. 52, No.4, pp.449-460(2003). [7] F. Crowe, A. Daly and W. Marnane, A Scalable Dual Mode Arithmetic Unit for Public Key Cryptosystems, Information Technology: Coding and Computing, 2005. ITCC 2005. International Conference on Vol.1, pp.568-573(2005) 853 << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Gray Gamma 2.2) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Warning /CompatibilityLevel 1.6 /CompressObjects /Off /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJDFFile false /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /LeaveColorUnchanged /DoThumbnails true /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams true /MaxSubsetPct 100 /Optimize false /OPM 0 /ParseDSCComments false /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo false /PreserveFlatness true /PreserveHalftoneInfo true /PreserveOPIComments false /PreserveOverprintSettings true /StartPage 1 /SubsetFonts false /TransferFunctionInfo /Remove /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true /Algerian /Arial-Black /Arial-BlackItalic /Arial-BoldItalicMT /Arial-BoldMT /Arial-ItalicMT /ArialMT /ArialNarrow /ArialNarrow-Bold /ArialNarrow-BoldItalic /ArialNarrow-Italic /ArialUnicodeMS /BaskOldFace /Batang /Bauhaus93 /BellMT /BellMTBold /BellMTItalic /BerlinSansFB-Bold /BerlinSansFBDemi-Bold /BerlinSansFB-Reg /BernardMT-Condensed /BodoniMTPosterCompressed /BookAntiqua /BookAntiqua-Bold /BookAntiqua-BoldItalic /BookAntiqua-Italic /BookmanOldStyle /BookmanOldStyle-Bold /BookmanOldStyle-BoldItalic /BookmanOldStyle-Italic /BookshelfSymbolSeven /BritannicBold /Broadway /BrushScriptMT /CalifornianFB-Bold /CalifornianFB-Italic /CalifornianFB-Reg /Centaur /Century /CenturyGothic /CenturyGothic-Bold /CenturyGothic-BoldItalic /CenturyGothic-Italic /CenturySchoolbook /CenturySchoolbook-Bold /CenturySchoolbook-BoldItalic /CenturySchoolbook-Italic /Chiller-Regular /ColonnaMT /ComicSansMS /ComicSansMS-Bold /CooperBlack /CourierNewPS-BoldItalicMT /CourierNewPS-BoldMT /CourierNewPS-ItalicMT /CourierNewPSMT /EstrangeloEdessa /FootlightMTLight /FreestyleScript-Regular /Garamond /Garamond-Bold /Garamond-Italic /Georgia /Georgia-Bold /Georgia-BoldItalic /Georgia-Italic /Haettenschweiler /HarlowSolid /Harrington /HighTowerText-Italic /HighTowerText-Reg /Impact /InformalRoman-Regular /Jokerman-Regular /JuiceITC-Regular /KristenITC-Regular /KuenstlerScript-Black /Kuenst