A Dual-Field Algorithm For Elliptic Curve Cryptosystem And Its Hardware Implementation

the same function, but ECC has more technology advantages, so it has been used wider and wider. At the same time, the research of ECC has attracted a lot of attention. In this paper, we improve the Algorithm of ECC and present a new Dual-Field ECC algorithm which supports both Galois fields GF(p) and GF(2m) for arbitrary prime numbers and irreducible polynomials. An arithmetic unit is also designs, which can do the Galois field arithmetic operations of addition, subtraction, multiplication, squaring, inversion and division. After the design and innovate work of ECC algorithm we discuss the hardware implementation. As the kernel operation of ECC, the point multiplication is the focus point of the hardware implementation. The module of point multiplication is divided into 3 levels, the first level is point multiplication module, the second level is AD (addition and double) module, and the last level is Galois field arithmetic module. Then we can improve every module respectively.In this paper, we present three innovations during the whole work:1. We extend the function of the ECC circuit. Galois field arithmetic module is the most important part of the ECC circuit, which can support the point multiplication operation of both Galois fields GF(p) and GF(2m) and all kinds of Galois field arithmetic operations, such as addition, subtraction, multiplication, squaring, inversion and division. The Galois field arithmetic module can not only been used for ECC, but also been used for RSA.2. A new Dual-Field ECC Algorithm is proposed. The new Dual-Field ECC Algorithm can support Galois fields GF(p) and GF(2m) and is suitable for hardware implementation3. We present a new construction of ECC point multiplication module originally, which is divided into 3 levels module.After the work of algorithm design and circuit design, we emulate and test the ECC circuit. We achieve both VLSI implementation and FPGA implementation of the new Dual-Field ECC algorithm. The VLSI implementation using 0.18-μm CMOS standard cell library of SMIC puts the emphasis on the test of the algorithm improvement, and then the circuit has also been implemented on a Xilinx Virtex2 FPGA to test the innovation of ECC circuit construction. The FPGA implementation results of the ECC over 163-bit Galois fields are shown in this paper, which achieve a point multiplication time of 4.23ms at 70MHz over GF(p) and 2.29ms at 70MHz over GF(2m). As the implementation and comparison results show, the proposed structure has strong advantages in function, speed and area. The emulation and test results show that the improvements and innovations of the algorithm and circuit structure are successful.