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 复杂度高等问题,提出了稀松形式下的区块式快速指数运算算法来改善其模指数运算。使用转换状态图来分析其效能,同时将其概念加以延伸,加强其实用性。分析表明,此算法在预先计算量小的时候有较好的效能,因此也特别适用于像智能卡这类存储空间受限的装置。     

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.     

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算法进行实现,并测试分析了根据估计公式计算出窗口大小的算法实现时间效率与理论分析基本吻合.     

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.     

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

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

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的解复用器模块研究

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

FPGA的空间容错技术研究

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

通用FPGA算法测试平台

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

A hardware Memetic accelerator for VLSI circuit partitioning

During the last decade, the complexity and size of circuits have been rapidly increasing, placing a stressing demand on industry for faster and more efficient CAD tools for VLSI circuit layout. One major problem is the computational requirements for optimizing the place and route operations of a VLSI circuit. Thus, this paper investigates the feasibility of using reconfigurable computing platforms to improve the performance of CAD optimization algorithms for the VLSI circuit partitioning problem. The proposed Genetic algorithm architecture achieves up-to 5× speedup over conventional software implementation while maintaining on average 88% solution quality. Furthermore, a reconfigurable computing based Hybrid Memetic algorithm improves upon this solution while using a fraction of the execution time required by the conventional software based approach.     

Resource efficient implementation of T-Boxes in AES on Virtex-5 FPGA

This work presents a resource efficient implementation of T-Box module of Advanced Encryption Standard (AES) on Xilinx's Virtex-5 Field Programmable Gate Array (FPGA). The proposed architecture utilizes the 100% capacity of FPGA's dedicated Block RAM (BRAM) as compared to conventional techniques, where the consumption of BRAM memory is from 25% to 50%. The results show that the module fits into 4 BRAMs, thus reducing on device resources by 50%.     

一种新颖的多模式FPGA配置方案

在FPGA调试或者应用过程中,通常利用JTAG接口将目标文件从PC下载到FPGA的SRAM中以实现配置,使得FPGA的调试和应用无法脱离存储在PC中的目标文件和Quartus软件,从而降低了FPGA调试和使用的灵活性.本文主要讨论和构造了一种新颖的FPGA配置方案,使用CPLD作为配置方案中的关键控制单元,极大方便和灵活地实现对于FPGA的配置,这将使基于FPGA的设计和调试更加简便和可靠.     

RSA密码系统有效实现算法

大整数模幂乘运算一直是制约RSA广泛应用的瓶颈,在对传统算法剖析的基础上,提出了一种新的快速模乘算法,借鉴生成Wallace tree的思想,结合查找表和并行乘法运算进行RSA模幂运算。理论分析和试验证明新算法时间复杂度降低到O(logn)。     

基于FPGA的可加密USB存储设备设计

基于FPGA的可加密USB存储设备的设计过程,介绍了FPCA芯片EP1C3T100、USB接口芯片AU6983等各个模块的功能及硬件电路设计。对AES加密算法作了详细说明,并对硬件FPGA实现进行了设计和优化。该设备由FPGA芯片通过硬件来完成数据加密过程,由高速传输总线进行数据传输。具有实时性好、安全性高等优点。     

Server-aided honest computation for cryptographic applications

A lot of discussions for smart card based identification and digital signature schemes have been considered in the literature. In this paper, a novel approach is proposed for smart cards to perform signature validation and identification verification efficiently with the help of the powerful signature signer and the identity prover.