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}=c{P}^{-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}=c{P}^{-1}=m\hat{G}{P}^{-1}+z{P}^{-1}=mSG+z{P}^{-1}$, és $P$ egy permutációs mátrix, így $z{P}^{-1}$ súlyozása többnyire $t$.

A Goppa kód, $G$ ki tudja javítani a $t$ hibákat, és az $mSG$ szó $c{P}^{-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}=mS{S}^{-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 {𝔽}_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: $(\genfrac{}{}{0ex}{}{n-t}{k})/(\genfrac{}{}{0ex}{}{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

• Sablon:CitLib
• Sablon:CitLib
• http://www.sciencedaily.com/releases/2008/10/081028132303.htm
• http://www.technologyreview.com/blog/arxiv/25629/ Sablon:Wayback

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