Multidimensionel kryptografi

Multidimensionel kryptografi eller multivariat offentlig nøglekryptografi er et generelt udtryk, der beskriver asymmetriske kryptografiske skemaer bygget på løsninger af ligninger baseret på multivariate polynomier over et begrænset felt . $\mathbb {F}$

Sikkerheden ved multidimensionel kryptografi er baseret på den antagelse, at løsning af et system af kvadratiske polynomier over et endeligt felt generelt er NP-komplet i stærk forstand eller blot NP-komplet . Dette er grunden til, at disse ordninger ofte betragtes som gode kandidater til post-kvantekryptografi . [en] $\mathbb {F}$

Oprettelseshistorie

Det første forsøg på at konstruere et kryptografisk skema baseret på multivariate kvadratiske polynomier blev lavet af Ong, Schnor og Shamir [2] , hvor de foreslog et signaturskema baseret på kompleksiteten i at løse ligningen: ;
$s_{1}^{2}+k*s_{2}^{2}=m(\mod n)$

Sikkerheden i denne ordning er dog stadig baseret på kompleksiteten af faktoriseringen , og derfor er denne ordning sårbar over for angreb ved hjælp af kvantecomputere . Udviklingen af multidimensionelle kryptografiske skemaer i moderne forstand begyndte i 1988 med C*-skemaet i Matsumoto-Imai-systemet [3] . $n=p*q$

Matsumoto og Imai brugte en bijektiv kortlægning over en gradfeltudvidelse fra formularen: . For at sikre, at denne transformation er reversibel, er det nødvendigt at vælge på en sådan måde, at . Ovenstående ligning giver, på grund af den kanoniske isomorfi mellem og vektorrummet, et system af flerdimensionelle kvadratiske ligninger på feltet , dette forklares med Frobenius endomorfismen . For at skjule strukturen brugte Matsumoto og Imai to affine transformationer og . Så de præsenterede den offentlige nøgle i formen: . ${\mathcal {F}}$ $n$ ${\mathbb {E}}$ $GF(2)$ ${\mathcal {F}}:\mathbb {E} \rightarrow \mathbb {E} ,{\mathcal {F}}(X)=X^{2^{\theta }+1}$
$\theta$ ${\text{gcd}}(2^{\theta }+1,2^{n}-1)=1$ $GF(2^n)$ ${\displaystyle GF(2)^{n))$ ${\mathcal {F}}$ $GF(2)$ ${\mathcal {F}}$ $\mathcal{S}$ $\mathcal{T}$ ${\mathcal {P}}={\mathcal {S}}\circ {\mathcal {F}}\circ {\mathcal {T}}$

Dette design kaldes bipolar. Det er stadig standardmetoden til at bygge multidimensionelle offentlige nøglekryptosystemer. [fire]

Multidimensionel kryptografi har været et aktivt forskningsområde, men der er stadig mangel på multidimensionelle skemaer såsom: nøgleudvekslingsprotokoller og signaturskemaer med specielle egenskaber [5] .

Relevans og udviklingsmuligheder

De fleste offentlige nøglekryptosystemer, der bruges i praksis, er baseret på heltalsfaktorisering eller diskrete logaritmer (i endelige felter eller elliptiske kurver ). [6] Disse systemer lider dog af to ulemper.

Fremskridt inden for talteori har ført til et fald i effektiviteten af beregninger, så parameterstørrelserne skal øges i overensstemmelse med sikkerhedskravene. [en]
Hvis der kan bygges store nok kvantecomputere, vil Shors algoritme gøre nuværende systemer fuldstændig usikre. Derfor er det vigtigt at lede efter alternative systemer, der fremmer effektiv og sikker kommunikation. [en]

Multidimensionel offentlig nøglekryptografi er et muligt alternativ til nuværende implementeringer af offentlige nøglekrypteringsalgoritmer. I 2003 blev Sflash- signatursystemet det endelige valg af NESSIE -projektet (New European Signature, Integrity and Encryption Schemes) [7] . Den første bog om multidimensionel kryptografi skrevet af Ding, Gower og Schmidt blev udgivet i 2006 [5] . Der er også en international workshop, PQCrypto, som fokuserer på post-kvantekryptering, herunder multidimensionel kryptografi. [otte]

Grundlæggende operationsalgoritme

