A State-of-the-art Elliptic Curve Cryptographic Processor Operating in the Frequency Domain

We propose a novel area/time efficient elliptic curve cryptography (ECC) processor architecture which performs all finite field arithmetic operations in the discrete Fourier domain. The proposed architecture utilizes a class of optimal extension fields (OEF) GF(q ^m ) where the field characteristic is a Mersenne prime q = 2 ⁿ  − 1 and m = n. The main advantage of our architecture is that it achieves extension field modular multiplication in the discrete Fourier domain with only a linear number of base field GF(q) multiplications in addition to a quadratic number of simpler operations such as addition and bitwise rotation. We achieve an area between 25k and 50k equivalent gates for the implementations over OEFs of size 169, 289 and 361 bits. With its low area and high speed, the proposed architecture is well suited for ECC in small device environments such as sensor networks. The work at hand presents the first hardware implementation of a frequency domain multiplier suitable for ECC and the first hardware implementation of ECC in the frequency domain.

点积加速器的设计与实现

提出了GF(2m)上的椭圆曲线点积加速器的一种有效的硬件设计,针对不同有限域GF(2m)及其上的椭圆曲线的特点,设计出较优的专用电路。此外,在控制器的设计中提出了一种新的方法—有限状态机的分解与合成,该方法灵活有效,且设计简单,尤其适合设计步进式状态机。最后,用Verilog HDL在FPGA上编程实现了GF(2193)上的点积加速器,计算一次点积仅需0.125ms,且通过重配置,可实现任何一个GF(2m)上的点积算术功能。     

Speeding up Scalar Multiplication in Genus 2 Hyperelliptic Curves with Efficient Endomorphisms

This paper proposes an efficient scalar multiplication algorithm for hyperelliptic curves, which is based on the idea that efficient endomorphisms can be used to speed up scalar multiplication. We first present a new Frobenius expansion method for special hyperelliptic curves that have Gallant‐Lambert‐Vanstone (GLV) endomorphisms. To compute kD for an integer k and a divisor D, we expand the integer k by the Frobenius endomorphism and the GLV endomorphism. We also present improved scalar multiplication algorithms that use the new expansion method. By our new expansion method, the number of divisor doublings in a scalar multiplication is reduced to a quarter, while the number of divisor additions is almost the same. Our experiments show that the overall throughputs of scalar multiplications are increased by 15.6 to 28.3 % over the previous algorithms when the algorithms are implemented over finite fields of odd characteristics.     

优化扩域上椭圆曲线标量乘的一个新算法

提出了一种优化扩域上椭圆曲线标量乘的新算法.算法基于Frobenius映射和二进制串的逻辑操作.文中对这个算法给出了细致精确的分析,而且在此基础上对新算法作了进一步改进.最后从理论分析和实际仿真两个方面就新算法和传统算法进行了比较.指出新算法执行时间比传统的φ-adic算法要少20%到40%.     

A Fast Diffie—Hellman Protocol in Genus 2

In this paper it is shown how the multiplication by M map on the Kummer surface of a curve of genus 2 defined over can be used to construct a Diffie—Hellman protocol. We show that this map can be computed using only additions and multiplications in . In particular we do not use any divisions, polynomial arithmetic, or square root functions in , hence this may be easier to implement than multiplication by M on the Jacobian. In addition we show that using the Kummer surface does not lead to any loss in security. Received 21 November 1996 and revised 28 March 1997     

Design and implementation of dual-field modular inversion algorithm

Modular inverse arithmetic plays an important role in elliptic curve cryptography. Based on the analysis of Montgomery modular inversion algorithm, this paper presents a new dual-field modular inversion algorithm, and a novel scalable and unified architecture for Montgomery inverse hardware in finite fields GF(p) and GF(2 ⁿ ) is proposed. Furthermore, this architecture based on the new modular inversion algorithm has been verified by modeling it in Verilog-HDL, and accomplished it under 0.18 μm CMOS technology. The result indicates that our work has better performance and flexibility than other works.     

GF(2n)域上的一种Ⅱ型优化正规基乘法器及其FPGA实现

有限域GF(2ⁿ)上的椭圆曲线密码体制以其密钥短,安全强度高的优点正在获得广泛的重视和应用.该密码体制最主要的运算是有限域上的乘法运算.本文提出了一种基于Ⅱ型优化正规基的乘法器,该乘法器具有Massey-Omura乘法器的优点,又避免了其不足,易于编程,适合FPGA实现.实验表明,该算法简单,快速.     

有限域GF (2m)上的一个新的求逆算法

