Flerdimensionell kryptografi

Multidimensionell kryptografi eller multivariat offentlig nyckelkryptografi är en allmän term som beskriver asymmetriska kryptografiska scheman byggda på lösningar av ekvationer baserade på multivariata polynom över ett ändligt fält . $\mathbb {F}$

Säkerheten för flerdimensionell kryptografi är baserad på antagandet att lösa ett system av kvadratiska polynom över ett ändligt fält i allmänhet är NP-komplett i stark mening, eller helt enkelt NP-komplett . Det är därför dessa system ofta anses vara bra kandidater för post-kvantkryptografi . [ett] $\mathbb {F}$

Skapande historia

Det första försöket att konstruera ett kryptografiskt schema baserat på flervariata kvadratiska polynom gjordes av Ong, Schnor och Shamir [2] , där de föreslog ett signaturschema baserat på komplexiteten i att lösa ekvationen: ;
$s_{1}^{2}+k*s_{2}^{2}=m(\mod n)$

Men säkerheten för detta schema är fortfarande baserat på komplexiteten i faktoriseringen , och därför är detta schema sårbart för attacker med kvantdatorer . Utvecklingen av flerdimensionella kryptografiska system i modern mening började 1988 med C*-schemat i Matsumoto-Imai-systemet [3] . $n=p*q$

Matsumoto och Imai använde en bijektiv mappning över en gradfältförlängning från formuläret: . För att säkerställa att denna transformation är reversibel är det nödvändigt att välja på ett sådant sätt att . Ekvationen ovan ger, på grund av den kanoniska isomorfismen mellan och vektorrummet, ett system av flerdimensionella kvadratiska ekvationer på fältet , detta förklaras av Frobenius-endomorfismen . För att dölja strukturen använde Matsumoto och Imai två affina transformationer och . Så de presenterade den publika nyckeln 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}}$

Denna design kallas bipolär. Det är fortfarande standardmetoden för att bygga flerdimensionella kryptosystem med publik nyckel. [fyra]

Flerdimensionell kryptografi har varit ett aktivt forskningsområde, men det finns fortfarande en brist på flerdimensionella scheman såsom: nyckelutbytesprotokoll och signaturscheman med speciella egenskaper [5] .

Relevans och utvecklingsmöjligheter

De flesta offentliga nyckelkryptosystem som används i praktiken är baserade på heltalsfaktorisering eller diskreta logaritmer (i finita fält eller elliptiska kurvor ). [6] Dessa system har dock två nackdelar.

Framsteg inom talteorin har lett till en minskning av effektiviteten i beräkningar, så parameterstorlekarna måste ökas i enlighet med säkerhetskraven. [ett]
Om tillräckligt stora kvantdatorer kan byggas kommer Shors algoritm att göra nuvarande system helt osäkra. Därför är det viktigt att leta efter alternativa system som främjar effektiv och säker kommunikation. [ett]

Flerdimensionell krypteringsnyckel är ett möjligt alternativ till nuvarande implementeringar av krypteringsalgoritmer för offentliga nyckel. År 2003 blev Sflash- signatursystemet det slutliga valet av NESSIE-projektet (New European Signature, Integrity and Encryption Schemes) [7] . Den första boken om flerdimensionell kryptografi skriven av Ding, Gower och Schmidt publicerades 2006 [5] . Det finns också en internationell workshop, PQCrypto, som fokuserar på post-kvantkryptering, inklusive flerdimensionell kryptografi. [åtta]

Grundläggande operationsalgoritm

Huvudidén med standardkonstruktionen av flerdimensionell kryptografi är valet av ett system (central transformation) av flerdimensionella kvadratiska polynom i variabler som lätt kan inverteras. [9] Därefter väljs två slumpmässiga affina reversibla transformationer för att dölja strukturen för den centrala transformationen i den publika nyckeln. [tio] ${\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 publika nyckeln för ett kryptosystem är en sammansatt kvadratisk transformation , som antas vara osannolikt att skilja sig från en slumpmässig och därför svår att invertera. ${\mathcal {P}}={\mathcal {S}}\circ {\mathcal {F}}\circ {\mathcal {T}}$

Den privata nyckeln består av , , och därför tillåter detta . $\mathcal{S}$ ${\mathcal {F}}$ $\mathcal{T}$ ${\mathcal {P}}$

Bygga en offentlig nyckel

Låt vara ett ändligt fält. Den publika nyckeln för flerdimensionella kryptografialgoritmer är en polynomavbildning $\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}}

