Enkelriktad funktion med hemlig entré

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 10 september 2017; kontroller kräver 37 redigeringar .

En enkelriktad funktion med hemlig ingång ( eng. falldörrsfunktion , TDF ) är en enkelriktad funktion från uppsättning till uppsättning , som har en egenskap (hemlig ingång, kryphål), tack vare vilken det blir möjligt att hitta för någon sådan det vill säga invertera funktionen. $f$ $X$ $Y$ $y\in Im{f},x\in X$ $f(x) = y$

Envägs hemliga inträdesfunktioner används ofta i asymmetriska krypteringsmetoder (public key-kryptering) såsom: RSA , Rabin-funktion , ElGamal- scheman , McEliece kryptosystem , NTRUEncrypt kryptografiskt system , Polly Cracker, och även mindre populärt på grund av dess kryptografiska instabilitet, ryggsäckskryptosystem Merkle-Hellman .

För närvarande är det inte säkert fastställt att enkelriktade funktioner med hemlig ingång verkligen är enkelriktade, det vill säga det finns inga bevis för att en kryptoanalytiker inte kan vända på funktionen utan att känna till den hemliga ingången.

Definition

Funktion , var $f:\{0,1\}^{l(n)}\times \{0,1\}^{n}{\xrightarrow[{}]{}}\{0,1\}^ {m(n)}$

$\{0,1\}^{l(n)}$ - uppsättning offentliga nycklar,

${\displaystyle \{0,1\}^{m(n)))$ är ett displayelement som består av n bitar,

kallas enkelriktad med hemlig ingång, om

Det är ensidigt ;
Det finns en effektiv algoritm som, givet den publika nyckeln , meddelandet och värdet för funktionen, beräknar så att för någon nyckel ; $Y$ $M$ $M'$ $f(M)=f(M')$ $Z$
För ett givet meddelande och funktion är det svårt att hitta ett meddelande som . $M$ $f(M)$ $M'\neq M$ $f(M)=f(M')$

Historik

Utveckling av enkelriktade funktioner med hemlig ingång

Idén om en bakdörrsfunktion introducerades i mitten av 1970-talet efter publiceringen av en artikel av Whitfield Diffie , Martin Hellman och Ralph Merkle om asymmetriska krypteringsmetoder (public key-kryptering). Det var Diffie och Hellman som myntade termen [1] . Men det första systemet där sådana idéer användes anses vara ett system som uppfanns 1973 av Clifford Cox , som arbetade på regeringens kommunikationscenter ( GCHQ ), men detta arbete bevarades endast i centrets interna dokument , så dess existens var inte känd förrän 1977 [2] .

Artikeln beskrev en ny metod för att minimera behovet av att överföra nycklar över säkra kanaler, och den tog också isär ett kryptografiskt system som kan användas för att skapa en digital signatur [3] .

Författarna har visat att en envägsfunktion för hemlig inmatning kan användas i kryptosystem med publika nyckel och digitala signaturenheter [4] . Ett kryptosystem med publik nyckel är ett system där den publika nyckeln sänds över en osäker kanal. Innebörden av en digital signatur är att när han skickar ett signerat meddelande från Alice till Bob kan Bob verifiera att meddelandet faktiskt skickades av Alice.

Tack vare envägs hemliga inmatningsfunktioner kan olika hemliga inmatningschiffer implementeras som är kryptografiskt säkra [1] .

Flera klasser av funktioner föreslogs, men det stod snart klart att lämpliga funktioner var svårare att hitta än man ursprungligen trodde. Till exempel var det först tänkt att använda funktioner baserade på delmängdssummaproblemet . Det stod snart klart att denna metod var oacceptabel. Ett exempel på en sådan implementering är Merkle-Hellman ryggsäckskryptosystem .

År 2005 var de mest lämpliga kandidaterna för envägsbakdörrsfunktioner de från RSA- och Rabinklasserna [5] . Dessa funktioner använder exponentieringsmodulo ett sammansatt tal, och båda är baserade på heltalsfaktoriseringsproblemet .

