Skjulte feltligninger

Hidden Field Equations (HFE) er en type offentlig nøgle kryptografisk system , der er en del af multidimensionel kryptografi . Også kendt som en-vejs HFE skjult indgangsfunktion . Dette system er en generalisering af Matsumoto-Imai-systemet og blev først introduceret af Jacques Patarin i 1996 på Eurocrypt-konferencen. [en]

Systemet med skjulte feltligninger er baseret på polynomier over endelige felter af forskellig størrelse for at maskere forholdet mellem den private nøgle og den offentlige nøgle. [2] $K$

HFE er faktisk en familie, der består af grundlæggende HFE'er og kombinationer af HFE-versioner. HFE-familien af kryptosystemer er baseret på vanskeligheden ved at finde løsninger på et system af multivariate kvadratiske ligninger (det såkaldte MQ-problem [3] ), fordi det bruger partielle affine transformationer til at skjule feltudvidelse og partielle polynomier. Skjulte feltligninger er også blevet brugt til at bygge digitale signatursystemer , såsom Quartz og Sflash . [2] [1]

Hovedidé [1]

Funktion $f$

Lad være en finit dimension felt med karakteristik (normalt, men ikke nødvendigvis ). $K$ $q$ $s$ $p=q=2$
Lad være en forlængelse af graden . $L_{N}$ $K$ $N$
Lad , og vær elementer af . ${\displaystyle \beta _{ij))$ $\alpha_i$ $\mu_{0}$ $L_{N}$
Lad , og være heltal. ${\displaystyle \theta _{ij))$ ${\displaystyle \varphi _{ij))$ $\xi _{i}$
Lad endelig være en funktion sådan, at: $f$ L N ↦ L N {\displaystyle L_{N}\mapsto L_{N}} $L_{N}\mapsto L_{N}$ f : x ↦ ∑ jeg , j β jeg j x q θ jeg j + q φ jeg j + ∑ jeg α jeg x q ξ jeg + μ 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))$

Så er et polynomium i . $f$ $x$

Lad nu være grundlaget . Så er udtrykket i grundlaget : $B$ $L_{N}$ $f$ $B$

f ( x en , . . . , x N ) = ( s en ( x en , . . . , x N ) , . . . , s N ( x en , . . . , 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}))$ hvor er polynomier i variable af grad 2 . $p_{1},...,p_{N}$ $N$ $N$

Dette er sandt, da for ethvert heltal , er en lineær funktion af . Polynomier kan findes ved at vælge en "repræsentation" . En sådan "repræsentation" gives normalt ved at vælge et irreducerbart gradspolynomium frem for , så vi kan angive ved hjælp af . I dette tilfælde er det muligt at finde polynomier . $\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 skal bemærkes, at det ikke altid er en permutation . Grundlaget for

HFE- algoritmen er dog følgende teorem.

f

L_{N}

Sætning : Lad være et begrænset felt, og med og "ikke for stort" (for eksempel, og ). $L_{N}$ $\mid {L_{N}}\mid =q^{n}$ $q$ $n$ $q\leq {64}$ $n\leq {1024}$ Lade være et givet polynomium i over et felt med graden "ikke for stor" (for eksempel ). $f(x)$ $x$ $L_{N}$ $d$ $d\leq {1024}$ Lad være en del af feltet . $-en$ $L_{N}$ Så kan du altid (på en computer) finde alle ligningens rødder . $f(x)=a$

Kryptering [1]

Præsentation af meddelelsen $M$

I feltet antallet af offentlige elementer . $K$ $q=p^{m}$

Hver meddelelse er repræsenteret af en værdi , hvor er en streng af feltelementer . Således, hvis , så er hver meddelelse repræsenteret af bits. Desuden antages det nogle gange, at der er placeret en vis redundans i meddelelsesrepræsentationen . $M$ $x$ $x$ $n$ $K$ $p=2$ $nm$ $x$ $r$

Kryptering $x$

Hemmelig del

Grad feltudvidelse . _ $L_{n}$ $K$ $n$
Funktion : , som blev beskrevet ovenfor, med en "ikke for stor" grad på . $f$ ${L_{n}}\mapsto {L_{n}}$ $d$
To affine transformationer og : $S$ $T$ ${K^{n}}\mapsto {K^{n}}$

Offentlig del

Felt med elementer og længde . $K$ $q=p^{m}$ $n$
$n$ polynomier af dimension over feltet . $(p_{1},...,p_{n})$ $n$ $K$
En måde at tilføje redundans til beskeder (det vil sige en måde at komme fra ). $r$ $x$ $M$

