Eliptik eğri kriptografisi

Elipktik eğri kriptolojisini kullanmak için, tüm taraflar eliptik eğriyi tanımlayan alan parametreler adı verilen elemanlar üzerinde anlaşmalıdır. Cisim asıl durumda ${\displaystyle p}$ sayısıyla, iki bileşenli durumda ise ${\displaystyle m}$ ve ${\displaystyle f}$ çifti ile tanımlanır. Eliptik eğriler, eşitliği sağlamak için sabit ${\displaystyle a}$ ve ${\displaystyle b}$ sayıları ile tanımlanırlar. Son olarak devirli alt-grup, üreteci olan G ile tanımlanır. Kriptografik uygulamalar için G nin mertebesi, ${\displaystyle nG=\infty }$ denklemini sağlayacak en küçük ${\displaystyle n}$ değeri, genellikle asal bir sayıdır. ${\displaystyle n}$, ${\displaystyle {\displaystyle E(\mathbb {F} _{p})}}$ alt-grubunun büyüklüğü olduğundan Lagrange Teoreminden 8 Nisan 2018 tarihinde Wayback Machine sitesinde arşivlendi. ${\displaystyle {\displaystyle h={\frac {1}{n}}|E(\mathbb {F} _{p})|}}$ sayısı tam sayıdır. Kriptografik uygulamalarda kofaktör olarak adlandırılan bu ${\displaystyle h}$ sayısı, küçük (${\displaystyle h\leq 4}$) bir tam sayı olarak, tercihen ${\displaystyle h=1}$, seçilmelidir. Özetle, asıl durum parametreleri ${\displaystyle (p,a,b,G,n,h)}$ ve ikili durum parametleri ise ${\displaystyle (m,f,a,b,G,n,h)}$ şeklindedir.

Eğer alan parametrelerinin guvenilir bir üretici tarafından oluşturulduğunun garantisi yoksa, bu parametreler kullanilmadan önce mutlaka doğrulanmalıdır.

Alan parametrelerinin oluşturulması genellikle her katılımcı tarafından yapılmaz çünkü bu durum zaman alan ve uygulaması zor olan bir eğri üzerindeki noktaların sayısını hesaplamayı gerektirir. Sonuç olarak, bazı yetkili standardizasyon kuruluşları yaygın cisim boyutları için eliptik eğri parametreleri yayınlamışlardır. Bu gibi alan parametreleri genellikle "standart eğriler" veya "adlandırılmış eğriler" olarak bilinir; Adlandırılmış bir eğri, bir ad veya standart belgelerde tanımlanan benzersiz nesne tanımlayıcısı tarafından referans edilebilir:

• NIST, Devlet İşlerinde Önerilen Eliptik Eğriler 20 Şubat 2018 tarihinde Wayback Machine sitesinde arşivlendi.
• SECG, SEC 2: Önerilen Eliptik Eğri Alan Parametreleri 5 Nisan 2018 tarihinde Wayback Machine sitesinde arşivlendi.
• ECC Brainpool (RFC 5639), ECC Brainpool Standart Eğrileri ve Eğri Üretimi

SECG test vektörleri de mevcuttur. NIST birçok SECG eğrisini onayladı, dolayısıyla NIST ve SECG tarafından yayınlanan özellikler arasında örtüşme vardır. Eliptik Eğri alan parametreleri, değer veya ad ile belirtilebilir.

Eğer biri (yukarıda anlatılanlara rağmen) kendi alan parametrelerini oluşturmak isterse, altta yatan cismi seçmeli ve uygun sayıda noktaya sahip bir eğri bulmak için aşağıdaki stratejilerden birini kullanmalıdır:

• Rassal bir eğri seçin ve genel bir nokta sayma algoritması kullanın, örneğin Schoof'un algoritması veya Schoof – Elkies – Atkin algoritması,
• Nokta sayısını hesaplamayı kolaylaştıran bir eğri ailesi belirleyin, veya
• Karmaşık çarpım tekniğini kullanarak puan sayısını belirleyin ve bu nokta sayısıyla bir eğri oluşturun.

Bazı eğri sınıfları zayıftır ve kesinlikle uzak durulmalıdır:

• Asal olmayan m ile tanımlanmış ${\displaystyle {\displaystyle \mathbb {F} _{2^{m}}}}$üzerindeki eğri Weil descent atağına karşı zayıftır.
• ${\displaystyle |{\displaystyle {\displaystyle E(\mathbb {F} _{q})}}|=q}$ şeklindeki eğri, eğri üzerindeki noktaları ${\displaystyle \mathbb {F} _{q}}$ üzerindeki noktaları eşlediği bir atağa karşı zayıfdır.

ECDLP'yi çözmek için bilinen en hızlı algoritmaların ${\displaystyle O({\sqrt {n}})}$ adıma ihtiyaç duyması nedeniyle, cismin boyutunun güvenlik parametresinin kabaca iki katı olması gerekir. Örneğin, 128 bitlik bir güvenlik için ${\displaystyle q\approx 2^{256}}$ olacak şekilde ${\displaystyle {\displaystyle \mathbb {F} _{q}}}$ üzerinde bir eğri seçilmesi gerekir. Bu, 3072 bit açık anahtar ve 256 bit gizli anahtar gerektiren sonlu cisim kriptografisi (Örn: DSA) ile ve yalnızca özel anahtarın büyük olması gereken 3072 bitlik çarpanlarına ayırma kriptografisiyle (Örn: RSA) karşılaştırılabilir. Ancak işlemcinin gücü sınırlı olduğunda, şifrelemenin daha verimli olabilmesi için anahtar boyutu küçültülebilir.

Şimdiye kadar kırılmış en zorlu ECC şeması asıl durum için 112-bit anahtar ve iki bileşenli durum için 109 bitlik bir anahtara sahipti. Asıl durum için bu, Temmuz 2009'da 200'ün üzerinde PlayStation 3 oyun konsolunu kullanarak kırıldı ve sürekli olarak çalıştırılmasına rağmen ancak 3,5 ay içinde tamamlanabildi. İki bileşenli durumda ise, Nisan 2004'te 17 ayda 2600 bilgisayar kullanılarak kırıldı.

Toplama kuralının yakından incelendiğinde, iki noktayı toplamak için ${\displaystyle {\displaystyle \mathbb {F} _{q}}}$ 'da sadece toplamın ve çarpmanın değil, aynı zamanda tersinin de gerekli olduğunu göstermektedir. Ters işlem (verilen ${\displaystyle x\in {\displaystyle \mathbb {F} _{q}}}$ için ${\displaystyle xy=1}$ olacak şekilde bir ${\displaystyle y\in {\displaystyle \mathbb {F} _{q}}}$ bulmak) çarpma işleminden birkaç kat daha yavaştır. Neyse ki, bir eğri üzerindeki noktalar iki noktayı toplamak için ters işlem gerektirmeyen farklı koordinat sistemlerinde temsil edilebilir. Bu tür birkaç sistem önerisi: İzdüşümsel sistemde her nokta aşağıdaki ilişkiyi kullanarak üç koordinat ${\displaystyle (X,Y,Z)}$ ile temsil edilir: ${\displaystyle {\displaystyle x={\frac {X}{Z}}},{\displaystyle y={\frac {Y}{Z}}};}$ Jacobian sisteminde bir nokta üç koordinat ile de temsil edilir (X, Y, Z) ama farklı bir ilişki kullanılır ${\displaystyle {\displaystyle x={\frac {X}{Z^{2}}}},{\displaystyle y={\frac {Y}{Z^{3}}}};}$ López-Dahab sisteminde ise ilişki: ${\displaystyle {\displaystyle x={\frac {X}{Z}}},{\displaystyle y={\frac {Y}{Z^{2}}}};}$ değiştirilmiş Jacobian sisteminde aynı ilişkiler kullanılır ancak hesaplamalar için dört koordinat ${\displaystyle {\displaystyle (X,Y,Z,aZ^{4})}}$ saklanır ve kullanılır; ve Chudnovsky Jacobian sisteminde beş koordinat ${\displaystyle (X,Y,Z,Z^{2},Z^{3})}$ kullanılır. Burada farklı isimlendirme gelenekleri olabileceğine dikkat ediniz, örneğin, IEEE P1363-2000 standartı "izdüşümsel koordinatlar" isimlendirmesini Jacobian koordinatları için kullanmaktadır. Eğer karışık koordinatlar kullanılırsa ek bir hızlandırma elde edilebilir.