根据有限域GF(2^m)上的正规基表示和Massey-Omura乘法器,本文提出了一个复杂性为O(logm)的求逆算法。新算法完成一次求逆运算只需要[log₂(m-1)]+w(m-1)-1次乘法和m-1次循环移位,这里[x]表示小于等于x的最大整数,w(m-1)表示m-1的二进制表示中“1”的个数。     

有限域GF(2~m)上的一个新的求逆算法

根据有限域GF(2~m)上的正规基表示和Massey-Omura乘法器,本文提出了一个复杂性为O(logm)的求逆算法。新算法完成一次求逆运算只需要[log22(m-1)]+w(m-1)-1次乘法和m-1次循环移位,这里[x]表示小于等于x的最大整数,w(m-1)表示m-1的二进制表示中“1”的个数。     

SIGMA: a VLSI systolic array implementation of a Galois field GF(2m) based multiplication and division algorithm

Finite or Galois fields are used in numerous applications like error correcting codes, digital signal processing and cryptography. The design of efficient methods for Galois field arithmetic such as multiplication and division is critical for these applications. A new algorithm based on a pattern matching technique for computing multiplication and division in GF(2^m) is presented. An efficient systolic architecture is described for implementing the algorithm which can produce a new result every clock cycle and the multiplication and division operations can be interleaved. The architecture has been implemented using 2-μm CMOS technology. The chip yields a computational rate of 33.3 million multiplications/divisions per second     

High-performance Public-key Cryptoprocessor for Wireless Mobile Applications

We present a high-speed public-key cryptoprocessor that exploits three-level parallelism in Elliptic Curve Cryptography (ECC) over GF(2 ⁿ ). The proposed cryptoprocessor employs a Parallelized Modular Arithmetic Logic Unit (P-MALU) that exploits two types of different parallelism for accelerating modular operations. The sequence of scalar multiplications is also accelerated by exploiting Instruction-Level Parallelism (ILP) and processing multiple P-MALU instructions in parallel. The system is programmable and hence independent of the type of the elliptic curves and scalar multiplication algorithms. The synthesis results show that scalar multiplication of ECC over GF(2¹⁶³) on a generic curve can be computed in 20 and 16 μs respectively for the binary NAF (Non-Adjacent Form) and the Montgomery method. The performance can be accelerated furthermore on a Koblitz curve and reach scalar multiplication of 12 μs with the TNAF (τ-adic NAF) method. This fast performance allows us to perform over 80,000 scalar multiplications per second and to enhance security in wireless mobile applications.

New Efficient Algorithms for Multiplication Over Fields of Characteristic Three

In this paper, we first present an enhancement of the well-known Karatsuba 2-way and 3-way algorithms for characteristic three fields, denoted by \(\mathbb {F}_{3^{n}}\) where n≥1. We then derive a 3-way polynomial multiplication algorithm with five 1/3 sized multiplications that use interpolation in \(\mathbb {F}_{9}\). Following the computation of the arithmetic and delay complexity of the proposed algorithm, we provide the results of our hardware implementation of polynomial multiplications over \(\mathbb {F}_{3}\) and \(\mathbb {F}_{9}\). The final proposal is a new 3-way polynomial multiplication algorithm over \(\mathbb {F}_{3}\) that uses three polynomial multiplications of 1/3 of the original size over \(\mathbb {F}_{3}\) and one polynomial multiplication of 1/3 of the original size over \(\mathbb {F}_{9}\). We show that this algorithm represents about 15% reduction of the complexity over previous algorithms for the polynomial multiplications whose sizes are of practical interest.     

Novel Radix Finite Field Multiplier for GF(2m)

In this paper, a new High-Radix Finite Field multiplication algorithm for GF(2^m) is proposed for the first time. The proposed multiplication algorithm can operate in a Digit-serial fashion, and hence can give a trade-off between the speed, the area , the input/output pin limitation, and the low power consumption by simply varying the digit size. A detailed example of a new Radix-16 GF(2^m) Digit-Serial multiplication architecture adopting the proposed algorithm illustrates a speed improvement of 75% when compared to conventional Radix-2 bit-serial realization. This is made more significant when it is noted that the speed improvement of 75% was achieved at the expense of only 2.3 times increase in the hardware requirements of the proposed architecture.     

Design of highly efficient elliptic curve crypto-processor with two multiplications over GF（2^163）

In this article, a parallel hardware processor is presented to compute elliptic curve scalar multiplication in polynomial basis representation. The processor is applicable to the operations of scalar multiplication by using a modular arithmetic logic unit (MALU). The MALU consists of two multiplications, one addition, and one squaring. The two multiplications and the addition or squaring can be computed in parallel. The whole computations of scalar multiplication over GF(2163) can be performed in 3 064 cycles. The simulation results based on Xilinx Virtex2 XC2V6000 FPGAs show that the proposed design can compute random GF(2163) elliptic curve scalar multiplication operations in 31.17 μs, and the resource occupies 3 994 registers and 15 527 LUTs, which indicates that the crypto-processor is suitable for high-performance application.     