Hovedideen med at konstruere en familie af systemer af skjulte feltligninger som et multidimensionelt kryptosystem er at konstruere en hemmelig nøgle, der starter fra et polynomium med et ukendt over et begrænset felt .

[2] Dette polynomium kan inverteres over , det vil sige, at enhver løsning til ligningen kan findes, hvis den findes. Den hemmelige transformation, såvel som dekrypteringen og/eller signaturen, er baseret på denne inversion.

P

x

L_{N}

L_{N}

P(x)=y

Som nævnt ovenfor kan det identificeres ved hjælp af et ligningssystem ved hjælp af en fast basis. For at opbygge et kryptosystem skal et polynomium transformeres på en sådan måde, at offentlig information skjuler den oprindelige struktur og forhindrer inversion. Dette opnås ved at betragte endelige felter som et

vektorrum over og vælge to lineære affine transformationer og . Tripletten danner den private nøgle. Det private polynomium er defineret på . Den offentlige nøgle er et polynomium . [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 → hemmelighed : S x " → hemmelighed : P y " → hemmelighed : T y {\displaystyle M{\overset {+r}{\to }}x{\overset {{\text{hemmelig}}:S}{\to }}x'{\overset {{\text{hemmelig}}: P}{\to }}y'{\overset {{\text{hemmelig}}:T}{\to }}y}

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

HFE-udvidelser

Skjulte feltligninger har fire grundlæggende modifikationer: + , - , v og f , og de kan kombineres på forskellige måder. Grundprincippet er som følger [2] :

"+" modifikationen består af en lineær kombination af offentlige ligninger med nogle tilfældige ligninger.
Ændring "-" dukkede op takket være Adi-Shamir og fjerner redundans " " fra offentlige ligninger. $r$
"f" -modifikationen består i at rette nogle offentlige nøgle-inputvariabler. $f$
Modifikation "v" er defineret som en kompleks konstruktion, således at den inverse funktion kun kan findes, hvis nogle v -variable er faste. Denne idé tilhører Jacques Patarin.

Angreb på HFE-kryptosystemer

De to mest berømte angreb på systemet med skjulte feltligninger [4] er:

Afledning af privat nøgle (Shamir-Kipnis): Nøglepunktet i dette angreb er at genskabe den private nøgle som sparsomme endimensionelle polynomier over udvidelsesfeltet . Angrebet virker kun for det grundlæggende system af skjulte feltligninger og virker ikke for alle dets variationer. $L_{n}$
Gröbner - algoritmeangreb (udviklet af Jean-Charles Fougères ): Ideen bag angrebet er at bruge en hurtig algoritme til at beregne Gröbner-grundlaget for et system af polynomielle ligninger . Fougeres hackede HFE i HFE Challenge 1 på 96 timer i 2002. I 2003 arbejdede Fougeres sammen med Zhu for at sikre HFE.

Noter

↑ 1 2 3 4 Jacques Patarin Hidden Field Equations (HFE) og Isomorphic Polynomial (IP): to nye familier af asymmetrisk algoritme . Dato for adgang: 15. december 2017. Arkiveret fra originalen 2. februar 2017. (ubestemt)
↑ 1 2 3 4 5 Christopher Wolf og Bart Preneel, Asymmetric Cryptography: Hidden Field Equations . Hentet 8. december 2017. Arkiveret fra originalen 10. august 2017. (ubestemt)
↑ Enrico Thomae og Christopher Wolf, Solving Systems of Multivariate Quadratic Equations over Finite Fields or: From Relinearization to MutantXL . Hentet 8. december 2017. Arkiveret fra originalen 10. august 2017. (ubestemt)
↑ Nicolas T. Courtois, "Sikkerheden ved skjulte feltligninger" . (ubestemt)

Links

Offentlig nøgle kryptosystemer

Algoritmer

Faktorisering af heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalingsmodtager Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritme	BLS Cramer - Shoup Diffie-Hellman protokol DSA ECDH Kurve25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypteret nøgleudveksling Ordning af ElGamal underskriftsordning MQV Schnorr ordning SPEKE SRP STS
Kryptografi på gitter	NTRUEncrypt NTRUSign Læringsbaseret nøgleudveksling med fejl Signaturbaseret træning med fejl i ringen LYKKELIGHED Nyt håb
Andet	AE CEILIDH EPOC Skjulte feltligninger IES Lamports underskrift McEliece Merkle-Hellman rygsæk kryptosystem Naccache-Stern rygsæk kryptosystem Tre trins protokol XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Post kvantekryptering

Emner

Elektronisk signatur
OAEP
Fingeraftryk
PKI
web af tillid
Nøglestørrelse
Identitetsbaseret kryptografi
Postkvantekryptografi
OpenPGP-kort