McEliece şifreleme sistemi - McEliece cryptosystem

İçinde kriptografi, McEliece şifreleme sistemi bir asimetrik şifreleme algoritması 1978 yılında Robert McEliece.^[1] Kullanılacak bu tür ilk şema buydu rastgeleleştirme şifreleme sürecinde. Algoritma, kriptografik toplulukta hiçbir zaman fazla kabul görmedi, ancak "kuantum sonrası kriptografi ", kullanarak saldırılara karşı bağışık olduğu için Shor'un algoritması ve - daha genel olarak - Fourier örneklemesini kullanarak koset durumlarını ölçmek.^[2]

Algoritma şunun sertliğine dayanmaktadır kod çözme bir genel doğrusal kod (olduğu bilinen NP-zor^[3]). Özel anahtarın açıklaması için bir hata düzeltme kodu etkin bir kod çözme algoritmasının bilindiği ve bunu düzeltebilen ${ displaystyle t}$ hatalar. Orijinal algoritma kullanır ikili Goppa kodları (geometrik alt alan kodları Goppa kodları karakteristik 2) 'nin sonlu alanları üzerinde bir cins-0 eğrisi; Patterson'dan kaynaklanan bir algoritma sayesinde bu kodlar verimli bir şekilde çözülebilir.^[4] Genel anahtar, seçilen kodu genel bir doğrusal kod olarak gizleyerek özel anahtardan türetilir. Bunun için kodun jeneratör matrisi ${ displaystyle G}$ rastgele seçilen iki ters çevrilebilir matris tarafından tedirgin edilir ${ displaystyle S}$ ve ${ displaystyle P}$ (aşağıya bakınız).

Bu şifreleme sisteminin çeşitleri, farklı kod türleri kullanılarak mevcuttur. Çoğunun daha az güvenli olduğu kanıtlandı; tarafından kırıldılar yapısal kod çözme.

Goppa kodlu McEliece şimdiye kadar kriptanalize direndi. Bilinen en etkili saldırılar bilgi seti kod çözme algoritmalar. Bir 2008 belgesi hem bir saldırıyı hem de bir düzeltmeyi anlatıyor.^[5] Başka bir makale, kuantum hesaplama için, bilgi seti kod çözmedeki gelişmeler nedeniyle anahtar boyutlarının dört kat artırılması gerektiğini gösteriyor.^[6]

McEliece şifreleme sisteminin bazı avantajları vardır, örneğin, RSA. Şifreleme ve şifre çözme daha hızlıdır.^[7] Uzun zamandır McEliece'nin üretim yapmak için kullanılamayacağı düşünülüyordu. imzalar. Bununla birlikte, bir imza şeması temel alınarak oluşturulabilir. Niederreiter şema, McEliece şemasının ikili varyantı. McEliece'nin ana dezavantajlarından biri, özel ve genel anahtarların büyük matrisler olmasıdır. Standart bir parametre seçimi için, genel anahtar 512 kilobit uzunluğundadır.

Şema tanımı

McEliece üç algoritmadan oluşur: bir genel ve bir özel anahtar üreten olasılıklı bir anahtar oluşturma algoritması, olasılıklı şifreleme algoritması ve deterministik bir şifre çözme algoritması.

Bir McEliece dağıtımındaki tüm kullanıcılar bir dizi ortak güvenlik parametresini paylaşır: ${ displaystyle n, k, t}$ .

Anahtar oluşturma

Prensip, Alice'in doğrusal bir kod seçmesidir. ${ displaystyle C}$ verimli bir kod çözme algoritması bildiği bazı kodlar ailesinden ve ${ displaystyle C}$ kamuya açık bilgiler ancak kod çözme algoritmasını gizli tutun. Böyle bir kod çözme algoritması sadece bilmeyi gerektirmez ${ displaystyle C}$ , rasgele bir jeneratör matrisini bilmek anlamında, ancak birinin belirtilirken kullanılan parametreleri bilmesini gerektirir ${ displaystyle C}$ seçilen kodlar ailesinde. Örneğin, ikili Goppa kodları için, bu bilgi Goppa polinomu ve kod yer belirleyicileri olacaktır. Bu nedenle Alice, uygun şekilde gizlenmiş bir jeneratör matrisini yayınlayabilir. ${ displaystyle C}$ alenen.

