Fast modular exponentiation of large numbers with large exponents

In many problems, modular exponentiation |x^b|_m is a basic computation, often responsible for the overall time performance, as in some cryptosystems, since its implementation requires a large number of multiplications.It is known that |x^b|_m=|x^|b|_(m)|_m for any x in [1,m−1] if m is prime; in this case the number of multiplications depends on (m) instead of depending on b. It was also stated that previous relation holds in the case m=pq, with p and q prime; this case occurs in the RSA method.In this paper it is proved that such a relation holds in general for any x in [1,m−1] when m is a product of any number n of distinct primes and that it does not hold in the other cases for the whole range [1,m−1].Moreover, a general method is given to compute |x^b|_m without any hypothesis on m, for any x in [1,m−1], with a number of modular multiplications not exceeding those required when m is a product of primes.Next, it is shown that representing x in a residue number system (RNS) with proper moduli m_i allows to compute |x^b|_m by n modular exponentiations |x_i^b|_mi in parallel and, in turn, to replace b by |b|_(mi) in the worst case, thus executing a very low number of multiplications, namely log₂m_i for each residue digit.A general architecture is also proposed and evaluated, as a possible implementation of the proposed method for the modular exponentiation.     

Improved batch exponentiation

An improved batch exponentiation algorithm is proposed that enhances the combination step of M'Raïhi-Naccache's batch exponentiation algorithm with a decremental combination strategy. In comparison with M'Raïhi-Naccache's algorithm for 160-bit and 1024-bit exponents, the proposed algorithm reduces the workload per exponentiation by about 15% in both cases when the optimal batch size is applied.     

稀疏形式下的区块式快速指数运算算法

针对在许多类 ElGamal 公钥密码体制中计算 AX mod n 与 AXBX mod n 复杂度高等问题,提出了稀松形式下的区块式快速指数运算算法来改善其模指数运算。使用转换状态图来分析其效能,同时将其概念加以延伸,加强其实用性。分析表明,此算法在预先计算量小的时候有较好的效能,因此也特别适用于像智能卡这类存储空间受限的装置。     

大整数模幂的固定基窗口组合算法

模幂乘运算是实现公钥密码体制的一个很重要的运算,其运算速度从整体上决定了公钥密码体制的实现效率。通过采用预处理技术,将椭圆曲线的定点标量乘的固定基窗口方法应用在模幂运算中,与SMM算法进行组合得到一种新的求模幂乘算法——固定基窗口方法。对算法的原理与效率进行了分析,实验结果表明,算法的运算速度得到了有效提高。     

方幂模快速计算的二进制分组查表法

在方幂模的二进制快速算法基础上,进一步改写方幂模计算表达式,设计了一种基于查表法的二进制快速算法。算法将指数的二进制形式进行分组,提前计算并记忆一个二进制分组中首位为1其他位任意变化的所有情况下的方幂模结果,然后遍历指数的二进制形式,按照算法规则直接平方或连续多次平方后与事先记忆的值相乘,已经记忆的值不需要重复计算,从而减少了大量的乘法运算。算法分析和实验结果证明,基于查表法的方幂模二进制快速算法比二进制算法减少了乘法次数,尤其指数二进制形式中有大量1连续出现或相对连续出现（同一分组内有两位以上为1）的情况下算法效率比二进制算法有大幅度提高。     

模幂运算安全外包算法的新设计

由于模幂运算的计算成本较高,资源有限的本地客户端可以将模幂运算外包给计算能力强大的云服务器。该算法主要研究形如u^a(mod N)的模幂运算的外包算法,其中N是两个大素数的乘积。其利用欧拉定理设计了一个基于双服务器模型的模幂运算安全外包方案。在运算外包过程中,保证底数u、指数a,以及运算结果对两个服务器的隐私保护。通过安全、效率分析和实验仿真表明,相较于现有方案,新方案具有更好的执行效率和可验证性,在用户端的效率更高,且新方案的可验证概率为1。     

Fast exponentiation by folding the signed-digit exponent in half

For modern cryptographic systems, the public key cryptosystem such as RSA requires modular exponentiation (M ^E mod?N). The M, E and N are either as large as the 1024-bit integers or even larger, it is not a very good idea to directly compute M ^E mod?N. Recently, there are many techniques have been invented to solve the time-consuming computations of such time-consuming modular exponentiation. Among these useful algorithms, the “binary (square-and-multiply) algorithm” reduces the amount of modulo multiplications. As the “signed-digit representation algorithm” has the property of the nonzero digit occurrence probability equals to 1/3, taking this advantage, this method can more effectively decrease the amount of modular multiplications. Moreover, by using the technique of recording the common parts in the folded substrings, the “folding-exponent algorithm” can improve the efficiency of the binary algorithm, thus can further decrease the computational complexity of modular exponentiation. In this paper, a new modular exponentiation algorithm is proposed which based on the binary algorithm, signed-digit representation, and the folding-exponent technique. By using the parallel processing technique, in our proposed method, the modular multiplications and modular squaring can be executed in parallel, and thus lower down the computational complexity to k?+?3 multiplications. As modular squaring operation over GF(2 ⁿ ) is carried out by a simple cyclic right shift operation, the computational complexity of our proposed method can be further reduced to 29k/36?+?3 multiplications.     

