Eliptik eğri kriptografisi

Eliptik Eğri Kriptolojisi (Elliptic Curve Cryptography), sonlu cisimler üzerindeki eliptik eğrilerin cebirsel topolojisine dayanan bir açık anahtar şifrelemesidir. Eliptik Eğri Kriptolojisi, diğer şifrelemeler göre daha küçük anahtar boyuna ihtiyaç duyar.

Eliptik Eğriler, anahtar anlasması, dijital imza, sözde rastlantısal üretici ve daha birçok alanda kullanılabilirler. Dolaylı olarak, anahtar anlasmasını simetrik bir şifreleme şemasıyla birleştirerek şifreleme için kullanılabilirler. Lenstra Eliptik Eğrileri gibi kriptografik uygulamaları olan eliptik eğrileri temel alan çarpanlarına ayırma algoritmalarında da kullanılırlar.

Mantık

Son zamanlardaki açık anahtar şifreleme algoritmaları iki ya da daha fazla çok büyük asal sayının çarpımının, çarpanlarına ayırılmasındaki zorluğuna dayanır. Eliptik eğri protokollerinde ise bu durum, eliptik eğrinin bilinen bir noktasına göre ayrık logaritmasını bulmanın imkânsız olduğunu varsaymaktadır. Buna “Eliptik Eğrinin Ayrık Logaritma Problemi” denir. Eliptik eğrinin güvenliği, nokta çarpımının hesaplanma hızına ve başlangıç noktası ile çarpım noktasına bakarak elde edilen noktanın hesaplanamamasına dayanmaktadır. Eliptik eğrinin boyutu aynı zamanda problemin zorluğunu da belirler.

Eliptik eğri kriptografisinin en büyük özelliği depolama ve iletme gereksinimlerini azaltarak daha küçük anahtar boyutuna sahip olmasıdır. Bir eliptik eğri grubu, büyük modülerli ve buna bağlı olarak büyük anahtar boyutlu RSA tabanlı sistem ile aynı güvenlik seviyesi sunabilir. Örneğin; Eliptik eğri ile 256-bitlik anahtar boyutunda elde edeceğimiz güvenliği RSA ‘de 3072-bitlik anahtar ile sağlanabilir.

Ulusal Standartlar ve Teknoloji Enstitüsü (İngilizce: National Institute of Standards and Technology, kısaca NIST), anahtar anlasması için eliptik eğri Diffie Hellman (ECDH) ve dijital imza için Eliptik Eğri Dijital İmza Algoritmasını (ECDSA), ABD Ulusal Güvenlik Ajansı (İngilizce: National Security Agency, kısaca NSA), Suite B kriptolojisinde önerilen algoritmalar arasına eliptik eğri kriptografisinin de girmesini onaylamıştır. NSA, çok gizli bilgileri korumak için 384-bitlik anahtar boyutunu tavsiye etmektedir. Ancak, Ağustos 2015'te, NSA, ECC'ye yönelik kuantum hesaplama saldırılarıyla ilgili endişeler nedeniyle Suite B'yi yeni bir şifre paketi ile değiştirmeyi planladığını duyurdu.

RSA patenti 2000'de dolmuş olsa da, ECC teknolojisinin belirli açılarını kapsayan patentler olabilir. Ancak ABD hükümeti eliptik eğri dijital imza standartının ve belirli kullanışlı ECC-tabanlı anahtar değişim yapılarının (ECDH dahil) bunlar ihlal edilmeden gerçeklenemeyeği yönünde tartışmalar mevcuttur, RSA Laboratuvarları ve Daniel J. Bernstein da dahil.

Tarihçe

Kriptografide eliptik eğrilerin kullanımı, 1985'te Neal Koblitz ve Victor S. Miller tarafından bağımsız olarak önerilmiştir. Eliptik eğri kriptografi algoritmaları, 2004'ten 2005'e kadar geniş kullanım alanına girmiştir.

Teori

Mevcut kriptografik amaçlar için, bir eliptik eğri, aşağıdaki denklemi sağlayan noktalardan oluşan sonlu cisim (gerçek sayılardan ziyade) üzerinde bir düzlem eğrisidir. (Buradaki koordinatlar, 2 ve 3 hariç olmak üzere sabit bir sonlu cismin karakteristiğinden veya biraz daha karmaşık olan bir eğri denkleminden seçilir.)

