Rejtett mező egyenletek

A Hidden Field Equations (HFE) a nyilvános kulcsú kriptográfiai rendszer egy típusa , amely a többdimenziós kriptográfia része . Más néven egyirányú HFE rejtett belépési funkció . Ez a rendszer a Matsumoto-Imai rendszer általánosítása, és először Jacques Patarin mutatta be 1996-ban az Eurocrypt konferencián. [egy]

A rejtett mező egyenletrendszere különböző méretű véges mezők feletti polinomokon alapul, hogy elfedje a privát kulcs és a nyilvános kulcs közötti kapcsolatot. [2] $K$

A HFE tulajdonképpen egy család, amely alapvető HFE-kből és HFE-változatok kombinációiból áll. A HFE kriptorendszerek családja azon alapul, hogy nehéz megoldást találni egy többváltozós másodfokú egyenletrendszerre (az ún. MQ probléma [3] ), mivel parciális affin transzformációkat alkalmaz a mezőbővítés és a részpolinomok elrejtésére . Rejtett mező egyenleteket is használtak digitális aláírási sémák felépítésére , mint például a Quartz és a Sflash . [2] [1]

Fő ötlet [1]

Funkció $f$

Legyen véges dimenziójú mező karakterisztikával (általában, de nem feltétlenül ). $K$ $q$ $p$ $p=q=2$
Legyen a fok kiterjesztése . $L_{N}$ $K$ $N$
Legyen , és elemei . $\beta _{ij}$ $\alpha_i$ $\mu_{0}$ $L_{N}$
Legyen , és egész számok. ${\displaystyle \theta _{ij))$ ${\displaystyle \varphi _{ij))$ $\xi _{i}$
Végül legyen egy olyan függvény, hogy: $f$ L N ↦ L N {\displaystyle L_{N}\mapsto L_{N}} $L_{N}\mapsto L_{N}$ f : x ↦ ∑ én , j β én j x q θ én j + q φ én j + ∑ én α én x q ξ én + μ 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))$

Ekkor van egy polinom -ben . $f$ $x$

Legyen most az alap . Ekkor a kifejezés az alapban a következő: $B$ $L_{N}$ $f$ $B$

f ( x egy , . . . , x N ) = ( p egy ( x egy , . . . , x N ) , . . . , p N ( x egy , . . . , 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}))$ ahol polinomok vannak a 2. fokú változókban . $p_{1},...,p_{N}$ $N$ $N$

Ez igaz, mivel bármely egész szám esetén a lineáris függvénye . A polinomokat egy "ábrázolás" kiválasztásával találhatja meg . Az ilyen "reprezentációt" általában úgy adjuk meg, hogy egy irreducibilis fokú polinomot választunk a helyett , így megadhatjuk a segítségével . Ebben az esetben lehetséges polinomokat találni . $\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}$

Inverzió $f$

Meg kell jegyezni, hogy ez nem mindig permutáció . A

HFE algoritmus alapja azonban a következő tétel.

f

L_{N}

Tétel : Legyen véges mező, és a és a "nem túl nagy" (például, és ). $L_{N}$ $\mid {L_{N}}\mid =q^{n}$ $q$ $n$ $q\leq {64}$ $n\leq {1024}$ Legyen egy adott polinom egy „nem túl nagy” fokozatú mezőben (például ). $f(x)$ $x$ $L_{N}$ $d$ $d\leq {1024}$ Legyen a mező eleme . $a$ $L_{N}$ Ekkor mindig (számítógépen) megtalálhatja az egyenlet összes gyökerét . $f(x)=a$

Titkosítás [1]

Az üzenet bemutatása $M$

A mezőben a nyilvános elemek száma . $K$ $q=p^{m}$

Minden üzenetet egy érték jelöl , ahol mezőelemek sorozata . Így, ha , akkor minden üzenetet bitek képviselnek. Ezenkívül néha azt feltételezik, hogy bizonyos redundanciát helyeztek el az üzenet megjelenítésében . $M$ $x$ $x$ $n$ $K$ $p=2$ $nm$ $x$ $r$

Titkosítás $x$

Titkos rész

Fokozatbővítés . _ _ $L_{n}$ $K$ $n$
Funkció : , amit fentebb leírtunk, "nem túl nagy" fokkal . $f$ ${L_{n}}\mapsto {L_{n}}$ $d$
Két affin transzformáció és : $S$ $T$ ${K^{n}}\mapsto {K^{n}}$

Nyilvános rész

Mező elemekkel és hosszával . $K$ $q=p^{m}$ $n$
$n$ a mező feletti dimenziós polinomok . $(p_{1},...,p_{n})$ $n$ $K$
Egy módja annak, hogy redundanciát adjon az üzenetekhez (vagyis egy módja annak, hogy érkezzen a címről ) . $r$ $x$ $M$

A rejtett mezőegyenlet-rendszerek többdimenziós kriptorendszerként való felépítésének fő ötlete az, hogy egy titkos kulcsot hozzunk létre egy ismeretlen polinomból valamilyen véges mező felett .

