HECC除子标量乘并行集群算法设计

为了加快超椭圆曲线密码体制(HECC)中除子标量乘的运算速度,进行基于大数据技术的除子标量乘并行算法研究。根据"空间换时间"的策略对除子标量乘法常规方法进行改进,在任务规模为1016的条件下,运算耗时减少16.28%,提出基于负载均衡的任务划分优化方案。此方案分别将Hadoop集群平台、Spark集群平台、Spark-GPU集群平台的并行技术应用于改进后的除子标量乘算法中,研究并行算法与串行算法的运行效率。当问题规模一定时,随着节点个数的增加,不同集群平台的加速呈上升趋势,其中Spark-GPU并行算法的增长趋势最为明显,当节点个数为4时,Spark-GPU并行算法的加速比达到了261.84。通过对比3种集群平台的并行算法,发现Spark-GPU可以最有效地缩短运算耗时,加快除子标量乘法的运算速度。     

一类j=0超奇异椭圆曲线的性质及其标量乘算法

针对非超奇异椭圆曲线上的标量乘算法已经有比较多的研究.与非超奇异曲线不同,超奇异椭圆曲线的自同态环是四元数代数的一个序模,为非交换环.本文主要针对特征大于3的有限域上一类j不变量为0的超奇异椭圆曲线,分析了曲线自同态环及其商环的结构.进而研究了此类曲线上整数表示的性质,并基于这种表示方法提出了一种针对此类曲线的标量乘算法.理论上证明了针对此类超奇异曲线,当选择合适系数集合时,此表示实质上为p-adic展开.实验结果表明：相较于4-NAF等方法,p-adic表示方法提高标量乘效率一倍以上.     

基于二进制Edwards曲线的椭圆曲线加密多标量乘结构设计与实现

标量乘及多标量乘算法是影响椭圆曲线密码系统性能的关键.基于二进制Edwards曲线提出并实现了一种新型的椭圆曲线标量乘法器.由于Edwards曲线的完备性,这种乘法器可对曲线上任意一点进行计算,而不用区分倍乘或者负元,实现较简单,有很高的运算速度和很强的抗侧信道攻击的能力.     

素数域上椭圆曲线快速实现技术研究

随着椭圆曲线公钥密码的广泛应用,怎样快速实现椭圆曲线密码一直是业界关注的重点,在一些应用场景下,如移动、无线领域的应用,对椭圆曲线的实现速度要求较高,目前有许多快速实现椭圆曲线的算法,其性能各有差异.文章全面地研究素数域上的椭圆曲线快速实现技术,如Mersenne素数运算、Fermat定理、Euclidean方法等,并分析了这些方法.在此基础上,给出了详细的素数域上的椭圆曲线完整的实现细节及其关键技术的详细分析和实现方法.用该方法,能快速实现素数域上的椭圆曲线.     

面向多曲线的通用高性能ECC处理器设计

该文针对广泛应用的TLS1.3协议，提出了一种高性能的椭圆曲线密码处理器.该处理器支持TLS1.3协议中定义的两类素数域椭圆曲线的通用模数.通过对高基蒙哥马利算法的改进，提出了一种支持521 bit及以下位宽的模乘运算单元，并提出了一种双模乘单元并行结构的标量乘法器.基于该结构在两类椭圆曲线下设计了雅阁比坐标系下并行的点运算时序排布，使模乘单元的利用率在不同点运算情况下达到100%,95.4%和86.5%.与现有设计相比，本文中标量乘法运算消耗的周期更少，运算单元利用率更高，在相似的时间面积乘积前提下，具有更强的通用性和可配置性的优势.在TSMC 55 nm CMOS工艺下达到454 MHz的时钟频率，等效逻辑门数851k,Secp256r1曲线的标量乘运算速度为31 230 times/s.     

一类安全椭圆曲线的选取及其标量乘法的快速计算

