McEliece

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 9. januar 2021; checks kræver 5 redigeringer .

McEliece er et offentlig nøglekryptosystem baseret på algebraisk kodningsteori, udviklet i 1978 af Robert McEliece [1] . Det var den første ordning, der brugte randomisering i krypteringsprocessen. Algoritmen har ikke fået bred anerkendelse inden for kryptografi , men den er samtidig en kandidat til post-kvantekryptografi , da den er modstandsdygtig over for angreb ved hjælp af Shor-algoritmen [2] .

Algoritmen er baseret på kompleksiteten af afkodning af fulde lineære koder (generelt afkodningsproblem er NP-hårdt ) [3] .

For at beskrive den private nøgle vælges en fejlretningskode, hvortil der kendes en effektiv afkodningsalgoritme, og som kan rette fejl. Algoritmen bruger binære Gopp- koder , som let afkodes takket være Peterson-algoritmen . Den offentlige nøgle opnås ved at skjule den valgte kode som en komplet lineær. For at gøre dette multipliceres den genererende matrix først til højre med permutationsmatricen og derefter med den ikke -singulære matrix til venstre (se arbejdsalgoritmen ). $t$ $G$ $P$ $S$

Der er flere varianter af kryptosystemet, der bruger forskellige typer koder. De fleste af dem er mindre sikre. Separat overvejelse fortjener spørgsmålet om valg af parametrene for kryptosystemet [4] .

Indtil videre er McElice med Goppa -koder ikke blevet krypteret [5] . De mest kendte angreb bruger datasæt- afkodningsalgoritmen . Nyere værker beskriver både angreb på systemet og dets forsvar [6] . Andre papirer har vist, at til kvanteberegning skal nøglestørrelsen øges med fire størrelsesordener på grund af forbedringer i datasætafkodning [2] .

Kryptosystemet har flere fordele, såsom over RSA . Kryptering og dekryptering er hurtigere, og efterhånden som nøglelængden vokser, vokser graden af databeskyttelse meget hurtigere. I lang tid troede man, at McEliece ikke kunne bruges til EDS . Det viste sig dog at være muligt at bygge et skema til en EDS baseret på Niederreiter-kryptosystemet (modificeret af McEliece). Da disse to kryptosystemer, afhængigt af de anvendte koder, udtrykker det samme kodeproblem, kan det i dag argumenteres for, at McEliece er anvendelig i autentificeringsproblemer .

På grund af mangler bruges McEliece sjældent. En undtagelse er brugen af McElice til kryptering på et Freenet -lignende ENTROPY -netværk .

Introduktion til Goppa-koder

Beskrivelse

Et goppa-polynomium er defineret som et polynomium over et felt af formen , hvor , og . Vi definerer også en dimensionel delmængde over feltudvidelsen : , hvilket er sandt for enhver . Yderligere, for kodeordet over feltet , er funktionen defineret . $GF(p^{m})$ $g(x)=g_{0}+g_{1}x+g_{2}x^{2}+...+g_{t}x^{t}=\sum _{i=0 }^{t}g_{i}x^{i}$ $g_{i}\in GF(p^{m})$ $t\in [2,...,(n-1)/d]$ $n$ $L$ $GF(p^{m})$ $L=[\alpha _{1},...,\alpha _{n}]\subseteq GF(p^{m})$ $g(\alpha _{i})\not =0$ ${\displaystyle \alpha _{i))$ $c=[c_{0},...c_{n}]$ $GF(p^{m})$ $R_{c}(x)=\sum _{i=1}^{n}{\frac {c_{i}}{x-\alpha _{i}}}$

Goppa-koden består af alle kodeord , der opfylder . Det betyder, at polynomiet deler sig . $\Gamma =\Gamma (L,g)$ $\mathbf {c} =(c_{1},...c_{n})$ $R_{c}(x)\equiv 0\ (mod\ g(x))$ $g(x)$ $R_{c}(x)$

Dimensionen af en Goppa-kode af længde er større end eller lig med , og den mindste kodeafstand er større end eller lig med . $k$ $\Gamma (L,g)$ $n$ $n-mt$ $d$ $t-1$

Tjekmatricen har følgende form: $\Gamma (L,g)$

$H={\begin{pmatrix}1/g(\alpha _{1})&\cdots &1/g(\alpha _{n})\\\alpha _{1}/g(\alpha _ {1})&\cdots &\alpha _{n}/g(\alpha _{n})\\\vdots &\ddots &\vdots \\\alpha _{1}^{t-1}/g (\alpha _{1})&\cdots &\alpha _{n}^{t-1}/g(\alpha _{n})\end{pmatrix}}$ .

