VSH

V kryptografii je Very Smooth Hash (VSH) n-bitová efektivní kryptografická hashovací funkce vyvinutá v roce 2005 Scottem Kotinim, Lestrou Arjen a Ronem Steinfeldem. Je odolný proti kolizím za předpokladu vysoké výpočetní náročnosti nalezení netriviální druhé odmocniny z velmi hladkého čísla modulo n. [1] Koncept velmi hladké funkce znamená, že hranice hladkosti je pevnou polynomickou funkcí n. Tento hashovací algoritmus předpokládá jediné násobení na bit zprávy a používá aritmetiku typu RSA , což eliminuje potřebu ukládat kód hashovací funkce samostatně. Proto je tento algoritmus užitečný v embedded prostředích, kde je omezený kódový prostor. Velmi hladkou hashovací funkci lze také použít k vytvoření funkce jednosměrného tajného vstupu , kterou lze použít v podpisových schématech pro urychlení ověřování a zvýšení soukromí. $\omega(n)$

VSSR a VSN

Pro VSH je hlavním matematickým problémem odolnost proti kolizi, která v podstatě spočívá v zakořenění modulo n velmi hladkých čísel, nazývaných velmi hladké kořeny (VSSR). Na druhé straně problém výpočtu velmi hladkého kořenového modulu n úzce souvisí s faktorizací celých čísel pomocí metody obecného číselného pole síta . [2] [3]

Pro pevné konstanty c a n se celé číslo m nazývá velmi hladké číslo, jestliže všechny prvočinitele m jsou nejvýše (log n ) c . Celé číslo b je velmi hladký kvadratický modulo n , jestliže největší prvočíslo b je nejvýše (log n ) c a existuje celé číslo x takové, že . Celé číslo x se nazývá velmi odmocnina modulo b . $b\equiv x^{2}\mod n$

Zajímají nás pouze kořeny, kde x 2 ≥ n . Protože je-li x 2 < n , pak lze kořen snadno vypočítat pomocí pole charakteristiky 0. Výpočet velmi hladkého kořene je následující problém: nechť n je součin dvou prvočísel přibližně stejné velikosti a nechť , a být posloupností prvočísel. Je-li dáno n , je nutné najít takové, že alespoň jedno z e 0 ,…, e k bude liché. ${\displaystyle k\leq (\log n)^{c))$ $p_{1}=2,p_{2}=3,p_{3}=5,\tečky$ $x\in \mathbb {Z} _{n}^{*}$ $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i))$

Příklad VSN a VSSR

Nechť jsou pevné následující parametry: a . $c=5$ $n=31$

Potom velmi hladké číslo z daných parametrů, protože je větší než všechny prvočinitele . Na druhou stranu není příliš hladké číslo v a . $m_{1}=35=5\cdot 7$ $(\log 31)^{5}~{\dot {=}}~7,37$ $m_1$ $m_{2}=55=5\cdot 11$ $c=5$ $n=31$

Celé číslo je velmi hladké kvadratické modulo , protože je velmi hladké (of ) a existuje tak, že (mod ). Toto je triviální druhá odmocnina, protože modul se při kvadraturaci nebere v úvahu. $b_{1}=9$ $n$ $c,n$ $x_{1}=3$ $x_{1}^{2}=b_{1}$ $n$ $3^{2}\not \geq n$

Celé číslo je také kvadratický modulový zbytek . Všechny prvočinitele jsou menší než 7,37 a všechny odmocniny modulo se rovnají , protože (mod ). Úkolem VSSR je najít podle dat a . A výpočetně stejně těžké jako faktorizace . $b_{2}=15$ $n$ $x_{2}=20$ $20^{2}=400\equiv 15$ $n$ $x_{2}$ $b_{2}$ $n$ $n$

VSH, základní algoritmus

Nechť je posloupnost prvočísel. Nechť délka bloku, největší celé číslo, je taková, že . Nechť existuje -bitová zpráva skládající se z , která musí být hašována s . Chcete-li vypočítat hash [4] : $p_{1}=2,p_{2}=3,\ldots$ $k$ $\textstyle \prod _{i=1}^{k}p_{i}<n$ $m$ $\ell$ $(m_{1},\ldots ,m_{\ell })$ ${\displaystyle \ell <2^{k))$ $m$

x0 = 1
Nechť nejmenší celé číslo větší nebo rovné je počet bloků. Nechat pro $L$ $l/k$ $m_{i}=0$ $l<i\leq Lk$
Nechť c je binární reprezentace zprávy délky a definujte pro . $\textstyle \ell =\sum _{i=1}^{k}l_{i}2^{i-1}$ $\ell _{i}\in \{0,1\}$ $\ell$ ${\displaystyle m_{Lk+i}=\ell _{i))$ $1\leq i\leq k$
pro každé j = 0, 1,…, L vypočítáme $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$
návrat x L + 1 .

Funkce v kroku 4 se nazývá kompresní funkce.

Vlastnosti VSH

