Efficient RSA Algorithm Designs and Analyses for Computer Security Applications

10.6459/JCM.200803_5(1).0007

C. L. Wu

RSA ； information security ； algorithm design ； cryptosystem ； number theory

危機管理學刊

5卷1期（2008 / 03 / 01）

63 - 70

英文

Most modern cryptographic protocols, which require a large number of processing steps, are based on modular evaluation. In fact modular arithmetic is the most dominant part of the computation which is performed in cryptographic applications especially for RSA encryption system. The operation is time-consuming for large operands. Therefore, a significant problem is how to reduce the time needed to perform modular arithmetic. These algorithms in the modular arithmetic are binary method, common multiplicand multiplication method, and signed-digit recoding method, addition chain method, and Montgomery algorithm. Most importantly, many relevant computer security papers and reports are issued in many journals to describe how to reduce the computational complexities in the cryptosystems.

1. B. Premkumar(2002).A formal framework for conversion from binary to residue numbers.IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing,49(2)
2. D.-C. Lou,C.-C. Chang(1996).Fast exponentiation method obtained by folding the exponent in half.Electronics Letters,32(11),984-985.
3. D.-C. Lou,C.-L. Wu(2004).Parallel exponentiation using common-multiplicand-multiplication and signed-digit-folding techniques.International Journal of Computer Mathematics,81(10),1187-1202.
4. D.-Z. Sun,Z.-F. Cao,Y. Sun(2006).How to compute modular exponentiation with large operators based on the right-to-left binary algorithm.Applied Mathematics and Computation,176(1),280-292.
5. G. Chen,B. Guoqiang,H. Chen(2007).A new systolic architecture for modular division.IEEE Transactions on Computers,56(2),282-286.
6. K. DeJong,W. M. Spears(1989).Using genetic algorithms to solve NPcomplete problems.Proceedings of the Third International Conference on Genetic Algorithms,Morgan Kaufmann:
7. K. Koc,S. Johnson(1994).Multiplication of signed-digit numbers.IEE Electronics Letters,30(11),840-841.
8. Khabbazian M.,Gulliver T. A.(2005).A new minimal average weight representation for left-to-right point multiplication methods.IEEE Transactions on Computers,54(11),1454-1459.
9. Knuth D. E.(1997).Seminumerical Algorithms.MA:Addison-Wesley.
10. Koren,A. K. Peters(2002).Computer Arithmetic Algorithms.MA:Natick.
11. M. E. Kaihara,N. Takagi(2005).A hardware algorithm for modular multiplication/division.IEEE Transactions on Computers,54(1),12-21.
12. N. Nedjah,L. M. Mourelle(2002).Minimal addition chains for efficient modular exponentiation using genetic algorithms.Proceedings of the Fifteenth International Conference on Industrial & Engineering Applications of Artificial Intelligence & Expert Systems, Cairns, Australia, Lecture Notes in Computer Science,Berlin:
13. N. Nedjah,L. M. Mourelle(2002).Efficient parallel modular exponentiation algorithm.Proceedings of the Second International Conference on Information Systems,Izmir, Turkey:
14. R. Katti,X. Ruan(2004).Left-to right binary signed-digit recording for elliptic curve cryptography.Proceedings of the 2004 International Symposium on Circuit and Systems,2,365-368.
15. R. L. Haupt,S. E. Haupt(1998).Practical genetic algorithms.New York:Wiley.
16. R. L. Rivest,A. Shamir,L. Adleman(1978).A method for obtaining digital signatures and public-key cryptosystems.Communications of the ACM,21,120-126.
17. S. Arno,F. S. Wheeler(1993).Signed digit representations of minimal hamming weight.IEEE Transactions on Computers,42(8),1007-1010.
18. S.-M.Yen,C.-S. Laih,A. K. Lenstra(1994).Multi-exponentiation.IEE Proceedings Computer Digital Technology,141(6),325-326.
19. T. Elgamal(1985).A public key cryptosystem and a signature scheme based on the discrete logarithms.IEEE Transactions on Information Theory,31(4),469-472.
20. T. Yamk,E. Savas,C. K. Koc(2002).Incomplete reduction in modular arithmetic.IEE Proceedings: Computers and Digital Technique,149(2),46-52.
21. W. Diffie,M. E. Hellman(1976).New directions in cryptography.IEEE Transactions on Information Theory,22(6),644-654.
22. W.-C. Yang,D. J. Guan,C.-S. Laih(2005).Algorithm of asynchronous binary signed-digit recording on fast multi-exponentiation.Applied Mathematics and Computation,167,108-117.
23. Y.-P. Lai,C.-C. Chang(2003).An efficient multi-exponentiation scheme based on modified Booth's method.Journal of Electronics Engineering,90(3),221-233.