Eliptik eğri şifreleme - Elliptic-curve cryptography

Eliptik eğri şifreleme (ECC) bir yaklaşımdır açık anahtarlı şifreleme göre cebirsel yapı nın-nin eliptik eğriler bitmiş sonlu alanlar. ECC, EC dışı kriptografiye kıyasla daha küçük anahtarlara izin verir (düz Galois alanları ) eşdeğer güvenlik sağlamak için.^[1]

Eliptik eğriler aşağıdakiler için geçerlidir: anahtar anlaşma, dijital imzalar, sözde rastgele üreteçler ve diğer görevler. Dolaylı olarak, bunlar için kullanılabilirler şifreleme anahtar anlaşmayı bir simetrik şifreleme düzeni. Ayrıca birkaçında da kullanılırlar tamsayı çarpanlara ayırma algoritmalar kriptografide uygulamaları olan eliptik eğrileri temel alır, örneğin Lenstra eliptik eğri çarpanlara ayırma.

Gerekçe

Açık anahtarlı kriptografi, inatçılık belli matematiksel sorunlar. Erken açık anahtar sistemleri, güvenliklerini zor olduğu varsayımına dayandırdı. faktör iki veya daha fazla büyük asal faktörden oluşan büyük bir tam sayı. Daha sonraki eliptik eğri tabanlı protokoller için temel varsayım, ayrık logaritma herkesin bildiği bir taban noktasına göre rastgele bir eliptik eğri elemanının kullanılması mümkün değildir: bu "eliptik eğri ayrık logaritma problemidir" (ECDLP). Eliptik eğri kriptografisinin güvenliği, hesaplama yeteneğine bağlıdır. nokta çarpımı ve orijinal ve çarpım puanları verilen çarpımın hesaplanamaması. Eliptik eğrinin boyutu, sorunun zorluğunu belirler.

Birleşik Devletler. Ulusal Standartlar ve Teknoloji Enstitüsü (NIST), eliptik eğri kriptografisini onayladı. Süit B özellikle önerilen algoritmalar kümesi eliptik eğri Diffie – Hellman (ECDH) anahtar değişimi için ve Eliptik Eğri Sayısal İmza Algoritması (ECDSA) dijital imza için. Birleşik Devletler. Ulusal Güvenlik Ajansı (NSA), şu tarihe kadar sınıflandırılmış bilgileri korumak için kullanılmasına izin verir: çok gizli 384 bit anahtarlarla.^[2] Ancak, Ağustos 2015'te NSA, Suite B'yi yeni bir şifre paketiyle değiştirmeyi planladığını duyurdu. kuantum hesaplama ECC'ye saldırılar.^[3]

RSA patentinin süresi 2000 yılında dolmuş olsa da, ECC teknolojisinin belirli yönlerini kapsayan yürürlükteki patentler. Ancak bazıları, ABD hükümeti eliptik eğri dijital imza standardı (ECDSA; NIST FIPS 186-3) ve bazı pratik ECC tabanlı anahtar değişim şemaları (ECDH dahil), bunları ihlal etmeden uygulanabilir. RSA Laboratuvarları^[4] ve Daniel J. Bernstein.^[5]

Eliptik eğri kriptografisinin vaat ettiği birincil fayda, daha küçük anahtar boyutu, depolama ve iletim gereksinimlerini azaltır,^[6] yani bir eliptik eğri grubu aynı şeyi sağlayabilir güvenlik seviyesi tarafından sağlanan RSA - büyük modüllü ve buna uygun olarak daha büyük anahtara sahip tabanlı sistem: örneğin, 256 bitlik bir eliptik eğri genel anahtarı, 3072 bitlik bir RSA açık anahtarıyla karşılaştırılabilir güvenlik sağlamalıdır.

Tarih

Kriptografide eliptik eğrilerin kullanımı bağımsız olarak önerilmiştir. Neal Koblitz^[7] ve Victor S. Miller^[8] 1985'te. Eliptik eğri kriptografi algoritmaları, 2004-2005'te yaygın kullanıma girdi.

Teori

Mevcut kriptografik amaçlar için, bir eliptik eğri bir düzlem eğrisi üzerinde sonlu alan denklemi sağlayan noktalardan oluşan (gerçek sayılardan ziyade)

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

seçkin bir sonsuzluk noktası, ∞ ile gösterilir. (Buradaki koordinatlar sabit bir sonlu alan nın-nin karakteristik 2 veya 3'e eşit değildir, yoksa eğri denklemi biraz daha karmaşık olacaktır.)

Bu, eliptik eğrilerin grup çalışması bir değişmeli grup bir kimlik unsuru olarak sonsuzluk noktasında. Grubun yapısı, bölen grup temelin cebirsel çeşitlilik.

${displaystyle mathrm {Div} ^ {0} (E) o mathrm {Pic} ^ {0} (E) simeq E ,,}$

Şifreleme şemaları

Birkaç ayrık logaritma tabanlı protokoller, grubun yerini alarak eliptik eğrilere uyarlandı ${displaystyle (mathbb {Z} _ {p}) ^ {imes}}$ eliptik bir eğri ile:

• Eliptik Eğri Diffie – Hellman (ECDH) anahtar anlaşma şeması, Diffie – Hellman şema
• Eliptik Eğri Entegre Şifreleme Şeması (ECIES), ayrıca Eliptik Eğri Arttırılmış Şifreleme Şeması veya sadece Eliptik Eğri Şifreleme Şeması olarak da bilinir,
• Eliptik Eğri Sayısal İmza Algoritması (ECDSA), Dijital İmza Algoritması,
• Harrison'ın p-adic Manhattan metriğini kullanan deformasyon şeması,
• Edwards Eğrisi Dijital İmza Algoritması (EdDSA) temel alır Schnorr imzası ve kullanır bükülmüş Edwards eğrileri,
• ECMQV anahtar anlaşma şeması, MQV anahtar anlaşma şeması,
• ECQV örtük sertifika şeması.

RSA Konferansı 2005'te, Ulusal Güvenlik Ajansı (NSA) duyuruldu Süit B Dijital imza üretimi ve anahtar değişimi için yalnızca ECC'yi kullanır. Paket, hem sınıflandırılmış hem de sınıflandırılmamış ulusal güvenlik sistemlerini ve bilgileri korumayı amaçlamaktadır.^[6]

Son zamanlarda, çeşitli eliptik eğri gruplarında çift doğrusal eşleştirmelere dayanan çok sayıda kriptografik ilkel, örneğin Weil ve Tate eşleşmeleri, tanıtıldı. Bu ilkellere dayalı şemalar, verimli kimlik tabanlı şifreleme eşleştirme tabanlı imzaların yanı sıra, işaret şifreleme, anahtar anlaşma, ve proxy yeniden şifreleme.

Uygulama

Bazı yaygın uygulama konuları şunları içerir:

Etki alanı parametreleri

ECC'yi kullanmak için, tüm taraflar eliptik eğriyi tanımlayan tüm unsurlar, yani etki alanı parametreleri planın. Alan şu şekilde tanımlanır: p birinci durumda ve çift m ve f ikili durumda. Eliptik eğri, sabitler tarafından tanımlanır a ve b tanımlayıcı denkleminde kullanılır. Son olarak, döngüsel alt grup, jeneratör (diğer adıyla. taban noktası) G. Kriptografik uygulama için sipariş nın-nin Gbu en küçük pozitif sayıdır n öyle ki ${displaystyle nG = {mathcal {O}}}$ ( sonsuzluk noktası eğrinin ve kimlik öğesi ), normalde asaldır. Dan beri n bir alt grubun boyutu ${displaystyle E (mathbb {F} _ {p})}$ buradan takip eder Lagrange teoremi bu numara ${displaystyle h = {frac {1} {n}} | E (mathbb {F} _ {p}) |}$ bir tamsayıdır. Kriptografik uygulamalarda bu numara h, aradı kofaktör, küçük olmalı (${displaystyle hleq 4}$) ve tercihen ${displaystyle h = 1}$. Özetlemek gerekirse: ana durumda, alan parametreleri ${displaystyle (p, a, b, G, n, h)}$; ikili durumda bunlar ${displaystyle (m, f, a, b, G, n, h)}$.

Etki alanı parametrelerinin, kullanımları açısından güvenilen bir taraf tarafından oluşturulduğuna dair bir güvence olmadığı sürece, etki alanı parametreleri zorunlu kullanmadan önce doğrulanmalıdır.

Etki alanı parametrelerinin oluşturulması genellikle her katılımcı tarafından yapılmaz çünkü bu, hesaplamayı içerir. bir eğri üzerindeki nokta sayısı bu, zaman alıcıdır ve uygulanması zahmetlidir. Sonuç olarak, birkaç standart gövde, birkaç ortak alan boyutu için eliptik eğrilerin alan parametrelerini yayınladı. Bu tür alan parametreleri genellikle "standart eğriler" veya "adlandırılmış eğriler" olarak bilinir; adlandırılmış bir eğriye isme göre veya benzersiz nesne tanımlayıcı standart belgelerde tanımlanmıştır:

• NIST, Devlet Kullanımı için Önerilen Eliptik Eğriler
• SECG, SEC 2: Önerilen Eliptik Eğri Alan Parametreleri
• ECC Beyin Havuzu (RFC 5639 ), ECC Brainpool Standart Eğrileri ve Eğri Üretimi

SECG test vektörleri de mevcuttur.^[9] NIST birçok SECG eğrisini onaylamıştır, bu nedenle NIST ve SECG tarafından yayınlanan spesifikasyonlar arasında önemli bir örtüşme vardır. EC alan parametreleri, değere göre veya adla belirtilebilir.

Kişi (yukarıdakilere rağmen) kendi alan parametrelerini oluşturmak istiyorsa, temel alan seçilmeli ve ardından aşağıdaki yöntemlerden birini kullanarak uygun (yani asal) sayıda noktaya sahip bir eğri bulmak için aşağıdaki stratejilerden birini kullanmalıdır. :

• Rastgele bir eğri seçin ve genel bir nokta sayma algoritması kullanın, örneğin, Schoof algoritması veya Schoof – Elkies – Atkin algoritması,
• Bir aileden, nokta sayısının kolay hesaplanmasına izin veren rastgele bir eğri seçin (örn. Koblitz eğrileri ) veya
• Nokta sayısını seçin ve kullanarak bu sayıda nokta ile bir eğri oluşturun. karmaşık çarpma tekniği.^[10]

Birkaç eğri sınıfı zayıftır ve bundan kaçınılması gerekir:

• Eğriler bitti ${displaystyle mathbb {F} _ {2 ^ {m}}}$ asal olmayan m savunmasız Weil iniş saldırılar.^[11][12]
• Eğriler öyle ki n böler ${görüntü stili p ^ {B} -1}$ (nerede p alanın özelliğidir: q bir ana alan için veya ${displaystyle 2}$ bir ikili alan için) yeterince küçük B Menezes – Okamoto – Vanstone (MOV) saldırısına karşı savunmasızdır^[13][14] hangisi olağan ayrık logaritma problemi (DLP) küçük dereceli bir uzatma alanında ${displaystyle mathbb {F} _ {p}}$ ECDLP'yi çözmek için. Sınır B öyle seçilmelidir ki ayrık logaritmalar alan içerisinde ${displaystyle mathbb {F} _ {p ^ {B}}}$ eliptik eğri üzerindeki ayrık günlükler kadar hesaplanması en az zordur ${displaystyle E (mathbb {F} _ {q})}$.^[15]
• Eğriler öyle ki ${displaystyle | E (mathbb {F} _ {q}) | = q}$ eğri üzerindeki noktaları ek grubu ile eşleştiren saldırıya karşı savunmasızdır. ${displaystyle mathbb {F} _ {q}}$.^[16][17][18]

Anahtar boyutları

Çünkü birinin ECDLP'yi çözmesine izin veren bilinen en hızlı algoritmalar (bebek adımı dev adım, Pollard's rho, vb.), ihtiyaç ${displaystyle O ({sqrt {n}})}$ adımlar, temel alan boyutunun güvenlik parametresinin kabaca iki katı olması gerektiğini takip eder. Örneğin, 128-bit güvenlik için birinin üzerinde bir eğriye ihtiyacı var. ${displaystyle mathbb {F} _ {q}}$, nerede ${displaystyle qapprox 2 ^ {256}}$. Bu, sonlu alan şifreleme ile karşılaştırılabilir (ör. DSA ) hangi gereksinimler^[19] 3072 bit genel anahtarlar ve 256 bit özel anahtarlar ve tamsayı faktorizasyon şifreleme (ör. RSA ) 3072 bitlik bir değer gerektiren n, özel anahtarın aynı büyüklükte olması gereken yer. Ancak, özellikle işlem gücü sınırlı olduğunda, etkin şifrelemeye uyum sağlamak için genel anahtar daha küçük olabilir.

