Faster Montgomery modular multiplication without pre-computational phase for some classes of finite fields

Date

2010-09-24

Author

Akleylek, Sedat
Cenk, Murat
Özbudak, Ferruh

Metadata

Show full item record

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

Item Usage Stats

197
views

0
downloads

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 with proposed sets of moduli. These methods are easy to implement for hardware.

Subject Keywords

Montgomery modular multiplication, Elliptic curve cryptography, Public key cryptography, VLSI implementation

URI

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

DOI

https://doi.org/10.1007/978-90-481-9794-1_75

Collections

Graduate School of Applied Mathematics, Conference / Seminar

Suggestions

OpenMETU
Core

Efficient interleaved Montgomery modular multiplication for lattice-based cryptography AKLEYLEK, SEDAT; Tok, Zaliha Yuce (2014-01-01) In this paper, we give modified version of interleaved Montgomery modular multiplication method for lattice-based cryptography. With the proposed algorithms, we improve the multiplication complexity and embed the conversion operation into the algorithm with almost free cost. We implement the proposed methods for the quotient ring (Z/qZ)[x]/(x(n) - 1) and (Z/pZ)[x]/(x(n) + 1) on the GPU (NVIDIA Quadro 600) using the CUDA platform. NTRUEncrypt is accelerated approximately 35% on the GPU by using the proposed ...
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...
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...
Sparse polynomial multiplication for lattice-based cryptography with small complexity Akleylek, Sedat; Alkim, Erdem; Tok, Zaliha Yuce (2016-02-01) In this paper, we propose efficient modular polynomial multiplication methods with applications in lattice-based cryptography. We provide a sparse polynomial multiplication to be used in the quotient ring (Z/pZ)[x]/(x(n) + 1). Then, we modify this algorithm with sliding window method for sparse polynomial multiplication. Moreover, the proposed methods are independent of the choice of reduction polynomial. We also implement the proposed algorithms on the Core i5-3210M CPU platform and compare them with numbe...
Faster residue multiplication modulo 521-bit mersenne prime and application to ECC Ali, Shoukat; Cenk, Murat; Department of Cryptography (2017) 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 impleme...

Citation Formats

S. Akleylek, M. Cenk, and F. Özbudak, “Faster Montgomery modular multiplication without pre-computational phase for some classes of finite fields,” 2010, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/32216.