An analysis on efficient polynomial multiplication algorithms for cryptographic purposes
Kriptografik amaçlar için verimli polinom çarpması üzerine bir analiz
- Tez No: 441919
- Danışmanlar: DOÇ. DR. MURAT CENK
- Tez Türü: Yüksek Lisans
- Konular: Matematik, Mathematics
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2016
- Dil: İngilizce
- Üniversite: Orta Doğu Teknik Üniversitesi
- Enstitü: Uygulamalı Matematik Enstitüsü
- Ana Bilim Dalı: Kriptografi Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 60
Özet
Açık Anahtarlı Kriptografi fikri W. Diffie ve M. Hellman?ın 1976 yılında yürüttüğü çalışmalardan sonra ortaya çıktı. Bu çalışmaların ışığında, ilk Açık Anahtarlı Kriptografi algoritması olan RSA ortaya çıktı. Bu algoritmada, modüler üst alma oldukça maliyetlidir. Buna ek olarak zaman geçtikçe güvenliği sağlamak için Açık-Anahtar Kriptosistem algoritmalarının anahtar uzunlukları artmaktadır. Bu sebeplerden ötürü, Simetrik Anahtarlı Kriptografi algoritmalarının hızıyla karşılaştırıldığında Açık Anahtarlı Kriptografi algoritmalarının hızı daha yavaştır. Buna karşın Açık Anahtarlı Kriptografi algoritmalarının geniş bir kullanım alanı vardır. Bu yüzden bu algoritmaları hızlandırmak oldukça önemlidir. Hızlı çarpma algoritmalarından yararlanmak maliyeti azaltmak için verimli bir yoldur. Bu tezde, ana fikir olarak bazı çarpma algoritmalarını zaman karmaşıklıklarına göre analiz etmektir. Karatsuba metodunun icadından önce iki polinomun çarpımının zaman karmaşıklığı $O(n^2)$ olarak biliniyordu. Bu icattan sonra, bu alanda birçok çalışma yapıldı. Örnek olarak, Hızlı Fourier Dönüşümü hızlı çarpma algoritmalarını tasarlamak için kullanılmıştır. Buna karşılık, bu metot günümüz dünyasında kriptografik talepler için yeterince verimli değildir. Bu sebeple, Karatsuba ve varyasyonları, Montgomery ve hibrid metodları gibi mevcut olan metotlar incelenmektedir.
Özet (Çeviri)
The idea of Public Key Cryptography showed up after the studies conducted by W. Diffie and M. Hellman in 1976. In the light of these works, RSA, the first Public Key Cryptography algorithm, came into play. In this algorithm, modular exponentiation is highly costly. In addition to this, key sizes of public key cryptography algorithms has become longer in order to ensure the security as the time passes. For these reasons, the speed of algorithms is relatively slower when it is compared to the speed of ones in Symmetric Key Cryptography algorithms. However, Public Key Cryptography algorithms have a wide area of utilization. Thus, it is highly crucial to accelerate these algorithms. Making use of fast multiplication algorithms is an effective way to reduce the cost. In this thesis, the main point is to analyze some multiplication algorithms with respect to their time complexities. Before the invention of Karatsuba method, time complexity of multiplying two polynomials was known to be O(n2). After this invention lots of research has been done in this field. For example, Fast Fourier Transform is used for designing fast multiplication algorithms. However, this method is not efficient enough for cryptographic demands in today's world. For this reason, existing methods such as Karatsuba and its variations, Montgomery, and hybrid methods are investigated.
Benzer Tezler
- Efficient batch algorithms for the post-quantum Crystals dilithium signature scheme and Crystals Kyber encryption scheme
Crystals dilithium imza şeması ve Crystals Kyber şifreleme şeması için verimli toplu kuantum ertesi algoritmalar
NAZLI DENİZ TÜRE
Doktora
İngilizce
2024
Bilim ve TeknolojiOrta Doğu Teknik ÜniversitesiKriptografi Ana Bilim Dalı
DOÇ. DR. OĞUZ YAYLA
PROF. DR. MURAT CENK
- Yeni nesil kriptosistemlerin analizi, tasarımı ve verimli uygulamaları
Analysis, design and efficient implementation of next-generation cryptosystems
ERDEM ALKIM
Doktora
Türkçe
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolEge ÜniversitesiMatematik Ana Bilim Dalı
PROF. DR. URFAT NURIYEV
YRD. DOÇ. DR. PETER SCHWABE
- Efficient hardware implementations for lattice-based cryptography primitives
Kafes-tabanlı kriptografi öğeleri için verimli donanım uygulamaları
AHMET CAN MERT
Doktora
İngilizce
2021
Elektrik ve Elektronik MühendisliğiSabancı ÜniversitesiElektronik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ ERDİNÇ ÖZTÜRK
- Faster secure matrix multiplication using the strassen algorithm
Strassen algoritması ile daha hızlı güvenli matris çarpımı
DİLEK ÖNER
Doktora
İngilizce
2023
MatematikOrta Doğu Teknik ÜniversitesiKriptografi Ana Bilim Dalı
PROF. DR. ERSAN AKYILDIZ
PROF. DR. MURAT CENK
- Burun iniş takımı sisteminde shimmy davranışının modellenmesi, analizi, testi ve kontrolü
Modelling, analysis, test, and control of the shimmy behavior in nose landing gear system
SENA KOÇAK
Yüksek Lisans
Türkçe
2021
Havacılık Mühendisliğiİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. ALİ FUAT ERGENÇ