„McEliece-féle titkosító rendszer” változatai közötti eltérés

Tartalom törölve Tartalom hozzáadva

Sorban

A lap 2012. augusztus 29., 09:32-kori változata

Kriptográfiaban a McEliece-féle titkosító rendszer, egy aszimmetrikus titkosító algorítmus, melyet Robert McEliece (1942 -), amerikai matematikus fejlesztett ki 1978-ban. ^[1]

Ez volt az első olyan algoritmus, ahol a titkosítási folyamatban véletlenszá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 immúnis támadásokra, a Shor-algoritmust felhasználva, és – még általánosabban –mellékosztály állapotokat használ Fourier mintavétellel. ^[2]

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. ^[3] Az algoritmus az P-hard ^[4]). 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. ^[5] 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 pertubálásával, két véletlenszerűen kiválasztott invertált $S$ és $P$ mátrixxal.

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. ^[6]

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 nyílvános és a magán kulcsok is nagy mátrixok. A nyílvá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. ^[7]

Eljárás definíá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ós matrixot.

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. ^[1].

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.^[6]

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 kisé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. ]].^[5]

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. ^[8]. 2008-ban Bernstein, Lange és Peters ^[6] leírtak egy praktikus támadási módot a McEliece-féle titkosító rendszer ellen^[9]. 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

Kapcsolódó szócikkek

Források

↑ ^a ^b See (R. J. McEliece 1978)
↑ Sablon:Cite arxiv
↑ Daniel J. Bernstein (2009. szeptember 23.). „Grover vs. McEliece”.
↑ (1978) „On the Inherent Intractability of Certain Coding Problems”. IEEE Transactions on Information Theory IT-24, 203–207. o.
↑ ^a ^b N. J. Patterson (1975). „The algebraic decoding of Goppa codes”. IEEE Transactions on Information Theory IT-21, 384–386. o.
↑ ^a ^b ^c (2008. augusztus 8.) „Attacking and defending the McEliece cryptosystem”. Proc. 2nd International Workshop on Post-Quantum Cryptography 5299, 31–46. o. DOI:10.1007/978-3-540-88403-3_3.
↑ „1978 Cryptosystem Resists Quantum Attack”, 2010. augusztus 18.
↑ (1998) „Cryptanalysis of the Original McEliece Cryptosystem”. Advances in Cryptology — ASIACRYPT’98 1514, 187–199. o. DOI:10.1007/3-540-49649-1.
↑ Jacques Stern (1989). „A method for finding codewords of small weight”. Coding Theory and Applications 388, 106–113. o, Kiadó: Springer Verlag. DOI:10.1007/BFb0019850.

[McEliece-1] See (R. J. McEliece 1978)

[quantum-fourier-2] Sablon:Cite arxiv

[quantum-3] Daniel J. Bernstein (2009. szeptember 23.). „Grover vs. McEliece”.

[intractability-4] (1978) „On the Inherent Intractability of Certain Coding Problems”. IEEE Transactions on Information Theory IT-24, 203–207. o.

[Patterson-5] N. J. Patterson (1975). „The algebraic decoding of Goppa codes”. IEEE Transactions on Information Theory IT-21, 384–386. o.

[fix-6] (2008. augusztus 8.) „Attacking and defending the McEliece cryptosystem”. Proc. 2nd International Workshop on Post-Quantum Cryptography 5299, 31–46. o. DOI:10.1007/978-3-540-88403-3_3.

[7] „1978 Cryptosystem Resists Quantum Attack”, 2010. augusztus 18.

[min-weight-8] (1998) „Cryptanalysis of the Original McEliece Cryptosystem”. Advances in Cryptology — ASIACRYPT’98 1514, 187–199. o. DOI:10.1007/3-540-49649-1.

[9] Jacques Stern (1989). „A method for finding codewords of small weight”. Coding Theory and Applications 388, 106–113. o, Kiadó: Springer Verlag. DOI:10.1007/BFb0019850.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]