Speeding up Curve25519 using Toeplitz Matrix-vector Multiplication

Taskin H. K., CENK M.

5th Workshop on Cryptography and Security in Computing Systems (CS2), Manchester, Birleşik Krallık, 24 Ocak 2018, ss.1-6 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Doi Numarası: 10.1145/3178291.3178292
  • Basıldığı Şehir: Manchester
  • Basıldığı Ülke: Birleşik Krallık
  • Sayfa Sayıları: ss.1-6
  • Anahtar Kelimeler: elliptic curve cryptography, toeplitz matrix-vector multiplication, curve25519
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.