Süpereliptik eğriler ile çarpanlara ayırma yöntemi

Abstract

Günümüzde yaşanan teknolojik gelişmeler sonucunda gerek günlük hayatta gerekse profesyonel iş hayatında kullanılan tüm sistemler internet ve makinalara bağımlı hale gelmiştir. Her türlü bankacılık, hastane randevu, tahlil görüntüleme, üniversite kayıt vb. gibi işlemleri artık internet aracılığı ile gerçekleştiriyoruz. İnternet hayatımızı bu kadar kolaylaştırıp bize zaman kazandırırken, aynı zamanda güvenlik sorununu da gün yüzüne çıkartmaktadır.İnternet üzerinde iletişimi sağlamak için belirli adımlar bulunmaktadır. Bir ağ üzerindeki iki makinanın haberleşmesi için en temel olarak birbirlerinini tanımaları gerekmektedir. Bu tanıma işleminin de güvenli bir şekilde gerçekleştirilmelir. Kimlik doğrulama işleminin (authentication) güvenli bir şekilde gerçekleştirilmesinden sonra iletişime devam edilebilir ve yapılmak istenen ilgili işlemler tamamlanabilir. Ancak kimlik doğrulama aşaması internet üzerinde güvenli iletişim için ilk ve temel adımdır. Bu aşamanın güvenli bir şekilde kontrol edilmemesi durumunda kötü niyetli kişilere davetiye çıkartılmış olur. Günümüzde bir çok veri kaybı yaşanmasına ve kişisel bilgilerin çalınmasına sebep olarak güvenilir olmayan web sitelerde önemli bilgilerin paylaşılmasıdır. Bu tarz saldırı ve kayıpların önüne geçmek adına güçlü kriptografik algoritmalar ile güvenlik sağlanmalıdır.Hali hazırda internet tarayıcılarının güvenliği sağlamak adına kullandığı algoritmalar bulunmaktadır. Bu algoritmalardan en çok kulanılanı RSA algoritmasınıdır. RSA şifreleme tekniği günümüzde özellikle internet tarayıcılarının SSL protokollerinde kullanılan bir tekniktir ve bu algoritmanın zorluğu temelde bir tam sayının çarpanlarına ayrılmasının zorluğuna dayanmaktadır.Çarpanlara ayırma konusu yüzyıllardır merak konusu olmuştur ve bir çok kişi tarafından bu alanda çalışmalar yapılmıştır ve halen devam etmektedir. Pek çok algoritma geliştirilmiş olmasına rağmen günümüz şartları gözönüne alındığında bu algoritmalar RSA'de kullanılan sayılar için yetersiz kalmaktadır. RSA'in en az 1024xviiibitlik anahtarlar kullandığı düşünülürse, bu denli büyük bir sayının çarpanlarına ayrılması için bilgisayarların ve özellikle yüksek başarımlı hesaplama sistemlerinin devreye girmesi zorunlu bir hal almıştır.Bu çalışmada çeşitli çarpanlara ayırma algoritmalarını inceleyerek temelde Lenstra'nın eliptik eğriler ile çarpanlara ayırma yöntemi açıklanacaktır. Sonrasında bu yöntemin süpereliptik eğriler kullanılarak geliştirdiğimiz versiyonu anlatılacaktır. Geliştirdiğimiz yöntemin avantaj ve dezavantajları tartışılacaktır. Bu tezdeki algoritma tamamen paralelleşebilen bir yapıya sahip olduğundan HPC sistemlerine kolayca adapte edilebilir ve verimlilik sağlanabilecektir. Yapılan çalışmaların kodlama aşamasında PARI kütüphanesinden faydalanılmış ve C++ programlama dili kullanılmıştır.

As a result of technological developments in this digital age, all systems that are used in professional bussines life and daily life have become dependent on internet. Almost all kind of operations in our daily life such as banking, hospital appointments, university registration is carried out via internet. Although internet makes our life so easy and saves our time, it also brings out the security problem.There are some certain steps to ensure communication on the Internet. Basically, two machines on a network need to know each other for communication. This recognition process should also be performed safely. After the authentication step is carried out safely, the communication can be continued and related operations can be completed. As long as authentication step is not controlled and completed securely, the system will be vulnerable against adversaries. Therefore, if important informations are shared through suspicious and probably unsecure network systems, a large amount of data loss can be occured and personel information can be stolen. So, security should be ensured with strong cryptographic algorithms to prevent such attacks and data losses.Currently, there are algorithms used by internet browsers to provide security. RSA algorithm is the most commonly used algorithm for especially authentication by the browsers. For example RSA method is used in transportation protocol with SSL. The vulnerability of this algorithm mainly depends on hardness of factorization of large integers.Integer factorization has been popular topic for centuries and many people have been worked on this field and also many are still working. Although many algorithms have been developed, these algorithms are weak considering today's conditions. Considering that RSA uses at least 1024-bit keys, computers and especially high-performance computing systems have to be become a part of this research area in order to factor out such a large number.xxIn this work, many different methods about factorization have been investigated and Lenstra 's elliptic curves method have been explained. After this general explanations, a factorization algorithm has been presented. The algorithm is similar to Lenstra's method but it mainly uses super elliptic curves. The elements of super elliptic curve come from jacobian groups of curve and they are named as ideal. As we know from Lenstra's method, to find a factor we have to compute a certain power of chosen ideal. If there exist any difference between the elements of ideal when trying to compute, a factor is found. In the superelliptic curves, the number of ideal elements increase in direct proportion to the degree of curve. For example, there exist 6 polynomials in the ideal of 3th degree curves and 15 in the ideal of 5th degree curves. In the hyperelliptic curve method, ideals occur the pairs, so the chance to catch a degree difference is lower than superelliptic curves. Hence, superelliptic curves are investigated and used in this work to increase the possibility of detection a factor.Then, advantages and disadvantages of our algorithm, which employes supereliptic curves as an improved version of Lenstra's method, has been explained. C ++ programming language with PARI library have been used in our experiments. In addition, the improved algorithm is embarrasingly parallel, so it can be easily adapted to the HPC environments.