A study on SIMD parallelization in elliptic curve cryptography / Eliptik eğri kriptografisinde SIMD paralelizasyonu üzerine bir çalışma

Abstract

Eliptik eğrilerin kriptografi ve kriptanaliz için büyük önemi vardır. Eliptik eğrilerdeki grup yasası nedeniyle eliptik eğri üzerindeki noktalar üzerinden özel bir toplama, dolayısıyla skaler çarpım yapılabilir. Hatta Montgomery merdiveni gibi skaler çarpma işlemini hızlandırmak için bazı yöntemler de vardır. Bu aritmetik hesaplamaların basit olmasına karşın çarpılan bir koordinatı çarpanlarına ayırmak zorlu bir problemdir. Kriptografi mühendisleri bu problemin zorluğuna güvenirler ve buna göre kriptografik algoritmalar geliştirirler. Kısa Weierstrass, Montgomery, Edwards ve Hessian eğrileri gibi birçok eliptik eğri eliptik eğri kriptografisinde kullanılabilir. Geliştirilen uygulamalara bağlı olarak aralarında avantaj ve dezavantajlar vardır. Bu tezde, isteğe bağlı özellikler alanı üzerinde tanımlanan tüm eliptik eğriler için tek koordinatlı toplama formüllerinin tüm istisnai durumların nasıl ele alınacağı gösterilmiştir. Bunlara dayanarak, bu tez, Brier ve Joye'nin ikiye katlama ve toplama formüllerini kullanarak tüm istisnaları verimli bir şekilde ele alarak kısa Weierstrass eliptik eğrileri üzerinde 4-yollu paralel ve SIMD uyumlu bir Montgomery merdiveni uygulaması sunar. Ayrıca, bu tez Montgomery merdiveni için biri 25519 asalı özelinde ve diğeri daha genel olmak üzere iki uygulama da sunulmuştur. There is great importance of elliptic curves for cryptography and cryptanalysis. Because of the group law on elliptic curves, a special addition, hence scalar multiplication, can be done over the points on the elliptic curve. Even there are some methods to accelerate the speed of scalar multiplication, such as the Montgomery ladder. These arithmetic calculations are straightforward; factoring the multiplied coordinate is a challenging problem. Cryptographic engineers rely on this difficulty of the problem and develop cryptographic algorithms. Multiple elliptic curves are suitable for use in elliptic curve cryptography, such as short Weierstrass, Montgomery, Edwards, and Hessian curves. There are advantages and disadvantages among them, depending on implementations. In this thesis, the single-coordinate addition formulas for all elliptic curves defined over a field of arbitrary characteristics have been shown how to handle all exceptional cases. Based on these, this thesis presents a 4-way parallel and SIMD-friendly Montgomery ladder step on the short Weierstrass form of elliptic curves using Brier and Joye's doubling and addition formulas by handling all exceptions efficiently. Furthermore, this thesis presents two implementations for the Montgomery ladder, one is 25519-prime specific, and the other one is more generic.