Dolda fältekvationer

Hidden Field Equations (HFE) är en typ av offentlig nyckel kryptografiskt system som är en del av flerdimensionell kryptografi . Även känd som envägs HFE - dold ingångsfunktion. Detta system är en generalisering av Matsumoto-Imai-systemet och introducerades först av Jacques Patarin 1996 vid Eurocrypt-konferensen. [ett]

Systemet med dolda fältekvationer är baserat på polynom över ändliga fält av olika storlekar för att maskera förhållandet mellan den privata nyckeln och den publika nyckeln. [2] $K$

HFE är egentligen en familj som består av grundläggande HFE och kombinationer av HFE-versioner. HFE-familjen av kryptosystem är baserad på svårigheten att hitta lösningar på ett system av multivariata kvadratiska ekvationer (det så kallade MQ-problemet [3] ), eftersom den använder partiella affina transformationer för att dölja fältexpansion och partiella polynom. Dolda fältekvationer har också använts för att bygga digitala signatursystem , såsom Quartz och Sflash . [2] [1]

Huvudidé [1]

Funktion $f$

Låta vara ett fält med ändlig dimension med karakteristik (vanligtvis, men inte nödvändigtvis ). $K$ $q$ $sid$ $p=q=2$
Låt vara en förlängning av examen . $L_{N}$ $K$ $N$
Låt , och vara delar av . ${\displaystyle \beta _{ij))$ $\alpha_i$ $\mu_{0}$ $L_{N}$
Låt , och vara heltal. ${\displaystyle \theta _{ij))$ ${\displaystyle \varphi _{ij))$ $\xi _{i}$
Låt slutligen vara en funktion sådan att: $f$ L N ↦ L N {\displaystyle L_{N}\mapsto L_{N}} $L_{N}\mapsto L_{N}$ f : x ↦ ∑ i , j β i j x q θ i j + q φ i j + ∑ i α i x q ξ i + μ 0 {\displaystyle f:x\mapsto \sum _{i,j}{\beta _{ij}x^{q^{\theta _{ij}}+q^{\varphi _{ij}}}}+ \sum _{i}{\alpha _{i}x^{q^{\xi _{i))))+\mu _{0)) ${\displaystyle f:x\mapsto \sum _{i,j}{\beta _{ij}x^{q^{\theta _{ij}}+q^{\varphi _{ij}}}}+ \sum _{i}{\alpha _{i}x^{q^{\xi _{i))))+\mu _{0))$

Då är ett polynom i . $f$ $x$

Låt nu vara grunden . Då är uttrycket i grunden : $B$ $L_{N}$ $f$ $B$

f ( x ett , . . . , x N ) = ( sid ett ( x ett , . . . , x N ) , . . . , sid N ( x ett , . . . , x N ) ) {\displaystyle f(x_{1},...,x_{N})=(p_{1}(x_{1},...,x_{N}),...,p_{N}( x_{1},...,x_{N}))} $f(x_{1},...,x_{N})=(p_{1}(x_{1},...,x_{N}),...,p_{N}( x_{1},...,x_{N}))$ där finns polynom i variabler av grad 2 . $p_{1},...,p_{N}$ $N$ $N$

Detta är sant, eftersom för alla heltal , är en linjär funktion av . Polynom kan hittas genom att välja en "representation" . En sådan "representation" ges vanligtvis genom att välja ett irreducerbart gradpolynom framför , så vi kan specificera med . I det här fallet är det möjligt att hitta polynom . $\lambda$ $x\mapsto x^{q^{\lambda ))$ $L_{N}\mapsto L_{N}$ $p_{1},...,p_{N}$ $L_{N}$ $i_{N}(X)$ $N$ $K$ $L_{N}$ $K[X]/(i_{N}(X))$ $p_{1},...,p_{N}$

Inversion $f$

Det bör noteras att det inte alltid är en permutation . Grunden för

HFE- algoritmen är dock följande teorem.

f

L_{N}

Sats : Låta vara ett ändligt fält, och med och "inte för stort" (till exempel och ). $L_{N}$ $\mid {L_{N}}\mid =q^{n}$ $q$ $n$ $q\leq {64}$ $n\leq {1024}$ Låta vara ett givet polynom i över ett fält med graden "inte för stor" (till exempel ). $f(x)$ $x$ $L_{N}$ $d$ $d\leq {1024}$ Låt vara en del av fältet . $a$ $L_{N}$ Sedan kan du alltid (på en dator) hitta alla rötter till ekvationen . $f(x)=a$

Kryptering [1]

Presentation av meddelandet $M$

I fältet antal offentliga element . $K$ $q=p^{m}$

Varje meddelande representeras av ett värde , där är en sträng av fältelement . Således, om , representeras varje meddelande av bitar. Dessutom antas det ibland att viss redundans har placerats i meddelanderepresentationen . $M$ $x$ $x$ $n$ $K$ $p=2$ $nm$ $x$ $r$