Délku zprávy nemusíte znát předem.
Složitost detekce kolizí se rovná složitosti nalezení velmi hladkého kořene, takže VSH je odolný proti kolizi. Odolnost proti kolizi je jedinou prokázanou vlastností VSH. [5] [6]
Kompresní funkce není odolná proti kolizi. Hašovací funkce je však odolná proti kolizi na základě předpokladu VSSR. Další verze VSH* používá kompresi odolnou proti kolizím a je 5krát rychlejší u krátkých zpráv. [7]
VSH je multiplikativní:

Nechť x, y a z jsou tříbitové řetězce stejné délky, kde z se skládá pouze z nulových bitů a splňuje x AND y = z. Potom H(z)H(x OR y) ≡ H(x)H(y) (mod n). VSH je horší než klasický útok na dočasné úložiště, který se používá na multiplikativní a aditivní hash. [osm]

Variace VSH

Bylo navrženo několik vylepšení, zrychlení a účinnějších variant VSH [9] . Žádný z nich nemění základní koncept funkce:

Kubický VSH (místo kvadratického).
VSH se zvýšením počtu prvočísel.
VSH s vypočteným součinem prvočísel.
Rychlé VSH.
Rychlé VSH se zvýšeným počtem bloků.
VSH-DL

VSH-DL - Diskrétní logaritmus VSH, který nemá funkci jednosměrného tajného vstupu , jeho bezpečnost závisí na obtížnosti nalezení diskrétního logaritmu modulo a prvočíslo p .

Velmi hladký číselný diskrétní logaritmus (VSDL) je diskrétní logaritmus nějakého modulu VSN s určitým číslem n .

Podobně jako u dříve představeného zápisu bereme jako -té prvočíslo. Dovolit být pevná konstanta a , být prvočísla taková, že a . VSDL-problém: dá se najít celá čísla taková, že , kde pro všechny , navíc alespoň jedno z nich je nenulové. $p_{i}$ $i$ $C$ $p$ $q$ $p=2q+1$ ${\displaystyle k\leq (\log p)^{c))$ $p$ ${\displaystyle e_{1},...,e_{k))$ $2^{e_{1}}\equiv \prod _{i=2}^{k}p_{i}^{e_{i}}\mod p$ $|e_{i}|<q$ $i=1,...,k$ ${\displaystyle e_{1},...,e_{k))$

Předpokladem VSDL je, že neexistuje žádný pravděpodobnostní polynomiální-časový algoritmus, který řeší VSDL. Existuje úzký vztah mezi složitostí výpočtu VSDL a složitostí výpočtu modulového diskrétního logaritmu . $p$

Viz také

Poznámky

↑ S.Contini, A.Lestra, R.Steinfield. VSH, efektivní a prokazatelná hašovací funkce odolná proti kolizi. // Eurocrypt. - 2006. - S. 1-2 . Archivováno z originálu 4. prosince 2018.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, efektivní a prokazatelná hašovací funkce odolná proti kolizi. // Eurocrypt. - 2006. - S. 3 . Archivováno z originálu 4. prosince 2018.
↑ Bart Preneel. [ https://www.esat.kuleuven.be/cosic/publications/article-1532.pdf Prvních 30 let kryptografických hashovacích funkcí a soutěž NIST SHA-3] // Stopa kryptografů na konferenci RSA. - 2010. - S. 5 . Archivováno z originálu 11. srpna 2017.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, efektivní a prokazatelná hašovací funkce odolná proti kolizi. // Eurocrypt. - 2006. - S. 6 . Archivováno z originálu 4. prosince 2018.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, efektivní a prokazatelná hašovací funkce odolná proti kolizi. // Eurocrypt. - 2006. - S. 8 . Archivováno z originálu 4. prosince 2018.
↑ M.-JOSaarinen. Bezpečnost VSH v reálném světě // INDOCRYPT. - 2006. - S. 2 . Archivováno z originálu 8. srpna 2017.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, efektivní a prokazatelná hašovací funkce odolná proti kolizi. // Eurocrypt. - 2006. - S. 14 . Archivováno z originálu 4. prosince 2018.
↑ M.-JOSaarinen. Bezpečnost VSH v reálném světě // INDOCRYPT. - 2006. - S. 3-4 . Archivováno z originálu 8. srpna 2017.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, efektivní a prokazatelná hašovací funkce odolná proti kolizi. // Eurocrypt. - 2006. - S. 10-13 . Archivováno z originálu 4. prosince 2018.

Literatura

S.Contini, A.Lestra, R.Steinfield. VSH, efektivní a prokazatelná hašovací funkce odolná proti kolizi. // Eurocrypt. - 2006. - S. 1-13 .
M.-JOSaarinen. Bezpečnost VSH v reálném světě // INDOCRYPT. — 2006.
Bart Preneel. [ https://www.esat.kuleuven.be/cosic/publications/article-1532.pdf Prvních 30 let kryptografického hash

Funkce a soutěž NIST SHA-3] // Stopa kryptografů na konferenci RSA. - 2010. - S. 5 . Archivováno z originálu 11. srpna 2017.