Computational methods for integer factorization

Abstract

Whitfield Diffie ve Martin E. Hellman 1976 yılında geliştirdikleri anahtar değiştirme yöntemiyle kriptografi alanında büyük bir değişikliğe imza attılar. Bu buluşla bilgisayar dünyasının en önemli ödülü olan Turing ödülünün de sahibi olan bilim insanları, geleneksel şifreleme yöntemlerinin aksine biri kapalı (diğer insanların ulaşımına kapalı), diğeri açık (diğer insanların ulaşımına açık) olmak üzere çift anahtarla iletişim halinde olanların yeni bir anahtar oluşturup şifrelemeleri fikrini gündeme getirdiler. Açık anahtar değiştirme yöntemi, üzerinde iletişim kurulan kanal güvenilir olmasa da gizli ortak anahtar oluşmasını sağlar. Diffie ve Hellman'nın geliştirdikleri anahtar değiştirme methodu, 1977 yılında adını onu bulanlardan alan RSA kriptosisteminin de gelişimine sebep oldu. RSA kriptosistemi, adını onu geliştiren Rivest, Shamir ve Adleman'dan almaktadır. Ortaya çıktığı 1977 yılından bu yana RSA kriptosistemi dijital güvenlik dünyasının belkemiği haline gelmiştir. RSA kriptosisteminin güvenilirliğinin altında iki asal sayının çarpımından oluşan bir sayının çarpanlara ayrılmasının zorluğu yatar. Rivest, Shamir ve Adleman'ın sahibi olduğu RSA dijital güvenlik firması, 2007 yılına kadar `RSA Challenge` ismi altında 100 basamaklı ve daha büyük yarı asal sayıların çarpanlarına ayrılmasını teşvik eden bir yarışma düzenliyordu. RSA kriptosistemi ile iletişim kurmak isteyen herkesin iki adet anahtar sahibi olması gerekmektedir. Bu anahtarların bir tanesi açık, bir tanesi kapalı olmalıdır. Anahtarların her biri aslında bir sayıdır, bu sayılardan kapalı olan anahtarın başkalarının eline geçmesi büyük güvenlik sorununa sebep olur. Örneğin kapalı anahtarı ele geçiren kişi, anahtarın asıl sahibiymişçesine başkalarıyla iletişim kurabilir, anahtarın asıl sahibine gelen mesajları okuyabilir. Açık anahtar ise sistemin mantığı itibariyle herkese görünmektedir.RSA kullanarak iletişim kurmak isteyen kişi ilk olarak n yarı asal sayısını seçer, n sayısının çarpanları p ve q asal sayılardır. p ve q sayılarının asallığından emin olmak için asallık testleri yapılmalıdır, Solovay-Strassen Asallık Testi, Fermat Asallık Testi, Miller-Rabin Asallık Testi asallık durumunun kontrolü için kullanılabilir. Fermat Asallık Testi yüksek doğruluk oranına sahiptir, fakat bulmayı garanti ettiği şey asallıktan ziyade asal olmama durumudur. n sayısının faktörlerine ayrılmasının zorluğunun sebebi sayının çok büyük bir sayı olmasıdır. Örneğin Bitcoin için gizli (kapalı) anahtarın uzunluğu 256 bittir. (p-1)*(q-1) sayısından Uzatılmış Öklit Algoritması ile açık anahtar e sayısının çarpmaya göre tersi bulunur. e sayısının çarpmaya göre tersi olan d sayısı kapalı (gizli) anahtardır. Gizli anahtarı bulmak isteyen bir kişinin n yarı asal sayısını çarpanlarına ayırmadan gizli anahtara ulaşması çok zordur. Büyük tam sayıların çarpanlarına ayrılması muazzam bir hesaplama gücü gerektirdiğinden geleneksel bilgisayarlardan çok daha hızlı olan kuantum bilgisayarlarla bu işlemin yapılması çok daha hızlı olacaktır, fakat günümüzde kuantum bilgisayarların yaygınlaşmaması, kuantum bilgisayarlara ulaşımın neredeyse imkansız olması, kuantum bilgisayarlar için tasarlanan algoritmaların geleneksel algoritmalardan farklı olması gerekliliği sebebiyle çalışmalar daha çok geleneksel bilgisayarlar üzerinden yürütülmektedir. Peter Shor'un algoritması adımda n sayısını çarpanlarına ayırabilmektedir. Bu çalışmada üzerinde durulan Daniel Shanks'in yaratıcısı olduğu Shanks Algoritması ise geleneksel Von Neumann Mimarili bilgisayarlarda çalışmaktadır. Shanks Algoritması yaygın olarak kullanılmamaktadır, zira hız ve hesaplama gücünün kritik olduğu bu işlem için çok yavaş kalmaktadır. Shanks Algoritması sayılar teorisinin birtakım kavramları üzerine kurulmuştur. Bu kavramlar arasında grup teorisi, ikili kuadratik formlar gösterilebilir. Nari, Özdemir ve Yaraneri Shanks Algoritmasını geliştirerek ikili kuadratik formların kullanıldığı yeni bir algoritma geliştirmişlerdir. Bu tezde, geliştirilmiş yeni algoritma üzerinde performans karşılaştırılması yapılmıştır. Shanks Algoritması'nın geliştirilmiş hali Özdemir ve Yaraneri'nin ortaya attığı üzere belli bir interval (sayı aralığı) arasından seçilen bir r sayısı ile hızlandırılabilmektedir. Bu interval çarpanlarına ayrılması istenen n sayısının çarpanları p ve q kullanılarak hesaplanmaktadır. Yeterli hesaplama gücüne sahip olunduğunda çarpımlara ayrılması istenen sayıya yakın daha önce çarpanlarına ayrılmış sayılardan yararlanmak mümkün olabilir.İkili kuadratik formlar şeklinde ifade edilir. Bu formun ikili kuadratik form olabilmesi için diskriminant deltanın aşağıdaki koşulları sağlaması gerekmektedir ( ). İlk koşul ∆ mod 4'ün bir veya sıfıra eşit olmasıdır, ikinci koşul ise b sayısının mod 2'de diskriminant deltaya eşit olması zorunluluğudur. a, b, c sayılarının en büyük ortak bölenlerinin 1 olduğu durumda, ikili kuadratik formun ilkel olduğu söylenir. Bu çalışmada da ilkel ikili kuadratik formlar kullanılmıştır. Bu çalışmada, aralarında denklik ilişkisi olan ikili kuadratik formlar kullanılarak yaratılan bir döngü ile yarı asal sayıları çarpanlara ayırma işleminin nasıl yapılabileceği anlatılmaktadır. Bu kadar yüksek hesaplama gücü ve hız gerektiren bir işlemi paralelleştirmek gerekmektedir. Ayrıca, 64 bitten çok daha büyük sayılarla uğraşıldığından klasik double değişkenler bu konuda işe yaramamaktadır. Büyük tam sayıları ifade etmek, onlarla yüksek hızlarda işlemler yapabilmek için GMP kütüphanesi kullanılmıştır. GMP kütüphanesi açık kaynak kodlu ifade edebileceği sayı büyüklüğü teoride sonsuza eşit olan bir kütüphanedir. Tam sayılarla yapılabilecek neredeyse tüm işlemler bu kütüphanede bulunmaktadır. 1991 yılında ilk defa yayınlanmış olan bu kütüphane işlemlerin hızlı olmasına odaklanmıştır ve gönüllülerin katkılarıyla neredeyse her yıl yeni özellikler, hata düzeltmeler ile gelişmeye devam etmektedir, üzerine eklentiler yapılmaktadır.GMP kütüphanesi (özellikle tamsayı fonksiyonları) genellikle kriptografi alanında çalışmalar yapan bilim insanları tarafından aktif olarak güvenle kullanılmaktadır. Bu çalışmada da kullanılan her platformda GMP kütüphanesinin tamsayı fonksiyonlarından faydalanılmıştır.Shanks Algoritması'nın hızlandırıcı çarpanlı yeni versiyonu çeşitli platformlarda denendi. Bu platformlar arasında dünyada en çok bilinen ve on yıllardır aktif olarak kullanılan C++, yeni fakat giderek daha da yaygın olarak kullanılan Julia programlama dili de var. Ayrıca sadece Julia ve C++'ın üzerinde çalıştığı ile CPU değil, GPU üzerinde de CUDA ile çeşitli denemeler yapıldı, fakat sonuçlar yeterince başarılı bulunmadı.GPU üzerindeki denemelerden iyi sonuçlar alınamadı, büyük sayılar için kullanılan GMP kütüphanesinin GPU mimarisi için yazılmış resmi bir kütüphanesi olmadığından Github'daki açık kaynak kodlu projeler üzerinden gidildi. Bulunan GPU üzerinde çalışan cuGMP kütüphanesi ile CPU üzerinde çalışan GMP kütüphanesinin performansları karşılaştırıldığında, CUDA için yazılan cuGMP kütüphanesinin oldukça düşük performanslı olduğu görüldü. Yapılan testlerin sonuçları raporda da yer aldı. C++ ve Julia karşılaştırılması için hem seri, hem paralel kodlar yazıldı. Julia'nın C ve C++ kütüphanelerini rahatlıkla çağırabilmesi sebebiyle Julia kodlarında da büyük tam sayıların temsili, büyük tam sayılarla yapılan işlemler için doğrudan GMP kütüphanesi kullanıldı.C++ ile paralelleştirme için üzerinde 1991 yılından itibaren çalışılan MPI kullanıldı. Artık standartlaşmış bir protokol haline gelmiş olan MPI için yazılmış farklı işletim sistemlerinde çalışan birçok farklı derleyici bulunmaktadır. Paralel işlemcilerin birbirleriyle haberleşmelerini sağlayan MPI için oldukça fazla programlama dilinden çağrılabilen farklı işlevde birçok fonksiyona sahiptir. MPI proses seviyesinde paralelliği sağlamaktadır. Aynı zamanda iplik seviyesinde paralelleştirme imkanı da sağlar. Bu çalışmada ise MPI kütüphanesinin proses seviyesinde paralelleştirme olanaklarından yararlanılmıştır. Julia, okunabilirliği oldukça yüksek olan, dolayısıyla öğrenmesi de kolay olan, popülaritesi giderek artan yeni nesil bir programlama dilidir. An itibariyle internette en çok aranan 21. programlama dili olarak listelerde yer almaktadır. Özellikle yüksek başarımlı hesaplamalar için dizayn edilmiş bu dil, paralel platformlarda C++/MPI kadar yüksek performanslı olmasa da ilerleyen zamanlarda prosesler arası iletişim daha da hızlanırsa birçok alanda C++ popülaritesine ulaşma imkanına sahip olabilir. Seri kodlar karşılaştırıldığında, Julia'nın gücü görülebilmektedir, hesaplama süresi arttıkça Julia performans açısından C++'ı geride bırakmaktadır. Bu tezin de son bölümünde karşılaştırmalar yer almaktadır.Günümüzde giderek artan hesaplama gücü ihtiyacını giderebilmek için artık elimizde birçok farklı programlama dili, standart ve kütüphane bulunmaktadır. Bu çalışmada İTÜ UHEM'in Sarıyer makinasındaki CPU ve GPUlar kullanılarak birtakım karşılaştırmalar yapıldı. Amaç, yarı asal bir sayıyı çarpanlarına ayırmakla beraber bilgisayar dünyasındaki standartları ve yenilikleri karşılaştırarak, hesaplama imkanlarını gözden geçirmektir.