Kryptering $x$

Hemlig del

Examensfältförlängning . _ _ $L_{n}$ $K$ $n$
Funktion : , som beskrevs ovan, med en "inte för stor" grad av . $f$ ${L_{n}}\mapsto {L_{n}}$ $d$
Två affina transformationer och : $S$ $T$ ${K^{n}}\mapsto {K^{n}}$

Offentlig del

Fält med element och längd . $K$ $q=p^{m}$ $n$
$n$ polynom av dimension över fältet . $(p_{1},...,p_{n})$ $n$ $K$
Ett sätt att lägga till redundans till meddelanden (det vill säga ett sätt att komma från ). $r$ $x$ $M$

Huvudidén med att konstruera en familj av system av dolda fältekvationer som ett flerdimensionellt kryptosystem är att konstruera en hemlig nyckel som börjar från ett polynom med ett okänd över något ändligt fält .

[2] Detta polynom kan inverteras över , det vill säga vilken lösning som helst på ekvationen kan hittas om den finns. Den hemliga transformationen, såväl som dekrypteringen och/eller signaturen, är baserad på denna inversion.

P

x

L_{N}

L_{N}

P(x)=y

Som nämnts ovan kan den identifieras av ett ekvationssystem som använder en fast bas. För att bygga ett kryptosystem måste ett polynom transformeras på ett sådant sätt att offentlig information döljer den ursprungliga strukturen och förhindrar inversion. Detta uppnås genom att betrakta ändliga fält som ett

vektorrum över och välja två linjära affina transformationer och . Tripletten bildar den privata nyckeln. Det privata polynomet definieras på . Den publika nyckeln är ett polynom . [2]

P

n

(p_{1},...,p_{n})

(p_{1},...,p_{n})

\mathbb {L} _{n}

\mathbb {K}

S

T

(S,P,T)

P

\mathbb {L} _{n}

(p_{1},...,p_{n})

M → + r x → hemlighet : S x " → hemlighet : P y " → hemlighet : T y {\displaystyle M{\overset {+r}{\to }}x{\overset {{\text{hemlig}}:S}{\to }}x'{\overset {{\text{hemlig}}: P}{\to }}y'{\overset {{\text{hemlig}}:T}{\to }}y}

M{\overset {+r}{\to }}x{\overset {{\text{hemlig}}:S}{\to }}x'{\overset {{\text{hemlig}}: P}{\to }}y'{\overset {{\text{hemlig}}:T}{\to }}y

HFE-tillägg

Dolda fältekvationer har fyra grundläggande modifikationer: + , - , v och f , och de kan kombineras på olika sätt. Grundprincipen är följande [2] :

"+"- modifikationen består av en linjär kombination av offentliga ekvationer med några slumpmässiga ekvationer.
Modifiering "-" dök upp tack vare Adi-Shamir och tar bort redundans " " från offentliga ekvationer. $r$
"f" -modifieringen består av att fixa några indatavariabler för publik nyckel. $f$
Modifiering "v" definieras som en komplex konstruktion så att den inversa funktionen endast kan hittas om några v -variabler är fixerade. Denna idé tillhör Jacques Patarin.

Attacker på HFE-kryptosystem

De två mest kända attackerna på systemet med dolda fältekvationer [4] är:

Härledning av privat nyckel (Shamir-Kipnis): Nyckelpunkten med denna attack är att återställa den privata nyckeln som glesa endimensionella polynom över förlängningsfältet . Attacken fungerar bara för det grundläggande systemet med dolda fältekvationer och fungerar inte för alla dess variationer. $L_{n}$
Gröbner - algoritmattack (utvecklad av Jean-Charles Fougères ): Tanken bakom attacken är att använda en snabb algoritm för att beräkna Gröbner-basen för ett system av polynomekvationer . Fougeres hackade HFE i HFE Challenge 1 på 96 timmar 2002. 2003 arbetade Fougeres med Zhu för att säkra HFE.

Anteckningar

↑ 1 2 3 4 Jacques Patarin Hidden Field Equations (HFE) och Isomorphic Polynomial (IP): två nya familjer av asymmetrisk algoritm . Tillträdesdatum: 15 december 2017. Arkiverad från originalet 2 februari 2017. (obestämd)
↑ 1 2 3 4 5 Christopher Wolf och Bart Preneel, asymmetrisk kryptografi: dolda fältekvationer . Hämtad 8 december 2017. Arkiverad från originalet 10 augusti 2017. (obestämd)
↑ Enrico Thomae och Christopher Wolf, Solving Systems of Multivariate Quadratic Equations over Finita Fields or: From Relinearization to MutantXL . Hämtad 8 december 2017. Arkiverad från originalet 10 augusti 2017. (obestämd)
↑ Nicolas T. Courtois, "Säkerheten för dolda fältekvationer" . (obestämd)

Länkar

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort