Eliptik Eğri İzojenileri: Matematiksel Temel

Bir k alanı üzerindeki E ve E' eliptik eğrileri arasındaki izogeni, sabit olmayan ve aynı zamanda bir grup homomorfizması olan rasyonel bir dönüşüm phi: E -> E'dir; E'nin grup işlemini E'ye taşır. Her izogeninin, phi_hat: E' -> E biçiminde bir eş izogenisi vardır ve phi_hat ile phi'nin bileşkesi, E üzerinde deg(phi) ile çarpmaya eşittir. Bir izogeninin derecesi, çekirdeğinin boyutudur: l dereceli bir izogeninin çekirdeği l büyüklüğündedir. İzogeniler skaler çarpmayı genelleştirir: n ile çarpma, E'den kendisine giden ve derecesi n^2 olan bir izogenidir. Sonlu alanlar üzerindeki izogeniler, verimli biçimde değerlendirilebilen rasyonel işlevler (polinomlar) olarak hesaplanır.

Velu formülleri (1971), E'nin bir G altgrubu verildiğinde phi: E -> E/G izogenisinin hesaplanması için açık formüller sağlar. Görüntü eğrisi E/G = E' ve rasyonel dönüşüm phi, G tarafından bütünüyle belirlenir. Velu formülleri, görüntü eğrisinin katsayılarını ve rasyonel dönüşümü, derecesi |G|'ye eşit rasyonel işlevler olarak hesaplar. Asal mertebeli bir G çekirdek altgrubu için izogeninin derecesi l'dir ve izogeni O(l) işlemle hesaplanabilir. sqrt-Velu algoritmaları (Bernstein ve diğerleri, 2019), büyük l değerleri için bunu O(sqrt(l)) işleme indirerek CSIDH'nin verimli büyük asal izogenilerini mümkün kılar. Velu formülleri, izogeni tabanlı tüm kriptografinin temel hesaplama aracıdır.

Bir sonlu alan olan Fp üzerindeki eliptik eğriler, bir izogeni grafiği içinde düzenlenebilir. Köşeler, eğriyi izomorfizmaya kadar belirleyen kanonik bir değişmez olan eliptik eğrilerin j-değişmezleridir. Kenarlar l-izogenileridir: her sıradan eğriden, küçük bir asal l için tam olarak l+1 adet giden l-izogenisi vardır (l-torsiyon altgruplarının yapısı nedeniyle). Fp üzerindeki l-izogeni grafiği (l+1)-düzenli bir graftır. Bu grafların Ramanujan özelliği (genişletici graflar), üzerlerindeki rastgele yürüyüşlerin hızla karışmasını sağlar ve izogeni tabanlı kriptografinin temelindeki zorluk varsayımını oluşturur: O(log p) uzunluğundaki rastgele yürüyüşler, j-değişmezleri üzerinde düzgün dağılımlar üretir.

Fp üzerindeki eliptik eğriler iki kategoriye ayrılır. Sıradan eğrilerin sıfırdan farklı bir p-rütbesi vardır; bu, p^2 izomorfizm sınıfının ve volkan yapısına (kraterler ve tabanlar) sahip karmaşık bir izogeni grafiğinin bulunduğu anlamına gelir. Süpersingüler eğrilerin p-rütbesi 0'dır ve tamamı Fp2 üzerinde tek bir bağlantılı izogeni grafiğinde yer alır. Fp üzerindeki süpersingüler j-değişmezlerinin sayısı yaklaşık olarak p/12'dir. SIDH ve SIKE, güçlü genişleme özelliklerine sahip bir Ramanujan grafiği olan ve yürüyüşün yönünü açığa çıkarabilecek bir volkan yapısı bulunmayan izogeni grafikleri nedeniyle süpersingüler eğrileri kullanır. CSIDH de süpersingüler eğrileri kullanır, ancak Fp2 yerine Fp üzerinde çalışarak farklı bir cebirsel yapıdan yararlanır.

