Niederreiterin salausjärjestelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 16. maaliskuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 3 muokkausta .

Niederreiterin salausjärjestelmä on julkisen avaimen salausjärjestelmä , joka perustuu algebrallisen koodauksen teoriaan ja jonka Harald Niederreiter kehitti vuonna 1986 [1] . Toisin kuin McEliece-salausjärjestelmä , Niederreiter-salausjärjestelmä käyttää koodintarkistusmatriisia . Niederreiter-salausjärjestelmä mahdollistaa digitaalisten allekirjoitusten luomisen ja on ehdokas postkvanttisalaukseen , koska se kestää Shor-algoritmia käyttäviä hyökkäyksiä .

Niederreiterin salausjärjestelmässä käytetty algoritmi perustuu kokonaisten lineaaristen koodien dekoodauksen vaikeuteen .

Huolimatta siitä, että tämä kryptojärjestelmä on hakkeroitu, jotkin sen modifikaatiot ovat edelleen kryptonkestäviä [2]

Toimintaalgoritmi

Avaimen luominen

Alice valitsee virheenkorjauskoodin Galois -kentän päälle . Tällä koodilla on oltava tehokas dekoodausalgoritmi [3] . $(n,k)$ $C$ $GF(q)$ $t$
Alice luo koodintarkistusmatriisin . $(nk)\kertaa n$ $H$ $C$
Alice valitsee satunnaisen ei- degeneroituneen matriisin kentän ja jonkin permutaatiomatriisin sijaan [3] . $(nk)\kertaa (nk)$ $S$ $GF(q)$ $n\ kertaa n$ $P$
Alice laskee matriisin $(nk)\kertaa n$ $H_{pub}=SHP$
Liisa julkinen avain on . Yksityinen avain on asetettu . $(H_{pub},t)$ ${\näyttötyyli (S^{-1},H,P^{-1})}$

Viestin salaus

Tässä tapauksessa viestit ovat kaikki vektoreita, joiden koordinaatit kentästä , jonka paino on enintään . Viestit ovat siis kaikki mahdollisia virheitä, jotka valittu koodi pystyy korjaamaan [2] . Oletetaan, että Bob haluaa lähettää viestin Alicelle, jonka julkinen avain on . $n-$ $GF(q)$ $t$
$(H_{pub},t)$

Bob esittää viestinsä binaarisena sekvenssinä , jonka pituus ei ylitä . $m$ $n$ $t$
Bob laskee salatekstin kaavalla: . Siten Niederreiterin salausjärjestelmän salateksti on meluisan salausvirhevektorin syndrooma [2] . $c=mH_{pub}^{T}$

Viestin dekoodaus

Saatuaan viestin Alice tekee seuraavaa: $c$

Alice laskee . Huomaa, että koska permutaatiomatriisi on , paino on sama kuin paino eikä ylitä , ja siksi dekoodausalgoritmi voi löytää oireyhtymää vastaavan virhevektorin [3] . $s=c{(S^{T})}^{-1}=mP^{T}H^{T}S^{T}(S^{T})^{-1}=(mP^{ T})H^{T}={\hattu {m}}H^{T}$ $P$ ${\hattu {m}}=(mP^{T})$ $m$ $t$ $C$ $s$
Alice käyttää nopeaa dekoodausalgoritmia koodin löytämiseen [3] . $C$ ${\hattu {m}}$
Alice laskee viestin . ${\hat {m}}P^{-1}=mPP^{-1}=m$

Alkuperäinen kryptojärjestelmä ja sen muutokset

