High performance hardware support for elliptic curve cryptography over general prime field

Secure information exchange in resource constrained devices can be accomplished efficiently through elliptic curve cryptography (ECC). Due to the high computational complexity of ECC arithmetic, a high performance dedicated hardware architecture is essential to provide sufficient performance in a computation of elliptic curve scalar multiplication. This paper presents a high performance hardware support for elliptic curve cryptography over a prime field GF(p). It exploited a best available possible parallelism of elliptic curve points in projective representation. The proposed hardware for ECC is implemented on Xilinx Virtex-4, Virtex-5 and Virtex-6 FPGAs. A 256-bit scalar multiplication is completed in 2.01  ms, 2.62  ms and 3.91  ms on Virtex-6, Virtex-5 and Virtex-4 FPGA platforms, respectively. The results show that the proposed design is 1.96 times faster with insignificant increase in area consumption as compared to the other reported designs. Therefore, it is a good choice to be used in many ECC based schemes.     

平稳与平衡--椭圆曲线密码体制抗旁信道攻击的策略与手段

旁信道攻击方法（side channel attack）通过对密码系统的一些特殊信息的获取来进行分析与攻击．对于椭圆曲线密码体制,最主要的就是要使标量乘能够抵抗旁信道攻击方式,密码学界的研究者在这方面做了很多具体且细致的工作,从各个不同的角度提出了很多新的算法与方案．综述了椭圆曲线密码体制上抗旁信道攻击的进展情况,以“平稳”与“平衡”作为两条线索,讨论了椭圆曲线密码系统上抗旁信道攻击的各种策略和方案,指出了它们各自的优劣以及适用范围,并在最后探讨了该领域未来研究和发展方向．     

An area/performance trade-off analysis of a GF(2) multiplier architecture for elliptic curve cryptography

A hardware architecture for GF(2^m) multiplication and its evaluation in a hardware architecture for elliptic curve scalar multiplication is presented. The architecture is a parameterizable digit-serial implementation for any field order m. Area/performance trade-off results of the hardware implementation of the multiplier in an FPGA are presented and discussed.     

基于FPGA椭圆曲线密码体制的研究

对基于FPGA椭圆曲线密码体制的实现进行全面研究,在Xilinx的FPGA上实现了二元有限域和椭圆曲线点运算的所有算法。将模乘算法、模逆算法、曲线点加算法、曲线点减算法、点乘算法、ECElgamal加密/解密方案、总线命令控制等在FPGA上完成仿真、综合和板级验证,并设计出具有PCI局部总线传输功能的加密/解密适配卡。研究中提出了新的基于正规基和正则基的比特串行模乘算法实现方案。     

椭圆曲线密码中抗功耗分析攻击的标量乘改进方案

椭圆曲线标量乘法运算是椭圆曲线密码(ECC)体制中最主要的计算过程,标量乘法的效率和安全性一直是研究的热点。针对椭圆曲线标量乘运算计算量大且易受功耗分析攻击的问题,提出了一种抗功耗分析攻击的快速滑动窗口算法,在雅可比和仿射混合坐标系下采用有符号滑动窗口算法实现椭圆曲线标量乘计算,并采用随机化密钥方法抵抗功耗分析攻击。与二进制展开法、密钥分解法相比的结果表明,新设计的有符号滑动窗口标量乘算法计算效率、抗攻击性能有明显提高。     

Implementation of Digital Electronic Arithmetics and its application in image processing

In this paper we introduce new algorithm implementations of a new parametric image processing framework that will accurately process images and speed up computation for addition, subtraction, and multiplication. Its potential applications include computer graphics, digital signal processing and other multimedia applications. This Parameterized Digital Electronic Arithmetic (PDEA) model replaces linear operations with non-linear ones. The implementation of a parameterized model is presented. We also present the design of arithmetic circuits including parallel counters, adders and multipliers based in two high performance threshold logic gate implementations that we have developed. We will also explore new microprocessor architectures to take advantage of arithmetic. The experiments executed have shown that the algorithm provides faster and better enhancements from those described in the literature. The FPGA chips used is Spartan 3E from Xilinix. The critical length in the circuit implemented on the FPGA had the minimum period for the proposed subsystem is 10.209 ns (maximum frequency 97.957 MHz). Maximum power consumed is 2.4 mW using 32 nm process and we used parallelism and reuse of the Hardware components to accomplish and speed up the process.     

