Ecuații de câmp ascunse

Hidden Field Equations (HFE) este un tip de sistem criptografic cu cheie publică care face parte din criptografia multidimensională . Cunoscută și ca funcție de intrare ascunsă HFE unidirecțională. Acest sistem este o generalizare a sistemului Matsumoto-Imai și a fost introdus pentru prima dată de Jacques Patarin în 1996 la conferința Eurocrypt. [unu]

Sistemul de ecuații de câmp ascuns se bazează pe polinoame peste câmpuri finite de diferite dimensiuni pentru a masca relația dintre cheia privată și cheia publică. [2] $K$

HFE este de fapt o familie care constă din HFE de bază și combinații de versiuni HFE. Familia de criptosisteme HFE se bazează pe dificultatea de a găsi soluții la un sistem de ecuații pătratice multivariate (așa-numita problemă MQ [3] ), deoarece folosește transformări afine parțiale pentru a ascunde expansiunea câmpului și polinoamele parțiale. Ecuațiile de câmp ascunse au fost, de asemenea, folosite pentru a construi scheme de semnătură digitală , cum ar fi Quartz și Sflash . [2] [1]

Ideea principală [1]

Funcția $f$

Fie un câmp de dimensiune finită cu caracteristică (de obicei, dar nu neapărat ). $K$ $q$ $p$ $p=q=2$
Fie o extensie a gradului . $L_{N}$ $K$ $N$
Fie , și să fie elemente ale . $\beta _{ij)$ $\alpha_i$ $\mu_{0}$ $L_{N}$
Fie , și să fie numere întregi. $\theta _{ij}$ $\varphi _{ij}$ $\xi _{i}$
În cele din urmă, să fie o funcție astfel încât: $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))$

Atunci este un polinom în . $f$ $x$

Să fie acum baza . Atunci expresia din bază este: $B$ $L_{N}$ $f$ $B$

f ( X unu , . . . , X N ) = ( p unu ( X unu , . . . , X N ) , . . . , p N ( X unu , . . . , 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}))$ unde sunt polinoame în variabile de gradul 2 . $p_{1},...,p_{N}$ $N$ $N$

Acest lucru este adevărat, deoarece pentru orice număr întreg , este o funcție liniară a . Polinoamele pot fi găsite prin alegerea unei „reprezentări” . O astfel de „reprezentare” este de obicei dată prin alegerea unui polinom de grad ireductibil peste , deci putem specifica folosind . În acest caz, este posibil să găsiți polinoame . $\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}$

Inversiunea $f$

Trebuie remarcat că nu este întotdeauna o permutare . Cu toate acestea, baza algoritmului

HFE este următoarea teoremă.

f

L_{N}

Teorema : Fie un câmp finit, și cu și „nu prea mare” (de exemplu, și ). $L_{N}$ $\mid {L_{N}}\mid =q^{n}$ $q$ $n$ $q\leq {64}$ $n\leq {1024}$ Fie un polinom dat într -un câmp cu gradul „nu prea mare” (de exemplu, ). $f(x)$ $X$ $L_{N}$ $d$ $d\leq {1024}$ Fie un element al câmpului . $A$ $L_{N}$ Apoi întotdeauna (pe un computer) puteți găsi toate rădăcinile ecuației . $f(x)=a$

Criptare [1]

Prezentarea mesajului $M$

În domeniu numărul elementelor publice . $K$ $q=p^{m}$

Fiecare mesaj este reprezentat de o valoare , unde este un șir de elemente de câmp . Astfel, dacă , atunci fiecare mesaj este reprezentat prin biți. Mai mult, uneori se presupune că a fost plasată o oarecare redundanță în reprezentarea mesajului . $M$ $X$ $X$ $n$ $K$ $p=2$ $nm$ $X$ $r$

Criptare $X$

Parte secretă

Extinderea domeniului de grad . $L_{n}$ $K$ $n$
Funcția : , care a fost descrisă mai sus, cu un grad „nu prea mare” de . $f$ ${L_{n}}\mapsto {L_{n}}$ $d$
Două transformări afine și : $S$ $T$ ${K^{n}}\mapsto {K^{n}}$

Partea publică

Câmp cu elemente și lungime . $K$ $q=p^{m}$ $n$
$n$ polinoame de dimensiune peste câmp . $(p_{1},...,p_{n})$ $n$ $K$
O modalitate de a adăuga redundanță la mesaje (adică o modalitate de a obține de la ). $r$ $X$ $M$

Ideea principală de a construi o familie de sisteme de ecuații de câmp ascuns ca un criptosistem multidimensional este de a construi o cheie secretă pornind de la un polinom cu o necunoscută peste un câmp finit .

