Koko verkkotunnuksen hash

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 24. tammikuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 30 muokkausta .

Salaustekniikassa Full Domain Hash ( FDH tai Full Domain Hash ) on RSA - pohjainen allekirjoitusjärjestelmä, joka noudattaa hajautus- ja allekirjoitusparadigmaa . Satunnaisessa oraakkelimallissa se on todistetusti turvallinen (eli siihen ei vaikuta mukautuvat valitun viestin hyökkäykset) . FDH sisältää viestin hajauttamisen funktiolla, jonka kuvan koko on RSA -moduulin koko, ja sitten tuloksen nostamisen salaisen RSA - eksponenttipotenssiin .

Johdanto

Siitä lähtien, kun Whitfield Diffie ja Martin Hellman löysivät julkisen avaimen kryptografian [ 1 ] , yksi tärkeimmistä tutkimusaiheista on ollut käytännöllisten ja todistetusti (käytännön ymmärtämisessä) turvallisten salausjärjestelmien kehittäminen. Käytännön turvallisuuden todisteena on yleensä laskennallinen monimutkaisuus tunnetun ongelman ratkaisemisesta kryptojärjestelmän rikkomiseen. Tunnettuja ongelmia ovat suurten kokonaislukujen laskenta, diskreetin logaritmin laskenta modulo alkuluvuksi p tai juurimodulo yhdistelmäkokonaisluvun erottaminen, johon RSA - salausjärjestelmä [2] perustuu .

Hyvin yleinen käytäntö allekirjoittamiseen RSA :lla on ensin tiivistää viesti, lisätä viestiin suola ja sitten nostaa se julkisen avaimen voimaan. Tämä "hash and decrypt" -paradigma on perusta lukuisille standardeille, kuten PKCS # 1 v2.0 [3] . Kaava on ottaa hash-funktio, jonka tulosten koko on täsmälleen moduulin kokoinen: tämä on Full domain hashing -järjestelmä (FDH), jonka esittelivät Bellard [ ja Rogaway artikkelissa "Satunnaiset oraakkelit ovat käytännöllisiä: a paradigma tehokkaiden protokollien suunnitteluun" [4] . FDH-malli on todistetusti turvallinen satunnaisessa oraakkelimallissa olettaen, että RSA : ta on vaikea invertoida , ts. ottaa juuri modulo komposiittikokonaisluku. Bellard ja Rogaway esittelivät satunnaisen oraakkelin metodologian teoksessa "Satunnaiset oraakkelit ovat käytännöllisiä: paradigma tehokkaiden protokollien suunnitteluun" [4] , jossa ne osoittavat, kuinka kehittää erittäin turvallisia allekirjoitusjärjestelmiä mistä tahansa funktiosta, jolla on salainen syöte . Satunnaisessa oraakkelimallissa hash-funktiota käsitellään oraakkelina , joka tuottaa satunnaisen arvon jokaiselle uudelle pyynnölle. Alkuperäisessä paperissa satunnainen oraakkeli muuntaa kiinteäpituisen 0:n ja 1:n sekvenssin äärettömän pituiseksi sekvenssiksi ja valitsee satunnaisesti tarvittavan pituisen osajonon sekvenssistä . Bellardin ja Rogawayn keskeinen työ korostaa, että todistettavan turvallisuuden käytännön soveltamiseksi on tärkeää harkita "kovia" turvallisuuden vähennyksiä. Turvallisuuden heikkeneminen on "kovaa", kun mikä tahansa kryptanalyytikon toiminta allekirjoitusjärjestelmän rikkomiseksi johtaa siihen, että vakiintunut ongelma ratkaistaan riittävällä todennäköisyydellä, mieluiten todennäköisyydellä 1. Tässä tapauksessa allekirjoitusjärjestelmä on melkein yhtä turvallinen kuin vakiintunut ongelma. Sitä vastoin jos supistuminen on "heikko", eli edellä mainittu todennäköisyys on liian pieni, allekirjoitusmallin takuu voi olla melko heikko. ${\{0,1\}}^{*}\longrightarrow {\{0,1\}}^{\infty }$