Hvis Goppa-polynomiet er et irreducerbart polynomium over feltet , så er minimumsafstanden for en sådan kode større end eller lig med . I det følgende antages det, at . $g(x)$ $GF(2^{m})$ $d$ $2t+1$ $d=2t+1$

Kryptologiske applikationer bruger en irreducerbar, binær Goppa-kode med parametre . $[n,kd]=[n,n-mt,2t+1]$

Årsager til at bruge

Der er flere grunde til at bruge Goppa-koder i McEliece-kryptosystemet. For det første er der flere hurtige polynomielle tidsafkodningsalgoritmer [7] . For det andet er ethvert irreducerbart polynomium over et felt egnet til at specificere en Goppa-kode, den genererende matrix af koden er næsten tilfældig. Derfor er Goppa-koder meget nemme at indstille, men samtidig svære at genkende. For en fast kodeordslængde er der mange koder. For eksempel, for en kode med længde , der er i stand til at rette op til fejl, er der omkring forskellige Goppa-koder. Deres antal vokser eksponentielt afhængigt af længden af ordet og graden af det genererende polynomium. $GF(2^{m})$ $n$ $n=128$ $t=10$ $10^{15}$

Operationsalgoritme

McEliece består af tre algoritmer:

en tilfældig nøglegenereringsalgoritme , der producerer en offentlig og privat nøgle;
tilfældig krypteringsalgoritme ;
deterministisk dekrypteringsalgoritme.

Teksten i beskeden er en længdevektor over det sidste felt . $k$ $GF(q)$

Alle brugere på systemet deler sikkerhedsindstillinger: . $n,~k,~t$

Nøglegenerering

Alice vælger en -lineær fejlkorrigerende kode. Derefter beregnes generatormatricen for koden . $(n,k)$ $C$ $t$ $C$ $k \ gange n$ $G$
For at gøre den originale kode svær at genskabe, genererer Alice en tilfældig ikke-singular matrix . $k\ gange k$ $S$
Alice genererer en tilfældig permutationsmatrix . $n\ gange n$ $P$
Alice beregner matrixen . $k \ gange n$ ${{\hat G}}=SGP$
Den offentlige nøgle er et par . Den private nøgle er sættet . $({{\hat G)),t)$ $(S,G,P)$

Beskedkryptering

Lad Bob ønske at sende en besked til Alice, hvis offentlige nøgle er . $m$ $({{\hat G)),t)$

Bob præsenterer sit budskab som sekvenser af binære tegn af længde . $m$ $k$
Bob genererer en tilfældig vektor af længde , som har en Hamming-vægt . $z$ $n$ $t$
Bob beregner chifferteksten , mens han sender den til Alice. $c'=m{\hat {G}}+z$

Meddelelsesdekryptering

Efter at have modtaget beskeden , udfører Alice følgende trin for at dekryptere beskeden: $c$

Alice beregner den inverse matrix ; $P^{-1}$
Alice beregner ; ${{\hat c}}=cP^{{-1}}$
Alice bruger en afkodningsalgoritme for koden at komme fra ; $C$ ${{\hat m))$ ${{\hat c))$
Alice beregner . $m={{\hat m}}S^{{-1}}$

Algoritme korrekthed

Lad os vise, at hovedegenskaben ved kryptosystemet [5] er opfyldt , det vil sige at . $D_{t}(E_{z}(m))=m$

Bob sender . Alice beregner . Da det er en permutationsmatrix, så er vægten højst . $c=m{\hat {G}}+z=mSGP+z$ ${{\hat c}}=cP^{{-1}}=mSG+zP^{{-1}}$ $P^{-1}$ $zP^{-1}$ $t$

Gopps kode retter op til fejl. Hammerafstand , så Alice får den rigtige besked . Alice beregner derefter den originale besked . $G$ $t$ $d_{H}(mSG,cP^{{-1}})\leq t$ ${{\hat m}}=mS$ $m={{\hat m}}S^{{-1}}=mSS^{{-1}}$

Et eksempel på, hvordan algoritmen fungerer

Lad en irreducerbar, binær Goppa-kode med parametre bruges , hvor er et irreducerbart polynomium af grad over feltet , og . $[12,4,5]$ ${\displaystyle g(x)=x^{2}+x+\alpha ^{3))$ $t=2$ $GF(2^{4})$ $\alpha ^{3}=(0,0,0,1)^{T}\in GF(2^{4})$

Alice genererer tilfældigt en generatormatrix af en sådan kode

{\displaystyle G={\begin{pmatrix}0&1&1&0&1&0&1&0&0&1&0&0\\0&1&1&1&1&1&0&0&1&1&0&0&0&0\\1&1&0&1&1&0&0&0&0&0&0&0&1\\\{1&1&1&0)\end

vælger en matrix

S={\begin{pmatrix}1&0&0&1\\0&1&0&1\\0&1&0&0\\0&0&1&1\end{pmatrix}}

og en permutationsmatrix

P={\begin{pmatrix}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&0&0&0&0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0&0&0&0&0\\0&0&0&0&1&0&0&0&0&0&0&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&0&0&0&0&0&0&0&0&0&1\\0&0&0&0&0&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&0&0&1&0\\0&0&0&0&0&0&1&0&0&0&0&0\\\end{ pmatrix}}

Derefter

{\hat {G}}=SGP={\begin{pmatrix}1&1&0&1&0&0&0&0&0&1&1&1\\1&1&0&0&0&1&0&1&0&0&1&0\\0&0&1&0&1&1&0&1&1&0&0&1\\0&1&0&0&0&1&1&0&1&0&1&1trix}}}\end{pmatrix}}}\end{pmatrix}}}\end{pmatrix }}

Denne matrix leveres som den offentlige nøgle og . Hvis Bob vil sende en besked til Alice, genererer han først en vektor med vægt , f.eks . $t=2$ $m=(1,0,1,0)$ $2$ $z=(1,1,0,0,0,0,0,0,0,0,0,0)$

Beregner chiffertekst

$c'=m{\hat {G}}+z=(1,1,1,1,1,1,0,1,1,1,1,0)+(1,1,0, 0,0,0,0,0,0,0,0,0)=(0,0,1,1,1,1,0,1,1,1,1,0)$

og sender den til Alice.

Efter at have modtaget en besked, beregner Alice først

${\hat {c}}=c'P^{-1}=m{\hat {G}}P^{-1}+zP^{-1}=m(SGP)P^{- 1}+zP^{-1}=(mS)G+y'=(0,1,1,1,1,0,1,0,1,1,1,0)$ .

På grund af permutationerne er fejlene flyttet til det første og sjette tegn. Alice finder ved hjælp af en hurtig afkodningsalgoritme

$mSG=(1,1,1,1,1,1,1,0,1,1,1,0)$ .

Fund . $mS=(1,1,0,1)$

Og til sidst får Alice . $m=(1,1,0,1)S^{-1}=(1,0,1,0)$

Nøglestørrelser

Indledningsvis blev parametrene foreslået: Som et resultat var størrelsen af den offentlige nøgle 524*(1024-524) = 262.000 bit. I en nylig analyse er følgende parametre blevet foreslået: for 80 bits sikkerhed ved brug af konventionel algebraisk dekodning eller ved brug af en afkodningstabel til Goppa-koden. I dette tilfælde øges den offentlige nøgle til henholdsvis 520.047 og 460.647 bit. For stabilitet mod en kvantecomputer bør parametrene øges til , og størrelsen af den offentlige nøgle til 8.373.911 bits [1] [6] . $n=1024,k=524,t=50$ $n=2048,k=1751,t=27$ $n=1632,k=1269,t=34$ $n=6960,k=5413,t=119$

Angreb

Systemets kryptografiske styrke er baseret på to komplekse beregningsproblemer: udtømmende nøglerumssøgning og maksimal sandsynlighedsafkodning. Litteraturen beskriver et ret stort antal angreb på McEliece [8] . Nogle angreb, kaldet strukturelle angreb , er baseret på et forsøg på at bygge/reverse engineering af en dekoder til den kode, der genereres af den offentlige nøgle . Hvis et sådant forsøg lykkes, vil den private nøgle blive afsløret, og kryptosystemet vil blive fuldstændig brudt. Koden genereret af matrixen og koden genereret af matrixen tilhører den samme ækvivalente klasse. Angriberen skal sammenligne den repræsentative kode fra hver klasse for at bestemme den tilsvarende kode. Da de tilsvarende klasser er meget lavt strømforbrug, er denne proces ud over selv de mest kraftfulde computeres muligheder. For originale parametre kræver dette strukturelle angreb flere koder at lære [5] . ${\hat {G}}$ $G$ ${\hat {C))$ ${\hat {G}}$ $C$ $G$ ${\hat {C))$ $(1024,524,50)$ $2^{466}$

