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
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
Faster residue multiplication modulo 521-bit mersenne prime and application to ECC
Download
index.pdf
Date
2017
Author
Ali, Shoukat
Metadata
Show full item record
Item Usage Stats
71
views
89
downloads
Cite This
We present faster algorithms for the residue multiplication modulo 521-bit Mersenne prime on 32- and 64-bit platforms by using Toeplitz Matrix-Vector Product (TMVP). The total arithmetic cost of our proposed algorithms is less than the existing algorithms and we select the ones, 32- and 64-bit residue multiplication, with the best timing results on our testing machine(s). For the 64-bit residue multiplication we have presented three versions of our algorithm along with their arithmetic cost and from implementation point of view, we provide the timing results of each version. The transition from 64- to 32-bit residue multiplication is full of challenges because the number of limbs becomes double and the bitlength of the limbs reduces by half. We propose three technique for 32-bit residue multiplication such that both the arithmetic cost and the timing results of each one is provided. Without use of any intrinsics and SIMD/assembly instructions in our implementation, on Intel(R) Core i5 -- 6402P CPU @ 2:80GHz, we find 136- and 550-cycle for our 64- and 32-bit residue multiplications, respectively. We implement constant-time variable- and fixed-base scalar multiplication on the standard NIST curve P-521 and Edwards curve E-521. Using our residue multiplication(s), we find E-521 more efficient than P-521 especially for variable-base scalar multiplication.
Subject Keywords
Mersenne prime.
,
Residue multiplication.
,
Elliptic curve cryptography.
,
Data encryption (Computer science).
URI
http://etd.lib.metu.edu.tr/upload/12621480/index.pdf
https://hdl.handle.net/11511/26963
Collections
Graduate School of Applied Mathematics, Thesis
Suggestions
OpenMETU
Core
Faster Residue Multiplication Modulo 521-bit Mersenne Prime and an Application to ECC
Ali, Shoukat; Cenk, Murat (2018-08-01)
We present faster algorithms for the residue multiplication modulo 521-bit Mersenne prime on 32- and 64-bit platforms by using Toeplitz matrix-vector product. The total arithmetic cost of our proposed algorithms is less than that of existing algorithms, with algorithms for 64- and 32-bit residue multiplication giving the best timing results on our test machine. The transition from 64- to 32-bit implementation is full of challenges because the number of limbs doubles and the limbs' bitlengths are cut in half...
A New Algorithm for Residue Multiplication Modulo 2(521)-1
Ali, Shoukat; Cenk, Murat (2016-12-02)
We present a new algorithm for residue multiplication modulo the Mersenne prime p = 2(521) - 1 based on the Toeplitz matrix-vector product. For this modulus, our algorithm yields better result in terms of the total number of operations than the previously known best algorithm of Granger and Scott presented in Public Key Cryptography (PKC) 2015. We have implemented three versions of our algorithm to provide an extensive comparison - according to the best of our knowledge with respect to the well-known algori...
Faster Montgomery modular multiplication without pre-computational phase for some classes of finite fields
Akleylek, Sedat; Cenk, Murat; Özbudak, Ferruh (2010-09-24)
In this paper, we give faster versions of Montgomery modular multiplication algorithm without pre-computational phase for GF(p) and GF(2 m ) which can be considered as a generalization of [3], [4] and [5]. We propose sets of moduli different than [3], [4] and [5] which can be used in PKC applications. We show that one can obtain efficient Montgomery modular multiplication architecture in view of the number of AND gates and XOR gates by choosing proposed sets of moduli. We eliminate precomputational phase wi...
Speeding up Curve25519 using Toeplitz Matrix-vector Multiplication
Taskin, Halil Kemal; Cenk, Murat (2018-01-24)
This paper proposes a new multiplication algorithm over F-2(255)-19 where the de-facto standard Curve25519 [2] algorithm is based on. Our algorithm for the underlying finite field multiplication exploits the Toeplitz matrix-vector multiplication and achieves salient results. We have used a new radix representation that is infeasible when used with schoolbook multiplication techniques but has notable advantages when used with Toeplitz matrix-vector multiplication methods. We present the new algorithm and dis...
Improved three-way split formulas for binary polynomial multiplication
Cenk, Murat; Hasan, M. Anwar (2011-08-12)
In this paper we deal with 3-way split formulas for binary field multiplication with five recursive multiplications of smaller sizes. We first recall the formula proposed by Bernstein at CRYPTO 2009 and derive the complexity of a parallel multiplier based on this formula. We then propose a new set of 3-way split formulas with five recursive multiplications based on field extension. We evaluate their complexities and provide a comparison.
Citation Formats
IEEE
ACM
APA
CHICAGO
MLA
BibTeX
S. Ali, “Faster residue multiplication modulo 521-bit mersenne prime and application to ECC,” Ph.D. - Doctoral Program, Middle East Technical University, 2017.