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

Anahtar Boyu

ECDLP'yi çözmek için bilinen en hızlı algoritmaları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  olacak şekilde  ü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  'da sadece toplamın ve çarpmanın değil, aynı zamanda tersinin de gerekli olduğunu göstermektedir. Ters işlem (verilen  için  olacak şekilde bir  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  ile temsil edilir:  Jacobian sisteminde bir nokta üç koordinat ile de temsil edilir (X, Y, Z) ama farklı bir ilişki kullanılır  López-Dahab sisteminde ise ilişki:  değiştirilmiş Jacobian sisteminde aynı ilişkiler kullanılır ancak hesaplamalar için dört koordinat  saklanır ve kullanılır; ve Chudnovsky Jacobian sisteminde beş koordinat  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 ; örneğin  veya ) ç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, ü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.

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 rasgele ü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.