Andre angreb er rettet mod at hente den originale tekst af beskeden fra den krypterede besked. De fleste af dem er baseret på datasætafkodning (ISD ) eller fødselsdagsparadokset [9] , deres generaliseringer og forbedringer. Der er angreb såsom iterativ afkodning [3] og statisk afkodning, men de er ikke succesfulde. ISD-angrebet viste sig at være det mindst vanskelige. Flere algoritmer og deres forbedringer er blevet beskrevet i de senere år. De vigtigste er anført i tabellen sammen med deres binære afkodningsomkostninger for Goppa-koden. For disse algoritmer er deres begrænsende indikatorer kendte [10] . $(1024,524,50)$

År	Algoritme	Sværhedsgrad ( ) $log_{2}$
1986	Adams-Meyer	80,7
1988	Lee Brickell	70,89
1989	hård	66,21
1994	Kanteout Chabannes	65,5
1998	Canteout-Shabant	64,1
2008	Bernstein-Lang-Peters	60,4
2009	Finiaz-Sendreir	59,9

Beskrivelse af Stern-angrebsalgoritmen

Lad er en længdekode over feltet , og dimensionel vektor har en afstand fra kodeordet , så er et element med en afstand fra . Omvendt, hvis er en længdekode over et felt med en minimumsafstand mindre end , så kan vægtelementet ikke være i , det skal være i . Eller på anden måde, er et element med afstand fra . $C$ $n$ $GF(2)$ $n$ $y$ $\omega$ $c\in C$ $yc$ $C$ $\omega$ $y$ $C$ $n$ $GF(2)$ $\omega$ $e\in C+[0,y]$ $\omega$ $C$ $C+[y]$ $ye$ $C$ $\omega$ $y$

Chifferteksten til McEliece-kryptosystemet har en afstand fra kodens unikke nærmeste kodeord , der har en afstand på mindst . Angriberen kender kodens generatormatrix og kan nemt tilføje for at danne generatormatricen for . Det eneste vægtkodeord i er . Efter at have fundet dette kodeord, finder angriberen og får nemt den ønskede tekst. Det er værd at overveje, at afkodning giver en lille forenkling: $y$ $t$ $c$ $C$ $2t+1$ $C$ $y$ $C+[0,y]$ $t$ $C+[0,y]$ $yc$ $c$

hvis det har dimension , så har det dimension . Stern-algoritmen giver dig mulighed for at finde kodeordet for den mindste vægt. $C$ $k$ $C+[0,y]$ $k+1$

Find det laveste kodeord

Algoritmens input er et tal og en kontrolmatrix af størrelse for koden over feltet . Ved hjælp af lineære algebra -metoder er det altid muligt at få en kontrolmatrix fra den genererende matrix. $\omega >0$ $H$ $(nk)\ gange n$ $(n,k)$ $\mathbb {F} _{2}$

Tilfældigt udvalgt fra kolonnerne i matrixen . Derefter vælges et -dimensionelt underrum tilfældigt , som deler de resterende delmængder i to delmængder og . For et kodeord, der har nøjagtigt ikke-nul bits i , nøjagtigt ikke-nul bits i , ikke-nul bits i , og nøjagtigt ikke-nul bits i andre kolonner. $nk$ $n$ $H$ $l$ $Z$ $k$ $x$ $Y$ $s$ $x$ $s$ $Y$ $0$ $Z$ $\omega-2p$

Søgningen består af tre trin. Ved det første trin, ved at anvende de enkleste operationer, får vi identitetsmatrixen fra de valgte kolonner . Dette kan ikke gøres, hvis den originale submatrix ikke er inverterbar, så genstartes algoritmen. Tab ved genstart undgås på grund af det adaptive valg af hver kolonne. $H$ $nk$ $(nk)\ gange (nk)$ $H$

I det andet trin er submatrixen identitetsmatrixen, kolonnesættet svarer til rækkerne . For hver dimensionel delmængde af sættet beregnes summen af kolonnerne i for hver af disse rækker. Resultatet er en -bit vektor . På samme måde for hver dimensionel delmængde af sættet . $(nk)\ gange (nk)$ $H$ $Z$ $l$ $l$ $s$ $EN$ $x$ $EN$ $l$ $l$ $\pi (A)$ $s$ $B$ $Y$

Ved det tredje trin, for hver kollision , summen af kolonnerne i . Denne sum vil være en -bit vektor. Hvis summen har en vægt , så fås den ved at tilføje de tilsvarende kolonner til submatrixen. Disse kolonner danner sammen med og danner det ønskede vægtkodeord . $\pi (A)=\pi (B)$ $2p$ $A\kop B$ $(nk)$ $\omega-2p$ $0$ $\omega-2p$ $(nk)\ gange (nk)$ $\omega-2p$ $EN$ $B$ $\omega$

