Úplný hash domény

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. ledna 2019; kontroly vyžadují 30 úprav .

V kryptografii je Full Domaine Hash ( FDH nebo Full Domain Hash ) schéma podpisu založené na RSA , které se řídí paradigmatem hash a podpisu . Je prokazatelně bezpečný (to znamená, že není ovlivněn adaptivními útoky na vybrané zprávy) v modelu náhodného orákula . FDH zahrnuje hašování zprávy pomocí funkce, jejíž velikost obrázku je velikost modulu RSA , a následné zvýšení výsledku na tajnou mocninu exponentu RSA .

Úvod

Od objevu kryptografie s veřejným klíčem Whitfieldem Diffiem a Martinem Hellmanem [ 1 ] je jedním z nejdůležitějších výzkumných témat vývoj praktických a prokazatelně (v praktickém chápání) bezpečných kryptosystémů. Důkazem praktické bezpečnosti je obvykle výpočetní náročnost od řešení známého problému až po prolomení kryptosystému. Mezi známé problémy patří faktorizace velkých celých čísel , výpočet diskrétního logaritmu modulo prvočíslo p nebo extrahování kořenového modulu složeného celého čísla, na kterém je založen kryptosystém RSA [2] .

Velmi běžnou praxí při podepisování pomocí RSA je nejprve zprávu hashovat, přidat ke zprávě sůl a poté ji zvýšit na sílu veřejného klíče. Toto paradigma „hash and decrypt“ je základem mnoha standardů, jako je PKCS # 1 v2.0 [3] . Schéma má převzít hašovací funkci, jejíž výstupní velikost je přesně stejná jako velikost modulu: toto je úplné schéma hašování domény (FDH), které představili Bellard a Rogaway v článku „Náhodné věštce jsou praktické: a paradigma pro navrhování účinných protokolů“ [4] . Schéma FDH je prokazatelně bezpečné v modelu náhodného orákula, za předpokladu, že je těžké invertovat RSA , tj. vzít kořenový modul ze složeného celého čísla. Metodika náhodného orákula byla představena Bellardem a Rogawayem v „Náhodné věštce jsou praktické: paradigma pro navrhování účinných protokolů“ [4] , kde ukazují, jak vyvinout vysoce bezpečná podpisová schémata z jakékoli funkce s tajným vstupem . V modelu náhodného orákula je hašovací funkce považována za orákulum , které vytváří náhodnou hodnotu pro každý nový požadavek. V původním článku náhodný orákulum převádí sekvenci 0 a 1 s pevnou délkou na sekvenci s nekonečnou délkou a náhodně vybírá ze sekvence podsekvenci požadované délky . Stěžejní práce Bellarda a Rogawaye zdůrazňuje, že pro praktickou aplikaci prokazatelného zabezpečení je důležité zvážit „tvrdé“ snížení zabezpečení. Degradace zabezpečení je „těžká“, když jakákoli akce kryptoanalytika k porušení podpisového schématu vede k vyřešení dobře zavedeného problému s dostatečnou pravděpodobností, ideálně s pravděpodobností 1. V tomto případě je podpisové schéma téměř stejně bezpečné jako ten zažitý problém. Naproti tomu, pokud je kontrakce "slabá", tj. výše zmíněná pravděpodobnost je příliš malá, může být garance podpisového schématu dosti slabá. ${\{0,1\}}^{*}\longrightarrow {\{0,1\}}^{\infty }$

Definice

Úplné schéma hash podpisu domény (Gen, Sign, Verify) je definováno následovně. Algoritmus generování klíčů spustí RSA, aby získal . Vypisuje kde a . Algoritmus podpisu a ověření má přístup k orákulu s hashovací funkcí $(N,e,d)$ $(pk,sk)$ $pk=(N,e)$ $sk=(N,d)$ $H_{FDH}:{\{0,1\}}\to {\mathbb {Z} _{N}}$

Podepisování a ověřování se provádí následovně:

{\textstyle {\begin{aligned}SignFDH_{N,d}(M)\\y\leftarrow H_{FDH}(M)\\return:y^{d}modN\\\\VerifyFDH_{N,e} (M,x)\\y\leftarrow x^{e}modN;\\y'\leftarrow H_{FDH}(M)\\if(y=y')pak\\return:1\\else\\ return:0\end{aligned}}}

Bezpečnostní analýza schématu FDH

Přístup Bellarda a Rogwaye

Věta 1 Předpokládejme, že RSA je -secure (s pravděpodobností ɛ′ trvá t′ čas, než se zlomí) Pak je schéma podpisu FDH -secure, kde $(t',\varepsilon ')$ $(t,\varepsilon)$

{\begin{aligned}t&=t'-(q_{\text{hash}}+q_{\text{sig}}+1)\\\varepsilon &=(q_{\text{hash}} +q_{\text{sig)))*\varepsilon '\end{aligned}}

