McEliece

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2021. január 9-én felülvizsgált verziótól ; az ellenőrzések 5 szerkesztést igényelnek .

A McEliece  egy algebrai kódolási elméleten alapuló nyilvános kulcsú kriptorendszer , amelyet 1978-ban fejlesztett ki Robert McEliece [1] . Ez volt az első séma, amely véletlenszerűsítést alkalmaz a titkosítási folyamatban. Az algoritmus nem kapott széles körű elismerést a kriptográfiában , ugyanakkor jelölt a posztkvantum kriptográfiára , mivel ellenáll a Shor Algorithm [2] támadásainak .

Az algoritmus a teljes lineáris kódok dekódolásának bonyolultságán alapul (az általános dekódolási probléma NP-nehéz ) [3] .

A privát kulcs leírására egy hibajavító kódot választanak, amelyhez ismert egy hatékony dekódoló algoritmus, és amely képes kijavítani a hibákat. Az algoritmus bináris Gopp kódokat használ , amelyek könnyen dekódolhatók a Peterson-algoritmusnak köszönhetően . A nyilvános kulcsot úgy kapjuk meg, hogy a választott kódot teljes lineárisnak álcázzuk. Ehhez a generáló mátrixot először a jobb oldalon meg kell szorozni a permutációs mátrixszal , majd a bal oldalon lévő nem szinguláris mátrixszal (lásd a munkaalgoritmust ).

A kriptorendszernek számos változata létezik, amelyek különböző típusú kódokat használnak. A legtöbbjük kevésbé biztonságos. Külön figyelmet érdemel a kriptorendszer paramétereinek megválasztása [4] .

Eddig a Goppa kódokkal rendelkező McElice-t nem kriptoanalízissel végezték [5] . A legismertebb támadások az adatkészlet -dekódoló algoritmust használják . A legújabb munkák a rendszer elleni támadásokat és annak védelmét egyaránt leírják [6] . Más tanulmányok kimutatták, hogy a kvantumszámításhoz a kulcsméretet négy nagyságrenddel kell növelni az adatkészlet-dekódolás fejlesztése miatt [2] .

A kriptorendszernek számos előnye van, például az RSA -val szemben . A titkosítás és a visszafejtés gyorsabb, és a kulcs hosszának növekedésével az adatvédelem mértéke sokkal gyorsabban növekszik. Sokáig azt hitték, hogy a McEliece nem használható EDS -re . Kiderült azonban, hogy a Niederreiter kriptorendszeren (McEliece módosította) alapuló EDS-sémát lehet építeni . Mivel a használt kódoktól függően ez a két titkosítási rendszer ugyanazt a kódproblémát fejezi ki, ma már vitatható, hogy a McEliece alkalmazható hitelesítési problémák esetén .

A hiányosságok miatt a McEliece-t ritkán használják. Az egyik kivétel a McElice használata a Freenet -szerű ENTROPY hálózat titkosítására .

Bevezetés a Goppa kódokba

Leírás

A goppa polinom egy polinom egy mező felett , ahol , és . Meghatározunk egy -dimenziós részhalmazt is a : mezőbővítmény felett , ami igaz bármely . Továbbá a mező feletti kódszó esetében a függvény definiálva van .

A Goppa kód minden olyan kódszóból áll, amely kielégíti a . Ez azt jelenti, hogy a polinom oszt .

A hosszú Goppa-kód mérete nagyobb vagy egyenlő , és a minimális kód távolság nagyobb vagy egyenlő, mint .

Az ellenőrző mátrix a következő formájú:

.

Ha a Goppa-polinom egy irreducibilis polinom a mezőn , akkor egy ilyen kód minimális távolsága nagyobb vagy egyenlő, mint . A következőkben azt feltételezzük, hogy .

A kriptológiai alkalmazások irreducibilis, bináris Goppa-kódot használnak paraméterekkel .

A

Számos oka van a Goppa kódok McEliece kriptorendszerben való használatának. Először is számos gyors polinomidő dekódoló algoritmus létezik [7] . Másodszor, bármely mező feletti irreducibilis polinom alkalmas Goppa kód megadására, a kód generáló mátrixa szinte véletlenszerű. Ezért a Goppa kódokat nagyon könnyű beállítani, ugyanakkor nehéz felismerni. Rögzített kódszóhosszúsághoz sok kód létezik. Például egy hosszúságú kódhoz , amely akár hibákat is kijavíthat, körülbelül különböző Goppa-kódok léteznek. Számuk exponenciálisan növekszik a szó hosszától és a generáló polinom mértékétől függően.