Bugüne kadar kırılan en zor ECC şeması (halka açık olarak), ana alan durumu için 112 bitlik bir anahtara ve ikili alan durumu için 109 bitlik bir anahtara sahipti. Temel saha örneği için bu, Temmuz 2009'da 200'ün üzerinde bir küme kullanılarak kırıldı PlayStation 3 oyun konsolları ve sürekli çalışırken bu kümeyi kullanarak 3.5 ayda tamamlanmış olabilir.^[20] İkili alan vakası, Nisan 2004'te 17 ayda 2600 bilgisayar kullanılarak bozuldu.^[21]

Mevcut bir proje, çok çeşitli farklı donanımlar kullanarak Certicom'un ECC2K-130 zorluğunu aşmayı hedefliyor: CPU'lar, GPU'lar, FPGA.^[22]

Projektif koordinatlar

Toplama kurallarının yakından incelendiğinde, iki nokta eklemek için, birinin yalnızca birkaç ekleme ve çarpmaya gerek olmadığını gösterir. ${displaystyle mathbb {F} _ {q}}$ ama aynı zamanda bir ters çevirme işlemi. Ters çevirme (verilen ${displaystyle xin mathbb {F} _ {q}}$ bulmak ${displaystyle yin mathbb {F} _ {q}}$ öyle ki ${displaystyle xy = 1}$) bir ila iki büyüklük sırası daha yavaştır^[23] çarpmadan daha çok. Bununla birlikte, bir eğri üzerindeki noktalar, iki nokta eklemek için bir ters çevirme işlemi gerektirmeyen farklı koordinat sistemlerinde gösterilebilir. Bu tür birkaç sistem önerildi: projektif sistem her nokta üç koordinatla temsil edilir ${görüntü stili (X, Y, Z)}$ aşağıdaki ilişkiyi kullanarak: ${displaystyle x = {frac {X} {Z}}}$, ${displaystyle y = {frac {Y} {Z}}}$; içinde Jacobian sistemi bir nokta da üç koordinatla temsil edilir ${görüntü stili (X, Y, Z)}$, ancak farklı bir ilişki kullanılır: ${displaystyle x = {frac {X} {Z ^ {2}}}}$, ${displaystyle y = {frac {Y} {Z ^ {3}}}}$; içinde López – Dahab sistemi ilişki ${displaystyle x = {frac {X} {Z}}}$, ${displaystyle y = {frac {Y} {Z ^ {2}}}}$; içinde değiştirilmiş Jacobian sistem aynı ilişkiler kullanılır ancak dört koordinat saklanır ve hesaplamalar için kullanılır ${görüntü stili (X, Y, Z, aZ ^ {4})}$; Ve içinde Chudnovsky Jacobian sistem beş koordinat kullanılır ${görüntü stili (X, Y, Z, Z ^ {2}, Z ^ {3})}$. Farklı adlandırma kurallarının olabileceğini unutmayın, örneğin, IEEE P1363 -2000 standardı, genellikle Jacobian koordinatları olarak adlandırılan şeyi belirtmek için "projektif koordinatlar" kullanır. Karışık koordinatlar kullanılırsa ek bir hızlanma mümkündür.^[24]

