Niederreiter kriptorendszer

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. március 16-án felülvizsgált verziótól ; az ellenőrzések 3 szerkesztést igényelnek .

A Niederreiter kriptorendszer egy nyilvános kulcsú titkosítási rendszer, amely az algebrai kódolás elméletén alapul , és 1986-ban fejlesztette ki Harald Niederreiter [1] . A McEliece kriptorendszerrel ellentétben a Niederreiter kriptorendszer kódellenőrző mátrixot használ . A Niederreiter kriptorendszer lehetővé teszi a digitális aláírások létrehozását, és alkalmas a posztkvantum kriptográfiára , mivel ellenáll a Shor algoritmussal szembeni támadásoknak .

A Niederreiter kriptorendszerben használt algoritmus a teljes lineáris kódok dekódolásának nehézségén alapul .

Annak ellenére, hogy ezt a kriptorendszert feltörték, néhány módosítása továbbra is kripto -ellenálló [2]

Műveleti algoritmus

Kulcsgenerálás

Alice választ egy hibajavító kódot a Galois mező helyett . Ennek a kódnak hatékony dekódoló algoritmussal kell rendelkeznie [3] . $(n,k)$ $C$ $GF(q)$ $t$
Alice létrehoz egy kódellenőrző mátrixot . $(nk)\szer n$ $H$ $C$
Alice egy véletlenszerű , nem degenerált mátrixot választ a mező és néhány permutációs mátrix helyett [3] . $(nk)\times (nk)$ $S$ $GF(q)$ $n\szer n$ $P$
Alice kiszámítja a mátrixot $(nk)\szer n$ $H_{pub}=SHP$
Alice nyilvános kulcsa . A privát kulcs a készlet . $(H_{pub},t)$ ${\megjelenítési stílus (S^{-1},H,P^{-1})}$

Üzenettitkosítás

Ebben az esetben az üzenetek a mező koordinátáival rendelkező vektorok, amelyek súlya nem haladja meg a . Így az üzenetek mind olyan lehetséges hibák, amelyeket a kiválasztott kód képes kijavítani [2] . Tegyük fel, hogy Bob üzenetet akar küldeni Alice-nek, akinek a nyilvános kulcsa . $n-$ $GF(q)$ $t$
$(H_{pub},t)$

Bob üzenetét bináris hosszúságú sorozatként mutatja be , amelynek súlya nem haladja meg a . $m$ $n$ $t$
Bob a rejtjelezett szöveget a következő képlet segítségével számítja ki: . Így a Niederreiter kriptorendszerben a rejtjelezett szöveg a zajos rejtjelezett hibavektor szindróma [2] . $c=mH_{pub}^{T}$

Üzenet dekódolás

Miután megkapta az üzenetet , Alice a következőket teszi: $c$

Alice kiszámolja . Figyeljük meg, hogy mivel a permutációs mátrix , a súly egybeesik a súllyal és nem haladja meg a -t , ezért a dekódoló algoritmus meg tudja találni a szindrómának megfelelő hibavektort [3] . $s=c{(S^{T})}^{-1}=mP^{T}H^{T}S^{T}(S^{T})^{-1}=(mP^{ T})H^{T}={\kalap {m}}H^{T}$ $P$ ${\hat {m}}=(mP^{T})$ $m$ $t$ $C$ $s$
Alice egy gyors dekódoló algoritmust használ a kód megtalálásához [3] . $C$ ${\kalap {m}}$
Alice kiszámolja az üzenetet . ${\hat {m}}P^{-1}=mPP^{-1}=m$

Az eredeti kriptorendszer és annak módosításai

Az eredeti kriptorendszerben Niederreiter Reed-Solomon kódok használatát javasolta, és nem használt permutációs mátrixot . Egy ilyen rendszer azonban instabilnak bizonyult, és Szidelnyikov és Sesztakov feltörte 1992-ben [4] . A szerzők megmutatták, hogy a nyilvános kulcsból kitalálható a privát kulcs szerkezete, és kiválasztható olyan mátrix és , hogy . Ezt követően a rendszer kriptográfiai erősségének növelése érdekében permutációs mátrix használatát javasolták . Ezenkívül a rendszer különféle módosításai jelentek meg, például: $P$ ${\kalap {H}}$ ${\kalap {S}}$ $H_{pub}={\kalap {S}}{\kalap {H}}$ $P$

