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 .
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 .
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.
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: .
Hagyja, hogy Bob üzenetet küldjön Alice-nek, akinek a nyilvános kulcsa .
Az üzenet kézhezvétele után Alice a következő lépéseket hajtja végre az üzenet visszafejtéséhez:
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 .
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 .
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] .
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 |
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éseAz 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 .
A McEliece kriptorendszer fő hátrányai [6] :