Hızlı indirgeme (NIST eğrileri)

Redüksiyon modülü p (toplama ve çarpma için gerekli olan), asal p sözdeMersenne asal, yani ${displaystyle papprox 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.}$ Nazaran Barrett azaltma, büyük bir hızlanma sırası olabilir.^[25] Buradaki hızlanma teorik olmaktan çok pratiktir ve sayıların ikiye yakın sayılara karşı modüllerinin ikili sayılar üzerinde çalışan bilgisayarlar tarafından verimli bir şekilde gerçekleştirilebilmesinden kaynaklanır. bitsel işlemler.

Eğriler bitti ${displaystyle mathbb {F} _ {p}}$ sözde Mersenne ile p NIST tarafından önerilmektedir. Yine NIST eğrilerinin bir başka avantajı da a = −3, Jacobian koordinatlarında toplamayı iyileştirir.

Bernstein ve Lange'ye göre, NIST FIPS 186-2'deki verimlilikle ilgili kararların çoğu yetersizdir. Diğer eğriler daha güvenlidir ve aynı hızda çalışır.^[26]

Başvurular

Eliptik eğriler aşağıdakiler için geçerlidir: şifreleme, dijital imzalar, sözde rastgele üreteçler ve diğer görevler. Ayrıca birkaçında da kullanılırlar tamsayı çarpanlara ayırma algoritmalar kriptografide uygulamaları olan Lenstra eliptik eğri çarpanlara ayırma.