; där är ett andragradspolynom .

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

För kryptering och dekryptering antar vi att för en elektronisk signatur : . [ett] $m\geq n$ $m\leq n$

Kryptering

För att kryptera ett meddelande eller måste du beräkna . Chiffertexten för det mottagna meddelandet är 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

För att dekryptera chiffertexten som beräknas rekursivt : , och . ${\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}$ är chiffertextens klartext . Eftersom , mappningen från till , och därmed den resulterande klartexten, är unika. [6] $\mathbf {h}$ $m\geq n$ $\mathbf {z}$ ${\mathcal {F}}$

Eller med andra ord, givet en chiffertext måste du hitta en sådan som . Det är vanligtvis en injektion i kryptografiska system, så dekryptering görs genom att beräkna . ${\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

För att signera ett dokument används en hashfunktion för att beräkna värdet på . Sedan måste du beräkna , och . Här betyder en, möjligen många förbilder för den centrala displayen . Sedan finns en sådan mappning. Således kan varje meddelande signeras. [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$

Verifiering av digital signatur

För att verifiera ett dokuments äkthet behöver du bara beräkna och hasha värdet från dokumentet. Om , då accepteras signaturen, annars avvisas den. [6] $\mathbf {h^{,}=} {\mathcal {P}}(\mathbf {z} )$ $\mathbf {h} ={\mathcal {H}}(d)$ $\mathbf {h^{,}=h}$

Säkerhet

Säkerheten för flerdimensionella kryptografialgoritmer bygger på följande:

Komplexiteten i att lösa kvadratiska flerdimensionella ekvationssystem över ändliga fält.

Givet ett system av ickelinjära polynomekvationer med variabler . Vi måste hitta sådana värden . ${\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}} )$

Att lösa ett slumpmässigt flerdimensionellt kvadratiskt system över ett ändligt fält är ett NP-komplett problem i stark mening, eller helt enkelt NP-komplett . Komplexiteten i att lösa detta problem hindrar en angripare från att härleda den privata nyckeln från att känna till den offentliga nyckeln . [elva]

Isomorfism av polynom. [12]

Patarin och medförfattare visade att svårigheten att lösa detta problem är åtminstone densamma som för grafisomorfism [13]

Fördelar med system byggda på flerdimensionella kryptografialgoritmer

Fart

System byggda på flerdimensionella kryptografialgoritmer är tillräckligt snabba, särskilt för att signera dokument. Det finns många förutsättningar för att de kan vara snabbare än klassiska kryptografiska system med offentlig nyckel som RSA . [14] [15]

Måttliga krav på datorresurser

De matematiska operationerna som utförs av flerdimensionella kretsar är vanligtvis mycket enkla: de flesta kretsar kräver bara addition och multiplikation över små finita fält. Därför kräver flerdimensionella kretsar blygsamma beräkningsresurser, vilket gör dem attraktiva för användning på lågkostnadsenheter som RFID-chips och smarta kort utan behov av en kryptografisk samprocessor. En variant av C*-schemat, kallat SFLASH, har föreslagits av Europeiska kommissionen som en standard för signaturscheman på lågkostnadsenheter. [16] [17]

