RSA ŞİFRELME SİSTEMİNE KARŞI YENİ BİR ÇARPANLARA AYIRMA SALDIRISI

Cihan MERT, Şadi Evren ŞEKER
1.528 492

Öz


Bu çalışmanın amacı, öncelikli olarak RSA şifreleme yönteminde kullanılan ve iki asal sayının çarpımından oluşan yarı-asal sayıları, çarpanlara ayırmaya yöneliktir. Bu makale kapsamında sık kullanılan ve öne çıkan çarpanlara ayırma yöntemlerinin açıklanması ve performanslarının karşılaştırılması yapılmıştır. Çalışma kapsamında yeni bir çarpanlara ayırma yöntemi önerilmiştir. Ayrıca çarpanlara ayırma yöntemleri, rastgele üretilen asal sayılar üzerinde denenerek yeni önerilen yöntemin başarısı sınanmıştır. Yapılan çalışmalar, RSA yönteminde kullanılan yarı-asal sayılara saldırmak için, önerilen yeni yöntemin, mevcut yöntemlere göre daha avantajlı olduğunu ortaya koymaktadır.

Günümüz şifreleme teknolojilerinin tamamı, matematiksel bir zorluğa dayalı olarak geliştirilmiştir. Örneğin iki sayının çarpılması kolay ancak bir sayının çarpanlarına ayrılması zordur. Benzer şekilde ab şeklinde üst almak kolay ancak tersi olan logaritma hesaplanması zor işlemdir. Bu zorluk, bilgisayar bilimleri açısından işlem karmaşıklığı veya daha açık bir ifadeyle zaman karmaşıklığı olarak ortaya çıkmaktadır. Günümüz şifreleme sistemlerine yapılan saldırıların tamamının bilgisayar tabanlı olduğu düşünülürse, bir sistemin güvenliği ne kadar uzun süre saldırıya dayanabileceği ile ölçülmektedir. En yaygın kullanılan şifreleme algoritmalarından birisi olan RSA, hem logaritma hem de çarpanlara ayırma zorluğu üzerine inşa edilmiştir. Örneğin RSA sistemine yapılacak bir saldırı sırasında kullanılan anahtarın, asal çarpanlarına ayrılması gerekmektedir. Çarpanlara ayırma için ise yıllar boyunca çeşitli yöntemler geliştirilmiştir. Bu yazı kapsamında mevcut çarpanlara ayırma yöntemleri incelenmiş ve bilgisayar üzerinde Java dili ile kodlanarak üretilen 1,000 adet 15 haneli rast gele sayı üzerinde performansları karşılaştırılmıştır. Bu çalışmada kullanılan çarpanlara ayırma yöntemleri, önerilen yeni yönteme ilave olarak, Deneme, Fermat, Eliptik Eğri (elliptic curve method), ikinci dereceden kalbur (quadratic sieve), Eratosthene Sieve (Atkin Kalburu) ve Polllar-Rho yöntemleridir.


Anahtar kelimeler


RSA, Eliptik Eğri, ECC, Ayrık Logaritma, Şifreleme, Kalburlama

Tam metin:

PDF


DOI: http://dx.doi.org/10.18185/eufbed.89538

Referanslar


Akben, S. B., & Subaşı, A. 2005. RSA ve Eliptik Eğri Algoritmasının Performans Karşılaştırması, KSÜ Fen ve Mühendislik Dergisi , 8 (1), 35-40.

Atkin, A. O., & Bernstein, D. J. 2004. Prime sieves using binary quadratic forms, Math. Comp , 73, 1023-1030.

Brumley, D., & Boneh, D. 2003. Remote Timing Attacks are Practical. SSYM'03 Proceedings of the 12th conference on USENIX Security Symposium.

Certicom Corp. Elliptic Curves . (n.d.). Retrieved from http://www.certicom.com/index.php/ecc-tutorial Dubey, M. K., Ratan, R., Verma, N., & Saxena, P. K. 2014. Cryptanalytic Attacks and Countermeasures on RSA. Proceedings of the Third International Conference on Soft Computing for Problem Solving Advances in Intelligent Systems and Computing, 258, pp. 805-819.

Gerver, J. 1983. Factoring Large Numbers with a Quadratic Sieve, Math. Comput. , 41, 287-294.

Lenstra, H. W. 1987. Factoring Integers with Elliptic Curves. Ann. of Math. , 126, 649-673.

Lu, Y., Zhang, R., & Lin, D. 2013. Factoring Multi-power RSA Modulus N = p r q with Partial Known Bits. Information Security and Privacy Lecture Notes in Computer Science. 7959, pp. 57-71. Springer.

McKee, J. 1999. Speeding Fermat’s Factoring Method, Mathematics of Computation , 1729–1738.

Pollard, J. M. 1975. A Monte Carlo method for factorization, BIT Numerical Mathematics , 15 (3), 331-334.

Rivest, R., Shamir, A., & Adleman, L. 1978. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM 21 , 2, 120–126.

Seker, S. E., & Mert, C. 2013. Reverse Factorization and Comparison of Factorization Algorithms in Attack to RSA. ISCIM'13 Proceedings of the International Conference on Scientific Computing, (pp. 881-887). Tiranna, Albania.

Seker S. E., Altun, O., Ayan, U., & Mert, C. 2014. A Novel String Distance Function based on Most Frequent K Characters. International Journal of Machine Learning and Computation (IJMLC) , 4 (2), 177-183.

Trappe, W., & Washington, L. C. 2006. Introduction to Cryptography with Coding Theory. Pearson Prentice Hall. ****