Fast algorithms of public key cryptosystem based on Chebyshev polynomials over finite field

doi:10.1016/S1005-8885(10)60049-0

中国邮电高校学报(英文) ›› 2011, Vol. 18 ›› Issue (2): 86-93.doi: 10.1016/S1005-8885(10)60049-0

• Artificial Intelligence • 上一篇下一篇

Fast algorithms of public key cryptosystem based on Chebyshev polynomials over finite field

李智慧¹,崔毅东¹,徐惠民²

1. 北京邮电大学信息与通信工程学院
2. 北京邮电大学电信工程学院

收稿日期:2010-08-05 修回日期:2010-11-09 出版日期:2011-04-30 发布日期:2011-04-15
通讯作者: 崔毅东 E-mail:lizhihui8601@gmail.com
基金资助:
国家973研究计划;国家863计划项目

Fast algorithms of public key cryptosystem based on Chebyshev polynomials over finite field

Received:2010-08-05 Revised:2010-11-09 Online:2011-04-30 Published:2011-04-15
Contact: Cui Yidong E-mail:lizhihui8601@gmail.com

摘要/Abstract

摘要：

The computation of Chebyshev polynomial over finite field is a dominating operation for a public key cryptosystem. Two generic algorithms with running time of have been presented for this computation: the matrix algorithm and the characteristic polynomial algorithm, which are feasible but not optimized. In this paper, these two algorithms are modified in procedure to get faster execution speed. The complexity of modified algorithms is still , but the number of required operations is reduced, so the execution speed is improved. Besides, a new algorithm relevant with eigenvalues of matrix in representation of Chebyshev polynomials is also presented, which can further reduce the running time of that computation if certain conditions are satisfied. Software implementations of these algorithms are realized, and the running time comparison is given. Finally an efficient scheme for the computation of Chebyshev polynomial over finite field is presented.

关键词:

Chebyshev polynomial, algorithm, running time, square root

Abstract:

Key words:

Chebyshev polynomial, algorithm, running time, square root

中图分类号:

TP918

参考文献

1. Kocarev L. Chaos-based cryptography: A brief overview. IEEE Circuits and Systems Magazine, 2001, 1(3): 6-21

2. Pareek N K, Patidar V , Sud K K. A random bit generator using chaotic maps. International Journal of Network Security, 2010, 10 (1): 32-38

3. He B, Luo L Y, Xiao D. A method for generating S-box based on iterating chaotic maps. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2010, 22 (1): 89-93 (in Chinese).

4. Kocarev L, Tasev Z. Public-key encryption based on Chebyshev maps. Proceedings of the International Symposium on Circuits and Systems (ISCAS’03), Vol 3, May 25-28, 2003, Bangkok, Thailand. Los Alamitos, CA, USA: IEEE Computer Society, 2003: 28-31

5. Bergamo P, D’Arco P, Santis A D, et al. Security of public-key cryptosystems based on Chebyshev polynomials. IEEE Transactions on Circuits and Systems I: Regular Papers, 2005, 52(7): 1382-1393

6. Fee G J, Monagan M B. Cryptography using Chebyshev polynomials. Proceedings of the Maple Summer Workshop (MSW’04), Jul 11-14, 2004, Burnaby, Canada. 2004: 15p

7. Kocarev L, Tasev Z, Amato P, et al. Encryption process employing chaotic maps and digital signature process. United States Patent 6892940. 2005

8. Kocarev L, Makraduli J, Amato P. Public-key encryption based on Chebyshev polynomials. Circuits, Systems, and Signal Processing, 2005, 24(5): 497-571

9. Ning H Z, Liu Y, He D Q. Public key encryption algorithm based on Chebyshev polynomials over finite fields. Proceedings of the 8th International Conference on Signal Processing (ICSP’06): Vol 4, Nov 16-20, 2006, Beijing, China. Piscataway, NJ, USA: IEEE, 2006: 4p

10. Elgamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 1985, 31(4): 469-472

11. Lima J B, Campello de Souza R M, Panario D. Security of publickey cryptosystems based on Chebyshev polynomials over prime finite fields. Proceedings of the IEEE International Symposium on Information Theory (ISIT’08), Jul 6-11, 2008, Toronto, Canada. Piscataway, NJ, USA: IEEE, 2008: 1843-1847

12. Wang D H, Yang H Z, Yu F S, et al. A new key exchange scheme based on Chebyshev polynomials. Proceedings of the Congress on Image and Signal Processing (CISP’08), May 27-30, 2008, Sanya, China. Piscataway, NJ, USA: IEEE, 2008: 124-127

