Implementasi Algoritme Shor pada Sirkuit Kuantum untuk Cracking Algoritme RSA
DOI:
https://doi.org/10.56706/ik.v16i3.62Keywords:
Qiskit, Quantum Computing, Quantum Gate, RSA, ShorAbstract
Penelitian ini membahas mengenai pemanfaatan teknologi quantum computing berupa sirkuit kuantum modular exponentiation untuk mencari periode dari algoritma Shor yang digunakan untuk memfaktorkan bilangan prima N yang digunakan dalam algoritma RSA. Sirkuit modular exponentiation yang digunakan dalam penelitian ini terdiri dari sirkuit adder, reverse adder, modular adder, reverse modular adder, modular multiplier dan reverse modular multiplier yang didesain menggunakan pendekatan dari VBE. Penelitian ini berhasil mengimplementasikan sirkuit modular exponentiation 8 bit dengan MSB bernilai 1 menggunakan tools open-source SDK Qiskit. Dari pengujian yang dilakukan terhadap nilai N = 143, 187, 209, 221, 247 dan 253 didapatkan hasil bahwa sirkuit kuantum modular exponentiation yang didesain menghasilkan periode yang sesuai dengan akurasi sebesar 100 %. Untuk menguji apakah implementasi algoritma Shor pada penelitian ini berhasil dalam melakukan cracking algoritma RSA maka dilakukan pengujian terhadap sistem yang dibuat dan didapatkan bahwa algoritma Shor berhasil dalam melakukan cracking algoritma RSA dengan cara memfaktorkan bilangan N yang dimasukkan dan menghitung kunci privat dari algoritma RSA.
References
J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum, vol. 2, no. July, pp. 1–20, 2018, doi: 10.22331/q-2018-08-06-79.
H. A. Al-Mohammed, M. S. Al-Ali, and M. Alkaeed, “Quantum Computer Architecture from Non-Conventional Physical Simulation up to Encryption Cracking, Machine Learning Application, and More,” 16th Int. Comput. Eng. Conf. ICENCO 2020, pp. 17–24, 2020, doi: 10.1109/ICENCO49778.2020.9357401.
P. V. Zahorodko, S. O. Semerikov, V. N. Soloviev, A. M. Striuk, M. I. Striuk, and H. M. Shalatska, “Comparisons of performance between quantum-enhanced and classical machine learning algorithms on the IBM Quantum Experience,” J. Phys. Conf. Ser., vol. 1840, no. 1, 2021, doi: 10.1088/1742-6596/1840/1/012021.
S. Nayak, S. Nayak, and J. P. Singh, “An Introduction to Basic Logic Gates for Quantum Computer,” Int. J. Adv. Res. Comput. Sci. Softw. Eng., vol. 3, no. 10, p. 2277, 2013, [Online]. Available: www.ijarcsse.com.
P. N. Singh and S. Aarthi, “Quantum circuits - An application in qiskit-python,” Proc. 3rd Int. Conf. Intell. Commun. Technol. Virtual Mob. Networks, ICICV 2021, no. Icicv, pp. 661–667, 2021, doi: 10.1109/ICICV50876.2021.9388498.
E. H. Shaik and N. Rangaswamy, “Implementation of quantum gates based logic circuits using IBM qiskit,” Proc. 2020 Int. Conf. Comput. Commun. Secur. ICCCS 2020, pp. 1–6, 2020, doi: 10.1109/ICCCS49678.2020.9277010.
C. Gidney and M. Ekerå, “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits,” Quantum, vol. 5, pp. 1–31, 2021, doi: 10.22331/Q-2021-04-15-433.
www.geeksforgeeks.org, “Difference between Bits and Quantum Bits,” 2021. .
V. N. Chernega, O. V. Man’ko, and V. I. Man’ko, “God Plays Coins or Superposition Principle for Classical Probabilities in Quantum Suprematism Representation of Qubit States,” J. Russ. Laser Res., vol. 39, no. 2, pp. 128–139, 2018, doi: 10.1007/s10946-018-9699-z.
D. Aggarwal and U. Maurer, “Breaking RSA Generically is Equivalent to Factoring,” IEEE Trans. Inf. Theory, vol. 62, no. 11, pp. 6251–6259, 2016, doi: 10.1109/TIT.2016.2594197.
V. Mavroeidis, K. Vishi, M. D. Zych, and A. Jøsang, “The impact of quantum computing on present cryptography,” Int. J. Adv. Comput. Sci. Appl., vol. 9, no. 3, pp. 405–414, 2018, doi: 10.14569/IJACSA.2018.090354.
P. Nair, “Quantum Computing in Data Security : A Critical Assessment,” 2020.
K. Li and Q. yu Cai, “Practical Security of RSA Against NTC-Architecture Quantum Computing Attacks,” Int. J. Theor. Phys., vol. 60, no. 8, pp. 2733–2744, 2021, doi: 10.1007/s10773-021-04789-x.
M. Sharma, V. Choudhary, R. S. Bhatia, S. Malik, A. Raina, and H. Khandelwal, “Leveraging the power of quantum computing for breaking RSA encryption,” Cyber-Physical Syst., vol. 7, no. 2, pp. 73–92, 2021, doi: 10.1080/23335777.2020.1811384.
L. Jian et al., “A survey on quantum cryptography,” Chinese J. Electron., vol. 27, no. 2, pp. 223–228, 2018, doi: 10.1049/cje.2018.01.017.
X. Zhou and X. Tang, “Research and implementation of RSA algorithm for encryption and decryption,” Proc. 6th Int. Forum Strateg. Technol. IFOST 2011, vol. 2, pp. 1118–1121, 2011, doi: 10.1109/IFOST.2011.6021216.
V. Bhatia and K. R. Ramkumar, “An Efficient Quantum Computing technique for cracking RSA using Shor’s Algorithm,” 2020 IEEE 5th Int. Conf. Comput. Commun. Autom. ICCCA 2020, pp. 89–94, 2020, doi: 10.1109/ICCCA49541.2020.9250806.
A. Veliche, “Shor ’ s Algorithm and Its Impact On Present-Day Cryptography,” no. Math 4020, pp. 1–19, 2018.
K. K. Soni and A. Rasool, “Cryptographic attack possibilities over RSA algorithm through classical and quantum computation,” Proc. Int. Conf. Smart Syst. Inven. Technol. ICSSIT 2018, no. Icssit, pp. 11–15, 2018, doi: 10.1109/ICSSIT.2018.8748675.
V. Gheorghiu and M. Mosca, “Benchmarking the quantum cryptanalysis of symmetric, public-key and hash-based cryptographic schemes,” pp. 1–19, 2019, [Online]. Available: http://arxiv.org/abs/1902.02332.
H. T. Larasati and H. Kim, “Simulation of modular exponentiation circuit for shor’s algorithm in qiskit,” Proceeding 14th Int. Conf. Telecommun. Syst. Serv. Appl. TSSA 2020, pp. 3–9, 2020, doi: 10.1109/TSSA51342.2020.9310794.
Z. Wang, X. Gou, R. Fu, and Z. Fu, “Quantum Fourier Transform and Its Application in Shor’s Algorithm,” no. Iccia, pp. 275–286, 2020, doi: 10.23977/iccia2020047.
R. LaPierre, “Shor Algorithm,” pp. 177–192, 2021, doi: 10.1007/978-3-030-69318-3_13.
Wikipedia, “Quantum.” https://en.wikipedia.org/wiki/Quantum.
Wikipedia, “Foton.” https://id.wikipedia.org/wiki/Foton.
S. Aralikatti, “Quantum Computing: Challenges and Opportunities,” 2021 4th Int. Conf. Electr. Comput. Commun. Technol. ICECCT 2021, pp. 13–16, 2021, doi: 10.1109/ICECCT52121.2021.9616647.
Qiskit.org, “Quantum State and Qubits.” https://learn.qiskit.org/course/ch-states/introduction.
F. Rioux, P. A. M. P. Adrian, and M. Dirac, “Element of Dirac Notation.”
mathsisfun.com, “Bra-Ket Notation.” https://www.mathsisfun.com/physics/bra-ket-notation.html.
Q. M. Hussein, “Chapter Two: Logic Gates,” no. August, 2020.
V. Vedral, A. Barenco, and A. Ekert, “Quantum networks for elementary arithmetic operations,” vol. 54, no. 1, pp. 147–153, 1996.
C. Intila, B. Gerardo, and R. Medina, “A study of public key ‘e’ in RSA algorithm,” IOP Conf. Ser. Mater. Sci. Eng., vol. 482, no. 1, pp. 0–9, 2019, doi: 10.1088/1757-899X/482/1/012016.
S. Y. Yan, “RSA Public-Key Cryptography BT - Cryptanalytic Attacks on RSA,” S. Y. Yan, Ed. Boston, MA: Springer US, 2008, pp. 55–89.
D. Hutama, “Shor ’ s Algorithm,” 2018.
T. Alexander et al., “Qiskit pulse: Programming quantum computers through the cloud with pulses,” Quantum Sci. Technol., vol. 5, no. 4, 2020, doi: 10.1088/2058-9565/aba404.
Quantum-computing.ibm.com, “IBM Quantum Services.” https://quantum-computing.ibm.com/services?services=systems&systems=yours.
Downloads
Submitted
Accepted
Published
Issue
Section
License
Copyright (c) 2022 Info Kripto
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