Alkuperäisessä kryptojärjestelmässä Niederreiter ehdotti Reed-Solomon-koodien käyttöä eikä käyttänyt permutaatiomatriisia . Tällainen järjestelmä osoittautui kuitenkin epävakaaksi, ja Sidelnikov ja Shestakov hakkeroivat sen vuonna 1992 [4] . Kirjoittajat ovat osoittaneet, että julkisesta avaimesta on mahdollista arvata yksityisen avaimen rakenne ja valita sellaiset matriisit ja , että . Sen jälkeen järjestelmän kryptografisen vahvuuden lisäämiseksi ehdotettiin permutaatiomatriisin käyttöä . Lisäksi järjestelmään ilmestyi erilaisia muutoksia, esimerkiksi: $P$ ${\hattu {H}}$ ${\hattu {S}}$ $H_{pub}={\hattu {S}}{\hattu {H}}$ $P$

käyttämällä erilaisia mittareita kuin klassista Hammingia , esimerkiksi sijoitus [5] : esimerkki tästä on modifioitu GPT-järjestelmä [3]
käyttämällä koodeja, joilla on tietyt ominaisuudet. Joten Goppa-koodeihin perustuvat modifikaatiot ovat edelleen kryptonkestäviä [2] .

Järjestelmän edut ja haitat

Edut

Toisin kuin McEliece, Niederreiterin salausjärjestelmä ei käytä satunnaisia parametreja. Näin ollen saman tekstin salauksen tulos on sama. Tämä tosiasia mahdollistaa Niederreiter-järjestelmän, ei McEliecen, käytön digitaalisen allekirjoituksen luomiseen .
Julkisen avaimen koko on Niederreiterin salausjärjestelmässä useita kertoja pienempi kuin McEliecessa [6] . ${\frac {n}{nk}}$
RSA :han verrattuna salausnopeus on noin 50 kertaa nopeampi ja salauksen purkunopeus 100 kertaa nopeampi [6] .

Haitat

Satunnaisen viestin salaamiseksi algoritmi, jolla muunnetaan -aarivektoriksi, jonka paino on enintään . $q$ $n$ $t$
Avaimen koko on suurempi kuin klassisissa julkisen avaimen salausjärjestelmissä ( RSA , ElGamal Scheme , GOST R 34.10-2012 ).
Salatekstin koko on paljon suurempi kuin salatun viestin koko (jos koon sanoma käännetään pituusvektoriksi ja salataan, saadaan koon salateksti , joka on vähintään 2 kertaa suurempi kuin ). $t$ $n$ $nk$ $t$

Alla olevassa taulukossa on useita McEliece-, Niederreiter- ja RSA-salausjärjestelmien parametreja, jotka osoittavat selkeästi niiden edut ja haitat [6] .

	McEliece n = 1024, k = 524, t = 101 binäärikoodi	Niederreiterin salausjärjestelmä n = 1024, k = 524, t = 101 binäärikoodi	RSA 1024-bittiset moduulit e=17
Julkisen avaimen koko tavuissa	67072	32750	256
Bittien määrä hyödyllistä tietoa	512	276	1024
Binäärioperaatioiden määrä salausta varten	514	viisikymmentä	2402
Binäärioperaatioiden määrä salauksen purkamista varten	5140	7863	738112

Niederreiter- ja McEliece-järjestelmän salaussuojauksen vastaavuus

Kuten alkuperäisessä Sidelnikov-järjestelmää käsittelevässä artikkelissa [7] käy ilmi , Niederreiter-järjestelmää vastaan hyökkääminen voidaan polynomiaalisesti pelkistää McEliece-järjestelmän hyökkäämiseksi ja päinvastoin.

Olkoon syndrooma tiedossa . Sitten voimme laskea vektorin jollain sellaisella, että . Vektoria käsitellään salatekstinä McEliece-järjestelmässä. Jos löydetään McEliece-järjestelmälle monimutkainen kryptografinen hyökkäys , eli algoritmi vektorin laskemiseksi , joka on salainen tieto tässä järjestelmässä, voidaan esittää vektori , joka on salaisuus Niederreiter-järjestelmälle. kuin . Siten määritelmän monimutkaisuus on sama kuin määritelmän monimutkaisuus . $c=eD$ $b=aE+e$ $a$ $c = bD$ $b$ $T$ $a$ $e$ $e=aE+b$ $e$ $a$