几种方幂模快速算法的加法链一致性分析

在RSA算法中,最主要、使用最频繁同时也是最耗时的是方幂模运算。自从RSA算法提出后,方幂模快速算法一直是研究重点之一,方幂模算法的改进和速度的提高直接影响RSA算法的整体性能和广泛应用。深入分析了方幂模计算的秦九韶算法、分块算法、二进制自适应分组查表法和最短加法链算法,提出了加法链的统一思想,认为这几种算法在本质上都是加法链算法,为以后的研究工作指出了方向。同时指出二进制自适应分组查表法可以获得更高的整体效率,但仍有进一步提升的空间。     

Parallel exponentiation using common-multiplicand-multiplication and signed-digit-folding techniques

An efficient computation of the modular exponentiations C?=?M^E mod N is very useful for public-key cryptosystems. In this paper, an efficient parallel modular exponentiation algorithm is proposed based on both the common-multiplicand-multiplication (CMM) and signed-digit-folding (SDF) techniques. The ‘minimal-signed-digit (SD) recoding algorithm’ has less occurrence probability of the nonzero digit than the binary number representation. Taking this advantage, we can effectively decrease the amount of modular multiplications. By dividing the bit string of the minimal-SD recoding exponent E into three equal-length parts and by using the technique of recording the common parts in the folded substrings, the ‘folding-exponent algorithm’ can improve the efficiency of the binary algorithm, thus it can further decrease the computational complexity of modular exponentiation. As the modular squaring operation in GF(2 ⁿ ) over the normal basis can be done by a simple shift operation, the modular multiplications and the modular squaring operations in our proposed CMM–SDF algorithm can be executed in parallel. By using our proposed parallel CMM–SDF algorithm, we can obtain the optimal overall computational complexity as 0.689k?+?11 multiplications by folding the minimal-SD recoding exponent E exactly one-time in SD radix-2 recoding system, where k denotes the digit-length of the exponent and n denotes the folding time of the exponent.     

硬件密码组件及其安全性研究

本文首先介绍了硬件密码组件的概念,简述了其与软件密码组件的区别然后提出了HCM的数学模型、系统结构和典型硬件组成,最后详细分析了HCM面临的安全威胁,设计了个相应的解决机制。     

模幂与点乘m_ary算法中窗口大小的最优化估计*

提出一种新大数模幂与点乘m_ary算法中窗口大小的最优化估计方法。该方法不同于传统的暴力搜寻方法,也不同于在窗口的取值范围内通过逐一测试程序来获得最优窗口大小的方法。其基于以下理论分析：模幂 m_ary算法的基本运算为大数乘法,其中包括大数平方算法和一般大数乘法;椭圆曲线加密算法中点乘的m_ary算法步骤与模幂的m_ary算法相同,后者的基本运算为倍乘和加法。根据m_ary算法的基本运算的调用次数,推算出了最优窗口大小的估计公式。通过实验对m_ary算法进行实现,并测试分析了根据估计公式计算出窗口大小的算     

模幂与点乘m_ary算法中窗口大小的最优化估计

提出一种新大数模幂与点乘m_ary算法中窗口大小的最优化估计方法.该方法不同于传统的暴力搜寻方法,也不同于在窗口的取值范围内通过逐一测试程序来获得最优窗口大小的方法.其基于以下理论分析:模幂 m_ary算法的基本运算为大数乘法,其中包括大数平方算法和一般大数乘法;椭圆曲线加密算法中点乘的m_ary算法步骤与模幂的m_ary算法相同,后者的基本运算为倍乘和加法.根据m_ary算法的基本运算的调用次数,推算出了最优窗口大小的估计公式.通过实验对m_ary算法进行实现,并测试分析了根据估计公式计算出窗口大小的算法实现时间效率与理论分析基本吻合.     

Should one always use repeated squaring for modular exponentiation?

Modular exponentiation is a frequent task, in particular for many cryptographic applications. To accelerate modular exponentiation for very large integers one may use repeated squaring, which is based on representing the exponent in the standard binary numeration system. We show here that for certain applications, replacing the standard system by one based on Fibonacci numbers may yield a new line of time/space tradeoffs.     

基于硬件的计算机安全策略