Nevýhodou tohoto výsledku je, že může být mnohem menší než . Pokud například předpokládáme, že kryptoanalytik se může dotázat na počet podpisů a vypočítat hash zpráv, i když pravděpodobnost inverze RSA je pouze , pak dostaneme pouze to, že pravděpodobnost je téměř , což není uspokojivé. Abychom získali přijatelnou úroveň zabezpečení, musíme použít větší velikost modulu, což pozitivně ovlivní účinnost obvodu. $\varepsilon '$ $\varepsilon$ $q_{\text{sig}}=2^{30}$ $q_{\text{hash}}=2^{60}$ $2^{-61}$ $1/2$

Aby Bellar a Rogaway získali co nejvhodnější bezpečnostní rozpětí, vyvinuli nové schéma, pravděpodobnostní schéma podpisu , které poskytuje přísné snížení bezpečnosti: pravděpodobnost padělání podpisu je téměř stejně malá jako u inverze . Místo toho existuje alternativní přístup, který lze použít na schéma FDH, aby se dosáhlo lepší vazby. [5] $(PSS)$ $RSA(\varepsilon =\varepsilon ')$

Alternativní přístup

Další snížení, které poskytuje lepší odhad bezpečnosti pro FDH, je založeno na důkazu teorému

Věta 2 Nechť je RSA v bezpečí. Potom je schéma podpisu FDH -secure, kde $(t',\epsilon ')$ $(t,\epsilon )$

{\begin{aligned}t&=t'-(q_{\text{hash}}+q_{\text{sig}}+1)\\\epsilon &={\frac {1}{\left (1-{\frac {1}{q_{\text{sig}}}\right)^{q_{\text{sig}}+1}}}\cdot q_{\text{sig}}\cdot \epsilon '\end{aligned}}

Pro velké ,. $q_{\text{sig}}$ $\epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '$

Definice 1

Invertorem budeme říkat algoritmus, který prolomí RSA, jehož pravděpodobnost úspěchu po uplynutí doby zpracování nejvýše t je alespoň ɛ. $já$ $(t,\epsilon )$

Definice 2

Padělatel je algoritmus, který porušuje schéma podpisu (Gen, Sign, Verify), pokud po maximálně požadavcích na hash oracle, podepsaných požadavcích a době zpracování vypíše padělek podpisu s pravděpodobností alespoň ɛ . $F$ $(t,q_{\text{sig}},q_{\text{hash}},\epsilon )$ $q_{\text{hash}}$ $q_{\text{sig}}$ $t$

Důkaz Nechť je padělatel , který rozbije FDH. Předpokládáme, že nikdy neopakuje stejný hashový požadavek oracle nebo požadavek na podpis. Stavba střídače , který rozbije RSA. Měnič přijímá jako vstup , kde je veřejný klíč, a je vybrán náhodně v (podmnožina všech hashovaných zpráv) . Střídač se snaží najít , odkud je funkce RSA definována . Měnič se spustí pro tento veřejný klíč. Padělatel provádí žádosti o hash oracle a žádosti o podpis. obdrží odpověď od hash oracle, nezávisle je podepíše. $F$ $(t,q_{\text{sig}},q_{\text{hash}},\epsilon )$ $F$ $já$ $(t',\epsilon ')$ $já$ $(N,e,y)$ $(N,e)$ $y$ $\mathbb {Z} _{N}$ $já$ $x=f^{-1}(y)$ $F$ $N,e$ $já$ $F$ $F$ $já$

Pro zjednodušení předpokládáme, že když požádá o podepsání zprávy , již odeslal odpovídající požadavek hash oracle pro . Pokud ne, pokračujeme a nezávisle vytvoříme hash-oracle požadavek na zprávu Měnič používá čítač , který je zpočátku nastaven na nulu. Při dotazování hash oracle na zprávu se invertor zvýší , přiřadí hashovanou zprávu k původní zprávě a vybere náhodné číslo v . pak se vrátí s pravděpodobností as pravděpodobností . Zde je pevná pravděpodobnost, která bude určena později. Při požadavku na podpis pro , již požadoval hash , takže pro některé .If , pak se vrátí jako podpis. Jinak se proces zastaví a střídač selže. $F$ $M$ $M$ $M$ $já$ $i$ $F$ $M$ $já$ $i$ $M_{i}=M$ $r_{i}$ $\mathbb {Z} _{N}$ $já$ $h_{i}=r_{i}^{e}modN$ $p$ $h_{i}=y*r_{i}^{e}modN$ $1-p$ $p$ $F$ $M$ $M$ ${\displaystyle M=M_{i))$ $i$ $h_{i}={r_{i}}^{e}modN$ $já$ ${\displaystyle r_{i))$

Nakonec úlohu dokončí a zobrazí falešný . Předpokládáme, že hash byl požadován dříve. Pokud ne, vznese požadavek na samotný hash oracle, takže v každém případě pro některé . Pak, pokud , Dostaneme, a výstupy jako převrácená hodnota . Jinak se proces zastaví a střídač selže. $F$ $(M,x)$ $F$ $M$ $já$ ${\displaystyle M=M_{i))$ $i$ $h_{i}=y*{r_{i}}^{e}modN$ $x={h_{i}}^{d}=y^{d}*r_{i}modN$ $já$ $y^{d}={\frac {x}{r_{i))}modN$ $y$

Pravděpodobnost, že odpovíme na všechny žádosti o podpis, je minimálně . Potom vypíše inverzní hodnotu for s pravděpodobností . Tedy s pravděpodobností alespoň , vyvozuje opak pro . Funkce je maximální pro a ${\displaystyle p^{q_{\text{sig))))$ $já$ $y$ $F$ $1-p$ $\alpha (p)=p^{q_{\text{sig))}*(1-p)$ $já$ $y$ $F$ $\alpha (p)$ $p_{\text{max}}=1-1/(q_{\text{sig}}+1)$

{\displaystyle \alpha (p_{\text{max)))={\frac {1}{q_{\text{sig))))(1-{\frac {1}{1+q_{\text{ sig))))^{1+q_{\text{sig))))

Dostáváme tedy:

{\begin{aligned}\epsilon (k)&={\frac {1}{\left(1-{\frac {1}{q_{\text{sig}}+1}}\right) ^{q_{\text{sig}}+1}}}\cdot q_{\text{sig}}\cdot \epsilon '\end{aligned}}

Pro ty velké $q_{\text{sig}}$

$\epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '$ .

Průběh je průběžný čas přidaný k času potřebnému k výpočtu hodnot . Je to v podstatě jediný výpočet RSA, což je krychlový čas (nebo lepší). To dává vzorec pro . $já$ $F$ $Ahoj}$ $t$

Konečná zkratka

Kvalita nového snížení nezávisí na počtu hashových volání provedených padělatelem, ale závisí pouze na počtu žádostí o podpis. To má praktický význam, protože v reálných aplikacích je počet volání hashovací funkce omezen pouze zpracovatelským výkonem padělatele, zatímco počet žádostí o podpis může být omezen: podepisující osoba může odmítnout podepsat více než nebo zpráv. Snížení však stále není rigidní a mezi přesným zabezpečením FDH a přesným zabezpečením PSS zůstává značný rozdíl . $2^{20}$ $2^{30}$

V mnoha bezpečnostních důkazech v modelu náhodného orákula musí střídač „uhodnout“, který hash dotaz použije protivník k vytvoření, což má za následek faktor pravděpodobnosti úspěchu. Bylo prokázáno, že nejlepší metodou je zahrnout dotaz jako odpověď na mnoho hashových dotazů, takže je pravděpodobnější, že falešná zpráva bude užitečná pro měnič. Toto pozorování platí také pro schéma podpisu Rabin [6] , schéma podpisu Peye [7] , stejně jako schéma podpisu Gennaro-Halevi-Rabin [8] , u kterého lze koeficient v náhodném věšteckém bezpečnostním důkazu také snížit do . $q_{\text{hash}}$ $y$ $q_{\text{hash}}$ ${\displaystyle q_{sig))$

Poznámky

↑ Nové směry v kryptografii . Získáno 25. prosince 2018. Archivováno z originálu 12. října 2019. (neurčitý)
↑ Metoda pro získávání digitálních podpisů a kryptosystémů s veřejným klíčem . Staženo 25. prosince 2018. Archivováno z originálu 26. prosince 2018. (neurčitý)
↑ Specifikace kryptografie RSA . Staženo 25. prosince 2018. Archivováno z originálu 12. prosince 2018. (neurčitý)
↑ 1 2 Náhodná orákula jsou praktická: paradigma pro navrhování účinných protokolů . Staženo 25. prosince 2018. Archivováno z originálu 24. prosince 2018. (neurčitý)
↑ Přesné zabezpečení digitálních podpisů – Jak podepisovat pomocí RSA a Rabin . Staženo 25. prosince 2018. Archivováno z originálu 23. prosince 2018. (neurčitý)
↑ Digitalizované podpisy a funkce veřejného klíče jsou stejně neovladatelné jako faktorizace . Získáno 25. prosince 2018. Archivováno z originálu 3. listopadu 2018. (neurčitý)
↑ Šifrovací systémy s veřejným klíčem založené na složených třídách stupně reziduozity. Proceedings of Eurocrypt'99 . Získáno 25. prosince 2018. Archivováno z originálu 6. května 2021. (neurčitý)
↑ Bezpečné hash-and-sign podpisy bez náhodného orákula, postup Eurocrypt'99 . Získáno 25. prosince 2018. Archivováno z originálu 14. července 2012. (neurčitý)