Full domän hash

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 januari 2019; kontroller kräver 30 redigeringar .

Inom kryptografi är Full Domaine Hash ( FDH eller Full Domain Hash ) ett RSA -baserat signaturschema som följer hash- och signaturparadigmet . Den är bevisligen säker (det vill säga opåverkad av adaptiva attacker med valt meddelande) i den slumpmässiga orakelmodellen . FDH involverar att hasha meddelandet med en funktion vars bildstorlek är storleken på RSA -modulen, och sedan höja resultatet till den hemliga RSA- exponentpotentialen .

Inledning

Sedan upptäckten av kryptografi med offentlig nyckel av Whitfield Diffie och Martin Hellman [ 1 ] har ett av de viktigaste forskningsämnena varit utvecklingen av praktiska och bevisligen (i praktisk förståelse) säkra kryptosystem. Beviset på praktisk säkerhet är vanligtvis den beräkningsmässiga komplexiteten från att lösa ett välkänt problem till att bryta ett kryptosystem. Välkända problem inkluderar faktorisering av stora heltal , att beräkna den diskreta logaritmen modulo ett primtal p, eller extrahera en rotmodulo ett sammansatt heltal, som RSA -kryptosystemet [2] är baserat på .

En mycket vanlig praxis för att signera med RSA är att först hasha meddelandet, lägga till ett salt till meddelandet och sedan höja det till makten för den publika nyckeln. Detta "hash and decrypt" paradigm är grunden för många standarder som PKCS # 1 v2.0 [3] . Schemat är att ta en hashfunktion vars utdatastorlek är exakt storleken på modulen: detta är hela domänhashingschemat (FDH) introducerat av Bellard och Rogaway i artikeln "Slumpmässiga orakel är praktiska: a paradigm för att designa effektiva protokoll" [4] . FDH-schemat är bevisligen säkert i den slumpmässiga orakelmodellen, förutsatt att det är svårt att invertera RSA , d.v.s. ta en rotmodulo ett sammansatt heltal. Den slumpmässiga orakelmetodiken introducerades av Bellard och Rogaway i "Random oracles are practice: a paradigm for designing efficient protocols" [4] , där de visar hur man utvecklar mycket säkra signaturscheman från vilken funktion som helst med en hemlig ingång . I den slumpmässiga orakelmodellen behandlas en hashfunktion som ett orakel som producerar ett slumpmässigt värde för varje ny begäran. I originalpapperet omvandlar ett slumpmässigt orakel en sekvens av nollor och 1:or med fast längd till en sekvens med oändlig längd och väljer slumpmässigt en undersekvens av den nödvändiga längden från sekvensen . Bellard och Rogaways framstående arbete betonar att för den praktiska tillämpningen av bevisbar säkerhet är det viktigt att överväga "hårda" säkerhetsminskningar. En säkerhetsförsämring är "svår" när någon åtgärd från kryptoanalytikern för att bryta signaturschemat resulterar i att ett väletablerat problem löses med tillräcklig sannolikhet, helst med en sannolikhet på 1. I det här fallet är signaturschemat nästan lika säkert som det väletablerade problemet. Om kontraktionen däremot är "svag", dvs. den tidigare nämnda sannolikheten är för liten, kan garantin för signaturschemat vara ganska svag. ${\{0,1\}}^{*}\longrightarrow {\{0,1\}}^{\infty }$

Definition

Hela domänens hash-signaturschema (Gen, Sign, Verify) definieras enligt följande. Nyckelgenereringsalgoritmen kör RSA för att få . Den matar ut var och . Signatur- och verifieringsalgoritmen har tillgång till ett orakel med en hashfunktion $(N,e,d)$ $(pk,sk)$ $pk=(N,e)$ $sk=(N,d)$ $H_{FDH}:{\{0,1\}}\to {\mathbb {Z} _{N}}$

Signering och verifiering görs enligt följande:

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

Säkerhetsanalys av FDH-schemat

Bellard och Rogways tillvägagångssätt

Sats 1 Antag att RSA är -säkert (med sannolikhet ɛ′ tar det t′ tid att bryta) Då är FDH-signaturschemat -säkert, där $(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}}

