McEliece-féle titkosító rendszer

A kriptográfiában a McEliece-féle titkosító rendszer, egy aszimmetrikus titkosító algoritmus, melyet Robert McEliece, amerikai matematikus fejlesztett ki 1978-ban.

Ez volt az első olyan algoritmus, ahol a titkosítási folyamatban véletlen-számokat használtak. Az algoritmus soha nem keltett különös figyelmet a titkosítással foglalkozó közösségben, de ez a módszer “jelölt” lehet a ‘post-kvantum titkosítási’ módszerek között, mivel immunis támadásokra, a Shor-algoritmust felhasználva, és – még általánosabban – mellékosztály állapotokat használ Fourier mintavétellel.

Egy közelmúltban nyilvánosságra került tanulmány szerint a kvantumszámítógépek alkalmazásakor a titkosító kulcsok mérete megnégyszereződik. Az algoritmus az P-hard ). elméleten alapul. A magán kulcs leírására egy hibajavító kódot választottak, mely elég hatékony dekódolási algoritmusként ismert, és képes a $t$ hibákat kijavítani.

Az eredeti algoritmus a bináris Goppa kódokat használja; ezeket könnyű dekódolni a Patterson-féle algoritmus miatt. A nyilvános kulcs a magán kulcsból származtatható azzal, hogy elrejtik a kódot, mint általános lineáris kód. Ezért $G$ generátor mátrix permutálásával, két véletlenszerűen kiválasztott invertált $S$ és $P$ mátrix-szal.

Számos titkosító rendszer létezik, különféle kódokkal. A legtöbb nem biztonságos; strukturális dekódolással könnyen feltörhető.

A McEliece, a Goppa kóddal ellenáll a kriptoanalízisnek. A következőkben ismertetjük a támadást és annak kivédését.

A McEliece-féle titkosító rendszernek van néhány előnye, például az RSA-hoz képest. A titkosítás és a titkosítás feloldása gyorsabb, és a kulcs méretének növelésekor a biztonság még gyorsabban nő.

Sokáig azt gondolták, hogy a McEliece-féle titkosító rendszer nem használható digitális aláírásra. Azonban a Niederreiter sémára épülő aláírás megvalósítható, mely a McEliece duális változata.

A McEliece-féle titkosító rendszer fő hátránya az, hogy a nyilvános és a magán kulcsok is nagy mátrixok. A nyilvános kulcs 512 kilobit hosszú. Ez azért van így, mert a gyakorlatban ritkán használják. Van egy kivétel, a Freenet-féle entrópia alkalmazás.

Eljárás definiálása

A McEliece három algoritmust tartalmaz: egy probabilista kulcs generáló algoritmust, mely létrehozza a nyilvános-, és a magán kulcsokat, a probabilisztikus titkosító algoritmust, és a determinisztikus titkosítást feloldó algoritmust. Minden - McEliece-t alkalmazó - használónak vannak biztonsági paraméterei: $n,k,t$.

Kulcs generálás

1. Vera kiválaszt egy bináris $(n,k)$ -lineáris $C$ kódot, mely képes a $t$ hibákat javítani. Ez lehet egy hatékony dekódoló algoritmus, és generál egy $k\times n$ generátor mátrixot,$G$.

2. Vera kiválaszt egy véletlenszerű $k\times k$ bináris nem szinguláris $S$ mátrixot.

3. Vera kiválaszt egy véletlenszerű $n\times n$, $P$ permutációmátrixot.

4. Vera kiszámolja a $k\times n$ mátrixot: ${\hat {G}}=SGP$.

5. Vera nyilvános kulcsa: $({\hat {G}},t)$; magán kulcsa: $(S,G,P)$.

Üzenet kódolása

Tegyük fel, hogy Sándor küld egy m üzenetet Verának, kinek a nyilvános kulcsa: $({\hat {G}},t)$.

1. Sándor kódolja az m üzenetetet, mint egy $k$ hosszúságú bináris stringet,

2. Sándor kiszámolja a $c^{\prime }=m{\hat {G}}$ vektort,

3. Sándor generál egy véletlenszerű $n$-bites vektort, $z$, mely tartalmazza a $t$-t,

4. Sándor kiszámolja a titkos szöveget, mint $c=c^{\prime }+z$.

Üzenet megfejtése

$c$ megérkezésekor, Vera a következő lépéseket teszi:

1. Vera kiszámolja a $P$ inverzét (azaz: $P^{-1}$),

2. Vera kiszámolja a ${\hat {c}}=cP^{-1}$,

