New fault attacks using Jacobi symbol and application to regular right-to-left algorithms

Fast exponentiation algorithms are central in the implementation of public key cryptography. They should be secure as well as efficient. Nowadays physical attacks such as side channel analysis or fault attacks become big threats in the implementation of cryptographic algorithms. In this article, we propose two new fault attacks using Jacobi symbol. Furthermore we show that Joye's regular right-to-left algorithms are vulnerable to them.     

An implementation for a fast public-key cryptosystem

In this paper we examine the development of a high-speed implementation of a system to perform exponentiation in fields of the form GF(2 ⁿ ). For sufficiently large n, this device has applications in public-key cryptography. The selection of representation and observations on the structure of multiplication have led to the development of an architecture which is of low complexity and high speed. A VLSI implementation has being fabricated with measured throughput for exponentiation for cryptographic purposes of approximately 300 kilobits per second.     

Fast exponentiation based on common-multiplicand-multiplication and minimal-signed-digit techniques

In this paper, an improved common-multiplicand-multiplication algorithm is proposed, utilizing the binary exponentiation method and minimal-signed-digit recoding technique for fast exponentiation. By adopting the recoding technique on the common signed-digit representations in the grouped exponent substrings, the proposed algorithm provides an efficient exponentiation method. The proposed algorithm achieves better performance in modern exponentiation methods by decreasing the overall computational complexity. In particular, the proposed method is very suitable for parallel processing systems to improve the efficiency of exponentiation operation.     

大数模幂算法的分析与研究

大数模幂在密码学领域有广泛的应用，它是公钥密码的基础。文章对目前比较典型的各种大数模幂算法的设计思想进行了深入剖析，从基本设计原理和实现角度对这些模幂算法进行了整理和分类，归纳给出了各种算法的优缺点、实现方法和使用环境。     

快速寻找大素数的算法分析与实现

RSA是目前最优秀的公钥方案之一,其安全性建立在大整数分解为两个素数之积的困难性假设基础之上.由于RSA进行的都是大数运算,因此受到素数产生技术的限制,产生密钥困难.本文从超大整数在内存中的表示方法及基本运算方法开始,讨论了两种产生素数的方法:试除法和测试法,根据产生素数范围的不同,使用试除法和测试法可以有效地解决快速产生大素数的技术难题.     

多机协同加解密模式及其算法研究*

针对模幂型公钥密码的快速实现问题提出了一种新的多机协同实现机制,结合RSA详细论述了多机协同机制的设计思想和实现方法,并针对新机制设计了一种多机模幂算法,分别从工作机制和算法上进行了实现效率和安全性分析。结果表明,模数和指数都为1 024bit时,新机制实现效率是单机模式的8倍,模数和指数都为2 048bit时实现效率可提高16倍。     

Partition Algorithm For Parallel Processing Of Array Multiplication In Gf(2m) Fields

The multiplication operations in GF(2m) fields are widely used in cryptosystems. However, the multiplication operations for public-key cryptosystems require very large operands with 512 bits or more, and then existing multipliers are not available for such multiplications. In this paper, we will present a partition algorithm to divide large operands into small operands such as 32 bits or 64 bits, and then existing multipliers can be employed. We also present a parallel version of the partition algorithm by employing an important natural property of the multiplication operations in GF(2m) fields.     

Efficient Exponentiation in Extensions of Finite Fields without Fast Frobenius Mappings

This paper proposes an exponentiation method with Frobenius mappings. The main target is an exponentiation in an extension field. This idea can be applied for scalar multiplication of a rational point of an elliptic curve defined over an extension field. The proposed method is closely related to so‐called interleaving exponentiation. Unlike interleaving exponentiation methods, it can carry out several exponentiations of the same base at once. This happens in some pairing‐based applications. The efficiency of using Frobenius mappings for exponentiation in an extension field was well demonstrated by Avanzi and Mihailescu. Their exponentiation method efficiently decreases the number of multiplications by inversely using many Frobenius mappings. Compared to their method, although the number of multiplications needed for the proposed method increases about 20%, the number of Frobenius mappings becomes small. The proposed method is efficient for cases in which Frobenius mapping cannot be carried out quickly.     

RSA密码算法的可重构设计与实现

本文对RSA密码算法的实现和可重构性进行了分析,在对模幂模块和模乘模块进行了可重构设计的基础上,提出一种可重构RSA硬件架构,使其能够适配256bit、512bit、1024bit、2048bit四种不同密钥长度的应用。RSA可重构设计在FPGA上进行了实现与测试,结果表明,工作在200MHz时钟时,2048bit密钥长度RSA在最坏情况下数据吞吐量可达46kb／s,能够满足高性能的信息安全系统对RSA算法的加密速度要求。     

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.