2008 introducerades envägsfunktioner för bakdörr, vilket gjorde att information om det ursprungliga meddelandet gick förlorad.

Utveckling av enkelriktade, förlustfria, bakdörrsfunktioner

Denna typ av funktion ( förlustfälld lucka funktion ), baserad på idén om att skada en betydande del av informationen [6] , introducerades av Chris Peikert och Brent Waters [7] i synnerhet, som ett medel att konstruera ett krypteringsschema för publik nyckel med en vald krypterad text.

Uppsättningen av dessa funktioner består av en familj med två funktioner:

De upprepar arbetet med en enkelriktad funktion med en hemlig ingång utan att förlora en del av informationen, det vill säga om det finns ett "kryphål", kan det effektivt beräknas från värdet på . $x$ $f(x)$
De förlorar en del av informationen om ingången, då har utmatningen många förbilder (det vill säga det är omöjligt att unikt invertera funktionen). $f(x)$

Nyckelpunkten är att de valda funktionsfamiljerna är polynomiellt omöjliga att särskilja . Därför kan nycklar ersättas med nycklar med förlust utan att meddela någon. Men när alla nycklar är förlorade innehåller chiffertexten inte längre (väsentlig) information om det krypterade meddelandet. Samtidigt, om man helt enkelt ersätter kryphålsfunktionen med en förlustfunktion, finns det inget sätt att svara ens på en välformad dekrypteringsförfrågan, eftersom klartextinformationen kommer att gå förlorad. Därför används mer fullständiga abstraktioner

Enkelriktade funktioner med hemlig ingång "Allt utom en"

En all-but-one (ABO)-funktion kan byggas från en uppsättning envägsfunktioner med hemlig inmatning och tillräcklig informationsförlust.

Uppsättningen ABO-funktioner är associerad med uppsättningen , vars element kallas förgrenar. ABO-funktionsgeneratorn tar en extra parameter , som kallas förlustgrenen, och matar ut en funktion och en bakdörr t. Funktionen har egenskapen att funktionen för vilken gren som helst har en dold ingång (och kan inverteras med ), men funktionen är en förlustlös funktion. Dessutom döljs förlustgrenen (beräkningsmässigt) av beskrivningen av . [8] . $B$ $b^{*}\in B$ $g({\cdot },{\cdot })$ $g$ $b\not =b^{*}$ $g(b,\cdot )$ $t$ $g(b^{*},\cdot )$ $g$

Enkelriktade funktioner med hemlig ingång "Allt-utom-N"

All-but-N (ABN)-funktioner har exakt förlustgivande grenar; alla andra filialer har en hemlig ingång. Detta kan användas för att lokalisera chiffertexter med hjälp av förlustgrenar - alla andra chiffertexter matchar bakdörrsfunktioner och kan dekrypteras. Observera att ABN:n kodar en uppsättning förlustfördelar med sin nyckel. Det vill säga, en beräkningsmässigt obegränsad motståndare kan alltid använda brute force för att hitta grenar som leder till en förlustfunktion. $N$

Därför har ABN-funktioner en allvarlig nackdel: nycklarnas rumsliga komplexitet är nämligen linjär i [9] $N.$

Envägs alla-utom många hemliga inmatningsfunktioner

Funktionen allt-utom-många (ABM) har en superpolynomuppsättning av förlustgrenar som kräver en speciell bakdörr.

Den viktigaste skillnaden från ABN-funktionen är att med ABN specificeras uppsättningen av förlustförlustiga grenar initialt, vid byggtid, medan ABM-funktioner har ett kryphål som gör att du kan prova dekryptering i farten från en stor pool av förlustförluster. Utan denna hemliga passage, och även med en godtycklig känd uppsättning av förlustiga grenar, finns det inget sätt att hitta en annan gren som inte tillhör den kända uppsättningen. Detta gör att du i synnerhet kan skapa ABM-instanser med kompakta nycklar och bilder, vars storlek inte beror på antalet grenar med förlust.