Daha spesifik olarak, adımlar aşağıdaki gibidir:

Alice bir ikili dosya seçer ${ displaystyle (n, k)}$ -doğrusal kod ${ displaystyle C}$ (verimli) düzeltme yeteneğine sahip ${ displaystyle t}$ bazı büyük kod ailesinden gelen hatalar, ör. ikili Goppa kodları. Bu seçim, verimli bir kod çözme algoritmasına yol açmalıdır ${ displaystyle A}$ . Ayrıca ${ displaystyle G}$ herhangi bir jeneratör matrisi olabilir ${ displaystyle C}$ . Herhangi bir doğrusal kodun birçok üretici matrisi vardır, ancak çoğu zaman bu kod ailesi için doğal bir seçim vardır. Bunun ortaya çıkacağını bilmek ${ displaystyle A}$ bu yüzden gizli tutulmalıdır.
Alice rastgele seçer ${ displaystyle k times k}$ ikili tekil olmayan matris ${ displaystyle S}$ .
Alice rastgele seçer ${ displaystyle n kere n}$ permütasyon matrisi ${ displaystyle P}$ .
Alice hesaplar ${ displaystyle k kere n}$ matris ${ displaystyle { hat {G}} = SGP}$ .
Alice'in genel anahtarı ${ displaystyle ({ hat {G}}, t)}$ ; onun özel anahtarı ${ displaystyle (S, P, A)}$ . Bunu not et ${ displaystyle A}$ seçim için kullanılan parametreler olarak kodlanabilir ve saklanabilir ${ displaystyle C}$ .

Mesaj şifreleme

Diyelim ki Bob bir mesaj göndermek istiyor m açık anahtarı olan Alice'e ${ displaystyle ({ hat {G}}, t)}$ :

Bob mesajı kodluyor ${ displaystyle m}$ ikili uzunluk dizisi olarak ${ displaystyle k}$ .
Bob vektörü hesaplar ${ displaystyle c ^ { prime} = m { hat {G}}}$ .
Bob rastgele üretir ${ displaystyle n}$ -bit vektör ${ displaystyle z}$ tam olarak içeren ${ displaystyle t}$ olanlar (uzunluk vektörü ${ displaystyle n}$ ve ağırlık ${ displaystyle t}$ )^[1]
Bob şifreli metni şu şekilde hesaplar: ${ displaystyle c = c ^ { prime} + z}$ .

Mesaj şifre çözme

Alındıktan sonra ${ displaystyle c}$ Alice, mesajın şifresini çözmek için aşağıdaki adımları gerçekleştirir:

Alice, tersini hesaplar ${ displaystyle P}$ (yani ${ displaystyle P ^ {- 1}}$ ).
Alice hesaplar ${ displaystyle { şapka {c}} = cP ^ {- 1}}$ .
Alice, kod çözme algoritmasını kullanır ${ displaystyle A}$ çözmek için ${ displaystyle { şapka {c}}}$ -e ${ displaystyle { şapka {m}}}$ .
Alice hesaplar ${ displaystyle m = { şapka {m}} S ^ {- 1}}$ .

Mesaj şifre çözme kanıtı

Bunu not et ${ displaystyle { hat {c}} = cP ^ {- 1} = m { hat {G}} P ^ {- 1} + zP ^ {- 1} = mSG + zP ^ {- 1}}$ ,ve şu ${ displaystyle P}$ bir permütasyon matrisidir, dolayısıyla ${ displaystyle zP ^ {- 1}}$ ağırlığı var ${ displaystyle t}$ .

