Abstract
The aim of this study is to factorize semi-prime numbers which are multiplication of two primes and primarily used in RSA encryption method. In this article, commonly used factorization methods are introduced and their performance are compared. A new method of factorization is proposed. Also the success of the new proposed method is tested by testing these factorization methods on randomly generated prime numbers. Studies reveals that the proposed new method has more advantages compared to existing methods in attacking semi-primes numbers used in the RSA method. All of today's encryption technology has been developed on the basis of a mathematical difficulty. For example, multiplying two numbers is easy but factoring a number is difficult. Similarly, taking bth power of a is an easy operation while its inverse operation calculating logarithms is relatively difficult. This difficulty in terms of computer science means complexity of the process or the time complexity. All of the attacks in today's sencryption systems are computer-based so the security of the system is measured by how long it can withstand the attack. RSA which is one of the most widely used cryptographic algorithms hasfactorization and logarithm. For example, the key used during an attack on the RSA system must be factorized into its prime factors. Over the years several methods have been developed for the factorization. In this article some popular current factorizationmethods were examined and their performances were compared on 1000 numbers which are 15-digit randomly generated and coded by using theJava language. Factorization methods used in this study, in addition to the proposed new method, are Trial Division , Fermat, Elliptic Curve, Quadratic Sieve, Atkin Sieve and PolllarRho methods
References
- 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. ****
Abstract
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.
Keywords
References
- 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. ****
Details
| Primary Language | Turkish |
|---|---|
| Journal Section | Makaleler |
| Authors | |
| Publication Date | June 6, 2014 |
| Published in Issue | Year 2014 |