基于有限域GF上圆锥曲线的公钥密码算法

圆锥曲线密码学是一种新型的公钥密码学,迄今对圆锥曲线密码学的研究成果都是以有限域GF(p)上的圆锥曲线为基础的.本文将有限域GF(p)上的圆锥曲线C(GF(p))推广为有限域GF(2ⁿ)上的圆锥曲线C(GF(2ⁿ)),证明了圆锥曲线C(GF(2ⁿ))上的点和加法运算构成有限交换群(C(GF(2ⁿ)),),并给出了圆锥曲线群(C(GF(2ⁿ)),)的阶的计算.此外,提出了使用有限域GF(2ⁿ)上的圆锥曲线群构造公钥密码系统,并给出了ElGamal加密方案和数字签名算法(DSA)在圆锥曲线C(GF(2ⁿ))上模拟的算法,最后分析其安全性.     

Low-complexity bit-parallel systolic multipliers over GF(2)

This paper presents new time-dependent and time-independent multiplication algorithms over finite fields GF(2^m) by employing an interleaved conventional multiplication and a folded technique. The proposed algorithm allows efficient realization of the bit-parallel systolic multipliers. The results show that the proposed time-independent multiplier saves about 54% space complexity as compared to other related multipliers for polynomial and dual bases of GF(2^m). The proposed architectures include the features of regularity, modularity and local interconnection. Accordingly, it is well suited for VLSI implementation.     

Scalable Gaussian Normal Basis Multipliers over GF(2<Superscript><Emphasis Type="Italic">m</Emphasis></Superscript>) Using Hankel Matrix-Vector Representation

This work presents a novel scalable multiplication algorithm for a type-t Gaussian normal basis (GNB) of GF(2^m). Utilizing the basic characteristics of MSD-first and LSD-first schemes with d-bit digit size, the GNB multiplication can be decomposed into n(n + 1) Hankel matrix-vector multiplications. where n = (mt + 1)/d. The proposed scalable architectures for computing GNB multiplication comprise of one d × d Hankel multiplier, four registers and one final reduction polynomial circuit. Using the relationship of the basis conversion from the GNB to the normal basis, we also present the modified scalable multiplier which requires only nk Hankel multiplications, where k = mt/2d if m is even or k = (mt − t + 2)/2d if m is odd. The developed scalable multipliers have the feature of scalability. It is shown that, as the selected digit size d ≥ 8, the proposed scalable architectures have significantly lower time-area complexity than existing digit-serial multipliers. Moreover, the proposed architectures have the features of regularity, modularity, and local interconnection ability. Accordingly, they are well suited for VLSI implementation.     

Existence of a 2n FFT algorithm with a number of multiplications lower than 2n+1

First we give a decomposition of an FFT of length 2n into a number of one-dimensional polynomial products. If these products are computed with minimum multiplication algorithms, we show that the 2n FFT can be computed with less than 2n+1 nontrivial complex multiplications. A variation of this algorithm is also shown to give the same multiplication count as the `split-radix? FFT.     

Algorithm and architecture for a Galois field multiplicative arithmetic processor

We present a new algorithm for generic multiplicative computations of the form ab/c in GF(p/sup m/), including multiplication, inversion, squaring, and division. The algorithm is based on solving a sequence of congruences that are derived from the theory of Grobner bases in modules over the polynomial ring GF(p)[x]. Its corresponding hardware and software architectures can be successfully used in applications such as error control coding and cryptography. We describe a versatile circuit associated with the algorithm for the most important case p=2. The same hardware can be used for a range of field sizes thus permitting applications in which different levels of error control or of security are required by different classes of user. The operations listed are all performed by the hardware in the same number of clock cycles, which prevents certain side-channel attacks. The loss in performance by having 2m iterations for multiplication is compensated by the full parameterization of the Galois field and the ability to perform division and multiplication in parallel.     

A Combined Circuit for Multiplication and Inversion in ${rm GF}(2^{m})$

A combined circuit for multiplication and inversion in ${rm GF}(2^{m})$ is proposed. In order to develop a combined circuit, we start with combining the most significant bit first multiplication algorithm and the modified extended Euclid's algorithm by focusing on the similarities between them. Since almost all hardware components of the circuits are shared by multiplication and inversion, the combined circuit can be implemented with significantly smaller hardware than that necessary to implement both multiplication and inversion separately. By logic synthesis, the area of the proposed circuit is estimated to be approximately over 15% smaller than that of previously proposed combined multiplication/division circuits.