McEliece-féle titkosító rendszer

A Wikipédiából, a szabad enciklopédiából

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

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

Eljárás definíálása[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkeszté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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

Fordítás[szerkesztés | forrásszöveg szerkesztése]

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.

Források[szerkesztés | forrásszöveg szerkesztése]

  1. ^ a b See (R. J. McEliece 1978)
  2. H. Dinh, C. Moore, A. Russell (2010. augusztus 17.). „The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks”.  
  3. Daniel J. Bernstein (2009. szeptember 23.). „Grover vs. McEliece”.  
  4. (1978.) „On the Inherent Intractability of Certain Coding Problems”. IEEE Transactions on Information Theory IT-24, 203–207. o.  
  5. ^ a b N. J. Patterson (1975.). „The algebraic decoding of Goppa codes”. IEEE Transactions on Information Theory IT-21, 384–386. o.  
  6. ^ 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.  
  7. 1978 Cryptosystem Resists Quantum Attack”, 2010. augusztus 18. 
  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.