Ulemper

De største ulemper ved McEliece-kryptosystemet [6] :

Størrelsen på den offentlige nøgle er for stor. Når du bruger Goppa-koder med parametrene foreslået af McEliece, er den offentlige nøgle en smule, hvilket forårsager vanskeligheder i implementeringen; ${{\hat G}}=SGP$ $2^{19}$

Den krypterede meddelelse er meget længere end originalen;

I øjeblikket er algoritmer, der bruger dette kryptosystem i autentificeringsopgaver, ikke meget brugt.

Noter

↑ 1 2 R. J. McEliece. Et offentligt nøglekryptosystem baseret på algebraisk kodningsteori // DSN-fremskridtsrapport 42-44. — 1978. Arkiveret den 2. november 2021.
↑ 1 2 Dinh H. , Moore C. , Russell A. McEliece og Niederreiter Cryptosystems That Resist Quantum Fourier Sampling Attacks // Advances in Cryptology - CRYPTO 2011 : 31st Annual Cryptology Conference, Santa Barbara, CA, USA, 14-18 august, august 2011, Proceedings / P. Rogaway - Springer Science + Business Media , 2011. - P. 761-779. — 782 s. — ISBN 978-3-642-22791-2 — doi:10.1007/978-3-642-22792-9_43
↑ 1 2 Berlekamp E. R. , McEliece R. J. , Tilborg H. C. A. v. Om visse kodningsproblemers iboende vanskelighed // IEEE Trans . inf. Teori / F. Kschischang - IEEE , 1978. - Vol. 24, Iss. 3. - S. 384-386. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1978.1055873
↑ Niebuhr R. , Meziani M. , Bulygin S. , Buchmann J. Selecting Parameters for Secure McEliece-based Cryptosystems (engelsk) // International Journal of Information Security - Springer Science + Business Media , 2012. - Vol. 11, Iss. 3. - S. 137-147. — ISSN 1615-5262 ; 1615-5270 - doi:10.1007/S10207-011-0153-2
↑ 1 2 3 4 5 A. Valentijn. Goppa-koder og deres anvendelse i McEliece Cryptosystems // Syracuse University SURFACE. - 2015. Arkiveret 21. december 2016.
↑ 1 2 3 4 Bernstein D. J. , Lange T. , Peters C. Attacking and Defending the McEliece Cryptosystem // Post-Quantum Cryptography : Second International Workshop , PQCrypto 2008 Cincinnati, OH, USA 17-19 oktober, 2008 J. Buchmannedings , J. Ding - Berlin , Heidelberg , New York, NY , London [etc.] : Springer Science + Business Media , 2008. - S. 31-46. — 231 s. - ( Lecture Notes in Computer Science ; Vol. 5299) - ISBN 978-3-540-88402-6 - ISSN 0302-9743 ; 1611-3349 - doi:10.1007/978-3-540-88403-3_3 D. J. Bernstein1 , Tanja Lange, C. Peters. Angribe og forsvare McEliece-kryptosystemet . - 2008. Arkiveret 1. august 2016.
↑ P. Loidreau. Styrkelse af McEliece Cryptosystem // Springer-Verlag Berlin Heidelberg. - 2000.
↑ 1 2 D. Engelbert, R. Overbeck, A. Schmidt. En oversigt over McEliece-type kryptosystemer og deres sikkerhed // IACR Eprint-arkiv. - 2006. Arkiveret 23. december 2016.
↑ N. Courtois, M. Finiasz, N. Sendrier. Sådan opnår du et McEliece-baseret digitalt signaturskema . - 2001. Arkiveret den 22. juli 2018.
↑ DJ Bernstein, T. Lange, C. Peters, HCA van Tilborg. Eksplicitte grænser for generiske afkodningsalgoritmer til kodebaseret kryptografi // International Workshop on Coding and Cryptography. - 2009. Arkiveret 20. december 2016.

Litteratur

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 .
Menezes A. J. , Oorschot P. v. , Vanstone S. A. Handbook of Applied Cryptography (engelsk) - CRC Press , 1996. - 816 s. — ( Diskret matematik og dens anvendelser ) — ISBN 978-0-8493-8523-0
Canteaut A. , Sendrier N. Cryptanalysis of the Original McEliece Cryptosystem (engelsk) // 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