线性规划在椭圆曲线密码系统中的应用

提高椭圆曲线上点加运算的速度在整个基于FPGA设计的椭圆曲线密码应用系统实现中极为关键。在对已有的几种投影坐标系下的点加运算进行分析比较的基础上，提出了一种适合于FPGA设计实现的椭圆曲线上的点加运算方案。同时结合椭圆曲线密码系统具体约束给出了整数线性规划算法，并将该算法应用干曲线点加算法的并行优化处理。试验结果表明，优化后的投影坐标下的点加运算较原来的算法在速度上提高了22％。     

FPGA implementation of a run-time configurable NTT-based polynomial multiplication hardware

Multiplication of polynomials of large degrees is the predominant operation in lattice-based cryptosystems in terms of execution time. This motivates the study of its fast and efficient implementations in hardware. Also, applications such as those using homomorphic encryption need to operate with polynomials of different parameter sets. This calls for design of configurable hardware architectures that can support multiplication of polynomials of various degrees and coefficient sizes.In this work, we present the design and an FPGA implementation of a run-time configurable and highly parallelized NTT-based polynomial multiplication architecture, which proves to be effective as an accelerator for lattice-based cryptosystems. The proposed polynomial multiplier can also be used to perform Number Theoretic Transform (NTT) and Inverse NTT (INTT) operations. It supports 6 different parameter sets, which are used in lattice-based homomorphic encryption and/or post-quantum cryptosystems. We also present a hardware/software co-design framework, which provides high-speed communication between the CPU and the FPGA connected by PCIe standard interface provided by the RIFFA driver [1]. For proof of concept, the proposed polynomial multiplier is deployed in this framework to accelerate the decryption operation of Brakerski/Fan-Vercauteren (BFV) homomorphic encryption scheme implemented in Simple Encrypted Arithmetic Library (SEAL), by the Cryptography Research Group at Microsoft Research [2]. In the proposed framework, polynomial multiplication operation in the decryption of the BFV scheme is offloaded to the accelerator in the FPGA via PCIe bus while the rest of operations in the decryption are executed in software running on an off-the-shelf desktop computer. The hardware part of the proposed framework targets Xilinx Virtex-7 FPGA device and the proposed framework achieves the speedup of almost 7 ×  in latency for the offloaded operations compared to their pure software implementations, excluding I/O overhead.     

A fast parallel implementation of elliptic curve point multiplication over GF(2m)

A fast parallel architecture for the implementation of elliptic curve scalar multiplication over binary fields is presented. The proposed architecture is implemented on a single-chip FPGA device using parallel strategies that trades area requirements for timing performance. The results achieved show that our proposed design is able to compute GF(2191) elliptic curve scalar multiplication operations in 63 μs.     

抗SPA的多点乘算法

SPA(Simple Power Analysis)攻击可能通过泄露的信息获取内存受限制的设备中的密钥,它是通过区分一次点乘运算中点加运算和倍点运算进行的。抗SPA攻击的点乘算法较多,但对于多点乘算法相关措施较少。Sharmir-NAF多点乘算法是一个时间和空间效率都非常优秀的多点乘算法。为此提出一种基于Sharmir-NAF的抗SPA攻击的多点乘算法。新的算法在内存空间消耗和计算速度上较原算法负担增加可以忽略不计,而且能够抗SPA攻击。     

利用半点计算椭圆曲线双标量乘法算法