1999'da NIST on beş eliptik eğri önermiştir. Özellikle FIPS 186-4^[27] on tane önerilen sonlu alana sahiptir:

• Beş ana alan ${displaystyle mathbb {F} _ {p}}$ belirli asal sayılar için p 192, 224, 256, 384 ve 521 bit boyutlarında. Asal alanların her biri için bir eliptik eğri önerilir.
• Beş ikili alan ${displaystyle mathbb {F} _ {2 ^ {m}}}$ için m 163, 233, 283, 409 ve 571'e eşittir. İkili alanların her biri için bir eliptik eğri ve bir Koblitz eğri seçildi.

NIST tavsiyesi bu nedenle toplam beş asal eğri ve on ikili eğri içerir. Eğriler, görünüşte optimum güvenlik ve uygulama verimliliği için seçildi.^[28]

2013 yılında, New York Times belirtti ki İkili Eliptik Eğri Belirleyici Rastgele Bit Üretimi (veya Dual_EC_DRBG), NIST ulusal standardı olarak dahil edilmiştir. NSA, algoritmada kasıtlı bir zayıflık ve önerilen eliptik eğri içeren.^[29] RSA Güvenliği Eylül 2013'te, müşterilerine Dual_EC_DRBG'ye dayalı herhangi bir yazılımı kullanmayı bırakmalarını öneren bir tavsiye yayınladı.^[30][31] Dual_EC_DRBG'nin "bir NSA gizli operasyonu" olarak ifşa edilmesinin ardından kriptografi uzmanları, NIST tarafından önerilen eliptik eğrilerin güvenliği konusundaki endişelerini de dile getirdiler.^[32] eliptik olmayan eğri gruplarına dayalı bir şifrelemeye geri dönüş önermektedir.

Eliptik eğri kriptografisi, kripto para birimi tarafından kullanılır Bitcoin.^[33]Ethereum sürüm 2.0 kullanarak eliptik eğri çiftlerinden kapsamlı bir şekilde yararlanır BLS imzaları - belirtildiği gibi IETF taslak BLS spesifikasyonu - belirli bir Eth2 doğrulayıcısının belirli bir işlemi gerçekten doğruladığını kriptografik olarak temin etmek için.^[34][35]

Güvenlik

Yan kanal saldırıları

Diğerlerinin aksine DLP sistemleri (kare alma ve çarpma için aynı prosedürü kullanmanın mümkün olduğu durumlarda), EC ekleme, ikiye katlama için önemli ölçüde farklıdır (P = Q) ve genel ekleme (P ≠ Q) kullanılan koordinat sistemine bağlı olarak. Sonuç olarak, karşı koymak önemlidir yan kanal saldırıları (ör. zamanlama veya basit / diferansiyel güç analizi saldırıları ) örneğin, sabit kalıp penceresi (a.k.a. tarak) yöntemlerini kullanma^{[açıklama gerekli ][36]} (bunun hesaplama süresini artırmadığını unutmayın). Alternatif olarak bir Edwards eğrisi; bu, aynı işlemle iki katına çıkarma ve ekleme yapılabilen özel bir eliptik eğri ailesidir.^[37] ECC sistemleri için bir başka endişe, hata saldırıları özellikle koşarken akıllı kartlar.^[38]