Integer factorization is the task of finding the prime factors of a composite number. Since integer factorization is a computationally expensive task, today many digital security systems rely on its difficulty. Many systems use the difficulty of integer factorization for assuring security. Today, RSA cryptosystem, which takes its name from its inventors, Rivest, Shamir and Adleman, dating back to 1977, is widely used for secure communication. RSA is a public key cryptosystem, which uses two asymmetric keys. The concept of asymmetric keys was firstly presented by Whitfield Diffie and Martin E. Hellman in 1976. Integer factorization has always been an attractive field of research for mathematicians and computer scientists. Many scientists developed algorithms for factoring large integers, however none of them are useful with regard to the limitations of the computational power we have as of today. Daniel Shanks' SQUFOF Algorithm, which was developed using Binary Quadratic Forms is one of the most popular algorithms for integer factorization, however it is not efficient due to the computational power it requires. Nari, Ozdemir and Yaraneri took this algorithm another step further and developed a new algorithm. By using a multiplier which lies within an interval calculated using the factors of the integer, the new algorithm can easily factor large semiprimes. The multiplier selected from the interval accelerates integer factorization. However, finding the interval without knowing the factors is difficult. Some properties of the intervals are studied in this thesis.In this work, new SQUFOF with a multiplier algorithm's parallel and serial versions were implemented on multiple platforms. The platforms include C++ and Julia. C++ is one of the most recognised programming languages in the world due to its widespread usage for decades. In contrast, Julia is a very young programming language with rising popularity. For achieving parallelism on multiple processors, MPI is used on C++, Julia has its own libraries for supporting parallelism. The Distributed.jl library is an open source library, which is suggested for writing parallel code on Julia. Not only CPUs, but also GPUs can be used for parallelism, therefore some experiments with CUDA were conducted. The benchmarks show that the cuGMP library written in C++ for representing Big Integers (integers larger than 64 bits) on GPUs is not successful. Julia is slower than C++ for parallel computations, however, considering its high level features which makes programming easier, it proves itself to be a fast and efficient programming language. C++ with MPI is nearly two times faster than Julia, however writing code in C++ using MPI is a more difficult task than achieving parallelism in Julia. The benchmarks are shown in this thesis.