Niederreiters kryptosystem

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 16 mars 2019; kontroller kräver 3 redigeringar .

Niederreiters kryptosystem är ett kryptosystem med offentlig nyckel baserat på teorin om algebraisk kodning , utvecklat 1986 av Harald Niederreiter [1] . Till skillnad från McEliece-kryptosystemet använder Niederreiters kryptosystem en kodkontrollmatris . Niederreiters kryptosystem tillåter skapandet av digitala signaturer och är en kandidat för post-kvantkryptering , eftersom det är resistent mot attacker med Shor-algoritmen .

Algoritmen som används i Niederreiters kryptosystem är baserad på svårigheten att avkoda fullständiga linjära koder .

Trots att detta kryptosystem har blivit hackat förblir vissa av dess modifieringar kryptoresistenta [2]

Operationsalgoritm

Nyckelgenerering

Alice väljer en felkorrigerande kod framför Galois-fältet . Denna kod måste ha en effektiv avkodningsalgoritm [3] . $(n,k)$ $C$ $GF(q)$ $t$
Alice genererar en kodkontrollmatris . $(nk)\ gånger n$ $H$ $C$
Alice väljer en slumpmässig icke degenererad matris över fältet och någon permutationsmatris [3] . $(nk)\ gånger (nk)$ $S$ $GF(q)$ $n\ gånger n$ $P$
Alice beräknar matrisen $(nk)\ gånger n$ $H_{pub}=SHP$
Alices publika nyckel är . Den privata nyckeln är uppsättningen . $(H_{pub},t)$ $(S^{-1},H,P^{-1})$

Meddelandekryptering

I detta fall är meddelanden alla vektorer med koordinater från fältet med en vikt som inte överstiger . Således är meddelanden alla möjliga fel som den valda koden kan fixa [2] . Anta att Bob vill skicka ett meddelande till Alice vars publika nyckel är . $n-$ $GF(q)$ $t$
$(H_{pub},t)$

Bob presenterar sitt meddelande som en binär längdsekvens , med en vikt som inte överstiger . $m$ $n$ $t$
Bob beräknar chiffertexten med formeln: . Således är chiffertexten i Niederreiters kryptosystem det bullriga chiffrerade felvektorsyndromet [ 2] . $c=mH_{pub}^{T}$

Meddelandeavkodning

Efter att ha tagit emot meddelandet gör Alice följande: $c$

Alice räknar ut . Observera att eftersom permutationsmatrisen är , sammanfaller vikten med vikten och överstiger inte , och därför kan avkodningsalgoritmen för hitta felvektorn som motsvarar syndromet [3] . $s=c{(S^{T})}^{-1}=mP^{T}H^{T}S^{T}(S^{T})^{-1}=(mP^{ T})H^{T}={\hat {m}}H^{T}$ $P$ ${\hat {m}}=(mP^{T})$ $m$ $t$ $C$ $s$
Alice använder en snabb avkodningsalgoritm för att koden ska hitta [3] . $C$ ${\hat {m}}$
Alice beräknar meddelandet . ${\hat {m}}P^{-1}=mPP^{-1}=m$

Det ursprungliga kryptosystemet och dess modifieringar

I det ursprungliga kryptosystemet föreslog Niederreiter att man skulle använda Reed-Solomon-koder och inte använda en permutationsmatris . Ett sådant system visade sig dock vara instabilt och hackades av Sidelnikov och Shestakov 1992 [4] . Författarna har visat att det är möjligt att gissa strukturen för den privata nyckeln från den publika nyckeln och välja sådana matriser och , att . Efter det, för att öka systemets kryptografiska styrka , föreslogs det att använda en permutationsmatris . Dessutom dök olika modifieringar av systemet upp, till exempel: $P$ ${\hat {H}}$ ${\hat {S}}$ $H_{pub}={\hat {S}}{\hat {H}}$ $P$

använder olika mätvärden andra än klassisk Hamming , till exempel, rang [5] : ett exempel på detta är det modifierade GPT-systemet [3]
använda koder med specifika egenskaper. Så modifieringar baserade på Goppa-koder är fortfarande kryptoresistenta [2] .

Fördelar och nackdelar med systemet

Fördelar