安全椭圆曲线的选取和标量乘法的快速计算是有效实现椭圆曲线密码体制的两个主要问题.本文将二者结合起来考虑给出了一类适合普通PC机实现的安全椭圆曲线,并详细给出了选取这类曲线的具体步骤和基于"大步-小步法"思想构造了一种新的计算这类曲线上标量乘法的快速算法.这类曲线不仅选取容易而且利用本文所提出方法计算其标量乘法时能使所需椭圆曲线运算次数大大减少.此外,选用这类曲线后基域中元素不再需要专门的表示方法,各种运算能非常快地得到实现,从而能极大地提高体制的整体实现速度.     

一种基于折半运算的Comb标量乘算法

通过将折半运算应用于Comb算法,提出了一种新的Comb标量乘算法,它可以提高域Fm2上的椭圆曲线标量乘法的效率.在预计算阶段和赋值阶段,新算法分别用高效的折半运算取代倍点运算.对新算法运行时间进行分析,并与传统的Comb算法进行比较,当窗口宽度w=4时,新算法效率提高58%~63%.     

Montgomery形式椭圆曲线的生成研究

文章详细分析了O-K-S算法[1],并给出改进算法。改进的算法有效地生成了广义Mersenne素数域上可抵抗时间分析攻击且阶恰好只能被4整除的Montgomery形式椭圆曲线,并且运用了早期终止策略和伪随机选取方法,在一定程度上提高了此类曲线的生成效率。     

Koblitz曲线上改进的ECDSA算法

标量乘法的效率决定着椭圆曲线密码体制的性能,而Koblitz曲线上的快速标量乘算法,是标量乘法研究的重要课题.Lee et al算法采用Frobenius映射扩展正整数k,并将其扩展后的系数改写成二进制形式,有效地提高标量乘算法效率.文中将JSF应用到扩展后的系数中,以较小存储空间为代价来提高算法效率k并将算法用到改进...     

椭圆曲线加密体制的构建与应用

采用Java提供的大数操作,对素数域上椭圆曲线进行深入分析,以国际上相关的研究和算法实现工作为基础,采用数学建模和面向对象的思想,根据椭圆曲线密码体制,实现素数域椭圆曲线加密系统,给出详细的设计,并分析了其中的关键算法。针对Java在网络上的广泛应用,将其应用于网络验证,保护网络应用系统的安全。     

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.     

Flexible Prime‐Field Genus 2 Hyperelliptic Curve Cryptography Processor with Low Power Consumption and Uniform Power Draw

This paper presents an energy‐efficient (low power) prime‐field hyperelliptic curve cryptography (HECC) processor with uniform power draw. The HECC processor performs divisor scalar multiplication on the Jacobian of genus 2 hyperelliptic curves defined over prime fields for arbitrary field and curve parameters. It supports the most frequent case of divisor doubling and addition. The optimized implementation, which is synthesized in a 0.13 μm standard CMOS technology, performs an 81‐bit divisor multiplication in 503 ms consuming only 6.55 μJ of energy (average power consumption is 12.76 μW). In addition, we present a technique to make the power consumption of the HECC processor more uniform and lower the peaks of its power consumption.     

Jacobian Coordinates on Genus 2 Curves

This paper presents a new projective coordinate system and new explicit algorithms which together boost the speed of arithmetic in the divisor class group of genus 2 curves. The proposed formulas generalize the use of Jacobian coordinates on elliptic curves, and their application improves the speed of performing cryptographic scalar multiplications in Jacobians of genus 2 curves over prime fields by an approximate factor of 1.25x. For example, on a single core of an Intel Core i7-3770 (Ivy Bridge), we show that replacing the previous best formulas with our new set improves the cost of generic scalar multiplications from 239,000 to 192,000 cycles and drops the cost of specialized GLV-style scalar multiplications from 155,000 to 123,000 cycles.     

有限域上超椭圆曲线离散对数问题的错误攻击