Määritelmä

Koko verkkotunnuksen hash-allekirjoitusmalli (Gen, Sign, Verify) määritellään seuraavasti. Avainten luontialgoritmi suorittaa RSA:n saadakseen . Se tulostaa missä ja . Allekirjoitus- ja vahvistusalgoritmilla on pääsy oraakkeliin, jossa on hash-toiminto ${\näyttötyyli (N,e,d)}$ ${\näyttötyyli (pk,sk)}$ $pk=(N,e)$ $sk=(N,d)$ $H_{FDH}:{\{0,1\}}\to {\mathbb {Z} _{N}}$

Allekirjoitus ja vahvistus tehdään seuraavasti:

{\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')niin\\return:1\\else\\ return:0\end{aligned}}}

FDH-järjestelmän turvallisuusanalyysi

Bellardin ja Rogwayn lähestymistapa

Lause 1 Oletetaan, että RSA on -secure (todennäköisyydellä ɛ′ kestää t′ aikaa rikkoutua) Silloin FDH-allekirjoituskaavio on -secure, missä $(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}}

Tämän tuloksen haittana on, että se voi olla paljon pienempi kuin . Jos esimerkiksi oletetaan, että kryptanalyytikko voi tiedustella allekirjoitusten määrää ja laskea hajautusarvoja viesteissä, vaikka RSA-inversion todennäköisyys on vain , niin saadaan vain, että todennäköisyys on melkein , mikä ei ole tyydyttävä. Hyväksyttävän turvallisuustason saavuttamiseksi meidän on käytettävä suurempaa moduulikokoa, mikä vaikuttaa positiivisesti piirin tehokkuuteen. $\varepsilon '$ $\varepsilon$ $q_{\text{sig}}=2^{30}$ $q_{\text{hash}}=2^{60}$ $2^{-61}$ $1/2$