Jos tunnetaan Niederreiter-järjestelmän monimutkainen kryptohyökkäys , on mahdollista laskea vektorit ja vektorit salatekstinä käyttämällä vektoria . $T$ $(aE+e)D^{T}=eD^{T}$ $e$ $a$

Digitaalisen allekirjoituksen rakentaminen

Vuonna 2001 Nicolas Courtois, Matthew Finiaz ja Nicolas Sandrier osoittivat [8] , että Niederreiterin salausjärjestelmää voidaan käyttää sähköisen allekirjoituksen luomiseen .

Viestin allekirjoitus

Olkoon Niederreiterin salausjärjestelmän julkinen avain lineaarista koodia käyttäen. Allekirjoittaaksesi asiakirjan sinun on: $H_{pub}$ $(n, k, d)$ $D$

Valitse hash-funktio , joka antaa merkkejä ulostulossa. Siten tietyn hash-funktion tulos voidaan esittää oireyhtymänä ja yrittää dekoodata; $h()$ $nk$
Laske hash ; $s=h(D)$
Jokaiselle laskelma ; $i=0,1,2,...$ $s_{i}=h(s|i)$
Etsi pienin luku , jolla oireyhtymä on mahdollista purkaa. Olkoon oireyhtymän dekoodauksen tulos ; $olen mukana}$ $s_{i_{min}}$ $z$ $s_{i_{min}}$
Asiakirjan allekirjoitus on pari . $D$ $(z,i_{min})$

Allekirjoituksen vahvistus

Laske ; $s_{1}=zH_{pub}^{T}$
Laske ; $s_{2}=h(t(D)|i_{min})$
Vertaa ja : jos ne täsmäävät, allekirjoitus on oikea. $s_{1}$ $s_{2}$

Esimerkki järjestelmän toiminnasta

Olkoon Reed-Solomon-koodi Galois-kentän yli konstruoitu modulo redusoitumaton polynomi valitaan koodaamaan generoivalla polynomilla $(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.$

Sitten koodin generoiva matriisi on: $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))$

Koodin tarkistusmatriisi: $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{pmatrix))$

Huomaa, että tämän koodin etäisyys eli korjattavien virheiden määrä . $d = n-k + 1 = 5$ $t = (d-1)/2 = 2$

Avaimen luominen

Olkoon matriisi valittu . Sitten sen käänteismatriisi $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}}$

Valitaan permutaatiomatriisi ${\displaystyle P={\begin{pmatrix}0&1&0&0&0&0&0\\0&0&0&1&0&0&0\\0&0&0&1&0&0\\1&0&0&0&0&0&0\\0&0&0&0&0&0))$

Tässä tapauksessa järjestelmän julkinen avain on matriisi: $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{pmatrix)$

Salaus

Esitetään valittu viesti painovektorina 2. $m={\begin{pmatrix}0&2&0&0&0&5&0\end{pmatrix}}$

Salattu viesti: $M=mH_{pub}^{T}={\begin{pmatrix}7&2&7&7\end{pmatrix}}$

Salauksen purku

Hyväksytty vektori $M={\begin{pmatrix}7&2&7&7\end{pmatrix}}$

Sitä varten laskemme dekoodattavan oireyhtymän $s=M(S^{-1})^{T}={\begin{pmatrix}0&1&3&6\end{pmatrix}}$

Dekoodaamme Reed-Solomon-dekoodausalgoritmin avulla . $s$

Hanki vektori ${\hat {m}}={\begin{pmatrix}2&0&0&0&0&0&5\end{pmatrix}}$

Sitten lasketaan alkuperäinen vektori $m=~{\hat {m}}P^{-1}={\begin{pmatrix}0&2&0&0&0&5&0\end{pmatrix}}$

Katso myös

