Show/Hide Menu
Hide/Show Apps
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Open Science Policy
Open Science Policy
Open Access Guideline
Open Access Guideline
Postgraduate Thesis Guideline
Postgraduate Thesis Guideline
Communities & Collections
Communities & Collections
Help
Help
Frequently Asked Questions
Frequently Asked Questions
Guides
Guides
Thesis submission
Thesis submission
MS without thesis term project submission
MS without thesis term project submission
Publication submission with DOI
Publication submission with DOI
Publication submission
Publication submission
Supporting Information
Supporting Information
General Information
General Information
Copyright, Embargo and License
Copyright, Embargo and License
Contact us
Contact us
An Analysis on efficient polynomial multiplication algorithms for cryptographic purposes
Date
2016
Author
İlter, Murat Burhan
Metadata
Show full item record
Item Usage Stats
219
views
0
downloads
Cite This
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
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
M. B. İlter, “An Analysis on efficient polynomial multiplication algorithms for cryptographic purposes,” M.S. - Master of Science, Middle East Technical University, 2016.