Hovedideen med standardkonstruktionen af multidimensionel kryptografi er valget af et system (central transformation) af flerdimensionale kvadratiske polynomier i variabler, der let kan inverteres. [9] Derefter vælges to tilfældige affine reversible transformationer for at skjule strukturen af den centrale transformation i den offentlige nøgle. [ti] ${\mathcal {F}}:\mathbb {F} ^{m}\rightarrow \mathbb {F} ^{n}$ $m$ $n$ ${\mathcal {S}}:\mathbb {F} ^{m}\rightarrow \mathbb {F} ^{m}$ ${\mathcal {T}}:\mathbb {F} ^{n}\rightarrow \mathbb {F} ^{m}$ ${\mathcal {F}}$

Den offentlige nøgle i et kryptosystem er en sammensat kvadratisk transformation , som antages at være usandsynlig at adskille sig fra en tilfældig og derfor vanskelig at invertere. ${\mathcal {P}}={\mathcal {S}}\circ {\mathcal {F}}\circ {\mathcal {T}}$

Den private nøgle består af , , og dermed tillader dette . $\mathcal{S}$ ${\mathcal {F}}$ $\mathcal{T}$ ${\mathcal {P}}$

Opbygning af en offentlig nøgle

Lad være et begrænset felt. Den offentlige nøgle til multidimensionelle kryptografialgoritmer er en polynomiel mapping $\mathbb {F}$ ${\mathcal {P}}:\mathbb {F} ^{n}\rightarrow \mathbb {F} ^{m}$

{\mathcal {P}}(x_{1},\ldots ,x_{n})={\begin{pmatrix}f_{1}(x_{1},\ldots,x_{n})\ \\vdots \\f_{m}(x_{1},\ldots,x_{n})\end{pmatrix}}

; hvor er et andengradspolynomium .

f_{i}\in \mathbb {F} [x_{1},\ldots ,x_{n}]

For kryptering og dekryptering antager vi, at for en elektronisk signatur :. [en] $m\geq n$ $m\leq n$

Kryptering

For at kryptere en besked eller skal du beregne . Chifferteksten for den modtagne besked er eller . [6] $\mathbf {z} \in \mathbb {F} ^{n}$ ${\displaystyle (x_{1},\ldots ,x_{n})\in \mathbb {F} ^{n))$ $\mathbf {h=} {\mathcal {P}}(\mathbf {z} )$ $\mathbf {z}$ ${\displaystyle \mathbf {h} \in \mathbb {F} ^{m))$ $(y_{1},\ldots ,y_{m})={\mathcal {P))(x_{1},\ldots ,x_{n})$

Dekryptering

For at dekryptere chifferteksten rekursivt beregnet: , og . ${\displaystyle \mathbf {h} \in \mathbb {F} ^{m))$ $\mathbf {x=} {\mathcal {S}}^{-1}(\mathbf {h} )$ $\mathbf {y=} {\mathcal {F}}^{-1}(\mathbf {x} )$ $\mathbf {z=} {\mathcal {T}}^{-1}(\mathbf {y} )$

$\mathbf {z} \in \mathbb {F} ^{n}$ er den almindelige tekst af chifferteksten . Siden , kortlægningen fra til , og dermed den resulterende klartekst, er unikke. [6] $\mathbf {h}$ $m\geq n$ $\mathbf {z}$ ${\mathcal {F}}$

Eller med andre ord, givet en chiffertekst , skal du finde en sådan, at . Det er normalt en indsprøjtning i kryptografiske systemer, så dekryptering sker ved at beregne . ${\displaystyle (y_{1},\ldots ,y_{m})\in \mathbb {F} ^{m))$ ${\displaystyle (x_{1},\ldots ,x_{n})\in \mathbb {F} ^{n))$ ${\mathcal {P}}(x_{1},\ldots ,x_{n})=(y_{1},\ldots,y_{m})$ ${\mathcal {P}}$ ${\mathcal {P}}^{-1}(y_{1},\ldots ,y_{n})$

Digital signatur