Goppa kodu ${ displaystyle G}$ kadar düzeltebilir ${ displaystyle t}$ hatalar ve kelime ${ displaystyle mSG}$ en fazla uzakta ${ displaystyle t}$ itibaren ${ displaystyle cP ^ {- 1}}$ . Bu nedenle, doğru kod sözcüğü ${ displaystyle { şapka {m}} = mS}$ elde edildi.

Tersi ile çarpma ${ displaystyle S}$ verir ${ displaystyle m = { şapka {m}} S ^ {- 1} = mSS ^ {- 1}}$ , düz metin mesajıdır.

Anahtar boyutları

McEliece başlangıçta şu güvenlik parametresi boyutlarını önerdi: ${ displaystyle n = 1024, k = 524, t = 50}$ ,^[1] 524 * (1024−524) = 262.000 bit genel anahtar boyutuyla sonuçlanır^{[açıklama gerekli ]}. Son analiz, parametre boyutlarını önermektedir. ${ displaystyle n = 2048, k = 1751, t = 27}$ 80 için güvenlik bitleri standart cebirsel kod çözme kullanılırken veya ${ displaystyle n = 1632, k = 1269, t = 34}$ Goppa kodu için liste kod çözme kullanıldığında, sırasıyla 520,047 ve 460,647 bitlik genel anahtar boyutlarına yol açar.^[5] Kuantum bilgisayarlara karşı dayanıklılık için, boyutları ${ displaystyle n = 6960, k = 5413, t = 119}$ 8,373,911 bitlik genel anahtar boyutu veren Goppa kodu önerildi.^[8]

Saldırılar

Saldırı, açık anahtarı bilen bir düşmandan oluşur ${ displaystyle ({ hat {G}}, t)}$ ancak gizli anahtar değil, düz metni ele geçirilen bazı şifreli metinlerden çıkararak ${ displaystyle y in mathbb {F} _ {2} ^ {n}}$ . Bu tür girişimler gerçekleştirilemez olmalıdır.

McEliece için iki ana saldırı dalı vardır:

Kaba kuvvet / Yapılandırılmamış saldırılar

Saldırgan bilir ${ displaystyle { hat {G}}}$ hangisinin üreteç matrisi ${ displaystyle (n, k)}$ kodu ${ displaystyle { hat {C}}}$ kombinasyonel olarak düzeltebilen ${ displaystyle t}$ Saldırgan şu gerçeği göz ardı edebilir: ${ displaystyle { hat {C}}}$ gerçekten belirli bir aileden seçilen yapılandırılmış bir kodun gizlenmesidir ve bunun yerine herhangi bir doğrusal kodla kod çözme için bir algoritma kullanır. Kodun her bir kod sözcüğünden geçmek gibi bu tür birkaç algoritma vardır, sendrom kod çözme veya bilgi seti kod çözme.

Bununla birlikte, genel bir doğrusal kodu çözmenin, NP-zor,^[3] ancak ve yukarıda bahsedilen yöntemlerin tümü üssel çalışma süresine sahiptir.

2008'de Bernstein, Lange ve Peters^[5] Stern'ün Bilgi Kümesi Kod Çözme yöntemini kullanarak orijinal McEliece şifreleme sistemine pratik bir saldırıyı anlattı.^[9]Başlangıçta McEliece tarafından önerilen parametreleri kullanarak, saldırı 2'de gerçekleştirilebilir.^60.55 bit işlemleri. Saldırı olduğu için utanç verici derecede paralel (düğümler arasında iletişim gerekli değildir), mütevazı bilgisayar kümelerinde günler içinde gerçekleştirilebilir.

Yapısal saldırılar

Saldırgan, bunun "yapısını" kurtarmaya çalışabilir. ${ displaystyle C}$ , böylece verimli kod çözme algoritmasının kurtarılması ${ displaystyle A}$ veya yeterince güçlü, verimli bir kod çözme algoritması.