[2] Acest polinom poate fi inversat peste , adică orice soluție a ecuației poate fi găsită dacă există. Transformarea secretă, precum și decriptarea și/sau semnătura, se bazează pe această inversare.

P

X

L_{N}

L_{N}

P(x)=y

După cum sa spus mai sus, poate fi identificat printr-un sistem de ecuații folosind o bază fixă. Pentru a construi un criptosistem, un polinom trebuie transformat în așa fel încât informațiile publice să ascundă structura originală și să împiedice inversarea. Acest lucru se realizează considerând câmpurile finite ca un

spațiu vectorial peste și alegând două transformări afine liniare și . Tripletul formează cheia privată. Polinomul privat este definit pe . Cheia publică este un polinom . [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 → secret : S X ′ → secret : P y ′ → secret : T y {\displaystyle M{\overset {+r}{\to }}x{\overset {{\text{secret}}:S}{\to }}x'{\overset {{\text{secret}}: P}{\to }}y'{\overset {{\text{secret}}:T}{\to }}y}

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

Extensii HFE

Ecuațiile câmpului ascuns au patru modificări de bază: + , - , v și f și pot fi combinate în moduri diferite. Principiul de bază este următorul [2] :

Modificarea „+” constă într-o combinație liniară de ecuații publice cu unele ecuații aleatorii.
Modificarea „-” a apărut datorită lui Adi-Shamir și elimină redundanța „ ” din ecuațiile publice. $r$
Modificarea „f” constă în repararea unor variabile de intrare cu cheie publică. $f$
Modificarea „v” este definită ca o construcție complexă, astfel încât funcția inversă poate fi găsită numai dacă unele variabile v sunt fixe. Această idee îi aparține lui Jacques Patarin.

Atacurile asupra criptosistemelor HFE

Cele mai cunoscute două atacuri asupra sistemului de ecuații de câmp ascuns [4] sunt:

Derivarea cheii private (Shamir-Kipnis): Punctul cheie al acestui atac este recuperarea cheii private ca polinoame rare unidimensionale în câmpul extensiilor . Atacul funcționează numai pentru sistemul de bază de ecuații de câmp ascuns și nu funcționează pentru toate variațiile sale. $L_{n}$
Atacul cu algoritm Gröbner (dezvoltat de Jean-Charles Fougères ): Ideea din spatele atacului este de a folosi un algoritm rapid pentru a calcula baza Gröbner a unui sistem de ecuații polinomiale . Fougeres a spart HFE în HFE Challenge 1 în 96 de ore în 2002. În 2003, Fougeres a lucrat cu Zhu pentru a asigura HFE.

Note

↑ 1 2 3 4 Jacques Patarin Ecuații de câmp ascuns (HFE) și polinom izomorf (IP): două familii noi de algoritm asimetric . Data accesului: 15 decembrie 2017. Arhivat din original pe 2 februarie 2017. (nedefinit)
↑ 1 2 3 4 5 Christopher Wolf și Bart Preneel, Asymmetric Cryptography: Hidden Field Equations . Preluat la 8 decembrie 2017. Arhivat din original la 10 august 2017. (nedefinit)
^ Enrico Thomae și Christopher Wolf, Solving Systems of Multivariate Quadratic Equations over Finite Fields sau: From Relinearization to MutantXL . Preluat la 8 decembrie 2017. Arhivat din original la 10 august 2017. (nedefinit)
↑ Nicolas T. Courtois, „Securitatea ecuațiilor de câmp ascunse” . (nedefinit)

Link -uri

Criptosisteme cu cheie publică

Algoritmi

Factorizarea numerelor întregi	Criptosistemul Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Pupa paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Logaritm discret	BLS Cramer - Shoup Protocolul Diffie-Hellman DSA ECDH Curba25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Schimb de chei criptate Schema lui ElGamal schema de semnătură MQV Schema Schnorr VORBIȚI SRP STS
Criptografia pe zăbrele	NTRUEncrypt NTRUSign Schimb de chei bazat pe învățare cu erori Antrenament bazat pe semnătură cu erori în ring FERICIRE Speranța nouă
Alte	AE CEILIDH EPOC Ecuații de câmp ascunse IES Semnătura lui Lampport McEliece Criptosistem de rucsac Merkle-Hellman Criptosistem de rucsac Naccache–Stern Protocol în trei etape XTR

Teorie

Logaritm discret pe o curbă eliptică
Criptografia eliptică
Criptografia bazată pe hash
Criptografia necomutativă
Problema RSA
Funcție unidirecțională cu intrare secretă

Standarde

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Criptografie post cuantică

Subiecte

Semnatura electronica
OAEP
Amprenta
PKI
rețea de încredere
Dimensiunea cheii
Criptografia bazată pe identitate
Criptografia post-cuantică
Card OpenPGP