实现椭圆曲线密码体制最主要的运算是椭圆曲线点群上的标量乘法(或点乘)运算。一些基于椭圆曲线的密码协议比如ECDSA签名验证,就需要计算双标量乘法kP+lQ,其中P、Q为椭圆曲线点群上的任意两点。一个高效计算kP+lQ的方法就是同步计算两个标量乘法,而不是分别计算每个标量乘法再相加。通过对域F2m上的椭圆曲线双标量乘法算法进行研究,将半点公式应用于椭圆曲线的双标量乘法中,提出了一种新的同步计算双标量乘法算法,分析了效率,并与传统的基于倍点运算的双标量乘法算法进行了详细的比较,其效率更优。     

基于FPGA椭圆曲线密码体制的研究

对基于FPGA椭圆曲线密码体制的实现进行全面研究，在Xilinx的FPGA上实现了二元有限域和椭圆曲线点运算的所有算法。将模乘算法、模逆算法、曲线点加算法、曲线点减算法、点乘算法、EC-Elgamal加密／解密方案、总线命令控制等在FPGA上完成仿真、综合和板级验证，并设计出具有PCI局部总线传输功能的加密／解密适配卡。研究中提出了新的基于正规基和正则基的比特串行模乘算法实现方案。     

A versatile Montgomery multiplier architecture with characteristic three support

We present a novel unified core design which is extended to realize Montgomery multiplication in the fields GF(2ⁿ), GF(3^m), and GF(p). Our unified design supports RSA and elliptic curve schemes, as well as the identity-based encryption which requires a pairing computation on an elliptic curve. The architecture is pipelined and is highly scalable. The unified core utilizes the redundant signed digit representation to reduce the critical path delay. While the carry-save representation used in classical unified architectures is only good for addition and multiplication operations, the redundant signed digit representation also facilitates efficient computation of comparison and subtraction operations besides addition and multiplication. Thus, there is no need for a transformation between the redundant and the non-redundant representations of field elements, which would be required in the classical unified architectures to realize the subtraction and comparison operations. We also quantify the benefits of the unified architectures in terms of area and critical path delay. We provide detailed implementation results. The metric shows that the new unified architecture provides an improvement over a hypothetical non-unified architecture of at least 24.88%, while the improvement over a classical unified architecture is at least 32.07%.     

A Secure Hardware Implementation for Elliptic Curve Digital Signature Algorithm

Since the end of the 1990s, cryptosystems implemented on smart cards have had to deal with two main categories of attacks: side-channel attacks and fault injection attacks. Countermeasures have been developed and validated against these two types of attacks, taking into account a well-defined attacker model. This work focuses on small vulnerabilities and countermeasures related to the Elliptic Curve Digital Signature Algorithm (ECDSA) algorithm. The work done in this paper focuses on protecting the ECDSA algorithm against fault-injection attacks. More precisely, we are interested in the countermeasures of scalar multiplication in the body of the elliptic curves to protect against attacks concerning only a few bits of secret may be sufficient to recover the private key. ECDSA can be implemented in different ways, in software or via dedicated hardware or a mix of both. Many different architectures are therefore possible to implement an ECDSA-based system. For this reason, this work focuses mainly on the hardware implementation of the digital signature ECDSA. In addition, the proposed ECDSA architecture with and without fault detection for the scalar multiplication have been implemented on Xilinx field programmable gate arrays (FPGA) platform (Virtex-5). Our implementation results have been compared and discussed. Our area, frequency, area overhead and frequency degradation have been compared and it is shown that the proposed architecture of ECDSA with fault detection for the scalar multiplication allows a trade-off between the hardware overhead and the security of the ECDSA.     

4次复乘域上的GLV分解

4 维Gallant-Lambert-Vanstone（GLV）方法可用于加速一些定义在Fp2上椭圆曲线的标量乘法计算,如Longa-Sica型具有特殊复乘结构的GLS曲线以及Guillevic-Ionica利用Weil限制得到的椭圆曲线.推广了Longa-Sica的4维GLV分解方法,并在4次复乘域中给出显式且有效的4维分解方法,且对分解系数的界做出理论估计.结果行之有效,很好地支持了GLV方法以用于这些椭圆曲线上的快速标量乘法运算的实现.     

基于Pell型序列的快速安全标量乘算法