Műveleti algoritmus

A McEliece három algoritmusból áll:

Az üzenet szövege egy hosszvektor az utolsó mező felett .

A rendszer összes felhasználója megosztja a biztonsági beállításokat: .

Kulcsgenerálás

  1. Alice -lineáris hibajavító kódot választ. Ezután a generátor mátrixot kiszámítják a kódhoz .
  2. Az eredeti kód visszaállításának megnehezítésére Alice véletlenszerű , nem szinguláris mátrixot generál .
  3. Alice véletlenszerű permutációs mátrixot generál .
  4. Alice kiszámítja a mátrixot .
  5. A nyilvános kulcs egy pár . A privát kulcs a készlet .

Üzenettitkosítás

Hagyja, hogy Bob üzenetet küldjön Alice-nek, akinek a nyilvános kulcsa .

  1. Bob üzenetét bináris karakterek hosszúságú sorozataiként mutatja be .
  2. Bob egy véletlenszerű hosszúságú vektort generál , amelynek Hamming súlya van .
  3. Bob kiszámolja a rejtjelezett szöveget , miközben elküldi Alice-nek.

Üzenet visszafejtése

Az üzenet kézhezvétele után Alice a következő lépéseket hajtja végre az üzenet visszafejtéséhez:

  1. Alice kiszámítja az inverz mátrixot ;
  2. Alice kiszámol ;
  3. Alice egy dekódoló algoritmust használ a kód megszerzéséhez ;
  4. Alice kiszámolja .

Algoritmus helyessége

Mutassuk meg, hogy a kriptorendszer [5] fő tulajdonsága teljesül , azaz .

Bob küldi . Alice kiszámolja . Mivel  egy permutációs mátrix, akkor a súly legfeljebb .

A Gopp kódja a hibákat kijavítja . Hamming távolság , így Alice a megfelelő üzenetet kapja . Alice ezután kiszámítja az eredeti üzenetet .

Példa az algoritmus működésére

Legyen egy irreducibilis, bináris Goppa-kód paraméterekkel , ahol  egy irreducibilis fokszámú polinom a mező felett , és .

Alice véletlenszerűen generál egy ilyen kód generátormátrixát

,

kiválaszt egy mátrixot

és egy permutációs mátrix

,

Akkor

.

Ez a mátrix nyilvános kulcsként és . Ha Bob üzenetet akar küldeni Alice-nek, először generál egy vektort, amelynek súlya , például .

Kiszámítja a titkosított szöveget

és elküldi Alice-nek.

Miután megkapta az üzenetet, Alice először számol

.

A permutációk miatt a hibák átkerültek az első és a hatodik karakterre. Alice egy gyors dekódoló algoritmus segítségével megtalálja

.

Találatok .

És a végén Alice megkapja .

Kulcsméretek

Kezdetben a következő paramétereket javasolták: , ennek eredményeként a nyilvános kulcs mérete 524*(1024-524) = 262 000 bit volt. Egy közelmúltbeli elemzésben a következő paramétereket javasolták: 80 bites biztonságra, ha hagyományos algebrai dekódolást használunk, vagy ha dekódoló táblázatot használunk a Goppa kódhoz. Ebben az esetben a nyilvános kulcs 520,047, illetve 460,647 bitre nő. A kvantumszámítógépekkel szembeni stabilitás érdekében a paramétereket értékre , a nyilvános kulcs méretét pedig 8 373 911 bitre kell növelni [1] [6] .

Támadások

