An Analysis on efficient polynomial multiplication algorithms for cryptographic purposes

Date

2016

Author

İlter, Murat Burhan

Metadata

Show full item record

Item Usage Stats

165
views

0
downloads

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(n^2)$. 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.

Subject Keywords

Cryptography., Computer algorithms., Public key cryptography.

URI

http://etd.lib.metu.edu.tr/upload/12620448/index.pdf
https://hdl.handle.net/11511/25978

Collections

Graduate School of Applied Mathematics, Thesis

Suggestions

OpenMETU
Core

On the trace based public key cryptosystems over finite fields Ashraf, Muhammad; Akyıldız, Ersan; Kırlar, Barış Bülent; Department of Cryptography (2013) In this thesis, the trace based Public Key Cryptosystems (PKC) are explored from theoretical and implementation point of view. We will introduce cryptographic protocols for the ones they are not discussed yet. We introduce improved trace based exponentiation algorithm for fifth degree recursive relation. The Discrete Log Problem (DLP), that is computing $x$, given $y=\alpha^x$ and $<\alpha>=G\subset \F_q^*$, based Public Key Cryptosystems (PKC) are being studied since late 1970's. Such development of PKC wa...
FGPA based cryptography computation platform and the basis conversion in composite finite fields Sial, Muhammad Riaz; Akyıldız, Ersan; Department of Cryptography (2013) In the study of this thesis work we focused on the hardware based cryptographic algorithms computation platform, especially for elliptic-curve and hyper-elliptic curve based protocols. We worked for making the hyperelliptic curve based Tate Pairing computation efficient specially for hardware implementations. To achieve this one needs to make the underlying finite field arithmetic implementations efficient. For this we study the finite fields of type $\mathbb{F}_q, q=p^{2pn}$ from the efficient implementati...
On provable security of some public key encryption schemes Hanoymak, Turgut; Akyıldız, Ersan; Selçuk, Ali Aydın; Department of Cryptography (2012) In this thesis, we analyse the security criteria of some public key encryption schemes. In this respect, we present the notion of adversarial goals and adversarial capabilities. We give the definition of provably security by means of several games between the challenger and the adversary in some security models, namely the standard model and the random oracle model. We state the main differences between these two models and observe the advantage of the success probability of the adversary in breaking the cr...
An efficient RSA public key encryption scheme Aboud, Sattar J.; AL-Fayoumi, Mohammad A.; Al-Fayoumi, Mustafa; Jabbar, Haidar S. (2008-04-09) In this paper, we propose an efficient RSA public key encryption scheme, which is an improved version of original RSA scheme. The proposed RSA encryption scheme is based on linear group over the ring of integer mod a composite modulus n which is the product of two distinct prime numbers. In the proposed scheme the original message and the encrypted message are h x h square matrices with entities in z(n) indicated via l(h,z(n)). Since the original RSA Scheme is a block cipher in which the original message an...
Analysis of Block Recombination and Lazy Interpolation Methods and Their Applications to Saber Aksoy, Berkin; Cenk, Murat (2022-01-01) Since the beginning of the National Institute of Standards and Technology (NIST), The Post-Quantum Cryptog-raphy (PQC) Standardization Process, efficient implementations of lattice-based algorithms have been studied extensively. Lattice-based NIST PQC finalists use polynomial or matrix-vector multiplications on the ring with type Zq [x]/f(x). For convenient ring types, Number Theoretic Transform (NTT) can be used to perform multiplications as done in Crystals-KYBER among the finalists of the NIST PQC Standa...

Citation Formats

M. B. İlter, “An Analysis on efficient polynomial multiplication algorithms for cryptographic purposes,” M.S. - Master of Science, Middle East Technical University, 2016.