High Speed FPGA Based Dual Field Elliptic Curve Cryptography Using Mixed Coordinates

High Speed FPGA Based Dual Field Elliptic Curve Cryptography Using Mixed Coordinates

Pallavi. B,

M.Tech 4th SEM Student

1. Institute of Technology, Digital Communication and Networking, Bangalore, India

   Abstract Cryptography has become a crucial issue to ensure the security of transmitted data. Elliptic Curve Cryptography is asymmetric key cryptography. In this paper, we can perform either prime field G (p) operations or binary field G (2m) operations for arbitrary prime numbers. Using this architecture we can achieve the high through put of both fields that is prime and binary fields.

   Keywords Elliptic Curve Cryptography, Prime field, Binary field, Processor

   1. INTRODUCTION

      Strength of R.S.A lies in integer factorisation problem. Elliptic curve is a curve that is a group. The dis advantage of

      R.S.A is the use of large numbers for its operation. Cryptography is used for confidentiality, authentication, data integrity, and non-repudiation. It is divided into two types: secret key and public key cryptography. Public Secret-key cryptography is mainly used in key management, authentication, signatures and certificates. The main dis advantage in public key cryptography is its key size is large to meet the requirements. ECC is one of the public key cryptography algorithms.

   2. INTRODUCTION TO ECC

      1. Basics of ECC

         The use of elliptic curves was introduced in 1985. Point addition and Point doubling are the main features of ECC. Its attractive feature is lesser key size. Elliptic curves are not ellipses. In general cubic equations for elliptic curves take the form which is givenby the below equation.

         y2=x3+ax+b. (1)

         We also have O (point of infinity). To plot such a curve we need to compute

         y= 3 + + (2)

         Fig1: Elliptic curve of y2= x3-3x+5

         There are 2 types of fields of interest

         • Prime field

         • Binary field

      2. Elliptic Curve Discrete Logarithmic Problem

         It has the following components

         • A well-defined finite field GF(p) or GF(2m)

         • Point P of higher field present on elliptic curve E

         • A scalar multiple of P lets say k such that k.P = P+P+P++P (k times)

      3. Advantages of ECC

         The following are some of the advantages of ECC

         • Solving Q = KP is more difficult than factorisation used by R.S.A

         • Different finite fields can be used for ECC according to security requirements.

         • ECCrequires less power and hence its used in mobile devices and wireless applications.

         • Implementing scalar multiplication in software and hardware is feasible.

   3. APPLICATION OF ECC: DIFFIE HELMANN KEY EXCHANGE

      According to the figure shown in the left the order n of a point G in an ellipse is the smallest positive integer. The key exchange is given by the following steps

      • A selects an integer nA less than n. This is As private key and A generates public key PA which is given by nA X G.

      • B computes PB = nB X G

      • A generates secret key K = nA X PB and B also generates the key K = nB X PA.

   4. OPERATIONS ON ECC

      1. Point Addition

         To add two distinct points P and Q on an elliptic curve shown below draw a straight line between them. The line will intersect the curve at one more point R. Reflection of R with respect to x axis gives the point R.

         Fig2: Point Addition

      2. Point Doubling

         To the point P on elliptic curve draw the tangent line to the elliptic curve at P.The line intersects the elliptic curve at the point R. The reflection of the point R with respect to x-axis gives the point R which is the result of doubling of point P.

         Fig3: Point Doubling

      3. Abelian Groups

         1. Closure : if a and b belong to G, then a.b is also in G

         2. Associative: a.(b.c) =(a.b).c for all a,b,c in G

         3. Commutative : a.b= b.a for all a.b in G

         4. Identity: a.e=e.a =a for all a in G

      4. Rules of addition

      • P+O=P ( In case of prime fields)

      • If P = (xp, yp) then P + (xp, -yp)=O. The point (xp, -yp) is called negative of point P.

        • P+O=P ( In case of binary field)

      • If P = (xp, yp) then P + (xp, xp+yp) = O. The point (xp, xp+yp) is called negative of point P.

      Fig4: elliptic curve E23 (1, 1)

      Fig5: Points on E23 (1, 1)

      Elliptical Curve Cryptography Hierarchical model

      Fig6: elliptic curve Diffie Helmann exchange

      In figure 6 client and server choose kC and kS. Client computes QC using ECC scalar multiplication (multiplying KC by point P). Server computes QS = (KS X P). Client transfers QC to client and QS to server. Client receives QS and multiplies it by KC. Server multiplies QC by KS.

      Hardware implementation of ECC passes through 3 main levels. As shown in figure 6 Galois field arithmetic includes field multiplication, addition, squaring and inversion. Elliptic curve arithmetic includes point addition and point doubling. Elliptical curve main operation is scalar multiplication.

      F. Dual field Processor Architecture

      The dual field architecture has input/output buffers, control unit register files. Data is fed into the input buffer and read out from the output buffer though I/O interface. Control instructions are stored in the control register and they are decoded by the main controller. Karatsuba multiplier is used to perform point addition and point doubling. All the results of the computation are stored in register files.

   5. FUNCTIONAL BLOCK DIAGRAM

      Fig7: ECC Modular Multiplier Fig8: Block diagram of ECC Processor chip

      ECC Modular Multiplier consists of Control Unit, Arithmetic Unit and output register. Control Unit decodes the 4 256 bit instructions and sends them to the Arithmetic unit which is performing adding and doubling operations.

      ECC Processor chip contains AHB interface, Main Controller, Clock Controller, ECC data selector, Input and Output Buffers. Data selector fetches instructions from main controller and decodes them to the multiplier unit. Clock control unit is required to compute the cycles required for scalar multiplication. Modular multiplier performs point addition, point doubling and scalar multiplication. Montgomery unit consists of Montgomery Scheduler and Data selector. Data scheduler fetches instructions input values from input buffer. Input values are prime field or binary field. During the computation we get some intermediate values and they are stored in register files.

   6. IMPLEMENTATION

      We have presented the dual field ECC architecture which is scalable for different field sizes (163 bit for binary field, 192 bit for prime field. Dual field multipliers and adders perform arithmetic over both fields (prime and binary field). Coding is done in Verilog HDL.

      Multiplication and squaring is done in Vedic Mathematics. Addition is done in normal method. We use Xilinx 12.1 Tool for the design and testing of point addition and point doubling. Code is written and simulation and synthesis results are tested.

   7. SYNTHESIS RESULTS

      In this section we are presenting synthesis results for point addition, point doubling, and scalar multiplication (using Mixed

      Coordinates) for both 163 bit binary and 192 bit prime field.

      No. of Bits	Delay(ns)
      192	65.884
      163	40.691

      No. of Bits	Delay(ns)
      192	56.558
      163	34.086

      Table1: Synthesis Result of point addition Table3: Synthesis Result of Point Doubling

      No. of Bits	Delay(ns)
      192	48.439
      163	21.708

      Table2: synthesis result of scalar multiplication

   8. SIMULATION RESULTS

      The below results are shown for point addition, point doubling for binary and prime field

      Fig9: Point Addition for 163 bits

      Fig10: Point doubling for 163 bits

      Fig11: Point addition for 192 bits (prime field)

      Fig12: Point doubling for 192 bits (prime field)

      Fig13: Scalar Multiplication for 192 bits (prime field)

      Fig14: Scalar Multiplication for 163 bits (binary field)

   9. CONCLUSION

We have presented dual field coprocessor with mixed coordinates. Our processor can be used for both binary field and prime field. In order to speed up the time required for multiplication we have adopted Karatsuba multiplier and

REFERENCES

1. Samish, Ashraf, Hardware implementation of efficient modified Karatsuba multiplier used in elliptic curves, International journal of Network Security (2010)

2. William, Fast elliptic curve Cryptography on FPGA, IEEE Transactions on VLSI, Vol.16.No.2, February 2008.

3. B.Muthu Kumar, S.Jeevanathan,High Speed Hardware Implementation of Elliptic Curve Cryptographic Processor, IEEE, 2010.

4. B. Ansari and M. A. Hasan, High-performance architecture of

   Montgomery multiplier. Addition and Subtraction is done in normal method. Multiplication and squaring is done using Vedic maths. Scalar multiplication for both prime and binary fields is implemented in Xilinx platform. Synthesis results show that our design has high throughput and power Efficiency.

   elliptic curve scalar multiplication IEEE Trans. Computers, vol. 57,

   no. 11,pp. 11431153, Nov. 2008.

5. J.-Y. Lai and C.-T. Huang, Energy-Adaptive Dual-Field Processor for High-Performance Elliptic Curve Cryptographic Applications IEEE Trans. On (VLSI) systems. Vol 56, no. 4, pp.356-360, March 2010.