İzogeni tabanlı kriptografi, birbiriyle ilişkili iki zor probleme dayanır. Süpersingüler İzogeni Problemi (SSIP): Fp2 üzerindeki iki süpersingüler eliptik eğri E ve E' verildiğinde, phi: E -> E' izogenisini bulun. Hesaplamalı Süpersingüler İzogeni (CSSI) problemi: E, E' = phi(E) ve phi'nin derecesi verildiğinde phi'yi bulun. SSIP için bilinen en iyi klasik algoritma O(p^{1/4}) zamanda çalışır. Bilinen en iyi kuantum algoritması (Tani'nin pençe bulma algoritması) O(p^{1/6}) zamanda çalışır. p = 2^{434} için bu, 128 bitlik klasik güvenlik sağlar. Bunlar, Shor algoritmasının RSA/ECC'ye karşı sağladığı üstel hızlanmaya kıyasla önemli ölçüde daha zayıf kuantum hızlanmalarıdır; bu nedenle izogeni tabanlı şemalar kuantum sonrası güvenlidir.

SIDH (Süpersingüler İzogeni Diffie-Hellman), Fp2 üzerindeki E eğrisinin 2^a-torsiyon noktalarına (2^a * P = 0 koşulunu sağlayan P noktaları kümesi) ve erişilebilir 3^b-torsiyon noktalarına sahip olmasını sağlayan, özel yapılı p = 2^a * 3^b - 1 asalını kullanır. Alice'in gizlisi, çekirdeği 2^a-torsiyonunun rastgele bir elemanı tarafından üretilen 2^a-izogenisi phi_A: E -> E_A'dır. Bob'un gizlisi 3^b-izogenisi phi_B: E -> E_B'dir. Torsiyon noktalarının görüntülerini değiş tokuş ederler: Alice, E_A ile phi_A(P_B) ve phi_A(Q_B) değerlerini yayımlar. Bob, E_B ile phi_B(P_A) ve phi_B(Q_A) değerlerini yayımlar. Bu, her bir tarafın diğer tarafın eğrisinden izogeniler hesaplamasını ve aynı ortak j-değişmezine ulaşmasını sağlar.

