Stopujte nulovou kryptografii - Trace zero cryptography

Tento článek má několik problémů. Prosím pomozte zlepšit to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Trasování nulové kryptografie“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Březen 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) The hlavní část tohoto článku možná bude třeba přepsat. Použijte průvodce rozvržením elektrody zajistit, aby tato část dodržovala normy Wikipedie a obsahovala všechny důležité podrobnosti. (Červen 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

V roce 1998 Gerhard Frey nejprve navrhováno použití sledovat nulové odrůdy pro kryptografické účely. Tyto odrůdy jsou podskupinami skupiny dělitele třídy na hyperelliptické křivce s nízkým rodem definované nad a konečné pole. Tyto skupiny lze použít k vytvoření asymetrická kryptografie za použití diskrétní logaritmus problém jako kryptografický primitiv.

Stopové nulové odrůdy mají lepší skalární multiplikační výkon než eliptické křivky. To umožňuje rychlou aritmetiku v těchto skupinách, což může urychlit výpočty s faktorem 3 ve srovnání s eliptickými křivkami, a tím urychlit kryptosystém.

Další výhodou je, že pro skupiny kryptograficky relevantní velikosti lze pořadí skupiny jednoduše vypočítat pomocí charakteristického polynomu Frobeniova endomorfismu. Není tomu tak například v případě kryptografie eliptické křivky když je skupina bodů eliptické křivky nad prvočíslem použita pro kryptografické účely.

K reprezentaci prvku odrůdy nulové stopy je však zapotřebí více bitů ve srovnání s prvky eliptických nebo hyperelliptických křivek. Další nevýhodou je skutečnost, že je možné snížit bezpečnost TZV z ¹/₆^th bitové délky pomocí útoku krytu.

Matematické pozadí

A hyperelliptická křivka C rodu G nad hlavním polem ${displaystyle mathbb {F} _ {q}}$ kde q = pⁿ (p prime) liché charakteristiky je definována jako

${displaystyle C: ~ y ^ {2} + h (x) y = f (x),}$

kde F monic, deg (F) = 2G + 1 a stupně (h) ≤ g. Křivka má alespoň jednu ${displaystyle mathbb {F} _ {q}}$- racionální Weierstraßpoint.

The Jacobian odrůda ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ z C je pro všechny konečné rozšíření ${displaystyle mathbb {F} _ {q ^ {n}}}$ je izomorfní s ideální třídou ${displaystyle operatorname {Cl} (C / mathbb {F} _ {q ^ {n}})}$. S Mumfordovo zastoupení je možné reprezentovat prvky ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ s dvojicí polynomů [u, v], kde u, proti ∈ ${displaystyle mathbb {F} _ {q ^ {n}} [x]}$.

The Frobeniova endomorfismus σ se používá na prvku [u, v] z ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ zvýšit sílu každého koeficientu daného prvku na q: σ ([u, v]) = [u^q(x), v^q(X)]. Charakteristický polynom tohoto endomorfismu má následující formu:

${displaystyle chi (T) = T ^ {2g} + a_ {1} T ^ {2g-1} + cdots + a_ {g} T ^ {g} + cdots + a_ {1} q ^ {g-1} T + q ^ {g},}$

kde_i v ℤ

S Hasse – Weilova věta je možné přijmout skupinovou objednávku libovolného pole rozšíření ${displaystyle mathbb {F} _ {q ^ {n}}}$ pomocí komplexních kořenů τ_i χ (T):

${displaystyle | J_ {C} (mathbb {F} _ {q ^ {n}}) | = prod _ {i = 1} ^ {2g} (1- au _ {i} ^ {n})}$

Nechat D být prvkem ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$ z C, pak je možné definovat endomorfismus z ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$, takzvaný stopa D.:

${displaystyle operatorname {Tr} (D) = součet _ {i = 0} ^ {n-1} sigma ^ {i} (D) = D + sigma (D) + cdots + sigma ^ {n-1} (D )}$

Na základě tohoto endomorfismu lze snížit jakobijskou odrůdu na podskupinu G s vlastností, že každý prvek má stopovou nulu:

${displaystyle G = {Din J_ {C} (mathbb {F} _ {q ^ {n}}) ~ | ~ {ext {Tr}} (D) = {extbf {0}}}, ~~~ ({ extbf {0}} {ext {neutrální prvek v}} J_ {C} (mathbb {F} _ {q ^ {n}})}$

G je jádrem stopového endomorfismu a tedy G je skupina, tzv stopová nula (pod) odrůda (TZV) ze dne ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$.

Křižovatka G a ${displaystyle J_ {C} (mathbb {F} _ {q})}$ vyrábí společnost n- torzní prvky ${displaystyle J_ {C} (mathbb {F} _ {q})}$. Pokud největší společný dělitel ${displaystyle gcd (n, | J_ {C} (mathbb {F} _ {q}) |) = 1}$ křižovatka je prázdná a lze vypočítat skupinové pořadí G:

${displaystyle | G | = {dfrac {| J_ {C} (mathbb {F} _ {q ^ {n}}) |} {| J_ {C} (mathbb {F} _ {q}) |}} = {dfrac {prod _ {i = 1} ^ {2g} (1- au _ {i} ^ {n})} {prod _ {i = 1} ^ {2g} (1- au _ {i})} }}$

Skutečná skupina použitá v kryptografických aplikacích je podskupina G₀ z G velkého hlavního řádu l. Tato skupina může být G sám.^[1][2]

Existují tři různé případy kryptografického významu pro TZV:^[3]

• G = 1, n = 3
• G = 1, n = 5
• G = 2, n = 3

Aritmetický

Aritmetika použitá ve skupině TZV G₀ na základě aritmetiky pro celou skupinu ${displaystyle J_ {C} (mathbb {F} _ {q ^ {n}})}$, Ale je možné použít Frobeniova endomorfismus σ k urychlení skalárního násobení. To lze archivovat, pokud G₀ generuje D řádu l pak σ (D) = sD, pro některá celá čísla s. Pro dané případy TZV s lze vypočítat následovně, kde A_i pocházejí z charakteristického polynomu Frobeniova endomorfismu:

• Pro G = 1, n = 3: ${displaystyle s = {dfrac {q-1} {1-a_ {1}}} {mod {ell}}}$
• Pro G = 1, n = 5: ${displaystyle s = {dfrac {q ^ {2} -q-a_ {1} ^ {2} q + a_ {1} q + 1} {q-2a_ {1} q + a_ {1} ^ {3} -a_ {1} ^ {2} + a_ {1} -1}} {mod {ell}}}$
• Pro G = 2, n = 3: ${displaystyle s = - {dfrac {q ^ {2} -a_ {2} + a_ {1}} {a_ {1} q-a_ {2} +1}} {mod {ell}}}$

S tímto vědomím je možné nahradit jakékoli skalární násobení mD (| m | ≤ l / 2) s:

${displaystyle m_ {0} D + m_ {1} sigma (D) + cdots + m_ {n-1} sigma ^ {n-1} (D), ~~~~ {ext {where}} m_ {i} = O (ell ^ {1 / (n-1)}) = O (q ^ {g})}$

S tímto trikem lze vícerozměrný součin snížit na přibližně 1 / (n − 1)^th zdvojnásobení nezbytných pro výpočet mD, pokud jsou implikované konstanty dostatečně malé.^[3][2]

Bezpečnostní

Zabezpečení kryptografických systémů založené na stopových nulových podrozměnách podle výsledků příspěvků^[2][3] srovnatelná s bezpečností hypereliptických křivek nízkého rodu G' přes ${displaystyle mathbb {F} _ {p '}}$, kde p ' ~ (n − 1)(g / g ' ) pro | G | ~ 128 bitů.

Pro případy, kdy n = 3, G = 2 a n = 5, G = 1 je možné snížit zabezpečení maximálně na 6 bitů, kde | G | ~ 2²⁵⁶, protože si tím nemůžete být jisti G je obsažen v jakobiánu křivky rodu 6. Zabezpečení křivek rodu 4 pro podobná pole je mnohem méně bezpečné.

Krycí útok na kryptosystém s nulovou stopou

Útok zveřejněn v^[4]ukazuje, že DLP ve stopových nulových skupinách rodu 2 nad konečnými poli charakteristických různorodých než 2 nebo 3 a rozšíření pole stupně 3 lze transformovat na DLP ve skupině tříd stupně 0 s rodem nejvýše 6 za základní pole. V této nové skupině tříd může být DLP napadeno metodami indexového počtu. To vede ke zmenšení délky bitu ¹/₆^th.

Poznámky

Reference

• Wienecke, Malte; Paar, Christof (17. února 2008). Kryptografie na odrůdách stopové nuly (PDF). Ruhr University Bochum.
• Sutherland, Andrew V. (2007). „101 užitečných stopových nulových odrůd“. Massachusetts Institute of Technology.