VSH

I kryptografi er en Very Smooth Hash (VSH) en n-bit effektiv kryptografisk hashfunktion udviklet i 2005 af Scott Kotini, Lestra Arjen og Ron Steinfeld. Det er modstandsdygtigt over for kollisioner under antagelsen om høj beregningsmæssig kompleksitet ved at finde en ikke-triviel kvadratrod af et meget glat tal modulo n. [1] Begrebet en meget glat funktion betyder, at glathedsgrænsen er en fast polynomisk funktion af n. Denne hashing-algoritme antager en enkelt multiplikation pr. beskedbit og bruger RSA -type aritmetik, hvilket eliminerer behovet for at gemme hashfunktionskoden separat. Derfor er denne algoritme nyttig i indlejrede miljøer, hvor kodepladsen er begrænset. En meget glat hash-funktion kan også bruges til at skabe en envejs hemmelig indtastningsfunktion, der kan anvendes i signaturskemaer for at fremskynde verifikation og forbedre privatlivets fred. $\omega(n)$

VSSR og VSN

For VSH er det vigtigste matematiske problem kollisionsmodstand, som i det væsentlige består i at tage rødder modulo n af meget glatte tal, kaldet meget glatte rødder (VSSR). Til gengæld er problemet med at beregne en meget glat rodmodulo n tæt forbundet med faktoriseringen af heltal ved hjælp af den generelle talfeltsigtemetode . [2] [3]

For faste konstanter c og n kaldes et heltal m et meget jævnt tal, hvis alle primfaktorer af m højst er (log n ) c . Et heltal b er et meget glat kvadratisk modulo n , hvis den største primfaktor b er højst (log n ) c , og der eksisterer et heltal x , således at . Heltallet x kaldes selve kvadratroden modulo b . $b\equiv x^{2}\mod n$

Vi er kun interesserede i rødderne, hvor x 2 ≥ n . Da hvis x 2 < n , så kan roden let beregnes ved hjælp af et felt med karakteristika 0. At beregne en meget glat rod er følgende problem: lad n være produktet af to primtal af omtrent samme størrelse og lad , og være en række af primtal. Givet n , er det nødvendigt at finde , sådan at mindst én af e 0 ,…, e k vil være ulige. ${\displaystyle k\leq (\log n)^{c))$ $p_{1}=2,p_{2}=3,p_{3}=5,\dots$ $x\in \mathbb {Z} _{n}^{*}$ $\textstyle x^{2}\equiv \prod _{i=0}^{k}p_{i}^{e_{i))$

Eksempel på VSN og VSSR

Lad følgende parametre fastsættes: og . $c=5$ $n=31$

Så et meget jævnt tal fra de givne parametre, fordi det er større end alle primfaktorer . På den anden side er der ikke et meget jævnt tal i og . $m_{1}=35=5\cdot 7$ $(\log 31)^{5}~{\dot {=}}~7.37$ $m_1$ $m_{2}=55=5\cdot 11$ $c=5$ $n=31$

Et heltal er et meget glat kvadratisk modulo , fordi det er meget glat (af ) og eksisterer sådan, at (mod ). Dette er en triviel kvadratrod, fordi og så modulet ikke tages i betragtning ved kvadrering. $b_{1}=9$ $n$ $c,n$ $x_{1}=3$ $x_{1}^{2}=b_{1}$ $n$ $3^{2}\not \geq n$

Et heltal er også en kvadratisk modulo-rest . Alle primfaktorer er mindre end 7,37, og alle kvadratrødder modulo er lige , da (mod ). VSSR's opgave er at finde ved hjælp af data og . Og beregningsmæssigt lige så hårdt som faktorisering . $b_{2}=15$ $n$ $x_{2}=20$ $20^{2}=400\equiv 15$ $n$ $x_{2}$ $b_{2}$ $n$ $n$

VSH, grundlæggende algoritme

