Бүтүн сандык факторизация алгоритмдери. эмпирикалык иш жүзүнө ашыруу жана иштөө убактысын анализдөө

Abstract

Көптөгөн ачык ачкычтуу криптосистемалардын негизи катары колдонулган натуралдык санды факторизациялоо проблемасы заманбап компьютерлер үчүн да оор маселе болуп саналат. Бул иште 4 алгоритмдин – Тривиалдык бөлүү, Ферма, Поллард rho, Брент алгоритмдеринин программасы 3 жол менен түзүлдү Алгач, С++ тилинде GMP китепканасын колдонуу менен, экинчи жолу графикалык процессорду колдонуу үчүн CUDA архитектурасына С тилинде жана акыркы учур, эч нерсе колдонулбастан С тилинде ар бир алгоритм үчүн программдык код жазылды. Андан соң, алынган программдык жабдыкты колдонуп, бул алгоритмдердин иштөө убактыларын салыштыруу анализин жүргүздүк. Алгоритмдер ар кандай өлчөмдөгү сандарды, ошондой эле факторлорунун ортосунда ар кандай аралык болгон сандарды факторизациялоо үчүн колдонулду.Биздин жыйынтыктар: GMP китепканасын колдонгон учурда 296 биттик санды факторлорго ажыратууда Поллард rho алгоритминин эң бат иштешин, ошол эле учурда, факторлордун ортосундагы аралык кичине болгон учурда Ферма алгоритминин эң бат иштешин көрсөттү. Мындай сандар үчүн Брент алгоритминин жай иштегени байкалды, бирок бул алгоритм Ферма алгоритми натыйжа бере албаган учурларда ийгиликтүү жыйынтык бере алды. CUDA архитектурасын колдонгон учурда параллель эсептөөдө Ферма жана Тривиалдык бөлүү алгоритмдеринин бат иштегенин байкай алдык. Ал эми эч нерсе колдонулбастан С тилинде жазылган программада Брент алгоритминин калган эки учурга салыштырмалуу бир канча эсе бат иштегени байкалды. viiАчкыч Сөздөр: Натуралдык сандын факторизациясы, GMP,Тривиалдык бөлүү, Ферма алгоритми, Поллард rho алгоритми, Брент алгоритми

