共查询到20条相似文献,搜索用时 0 毫秒
1.
2.
In many problems, modular exponentiation |xb|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 |xb|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 |xb|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 mi allows to compute |xb|m by n modular exponentiations |xib|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 log2mi for each residue digit.A general architecture is also proposed and evaluated, as a possible implementation of the proposed method for the modular exponentiation. 相似文献
3.
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. 相似文献
4.
5.
《国际计算机数学杂志》2012,89(10):1251-1259
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 n ) 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. 相似文献
6.
Parallel exponentiation using common-multiplicand-multiplication and signed-digit-folding techniques
《国际计算机数学杂志》2012,89(10):1187-1202
An efficient computation of the modular exponentiations C?=?ME 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 n ) 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. 相似文献
7.
秦小龙 《网络安全技术与应用》2003,(11):19-23
本文首先介绍了硬件密码组件的概念,简述了其与软件密码组件的区别然后提出了HCM的数学模型、系统结构和典型硬件组成,最后详细分析了HCM面临的安全威胁,设计了个相应的解决机制。 相似文献
8.
提出一种新大数模幂与点乘m_ary算法中窗口大小的最优化估计方法.该方法不同于传统的暴力搜寻方法,也不同于在窗口的取值范围内通过逐一测试程序来获得最优窗口大小的方法.其基于以下理论分析:模幂 m_ary算法的基本运算为大数乘法,其中包括大数平方算法和一般大数乘法;椭圆曲线加密算法中点乘的m_ary算法步骤与模幂的m_ary算法相同,后者的基本运算为倍乘和加法.根据m_ary算法的基本运算的调用次数,推算出了最优窗口大小的估计公式.通过实验对m_ary算法进行实现,并测试分析了根据估计公式计算出窗口大小的算法实现时间效率与理论分析基本吻合. 相似文献
9.
Shmuel T. Klein 《Information Processing Letters》2008,106(6):232-237
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. 相似文献
10.
11.
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. 相似文献
12.
介绍了DVB-T解复用器的原理及模块构造,并介绍了如何使用现场可编程门阵列实现其功能。详细介绍了实现的具体步骤以及需要注意的事项。 相似文献
13.
基于SRAM的FPGA对于空间粒子辐射非常敏感,很容易产生软故障,所以对基于FPGA的电子系统采取容错措施以防止此类故障的出现非常重要.通过对敏感电路使用三模冗余(TMR)方法并利用FPGA的动态可重构特性,可以有效的增强FPGA的抗单粒子性能,解决FPGA对因空间粒子辐射而形成的软故障. 相似文献
14.
15.
Stephen Coe Author Vitae Author Vitae Medhat Moussa Author Vitae 《Computers & Electrical Engineering》2007,33(4):233-248
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. 相似文献
16.
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%. 相似文献
17.
18.
大整数模幂乘运算一直是制约RSA广泛应用的瓶颈,在对传统算法剖析的基础上,提出了一种新的快速模乘算法,借鉴生成Wallace tree的思想,结合查找表和并行乘法运算进行RSA模幂运算。理论分析和试验证明新算法时间复杂度降低到O(logn)。 相似文献
19.
20.
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. 相似文献