Envejsfunktion med hemmelig indgang

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 10. september 2017; checks kræver 37 redigeringer .

En envejsfunktion med hemmelig indgang ( eng. falddørsfunktion , TDF ) er en envejsfunktion fra sæt til sæt , som har en egenskab (hemmelig indgang, smuthul), takket være hvilken det bliver muligt at finde til enhver sådan det vil sige invertere funktionen. $f$ $x$ $Y$ $y\in Im{f},x\in X$ $f(x) = y$

Envejs hemmelige indtastningsfunktioner bruges i vid udstrækning i asymmetriske krypteringsmetoder (offentlig nøglekryptering) såsom: RSA , Rabin-funktion , ElGamal- skemaer , McEliece-kryptosystem , NTRUEncrypt kryptografisk system , Polly Cracker, og også mindre populære på grund af dets kryptografiske ustabilitet, rygsækkryptosystem Merkle-Hellman .

På nuværende tidspunkt er det ikke fastslået med sikkerhed, at envejsfunktioner med en hemmelig indgang virkelig er envejs, det vil sige, at der ikke er bevis for, at en kryptoanalytiker ikke kan vende funktionen uden at kende den hemmelige indgang.

Definition

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

$\{0,1\}^{l(n)}$ - sæt offentlige nøgler,

${\displaystyle \{0,1\}^{m(n)))$ er et displayelement bestående af n bit,

kaldes ensrettet med hemmelig indgang, hvis

Det er ensidigt ;
Der er en effektiv algoritme , der, givet den offentlige nøgle , besked og værdi af funktionen, beregner sådan, at for en eller anden nøgle ; $Y$ $M$ $M'$ $f(M)=f(M')$ $Z$
For en given besked og funktion er det svært at finde et budskab sådan, at . $M$ $f(M)$ $M'\neq M$ $f(M)=f(M')$

Historie

Udvikling af envejsfunktioner med hemmelig indgang

Forestillingen om en bagdørs envejsfunktion blev introduceret i midten af 1970'erne efter offentliggørelsen af en artikel af Whitfield Diffie , Martin Hellman og Ralph Merkle om asymmetriske krypteringsmetoder (offentlig nøglekryptering). Det var Diffie og Hellman, der opfandt udtrykket [1] . Men det første system, hvor sådanne ideer blev brugt, anses for at være et system opfundet i 1973 af Clifford Cox , som arbejdede på regeringens kommunikationscenter ( GCHQ ), men dette arbejde blev kun opbevaret i centrets interne dokumenter , så dets eksistens blev først kendt i 1977 [2] .

Artiklen beskrev en ny metode til at minimere behovet for at overføre nøgler over sikre kanaler, og den adskilte også et kryptografisk system, der kan bruges til at skabe en digital signatur [3] .

Forfatterne har vist, at en envejs hemmelig indtastningsfunktion kan bruges i offentlige nøglekryptosystemer og digitale signaturenheder [4] . Et offentlig nøglekryptosystem er et system, hvor den offentlige nøgle transmitteres over en usikker kanal. Betydningen af en digital signatur er, at når du sender en underskrevet besked fra Alice til Bob , kan Bob bekræfte, at beskeden faktisk blev sendt af Alice.

Takket være envejs hemmelige indtastningsfunktioner kan forskellige hemmelige indtastningscifre implementeres , som er kryptografisk sikre [1] .

Flere klasser af funktioner blev foreslået, men det blev hurtigt klart, at passende funktioner var sværere at finde end oprindeligt antaget. For eksempel var det først hensigten at bruge funktioner baseret på delmængdesumproblemet . Det blev hurtigt klart, at denne metode var uacceptabel. Et eksempel på en sådan implementering er Merkle-Hellman ranselskryptosystemet .

I 2005 var de bedst egnede kandidater til envejs bagdørsfunktioner dem fra RSA- og Rabin -klasserne [5] . Disse funktioner bruger eksponentieringsmodulo et sammensat tal, og begge er baseret på heltalsfaktoriseringsproblemet .

I 2008 blev bagdørs envejsfunktioner introduceret, hvilket tillod tab af information om den originale besked.

Udvikling af envejs, tabsgivende, bagdørsfunktioner

Denne type funktion ( tabsdørsfunktion ), baseret på ideen om at beskadige en væsentlig del af informationen [6] , blev introduceret af Chris Peikert og Brent Waters [7] i særdeleshed, som et middel at konstruere et offentligt nøglekrypteringsskema med en valgt krypteret tekst.

Sættet af disse funktioner består af en familie af to funktioner:

De gentager arbejdet med en envejsfunktion med et hemmeligt input uden at miste en del af informationen, det vil sige, hvis der er et "smuthul", kan det effektivt beregnes ud fra værdien af . $x$ $f(x)$
De mister en del af informationen om inputtet, så har outputtet mange forbilleder (det vil sige, at det er umuligt entydigt at invertere funktionen). $f(x)$

Nøglepunktet er, at de valgte familier af funktioner ikke kan skelnes polynomielt . Derfor kan nøgler erstattes med nøgler med tab uden at give besked til nogen. Men når alle nøglerne er tabt, indeholder chifferteksten ikke længere (væsentlige) informationer om den krypterede besked. På samme tid, hvis man blot erstatter smuthulsfunktionen med en tabsgivende funktion, er der ingen måde at reagere på selv på en veludformet dekrypteringsanmodning, fordi klartekstinformationen vil gå tabt. Derfor bruges mere komplette abstraktioner

Envejsfunktioner med hemmelig indgang "Alle-undtagen-en"

En alt-undtagen-en-funktion (ABO) kan bygges ud fra et sæt envejsfunktioner med hemmelig indtastning og tilstrækkeligt tab af information.

Sættet af ABO-funktioner er knyttet til sættet , hvis elementer kaldes forgrene. ABO-funktionsgeneratoren tager en ekstra parameter , kaldet den tabsgivende gren, og udsender en funktion og en bagdør t. Funktionen har den egenskab, at funktionen for enhver gren har et skjult input (og kan inverteres med ), men funktionen er en tabsgivende funktion. Desuden er den tabsgivende gren skjult (beregningsmæssigt) af beskrivelsen af . [8] . $B$ $b^{*}\in B$ $g({\cdot },{\cdot })$ $g$ $b\not =b^{*}$ $g(b,\cdot )$ $t$ $g(b^{*},\cdot )$ $g$

Envejsfunktioner med hemmelig indgang "All-but-N"

All-but-N (ABN) funktioner har nøjagtigt tabsgivende grene; alle andre filialer har en hemmelig indgang. Dette kan bruges til at lokalisere chiffertekster ved hjælp af tabsgivende grene - alle andre chiffertekster matcher bagdørsfunktioner og kan dekrypteres. Bemærk, at ABN'er koder et sæt tabsgivende grene ved deres nøgle. Det vil sige, at en beregningsmæssigt ubegrænset modstander altid kan bruge brute force til at finde grene, der fører til en tabsgivende funktion. $N$

Derfor har ABN-funktioner en alvorlig ulempe: nemlig den rumlige kompleksitet af tasterne er lineær i [9] $N.$

Envejs alle-undtagen mange hemmelige indtastningsfunktioner

Funktionen alt-undtagen-mange (ABM) har et superpolynomisk sæt af tabsgivende grene, der kræver en speciel bagdør.

Den vigtigste forskel fra ABN-funktionen er, at med ABN er sættet af tabsgivende grene angivet indledningsvis, på byggetidspunktet, mens ABM-funktioner har et smuthul, der giver dig mulighed for at prøve dekryptering på farten fra en stor pulje af tabsgivende grene. Uden denne hemmelige passage, og selv med et vilkårligt kendt sæt af tabsgivende grene, er der ingen måde at finde en anden gren, der ikke tilhører det kendte sæt. Dette giver dig især mulighed for at oprette ABM-instanser med kompakte nøgler og billeder, hvis størrelse ikke afhænger af antallet af tabsgivende filialer.

Disse designs kan ses som "forklædte" varianter af Boneh-Boyen (BB) signalkredsløb. Især tabsgivende grene svarer til reelle signaturer. Men for at tabsmærkerne og hemmelige passagemærker skal se ud til at kunne skelnes, er det nødvendigt at lave blinde signaturer , enten ved at kryptere dem eller ved at gange dem med et tilfældigt element i undergruppen. [9]

Konstruktion af envejsfunktioner med skjult tabsgivende input

For at bemærke de grundlæggende principper, antag, at et generelt CPA-aktiveret kryptosystem har nogle få specielle (men uformelt beskrevne) egenskaber.

Den første egenskab antager, at det underliggende kryptosystem er additiv-homomorft. Funktionen (en-vejs smuthul eller tabsfunktion) bestemmes ved at kryptere en kvadratisk matrix element-mæssigt . $f$ ${\displaystyle \{0,1\}^{n))$ $M$

For at estimere leverer vi et input - en n-dimensionel binær vektor og beregner (i etaper) krypteringen af et lineært produkt ved at anvende homomorfe operationer på krypterede poster . $f(x)$ ${\displaystyle x\in \{0,1\}^{n))$ $x*M$ $M$

For en hemmelig indtastningsfunktion er den krypterede matrix identitetsmatrixen , og smuthullet er dekrypteringsnøglen til kryptosystemet. Funktionen er reversibel med et hemmeligt input, fordi det er inputkryptering , der kan dekrypteres til værdien af hver bit . $M$ $jeg$ $f$ $f(x)$ $x*I=x$ $x$