[2] Ez a polinom megfordítható -re , azaz az egyenletre bármilyen megoldás megtalálható , ha létezik. A titkos transzformáció, valamint a visszafejtés és/vagy aláírás ezen az inverzión alapul.

P

x

L_{N}

L_{N}

P(x)=y

Mint fentebb említettük, egy fix alapot használó egyenletrendszerrel azonosítható . A kriptorendszer felépítéséhez egy polinomot úgy kell átalakítani, hogy a nyilvános információ elrejtse az eredeti struktúrát és megakadályozza az inverziót. Ezt úgy érjük el, hogy véges mezőket

vektortérnek tekintjük , és két lineáris affin transzformációt és . A triplet alkotja a privát kulcsot. A privát polinom a következőn van definiálva . A nyilvános kulcs egy polinom . [2]

P

n

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

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

\mathbb {L} _{n}

\mathbb {K}

S

T

{\megjelenítési stílus (S,P,T)}

P

\mathbb {L} _{n}

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

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

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

HFE kiterjesztések

A rejtett mezőegyenleteknek négy alapvető módosítása van: + , - , v és f , és ezek többféleképpen kombinálhatók. Az alapelv a következő [2] :

A "+" módosítás nyilvános egyenletek és néhány véletlenszerű egyenlet lineáris kombinációjából áll.
A "-" módosítás Adi-Shamirnak köszönhetően jelent meg, és eltávolítja a " " redundanciát a nyilvános egyenletek közül. $r$
Az "f" módosítás néhány nyilvános kulcs bemeneti változójának rögzítéséből áll . $f$
A "v" módosítást olyan összetett konstrukcióként definiáljuk, hogy az inverz függvény csak akkor található meg, ha néhány v változó rögzítve van. Ez az ötlet Jacques Patariné.

Támadások HFE kriptorendszerek ellen

A két leghíresebb támadás a rejtett mező egyenletek rendszere ellen [4] :

Privát kulcs levezetése (Shamir-Kipnis): Ennek a támadásnak a kulcsa, hogy a privát kulcsot ritka egydimenziós polinomokként állítsa vissza a kiterjesztések területén . A támadás csak a rejtett mezőegyenletek alaprendszerére működik, és nem minden változatára. $L_{n}$
Gröbner - algoritmus támadás ( Jean-Charles Fougères fejlesztette ): A támadás mögött az az ötlet, hogy egy gyors algoritmus segítségével számítsák ki egy polinomiális egyenletrendszer Gröbner-alapját . Fougeres 2002-ben 96 óra alatt feltörte a HFE-t a HFE Challenge 1-ben. 2003-ban Fougeres Zhuval együttműködve biztosította a HFE-t.

Jegyzetek

↑ 1 2 3 4 Jacques Patarin rejtett mezőegyenletek (HFE) és izomorf polinom (IP): az aszimmetrikus algoritmusok két új családja . Hozzáférés dátuma: 2017. december 15. Az eredetiből archiválva : 2017. február 2.. (határozatlan)
↑ 1 2 3 4 5 Christopher Wolf és Bart Preneel, Aszimmetrikus kriptográfia: Rejtett mezőegyenletek . Letöltve: 2017. december 8. Az eredetiből archiválva : 2017. augusztus 10.. (határozatlan)
↑ Enrico Thomae és Christopher Wolf, Többváltozós másodfokú egyenletrendszerek megoldása véges mezőkön vagy: Az újralinearizálástól a MutantXL-ig . Letöltve: 2017. december 8. Az eredetiből archiválva : 2017. augusztus 10.. (határozatlan)
↑ Nicolas T. Courtois, "The Security of Hidden Field Equations" . (határozatlan)

Linkek

Nyilvános kulcsú kriptorendszerek

Algoritmusok

Egész számok faktorizálása	Benalo kriptorendszer Bluma – Goldwasser Cayley Purser Damgorda – Eureka GMR Goldwasser – Micali Nakasha – Stern paye Rabin RSA Okamoto – Uchiyama Schmidt-Szamoa
Diszkrét logaritmus	BLS Cramer – Shoup Diffie-Hellman protokoll DSA ECDH Görbe 25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Titkosított kulcscsere ElGamal séma aláírási séma MQV Schnorr-séma SPEKE SRP STS
Kriptográfia rácsokon	NTRUEncrypt NTRUSign Tanulás alapú kulcscsere hibákkal Aláírás alapú edzés hibákkal a ringben BOLDOGSÁG Új remény
Egyéb	AE CEILIDH EPOC Rejtett mező egyenletek IES Lamport aláírása McEliece Merkle-Hellman háti kriptorendszer Naccache–Stern háti kriptorendszer Három lépéses protokoll XTR

Elmélet

Szabványok

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Posztkvantum kriptográfia

Témák

Elektronikus aláírás
OAEP
Ujjlenyomat
PKI
a bizalom hálója
Kulcsméret
Identitás alapú kriptográfia
Posztkvantum kriptográfia
OpenPGP kártya