Algorithms for Super Long Integers in Cryptosystems

SU Shenghui; LI Jian; LÜ Shuwang

Article Contents

Article Navigation > Chinese Journal of Electronics > 2013 > 22(2): 258-262

SU Shenghui, LI Jian, LÜ Shuwang, “Algorithms for Super Long Integers in Cryptosystems,” Chinese Journal of Electronics, vol. 22, no. 2, pp. 258-262, 2013,

Citation:

SU Shenghui, LI Jian, LÜ Shuwang, “Algorithms for Super Long Integers in Cryptosystems,” Chinese Journal of Electronics, vol. 22, no. 2, pp. 258-262, 2013,

SU Shenghui, LI Jian, LÜ Shuwang, “Algorithms for Super Long Integers in Cryptosystems,” Chinese Journal of Electronics, vol. 22, no. 2, pp. 258-262, 2013,

Citation:

SU Shenghui, LI Jian, LÜ Shuwang, “Algorithms for Super Long Integers in Cryptosystems,” Chinese Journal of Electronics, vol. 22, no. 2, pp. 258-262, 2013,

PDF( 149 KB)

Algorithms for Super Long Integers in Cryptosystems

1.
College of Computer, Beijing University of Technology, Beijing 100124, China;
2.
College of Information Engineering, Yangzhou University, Yangzhou 225009, China;
3.
Graduate School, Chinese Academy of Sciences, Beijing 100039, China

Funds: This work is supported by the MOST with the projects (No.2007CB311100, No.2009AA01Z441).

Received Date: 2011-02-01
Rev Recd Date: 2012-01-01
Publish Date: 2013-04-25

Abstract

Abstract

Super long integers which exceed the limit of numbers defined in existent computers are widely employed in cryptosystems. In the paper, design 10 algorithms which address operands by the byte, and are used for the operation of unsigned super long integers, including conversion between a binary number and a decimal one, shift, comparison, addition, subtraction, multiplication, division, and modular power, analyze the time complexity of each of the algorithms in the amount of bit operations, offer the source code of the modular power operation in C, and give some examples which are utilized for validating the correctness of the algorithms according to the properties of a group.
- Cryptosystem,
- Super long integer,
- Algorithm,
- Time complexity,
- Validation

FullText(HTML)

References(16)

References

W. Diffie and M. E. Hellman, "New directions in cryptography", IEEE Transactions on Information Theory, Vol.22, No.6, pp.644-654, 1976.

R.L. Rivest, A. Shamir and L.M. Adleman, "A method for obtaining digital signatures and public-key crypto-systems", Communications of the ACM, Vol.21, No.2, pp.120-126, 1978.

T. ElGamal, "A public-key cryptosystem and a signature scheme based on discrete logarithms", IEEE Transactions on Information Theory, Vol.31, No.4, pp.469-472, 1985.

S. Su and S. Lü, "A public key cryptosystem based on three new provable problems", Theoretical Computer Science, Vol.426- 427, pp.91-117, Apr. 2012.

I.F. Blake, G. Seroussi and N.P. Smart, Elliptic Curves in Cryptography, Cambridge University Press, Cambridge, UK, 1999.

S. Su, Y. Yang, B. Yang et al., "Design and analysis of a hash ring-iterative structure", Chinese Journal of Electronics, Vol.20, No.2, pp.232-236, 2010.

M.T. Goldrich and R. Tamassia, Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, New York, 2001.

H. Davenport, The Higher Arithmetic (7nd ed), Cambri-dge University Press, Cambridge, UK, 1999.

D.Z. Du and K. Ko, Theory of Computational Comple-xity, John Wiley & Sons, New York, 2000.

A.J. Menezes, P. van Oorschot and S. Vanstone, Hand-book of Applied Cryptography, CRC Press, London, UK, 1997.

Y. Gu, Y. Ji, H. Chen and B. Zhao, "Using mobile sinks inWSN: Computational complexity and a theoretical bound", Chinese Journal of Electronics, Vol.20, No.1, pp.147-150, 2011.

J.H. Fetzer, "Program verification: The very idea", Communications of the ACM, Vol.31, No.9, pp.1048-1063, 1988.

G.L. Miller, "Riemann's hypothesis and tests for primality", Journal of Computer Systems Science, Vol.13, No.3, pp.300- 317, 1976.

M.O. Rabin, "Probabilistic algorithm for testing primality", Journal of Number Theory, Vol.12, No.1, pp.128-138, 1980.

V.P. Snaith, Groups, Rings and Galois Theory, World Scientific Publishing, Singapore, 1998.

M.J. Coster, A. Joux, B.A. LaMacchia et al., "Improved lowdensity subset sum algorithms", Computational Complexity, Vol.2, No.2, pp.111-128, 1992.

Relative Articles

Supplements(0)

Cited By

Proportional views