For at underskrive et dokument , bruges en hash-funktion til at beregne værdien af . Så skal du beregne , og . Her betyder et, muligvis mange forbilleder til det centrale display . Siden eksisterer en sådan kortlægning. Således kan hver besked underskrives. [6] $d$ ${\mathcal {H}}:\{0,1\}^{*}\rightarrow \mathbb {F} ^{m}$ $\mathbf {h} ={\mathcal {H}}(d)\in \mathbb {F} ^{m}$
$\mathbf {x=} {\mathcal {S}}^{-1}(\mathbf {h} )$ $\mathbf {y=} {\mathcal {F}}^{-1}(\mathbf {x} )$ $\mathbf {z=} {\mathcal {T}}^{-1}(\mathbf {y} )$ ${\mathcal {F}}^{-1}(\mathbf {x} )$ $x$ ${\mathcal {F}}$ $n\geq m$

Verifikation af digital signatur

For at verificere ægtheden af et dokument skal du blot beregne og hash værdi fra dokumentet. Hvis , så accepteres underskriften, ellers afvises den. [6] $\mathbf {h^{,}=} {\mathcal {P}}(\mathbf {z} )$ $\mathbf {h} ={\mathcal {H}}(d)$ $\mathbf {h^{,}=h}$

Sikkerhed

Sikkerheden af multidimensionelle kryptografiske algoritmer er afhængig af følgende:

Kompleksiteten ved at løse kvadratiske multidimensionale ligningssystemer over endelige felter.

Givet et system af ikke-lineære polynomialligninger med variable . Vi er nødt til at finde sådanne værdier . ${\mathcal {P}}=(p^{1},\ldots ,p^{m})$ $m$ $x_{1},\ldots ,x_{n}$ $\mathbf {x_{1}} ,\ldots ,\mathbf {x_{n}}$ $p^{1}(\mathbf {x_{1}} ,\ldots ,\mathbf {x_{n}} )=\ldots =p^{m}(\mathbf {x_{1}} ,\ ldots ,\mathbf {x_{n}} )$

Løsning af et tilfældigt flerdimensionalt kvadratisk system over et begrænset felt er et NP-komplet problem i stærk forstand, eller blot NP-komplet . Kompleksiteten i at løse dette problem forhindrer en hacker i at udlede den private nøgle fra at kende den offentlige nøgle . [elleve]

Isomorfi af polynomier. [12]

Patarin og medforfattere viste, at vanskeligheden ved at løse dette problem er mindst den samme som ved grafisomorfi [13]

Fordele ved systemer bygget på multidimensionelle kryptografialgoritmer

Hastighed

Systemer bygget på multidimensionelle kryptografialgoritmer er hurtige nok, især til at signere dokumenter. Der er mange forudsætninger for, at de kan være hurtigere end klassiske kryptografiske programmer med offentlig nøgle som RSA . [14] [15]

Beskeden krav til computerressourcer

De matematiske operationer udført af multidimensionelle kredsløb er normalt meget enkle: de fleste kredsløb kræver kun addition og multiplikation over små finite felter. Derfor kræver multidimensionelle kredsløb beskedne computerressourcer, hvilket gør dem attraktive til brug på billige enheder såsom RFID-chips og smart cards uden behov for en kryptografisk coprocessor. En variant af C*-ordningen, kaldet SFLASH, er blevet foreslået af Europa-Kommissionen som en standard for signaturordninger på billige enheder. [16] [17]

SFLASH-systemet [1] bruger et endeligt felt og definerer en mapping . Notationen angiver, at ligningerne er fjernet fra funktionen , som er opbygget som følger: . Her og er to reversible lineære transformationer. Funktionen ser sådan ud :. Den offentlige nøgle består således af kvadratiske polynomier med variable koefficienter i . Hvert kvadratisk polynomium vil have koefficienter. Dette kræver KB hukommelse, hvis hver koefficient er gemt i en byte, den kan også reduceres til KB ved kun at bruge en bit for hver koefficient $\mathbb {F} ={\frac {Z_{2}[2]}{x^{7}+x+1))$ ${\mathcal {P^{-}}}:\mathbb {F} ^{67}\rightarrow \mathbb {F} ^{56}$ ${\displaystyle {\mathcal {P^{-)))))$ $elleve$ ${\mathcal {P}}$ ${\mathcal {P}}={\mathcal {L_{1}}}\circ {\mathcal {f}}\circ {\mathcal {L_{2}}}$ ${\displaystyle {\mathcal {L_{1))))$ ${\displaystyle {\mathcal {L_{2))))$ ${\displaystyle {\mathcal {f^{-)))))$ ${\mathcal {f^{-}}}(X)=X^{1+128^{33}}$ $56$ $67$ $\mathbb {F}$ $67*34+67+1$ $128.3$ $112.3$ $7$