Dessa konstruktioner kan ses som "förklädda" varianter av Boneh-Boyen (BB) signalkretsar. I synnerhet motsvarar förlustgivande grenar riktiga signaturer. Men för att förlustmärkena och hemliga passagemärken ska verka oskiljaktiga är det nödvändigt att göra blinda signaturer , antingen genom att kryptera dem eller genom att multiplicera dem med ett slumpmässigt element i undergruppen. [9]

Konstruktion av envägsfunktioner med dold förlustsignal

För att notera de grundläggande principerna, anta att ett allmänt CPA-aktiverat kryptosystem har några speciella (men informellt beskrivna) egenskaper.

Den första egenskapen antar att det underliggande kryptosystemet är additiv-homomorft. Funktionen (envägs kryphål eller förlustfunktion) bestäms genom att kryptera en kvadratisk matris elementmässigt . $f$ ${\displaystyle \{0,1\}^{n))$ $M$

För att uppskatta , tillhandahåller vi en indata - en n-dimensionell binär vektor och beräknar (i etapper) krypteringen av en linjär produkt genom att tillämpa homomorfa operationer på krypterade poster . $f(x)$ ${\displaystyle x\in \{0,1\}^{n))$ $x*M$ $M$

För en hemlig ingångsfunktion är den krypterade matrisen identitetsmatrisen , och kryphålet är dekrypteringsnyckeln för kryptosystemet. Funktionen är reversibel med en hemlig ingång, eftersom den är ingångskrypteringen som kan dekrypteras till värdet av varje bit . $M$ $jag$ $f$ $f(x)$ $x*I=x$ $x$

För en förlustlös funktion är den krypterade matrisen en matris som består av nollor: . Sedan, för varje inmatat meddelande , är värdet en elementvis kryptering av noll-vektorn, så det "förlorar" information om . Detta är dock inte tillräckligt för att säkerställa en fullständig förlust, eftersom de utgående krypterade meddelandena fortfarande innehåller en del intern slumpmässig information som kan fungera som en källa för data om ingångsmeddelandet. Därför är ytterligare kontroll över deras beteende nödvändig. För detta finns det speciella egenskaper hos kryptosystemet: $M$ $M=0$ $x$ $f(x)$ $f$ $x$

slumpmässighet kan återanvändas i kombinationer med olika tangenter utan att kompromissa med styrkan.
den homomorfa operationen isolerar slumpmässighet, det vill säga slumpmässigheten hos den utgående chiffertexten beror endast på slumpmässigheterna i inmatningsmeddelandet (och inte på den publika nyckeln eller krypterade meddelanden). Många kända kryptosystem är homomorfa med avseende på slumpmässighet.

