A NOVEL FACTORIZATION ATTACK FOR RSA CRYPTO SYSTEM
Journal Name:
- Erzincan Üniversitesi Fen Bilimleri Enstitüsü Dergisi
Keywords (Original Language):
| Author Name | University of Author | Faculty of Author |
|---|---|---|
Abstract (2. Language):
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 has been built on the difficulty of factorization 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 factorization methods were examined and their performances were compared on 1000 numbers which are 15-digit randomly generated and coded by using the Java 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 Polllar-Rho methods.
Bookmark/Search this post with
Abstract (Original Language):
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.
- 1