Speeding up Curve25519 using Toeplitz Matrix-vector Multiplication

Date

2018-01-24

Author

Taskin, Halil Kemal
Cenk, Murat

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

84
views

0
downloads

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 discuss the comparison and implementation details. In addition, we evaluate the delay complexity of four-core almost embarrassingly parallel implementation of our algorithm when computations are performed using multi-core systems.

Subject Keywords

Elliptic curve cryptography, Toeplitz matrix-vector multiplication, curve25519

URI

https://hdl.handle.net/11511/31681

DOI

https://doi.org/10.1145/3178291.3178292

Collections

Graduate School of Applied Mathematics, Conference / Seminar

Suggestions

OpenMETU
Core

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 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...
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...
On the generalisation of special moduli for faster interleaved montgomery modular multiplication AKLEYLEK, SEDAT; Cenk, Murat; Özbudak, Ferruh (2013-09-01) In this study, the authors give a generalisation of special moduli for faster interleaved Montgomery modular multiplication algorithm with simplified pre-computational phase for GF(p(n)), where p 2 is a prime number and n is a positive integer. The authors propose different sets of moduli that can be used in elliptic curve crytographic applications and pairing-based cryptography. Moreover, this method also leads to efficient implementations for the elliptic curve parameters given in standards. It is shown t...
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

H. K. Taskin and M. Cenk, “Speeding up Curve25519 using Toeplitz Matrix-vector Multiplication,” 2018, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/31681.