An analysis on efficient polynomial multiplication algorithms for cryptographic purposes

Abstract

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.

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 KeyCryptography algorithm, came into play. In this algorithm, modular exponentiation ishighly costly. In addition to this, key sizes of public key cryptography algorithms hasbecome 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 onesin Symmetric Key Cryptography algorithms. However, Public Key Cryptography algorithmshave a wide area of utilization. Thus, it is highly crucial to accelerate thesealgorithms. Making use of fast multiplication algorithms is an effective way to reducethe cost.In this thesis, the main point is to analyze some multiplication algorithms with respectto their time complexities. Before the invention of Karatsuba method, time complexityof multiplying two polynomials was known to be O(n2). After this invention lots ofresearch has been done in this field. For example, Fast Fourier Transform is used fordesigning fast multiplication algorithms. However, this method is not efficient enoughfor cryptographic demands in today's world. For this reason, existing methods such asKaratsuba and its variations, Montgomery, and hybrid methods are investigated.