Efficient implementation of TMVP-based prime field multiplication and its applications to ecc

---

Tezin Türü: Doktora

Tezin Yürütüldüğü Kurum: Orta Doğu Teknik Üniversitesi, Uygulamalı Matematik Enstitüsü, Kriptografi Anabilim Dalı, Türkiye

Tezin Onay Tarihi: 2019

Öğrenci: HALİL KEMAL TAŞKIN

Danışman: MURAT CENK

Özet:

The need for faster and practical cryptography is a research topic for decades. For elliptic curve cryptography, which is proposed independently by Koblitz and Miller in 1985 as a more efficient alternative to RSA, the applications of it in real life started after 2000s. Today, most of the popular applications and protocols like Whatsapp, Signal, iOS, Android, TLS, SSH, Bitcoin etc. make use of elliptic curve cryptography. In this thesis, we present a new representation of finite field multiplication which is one of the basic building blocks for the ECC using Toeplitz matrix-vector product (TMVP) and discuss its arithmetic cost and comparison. In addition, we evaluate the delay complexity of the proposed algorithm when computations are performed using multi-core systems. We also describe how to choose proper prime fields that make use of Toeplitz matrices to get faster field arithmetic. Then, we give parameter choice details to select prime fields that support TMVP operations and propose some prime fields to work on. We propose a new multiplication algorithm over F_{2^{255}-19} where the de-facto standard Curve25519 algorithm is based on. The proposed algorithm for the underlying finite field multiplication exploits the TMVP and achieves salient results. We also introduce the safe curve selection rationale and discuss about attacks on ECC. Next, we propose a new curve choice parameter and safe curve generation process. Finally, we introduce the Curve2663 and give details about its implementation and benchmark results and conclude the thesis.