İndirgeme modu p (toplama ve çarpma için gerekli), eğer p asalı sözde-Mersenne asalı ise (yani ${\displaystyle p\approx 2^{d}}$; örneğin ${\displaystyle p=2^{521}-1}$ veya ${\displaystyle p=2^{256}-2^{32}-2^{9}-2^{8}-2^{7}-2^{6}-2^{4}-1}$) çok daha hızlı çalıştırılabilir. Barrett indirgemesine göre, 10'un katları ölçekli bir hızlanma elde edilebilir. Buradaki hızlanma teorik olana göre daha kullanışlıdır, ve sayıların "moduli"si, 2'nin üslerine yakın sayılara kıyasla ikilik tabanda bit düzeyinde operasyonlarla bilgisayarlarda daha verimli işlenebilir.

p sözde-Mersenne olmak üzere, ${\displaystyle {\displaystyle \mathbb {F} _{p}}}$üzerinde eğriler, NIST tarafından önerilmektedir. NIST eğrilerinin bir diğer avantajı ise, Jacobian koordinatlarında toplamayı geliştiren a = -3 kullanıyor olmasıdır.

Bernstein ve Lange'e göre, NIST FIPS 186-2'teki verimlilikle ilgili kararlar "sub-optimal". Diğer eğriler daha güvenli ve yeterince hızlı çalışıyor.

Diğer çoğu ayrık logaritma sistemlerinin aksine (karesini almak ve çarpmak için aynı yöntemi kullanmanın mümkün olduğu), eliptik eğride toplama işlemi çift(P=Q) ve genel toplam (P ≠ Q) bakımından kullanılan koordinat sistemine göre kayda değer ölçüde farklılık gösterir. Bu nedenle, yan kanal saldırılarının etkisini, örneğin "fixed pattern window" yöntemini kullanarak, ortadan kaldırmak önem kazanır(bu metot işlem süresini uzatmaz). Alternatif olarak, eliptik eğriler ailesinin çift ve toplama işlemlerinin aynı anda yapılabildiği özel bir türü olan Edward eğrisi de kullanılabilir. ECC sistemleri için bir başka endişe, özellikle akıllı kartlarda çalışırken, arıza saldırıları tehlikesidir.

Kriptografik uzmanlar Ulusal Güvenlik Ajansı'nın kleptografik bir arka kapıyı en az bir eliptik eğri tabanlı sözde rastgele üretecinin içine yerleştirdikleri endişesini dile getirdiler. Eski NSA çalışanı Edward Snowden tarafından sızdırılmış olan notlar, NSA'nın Dual_EC_DRBG standardında bir arka kapı koyduğunu gösteriyor. Olası arka kapıya ait bir analiz, algoritmanın gizli anahtarına sahip olan bir rakibin şifreleme anahtarlarını yalnızca 32 bayt şifreli metinle elde edebileceği sonucuna varmıştır.

Güvenli bir şekilde uygulanması kolay olan ve arka kapı şansını en aza indirgemek için tamamen kamuya açık bir şekilde tasarlanan eğrileri kataloglamak için SafeCurves projesi başlatıldı.

Shor algoritması, olası bir kuantum bilgisayardaki ayrık logaritmaları hesaplayarak eliptik eğri kriptografisini kırmak için kullanılabilir. 256 bitlik bir modül (128 bit güvenlik seviyesi) ile bir eğriyi kırmak için yapılan son kuantum kaynak tahminleri 2330 qubit ve 126 milyar Toffoli kapısıdır. Buna karşılık, Shor algoritmasının RSA algoritmasını kırmak için kullandığı algoritma, 2048 bit RSA anahtarı için 4098 qubit ve 5.2 trilyon Toffoli geçit kapısı gerektirmektedir, bu da Eliptik Eğri Kriptolojisinin kuantum bilgisayarlar için RSA'dan daha kolay bir hedef olduğunu göstermektedir. Tüm bu rakamlar, şimdiye kadar yapılmış olan herhangi bir kuantum bilgisayarı fazlasıyla aşıyor ve bu derece güçlü bilgisayarların oluşturulmasının on yıl veya daha uzun bir süre olacağı tahmin ediliyor.

Ağustos 2015'te NSA, "uzak olmayan bir gelecekte" kuantum ataklarına dirençli yeni bir şifre paketine geçiş yapmayı planladığını duyurdu.“Ne yazık ki, eliptik eğri kullanımının büyümesi, kuantum hesaplaması üzerine yapılan araştırmada devam eden ilerlemenin gerçeğine karşı çarparak, kriptografik stratejimizin yeniden değerlendirilmesini gerekli kılmıştır.[1]”