Angreb på multidimensionelle kryptografisystemer

Re-linearisering

Relineriseringsangrebet er rettet mod at løse overbestemte systemer af multivariate kvadratiske ligninger. Lade være et system af andengradsligninger i variable . Hovedideen er at introducere en ny variabel for hver andengradsled . Således opnås et system af lineære ligninger, hvis antallet af ligninger er stort nok, kan Gauss-metoden bruges . Det er nødvendigt at sikre sig, om løsningen opnået på denne måde virkelig er løsningen af det kvadratiske system, forudsat at . For at løse et system af andengradsligninger i form af variable, kræver denne metode ligninger. Således giver re-lineariseringsangrebet dig mulighed for at reducere antallet af ukendte variabler i den private nøgle, dvs. reducere dens dimension. [atten] ${\mathcal {P}}$ $m$ $n$ $x_{1},\ldots ,x_{n}$ $x_{ij}$ $x_{i}x_{j}$ ${\displaystyle x_{ij}=x_{i}x_{j}\forall i,j\in \{1,\ldots ,n\))$ $n$ $m\geq {\frac {(n+1)(n+2)}{2}}-1$

XL-algoritme

Lade være mængden af alle polynomier i grad . $T_{D}^{n}$ $\mathbb {F} [x_{1},\ldots ,x_{n}]$ $\leq D$

XL-algoritme:
Input data : sæt af kvadratiske polynomier . Output : en vektor sådan at . ${\mathcal {F}}=\{f^{(1)},\ldots ,f^{(m)}\}$
$\mathbf {x=} (x_{1},\ldots ,x_{n})$ $f^{(1)}(\mathbf {x} )=\ldots =f^{(m)}(\mathbf {x} )$

for at gøre $i=1$ $n$
- Et heltal er fast . $D>2$
- Alle polynomier dannes: , hvor og . ${\displaystyle h\cdot f^{(j)))$ $h\in T_{D-2}^{n}$ $j=1,\ldots ,m$
- Du skal bruge Gauss-metoden til ligningerne opnået i det foregående trin for at generere én ligning, der kun indeholder . $x_{i}$
- Hvis der i det foregående trin blev opnået mindst et endimensionelt polynomium af , så skal det løses, for eksempel ved hjælp af Berlekamp-algoritmen . $x_{i}$
- Det er nødvendigt at forenkle ligningerne ved at ændre værdien af . ${\displaystyle f^{(1)},\ldots,f^{(m)))$ $x_{i}$
ende for $\mathbf {x=} (x_{1},\ldots ,x_{n})$
Vend tilbage $\mathbf {x=} (x_{1},\ldots ,x_{n})$

Et angreb ved hjælp af XL-algoritmen giver dig mulighed for at reducere dimensionen af den private nøgle ved at reducere systemet af ligninger til en invariant i en eller anden variabel. Ved hjælp af XL-algoritmen er det således muligt at angribe den offentlige nøgle. [fire]

Eksempler på multidimensionelle kryptosystemer

Trekantede kryptosystemer [19] .
Matsumoto-Imai-systemer [20] .
Minus-Plus generaliseringer af Matsumoto-Imai systemet [21] .
Skjulte feltligninger
Ubalanceret olie og eddike

Noter