SFLASH-systemet [1] använder ett sista fält och definierar en mappning . Notationen anger att ekvationerna har tagits bort från funktionen , som är konstruerad enligt följande: . Här och är två reversibla linjära transformationer. Funktionen ser ut som: . Den publika nyckeln består alltså av kvadratiska polynom med variabla koefficienter i . Varje kvadratiskt polynom kommer att ha koefficienter. Detta kräver KB minne om varje koefficient är lagrad i en byte, den kan också reduceras till KB genom att bara använda en bit för varje koefficient $\mathbb {F} ={\frac {Z_{2}[2]}{x^{7}+x+1))$ ${\mathcal {P^{-}}}:\mathbb {F} ^{67}\rightarrow \mathbb {F} ^{56}$ ${\displaystyle {\mathcal {P^{-)))))$ $elva$ ${\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$

Attacker på flerdimensionella kryptografisystem

Omlinjärisering

Relineriseringsattacken syftar till att lösa överbestämda system av multivariata kvadratiska ekvationer. Låta vara ett system av andragradsekvationer i variabler . Huvudtanken är att införa en ny variabel för varje kvadratisk term . Således erhålls ett system av linjära ekvationer, om antalet ekvationer är tillräckligt stort kan Gaussmetoden användas . Det är nödvändigt att se till om lösningen som erhålls på detta sätt verkligen är lösningen av det kvadratiska systemet, förutsatt att . För att lösa ett system av andragradsekvationer i termer av variabler kräver denna metod ekvationer. Således låter återlinjäriseringsattacken dig minska antalet okända variabler i den privata nyckeln, d.v.s. minska dess dimension. [arton] ${\mathcal {P}}$ $m$ $n$ $x_{1},\ldots ,x_{n}$ $x_{ij}$ ${\displaystyle 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-algoritm

Låta vara mängden av alla polynom i grad . $T_{D}^{n}$ $\mathbb {F} [x_{1},\ldots ,x_{n}]$ $\leq D$

XL-algoritm:
Indata : uppsättning kvadratiska polynom . Utdata : en vektor sådan att . ${\mathcal {F}}=\{f^{(1)},\ldots ,f^{(m)}\}$
$\mathbf {x=} (x_{1},\ldots ,x_{n})$ $f^{(1)}(\mathbf {x} )=\ldots =f^{(m)}(\mathbf {x} )$

för att göra $i=1$ $n$
- Ett heltal är fixerat . $D>2$
- Alla polynom bildas: , var och . ${\displaystyle h\cdot f^{(j)))$ ${\displaystyle h\in T_{D-2}^{n))$ $j=1,\ldots ,m$
- Du måste använda Gauss-metoden för ekvationerna som erhölls i föregående steg för att generera en ekvation som endast innehåller . $x_{i}$
- Om i föregående steg erhölls minst ett endimensionellt polynom av , måste det lösas, till exempel med Berlekamp-algoritmen . $x_{i}$
- Det är nödvändigt att förenkla ekvationerna genom att ändra värdet på . ${\displaystyle f^{(1)},\ldots ,f^{(m)))$ $x_{i}$
slut för $\mathbf {x=} (x_{1},\ldots ,x_{n})$
lämna tillbaka $\mathbf {x=} (x_{1},\ldots ,x_{n})$

En attack som använder XL-algoritmen låter dig minska dimensionen på den privata nyckeln genom att reducera ekvationssystemet till en invariant i någon variabel. Med hjälp av XL-algoritmen är det alltså möjligt att attackera den publika nyckeln. [fyra]

Exempel på flerdimensionella kryptosystem

Triangulära kryptosystem [19] .
Matsumoto-Imai-system [20] .
Minus-Plus generaliseringar av Matsumoto-Imai-systemet [21] .
Dolda fältekvationer
Obalanserad olja och vinäger

Anteckningar

↑ 1 2 3 4 5 JINTAI DING, DIETER SCHMIDT. Reuleaux Triangel . MULTIVARIABLA PUBLIC-KEY KRYPTOSYSTEM . Datum för åtkomst: 18 december 2017. Arkiverad från originalet den 9 augusti 2016.
↑ H. Ong, C.-P. Schnorr och A. Shamir Effektiva signaturscheman baserade på polynomekvationer. I CRYPTO, volym 196 av Lecture Notes in Computer Science // Springer: journal. — 1984, sid 37–46.
↑ T. Matsumoto och H. Imai EP Offentliga kvadratiska polynom-tuplar för effektiv signaturverifiering och meddelandekryptering. I EUROCRYPT, volym 330 av Lecture Notes in Computer Science // Springer: journal. — 1988, sid 419–553
↑ 1 2 Albrecht Petzoldt. Välja och minska nyckelstorlekar för multivariat kryptografi . Hämtad 21 december 2017. Arkiverad från originalet 8 augusti 2017.
↑ 1 2 Jintai Ding, Jason Gower och Deiter Schmidt Multivariate Public Key Cryptosystems // Springer: journal. – 2006.
↑ 1 2 3 4 5 Jintai Ding och Bo-Yin Yang. Multivariat offentlig nyckelkryptering . Hämtad 4 december 2017. Arkiverad från originalet 5 december 2017.
↑ NESSIE. Reuleaux Triangel . NESSIE: Nya europeiska system för signaturer, integritet och kryptering. NESSIE-projektet tillkännager slutgiltigt urval av kryptoalgoritmer . Europeiska kommissionens program för informationssamhällets teknologi (IST-1999-12324). Hämtad 3 december 2017. Arkiverad från originalet 12 juni 2018.
↑ Inledning . Hämtad 16 december 2017. Arkiverad från originalet 14 december 2017. (obestämd)
↑ Shuaiting Qiao, Wenbao Han, Yifa Li och Luyao Jiao. Konstruktion av utökade multivariata publika nyckelkrypteringssystem . Datum för åtkomst: 21 december 2017. Arkiverad från originalet 22 december 2017.
↑ Lih-Chung Wang, Bo-Yin Yang, Yu-Hua Hu och Feipei Lai. Ett medelstort multivariat krypteringsschema för offentlig nyckel . Hämtad 18 december 2017. Arkiverad från originalet 5 juli 2017.
↑ Jacques Patarin, Louis Goubin och Nicolas Courtois. Reuleaux Triangel . Förbättrade algoritmer för isomorfismer av polynomer (1998) . Springer . Hämtad 21 december 2017. Arkiverad från originalet 16 juli 2017.
↑ Jacques Patarin. IHidden Field Equations (HFE) och Isomorphisms of Polynomials (IP): två nya familjer av asymmetriska algoritmer . Hämtad 21 december 2017. Arkiverad från originalet 15 december 2017.
↑ Takanori Yasuda, Xavier Dahan, Yun-Ju Huang, Tsuyoshi Takagi och Kouichi Sakurai1. MQ utmaning . MQ Challenge: Hårdhetsutvärdering för att lösa flervariata kvadratiska problem . Hämtad 3 december 2017. Arkiverad från originalet 4 december 2017.
↑ I.-T. Chen, M.-S. Chen, T.-R. Chen, C.-M. Cheng, J. Ding, EL-H. Kuo, FY-S. Lee och B.-Y. Yang SSE-implementering av multivariata PKC:er på moderna x86-processorer. I CHES, volym 5747 av Lecture Notes in Computer Science // Springer: journal. — 2009, sidorna 33–48
↑ A. Bogdanov, T. Eisenbarth, A. Rupp och C. Wolf Tidsområdesoptimerade publika nyckelmotorer: MQ-kryptosystem som ersättning för elliptiska kurvor? // Springer : CHES, volym 5154 av Lecture Notes in Computer Science. — 2008, sidorna 45–61
↑ J. Patarin, N. Courtois och L. Goubin Flash, en snabb multivariat signaturalgoritm // Springer: In CT-RSA, volym 2020 av Lecture Notes in Computer Science. — 2001, sid 298–307
↑ B. Preneel NESSIE-projektet: Mot nya kryptografiska algoritmer // Swww.cryptonessie.org - 2000
↑ Raymond Heindl. Nya anvisningar i multivariat offentlig nyckelkryptering . Datum för åtkomst: 18 december 2017. Arkiverad från originalet 26 december 2017.
↑ Harriet Fell och Whitfield Diffie Analys av ett tillvägagångssätt med offentlig nyckel baserat på polynomsubstitution. In Advances in cryptology—CRYPTO '85 (Santa Barbara, Kalifornien) // Springer: journal. - 1986. - volym 218, sid 340–349.
↑ T. Matsumoto och H. Imai Offentliga kvadratiska polynom-tuplar för effektiv signaturverifiering och meddelandekryptering. I CG Guenther, redaktör, Advances in cryptology – EUROCRYPT '88 // Springer : journal. - 1988. - volym 330, sid 419–453.
↑ Jacques Patarin, Louis Goubin och Nicolas Courtois C∗−+ och HM: variationer kring två scheman av T. Matsumoto och H. Imai. I K. Ohta och D. Pei, redaktörer, ASIACRYPT'98 // Springer: journal. - 1998. - volym 1514, sid 35–50.

Länkar

[1] Multivariat offentlig nyckelkryptering