Niederreiter kryptosystem

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 16. marts 2019; checks kræver 3 redigeringer .

Niederreiter -kryptosystemet er et offentlig -nøgle -kryptosystem baseret på teorien om algebraisk kodning , udviklet i 1986 af Harald Niederreiter [1] . I modsætning til McEliece-kryptosystemet bruger Niederreiter -kryptosystemet en kodekontrolmatrix . Niederreiter-kryptosystemet tillader oprettelse af digitale signaturer og er en kandidat til post-kvantekryptografi , da det er modstandsdygtigt over for angreb ved hjælp af Shor-algoritmen .

Algoritmen, der bruges i Niederreiter-kryptosystemet, er baseret på vanskeligheden ved at afkode komplette lineære koder .

På trods af at dette kryptosystem er blevet hacket, forbliver nogle af dets modifikationer krypto -resistente [2]

Operationsalgoritme

Nøglegenerering

Alice vælger en fejlkorrigerende kode frem for Galois-feltet . Denne kode skal have en effektiv afkodningsalgoritme [3] . $(n,k)$ $C$ $GF(q)$ $t$
Alice genererer en kodekontrolmatrix . $(nk)\ gange n$ $H$ $C$
Alice vælger en tilfældig ikke-degenereret matrix frem for feltet og en eller anden permutationsmatrix [3] . $(nk)\ gange (nk)$ $S$ $GF(q)$ $n\ gange n$ $P$
Alice beregner matrixen $(nk)\ gange n$ $H_{pub}=SHP$
Alices offentlige nøgle er . Den private nøgle er sættet . $(H_{pub},t)$ $(S^{-1},H,P^{-1})$

Beskedkryptering

I dette tilfælde er meddelelser alle vektorer med koordinater fra feltet med en vægt, der ikke overstiger . Meddelelser er således alle mulige fejl, som den valgte kode er i stand til at rette [2] . Antag, at Bob vil sende en besked til Alice, hvis offentlige nøgle er . $n-$ $GF(q)$ $t$
$(H_{pub},t)$

Bob præsenterer sit budskab som en binær sekvens af længde , med en vægt, der ikke overstiger . $m$ $n$ $t$
Bob beregner chifferteksten ved hjælp af formlen: . Således er chifferteksten i Niederreiters kryptosystem det støjende krypterede fejlvektorsyndrom [ 2] . $c=mH_{pub}^{T}$

Meddelelsesafkodning

Efter at have modtaget beskeden gør Alice følgende: $c$

Alice beregner . Bemærk, at da permutationsmatricen er , falder vægten sammen med vægten og ikke overstiger , og derfor kan afkodningsalgoritmen for finde fejlvektoren svarende til 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 bruger en hurtig afkodningsalgoritme til at finde koden [3] . $C$ ${\hat {m}}$
Alice beregner beskeden . ${\hat {m}}P^{-1}=mPP^{-1}=m$

Det originale kryptosystem og dets modifikationer

I det originale kryptosystem foreslog Niederreiter at bruge Reed-Solomon-koder og brugte ikke en permutationsmatrix . Et sådant system viste sig dog at være ustabilt og blev hacket af Sidelnikov og Shestakov i 1992 [4] . Forfatterne har vist, at det er muligt at gætte strukturen af den private nøgle fra den offentlige nøgle og vælge sådanne matricer og , at . Derefter blev det foreslået at bruge en permutationsmatrix for at øge systemets kryptografiske styrke . Derudover dukkede forskellige ændringer af systemet op, for eksempel: $P$ ${\hat {H}}$ ${\hat {S}}$ $H_{pub}={\hat {S}}{\hat {H}}$ $P$

ved at bruge forskellige andre metrikker end klassisk Hamming , for eksempel rang [5] : et eksempel på dette er det modificerede GPT-system [3]
ved hjælp af koder med specifikke egenskaber. Så modifikationer baseret på Goppa-koder er stadig krypto-resistente [2] .

Fordele og ulemper ved systemet

Fordele

I modsætning til McEliece bruger Niederreiter-kryptosystemet ikke tilfældige parametre. Resultatet af kryptering af den samme tekst vil således være det samme. Dette faktum gør det muligt at bruge Niederreiter-systemet, og ikke McEliece, til at skabe en digital signatur .
Størrelsen af den offentlige nøgle i Niederreiters kryptosystem er flere gange mindre end i McEliece [6] . ${\frac {n}{nk}}$
Sammenlignet med RSA er krypteringshastigheden omkring 50 gange hurtigere, og dekrypteringshastigheden er 100 gange hurtigere [6] .

Ulemper

For at kryptere en vilkårlig besked, en algoritme til oversættelse til en -ær vektor med en vægt på ikke mere end . $q$ $n$ $t$
Nøglestørrelsen er større end i klassiske offentlige nøglekryptosystemer ( RSA , ElGamal Scheme , GOST R 34.10-2012 ).
Størrelsen af chifferteksten er meget større end størrelsen af den krypterede meddelelse (hvis meddelelsen af størrelse er oversat til en vektor af længde og krypteret, opnås en chiffertekst af størrelse , som er mindst 2 gange større end ). $t$ $n$ $nk$ $t$

Tabellen nedenfor viser forskellige parametre for McEliece, Niederreiter og RSA kryptosystemer, der tydeligt viser deres fordele og ulemper [6] .

	McEliece n=1024, k=524, t=101 binær kode	Niederreiter kryptosystem n=1024, k=524, t=101 binær kode	RSA 1024-bit moduler e=17
Offentlig nøglestørrelse i bytes	67072	32750	256
Antal bits brugbar information	512	276	1024
Antal binære operationer til kryptering	514	halvtreds	2402
Antal binære operationer til dekryptering	5140	7863	738112

Ækvivalens af kryptografisk sikkerhed for Niederreiter-systemet og McEliece-systemet

Som vist i det originale papir om Sidelnikov-systemet [7] kan angreb på Niederreiter-systemet polynomielt reduceres til at angribe McEliece-systemet og omvendt.

Lad syndromet være kendt . Så kan vi beregne en vektor med nogle sådan, at . Vektoren vil blive behandlet som en chiffertekst i McEliece-systemet. Hvis der findes et kryptografisk angreb med kompleksitet for McEliece-systemet, det vil sige en algoritme til beregning af vektoren , som er hemmelig information i dette system, er kendt, så kan vektoren , som er en hemmelighed for Niederreiter-systemet, repræsenteres som . Således er kompleksiteten af definitionen den samme som kompleksiteten af definitionen af . $c=eD$ $b=aE+e$ $-en$ $c=bD$ $b$ $T$ $-en$ $e$ $e=aE+b$ $e$ $-en$

Hvis et kryptoangreb med kompleksitet for Niederreiter-systemet er kendt, så er det muligt, ved at bruge vektoren som chiffertekst , at beregne vektorerne og . $T$ $(aE+e)D^{T}=eD^{T}$ $e$ $-en$

Opbygning af en digital signatur

I 2001 viste Nicolas Courtois, Matthew Finiaz og Nicolas Sandrier [8] , at Niederreiter-kryptosystemet kan bruges til at skabe en elektronisk signatur .

Meddelelsessignatur

Lad være den offentlige nøgle til Niederreiter-kryptosystemet ved hjælp af en -lineær kode. For at underskrive et dokument skal du: $H_{pub}$ $(n,k,d)$ $D$

Vælg en hash-funktion , der giver tegn ved udgangen. Resultatet af en given hashfunktion kan således repræsenteres som et syndrom og forsøges afkodet; $h()$ $nk$
Beregn hash ; $s=h(D)$
For hver beregn ; $i=0,1,2,...$ $s_{i}=h(s|i)$
Find det mindste tal , således at syndromet vil være muligt at afkode. Lad være resultatet af afkodning af syndromet ; $jeg er med}$ $s_{i_{min}}$ $z$ $s_{i_{min}}$
Dokumentets underskrift er et par . $D$ $(z,i_{min})$

Signaturbekræftelse

Beregn ; $s_{1}=zH_{pub}^{T}$
Beregn ; $s_{2}=h(h(D)|i_{min})$
Sammenlign og : hvis de matcher, er signaturen korrekt. $s_{1}$ $s_{2}$

Et eksempel på hvordan systemet fungerer

Lad Reed-Solomon-koden over Galois-feltet konstrueret modulo det irreducible polynomium vælges til kodning med det genererende polynomium $(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.$

Så er den genererende matrix for 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))$

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

Bemærk, at afstanden til denne kode , det vil sige antallet af korrigerbare fejl . $d=n-k+1=5$ $t=(d-1)/2=2$

Nøglegenerering

Lad matrixen vælges . Så dens omvendte matrix $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}}$

Lad en permutationsmatrix vælges $P={\begin{pmatrix}0&1&0&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&1\\\0&0&0&01&0)\end$

I dette tilfælde vil systemets offentlige nøgle være matrixen: $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

Lad den valgte meddelelse blive repræsenteret som en vægtvektor på 2. $m={\begin{pmatrix}0&2&0&0&0&5&0\end{pmatrix}}$

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

Dechifrering

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

Til det beregner vi det afkodbare syndrom $s=M(S^{-1})^{T}={\begin{pmatrix}0&1&3&6\end{pmatrix}}$

Ved at bruge Reed-Solomon afkodningsalgoritmen afkoder vi . $s$

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

Derefter beregner vi den oprindelige vektor $m=~{\hat {m}}P^{-1}={\begin{pmatrix}0&2&0&0&0&5&0\end{pmatrix}}$

Se også

Noter

↑ Niederreiter H. Kryptosystemer og algebraisk kodningsteori (engelsk) // Problems of Control and Information Theory - 1986. - Vol. 15, Iss. 2. - S. 159-166.
↑ 1 2 3 4 Samokhina M. A. Ændringer af Niederreiter-kryptosystemet, deres sikkerhed og praktiske anvendelser // 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. Modificeret Niederreiter-type af GPT-kryptosystem baseret på reducerbare 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 et krypteringssystem baseret på generaliserede Reed–Solomon-koder // Diskret matematik. matematik. - 1992. - Bind 4, udgave. 3. - S. 57-63. — ISSN 2305-3143 ; 0234-0860
↑ Gabidulin E. M. Teori om koder med maksimal rangdistance // Probl. overførsel af information - 1985. - T. 21, no. 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, Beijing, Kina, 18.- 22. oktober 1998, Proceedings - Berlin : Springer Berlin Heidelberg , 1998. - S. 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. Åben kryptering baseret på binære Reed-Muller-koder // Diskr. matematik. - 1994. - V. 4, udgave. 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, December 9-13, 2001, Proceedings / C. Boyd - London : Springer Science + Business Media , 2001. - S. 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 // Indsamling af problemer om kodningsteori, kryptologi og datakomprimering - Novosibirsk : NGU , 2013. - S. 41-49. - 100 sek. — ISBN 978-5-4437-0184-4
Schneier B. Anvendt kryptografi. Protokoller, algoritmer, kildekode i C-sprog = Applied Cryptography. Protocols, Algoritms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 eksemplarer. - ISBN 5-89392-055-4 .