Kriptoloji, kriptografik sistemler bilimidir. Kriptoloji bilimi kendi içerisinde iki farklı branşa ayrılır. Bunlar Kriptografi; şifreli yazı yazma ve Kriptoanaliz; şifreleri çözme ya da analiz etmedir. Neden Kriptografik sistemleri kullanıyoruz sorusunun cevabı aşağıdaki bilgilerde bulunuyordur: Gizlilik (confidentiality): Bilgiyi görme yetkisi olanlar dışındaki herkesten gizli tutmak. Kimlik denetimi (authentication): İletimi gerçekleştirilen bir mesajın göndericisinin gerçekten gönderen kişi olduğu garantisi.Bütünlük (integrity): Bütünlük bir bağlantının tamamı ya da tek bir veri parçası için, mesajın gönderildiği gibi olduğuna, üzerinde hiçbir değişiklik, ekleme, yeniden düzenleme yapılmadığı garantisi. Kriptoloji, çok eski ve renkli bir geçmişe sahiptir. Tarihten günümüze kadar, bazı şifreleme teknikleri şunlardır: Sezar şifrelemesi Rotor makinesi (Enigma) Açık anahtarlı şifreleme Çırpı fonksiyonları Veri gizleme teknikleri Açık anahtarlı şifreleme tarihi 1976'den başlanıyor, yani 1997'de bir kaç insanın aynı fikirde olduğunu gösteren bilgi yayınlanana kadar öyle olduğuna inanılmıştır. 1976 yılında Whitfield Diffie ve Martin Hellman tarafından `New Directions in Cryptography` isimli makale yayımlanmıştır. Makale kriptografide bir devrim oluşturmakla birlikte, matematik alanında da yeni yöntemlerin oluşmasına ve gelişmesine neden olmuştur. Açık anahtarlı şifreleme, şifre ve deşifre işlemleri için farklı anahtarların kullanıldığı bir şifreleme sistemidir. Haberleşen taraflardan her birinde birer çift anahtar bulunur. Bu anahtar çiftlerini oluşturan anahtarlardan biri gizli xiianahtar diğeri açık (gizli olmayan) anahtardır. Bu anahtarlardan bir tanesiyle şifreleme yapılırken diğeriyle de şifre çözme işlemi gerçekleştirilir. Bu iki anahtar çifti matematiksel olarak birbirleriyle bağlantılıdır. Whitfield Diffie ve Martin Hellman gizli tek yönlü fonksiyon kullanarak açık anahtarlı şifreleme sistemini oluşturmuştur, ama onlar bu işlemi gerçekleştirebilmek için uygun bir fonksiyon teklif etmemiştir. Ancak, 1977 yılında amerikalı uzmanlar: Ron Rivest, Adi Shamir ve Leonard Adleman MIT'de böule bir fonksiyonu bulmuştur. O fonksiyon üzerine uygulanmış sistem 'RSA sistemi' adıyla bilinmiş bir sistemdir. RSA harfleri soyisimlerinin baş harflerini temsil etmektedir. RSA, güvenliği tam sayıları çarpanlarına ayrımanın algoritmik zorluğuna dayanan bir tür Açık anahtarlı şifreleme yöntemidir.Asal çarpanlarına ayırma zor bir problem olarak sayılır. Bu problemin bilinen bir çözümü yoktur. Sayılar çok büyük olduğunda, kuantum olmayan hızlı bir algoritma bilinmemektedir RSA gibi çok sayıda kriptografik protokol bu problemin veya bir benzerinin zorluğuna dayanmaktadır. Bir başka deyişle eğer bir sayıyı hızlı bir şekilde çarpanlara ayırma algoritması bulunsaydı, RSA tabanlı açık anahtar kriptografisi güvenliğini yitirirdi.Aşağıda çarpanlara ayırma algoritmalarının türleri gösterilmiştir: Amaca özel Genel amaçlıAmaca özel bir çarpanlara ayırma algoritmasının çalışma zamanı, çarpanlara ayrılmaya çalışan sayının veya bilinmeyen çarpanlarından birinin özelliklerine bağlıdır. Genel amaçlı çarpanlara ayırma algoritmalarının çalışma süreleri sadece çarpanlarına ayrılacak olan sayının büyüklüğüne bağlıdır.Amaca özel çarpanlara ayırma algoritmaları: Deneme bölmesi Tekerlek çarpanlara ayırma yöntemi Pollard'ın rho algoritması Cebirsel-grup çarpanlara ayırma algoritmaları:Pollard'ın p - 1 algoritması Williams'ın p + 1 algoritması Lenstra eliptik eğri çarpanlara ayırma yöntemi xiii Fermat'ın çarpanlara ayırma metodu Euler'in çarpanlara ayırma metodu Özel sayı cismi eleme yöntemi Bu çalışmada, 4 tane sayıları çarpanlarına ayırma algoritmalarının; Deneme bölmesi, Fermat'ın çarpanlara ayırma metodu, Pollard'ın rho algoritması ve Brent metodu algoritmalarının uygulaması yapılmıştır. Uygulama hem CPU, hem de GPU için ayrı gerçekleştirilmiştir. İlk olarak, CPU üzerindeki uygulama herhangi bir kütüphaneler kullanılmadan, saf C kodu üzerinde yazılmıştır. İkinci, algoritmalar, C++ üzerinde GMP kütüphanesi kullanılarak uygulanmıştır. Son olarak, algoritmalar, GPU'de CUDA mimarisi kullanılarak uygulanmıştır. Uygulama aşamasından sonra, algoritmaların çalışma süreleri ölçülmüştür, karşılaştırılmıştır ve analiz edilmiştir. Algoritmalar, farklı boyutlardaki sayılar ve sayı çarpanlarının arasındaki mesafe farklı olan sayılar için kullanılmıştır.Sonuçlara göre, C++ üzerinde GMP kütüphanesi kullanılmış durumda, faktörler arasındaki mesafeler küçük sayılar için Fermat algoritmasının, aynı zamanda, boyutu 296 bit üzerindeki sayılar için de Pollard'ın rho algoritmasının hızlı çalıştığı gözlemlenmiştir. Brent algoritmasının yukarıda bahsedilen sayılar için yavaş çalışmasına rağmen, Fermat algoritmasının başarısız olduğu, sayıları çarpanlara ayırmada, başarılı olmuştur. Fermat ve Deneme bölmesi algoritmalarının, CUDA mimarisi üzerinde paralel uygulanmasında, hızlı çalışma süresi gözlemlenmiştir. Ancak, saf C uygulamasında, Brent algoritması, diğer uygulamalara göre birkaç kez hızlı çalışmıştır. xivAnahtar Kelimeler: Tam sayıları çarpanlarına ayırma, GMP, Deneme bölmesi, Fermat'ın çarpanlara ayırma metodu, Pollard'ın rho algoritması, Brent metodu algoritması.