13. Wang D H, Hu Z G, Tong Z J, et al. An identity authentication system based on Chebyshev polynomials. Proceedings of the 1st International Conference on Information Science and Engineering (ICISE’09), Dec 26-28, 2009, Nanjing, China. Piscataway, NJ, USA: IEEE, 2010: 1648-1650

14. Wang X Y, Zhao J F. An improved key agreement protocol based on chaos. Communications in Nonlinear Science and Numerical Simulation, 2010, 15(12): 4052-4057

15. Menezes A J, Van Oorschot P C, Vanstone S A. Handbook of applied cryptography. New York, NY, USA: CRC Press, 1997

16. Muller S. On the Computation of square roots in finite fields. Designs, Codes and Cryptography, 2004, 31 (3): 301-312

1. Kocarev L. Chaos-based cryptography: A brief overview. IEEE Circuits and Systems Magazine, 2001, 1(3): 6?21 2. Pareek N K, Patidar V , Sud K K. A random bit generator using chaotic maps. International Journal of Network Security, 2010, 10 (1): 32?38 3. He B, Luo L Y, Xiao D. A method for generating S-box based on iterating chaotic maps. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2010, 22 (1): 89?93 (in Chinese). 4. Kocarev L, Tasev Z. Public-key encryption based on Chebyshev maps. Proceedings of the International Symposium on Circuits and Systems (ISCAS’03), Vol 3, May 25?28, 2003, Bangkok, Thailand. Los Alamitos, CA, USA: IEEE Computer Society, 2003: 28?31 5. Bergamo P, D’Arco P, Santis A D, et al. Security of public-key cryptosystems based on Chebyshev polynomials. IEEE Transactions on Circuits and Systems I: Regular Papers, 2005, 52(7): 1382?1393 6. Fee G J, Monagan M B. Cryptography using Chebyshev polynomials. Proceedings of the Maple Summer Workshop (MSW’04), Jul 11?14, 2004, Burnaby, Canada. 2004: 15p 7. Kocarev L, Tasev Z, Amato P, et al. Encryption process employing chaotic maps and digital signature process. United States Patent 6892940. 2005 8. Kocarev L, Makraduli J, Amato P. Public-key encryption based on Chebyshev polynomials. Circuits, Systems, and Signal Processing, 2005, 24(5): 497?571 9. Ning H Z, Liu Y, He D Q. Public key encryption algorithm based on Chebyshev polynomials over finite fields. Proceedings of the 8th International Conference on Signal Processing (ICSP’06): Vol 4, Nov 16?20, 2006, Beijing, China. Piscataway, NJ, USA: IEEE, 2006: 4p 10. Elgamal T. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 1985, 31(4): 469?472 11. Lima J B, Campello de Souza R M, Panario D. Security of publickey cryptosystems based on Chebyshev polynomials over prime finite fields. Proceedings of the IEEE International Symposium on Information Theory (ISIT’08), Jul 6?11, 2008, Toronto, Canada. Piscataway, NJ, USA: IEEE, 2008: 1843?1847 12. Wang D H, Yang H Z, Yu F S, et al. A new key exchange scheme based on Chebyshev polynomials. Proceedings of the Congress on Image and Signal Processing (CISP’08), May 27?30, 2008, Sanya, China. Piscataway, NJ, USA: IEEE, 2008: 124?127 13. Wang D H, Hu Z G, Tong Z J, et al. An identity authentication system based on Chebyshev polynomials. Proceedings of the 1st International Conference on Information Science and Engineering (ICISE’09), Dec 26?28, 2009, Nanjing, China. Piscataway, NJ, USA: IEEE, 2010: 1648?1650 14. Wang X Y, Zhao J F. An improved key agreement protocol based on chaos. Communications in Nonlinear Science and Numerical Simulation, 2010, 15(12): 4052?4057 15. Menezes A J, Van Oorschot P C, Vanstone S A. Handbook of applied cryptography. New York, NY, USA: CRC Press, 1997 16. Muller S. On the Computation of square roots in finite fields. Designs, Codes and Cryptography, 2004, 31 (3): 301?312

Fast algorithms of public key cryptosystem based on Chebyshev polynomials over finite field

Fast algorithms of public key cryptosystem based on Chebyshev polynomials over finite field

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 0

编辑推荐

Metrics

本文评价