Hangi kod ailesi ${ displaystyle C}$ seçilmesi, bunun saldırgan için mümkün olup olmadığını tamamen belirler. McEliece için birçok kod ailesi önerilmiştir ve bunların çoğu, örneğin verimli bir kod çözme algoritmasını kurtaran saldırılar bulunması anlamında tamamen "kırılmıştır". Reed-Solomon kodları.

Başlangıçta önerilen ikili Goppa kodları, yapısal saldırılar tasarlama girişimlerine büyük ölçüde direnen birkaç önerilen kod ailesinden biri olmaya devam ediyor.

Referanslar

^ ^a ^b ^c McEliece, Robert J. (1978). "Cebirsel Kodlama Teorisine Dayalı Açık Anahtarlı Bir Şifreleme Sistemi" (PDF). DSN İlerleme Raporu. 44: 114–116. Bibcode:1978DSNPR..44..114M.
^ Dinh, Asın; Moore, Cristopher; Russell, Alexander (2011). Rogaway, Philip (ed.). Kuantum Fourier örnekleme saldırılarına direnen McEliece ve Niederreiter şifreleme sistemleri. Kriptolojideki Gelişmeler - CRYPTO 2011. Bilgisayar Bilimi Ders Notları. 6841. Heidelberg: Springer. sayfa 761–779. doi:10.1007/978-3-642-22792-9_43. ISBN 978-3-642-22791-2. BAY 2874885.
^ ^a ^b Berlekamp, Elwyn R .; McEliece, Robert J .; Van Tilborg, Henk C.A. (1978). "Bazı Kodlama Sorunlarının Doğasında Bulunan İnatçılık Üzerine". Bilgi Teorisi Üzerine IEEE İşlemleri. IT-24 (3): 384–386. doi:10.1109 / TIT.1978.1055873. BAY 0495180.
^ N. J. Patterson (1975). "Goppa kodlarının cebirsel kod çözümü". Bilgi Teorisi Üzerine IEEE İşlemleri. IT-21 (2): 203–207. doi:10.1109 / TIT.1975.1055350.
^ ^a ^b ^c Bernstein, Daniel J .; Lange, Tanja; Peters, Christiane (8 Ağustos 2008). McEliece şifreleme sistemine saldırı ve savunma. Proc. 2. Uluslararası Post Kuantum Kriptografi Çalıştayı. Bilgisayar Bilimlerinde Ders Notları. 5299. sayfa 31–46. CiteSeerX 10.1.1.139.3548. doi:10.1007/978-3-540-88403-3_3. ISBN 978-3-540-88402-6.
^ Bernstein, Daniel J. (2010). Sendrier Nicolas (ed.). Grover ve McEliece (PDF). Post-kuantum kriptografi 2010. Bilgisayar Bilimleri Ders Notları. 6061. Berlin: Springer. sayfa 73–80. doi:10.1007/978-3-642-12929-2_6. ISBN 978-3-642-12928-5. BAY 2776312.
^ "eBATS: ECRYPT Asimetrik Sistemlerin Kıyaslanması". bench.cr.yp.to. 25 Ağustos 2018. Alındı 1 Mayıs 2020.
^ Daniel Augot; et al. (7 Eylül 2015). "Uzun vadeli güvenli post-kuantum sistemlerin ilk önerileri" (PDF). PQCRYPTO: Uzun Süreli Güvenlik için Kuantum Sonrası Kriptografi.
^ Jacques Stern (1989). Küçük ağırlıklı kod sözcükleri bulmak için bir yöntem. Kodlama Teorisi ve Uygulamaları. Bilgisayar Bilimlerinde Ders Notları. 388. Springer Verlag. s. 106–113. doi:10.1007 / BFb0019850. ISBN 978-3-540-51643-9.