Till skillnad från McEliece använder Niederreiters kryptosystem inte slumpmässiga parametrar. Således kommer resultatet av kryptering av samma text att bli detsamma. Detta faktum gör det möjligt att använda Niederreiter-systemet, och inte McEliece, för att skapa en digital signatur .
Storleken på den publika nyckeln i Niederreiters kryptosystem är flera gånger mindre än i McEliece [6] . ${\frac {n}{nk}}$
Jämfört med RSA är krypteringshastigheten cirka 50 gånger snabbare, och dekrypteringshastigheten är 100 gånger snabbare [6] .

Nackdelar

För att kryptera ett godtyckligt meddelande, en algoritm för att översätta till en -är vektor med en vikt på högst . $q$ $n$ $t$
Nyckelstorleken är större än i klassiska offentliga nyckelkryptosystem ( RSA , ElGamal Scheme , GOST R 34.10-2012 ).
Storleken på chiffertexten är mycket större än storleken på det krypterade meddelandet (om meddelandet av storlek översätts till en vektor med längd och krypteras, erhålls en chiffertext av storlek , som är minst 2 gånger större än ). $t$ $n$ $nk$ $t$

Tabellen nedan visar olika parametrar för McEliece, Niederreiter och RSA kryptosystem, och visar tydligt deras fördelar och nackdelar [6] .

	McEliece n=1024, k=524, t=101 binär kod	Niederreiters kryptosystem n=1024, k=524, t=101 binär kod	RSA 1024-bitars moduler e=17
Storlek på offentlig nyckel i byte	67072	32750	256
Antal bitar användbar information	512	276	1024
Antal binära operationer för kryptering	514	femtio	2402
Antal binära operationer för dekryptering	5140	7863	738112

Likvärdighet mellan kryptografisk säkerhet för Niederreiter-systemet och McEliece-systemet

Som visas i den ursprungliga uppsatsen om Sidelnikov-systemet [7] , kan attackera Niederreiter-systemet polynomiskt reduceras till att attackera McEliece-systemet och vice versa.

Låt syndromet vara känt . Sedan kan vi beräkna en vektor med några sådana att . Vektorn kommer att behandlas som en chiffertext i McEliece-systemet. Om en kryptografisk attack med komplexitet för McEliece-systemet hittas, det vill säga en algoritm för att beräkna vektorn , som är hemlig information i detta system, är känd, kan vektorn , som är en hemlighet för Niederreiter-systemet, representeras som . Således är komplexiteten i definitionen densamma som komplexiteten i definitionen av . $c=eD$ $b=aE+e$ $a$ $c=bD$ $b$ $T$ $a$ $e$ $e=aE+b$ $e$ $a$

Om en kryptoattack med komplexitet för Niederreiter-systemet är känd, är det möjligt att, med hjälp av vektorn som chiffertext , beräkna vektorerna och . $T$ $(aE+e)D^{T}=eD^{T}$ $e$ $a$

Bygga en digital signatur

2001 visade Nicolas Courtois, Matthew Finiaz och Nicolas Sandrier [8] att Niederreiters kryptosystem kan användas för att skapa en elektronisk signatur .

Meddelandesignatur

Låt vara den publika nyckeln till Niederreiters kryptosystem med en -linjär kod. För att underteckna ett dokument måste du: $H_{pub}$ $(n,k,d)$ $D$

Välj en hashfunktion som ger tecken vid utgången. Således kan resultatet av en given hashfunktion representeras som ett syndrom och försöka avkodas; $h()$ $nk$
Beräkna hash ; $s=h(D)$
För varje beräkna ; $i=0,1,2,...$ $s_{i}=h(s|i)$
Hitta det minsta antalet så att syndromet kommer att vara möjligt att avkoda. Låt vara resultatet av att avkoda syndromet ; $jag är i}$ $s_{i_{min}}$ $z$ $s_{i_{min}}$
Signaturen för dokumentet är ett par . $D$ $(z,i_{min})$

Signaturverifiering

Beräkna ; $s_{1}=zH_{pub}^{T}$
Beräkna ; $s_{2}=h(h(D)|i_{min})$
Jämför och : om de matchar är signaturen korrekt. $s_{1}$ $s_{2}$

Ett exempel på hur systemet fungerar

Låt Reed-Solomon-koden över Galois-fältet konstruerat modulo det irreducerbara polynomet väljas för kodning med det genererande polynomet $(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.$

Sedan är den genererande matrisen för koden: $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))$

Kodkontrollmatris: $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))$

