Algoritme Kritpografi RSA Menggunakan Algoritme Schönhage-Strassen
Abstract
The RSA algorithm (Rivest-Shamir-Adleman) is a public key cryptographic algorithm used in the process of encrypting symmetric cryptographic keys or private keys. The RSA algorithm relies on the difficulty of finding a large number to factor into prime factors. The RSA algorithm has a slower speed than the symmetric cryptographic algorithm, this means that the multiplication process of the numbers used is very large, more than 1024-bits. The number multiplication process requires special algorithms such as Montgomerry, Karatsuba, and Chinese Remainders. Based on this problem, this research attempts to develop an RSA algorithm library that uses the Schönhage-Strassen algorithm. The library will be developed using the SDLC (Software Development Life Cycle) methodology and the RAD (Ravid Application Development) method. After the library can be developed, the library will be tested with other multiplication algorithms, namely, Montgomerry, Karatsuba, and Chinese Remainder. The test results from this study have different values, where the Schönhage-Strassen algorithm has good performance, but not on all key variants.
Keywords: Rivest-Shamir-Adleman; multiplication; Schönhage-Strassen; Software Development Life Cycle; Ravid Application Development.
Abstrak
Algoritme RSA (Rivest-Shamir-Adleman) merupakan algoritme kriptografi kunci publik yang digunakan pada proses enkripsi kunci kriptografi simetris atau kunci privat. Algoritme RSA mengandalkan sulitnya mencari factor bilangan yang besar menjadi factor-faktor prima. Algoritme RSA memiliki kecepatan yang lebih lambat daripada algoritme kriptografi simetris, hal tersebut proses multiplication bilangan-bilangan yang digunakan sangat besar lebih dari 1024-bit. Proses multiplication bilangan membutuhkan algoritme-algortime khusus seperti Montgomerry, Karatsuba, dan Chinese Remainders. Berdasarkan pada masalah itu penelitian ini mencoba mngembangkan library algoritme RSA yang menggunakan algoritme Schönhage-Strassen. Library akan dikembangkan menggunakan metodologi SDLC (Software Development Life Cycle) dan metode RAD (Ravid Application Development). Setelah library dapat dikembangkan, library akan dilakukan pengujian tingkat eksekusi waktu dengan algoritme multiplication lainya yaitu, Montgomerry, Karatsuba, dan Chinese Remainder. Hasil pengujian dari penelitian ini memiliki nilai yang berbeda-beda, dimana algoritme Schönhage-Strassen memiliki kinerja yang baik, namun tidak pada semua varian kunci.
Kata Kunci: Rivest-Shamir-Adleman; Multiplication; Schönhage-Strassen; Software Development Life Cycle; Ravid Application Development.
References
L. M. Batten, “The RSA Scheme,” in Public Key Cryptography: Applications and Attacks, IEEE, 2013. doi: 10.1002/9781118482261.ch4.
N. Thiranant, Y.S. Lee, & H. Lee, "Performance comparison between RSA and elliptic curve cryptography-based QR code authentication". In 2015 IEEE 29th International Conference on Advanced Information Networking and Applications Workshops, IEEE, pp. 278-282, 2015
J. Kilgallin, & R. Vasko, "Factoring RSA keys in the IoT era. In 2019 First IEEE International Conference on Trust, Privacy and Security in Intelligent Systems and Applications (TPS-ISA), IEEE, pp. 184-189, 2019
L.C.C. Garcıa, "Can Schönhage multiplication speed up the RSA decryption or encryption? Technische Universität Darmstadt, pp. 1-6, 2017
D. Mahto and D. K. Yadav, “RSA and ECC: A Comparative Analysis,” vol. 12, no. 19, p. 9, 2017.
H. Nozaki, M. Motoyama, A. Shimbo, & S. Kawamura, "Implementation of RSA algorithm based on RNS Montgomery multiplication. In Cryptographic Hardware and Embedded Systems—CHES 2001: Third International Workshop Paris, France, May 14–16, Proceedings, Springer Berlin Heidelberg, 3, pp. 364-376, 2020.
Z. Gu and S. Li, "Optimized Interpolation of Four-Term Karatsuba Multiplication and a Method of Avoiding Negative Multiplicands," in IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 69, no. 3, pp. 1199-1209, March 2022, doi: 10.1109/TCSI.2021.3126797.
A. Mantri, A. Razaque, H. Makwana, P. Parekh, and T. Soomro, “Analytical Comparison of RSA and RSA with Chinese Remainder Theorem,” JISR Comput., vol. 14, pp. 16–21, Jan. 2016, doi: 10.31645/jisrc/(2016).14.1.0003.
Sze, T. W. “Schönhage-Strassen algorithm with MapReduce for multiplying terabit integers.” Symbolic-Numeric Computation. pp. 54-62, 2012.
M.M. Asad, I. Marouf, Q.A. Al-Haija, "Review of fast multiplication algorithms for embedded systems design". International Journal of Scientific & Technology Research, vol. 6, no. 8, pp. 238-242, 2017.
S. Covanov, & E. Thomé, "Fast integer multiplication using generalized Fermat primes". Mathematics of Computation, vol. 88, no. 317, pp. 449-1477, 2019.
S. A. Nagar and S. Alshamma, “High speed implementation of RSA algorithm with modified keys exchange,” in 2012 6th International Conference on Sciences of Electronics, Technologies of Information and Telecommunications (SETIT), pp. 639–642, 2012. doi: 10.1109/SETIT.2012.6481987.
Y. Wu and X. Wu, “Implementation of efficient method of RSA key-pair generation algorithm,” in 2017 IEEE International Symposium on Consumer Electronics (ISCE), pp. 72–73, 2017. doi: 10.1109/ISCE.2017.8355552.
E. Ochoa-Jiménez, L. Rivera-Zamarripa, N. Cruz-Cortés, and F. Rodríguez-Henríquez, “Implementation of RSA Signatures on GPU and CPU Architectures,” IEEE Access, vol. 8, pp. 9928–9941, 2020, doi: 10.1109/ACCESS.2019.2963826.
A.M. Fernandes, A. Pai, & L.M.M. Colaco, "Secure SDLC for IoT based health monitor. In 2018 Second International Conference on Electronics, Communication and Aerospace Technology (ICECA), IEEE, pp. 1236-1241, 2018.
P. Beynon-Davies, C. Carne, H. Mackay, & D. Tudhope, "Rapid application development (RAD): an empirical review". European Journal of Information Systems, vol. 8, no. 3, pp. 211-223, 2019.
S. D. Teasley, L. A. Covi, M. S. Krishnan, and J. S. Olson, “Rapid software development through team collocation,” IEEE Trans. Softw. Eng., vol. 28, no. 7, pp. 671–683, Jul. 2012, doi: 10.1109/TSE.2002.1019481.
How To Cite This :
Refbacks
- There are currently no refbacks.