Dış bağlantılar

Alfred J. Menezes; Scott A. Vanstone; A. J. Menezes; Paul C. van Oorschot (1996). "Bölüm 8: Açık Anahtarlı Şifreleme". Uygulamalı Kriptografi El Kitabı. CRC Basın. ISBN 978-0-8493-8523-0.

"Kuantum Bilgisayarlar? Geleceğin İnternet Güvenlik Kodu Kırıldı". Günlük Bilim. Eindhoven Teknoloji Üniversitesi. 1 Kasım 2008.

"Klasik McEliece". (NIST'e gönderim Kuantum Sonrası Kriptografi Standardizasyonu Proje)

[McEliece-1] McEliece, Robert J. (1978). "Cebirsel Kodlama Teorisine Dayalı Açık Anahtarlı Bir Şifreleme Sistemi" (PDF). DSN İlerleme Raporu. 44: 114–116. Bibcode:1978DSNPR..44..114M.

[quantum-fourier-2] Dinh, Asın; Moore, Cristopher; Russell, Alexander (2011). Rogaway, Philip (ed.). Kuantum Fourier örnekleme saldırılarına direnen McEliece ve Niederreiter şifreleme sistemleri. Kriptolojideki Gelişmeler - CRYPTO 2011. Bilgisayar Bilimi Ders Notları. 6841. Heidelberg: Springer. sayfa 761–779. doi:10.1007/978-3-642-22792-9_43. ISBN 978-3-642-22791-2. BAY 2874885.

[intractability-3] Berlekamp, Elwyn R .; McEliece, Robert J .; Van Tilborg, Henk C.A. (1978). "Bazı Kodlama Sorunlarının Doğasında Bulunan İnatçılık Üzerine". Bilgi Teorisi Üzerine IEEE İşlemleri. IT-24 (3): 384–386. doi:10.1109 / TIT.1978.1055873. BAY 0495180.

[Patterson-4] N. J. Patterson (1975). "Goppa kodlarının cebirsel kod çözümü". Bilgi Teorisi Üzerine IEEE İşlemleri. IT-21 (2): 203–207. doi:10.1109 / TIT.1975.1055350.

[fix-5] Bernstein, Daniel J .; Lange, Tanja; Peters, Christiane (8 Ağustos 2008). McEliece şifreleme sistemine saldırı ve savunma. Proc. 2. Uluslararası Post Kuantum Kriptografi Çalıştayı. Bilgisayar Bilimlerinde Ders Notları. 5299. sayfa 31–46. CiteSeerX 10.1.1.139.3548. doi:10.1007/978-3-540-88403-3_3. ISBN 978-3-540-88402-6.

[6] Bernstein, Daniel J. (2010). Sendrier Nicolas (ed.). Grover ve McEliece (PDF). Post-kuantum kriptografi 2010. Bilgisayar Bilimleri Ders Notları. 6061. Berlin: Springer. sayfa 73–80. doi:10.1007/978-3-642-12929-2_6. ISBN 978-3-642-12928-5. BAY 2776312.

[7] "eBATS: ECRYPT Asimetrik Sistemlerin Kıyaslanması". bench.cr.yp.to. 25 Ağustos 2018. Alındı 1 Mayıs 2020.

[PQcrypto-initial-8] Daniel Augot; et al. (7 Eylül 2015). "Uzun vadeli güvenli post-kuantum sistemlerin ilk önerileri" (PDF). PQCRYPTO: Uzun Süreli Güvenlik için Kuantum Sonrası Kriptografi.

[9] Jacques Stern (1989). Küçük ağırlıklı kod sözcükleri bulmak için bir yöntem. Kodlama Teorisi ve Uygulamaları. Bilgisayar Bilimlerinde Ders Notları. 388. Springer Verlag. s. 106–113. doi:10.1007 / BFb0019850. ISBN 978-3-540-51643-9.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]