ESIGN

ESIGN ( anglicky Efficient digital SIGNature - efektivní digitální podpis) je schéma digitálního podpisu s veřejným klíčem založené na problému faktorizace čísel . Charakteristickým rysem tohoto schématu je schopnost rychle generovat podpis. [jeden]

Historie

Digitální podpis vyvinula japonská společnost NTT v roce 1985. [2] Schéma se ukázalo jako efektivní z hlediska rychlosti generování digitálního podpisu. První verze však prolomili Ernie Btickel a John DeLaurentis , poté byly doporučené parametry algoritmu upraveny . [3] Následné pokusy o hackování byly neúspěšné. Autoři tvrdí, že složitost crackování poslední verze ESIGN je srovnatelná se složitostí problému faktorizace pro řadu formulářů , kde a jsou prvočísla . [čtyři] $n$ $p^{2}q$ $p$ $q$

Popis protokolu

Úvod

Do protokolu se zapojují dvě entity: entita , jejímž účelem je prokázat, že autor zprávy je , a subjekt , jehož účelem je ověřit autorství. V ESIGN pro realizaci stanovených cílů a musí provést následující akce [5] . $A$ $m$ $B$ $A$ $B$

Dříve generuje klíče : veřejné, známé všem, a soukromé , známé pouze subjektu . $A$ $A$
Subjekt generuje digitální podpis zprávy na základě soukromého klíče. $A$ $s$ $m$
$A$ odešle zprávu spolu s podpisem předmětu . $m$ $s$ $b$
Subjekt ověřuje podpis na základě veřejného klíče. $B$

Generování veřejných a soukromých klíčů

Klíče ESIGN se generují následovně [6] .

Náhodně jsou vybrána dvě prvočísla stejné bitové délky. $p$ $q$
Počet je vypočítán . $n=p^{2}q$
Je vybráno kladné celé číslo . $k\geqslant 4$
Dvojice čísel je veřejný klíč. $(n,k)$
Pár čísel je soukromý klíč. $(p,q)$

Generování podpisu

Pro podepsání zprávy , kde je binární číslo libovolné délky, jsou provedeny následující kroky [6] . $m$ $m$

, kde je předvolená hašovací funkce , která nabývá hodnot od do . $\mu=h(m)$ $h$ $0$ $n-1$
Z intervalu je vybráno náhodné číslo . $X$ $[0,pq)$
A vypočítá se , kde je funkce zaokrouhlení na nejmenší celé číslo, větší argument. $\chi =\left\lceil {\frac {\mu -(x^{k}{\bmod {n)))}{pq))\right\rceil$ $\varkappa =\left({\frac {\chi }{k*x^{k-1}}}\right){\bmod {p}}$ $\lceil \cdot \rceil \colon \mathbb {R} \to \mathbb {Z}$
Vypočítá se podpis . $s=x+\varkappa pq$

Ověření podpisu

Chcete-li ověřit, že podpis skutečně podepisuje zprávu , jsou provedeny následující kroky [6] . $s$ $m$

, kde je stejná hashovací funkce, která byla použita k vygenerování podpisu. $\mu=h(m)$ $h$
Vypočteno . $\xi =\left\lceil {\frac {2}{3}}\log _{2}{n}\right\rceil$
Provede se test nerovnosti . $\mu \leqslant s^{k}{\bmod {n}}\leqslant \mu +2^{\xi }$
Podpis je považován za platný, pokud je splněna nerovnost.

Předchozí verze

V původně navrhované verzi ESIGN byl parametr roven dvěma. [5] Po úspěšném útoku Ernieho Brickela a Johna DeLaurentise, který se rozšířil i na okruhovou variantu s , však autoři změnili požadavek na tento parametr na stávající . [7] $k$ $k = 3$ $k\geqslant 4$

Kryptoanalýza

Útok na hashovací funkci

Útoky na hašovací funkci s cílem zfalšovat podpis jsou založeny na její nedokonalosti, tedy na nesouladu hašovací funkce s jedním nebo více kritérii kryptografické síly, s tím, že v případě ESIGN je rovnost kritérií by měly být pochopeny až do nejvýznamnějších bitů. Toto uvolnění je způsobeno podmínkou ověření podpisu, která je splněna nejen pro původní hash hodnotu, ale také pro ostatní, které se shodují v prvních vysokých bitech. $h$ $(\log _{2}{n})/3$ $(\log _{2}{n})/3$