Med dessa två egenskaper krypterar vi matrisen på ett speciellt sätt. Varje kolumn i matrisen är associerad med en annan nyckel , och kryphålet är en uppsättning motsvarande dekrypteringsnycklar. Genom varje rad krypterar vi posten under nyckeln och samma slumpmässighet (med en ny slumpmässighet för varje rad). Enligt konvention är det säkert att återanvända slumpmässighet med en nyckel , så matrisen är beräkningsmässigt dold. Dessutom, eftersom homomorfism isolerar slumpmässighet, är alla chiffertexter i den slutliga vektorn också krypterade med samma slumpmässighet (vilket bara beror på . $M$ $j$ ${\displaystyle p_{kj))$ $i$ ${\displaystyle m_{i,j))$ ${\displaystyle p_{kj))$ $r_{i}$ ${\displaystyle p_{kj))$ $M$ $f(x)$ $R$ $(r_{1},r_{2}...r_{m})$

När , kan vi fortfarande invertera funktionen (genom ett kryphål) och dekryptera varje krypterad post . Å andra sidan, när matrisen är noll , är utdata från funktionen alltid en vektor av krypterade nollmeddelanden, där varje post är krypterad med samma slumpmässighet (men under olika fasta nycklar). Därför begränsas antalet möjliga utgångar av antalet möjliga slumpmässiga strängar som kan uppstå. Genom att välja en dimension så att antalet ingångar är betydligt större än antalet slumpmässiga rader kan vi säkerställa att funktionen innehåller mycket information. $M=I$ $f(x)$ $M=0$ $f$ $n$ $2^{n}$

Bygga alla-utom-en-funktioner

Konstruktionen av "Allt-utom-en"-funktioner med hemlig ingång är något mer generell. Varje funktionsgren motsvarar helt enkelt en annan matris , vars kryptering kan erhållas från funktionens offentliga beskrivning. Funktionen genereras så att den är en inverterbar matris (och beräknas med hjälp av en hemlig post) för alla grenar , medan för grenar med förlust $b$ ${\displaystyle M_{b))$ ${\displaystyle M_{b))$ $b$ $M_{b^{*}}=0$ $b^{*}$

Exempel på enkelriktade funktioner med dolda ingångar

rsa

Ta ett tal , var och tillhör uppsättningen av primtal . Man tror att för ett givet nummer är beräkningen en matematiskt svår uppgift. RSA-krypteringsfunktionen är , där är coprime med . Siffror och är en hemlig ingång, att veta vilken det är lätt att beräkna den inversa funktionen . Den överlägset bästa attacken mot RSA är nummerfaktorisering [ 10] [11] . $n=p\cdot q$ $sid$ $q$ $n$ $sid$ $q$ $E(m)=m^{e}\mod n$ $e$ $(p-1)(q-1)$ $sid$ $q$ $E^{-1}$ $n$

Rabins funktion

Betrakta funktionen , där , och p och q hör till mängden primtal. Rabin visade att det är lätt att beräkna en funktion om och bara om faktorisering av ett sammansatt tal från två primtal är en enkel uppgift [12] . $F(x,n)=x^{2}mod(n)$ $n=p\cdot q$ $f^{-1}$

Schema för ElGamal

Detta system föreslogs av Taher El- Gamal 1984 . Det är baserat på det diskreta logaritmproblemet [13] .

Algoritm

Alice väljer ett primtal p och ett godtyckligt tal a .
Alice beräknar sin publika nyckel ( a , b ), där , $b=a^{c}$ $1<c<p$
Bob väljer och krypterar ett meddelande m : $1<d<p$ $(m_{1},m_{2})=(a^{d},m\cdot b^{d})$
Alice dekrypterar meddelandet $m=m_{2}\cdot (m_{1}^{c})^{-1}.$

Kryptosystem Polly Cracker

Algoritm [14]

Alice väljer slumpmässigt en vektor i ett ändligt fält .
Alice bygger polynom som försvinner vid den punkt som ges av denna vektor.
Bob genererar en summa $p=\sum {q_{i}\cdot b_{i}}$
Bob skickar $p+m$

Andra exempel

Det är känt att funktionerna associerade med det diskreta logaritmproblemet inte är envägsfunktioner med hemlig inmatning, eftersom det inte finns någon information om "kryphålet" som skulle tillåta att den diskreta logaritmen kan beräknas effektivt. Emellertid kan det diskreta logaritmproblemet användas som grund för ett "kryphål", såsom beräkningsproblemet Diffie-Hellman (CDH) och dess variationer. Den digitala signaturalgoritmen är baserad på detta beräkningsproblem.

Anteckningar

Envägs hemliga inträdesfunktioner har en mycket specifik användning inom kryptografi och bör inte förväxlas med en bakdörr (ofta ersätts ett begrepp av ett annat, men det är fel). En bakdörr är en mekanism som medvetet läggs till i en krypteringsalgoritm (som en nyckelparsgenereringsalgoritm , en digital signaturalgoritm, etc.) eller till operativsystem, vilket gör att en eller flera tredje parter kan kringgå eller äventyra systemets säkerhet.

Se även

Envägsfunktion

Anteckningar

↑ 1 2 Diffie, Hellman, 1976 , sid. 652.
↑ Cliff Cocks. Cliff Cocks papper (inte tillgänglig länk) . Hämtad 23 november 2017. Arkiverad från originalet 16 februari 2017. (obestämd)
↑ Diffie, Hellman, 1976 , sid. 644.
↑ Diffie, Hellman, 1976 , s. 647-649.
↑ Katja Schmidt-Samoa. En ny Rabin-typ falldörrspermutation som motsvarar faktorisering och dess tillämpningar // Elektroniska anteckningar i teoretisk datavetenskap. - Elsevier, 2006. - Vol. 157 . - S. 79-94 . — ISSN 1571-0661 . - doi : 10.1016/j.entcs.2005.09.039 .
↑ Peikert, Waters, 2008 , s. åtta.
↑ Peikert, Waters, 2008 , s. 6.
↑ Peikert, Waters, 2008 , s. 13-14.
↑ 1 2 Chris Peikert, Brent Waters. Lossy Trapdoor-funktioner och deras tillämpningar∗ // Fortsätt STOC '08 Proceedings of the fyrtionde årliga ACM-symposium on Theory of computing. - 2008. - Vol. 41 . - S. 79-94 . — ISSN 1571-0661 . - doi : 10.1145/1374376.1374406 .
↑ Daniel Lerch Hostalot. Factorization Attack to RSA (engelska) // Hakin9 : journal. – 2007.
↑ S. Goldwasser, M. Bellaret. Lecture Notes on Cryptography (engelska) : journal. — 2008.
↑ Katja Schmidt-Samoa. En ny fälldörrspermutation av Rabin-typ som motsvarar Factoring och dess tillämpningar : journal . — 2005.
↑ Elgamal T. Ett kryptosystem med offentlig nyckel och ett signaturschema baserat på diskreta logaritmer, ett kryptosystem med offentlig nyckel och ett signaturschema baserat på diskreta logaritmer // IEEE Trans . inf. Theory / F. Kschischang - IEEE , 1985. - Vol. 31, Iss. 4. - P. 469-472. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1985.1057074 ; doi:10.1007/3-540-39568-7_2
↑ Neal Koblitz, 1998 , s. 105-106.

Litteratur

Xavier Boyen, Xiaofeng Chen. Allmän konstruktion av Chameleon All-But-One-fälldörrsfunktioner // Bevisbar säkerhet: 5:e internationella konferensen . - Springer, 2011. - S. 257-261 . — ISBN 9783642243158 .
Giuseppe Longo. Avsnitt 4.2: Kryptografiska funktioner // Säker digital kommunikation (neopr.) . - 1983. - S. 29-30. — ISBN 0-387-81784-0 .
Chris Peikert, Brent Waters. Förlustiga falldörrsfunktioner och deras tillämpningar . - 2008. - ISBN 978-1-60558-047-0 .
Julien Cathalo, Christophe Petit. Engångsfälldörr envägsfunktioner . - Springer, 2011. - ISBN 9783642181771 .
Ronald C. Mullin, Gary L. Mullen. Finita fält: teori, tillämpningar och algoritmer: Fjärde internationella konferensen om ändliga fält: teori, tillämpningar och algoritmer . — Providence, RI: American Mathematical Society, 1998. — ISBN 0821808176 .
Neal Koblitz . Algebraiska aspekter av kryptografi. — Springer. - 1998. - ISBN 3540634460 .
Diffie W. , Hellman M. E. New Directions in Cryptography // IEEE Trans . inf. Theory / F. Kschischang - IEEE , 1976. - Vol. 22, Iss. 6. - P. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638