计算机的安全问题日益突出,相应地,对计算机安全的研究也越来越受到重视,但目前对计算机安全的研究主要集中在软件方面,为了更有效地提高计算机的安全,对基于硬件的计算机安全进行了研究。应用分类的研究方法,较系统地提出了基于硬件的计算机安全策略,首先从计算机硬件的各个组成部分出发,分析如何提高计算机的安全,然后分析各组成部分如何协调一致。研究结果可以作为计算机安全策略的一部分,用于指导如何提高计算机的安全。     

基于FPGA的解复用器模块研究

介绍了DVB-T解复用器的原理及模块构造,并介绍了如何使用现场可编程门阵列实现其功能。详细介绍了实现的具体步骤以及需要注意的事项。     

FPGA的空间容错技术研究

基于SRAM的FPGA对于空间粒子辐射非常敏感,很容易产生软故障,所以对基于FPGA的电子系统采取容错措施以防止此类故障的出现非常重要.通过对敏感电路使用三模冗余(TMR)方法并利用FPGA的动态可重构特性,可以有效的增强FPGA的抗单粒子性能,解决FPGA对因空间粒子辐射而形成的软故障.     

Secure evolvable hardware for public-key cryptosystems

In this paper, genetic programming is used as an alternative means to automatically generate secure and minimal hardware designs of public-key cryptosystems such as the RSA cryptosystem. We evolve optimal hardware circuits for modular exponentiation, which is a cornerstone operation in many public-key cryptographic system. The evolved circuits minimize both space (i.e. required gate number) and time (i.e. encryption and decryption time). The evolved designs are shielded against side-channel leakage and hence secure. The structure of the cryptographic circuit is random and so the private key cannot be deduced using known attacks. We compare our results against existing well-known designs, which were produced by human designers based on the binary method. Nadia Nedjah, Ph.D.: She is an associate professor in the Department of Electronics Engineering and Telecommunications at the Faculty of Engineering, State University of Rio de Janeiro, Brazil. Her research interests include functional programming, embedded systems and reconfigurable hardware design as well as cryptography. Nedjah received her Ph.D. in Computation from the University of Manchester — Institute of Science and Technology (UMIST), England, her M.S.c. in System Engineering and Computation from the University of Annaba, Algeria and her Engineerind degree in Computer Science also from the University of Annaba, Algeria. Luiza de Macedo Mourelle, Ph.D.: She is an associate professor in the Department of System Engineering and Computation at the Faculty of Engineering, State University of Rio de Janeiro, Brazil. Her research interests include computer architecture, embedded systems design, hardware/software codesign and reconfigurable hardware. She received her Ph.D. in Computation from the University of Manchester — Institute of Science and Technology (UMIST), England, her M.S.c. in System Engineering and Computation from the Federal University of Rio de Janeiro (UFRJ), Brazil and her Engineering degree in Electronics also from UFRJ, Brazil.     

通用FPGA算法测试平台

基于FPGA实现的通信系统需要进行大规模的数据测试,为缩短FPGA的设计周期以及降低大数据量测试带来的复杂性,基于DSP处理器建立了一个通用FPGA测试平台。采用此平台可以对FPGA上不同功能的算法进行功能、可靠性的测试,解决了传统FPGA测试方法难以进行大数据量、长时间测试的问题。该平台易于扩展,可以直接应用于多种通信系统的硬件实现。     

Improving the computational efficiency of modular operations for embedded systems

Security protocols such as IPSec, SSL and VPNs used in many communication systems employ various cryptographic algorithms in order to protect the data from malicious attacks. Thanks to public-key cryptography, a public channel which is exposed to security risks can be used for secure communication in such protocols without needing to agree on a shared key at the beginning of the communication. Public-key cryptosystems such as RSA, Rabin and ElGamal cryptosystems are used for various security services such as key exchange and key distribution between communicating nodes and many authentication protocols. Such public-key cryptosystems usually depend on modular arithmetic operations including modular multiplication and exponentiation. These mathematical operations are computationally intensive and fundamental arithmetic operations which are intensively used in many fields including cryptography, number theory, finite field arithmetic, and so on. This paper is devoted to the analysis of modular arithmetic operations and the improvement of the computation of modular multiplication and exponentiation from hardware design perspective based on FPGA. Two of the well-known algorithms namely Montgomery modular multiplication and Karatsuba algorithms are exploited together within our high-speed pipelined hardware architecture. Our proposed design presents an efficient solution for a range of applications where area and performance are both important. The proposed coprocessor offers scalability which means that it supports different security levels with a cost of performance. We also build a system-on-chip design using Xilinx’s latest Zynq-7000 family extensible processing platform to show how our proposed design improve the processing time of modular arithmetic operations for embedded systems.