Arka kapılar

Kriptografik uzmanlar, Ulusal Güvenlik Ajansı bir kleptografik arka kapıdan en az bir eliptik eğri tabanlı sözde rastgele oluşturucu.^[39] Eski NSA yüklenicisi tarafından sızdırılan dahili notlar, Edward Snowden, NSA'nın bir arka kapı koymasını önerin. Çift EC DRBG standart.^[40] Olası arka kapının bir analizi, algoritmanın gizli anahtarına sahip bir rakibin, yalnızca 32 baytlık PRNG çıkışı verilen şifreleme anahtarlarını elde edebileceği sonucuna vardı.^[41]

SafeCurves projesi, güvenli bir şekilde uygulanması kolay ve arka kapı olasılığını en aza indirgemek için tamamen kamu tarafından doğrulanabilir bir şekilde tasarlanmış eğrileri kataloglamak için başlatıldı.^[42]

Kuantum bilişim saldırıları

Shor'un algoritması bir varsayım üzerinde ayrı logaritmalar hesaplayarak eliptik eğri kriptografisini kırmak için kullanılabilir kuantum bilgisayar. 256 bit modüllü (128 bit güvenlik seviyesi) bir eğriyi kırmak için en son kuantum kaynak tahminleri 2330 kübit ve 126 milyar Toffoli kapıları.^[43] Buna karşılık, Shor'un algoritmasını kullanarak RSA algoritması, 2048 bitlik RSA anahtarı için 4098 kübit ve 5,2 trilyon Toffoli geçidi gerektirir, bu da ECC'nin kuantum bilgisayarlar için RSA'dan daha kolay bir hedef olduğunu gösterir. Tüm bu rakamlar, şimdiye kadar yapılmış herhangi bir kuantum bilgisayarı büyük ölçüde aşıyor ve tahminler, bu tür bilgisayarların yaratılmasının on yıl veya daha uzun bir süre uzakta olduğunu gösteriyor.^{[kaynak belirtilmeli ]}

Supersingular Isogeny Diffie – Hellman Anahtar Değişimi sağlar kuantum sonrası güvenli eliptik eğri şifreleme formu kullanarak eş genler uygulamaya Diffie – Hellman anahtar değişimleri. Bu anahtar değişimi, mevcut eliptik eğri kriptografisi ile aynı alan aritmetiğinin çoğunu kullanır ve şu anda kullanılan birçok genel anahtar sistemine benzer hesaplama ve iletim ek yükü gerektirir.^[44]

Ağustos 2015'te NSA, "çok da uzak olmayan bir gelecekte" dirençli yeni bir şifre paketine geçmeyi planladığını duyurdu. kuantum saldırılar. "Ne yazık ki, eliptik eğri kullanımındaki artış, kuantum hesaplama araştırmasında devam eden ilerleme gerçeğine karşı çıktı ve kriptografik stratejimizin yeniden değerlendirilmesini gerektirdi."^[3]

Geçersiz eğri saldırısı

ECC kullanıldığında Sanal makineler, bir saldırgan tam bir PDH özel anahtarı almak için geçersiz bir eğri kullanabilir.^[45]

Patentler

En az bir ECC şeması (ECMQV ) ve bazı uygulama teknikleri patent kapsamındadır.

Alternatif gösterimler

Eliptik eğrilerin alternatif gösterimleri şunları içerir:

• Hessian eğrileri
• Edwards eğrileri
• Bükülmüş eğriler
• Bükülmüş Hessen eğrileri
• Twisted Edwards eğrisi
• İkiye katlama yönelimli Doche – Icart – Kohel eğrisi
• Üçlü odaklı Doche – Icart – Kohel eğrisi
• Jacobian eğrisi
• Montgomery eğrileri

Ayrıca bakınız

Notlar

Referanslar

• Jacques Vélu, Courbes eliptikleri (...), Société Mathématique de France, 57, 1-152, Paris, 1978.

Dış bağlantılar

• Eliptik Eğriler -de Stanford Üniversitesi