A rendszer kriptográfiai erőssége két összetett számítási problémán alapul: a kulcstér kimerítő keresésén és a maximális valószínűségű dekódoláson. A szakirodalom meglehetősen nagyszámú McEliece elleni támadást ír le [8] . Egyes támadások, úgynevezett strukturális támadások a nyilvános kulcs által generált kód dekóderének felépítésére/visszafejtésére irányuló kísérleten alapulnak . Ha egy ilyen próbálkozás sikeres, akkor a privát kulcs felfedésre kerül, és a kriptorendszer teljesen megszakad. A mátrix által generált kód és a mátrix által generált kód ugyanabba az egyenértékű osztályba tartozik. A támadónak össze kell hasonlítania az egyes osztályok reprezentatív kódját, hogy meghatározza az egyenértékű kódot. Mivel az egyenértékű osztályok nagyon alacsony fogyasztásúak, ez a folyamat még a legerősebb számítógépek képességeit is meghaladja. Az eredeti paraméterek esetében ez a strukturális támadás több kódot igényel [5] .

Más támadások célja az üzenet eredeti szövegének kinyerése a titkosított üzenetből. Legtöbbjük adathalmaz dekódoláson (ISD  ) vagy a születésnapi paradoxonon [9] , ezek általánosításán és továbbfejlesztésén alapul. Vannak támadások, mint például az iteratív dekódolás [3] és a statikus dekódolás, de ezek nem sikeresek. Az ISD-támadás bizonyult a legkevésbé nehéznek. Az elmúlt években számos algoritmust és azok fejlesztéseit ismertették. A legfontosabbakat a táblázat tartalmazza a Goppa kód bináris dekódolási költségével együtt. Ezen algoritmusok korlátozó indikátorai ismertek [10] .

Év Algoritmus Nehézségi fok ( )
1986 Adams-Meyer 80.7
1988 Lee Brickell 70,89
1989 zord 66.21
1994 Canteout Chabannes 65.5
1998 Canteout-Shabant 64.1
2008 Bernstein-Lang-Peters 60.4
2009 Finiaz-Sendreir 59.9

A Stern támadási algoritmus leírása

Legyen  egy hosszúságú kód a mező felett , és a -dimenziós vektornak van távolsága a kódszótól , akkor  olyan elem , amelynek távolsága van -tól . Ellenkező esetben, ha  egy hosszúságkód olyan mező felett van, amelynek minimális távolsága kisebb, mint , akkor a súlyelem nem lehet -ben , hanem -ben kell lennie . Vagy másképpen,  olyan elem , amelynek távolsága van -tól .

A McEliece kriptorendszer rejtjelezett szövegének távolsága a kód egyedi legközelebbi kódszavaitól legalább . A támadó ismeri a kód generátormátrixát, és könnyen hozzáadhatja a kód generátormátrixát . Az egyetlen súlykód  szó a . Miután megtalálta ezt a kódszót, a támadó megtalálja és könnyen megkapja a kívánt szöveget. Érdemes megfontolni, hogy a dekódolás némi egyszerűsítést ad:

ha van dimenziója , akkor van dimenziója . A Stern algoritmus lehetővé teszi, hogy megtalálja a legkisebb súlyú kódszót.

A legkisebb súlyú kódszó megkeresése

Az algoritmus bemenete egy szám és a mező feletti kód méretének ellenőrző mátrixa . A lineáris algebrai módszerek segítségével mindig lehetséges egy ellenőrző mátrix kinyerése a generáló mátrixból.

Véletlenszerűen kiválasztott a mátrix oszlopaiból . Ezután véletlenszerűen kiválasztunk egy -dimenziós alteret , amely a fennmaradó részhalmazokat két részhalmazra osztja és . Olyan kódszóhoz, amelynek pontosan nullától eltérő bitjei vannak , pontosan nullától eltérő bitjei -ben , nullától eltérő bitjei -ban , és pontosan nem nullától eltérő bitjei vannak más oszlopokban.

A keresés három lépésből áll. Első lépésben a legegyszerűbb műveleteket alkalmazva megkapjuk az azonosságmátrixot a kiválasztott oszlopokból . Ez nem tehető meg, ha az eredeti almátrix nem invertálható, akkor az algoritmus újraindul. Az egyes oszlopok adaptív kiválasztásának köszönhetően elkerülhetők az újraindítások veszteségei.

A második lépésben az almátrix az identitásmátrix, az oszlopkészlet a soroknak felel meg . A halmaz minden dimenziós részhalmazához a rendszer kiszámítja az egyes sorok oszlopainak összegét . Az eredmény egy -bites vektor . Hasonlóképpen a halmaz minden dimenziós részhalmazához .