Bir eliptik eğrinin End(E) endomorfizma halkası, E'den kendisine giden tüm izogenilerin halkasıdır (skaler çarpmalar dâhil). Fp üzerindeki sıradan eğriler için End(E), imajiner ikinci dereceden bir alandaki bir düzendir. Süpersingüler eğriler için End(E), p'de ve sonsuzda dallanmış bir kuaterniyon cebirindeki maksimal düzendir. End(E)'nin yapısı, eğriyi izomorfizmaya kadar bütünüyle belirler. Endomorfizma halkası problemi, E verildiğinde End(E)'yi hesaplama problemidir ve zor olduğuna inanılır (süpersingüler eğriler için SSIP'ye denktir). Castryck-Decru saldırısı, SIDH protokolünde sızan ek bilgileri kullanarak endomorfizma halkasının bir bölümünü verimli biçimde yeniden oluşturdu ve şemayı kırdı.

l dereceli bir phi: E -> E' izogenisi, l dereceli bir polinomla (veya nokta terslerinin aynı x-koordinatına sahip olması gerçeğinden yararlanan simetri iyileştirmesinden sonra l/2 dereceli bir polinomla) gösterilebilir. Verilen bir P noktası için phi(P) hesaplamak, Velu formülleri kullanılarak O(l) çarpma işlemi gerektirir. l = 2^a değerinin yaklaşık 2^216 olduğu SIDH için bu, uygulanamayacak kadar maliyetli görünür; ancak SIDH, 2^a-izogenilerinin a adet 2-izogeniden oluşan bir zincire ayrıştırılabilmesi gerçeğinden yararlanır. Her 2-izogeni ucuzdur ve a adımlı bir zincir 2^a-izogenisi üretir. Benzer şekilde 3^b için de çalışır. sqrt-Velu, CSIDH'nin büyük tek asal izogenisi hesaplamalarının O(l) yerine O(sqrt(l)) zamanda çalışmasını sağlayarak CSIDH'yi pratik hâle getirir.

SIKE (Süpersingüler İzogeni Anahtar Kapsüllemesi), dördüncü tura kadar tüm turları geçen ve o turda kırılan bir NIST PQC adayıydı. SIKE, tüm NIST adayları arasında en küçük anahtar boyutlarına sahip olmasıyla dikkat çekiyordu: SIKEp434 için 374 bayt (NIST Seviye 1). Karşılaştırma için ML-KEM-512'nin açık anahtarları 800 bayttır. SIKE bu küçüklüğü, ortak sırrın yaklaşık 430 bitlik bir alan elemanı olan tek bir j-değişmezinden türetilmesi sayesinde elde etti. Bu küçüklüğün bir bedeli vardı: SIKE, diğer adaylardan 100-1000 kat daha yavaştı. Castryck ve Decru, Temmuz 2022'de SIKE'yi bir dizüstü bilgisayarda dakikalar içinde çalışan klasik bir saldırıyla kırdığında SIKE, NIST yarışmasından derhal elendi.

İzogeni tabanlı kriptografi, kuantum sonrası yaklaşımlar arasında özgün bir konuma sahiptir. Anahtar boyutları, kafes tabanlı yaklaşımlardan (ML-KEM: 800+ bayt) veya özet tabanlı imzalardan (SLH-DSA: 32-49 baytlık açık anahtar, ancak 7856-49856 baytlık imzalar) çok daha küçüktür. Başarım, tüm alternatiflerden çok daha düşüktür (SIKE, ML-KEM'den 100-1000 kat daha yavaştı). Güvenlik varsayımı, LWE (ML-KEM/ML-DSA'de kullanılır), SIS veya özet işlevlerinden farklıdır ve kriptografik çeşitlilik sağlar. Kuantum sonrası güvenliğin temeli, izogeni yolu problemidir; bu problem için RSA/ECC'nin aksine bilinen polinom zamanlı bir kuantum algoritması yoktur ve RSA/ECC, Shor algoritması tarafından bütünüyle kırılır. SIKE'nin klasik saldırıyla kırılması, LWE problemi üzerinde kapsamlı biçimde çalışılmış olmasına karşın izogeni zorluğunun hâlâ anlaşılma aşamasında olduğunu gösterir.

SIKE'nin kırılmasına rağmen izogeni tabanlı kriptografi etkin bir araştırma alanı olmaya devam etmektedir. SQISign (Kısa Kuaterniyon ve İzogeni İmzası), 177 baytlık imzalara sahip bir izogeni tabanlı imza şemasıdır (Seviye 2 için ML-DSA'nın 2420 baytına karşılık); bilinen en küçük PQC imzalarını sunar. SQISign, verilen iki süpersingüler eğri arasında önceden belirlenmiş derecede bir izogeni hesaplama zor probleminden yararlanır; bu problem endomorfizma halkası problemi olarak biçimselleştirilmiştir. FESTA (Süpersingüler Torsiyon Saldırılarıyla Hızlı Şifreleme), SIDH'yi savunmasız hâle getiren ek torsiyon noktası yardımcı verilerinden kaçınan yeni bir KEM tasarımıdır. CTIDH (Sabit Zamanlı CSIDH), CSIDH'nin başarımını iyileştirir. Bu şemalar, SIKE'nin elenmesinden sonra bile izogeni araştırmalarını güncel tutar.

Eliptik eğriler arasındaki izogeni nedir?

İzogeni, grup homomorfizması olan ve derecesi çekirdeğinin boyutuna eşit bir rasyonel dönüşümdür phi: E -> E'. Velu formülleri, görüntü eğrisini ve dönüşümü çekirdek altgrubundan hareketle hesaplar. İzogeni grafları, eğrileri köşeler ve l-izogeni kenarları olarak düzenler; bu kenarlar (l+1)-düzenli Ramanujan grafları oluşturur. SIDH/SIKE/CSIDH'de kullanılan süpersingüler eğriler, güçlü genişleme özelliklerine sahip izogeni graflarına sahiptir. SSIP ve CSSI problemleri izogeni güvenliğinin temelini oluşturur. SIDH, dönüşümlü 2- ve 3-izogeni zincirleriyle torsiyon noktası yapısını kullanır. Endomorfizma halkasının hesaplanması SSIP'ye denktir. SQISign ve FESTA, endomorfizma halkasının zorluğunu kullanan, SIKE sonrası etkin araştırma yönlerini temsil eder.