The week's pick
Random Articles
Reseach Article
Enhancing the Time Complexity of Mathematically Intensive Algorithms; the Case of Cryptography
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 185 - Number 8 |
| Year of Publication: 2023 |
| Authors: Paul K. Arhin Jnr, Michael Asante, Linda Otoo |
10.5120/ijca2023922736
|
Paul K. Arhin Jnr, Michael Asante, Linda Otoo . Enhancing the Time Complexity of Mathematically Intensive Algorithms; the Case of Cryptography. International Journal of Computer Applications. 185, 8 ( May 2023), 22-26. DOI=10.5120/ijca2023922736
Abstract
This article aims to compare the performance of the RSA encryption algorithm on two different hardware architectures, namely a CPU and a GPU CUDA. The RSA encryption algorithm is widely used for secure data storage and transmission. The algorithm requires complex mathematical processes that can be computationally demanding and can take significant time to execute, particularly for keys with larger sizes. In this paper, A parallelization technique is proposed in this article, which leverages the capabilities of GPUs to speed up the RSA algorithm. The research is done by experiment using different key sizes to measure the performance of RSA on both platforms; CPU and GPU. The proposed approach involves the parallelization of the most computationally intensive parts of the RSA Algorithm, including modular exponentiation and multiplication. GPU implementation of the RSA algorithm is done using CUDA, a programming model developed by NVIDIA for parallel computing on GPUs. The experimental results show the effectiveness of using GPUs to accelerate the RSA algorithm thus resulting in a faster and more efficient cryptographic solutions. This has significant implications for real-world applications, especially those that are mathematically intensive and demand secure and effective data transmission, like e-commerce, banking, and other financial services.
References
- Rivest, R. L., Shamir, A., & Adleman, L. M. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126
- Dullweber, M., Schoppmann, P., Rechberger, C., & Schrammel, P. (2011). RSA on GPU: Fast factorization and secure implementation. In International Conference on Selected Areas in Cryptography (pp. 205-222). Springer, Berlin, Heidelberg.
- Ananthakrishnan, S., & Mehta, S. (2014). Implementation of RSA on CUDA platform. International Journal of Computer Applications, 93(8), 25-28.
- Dong, Y., Zhang, W., & Liu, X. (2017). GPU-accelerated RSA key generation and encryption. Journal of Supercomputing, 73(10), 4528-4541
- Liu, Y., Sun, Z., Zhang, Q., & Chen, C. (2019). A GPU-accelerated RSA cryptosystem using CUDA. IEEE Access, 7, 114330-114339
- Narula, R., Bonneau, J., Felten, E., Miller, A., & Goldfeder, S. (2016). Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction. Princeton University Press.
- Kumar, P., Srinivasan, S., & Rawat, S. (2018). A comparative study of CPU and GPU performance for RSA algorithm. International Journal of Computer Applications, 181(32), 29-33.
- Wang, Y., Li, H., Li, X., & Li, Z. (2019). Implementation and comparison of RSA algorithm on CPU and GPU platforms. 6th International Conference on Information Technology and Quantitative Management (ITQM).
- Zhang, Y., Wang, X., & Wang, Q. (2021). A comparative study of RSA algorithm performance on CPU and GPU. IEEE International Conference on Computational Science and Engineering (CSE).
- Shen, C., Chen, Y., & Chen, K. (2005). Implementation of RSA cryptosystem on GPU. In International Symposium on Parallel and Distributed Processing and Applications (pp. 839-844). Springer.
- Satoh, A., & Takano, K. (2008). Fast RSA implementation using a GPU with modified sliding-window method. In International Workshop on Cryptographic Hardware and Embedded Systems (pp. 344-360). Springer
- Li, X., Yang, C., & Dai, Y. (2010). A hybrid CPU-GPU implementation of RSA based on OpenCL. In International Conference on High Performance Computing and Communications (pp. 505-510). IEEE.
- Vaidya, S., & Jadhav, A. (2021). GPU-Based Implementation of RSA Algorithm Using Multi-Precision Arithmetic. International Journal of Computer Science and Network Security (IJCSNS), 21(2), 12-20.
- Yu, X., Li, M., Li, J., & Liao, X. (2020). GPU-accelerated RSA encryption algorithm based on Chinese Remainder Theorem. The Journal of Supercomputing, 76(2), 1083-1096. doi: 10.1007/s11227-019-02911-2
- Shoup, Victor. A Computational Introduction to Number Theory and Algebra. Cambridge University Press, 2005
- Crandall, Richard E., and Carl Pomerance. Prime Numbers: A Computational Perspective. Springer Science & Business Media, 2012
- Hankerson, Darrel, Alfred J. Menezes, and Scott Vanstone. Guide to Elliptic Curve Cryptography. Springer Science & Business Media, 2010
- Dwork, Cynthia, and Moni Naor. "On the Practicality of One-Way Functions." Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing. ACM, 1990.
- Katz, Jonathan, and Yehuda Lindell. Introduction to Modern Cryptography. CRC Press, 2014
- Schneier, Bruce. Applied Cryptography: Protocols, Algorithms, and Source Code in C. Wiley, 1996.
- Goldwasser, Shafi, Silvio Micali, and Charles Rackoff. "The Knowledge Complexity of Interactive Proof Systems." SIAM Journal on Computing, vol. 18, no. 1, 1989, pp. 186-208
Index Terms
Keywords