A harmadik lépésben minden ütközésnél a -ban lévő oszlopok összege . Ez az összeg egy -bites vektor lesz. Ha az összegnek súlya van , akkor azt úgy kapjuk meg, hogy a megfelelő oszlopokat hozzáadjuk az almátrixhoz. Ezek az oszlopok a és a kívánt súlyú kódszóval együtt alkotják .

Hátrányok

A McEliece kriptorendszer fő hátrányai [6] :

  • A nyilvános kulcs mérete túl nagy. Amikor Goppa kódokat használunk a McEliece által javasolt paraméterekkel, a nyilvános kulcs egy kicsit, ami nehézségeket okoz a megvalósításban;
  • A titkosított üzenet sokkal hosszabb, mint az eredeti;
  • Jelenleg nem széles körben használják azokat az algoritmusokat, amelyek ezt a titkosítási rendszert használják hitelesítési feladatokban.

Jegyzetek

  1. ↑ 1 2 R. J. McEliece. Az algebrai kódolás elméletén alapuló nyilvános kulcsú kriptorendszer  // DSN előrehaladási jelentés 42-44. — 1978. Archiválva : 2021. november 2.
  2. 1 2 Dinh H. , Moore C. , Russell A. McEliece és Niederreiter kriptorendszerek, amelyek ellenállnak a kvantum-Fourier-mintavételezési támadásoknak  // Advances in Cryptology - CRYPTO 2011 : 31. Annual Cryptology Conference, CA4, USA, Santa Barbara, 1. augusztus 1. 2011, Proceedings / P. Rogaway - Springer Science + Business Media , 2011. - P. 761-779. — 782 p. — ISBN 978-3-642-22791-2 — doi:10.1007/978-3-642-22792-9_43
  3. 1 2 Berlekamp E. R. , McEliece R. J. , Tilborg H. C. A. v. Egyes kódolási problémák eredendő megoldhatatlanságáról  // IEEE Trans . inf. Elmélet / F. Kschischang - IEEE , 1978. - 1. kötet. 24, Iss. 3. - P. 384-386. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1978.1055873
  4. Niebuhr R. , Meziani M. , Bulygin S. , Buchmann J. Parameters Selecting for Secure McEliece-based Cryptosystems  (angol) // International Journal of Information Security - Springer Science + Business Media , 2012. - Vol. 11, Iss. 3. - P. 137-147. — ISSN 1615-5262 ; 1615-5270 - doi:10.1007/S10207-011-0153-2
  5. ↑ 1 2 3 4 5 A. Valentin. Goppa kódok és felhasználásuk a McEliece kriptorendszerekben  // Syracuse University SURFACE. - 2015. Archiválva : 2016. december 21.
  6. ↑ 1 2 3 4 Bernstein D. J. , Lange T. , Peters C. A McEliece kriptorendszer megtámadása és védelme  // Post-Quantum Cryptography : Second International Workshop , PQCrypto 2008 Cincinnati, OH, USA, október 17-19. J. Procechmanns08 . , J. Ding - Berlin , Heidelberg , New York, NY , London [stb.] : Springer Science + Business Media , 2008. - P. 31-46. — 231 p. - ( Számítástechnikai előadások jegyzetei ; 5299. kötet) - ISBN 978-3-540-88402-6 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-540-88403-3_3 D. J. Bernstein1, Tanja Lange, C. Peters. A McEliece kriptorendszer megtámadása és védelme . - 2008. Archiválva : 2016. augusztus 1.
  7. P. Loidreau. A McEliece kriptorendszer megerősítése // Springer-Verlag Berlin Heidelberg. – 2000.
  8. ↑ 1 2 D. Engelbert, R. Overbeck, A. Schmidt. A McEliece-típusú kriptorendszerek és azok biztonságának összefoglalása  // IACR Eprint archívum. - 2006. Archiválva : 2016. december 23.
  9. N. Courtois, M. Finiasz, N. Sendrier. Hogyan lehet McEliece-alapú digitális aláírási rendszert létrehozni ? - 2001. Archiválva : 2018. július 22.
  10. DJ Bernstein, T. Lange, C. Peters, HCA van Tilborg. A kódalapú kriptográfia általános dekódoló algoritmusainak kifejezett határai  // Kódolás és kriptográfia nemzetközi műhelye. - 2009. Archiválva : 2016. december 20.

Irodalom