Saadakseen sopivimman suojausmarginaalin Bellar ja Rogaway kehittivät uuden järjestelmän, todennäköisyyspohjaisen allekirjoitusmallin , joka tarjoaa tiukan suojauksen vähentämisen: allekirjoituksen väärentämisen todennäköisyys on lähes yhtä pieni kuin inversiolla . Sen sijaan on olemassa vaihtoehtoinen lähestymistapa, jota voidaan soveltaa FDH-järjestelmään paremman rajauksen saamiseksi. [5] ${\näyttötyyli (PSS)}$ $RSA(\varepsilon =\varepsilon ')$

Vaihtoehtoinen lähestymistapa

Toinen pelkistys, joka antaa paremman turvallisuusarvion FDH:lle, perustuu lauseen todistukseen

Lause 2 Olkoon RSA turvallinen. Silloin FDH-allekirjoitusmalli on -secure, missä $(t',\epsilon ')$ ${\näyttötyyli (t,\epsilon )}$

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

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

Määritelmä 1

Invertteriksi kutsutaan RSA:ta rikkovaa algoritmia, jonka onnistumisen todennäköisyys enintään t käsittelyajan jälkeen on vähintään ɛ. $minä$ ${\näyttötyyli (t,\epsilon )}$

Määritelmä 2

Väärentäjä on algoritmi, joka rikkoo allekirjoitusmallia (Gen, Sign, Verify), jos se lähettää enintään tiivisteoraakkelille tehtyjen pyyntöjen, allekirjoitettujen pyyntöjen ja käsittelyajan jälkeen allekirjoituksen väärennöksen todennäköisyydellä vähintään ɛ . $F$ $(t,q_{\text{sig}},q_{\text{hash}},\epsilon )$ $q_{\text{hash}}$ $q_{\text{sig}}$ $t$

Todiste Olkoon väärentäjä , joka rikkoo FDH:n. Oletamme, että se ei koskaan toista samaa hash-oraakkelipyyntöä tai allekirjoituspyyntöä. RSA :ta rikkovan invertterin rakentaminen . Invertteri vastaanottaa syötteenä , jossa on julkinen avain, ja se valitaan satunnaisesti (kaikkien hajautusviestien osajoukosta). Taajuusmuuttaja yrittää etsiä , missä on RSA-funktio, joka on määritetty kohdasta . Invertteri käynnistyy tälle julkiselle avaimelle. Väärentäjä tekee hash-oraakkelipyyntöjä ja allekirjoituspyyntöjä. vastaanottaessaan vastauksen hash-oraakkelilta, se allekirjoittaa ne itsenäisesti. $F$ $(t,q_{\text{sig}},q_{\text{hash}},\epsilon )$ $F$ $minä$ $(t',\epsilon ')$ $minä$ ${\näyttötyyli (N,e,y)}$ ${\näyttötyyli (N,e)}$ $y$ $\mathbb {Z} _{N}$ $minä$ $x=f^{-1}(y)$ $f$ $N,e$ $minä$ $F$ $F$ $minä$

Yksinkertaisuuden vuoksi oletetaan, että kun se pyytää allekirjoittamaan viestin , se on jo tehnyt vastaavan pyynnön hash-oraakkelille . Jos ei, jatkamme ja luomme itsenäisesti hash-oracle-pyynnön viestille . Invertteri käyttää laskuria , joka on alun perin asetettu nollaan. Kun hajautusoraakkelilta kysytään viestiä , invertteri kasvaa , sovittaa tiivistetyn viestin alkuperäiseen viestiin ja valitsee satunnaisluvun . sitten palauttaa todennäköisyydellä ja todennäköisyydellä . Tässä on kiinteä todennäköisyys, joka määritetään myöhemmin. Allekirjoituspyyntöä tehdessään se on jo pyytänyt tiivistettä , joten joillekin .If :lle se palaa allekirjoituksena. Muuten prosessi pysähtyy ja invertteri epäonnistuu. $F$ $M$ $M$ $M$ $minä$ $i$ $F$ $M$ $minä$ $i$ $M_{i}=M$ $r_{i}$ $\mathbb {Z} _{N}$ $minä$ $h_{i}=r_{i}^{e}modN$ $s$ $h_{i}=y*r_{i}^{e}modN$ $1-s$ $s$ $F$ $M$ $M$ ${\näyttötyyli M=M_{i))$ $i$ $h_{i}={r_{i}}^{e}modN$ $minä$ ${\displaystyle r_{i))$

Lopulta lopettaa työn ja näyttää väärennöksen . Oletamme, että tiivistettä pyydettiin aiemmin. Jos ei, se tekee pyynnön itse hash-oraakkelille, joten joka tapauksessa joillekin . Sitten, jos , saamme ja tulostaa käänteislukuna . Muuten prosessi pysähtyy ja invertteri epäonnistuu. $F$ ${\näyttötyyli (M,x)}$ $F$ $M$ $minä$ ${\näyttötyyli M=M_{i))$ $i$ $h_{i}=y*{r_{i}}^{e}modN$ $x={h_{i}}^{d}=y^{d}*r_{i}modN$ $minä$ $y^{d}={\frac {x}{r_{i))}modN$ $y$

Todennäköisyys, että vastaamme kaikkiin allekirjoituspyyntöihin, on vähintään . Tulostaa sitten käänteisarvon todennäköisyydellä . Näin ollen ainakin todennäköisyydellä , päättelee päinvastaista varten . Toiminto on maksimi ja ${\displaystyle p^{q_{\text{sig))))$ $minä$ $y$ $f$ $1-s$ $\alpha (p)=p^{q_{\text{sig))}*(1-p)$ $minä$ $y$ $f$ ${\näyttötyyli \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))))

Siten saamme:

{\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}}

Isoille _ $q_{\text{sig}}$

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