Observera att avståndet för denna kod , det vill säga antalet korrigerbara fel . $d=n-k+l=5$ $t=(d-1)/2=2$

Nyckelgenerering

Låt matrisen väljas . Sedan dess inversa matris $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}}$

Låt en permutationsmatris väljas ${\displaystyle P={\begin{pmatrix}0&1&0&0&0&0&0\\0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\\1&0&0&0&0&0&0\\\0&0&0&0&0&0&0&1\\\0&0&0&0&0&0&0&0&0&0&1&0&0\\\1&0&0&0&0&0&0\\\0&0&0&0&0&0&0&1\\\0&0&0&0)\slut$

I det här fallet kommer systemets publika nyckel att vara matrisen: $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))$

Kryptering

Låt det valda meddelandet representeras som en viktvektor på 2. $m={\begin{pmatrix}0&2&0&0&0&5&0\end{pmatrix}}$

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

Dechiffrera

Godkänd vektor $M={\begin{pmatrix}7&2&7&7\end{pmatrix}}$

För det beräknar vi det avkodningsbara syndromet $s=M(S^{-1})^{T}={\begin{pmatrix}0&1&3&6\end{pmatrix}}$

Med hjälp av Reed-Solomon-avkodningsalgoritmen avkodar vi . $s$

Skaffa en vektor ${\hat {m}}={\begin{pmatrix}2&0&0&0&0&0&5\end{pmatrix}}$

Sedan beräknar vi den ursprungliga vektorn $m=~{\hat {m}}P^{-1}={\begin{pmatrix}0&2&0&0&0&5&0\end{pmatrix}}$

Se även

Anteckningar

↑ Niederreiter H. Kryptosystem och algebraisk kodningsteori av knäppsäckstyp (engelska) // Problems of Control and Information Theory - 1986. - Vol. 15, Iss. 2. - S. 159-166.
↑ 1 2 3 4 Samokhina M. A. Modifieringar av Niederreiters kryptosystem, deras säkerhet och praktiska tillämpningar // 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. Modifierad Niederreiter-typ av GPT-kryptosystem baserat på reducerbara rangkoder // Des . Koder Cryptogr. — Springer US , Springer Science+Business Media , 2014. — Vol. 70, Iss. 1. - S. 231-239. — ISSN 0925-1022 ; 1573-7586 - doi:10.1007/S10623-012-9757-4
↑ Sidelnikov V. M. , Shestakov S. O. Om ett krypteringssystem baserat på generaliserade Reed–Solomon-koder // Discrete Math. matematik. - 1992. - Vol. 4, nummer. 3. - S. 57-63. — ISSN 2305-3143 ; 0234-0860
↑ Gabidulin E. M. Teori om koder med maximal rangdistans // Probl. överföring av information - 1985. - T. 21, nr. 1. - S. 3-16.
↑ 1 2 3 Canteaut A. , Sendrier N. Cryptanalysis of the Original McEliece Cryptosystem // Advances in Cryptology - ASIACRYPT 1998 : International Conference on the Theory and Applications of Cryptology and Information Security, Peking, Kina, 18-22 oktober 1998, 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. Öppen kryptering baserad på binära Reed-Muller-koder // Diskr. matematik. - 1994. - V. 4, nummer. 3. - S. 191-207. — ISSN 2305-3143 ; 0234-0860
↑ Courtois N. , Finiasz M. , Sendrier N. How to Achieve a McEliece-Based Digital Signature Scheme // Advances in Cryptology - ASIACRYPT 2001 : 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australien, 9-13 december 2001, Proceedings / C. Boyd - London : 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

Litteratur

Wieschebrink C. Cryptanalysis of the Niederreiter Public Key Scheme Based on GRS Subcodes // Post -Quantum Cryptography : Third International Workshop, PQCrypto 2010, Darmstadt, Tyskland, 25-28 maj 2010. Proceedings / N. Sendrier — Berlin : Springer Berlin Heidelberg , 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 Kryptologi // Samling av problem om kodningsteori, kryptologi och datakomprimering - Novosibirsk : NGU , 2013. - P. 41-49. - 100 s. — ISBN 978-5-4437-0184-4
Schneier B. Tillämpad kryptografi. Protokoll, algoritmer, källkod i C-språk = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 sid. - 3000 exemplar. - ISBN 5-89392-055-4 .