a klasszikus Hammingtől eltérő metrikák használatával , például rang [5] : erre példa a módosított GPT rendszer [3]
meghatározott tulajdonságokkal rendelkező kódok használatával. Tehát a Goppa kódokon alapuló módosítások továbbra is titkosításállóak [2] .

A rendszer előnyei és hátrányai

Előnyök

A McEliece-től eltérően a Niederreiter kriptorendszer nem használ véletlenszerű paramétereket. Így ugyanazon szöveg titkosításának eredménye ugyanaz lesz. Ez a tény lehetővé teszi, hogy a Niederreiter rendszert, és nem a McEliece-t használjuk digitális aláírás létrehozására .
A Niederreiter kriptorendszerben a nyilvános kulcs mérete többszöröse, mint a McEliece-ben [6] . ${\frac {n}{nk}}$
Az RSA - hoz képest a titkosítási sebesség körülbelül 50-szer, a visszafejtési sebesség pedig 100-szor gyorsabb [6] .

Hátrányok

Egy tetszőleges üzenet titkosításához egy algoritmus egy legfeljebb súllyal rendelkező -áris vektorra történő fordításhoz . $q$ $n$ $t$
A kulcs mérete nagyobb, mint a klasszikus nyilvános kulcsú kriptorendszerekben ( RSA , ElGamal Scheme , GOST R 34.10-2012 ).
A rejtjelezett szöveg mérete jóval nagyobb, mint a titkosított üzenet mérete (ha a méretüzenetet hosszúságú vektorra fordítjuk és titkosítjuk, akkor méretű rejtjelezett szöveget kapunk , amely legalább 2-szer nagyobb, mint ). $t$ $n$ $nk$ $t$

Az alábbi táblázat különböző paramétereket mutat be a McEliece, Niederreiter és RSA kriptorendszerekhez, világosan bemutatva azok előnyeit és hátrányait [6] .

	McEliece n=1024, k=524, t=101 bináris kód	Niederreiter kriptorendszer n=1024, k=524, t=101 bináris kód	RSA 1024 bites modulok e=17
Nyilvános kulcs mérete bájtokban	67072	32750	256
Bitek száma hasznos információ	512	276	1024
Bináris műveletek száma titkosításhoz	514	ötven	2402
Bináris műveletek száma a visszafejtéshez	5140	7863	738112

A Niederreiter rendszer és a McEliece rendszer kriptográfiai biztonságának egyenértékűsége

Amint azt a Szidelnyikov-rendszerről szóló eredeti cikk [7] mutatja , a Niederreiter-rendszer támadása polinomiálisan redukálható a McEliece- rendszer megtámadására és fordítva.

Legyen ismert a szindróma . Ekkor kiszámolhatunk egy vektort olyasmivel , hogy . A vektort titkosított szövegként kezeli a McEliece rendszer. Ha a McEliece rendszer számára bonyolult kriptográfiai támadást találunk, azaz ismerjük a vektor kiszámítására szolgáló algoritmust , amely titkos információ ebben a rendszerben, akkor a vektor , amely a Niederreiter rendszer titkossága , ábrázolható. mint . Így a definíció összetettsége megegyezik a definíció összetettségével . $c=eD$ $b=aE+e$ $a$ $c=bD$ $b$ $T$ $a$ $e$ $e=aE+b$ $e$ $a$

Ha ismert a Niederreiter rendszer bonyolultságú kriptotámadása , akkor a vektort titkosított szövegként használva ki lehet számítani a és vektorokat . $T$ $(aE+e)D^{T}=eD^{T}$ $e$ $a$

Digitális aláírás felépítése

2001-ben Nicolas Courtois, Matthew Finiaz és Nicolas Sandrier megmutatta [8] , hogy a Niederreiter kriptorendszer használható elektronikus aláírás létrehozására .