For en tabsgivende funktion er den krypterede matrix en matrix bestående af nuller: . Derefter er værdien for hver inputmeddelelse en elementmæssig kryptering af null-vektoren, så den "taber" information om . Dette er dog ikke nok til at sikre et fuldstændigt tab, da de krypterede udgangsmeddelelser stadig bærer nogle interne tilfældige informationer, der kan tjene som en kilde til data om inputmeddelelsen. Derfor er yderligere kontrol over deres adfærd nødvendig. Til dette er der særlige egenskaber ved kryptosystemet: $M$ $M=0$ $x$ $f(x)$ $f$ $x$

tilfældighed kan genbruges i kombinationer med forskellige taster uden at gå på kompromis med styrken.
den homomorfe operation isolerer tilfældighed, det vil sige, tilfældigheden af den udgående chiffertekst afhænger kun af tilfældighederne i inputmeddelelsen (og ikke af den offentlige nøgle eller krypterede beskeder). Mange kendte kryptosystemer er homomorfe med hensyn til tilfældighed.

Med disse to egenskaber krypterer vi matrixen på en særlig måde. Hver kolonne i matrixen er forbundet med en anden nøgle , og smuthullet er et sæt af tilsvarende dekrypteringsnøgler. Gennem hver linje krypterer vi indtastningen under nøglen og den samme tilfældighed (ved at bruge en ny tilfældighed for hver linje). Konventionelt er det sikkert at genbruge tilfældighed med en nøgle , så matrixen er beregningsmæssigt skjult. Da homomorfi isolerer tilfældighed, er alle chiffertekster i den endelige vektor også krypteret med den samme tilfældighed (som kun afhænger af . $M$ $j$ ${\displaystyle p_{kj))$ $jeg$ ${\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 stadig invertere funktionen (gennem et smuthul) og dekryptere hver krypteret indgang . På den anden side, når matricen er nul , er outputtet af funktionen altid en vektor af krypterede nul-meddelelser, hvor hver indtastning er krypteret med den samme tilfældighed (men under forskellige faste nøgler). Derfor er antallet af mulige output begrænset af antallet af mulige tilfældige strenge, der kan forekomme. Ved at vælge en dimension , så antallet af input er væsentligt større end antallet af tilfældige rækker, kan vi sikre, at funktionen indeholder en masse information. $M=I$ $f(x)$ $M=0$ $f$ $n$ $2^{n}$

Opbygning af alle-undtagen-én-funktioner

Opbygningen af "Alle-und-en"-funktioner med hemmelig indgang er noget mere generel. Hver funktionsgren svarer ganske enkelt til en anden matrix , hvis kryptering kan hentes fra funktionens offentlige beskrivelse. Funktionen genereres således, at den er en inverterbar matrix (og beregnes ved hjælp af en hemmelig post) for alle grene , mens det er for tabsgivende grene $b$ ${\displaystyle M_{b))$ ${\displaystyle M_{b))$ $b$ $M_{b^{*}}=0$ $b^{*}$

Eksempler på envejsfunktioner med skjulte indgange

rsa

Tag et tal , hvor og hører til sættet af primtal . Det menes, at for et givet tal er beregningen en matematisk vanskelig opgave. RSA-krypteringsfunktionen er , hvor er coprime med . Tal og er en hemmelig indgang, vel vidende at det er nemt at beregne den inverse funktion . Det klart bedste angreb på RSA er talfaktorisering [ 10] [11] . $n=p\cdot q$ $s$ $q$ $n$ $s$ $q$ $E(m)=m^{e}\mod n$ $e$ $(p-1)(q-1)$ $s$ $q$ $E^{-1}$ $n$

Rabins funktion

Overvej funktionen , hvor , og p og q hører til sættet af primtal. Rabin viste, at det er let at beregne en funktion, hvis og kun hvis faktorisering af et sammensat tal fra to primtal er en simpel opgave [12] . $F(x,n)=x^{2}mod(n)$ $n=p\cdot q$ $f^{-1}$

Ordning af ElGamal

Denne ordning blev foreslået af Taher El-Gamal i 1984 . Den er baseret på det diskrete logaritmeproblem [13] .

Algoritme

Alice vælger et primtal p og et vilkårligt tal a .
Alice beregner sin offentlige nøgle ( a , b ), hvor , ${\displaystyle b=a^{c))$ $1<c<p$
Bob vælger og krypterer en besked m : $1<d<p$ $(m_{1},m_{2})=(a^{d},m\cdot b^{d})$
Alice dekrypterer beskeden $m=m_{2}\cdot (m_{1}^{c})^{-1}.$

Kryptosystem Polly Cracker

Algoritme [14]

Alice vælger tilfældigt en vektor i et begrænset felt .
Alice bygger polynomier, der forsvinder på det punkt, som denne vektor giver.
Bob genererer en sum $p=\sum {q_{i}\cdot b_{i}}$
Bob sender $p+m$

Andre eksempler

Det er kendt, at de funktioner, der er forbundet med det diskrete logaritmeproblem , ikke er envejsfunktioner med hemmelig input, fordi der ikke er nogen information om "smuthulet", der ville tillade, at den diskrete logaritme kan beregnes effektivt. Det diskrete logaritmeproblem kan dog bruges som grundlag for et "smuthul", såsom det beregningsmæssige Diffie-Hellman-problem (CDH) og dets variationer. Den digitale signaturalgoritme er baseret på dette beregningsproblem.

Noter

Envejs hemmelige indtastningsfunktioner har en meget specifik anvendelse i kryptografi og bør ikke forveksles med en bagdør (ofte erstattes et begreb med et andet, men det er forkert). En bagdør er en mekanisme, der bevidst er tilføjet til en krypteringsalgoritme (såsom en nøglepargenereringsalgoritme , en digital signaturalgoritme osv.) eller til operativsystemer, hvilket tillader en eller flere tredjeparter at omgå eller kompromittere systemets sikkerhed.

Se også

Envejs funktion

Noter

↑ 1 2 Diffie, Hellman, 1976 , s. 652.
↑ Cliff Cocks. Cliff Cocks papir (ikke tilgængeligt link) . Hentet 23. november 2017. Arkiveret fra originalen 16. februar 2017. (ubestemt)
↑ Diffie, Hellman, 1976 , s. 644.
↑ Diffie, Hellman, 1976 , s. 647-649.
↑ Katja Schmidt-Samoa. En ny Rabin-type fældedør-permutation svarende til faktorisering og dens anvendelser // Elektroniske noter i teoretisk datalogi. - Elsevier, 2006. - Vol. 157 . - S. 79-94 . — ISSN 1571-0661 . - doi : 10.1016/j.entcs.2005.09.039 .
↑ Peikert, Waters, 2008 , pp. otte.
↑ Peikert, Waters, 2008 , pp. 6.
↑ Peikert, Waters, 2008 , pp. 13-14.
↑ 1 2 Chris Peikert, Brent Waters. Lossy Trapdoor-funktioner og deres applikationer∗ // Proceeding STOC '08 Proceedings of the 40. årlige ACM symposium on Theory of computing. - 2008. - Bd. 41 . - S. 79-94 . — ISSN 1571-0661 . - doi : 10.1145/1374376.1374406 .
↑ Daniel Lerch Hostalot. Faktoriseringsangreb til RSA (engelsk) // Hakin9 : tidsskrift. – 2007.
↑ S. Goldwasser, M. Bellaret. Lecture Notes on Cryptography (engelsk) : tidsskrift. – 2008.
↑ Katja Schmidt-Samoa. En ny Rabin-type fældedør-permutation svarende til faktorisering og dens anvendelser : tidsskrift . - 2005.
↑ Elgamal T. Et offentligt nøglekryptosystem og et signaturskema baseret på diskrete logaritmer, et offentligt nøglekryptosystem og et signaturskema baseret på diskrete logaritmer // IEEE Trans . inf. Teori / F. Kschischang - IEEE , 1985. - Vol. 31, Iss. 4. - S. 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. Generel konstruktion af Chameleon All-But-One-fældedørsfunktioner // Bevisbar sikkerhed: 5. internationale konference . - Springer, 2011. - S. 257-261 . — ISBN 9783642243158 .
Giuseppe Longo. Afsnit 4.2: Kryptografiske funktioner // Sikker digital kommunikation (neopr.) . - 1983. - S. 29-30. — ISBN 0-387-81784-0 .
Chris Peikert, Brent Waters. Lossy Trapdoor-funktioner og deres applikationer . - 2008. - ISBN 978-1-60558-047-0 .
Julien Cathalo, Christophe Petit. Engangsfaldsdør envejsfunktioner . - Springer, 2011. - ISBN 9783642181771 .
Ronald C. Mullin, Gary L. Mullen. Finite fields: teori, applikationer og algoritmer: Fjerde internationale konference om endelige felter: teori, applikationer og algoritmer . — Providence, RI: American Mathematical Society, 1998. — ISBN 0821808176 .
Neal Koblitz . Algebraiske aspekter af kryptografi. — Springer. - 1998. - ISBN 3540634460 .
Diffie W. , Hellman M. E. New Directions in Cryptography // IEEE Trans . inf. Teori / F. Kschischang - IEEE , 1976. - Vol. 22, Iss. 6. - S. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638