Nackdelen med detta resultat är att det kan vara mycket mindre än . Till exempel, om vi antar att en kryptoanalytiker kan fråga antalet signaturer och beräkna hash för meddelanden även om sannolikheten för RSA-inversion bara är , då får vi bara att sannolikheten är nästan , vilket inte är tillfredsställande. För att få en acceptabel säkerhetsnivå måste vi använda en större modulstorlek, vilket kommer att påverka kretsens effektivitet positivt. $\varepsilon '$ $\varepsilon$ $q_{\text{sig}}=2^{30}$ $q_{\text{hash}}=2^{60}$ $2^{-61}$ $1/2$

För att få den mest lämpliga säkerhetsmarginalen utvecklade Bellar och Rogaway ett nytt schema, det probabilistiska signaturschemat , som ger en strikt säkerhetsreduktion: sannolikheten för signaturförfalskning är nästan lika liten som med inversion . Istället finns det ett alternativt tillvägagångssätt som kan tillämpas på FDH-schemat för att få en bättre gräns. [5] $(PSS)$ $RSA(\varepsilon =\varepsilon ')$

Alternativt tillvägagångssätt

En annan minskning som ger en bättre säkerhetsuppskattning för FDH är baserad på beviset för satsen

Sats 2 Låt RSA vara säker. Då är FDH-signaturschemat -säkert, där $(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}}

För stora , . $q_{\text{sig}}$ $\epsilon \sim \exp(1)\cdot q_{\text{sig}}\cdot \epsilon '$

Definition 1

Vi kommer att kalla en växelriktare för en algoritm som bryter RSA, vars sannolikhet för att lyckas efter att inte mer än t behandlingstid har förflutit är minst ɛ. $jag$ $(t,\epsilon )$

Definition 2

En förfalskare är en algoritm som bryter mot signaturschemat (Gen, Sign, Verify) om den, efter inte mer än förfrågningar till hash-oraklet, signerade förfrågningar och bearbetningstid, matar ut en signaturförfalskning med en sannolikhet på minst ɛ . $F$ $(t,q_{\text{sig}},q_{\text{hash}},\epsilon )$ $q_{\text{hash}}$ $q_{\text{sig}}$ $t$

Bevis Låt vara en förfalskare som bryter mot FDH. Vi antar att vi aldrig upprepar samma hash-oracle-begäran eller signaturbegäran. Att bygga en växelriktare som knäcker RSA. Växelriktaren tar emot som ingång , där är den publika nyckeln, och väljs slumpmässigt i (en delmängd av alla hashade meddelanden) . Växelriktaren försöker hitta var RSA-funktionen definieras från . Växelriktaren startar för denna publika nyckel. Förfalskaren gör hash-orakelförfrågningar och signaturförfrågningar. får ett svar från hash-oraklet, signerar det dem självständigt. $F$ $(t,q_{\text{sig}},q_{\text{hash}},\epsilon )$ $F$ $jag$ $(t',\epsilon ')$ $jag$ $(N,e,y)$ $(N,e)$ $y$ $\mathbb {Z} _{N}$ $jag$ $x=f^{-1}(y)$ $f$ $N,e$ $jag$ $F$ $F$ $jag$

För enkelhetens skull antar vi att när den gör en begäran om att signera ett meddelande har den redan gjort en motsvarande begäran till hash-oraklet för . Om inte, fortsätter vi och skapar självständigt en hash-oracle-begäran för meddelandet Växelriktaren använder en räknare som initialt är inställd på noll. När du frågar hash-oraklet efter ett meddelande , ökar växelriktaren , matchar det hashade meddelandet med det ursprungliga meddelandet och väljer ett slumpmässigt nummer i . återkommer sedan med sannolikhet och med sannolikhet . Här finns en fast sannolikhet, som kommer att fastställas senare. När man gör en signaturbegäran för , har den redan begärt en hash , så för vissa .If , så återgår den som en signatur. Annars stannar processen och växelriktaren misslyckas. $F$ $M$ $M$ $M$ $jag$ $i$ $F$ $M$ $jag$ $i$ $M_{i}=M$ $r_{i}$ $\mathbb {Z} _{N}$ $jag$ $h_{i}=r_{i}^{e}modN$ $sid$ $h_{i}=y*r_{i}^{e}modN$ $1-s$ $sid$ $F$ $M$ $M$ ${\displaystyle M=M_{i))$ $i$ $h_{i}={r_{i}}^{e}modN$ $jag$ ${\displaystyle r_{i))$