$y^{2}=x^{3}+ax+b,$

Eliptik eğrinin grup işlemlerinin bulunduğu küme abelyen bir kümedir. Bu grubun yapısı, cebirsel çeşitliliğin altında yatan bölen grubundan geçmiştir.

$Div^{0}(E)\rightarrow Pic^{0}(E)\simeq E,$

Kriptografik Şema

Birçok ayrık logaritma tabanlı protokol, ${\displaystyle (\mathbb {Z} _{p})^{\times }}$ grubunun eliptik eğri ile değiştirilmesi sayesinde eliptik eğrilere uyarlanabilmiştir :

• Eliptik Eğri Diffie-Hellman (ECDH) anahtar anlaşma şemasının Diffie-Hellman şemasına dayanmaktadır,
• Eliptik Eğri Entegre Şifreleme Şeması, Eliptik Eğri Artırılmış Şifreleme şeması olarak da bilinen veya sadece Eliptik Eğri Şifreleme Şeması,
• Eliptik Eğri Dijital İmza Algoritması (ECDSA), Dijital İmza Algoritmasına dayanmaktadır,
• Edwards-eğrisi Dijital İmza Algoritması (EdDSA), Schnorr imzasına dayanır ve Twisted Edwards eğrilerini kullanır,
• ECMQV anahtar anlaşma şeması, MQV anahtar anlaşma şemasına dayanmaktadır.

Ulusal Güvenlik Ajansı (NSA) 2005'te RSA konferansında dijital imza üretimi ve anahtar anlaşması için Eliptik Eğri Kriptolojisini özel olarak kullanan Suite B'yi duyurdu. SuitB, hem gizli hem de gizli olmayan ulusal güvenlik sistemlerini ve bilgilerini korumayı amaçlamıştır.

Yakın zamanda, Weil ve Tate çifti gibi çeşitli eliptik eğri gruplarında çift yönlü eşlemelere dayalı çok sayıda kriptografik ilke tanıtılmıştır. Bu ilkelere dayalı şemalar, eşleme tabanlı imzalar, işaretleme, anahtar anlaşması ve proxy şifrelemenin yanı sıra verimli kimlik tabanlı şifreleme de sağlar.

Yürütme

Alan Parametreler

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 $p$ sayısıyla, iki bileşenli durumda ise $m$ ve $f$ çifti ile tanımlanır. Eliptik eğriler, eşitliği sağlamak için sabit $a$ ve $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, $nG=\infty$ denklemini sağlayacak en küçük $n$ değeri, genellikle asal bir sayıdır. $n$, ${\displaystyle E(\mathbb {F} _{p})}$ alt-grubunun büyüklüğü olduğundan Lagrange Teoreminden 8 Nisan 2018 tarihinde Wayback Machine sitesinde arşivlendi. ${\displaystyle h={\frac {1}{n}}|E(\mathbb {F} _{p})|}$ sayısı tam sayıdır. Kriptografik uygulamalarda kofaktör olarak adlandırılan bu $h$ sayısı, küçük ($h\leq 4$) bir tam sayı olarak, tercihen $h=1$, seçilmelidir. Özetle, asıl durum parametreleri $(p,a,b,G,n,h)$ ve ikili durum parametleri ise $(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 \mathbb {F} _{2^{m}}}$üzerindeki eğri Weil descent atağına karşı zayıftır.
• $|{\displaystyle {\displaystyle E(\mathbb {F} _{q})}}|=q$ şeklindeki eğri, eğri üzerindeki noktaları $\mathbb {F} _{q}$ üzerindeki noktaları eşlediği bir atağa karşı zayıfdır.

Anahtar Boyu

ECDLP'yi çözmek için bilinen en hızlı algoritmaların $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 $q\approx 2^{256}$ olacak şekilde ${\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ı.

İzdüşümsel Koordinatlar

Toplama kuralının yakından incelendiğinde, iki noktayı toplamak için ${\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 $x\in {\displaystyle \mathbb {F} _{q}}$ için $xy=1$ olacak şekilde bir $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 $(X,Y,Z)$ ile temsil edilir: ${\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 x={\frac {X}{Z^{2}}}},{\displaystyle y={\frac {Y}{Z^{3}}}};$ López-Dahab sisteminde ise ilişki: ${\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 (X,Y,Z,aZ^{4})}$ saklanır ve kullanılır; ve Chudnovsky Jacobian sisteminde beş koordinat $(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.

Hızlı İndirgeme (NIST Eğrileri)

İndirgeme modu p (toplama ve çarpma için gerekli), eğer p asalı sözde-Mersenne asalı ise (yani $p\approx 2^{d}$; örneğin $p=2^{521}-1$ veya $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 \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.

Uygulamalar

Eliptik eğriler şifreleme, dijital imzalar, sözde rastgele üreteçler ve diğer görevlere uyarlanabilir. Ayrıca, Lenstra eliptik eğri faktörizasyonu gibi kriptografi uygulamalarına sahip olan birkaç çarpanlarına ayırma algoritmasında da kullanılırlar.

NIST, 1999 yılında 15 eliptik eğri önerdi. Özellikle, FIPS 186-3'ün önerilen 10 sonlu cisim vardır:

• 92, 224, 256, 384 ve 521 bit boyutlarında asal p için ${\displaystyle \mathbb {F} _{p}}$ asıl 5 cisim. Asıl cisimlerin her biri için, bir eliptik eğri tavsiye edilir.
• 163, 233, 283, 409, and 571 bitlik m değeri için ${\displaystyle \mathbb {F} _{2^{m}}}$ İki bileşenli 5 cisim. İki bileşenli her biri için bir eliptik eğri ve bir Koblitz eğrisi seçildi.

NIST tavsiyesi, toplam 5 asıl eğri ve 10 iki bileşenli eğri içerir. Bu eğriler optimum güvenlik ve uygulama verimliliği için seçildi.

2013 yılında New York Times Çift Eliptik Eğri Deterministik Rastgele Bit Üretiminin(veya Dual_EC_DRBG), algoritmaya ve önerilen eliptik egriye kasti bir zayıflık ekleyen NSA'in etkisinden dolayı NIST ulusal standartlari icerisine dahil edildigini yazdi. Eylül 2013'te RSA Security 5 Nisan 2018 tarihinde Wayback Machine sitesinde arşivlendi., müşterilerinin Dual_EC_DRBG'ye dayalı herhangi bir yazılımı kullanmaya devam etmelerini tavsiye eden bir karar yayınladı. Dual_EC_DRBG'nin "bir NSA gizli operasyonu" olarak ortaya çıkmasının ardından, şifreleme uzmanları, NIST'in eliptik eğrilerinin güvenliğiyle ilgili endişelerini dile getirerek, eliptik olmayan eğri gruplarına dayanan şifrelemeye geri dönüşü önerdiler.

Güvenlik

Yan Kanal Saldırıları

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.

Arka Kapı

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ı.

Kuantum Bilgisayar Atağı

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.”

Patentler

En az bir Eliptik Eğri Kriptolojisi şema planı (ECMQV) ve bazı uygulama teknikleri patentlenmiştir.

Alternatif Temsiller

• Hessian eğrileri
• Edwards eğrileri
• Twisted eğrileri
• Twisted Hessian eğrileri
• Twisted Edwards eğrileri
• Doubling-oriented Doche–Icart–Kohel eğrileri
• Tripling-oriented Doche–Icart–Kohel eğrileri
• Jacobian eğrileri
• Montgomery eğrileri

Sonuç

ECC'nin diğer açık anahtar kripto sistemlerine göre daha geç geliştirilmesine karşın güvenilirliğinin test edilebilmesi için yeterli süre geçmiş ve ECC birçol atağa karşın ayakta kalabilmeyi başarmıştır. ECC'nin diğer popüler açık anahtar sistemlerine karşı aynı güvenlik seviyesinde hem anahtar boyutu hem de hız olarak büyük avantajı olmasına rağmen ECC'yi ilgilendiren patentlerin hala geçerli olması sebebiyle dezavantajı da vardır. Yine de özellikle yüksek hızın çok önemli olduğu kablosuz sistemler gibi çeşitli sistemlerde gittikçe daha sık kullanılmaktadır. Motorola, IBM, Sun Microsystems, Microsoft ve Hewlett-Packard gibi büyük teknoloji firmaları da ECC kullanan kripto sistemlere yatırım yapmaktadır.