Předpokládejme, že funkce je nestabilní při hledání kolizí, to znamená, že v prvních vysokých bitech můžete najít různé a jiné. Poté, podepsání zprávy , autor , nic netušící, automaticky zprávu podepíše , protože nerovnost $h$ $m$ $m'$ $h(m)$ $h(m')$ $(\log _{2}{n})/3$ $m$ $A$ $m'$ $h(m')\leqslant s^{k}{\bmod {n}}\leqslant h(m')+2^{\left\lceil {\frac {2}{3}}\log _ {2}{n}\right\rceil}$

Pokud je zvolená hašovací funkce kryptograficky bezpečná, pak kolizní útok převezme operace výpočtu hašovací funkce, útok pomocí druhého předobrazu provede operace, které jsou považovány za neproveditelné, pro velké . [8] [9] $2^{(\log _{2}{n})/3}$ $2^{(\log _{2}{n})/6}$ $n$

Útok na veřejný klíč

Útok na veřejný klíč je pokus získat z něj soukromý klíč . Toho lze dosáhnout řešením rovnice , tedy faktorováním čísla . Můžete vidět, že v RSA se číslo generuje podobným způsobem, ale dnes zůstává otevřená otázka, ve kterém z případů se faktorizace zjednoduší nebo ztíží, protože stále neexistují žádné efektivní algoritmy faktorizace. V současnosti je nejrychlejším způsobem rozkladu čísla , ať už pro ESIGN nebo pro RSA, metoda číselného pole síta , která to provádí rychlostí závislou na délce bitu . Při velké bitové délce čísla se však úloha faktorizace stává nemožným. [10] [9] $(n,k)$ $(p,q)$ $n=p^{2}q$ $n$ $n$ $n=pq$ $n$ $n$ $n$

Doporučená nastavení

Kromě omezení již uvedených v popisu ESIGN se pro větší bezpečnost doporučuje zvolit velikost a rovnou nebo větší než bity, velikost rovnou nebo větší a parametr větší nebo rovný 8 [ 11] : $p$ $q$ $320$ $n$ $960$ $k$

$\log _{2}{p}\geqslant 320$ ;
$k\geqslant 8$ ;

Úroveň zabezpečení ve vztahu k jiným schématům digitálního podpisu

Níže je uvedena tabulka shody mezi úrovní zabezpečení ESIGN a úrovněmi zabezpečení RSA a ECDSA pro různé velikosti parametrů v bitech. Můžete vidět, že při stejných velikostech jsou RSA a ESIGN z hlediska bezpečnosti srovnatelné. [12] $n$ $n$

Velikost v ESIGN, bity $n$	Velikost v RSA, bity $n$	Velikost v ECDSA, bity $n$
960	960	152
1024	1024	160
2048	2048	224
3072	3072	256
7680	7680	384

Výhody

Schéma ESIGN umožňuje rychle vygenerovat podpis. Protože výpočetně složité operace, jako je umocňování a hledání inverzního prvku , nezávisí na podepsané zprávě , lze je provést předem a uložit do paměti. K podepsání zprávy tedy stačí provést zbývající operace sčítání, násobení a dělení, jejichž podíl na výpočetní složitosti algoritmu vytváření podpisu je malý. V případě, kdy , a bitová délka je rovna , je rychlost generování podpisu v vyšší než u RSA s odpovídajícími parametry. Co se týče ověřování podpisu, jeho rychlost je srovnatelná s rychlostí ověřování podpisu v algoritmu RSA , jehož otevřený exponent je malý. [13] [9] $(x^{k}{\bmod {n)))$ ${\displaystyle (k*x^{k-1})^{-1))$ $m$ $k = 4$ $n$ $768$ $10\div 100$

Autentizační protokoly založené na ESIGN

S pomocí ESIGN můžete implementovat identifikační protokoly s nulovou znalostí , které subjektu ( anglicky Prover - proving) umožní prokázat subjektu ( anglicky Verifier - kontrola) skutečnost přítomnosti informace a utajit ji před . Identifikační protokoly založené na ESIGN jsou stejně účinné jako protokol Feig-Fiat-Shamir . Budeme zvažovat dva takové protokoly: tříkolový a dvoukolový. [čtrnáct] $P$ $PROTI$ $PROTI$

Tříkolové identifikační schéma

$P$ generuje veřejné a soukromé klíče ESIGN. $(n,k)$ $(p,q)$
$P$ náhodně vybere čísla a vypočítá , kde je jednosměrná funkce , je operace zřetězení a odešle ověřovateli . $r$ $u$ $x=f(r\|u)$ $F$ $\|$ $X$ $PROTI$
$PROTI$ náhodně vybere číslo a pošle ho dokazovateli. $y$
$P$ vypočítá , vygeneruje podpis pro a odešle trojnásobek ověřovateli. $m=r\oplus y$ $s$ $m$ $(s,r,u)$
$PROTI$ ověří, že podpis zprávy je stejný a platný . $x=f(r\|u)$ $s$ $m$

Dvoukolové identifikační schéma

$P$ generuje veřejné a soukromé klíče ESIGN. $(n,k)$ $(p,q)$
$PROTI$ náhodně vybere číslo a pošle ho dokazovateli. $r$
$P$ náhodně vybere číslo , vypočítá , vygeneruje podpis pro a odešle jej ověřovateli. $u$ $m=f(r\|u)$ $s$ $m$ $(s,u)$
$PROTI$ ověří, že podpis zprávy je stejný a platný . $m=f(r\|u)$ $s$ $m$

Ve výše uvedených protokolech jsou tajnou informací klíče , jejichž znalost dokazuje předmět . Pokud jsou výsledky všech kontrol v závěrečných fázích úspěšné, má se za to, že má skutečně tajemství. $(p,q)$ $P$ $P$

Poznámky

↑ Menezes, Oorschot, Vanstone, 1996 , §11.7 s.2, s. 473-474.
↑ Minghua, 2001 , str. jeden.
↑ Schneier, 2002 , kapitola 20, s.6.
↑ Atsushi, 1991 , kapitola 2, odstavec 3: „Domníváme se, že prolomit naši verzi vyššího stupně (ESIGN) je stejně těžké jako faktoring N“.
↑ 1 2 Schneier, 2002 , kapitola 2, s.6.
↑ 1 2 3 Menezes, Oorschot, Vanstone, 1996, § 11.7 s. 2, s. 473.
↑ Menezes, Oorschot, Vanstone, 1996 , §11.9, pp. 486-487.
↑ Minghua, 2001 , str. 3.
↑ 1 2 3 Menezes, Oorschot, Vanstone, 1996, § 11.7 s. 2, s. 474.
↑ Minghua, 2001 , str. čtyři.
↑ Minghua, 2001 , str. 6.
↑ Minghua, 2001 , str. 7.
↑ Atsushi, 1991 , kapitola 3.
↑ Atsushi, 1991 , kapitola 4.

Literatura

Schneier B. Aplikovaná kryptografie. Protokoly, algoritmy, zdrojový kód v jazyce C = Aplikovaná kryptografie. Protocols, Algorithms and Source Code in C. - M. : Triumph, 2002. - 816 s. - 3000 výtisků. - ISBN 5-89392-055-4 .
Alfred J. Menezes, Paul C. van Oorschot a Scott A. Vanstone. Kapitola 11. Digitální podpisy // Příručka aplikované kryptografie . - 5. vyd. - CRC Press , 1996. - S. 473-474. — 816 s. - ISBN 0-8493-8523-7 .
Atsushi Fujioka, Tatsuaki Okamoto, Shoji Miyaguchi. ESIGN: Efektivní implementace digitálního podpisu pro čipové karty // Pokroky v kryptologii - EUROCRYPT '91 : Proceedings of Conf. / Advances in Cryptology - EUROCRYPT '91, Brighton, UK, 8.-11. dubna 1991. - Springer Berlin Heidelberg, 1991. - S. 446-457 . — ISBN 978-3-540-54620-7 . (nedostupný odkaz)
Alfred Menezes, Minghua Qu, Doug Stinson, Yongge Wang Hodnocení úrovně zabezpečení kryptografie: ESIGN podpisové schéma : projektové materiály / CRYPREC Project, Japonsko. - 2001. - leden. Archivováno z originálu 9. srpna 2017.