Ajoaika on käyntiaika, joka lisätään arvojen laskemiseen tarvittavaan aikaan . Se on pohjimmiltaan yksi RSA-laskenta, joka on kuutioaika (tai parempi). Tämä antaa kaavan . $minä$ $F$ $Hei}$ $t$

Lopullinen lyhenne

Uuden vähennyksen laatu ei riipu väärentäjän tekemien hash-kutsujen määrästä, vaan riippuu vain allekirjoituspyyntöjen määrästä. Tällä on käytännön merkitystä, koska todellisissa sovelluksissa hash-funktiokutsujen määrää rajoittaa vain väärentäjän prosessointiteho, kun taas allekirjoituspyyntöjen määrää voidaan rajoittaa: allekirjoittaja voi kieltäytyä allekirjoittamasta enemmän kuin tai viestejä. Vähennys ei kuitenkaan ole vielä jäykkää, ja FDH:n tarkan turvallisuuden ja PSS :n tarkan turvallisuuden välillä on edelleen merkittävä ero . $2^{20}$ $2^{30}$

Monissa satunnaisen oraakkelimallin turvatodistuksissa invertterin on "arvattava", mitä hash-kyselyä vastustaja käyttää väärentämiseen, mikä johtaa onnistumisen todennäköisyyteen. On todistettu, että paras tapa on sisällyttää kysely vastauksena moniin hash-kyselyihin, jotta huijauksesta on todennäköisemmin hyötyä invertterille. Tämä havainto pätee myös Rabinin allekirjoitusskeemaan [6] , Peyen allekirjoitusskeemaan [7] sekä Gennaro-Halevi-Rabinin allekirjoitusskeemaan [8] , jonka kerrointa satunnaisen oraakkelin turvatodistuksessa voidaan myös pienentää. . _ $q_{\text{hash}}$ $y$ $q_{\text{hash}}$ ${\displaystyle q_{sig))$

Muistiinpanot

↑ Uudet suunnat kryptografiassa . Haettu 25. joulukuuta 2018. Arkistoitu alkuperäisestä 12. lokakuuta 2019. (määrätön)
↑ Menetelmä digitaalisten allekirjoitusten ja julkisen avaimen salausjärjestelmien hankkimiseksi . Haettu 25. joulukuuta 2018. Arkistoitu alkuperäisestä 26. joulukuuta 2018. (määrätön)
↑ RSA-salauksen tekniset tiedot . Haettu 25. joulukuuta 2018. Arkistoitu alkuperäisestä 12. joulukuuta 2018. (määrätön)
↑ 1 2 Satunnaiset oraakkelit ovat käytännöllisiä: paradigma tehokkaiden protokollien suunnittelussa . Haettu 25. joulukuuta 2018. Arkistoitu alkuperäisestä 24. joulukuuta 2018. (määrätön)
↑ Digitaalisten allekirjoitusten tarkka turvallisuus - Kuinka allekirjoittaa RSA:lla ja Rabinilla . Haettu 25. joulukuuta 2018. Arkistoitu alkuperäisestä 23. joulukuuta 2018. (määrätön)
↑ Digitaaliset allekirjoitukset ja julkisen avaimen toiminnot ovat yhtä vaikeaselkoisia kuin tekijöiden lisääminen . Haettu 25. joulukuuta 2018. Arkistoitu alkuperäisestä 3. marraskuuta 2018. (määrätön)
↑ Julkisen avaimen salausjärjestelmät, jotka perustuvat yhdistelmätutkintojäännösluokkiin. Proceedings of Eurocrypt'99 . Haettu 25. joulukuuta 2018. Arkistoitu alkuperäisestä 6. toukokuuta 2021. (määrätön)
↑ Suojaa hajautus- ja allekirjoitusallekirjoitukset ilman satunnaista oraakkelia, Eurocrypt'99:n prosessi . Haettu 25. joulukuuta 2018. Arkistoitu alkuperäisestä 14. heinäkuuta 2012. (määrätön)