In this paper, we present two explicit inva-lid-curve attacks on the genus 2 hyperelliptic curve o-ver a finite field. First, we propose two explicit attack models by injecting a one-bit fault in a given divisor. Then, we discuss the construction of an invalid curve based on the faulted divisor. Our attacks are based on the fact that the Hyperelliptic Curve Scalar Multiplica-tion (HECSM) algorithm does not utilize the curve parameters and We consider three hyperelliptic curves as the attack targets. For curve with security level 186 (in bits), our attack method can get the weakest inva-lid curve with security level 42 (in bits); there are 93 invalid curves with security level less than 50. We al-so estimate the theoretical probability of getting a weak hyperelliptic curve whose cardinality is a smooth integer. Finally, we show that the complexity of the fault attack is subexponential if the attacker can freely inject a fault in the input divisor. Cryptosystems based on the genus 2 hyperelliptic curves cannot work against our attack algorithm in practice.     

Effective generalized equations of secure hyperelliptic curve digital signature algorithms

A hyperelliptic curve digital signature algorithm (HECDSA) can be viewed as the hyperelliptic curve analogue of the standard digital signature algorithm (DSA). This article discusses divisor evaluations, the basic HECDSA, variants, two HECDSA equations and a 4-tuple HECDSA scheme, and puts forward a generalized equation for HECDSA. From this generalized equation, seven general HECDSA types are derived based on the efficiency requirements. Meanwhile, the securities of these general HECDSA types are analyzed in detail.     

The Complexity of Certain Multi-Exponentiation Techniques in Cryptography

We describe, analyze and compare some combinations of multi-exponentiation algorithms with representations of the exponents. We are especially interested in the case where the inversion of group elements is fast: this is true for example for elliptic curves, groups of rational divisor classes of hyperelliptic curves, trace zero varieties and XTR. The methods can also be used for computing single exponentiations in groups which admit an appropriate automorphism satisfying a monic equation of small degree over the integers.     

超椭圆曲线离散对数的Weil Descent代数攻击的分析

本文首先介绍了Galbraith的Weil Descent代数攻击方法，然后对定义在GF（q^n)上的形如y^2 xy=f(x)的HCDLP能否用Weil Descent代数方法攻击作了详细讨论，作为例子，研究了GF（4）和GF（8）上的这类曲线。得到结论：（1）Weil Descent代数攻击法只能适用于极少部分这类超椭圆曲线；（2）当亏格或基域增大时，Weil Descent方法攻击成功的概率趋向于0。所以说Weil Descent代数攻击法对建立在GF（2^n)上的这类超椭圆曲线密码体制并没有太大的威胁。     

Hyperelliptic Curve Crypto‐Coprocessor over Affine and Projective Coordinates

This paper presents the design and implementation of a hyperelliptic curve cryptography (HECC) coprocessor over affine and projective coordinates, along with measurements of its performance, hardware complexity, and power consumption. We applied several design techniques, including parallelism, pipelining, and loop unrolling, in designing field arithmetic units, group operation units, and scalar multiplication units to improve the performance and power consumption. Our affine and projective coordinate‐based HECC processors execute in 0.436 ms and 0.531 ms, respectively, based on the underlying field GF(2⁸⁹). These results are about five times faster than those for previous hardware implementations and at least 13 times better in terms of area‐time products. Further results suggest that neither case is superior to the other when considering the hardware complexity and performance. The characteristics of our proposed HECC coprocessor show that it is applicable to high‐speed network applications as well as resource‐constrained environments, such as PDAs, smart cards, and so on.     

Optimized FPGA-based elliptic curve cryptography processor for high-speed applications

In this paper, we introduce an FPGA-based processor for elliptic curve cryptography on Koblitz curves. The processor targets specifically to applications requiring very high speed. The processor is optimized for performing scalar multiplications, which are the basic operations of every elliptic curve cryptosystem, only on one specific Koblitz curve; the support for other curves is achieved by reconfiguring the FPGA. We combine efficient methods from various recent papers into a very efficient processor architecture. The processor includes carefully designed processing units dedicated for different parts of the scalar multiplication in order to increase performance. The computation is pipelined providing simultaneous processing of up to three scalar multiplications. We provide experimental results on an Altera Stratix II FPGA demonstrating that the processor computes a single scalar multiplication on average in and achieves a throughput of 235,550 scalar multiplications per second on NIST K-163.