提出了一种新的椭圆曲线快速安全的标量乘算法。利用佩尔序列前后项分割比产生新的佩尔型点加-倍点链（Pell Type Double-and-Add Chain，PTDAC），其循环固定的“倍点-点加”操作可天然抵抗简单能量分析（Simple Power Analysis，SPA）攻击。PTDAC算法结合Edwards椭圆曲线可从底层域减少运算时间，进一步优化算法。经过理论分析和仿真实验表明，PTDAC算法在最优情况下比EAC-270和GRAC-258算法在时间效率上分别提高了2.6%和22.8%。     

A unified architecture for a public key cryptographic coprocessor

This paper presents a unified architecture for public key cryptosystems that can support the operations of the Rivest–Shamir–Adleman cryptogram (RSA) and the elliptic curve cryptogram (ECC). A hardware solution is proposed for operations over finite fields GF(p) and GF(2^p). The proposed architecture presents a unified arithmetic unit which provides the functions of dual-field modular multiplication, dual-field modular addition/subtraction, and dual-field modular inversion. A new adder based on the signed-digit (SD) number representation is provided for carry-propagated and carry-less operations. The critical path of the proposed design is reduced compared with previous full adder implementation methods. Experimental results show that the proposed design can achieve a clock speed of 1 GHz using 776 K gates in a 0.09 μm CMOS standard cell technology, or 150 MHz using 5227 CLBs in a Xilinx Virtex 4 FPGA. While the different technologies, platforms and standards make a definitive comparison difficult, based on the performance of our proposed design, we achieve a performance improvement of between 30% and 250% when compared with existing designs.     

GF(2~n)域上基于ONB的ECC芯片设计与实现

分析了GF(2~n)域上的椭圆曲线的运算法则,提出了一种串-并行结构的基于优化正规基(ONB)的高速有限域运算单元,比较了域划分D对芯片实现速度和硬件资源占用的影响,完成了域GF(2191)上基于ONB的ECC芯片快速实现。FPGA验证表明,GF(2191)域上一次点加运算需要183个时钟,一次点倍运算需要175个时钟,完成一次求乘法逆运算的总时钟数为133。在50MHz时钟下,完整的点乘运算速度平均为981次/s。     

Low-latency X25519 hardware implementation: breaking the 100 microseconds barrier

In the past few years, there has been a growing interest in Curve25519 due to its elegant design aimed at both high-security and high-performance, making it one of the most promising candidates to secure IoT applications. Until now Curve25519 hardware implementations were mainly optimized for high-throughput applications, while no special care was given to low-latency designs. In this work, we close this gap and provide a Curve25519 hardware design targeting low-latency applications. We present a fast constant-time variable-base-point elliptic curve scalar multiplication using Curve25519 that computes a session key in less than 100 μs. This is achieved by using a high-speed prime field multiplier that smartly combines the reduction procedure with the summation of the digit-products. As a result, our presented implementation requires only 10465 cycles for one session key computation. Synthesized on a Zynq-7030 and operating with a clock frequency of 115 MHz this translates to a latency of 92 μs which represents an improvement of factor 3.2 compared to other Curve25519 implementations. Our implementation uses Montgomery ladder as the scalar multiplication algorithm and includes randomized projective coordinates to thwart side-channel attacks.     

Clustering Collision Power Attack on RSA-CRT

In this paper, we propose two new attack algorithms on RSA implementations with CRT (Chinese remainder theorem). To improve the attack efficiency considerably, a clustering collision power attack on RSA with CRT is introduced via chosen-message pairs. This attack method is that the key parameters d_p and d_q are segmented by byte, and the modular multiplication collisions are identified by k-means clustering. The exponents d_p and d_q were recovered by 12 power traces of six groups of the specific message pairs, and the exponent d was obtained. We also propose a second order clustering collision power analysis attack against RSA implementation with CRT, which applies double blinding exponentiation. To reduce noise and artificial participation, we analyze the power points of interest by preprocessing and k-means clustering with horizontal correlation collisions. Thus, we recovered approximately 91% of the secret exponents manipulated with a single power curve on RSA-CRT with countermeasures of double blinding methods.