↑ 1 2 3 4 5 JINTAI DING, DIETER SCHMIDT. Reuleaux trekant . MULTIVARIABLE PUBLIC-KEY CRYPTOSYSTEMER . Dato for adgang: 18. december 2017. Arkiveret fra originalen 9. august 2016.
↑ H. Ong, C.-P. Schnorr og A. Shamir Effektive signaturskemaer baseret på polynomieligninger. I CRYPTO, bind 196 af Lecture Notes in Computer Science // Springer: journal. — 1984, side 37-46.
↑ T. Matsumoto og H. Imai EP Offentlige kvadratiske polynomietupler til effektiv signaturverifikation og beskedkryptering. I EUROCRYPT, bind 330 af Lecture Notes in Computer Science // Springer: tidsskrift. — 1988, side 419-553
↑ 1 2 Albrecht Petzoldt. Valg og reduktion af nøglestørrelser til multivariat kryptografi . Hentet 21. december 2017. Arkiveret fra originalen 8. august 2017.
↑ 1 2 Jintai Ding, Jason Gower og Deiter Schmidt Multivariate Public Key Cryptosystems // Springer: journal. – 2006.
↑ 1 2 3 4 5 Jintai Ding og Bo-Yin Yang. Multivariat offentlig nøglekryptering . Hentet 4. december 2017. Arkiveret fra originalen 5. december 2017.
↑ NESSIE. Reuleaux trekant . NESSIE: Nye europæiske ordninger for signaturer, integritet og kryptering. NESSIE-projektet annoncerer det endelige valg af kryptoalgoritmer . Europa-Kommissionens program for informationssamfundsteknologier (IST-1999-12324). Hentet 3. december 2017. Arkiveret fra originalen 12. juni 2018.
↑ Indledning . Hentet 16. december 2017. Arkiveret fra originalen 14. december 2017. (ubestemt)
↑ Shuaiting Qiao, Wenbao Han, Yifa Li og Luyao Jiao. Konstruktion af udvidede multivariate offentlige nøglekryptosystemer . Dato for adgang: 21. december 2017. Arkiveret fra originalen 22. december 2017.
↑ Lih-Chung Wang, Bo-Yin Yang, Yu-Hua Hu og Feipei Lai. Et mellemfelt multivariat offentlig nøglekrypteringsskema . Hentet 18. december 2017. Arkiveret fra originalen 5. juli 2017.
↑ Jacques Patarin, Louis Goubin og Nicolas Courtois. Reuleaux trekant . Forbedrede algoritmer for isomorfismer af polynomier (1998) . Springer . Hentet 21. december 2017. Arkiveret fra originalen 16. juli 2017.
↑ Jacques Patarin. IHidden Field Equations (HFE) og Isomorphisms of Polynomials (IP): to nye familier af asymmetriske algoritmer . Hentet 21. december 2017. Arkiveret fra originalen 15. december 2017.
↑ Takanori Yasuda, Xavier Dahan, Yun-Ju Huang, Tsuyoshi Takagi og Kouichi Sakurai1. MQ udfordring . MQ Challenge: Hårdhedsvurdering af løsning af multivariate kvadratiske problemer . Hentet 3. december 2017. Arkiveret fra originalen 4. december 2017.
↑ I.-T. Chen, M.-S. Chen, T.-R. Chen, C.-M. Cheng, J. Ding, EL-H. Kuo, FY-S. Lee og B.-Y. Yang SSE implementering af multivariate PKC'er på moderne x86 CPU'er. I CHES, bind 5747 af Lecture Notes in Computer Science // Springer: journal. — 2009, side 33-48
↑ A. Bogdanov, T. Eisenbarth, A. Rupp og C. Wolf Tidsområdeoptimerede offentlige nøglemotorer: MQ-kryptosystemer som erstatning for elliptiske kurver? // Springer: CHES, bind 5154 af Lecture Notes in Computer Science. — 2008, side 45-61
↑ J. Patarin, N. Courtois og L. Goubin Flash, en hurtig multivariat signaturalgoritme // Springer: In CT-RSA, bind 2020 af Lecture Notes in Computer Science. — 2001, side 298–307
↑ B. Preneel NESSIE- projektet: Mod nye kryptografiske algoritmer // Swww.cryptonessie.org - 2000
↑ Raymond Heindl. Nye retninger i multivariat offentlig nøglekryptering . Dato for adgang: 18. december 2017. Arkiveret fra originalen 26. december 2017.
↑ Harriet Fell og Whitfield Diffie Analyse af en offentlig nøgletilgang baseret på polynomisk substitution. In Advances in cryptology—CRYPTO '85 (Santa Barbara, Californien) // Springer: tidsskrift. - 1986. - bind 218, side 340–349.
↑ T. Matsumoto og H. Imai Offentlige kvadratiske polynomietupler til effektiv signaturverifikation og meddelelseskryptering. I CG Guenther, redaktør, Advances in cryptology – EUROCRYPT '88 // Springer: tidsskrift. - 1988. - bind 330, side 419–453.
↑ Jacques Patarin, Louis Goubin og Nicolas Courtois C∗−+ og HM: variationer omkring to skemaer af T. Matsumoto og H. Imai. I K. Ohta og D. Pei, redaktører, ASIACRYPT'98 // Springer: tidsskrift. - 1998. - bind 1514, side 35–50.