3. Vera dekódoló algoritmust használ a $C$ kódra,hogy dekódolja a ${\hat {c}}$ - ${\hat {m}}$,

4. Vera kiszámolja: $m={\hat {m}}S^{-1}$.

Az üzenet megfejtésének bizonyítása

Megjegyezzük, hogy ${\hat {c}}=cP^{-1}=m{\hat {G}}P^{-1}+zP^{-1}=mSG+zP^{-1}$, és $P$ egy permutációs mátrix, így $zP^{-1}$ súlyozása többnyire $t$.

A Goppa kód, $G$ ki tudja javítani a $t$ hibákat, és az $mSG$ szó $cP^{-1}$-től $t$-re van, azért a korrekt kód szó: ${\hat {m}}=mS$ megkapható. Az $S$ inverzével szorozva, adódik $m={\hat {m}}S^{-1}=mSS^{-1}$, mely a megfejtett üzenet.

Kulcs méretek

McEliece eredetileg a következő biztonsági paramétereket javasolta: $n=1024,k=524,t=50$, mely 524*(1024-524) = 262,000 bites nyilvános kulcsot eredményez.

Egy későbbi analízis azt ajánlja, hogy $n=2048,k=1751,t=27$ legyen a paraméterek nagysága, 80 bitre, ha standard algebrai dekódolást használunk, vagy $n=1632,k=1269,t=34$, ha lista dekódolást alkalmazunk a Goppa kódra, mely megnöveli a nyilvános kulcsot 520,047 és 460,647 bitre, megfelelően.

Támadások

Egy sikeres ellenséges támadás, ismerve a $({\hat {G}},t)$ nyilvános kulcsot, de a magán kulcsot nem, eredményezheti a szöveg kikövetkeztetését a titkos írásból $y\in \mathbb {F} _{2}^{n}$. Az ilyen kísérletek nem működnek.

Ez a fejezet tárgyalja az irodalomból ismert támadási stratégiákat a McEliece rendszer ellen.

A nyers erő módszer

A támadó esetleg kitalálhatja, mi a $G$, és képes alkalmazni a Patterson algoritmust.

Ez nem valószínű n és t nagy értékeire, mivel túl sok lehetőség van a $G$, $S$ és $P$-kre.

Egy olyan támadási stratégia, mely nem igényli a $G$-t, az “információ készlet dekódolása” koncepcióra épülhet.

McEliece megemlít egy egyszerű támadási formát: ki kell választani k-t az n koordinátából véletlenszerűen abban a reményben, hogy egy k sem hibás (azaz, a kiválasztott $z$ vektor koordinátái közül egy sem 1 bites), és kalkulálja az m-t.

Azonban, ha a k, n, és t paramétereket gondosan választották, akkor annak a valószínűsége, hogy nem lesz hiba ebben a k elemű halmazban: $\textstyle {\binom {n-t}{k}}/{\binom {n}{k}}$, és így ez elhanyagolható.

Információ készlet dekódolás

Az ‘információ készlet dekódolás’ algoritmus a leghatékonyabb támadási módszer a McEliece-, és a Niederreiter-féle titkosítási rendszerek ellen.

Számos forma ismert.

Egy hatékony eljárás az, amely a minimális, és maximális súlyozású kódszóra épül. 2008-ban Bernstein, Lange és Peters leírtak egy praktikus támadási módot a McEliece-féle titkosító rendszer ellen. Mivel a támadás zavarbaejtően párhuzamos (nincs szükség a csomópontok közötti kommunikációra), végrehajtható egy számítógép klaszteren néhány nap alatt.

Irodalom

• R. J. McEliece: "A Public-Key Cryptosystem Based On Algebraic Coding Theory". (hely nélkül): DSN Progress Report. 1978. 42–44. o.  
• Handbook of Applied Cryptography. (hely nélkül): CRC Press
• Buttyán Levente - Vajda István: Kriptográfia és alkalmazásai. (hely nélkül): TYPOTEX ELEKTRONIKUS KIADÓ KFT. 2005. 42–44. o. ISBN 9789639548138  . 1996. ISBN 0849385237  
• http://www.sciencedaily.com/releases/2008/10/081028132303.htm
• http://www.technologyreview.com/blog/arxiv/25629/ Archiválva 2011. április 16-i dátummal a Wayback Machine-ben

Kapcsolódó szócikkek

• A kriptográfia története
• Szimmetrikus kulcsú rejtjelezés
• Nyilvános kulcsú rejtjelezés
• Véletlenszám generálás
• Szteganográfia

Fordítás

Ez a szócikk részben vagy egészben a McEliece cryptosystem című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.