Üzenet aláírása

Legyen a Niederreiter kriptorendszer nyilvános kulcsa egy -lineáris kód használatával. Egy dokumentum aláírásához a következőket kell tennie: $H_{kocsma}$ $(n, k, d)$ $D$

Válasszon egy hash függvényt , amely karaktereket ad a kimeneten. Így egy adott hash függvény eredménye szindrómaként ábrázolható és megkísérelhető dekódolni; $h()$ $nk$
Hash kiszámítása ; $s=h(D)$
Minden egyes számításhoz ; $i=0,1,2,...$ $s_{i}=h(s|i)$
Keresse meg a legkisebb számot , amely lehetővé teszi a szindróma dekódolását. Legyen a szindróma dekódolásának eredménye ; $én benne vagyok}$ $s_{i_{min}}$ $z$ $s_{i_{min}}$
A dokumentum aláírása egy pár . $D$ $(z,i_{min})$

Aláírás ellenőrzése

Számíts ; $s_{1}=zH_{pub}^{T}$
Számíts ; $s_{2}=ó(h(D)|i_{min})$
Hasonlítsa össze és : ha egyezik, az aláírás helyes. $s_{1}$ $s_{2}$

Példa a rendszer működésére

Legyen a Reed-Solomon kód a modulo szerkesztett Galois-mező felett az irreducibilis polinom a generáló polinommal való kódoláshoz $(7.3)$ $GF(2^{3})$ $x^{3}+x+1$ $g(x)=(x-1)(x-{\alpha })(x-{\alpha }^{2})(x-{\alpha }^{3})=(x-1)(x -2)(x-4)(x-3)=x^{4}+4x^{3}+7x^{2}+7x+5.$

Ezután a kód generáló mátrixa a következő: $G={\begin{pmatrix}1&4&7&7&5&0&0\\0&1&4&7&7&5&0\\0&0&1&4&7&7&5\end{pmatrix))$

Kódellenőrző mátrix: $H={\begin{pmatrix}1&1&1&1&1&1&1\\1&2&4&3&6&7&5\\1&4&6&5&2&3&7\\1&3&5&4&7&2&6\end{pmátrix))$

Vegye figyelembe, hogy a kód távolsága , azaz a javítható hibák száma . $d=n-k+1=5$ $t=(d-1)/2=2$

Kulcsgenerálás

Legyen a mátrix kiválasztva . Aztán az inverz mátrixa $S={\begin{pmatrix}4&1&3&5\\7&1&5&2\\2&6&5&4\\1&7&2&1\end{pmatrix}}$ $S^{-1}={\begin{pmatrix}1&5&2&7\\7&5&0&7\\4&4&1&5\\1&0&0&4\end{pmatrix}}$

Válasszunk egy permutációs mátrixot ${\displaystyle P={\begin{pmatrix}0&1&0&0&0&0&0\\0&0&0&1&0&0&0\\0&0&0&0&1&0&0\\1&0&0&0&0&0&0\\0&0&0&0&0&0)$

Ebben az esetben a rendszer nyilvános kulcsa a mátrix lesz: $H_{pub}=SHP={\begin{pmatrix}1&3&7&5&6&0&2\\0&1&0&1&1&3&5\\2&5&1&0&6&2&0\\6&5&6&4&2&4&6\end{pmátrix)$

Titkosítás

Legyen a kiválasztott üzenet 2 súlyvektora . $m={\begin{pmatrix}0&2&0&0&0&5&0\end{pmatrix}}$

Titkosított üzenet: $M=mH_{pub}^{T}={\begin{pmatrix}7&2&7&7\end{pmatrix}}$

Megfejtés

Elfogadott vektor $M={\begin{pmatrix}7&2&7&7\end{pmatrix}}$

Ehhez kiszámítjuk a dekódolható szindrómát $s=M(S^{-1})^{T}={\begin{pmatrix}0&1&3&6\end{pmatrix}}$

A Reed-Solomon dekódoló algoritmus segítségével dekódoljuk . $s$

Szerezz vektort ${\hat {m}}={\begin{pmatrix}2&0&0&0&0&0&5\end{pmatrix}}$

Ezután kiszámítjuk az eredeti vektort $m=~{\hat {m}}P^{-1}={\begin{pmatrix}0&2&0&0&0&5&0\end{pmatrix}}$

Lásd még

Jegyzetek

↑ Niederreiter H. Hátizsák-típusú kriptorendszerek és algebrai kódoláselmélet (angol) // Control and Information Theory problémák - 1986. - Vol. 15, Iss. 2. - P. 159-166.
↑ 1 2 3 4 Samokhina M. A. A Niederreiter kriptorendszer módosításai, azok biztonsága és gyakorlati alkalmazása // Proceedings of the Moscow Institute of Physics and Technology - M. : 2009. - V. 1, no. 2. - S. 121-127. — ISSN 2072-6759
↑ 1 2 3 4 5 Khan E. , Gabidulin E. , Honary B. , Ahmed H. A redukálható rangkódokon alapuló Niederreiter típusú GPT kriptorendszer módosított // Des . Kódok Cryptogr. — Springer US , Springer Science+Business Media , 2014. — Vol. 70, Iss. 1. - P. 231-239. — ISSN 0925-1022 ; 1573-7586 - doi:10.1007/S10623-012-9757-4
↑ Sidelnikov V. M. , Shestakov S. O. Egy általánosított Reed–Solomon kódokon alapuló titkosítási rendszerről // Discrete Math. matematika. - 1992. - 4. évf., szám. 3. - S. 57-63. — ISSN 2305-3143 ; 0234-0860
↑ Gabidulin E. M. Maximális rangtávolságú kódok elmélete // Probl. információ továbbítása - 1985. - T. 21. sz. 1. - S. 3-16.
↑ 1 2 3 Canteaut A. , Sendrier N. Az eredeti McEliece kriptorendszer kriptoanalízise // Advances in Cryptology - ASIACRYPT 1998 : International Conference on the Theory and Applications of Cryptology and Information Security, Peking, Kína, október 18-22, 1998. Proceedings - Berlin : Springer Berlin Heidelberg , 1998. - P. 187-199. - ( Számítástechnikai előadások jegyzetei ; 1514. kötet) - ISBN 978-3-540-65109-3 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-49649-1_16
↑ Sidelnikov V. M. Nyílt titkosítás bináris Reed-Muller kódokon // Diskr. matematika. - 1994. - V. 4. szám. 3. - S. 191-207. — ISSN 2305-3143 ; 0234-0860
↑ Courtois N. , Finiasz M. , Sendrier N. Hogyan érjünk el McEliece-alapú digitális aláírási rendszert // Advances in Cryptology - ASIACRYPT 2001 : 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Ausztrália, 2001. december 9-13., Proceedings / C. Boyd - London : Springer Science + Business Media , 2001. - P. 157-174. - ( Számítástechnikai előadások jegyzetei ; 2248. kötet) - ISBN 978-3-540-42987-6 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-45682-1

Irodalom

Wieschebrink C. A Niederreiter nyilvános kulcsú rendszer kriptoanalízise GRS-alkódok alapján // Post -Quantum Cryptography : Third International Workshop, PQCrypto 2010, Darmstadt, Németország, 2010. május 25-28. Proceedings / N. Sendrier Berlin – Heidelberg Springer , 2010. - P. 61-72. - ( Számítástechnikai előadások jegyzetei ; 6061. kötet) - ISBN 978-3-642-12928-5 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-642-12929-2
Solovieva F. I. , Los A. V. , Mogilnykh I. Yu. II Kriptológia // Problémák gyűjteménye a kódoláselméletről, kriptológiáról és adattömörítésről - Novoszibirszk : NGU , 2013. - P. 41-49. - 100 s. — ISBN 978-5-4437-0184-4
Schneier B. Alkalmazott kriptográfia. Protokollok, algoritmusok, forráskód C nyelven = Applied Cryptography. Protokollok, algoritmusok és forráskód in C. - M .: Triumph, 2002. - 816 p. - 3000 példányban. - ISBN 5-89392-055-4 .