Based on the analysis of several familiar large integer modular multiplication algorithms, this paper proposes a new Scalable Hybrid modular multiplication (SHyb) algorithm which has scalable operands, and presents an...Based on the analysis of several familiar large integer modular multiplication algorithms, this paper proposes a new Scalable Hybrid modular multiplication (SHyb) algorithm which has scalable operands, and presents an RSA algorithm model with scalable key size. Theoretical analysis shows that SHyb algorithm requires m 2 n /2 + 2miterations to complete an mn-bit modular multiplication with the application of an n-bit modular addition hardware circuit. The number of the required iterations can be reduced to a half of that of the scalable Montgomery algorithm. Consequently, the application scope of the RSA cryptosystem is expanded and its operation speed is enhanced based on SHyb al- gorithm.展开更多
Modular arithmetic is a fundamental operation and plays an important role in public key cryptosystem. A new method and its theory evidence on the basis of modular arithmetic with large integer modulus-changeable modul...Modular arithmetic is a fundamental operation and plays an important role in public key cryptosystem. A new method and its theory evidence on the basis of modular arithmetic with large integer modulus-changeable modulus algorithm is proposed to improve the speed of the modular arithmetic in the presented paper. For changeable modulus algorithm, when modular computation of modulo n is difficult, it can be realized by computation of modulo n-1 and n-2 on the perquisite of easy modular computations of modulo n-1 and modulo n-2. The conclusion is that the new method is better than the direct method by computing the modular arithmetic operation with large modulus. Especially, when computations of modulo n-1 and modulo n-2 are easy and computation of modulo n is difficult, this new method will be faster and has more advantages than other algorithms on modular arithmetic. Lastly, it is suggested that the proposed method be applied in public key cryptography based on modular multiplication and modular exponentiation with large integer modulus effectively展开更多
A new structure of bit-parallel Polynomial Basis(PB)multiplier is proposed,which isbased on a fast modular reduction method.The method was recommended by the National Instituteof Standards and Technology(NIST).It take...A new structure of bit-parallel Polynomial Basis(PB)multiplier is proposed,which isbased on a fast modular reduction method.The method was recommended by the National Instituteof Standards and Technology(NIST).It takes advantage of the characteristics of irreducible polyno-mial,i.e.,the degree of the second item of irreducible polynomial is far less than the degree of thepolynomial in the finite fields GF(2m).Deductions are made for a class of finite field in which trino-mials are chosen as irreducible polynomials.Let the trinomial bex m +x k+1,where 1 ≤k≤?m/2?.??The proposed structure has shorter critical path than the best known one up to date,whilethe space requirement keeps the same.The structure is practical,especially in real time crypto-graphic applications.展开更多
RSA(Rivest-Shamir-Adleman)public-key cryptosystem is widely used in the information security area such as encryption and digital signature. Based on the modified Montgomery modular multiplication algorithm, a new arch...RSA(Rivest-Shamir-Adleman)public-key cryptosystem is widely used in the information security area such as encryption and digital signature. Based on the modified Montgomery modular multiplication algorithm, a new architecture using CSA(carry save adder)was presented to implement modular multiplication. Compared with the popular modular multiplication algorithms using two CSA, the presented algorithm uses only one CSA, so it can improve the time efficiency of RSA cryptoprocessor and save about half of hardware resources for modular multiplication. With the increase of encryption data size n, the clock cycles for the encryption procedure reduce in (T(n^2),) compared with the modular multiplication algorithms using two CSA.展开更多
In order to make the typical Montgomery’s algorithm suitable for implementation on FPGA, a modified version is proposed and then a high-performance systolic linear array architecture is designed for RSA cryptosystem ...In order to make the typical Montgomery’s algorithm suitable for implementation on FPGA, a modified version is proposed and then a high-performance systolic linear array architecture is designed for RSA cryptosystem on the basis of the optimized algorithm. The proposed systolic array architecture has dis- tinctive features, i.e. not only the computation speed is significantly fast but also the hardware overhead is drastically decreased. As a major practical result, the paper shows that it is possible to implement public-key cryptosystem at secure bit lengths on a single commercially available FPGA.展开更多
The present paper proposes a secure design of the energy-efficient multi-modular exponential techniques that use store and reward method and store and forward method.Computation of the multi-modular exponentiation can...The present paper proposes a secure design of the energy-efficient multi-modular exponential techniques that use store and reward method and store and forward method.Computation of the multi-modular exponentiation can be performed by three novel algorithms:store and reward,store and forward 1-bit(SFW1),and store and forward 2-bit(SFW2).Hardware realizations of the proposed algorithms are analyzed in terms of throughput and energy.The experimental results show the proposed algorithms SFW1 and SFW2 increase the throughput by orders of 3.98% and 4.82%,reducing the power by 5.32% and 6.15% and saving the energy in the order of 3.95% and 4.75%,respectively.The proposed techniques can prevent possible side-channel attacks and timing attacks as a consequence of an inbuilt confusion mechanism.Xilinx Vivado-21 on Virtex-7 evaluation board and integrated computer application for recognizing user services(ICARUS)Verilog simulation and synthesis tools are used for field programmable gate array(FPGA)for hardware realization.The hardware compatibility of proposed algorithms has also been checked using Cadence for application specific integrated circuit(ASIC).展开更多
It is well known that almost all subset sum problems with density less than 0.9408… can be solved in polynomial time with an SVP oracle that can find a shortest vector in a special lattice.In this paper,the authors s...It is well known that almost all subset sum problems with density less than 0.9408… can be solved in polynomial time with an SVP oracle that can find a shortest vector in a special lattice.In this paper,the authors show that a similar result holds for the k-multiple subset sum problem which has k subset sum problems with exactly the same solution.Specially,for the single subset sum problem(k=1),a modified lattice is introduced to make the proposed analysis much simpler and the bound for the success probability tighter than before.Moreover,some extended versions of the multiple subset sum problem are also considered.展开更多
文摘Based on the analysis of several familiar large integer modular multiplication algorithms, this paper proposes a new Scalable Hybrid modular multiplication (SHyb) algorithm which has scalable operands, and presents an RSA algorithm model with scalable key size. Theoretical analysis shows that SHyb algorithm requires m 2 n /2 + 2miterations to complete an mn-bit modular multiplication with the application of an n-bit modular addition hardware circuit. The number of the required iterations can be reduced to a half of that of the scalable Montgomery algorithm. Consequently, the application scope of the RSA cryptosystem is expanded and its operation speed is enhanced based on SHyb al- gorithm.
基金Supported by the National Natural Science Foun-dation of China (60373087)
文摘Modular arithmetic is a fundamental operation and plays an important role in public key cryptosystem. A new method and its theory evidence on the basis of modular arithmetic with large integer modulus-changeable modulus algorithm is proposed to improve the speed of the modular arithmetic in the presented paper. For changeable modulus algorithm, when modular computation of modulo n is difficult, it can be realized by computation of modulo n-1 and n-2 on the perquisite of easy modular computations of modulo n-1 and modulo n-2. The conclusion is that the new method is better than the direct method by computing the modular arithmetic operation with large modulus. Especially, when computations of modulo n-1 and modulo n-2 are easy and computation of modulo n is difficult, this new method will be faster and has more advantages than other algorithms on modular arithmetic. Lastly, it is suggested that the proposed method be applied in public key cryptography based on modular multiplication and modular exponentiation with large integer modulus effectively
基金the Hi-Tech Research and DevelopmentProgram of China(863)(No.2003AA1Z1060).
文摘A new structure of bit-parallel Polynomial Basis(PB)multiplier is proposed,which isbased on a fast modular reduction method.The method was recommended by the National Instituteof Standards and Technology(NIST).It takes advantage of the characteristics of irreducible polyno-mial,i.e.,the degree of the second item of irreducible polynomial is far less than the degree of thepolynomial in the finite fields GF(2m).Deductions are made for a class of finite field in which trino-mials are chosen as irreducible polynomials.Let the trinomial bex m +x k+1,where 1 ≤k≤?m/2?.??The proposed structure has shorter critical path than the best known one up to date,whilethe space requirement keeps the same.The structure is practical,especially in real time crypto-graphic applications.
文摘RSA(Rivest-Shamir-Adleman)public-key cryptosystem is widely used in the information security area such as encryption and digital signature. Based on the modified Montgomery modular multiplication algorithm, a new architecture using CSA(carry save adder)was presented to implement modular multiplication. Compared with the popular modular multiplication algorithms using two CSA, the presented algorithm uses only one CSA, so it can improve the time efficiency of RSA cryptoprocessor and save about half of hardware resources for modular multiplication. With the increase of encryption data size n, the clock cycles for the encryption procedure reduce in (T(n^2),) compared with the modular multiplication algorithms using two CSA.
文摘In order to make the typical Montgomery’s algorithm suitable for implementation on FPGA, a modified version is proposed and then a high-performance systolic linear array architecture is designed for RSA cryptosystem on the basis of the optimized algorithm. The proposed systolic array architecture has dis- tinctive features, i.e. not only the computation speed is significantly fast but also the hardware overhead is drastically decreased. As a major practical result, the paper shows that it is possible to implement public-key cryptosystem at secure bit lengths on a single commercially available FPGA.
基金the DST of India for sponsoring this project under Interdisciplinary Cyber Physical Systems(ICPS)Division individual category with reference number:DST/ICPS/CPSIndividual/2018/895(G)(T-895).
文摘The present paper proposes a secure design of the energy-efficient multi-modular exponential techniques that use store and reward method and store and forward method.Computation of the multi-modular exponentiation can be performed by three novel algorithms:store and reward,store and forward 1-bit(SFW1),and store and forward 2-bit(SFW2).Hardware realizations of the proposed algorithms are analyzed in terms of throughput and energy.The experimental results show the proposed algorithms SFW1 and SFW2 increase the throughput by orders of 3.98% and 4.82%,reducing the power by 5.32% and 6.15% and saving the energy in the order of 3.95% and 4.75%,respectively.The proposed techniques can prevent possible side-channel attacks and timing attacks as a consequence of an inbuilt confusion mechanism.Xilinx Vivado-21 on Virtex-7 evaluation board and integrated computer application for recognizing user services(ICARUS)Verilog simulation and synthesis tools are used for field programmable gate array(FPGA)for hardware realization.The hardware compatibility of proposed algorithms has also been checked using Cadence for application specific integrated circuit(ASIC).
基金supported by the National Natural Science Foundation of China under Grant Nos.11201458,11471314in part by 973 Project under Grant No.2011CB302401in part by the National Center for Mathematics and Interdisciplinary Sciences,Chinese Academy of Sciences
文摘It is well known that almost all subset sum problems with density less than 0.9408… can be solved in polynomial time with an SVP oracle that can find a shortest vector in a special lattice.In this paper,the authors show that a similar result holds for the k-multiple subset sum problem which has k subset sum problems with exactly the same solution.Specially,for the single subset sum problem(k=1),a modified lattice is introduced to make the proposed analysis much simpler and the bound for the success probability tighter than before.Moreover,some extended versions of the multiple subset sum problem are also considered.