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

Abstract

Daha hızlı ve pratik şifrelemeye duyulan ihtiyaç, onlarca yıldır bir araştırma konusudur. 1985 yılında Koblitz ve Miller tarafından bağımsız olarak RSA'ya daha etkin bir alternatif olarak önerilen eliptik eğri kriptografisinin gerçek hayattaki uygulamaları 2000'li yıllardan sonra başlamıştır. Günümüzde Whatsapp, Signal, iOS, Android, TLS, SSH, Bitcoin gibi popüler uygulamaların ve protokollerin çoğu eliptik eğri kriptosistemler (EEK) kullanmaktadırlar.Bu tez çalışmasında, Toeplitz matris-vektör çarpımını (TMVÇ) kullanarak EEK'nin temel yapı taşlarından birisi olan sonlu cisim çarpımı için yeni bir gösterim sunuyoruz ve bu gösterimin aritmetik maliyetini ve karşılaştırmasını ele alıyoruz. Buna ek olarak, çok çekirdekli sistemler kullanılarak hesaplamalar yapıldığında algoritmamızın gecikme karmaşıklığını hesaplıyoruz. Ayrıca daha hızlı cisim aritmetiği elde etmek için Toeplitz matrislerini kullanabileceğimiz uygun asal cisimlerin nasıl seçileceğini de açıklıyoruz. Ardından, TMVÇ'yi destekleyen asal cisimlerin seçilmesinin ve üzerinde çalışılabilecek asal cisimlerin önerilmesi için parametre seçilmesinin detaylarını veriyoruz. Curve25519 algoritmasının üzerine inşaa edildiği F_{2^{255}-19} sonlu cismi üzerinde TMVÇ kullanan yeni bir çarpma algoritması gösterimi öneriyoruz. Önerdiğimiz bu algoritma dikkat çekici sonuçlar elde etmektedir.Ayrıca güvenli eğri seçimi gerekçelerini ortaya koyup, EEK'ye yapılan ataklar hakkında bilgi veriyoruz. Daha sonra yeni bir eliptik eğri seçim parametresi ve güvenli eliptik eğri üretme sürecini öneriyoruz. Son olarak, Curve2663 eğrisini tanıtıyoruz, gerçeklemesi ve kıyaslama sonuçları hakkında ayrıntılı bilgi veriyoruz ve tezi sonuçlandırıyoruz.

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.