Muistiinpanot

↑ Niederreiter H. Knapsack-tyyppiset salausjärjestelmät ja algebrallinen koodausteoria (englanti) // Control and Information Theory -ongelmat - 1986. - Vol. 15, Iss. 2. - s. 159-166.
↑ 1 2 3 4 Samokhina M. A. Niederreiterin salausjärjestelmän modifikaatiot, niiden turvallisuus ja käytännön sovellukset // Moskovan fysiikan ja tekniikan instituutin julkaisut - 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. Muokattu Niederreiter-tyyppinen GPT-salausjärjestelmä, joka perustuu pelkistettäviin arvokoodeihin // Des . Koodit Cryptogr. — Springer US , Springer Science+Business Media , 2014. — Voi. 70, Iss. 1. - s. 231-239. — ISSN 0925-1022 ; 1573-7586 - doi:10.1007/S10623-012-9757-4
↑ Sidelnikov V. M. , Shestakov S. O. Yleistettyihin Reed-Solomon -koodeihin perustuvasta salausjärjestelmästä // Discrete Math. matematiikka. - 1992. - Vol. 4, numero. 3. - S. 57-63. — ISSN 2305-3143 ; 0234-0860
↑ Gabidulin E. M. Teoria koodeista, joilla on maksimiarvoetäisyys // Probl. tiedon siirto - 1985. - T. 21, no. 1. - S. 3-16.
↑ 1 2 3 Canteaut A. , Sendrier N. Alkuperäisen McEliece-salausjärjestelmän kryptaanalyysi // Advances in Cryptology - ASIACRYPT 1998 : Kansainvälinen konferenssi kryptologian ja tietoturvan teoriasta ja sovelluksista, Peking, Kiina, 18.-22.10., 19. Proceedings - Berlin : Springer Berlin Heidelberg , 1998. - P. 187-199. - ( Lecture Notes in Computer Science ; Vol. 1514) - ISBN 978-3-540-65109-3 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-49649-1_16
↑ Sidelnikov V. M. Avoin salaus perustuu Reed-Muller-binäärikoodeihin // Diskr. matematiikka. - 1994. - V. 4, numero. 3. - S. 191-207. — ISSN 2305-3143 ; 0234-0860
↑ Courtois N. , Finiasz M. , Sendrier N. Kuinka saavuttaa McEliece-pohjainen digitaalinen allekirjoitusjärjestelmä // Advances in Cryptology - ASIACRYPT 2001 : 7. kansainvälinen konferenssi kryptologian ja tietoturvan teoriasta ja soveltamisesta, Gold Coast, Australia, 9.- 13. joulukuuta 2001, Proceedings / C. Boyd - Lontoo : Springer Science + Business Media , 2001. - P. 157-174. - ( Lecture Notes in Computer Science ; Vol. 2248) - ISBN 978-3-540-42987-6 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/3-540-45682-1

Kirjallisuus

Wieschebrink C. GRS-alikoodeihin perustuvan Niederreiterin julkisen avainjärjestelmän kryptaanalyysi // Post -Quantum Cryptography : Third International Workshop, PQCrypto 2010, Darmstadt, Saksa, 25.-28.5.2010. Proceedings / N. Sendrier Berlin - Heidelberg Springer Berlin , 2010. - s. 61-72. - ( Lecture Notes in Computer Science ; Vol. 6061) - 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 Kryptologia // Kokoelma koodausteorian, kryptologian ja tiedonpakkauksen ongelmia - Novosibirsk : NGU , 2013. - P. 41-49. -100 s. — ISBN 978-5-4437-0184-4
Schneier B. Sovellettu kryptografia. Protokollat, algoritmit, lähdekoodi C-kielellä = Applied Cryptography. Protokollat, algoritmit ja lähdekoodi julkaisussa C. - M. : Triumph, 2002. - 816 s. - 3000 kappaletta. - ISBN 5-89392-055-4 .