Lade være en sekvens af primtal. Lad bloklængden, det største heltal, være sådan, at . Lad der være en -bit besked bestående af , som skal hash, med . For at beregne hashen [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
Lad det mindste heltal større end eller lig være antallet af blokke. Lad for $L$ $l/k$ $m_{i}=0$ $l<i\leq Lk$
Lad c være en binær repræsentation af en meddelelse af længde og definere for . $\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$
for hver j = 0, 1,…, L beregner vi $x_{j+1}=x_{j}^{2}\prod _{i=1}^{k}p_{i}^{m_{jk+i}}\mod n$
retur x L + 1 .

Funktionen i trin 4 kaldes komprimeringsfunktionen.

VSH-egenskaber

Du behøver ikke at vide længden af beskeden på forhånd.
Kompleksiteten af kollisionsdetektion er lig med kompleksiteten i at finde en meget glat rod, så VSH er kollisionsbestandig. Kollisionsmodstand er den eneste beviste egenskab for VSH. [5] [6]
Kompressionsfunktionen er ikke kollisionsbestandig. Imidlertid er hash-funktionen kollisionsbestandig baseret på VSSR-antagelsen. Den næste version af VSH* bruger kollisionsbestandig kompression og er 5 gange hurtigere på korte beskeder. [7]
VSH er multiplikativ:

Lad x, y og z være tre-bit strenge af samme længde, hvor z kun består af nul bit og opfylder x OG y = z. Derefter H(z)H(x OR y) ≡ H(x)H(y) (mod n). VSH er ringere end det klassiske midlertidige lagerangreb, der anvendes på multiplikative og additive hashes. [otte]

VSH-variationer

Adskillige forbedringer, speedups og mere effektive varianter af VSH er blevet foreslået [9] . Ingen af dem ændrer det grundlæggende koncept for funktionen:

Kubisk VSH (i stedet for kvadratisk).
VSH med en stigning i antallet af primtal.
VSH med beregnet produkt af primtal.
Hurtig VSH.
Hurtig VSH med øget antal blokke.
VSH-DL

VSH-DL - Diskret logaritme VSH, der ikke har en envejs hemmelig indtastningsfunktion , dens sikkerhed afhænger af vanskeligheden ved at finde den diskrete logaritme modulo et primtal p .

Very Smooth Number Discrete Logaritme (VSDL) er den diskrete logaritme af nogle VSN modulo nogle tal n .

På samme måde som den tidligere introducerede notation tager vi det -th primtal. Lade være en fast konstant og , Være primtal sådan, at og . VSDL-problem: givet for at finde heltal , således at , hvor for alle , desuden er mindst én af dem ikke-nul. $p_{i}$ $jeg$ $c$ $s$ $q$ $p=2q+1$ ${\displaystyle k\leq (\log p)^{c))$ $s$ ${\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))$

Antagelsen af VSDL er, at der ikke er nogen probabilistisk polynomiel-tidsalgoritme, der løser VSDL. Der er en tæt sammenhæng mellem kompleksiteten ved at beregne en VSDL og kompleksiteten ved at beregne en modulo-diskret logaritme . $s$

Se også

Noter

↑ S.Contini, A.Lestra, R.Steinfield. VSH, en effektiv og beviselig kollisionsbestandig hash-funktion. // Eurocrypt. - 2006. - S. 1-2 . Arkiveret fra originalen den 4. december 2018.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, en effektiv og beviselig kollisionsbestandig hash-funktion. // Eurocrypt. - 2006. - S. 3 . Arkiveret fra originalen den 4. december 2018.
↑ Bart Preneel. [ https://www.esat.kuleuven.be/cosic/publications/article-1532.pdf De første 30 års kryptografiske hash-funktioner og NIST SHA-3-konkurrencen] // Kryptografers spor på RSA-konferencen. - 2010. - S. 5 . Arkiveret fra originalen den 11. august 2017.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, en effektiv og beviselig kollisionsbestandig hash-funktion. // Eurocrypt. - 2006. - S. 6 . Arkiveret fra originalen den 4. december 2018.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, en effektiv og beviselig kollisionsbestandig hash-funktion. // Eurocrypt. - 2006. - S. 8 . Arkiveret fra originalen den 4. december 2018.
↑ M.-JOSaarinen. Sikkerhed for VSH i den virkelige verden // INDOCRYPT. - 2006. - S. 2 . Arkiveret fra originalen den 8. august 2017.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, en effektiv og beviselig kollisionsbestandig hash-funktion. // Eurocrypt. - 2006. - S. 14 . Arkiveret fra originalen den 4. december 2018.
↑ M.-JOSaarinen. Sikkerhed for VSH i den virkelige verden // INDOCRYPT. - 2006. - S. 3-4 . Arkiveret fra originalen den 8. august 2017.
↑ S.Contini, A.Lestra, R.Steinfield. VSH, en effektiv og beviselig kollisionsbestandig hash-funktion. // Eurocrypt. - 2006. - S. 10-13 . Arkiveret fra originalen den 4. december 2018.

Litteratur

S. Contini, A. Lestra, R. Steinfield. VSH, en effektiv og beviselig kollisionsbestandig hash-funktion. // Eurocrypt. - 2006. - S. 1-13 .
M.-JOSaarinen. Sikkerhed for VSH i den virkelige verden // INDOCRYPT. – 2006.
Bart Preneel. [ https://www.esat.kuleuven.be/cosic/publications/article-1532.pdf De første 30 år med kryptografisk hash

Funktioner og NIST SHA-3-konkurrencen] // Cryptographers' Track på RSA-konferencen. - 2010. - S. 5 . Arkiveret fra originalen den 11. august 2017.