Till slut avslutar jobbet och visar en falsk . Vi antar att hashen efterfrågades tidigare. Om inte gör den en förfrågan till hash-oraklet själv, så i alla fall för vissa . Sedan, om , vi får, och utgångar som den ömsesidiga av . Annars stannar processen och växelriktaren misslyckas. $F$ $(M,x)$ $F$ $M$ $jag$ ${\displaystyle M=M_{i))$ $i$ $h_{i}=y*{r_{i}}^{e}modN$ $x={h_{i}}^{d}=y^{d}*r_{i}modN$ $jag$ $y^{d}={\frac {x}{r_{i))}modN$ $y$

Sannolikheten att vi kommer att svara på alla signaturförfrågningar är minst . Skriver sedan ut inversen för med sannolikhet . Således, med sannolikhet åtminstone , drar slutsatsen motsatsen för . Funktionen är maximal för och ${\displaystyle p^{q_{\text{sig))))$ $jag$ $y$ $f$ $1-s$ $\alpha (p)=p^{q_{\text{sig))}*(1-p)$ $jag$ $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))))

Därför får vi:

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

För de stora $q_{\text{sig}}$

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

Drifttiden är den löptid som läggs till den tid som krävs för att beräkna värdena . Det är i huvudsak en enda RSA-beräkning, vilket är kubiktid (eller bättre). Detta ger formeln för . $jag$ $F$ $Hej}$ $t$

Slutlig förkortning

Kvaliteten på den nya minskningen beror inte på antalet hash-anrop som förfalskaren gör, och beror bara på antalet signaturförfrågningar. Detta är av praktisk betydelse, eftersom antalet hashfunktionsanrop i verkliga applikationer endast begränsas av förfalskarens processorkraft, medan antalet signaturförfrågningar kan begränsas: undertecknaren kan vägra att underteckna mer än eller meddelanden. Minskningen är dock fortfarande inte stel och det finns fortfarande ett betydande gap mellan den exakta säkerheten för FDH och den exakta säkerheten för PSS . $2^{20}$ $2^{30}$

I många säkerhetsbevis i den slumpmässiga orakelmodellen måste växelriktaren "gissa" vilken hashfråga som kommer att användas av motståndaren att förfalska, vilket resulterar i en faktor i sannolikheten för framgång. Det har bevisats att den bästa metoden är att inkludera en fråga som svar på många hash-förfrågningar så att spoofen är mer sannolikt att vara användbar för växelriktaren. Denna observation gäller även för Rabins signaturschema [6] , Peyes signaturschema [7] , såväl som för Gennaro-Halevi-Rabins signaturschema [8] , för vilket koefficienten i det slumpmässiga orakelsäkerhetsbeviset också kan reduceras till . $q_{\text{hash}}$ $y$ $q_{\text{hash}}$ ${\displaystyle q_{sig))$

Anteckningar

↑ Nya riktningar i kryptografi . Hämtad 25 december 2018. Arkiverad från originalet 12 oktober 2019. (obestämd)
↑ En metod för att erhålla digitala signaturer och kryptosystem med publik nyckel . Hämtad 25 december 2018. Arkiverad från originalet 26 december 2018. (obestämd)
↑ RSA-kryptografispecifikationer . Hämtad 25 december 2018. Arkiverad från originalet 12 december 2018. (obestämd)
↑ 1 2 Slumpmässiga orakel är praktiska: ett paradigm för att designa effektiva protokoll . Hämtad 25 december 2018. Arkiverad från originalet 24 december 2018. (obestämd)
↑ Den exakta säkerheten för digitala signaturer - Hur man signerar med RSA och Rabin . Hämtad 25 december 2018. Arkiverad från originalet 23 december 2018. (obestämd)
↑ Digitaliserade signaturer och offentliga nyckelfunktioner lika svårlösta som faktorisering . Hämtad 25 december 2018. Arkiverad från originalet 3 november 2018. (obestämd)
↑ Kryptosystem med offentliga nyckel baserade på sammansatta restklasser. Proceedings of Eurocrypt'99 . Hämtad 25 december 2018. Arkiverad från originalet 6 maj 2021. (obestämd)
↑ Säkra hash-and-sign-signaturer utan det slumpmässiga oraklet, processer av Eurocrypt'99 . Hämtad 25 december 2018. Arkiverad från originalet 14 juli 2012. (obestämd)