Egyirányú funkció titkos bejárattal

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2017. szeptember 10-én felülvizsgált verziótól ; az ellenőrzések 37 szerkesztést igényelnek .

A titkos bejárattal rendelkező egyirányú funkció ( eng. trapdoor function , TDF ) egy halmaztól halmazig egyirányú funkció , amelynek van egy tulajdonsága (titkos bejárat, kiskapu), aminek köszönhetően minden ilyenhez meg lehet találni . vagyis megfordítja a függvényt. $f$ $x$ $Y$ $y\in Im{f},x\in X$ $f(x) = y$

Az egyirányú titkos beviteli funkciókat széles körben használják az aszimmetrikus titkosítási módszerekben (nyilvános kulcsú titkosítás), mint például: RSA , Rabin függvény , ElGamal sémák , McEliece kriptorendszer , NTRUEncrypt kriptográfiai rendszer , Polly Cracker, és kriptográfiai instabilitása miatt kevésbé népszerűek, hátizsákos kriptorendszer Merkle-Hellman .

Jelenleg nem biztos, hogy a titkos bejáratú egyirányú funkciók valóban egyirányúak, vagyis nincs bizonyíték arra, hogy a titkos bejárat ismerete nélkül egy kriptanalitikus nem tudja megfordítani a funkciót.

Definíció

Funkció , hol $f:\{0,1\}^{l(n)}\times \{0,1\}^{n}{\xrightarrow[{}]{}}\{0,1\}^ {m(n)}$

$\{0,1\}^{l(n)}$ - nyilvános kulcsok készlete,

${\displaystyle \{0,1\}^{m(n)))$ egy n bitből álló kijelzőelem,

titkos bejáratú egyirányúnak nevezik, ha

Ez egyoldalú ;
Létezik egy hatékony algoritmus , amely a nyilvános kulcs , üzenet és a függvény értékének ismeretében úgy számítja ki , hogy bizonyos kulcsokra ; $Y$ $M$ $M'$ $f(M)=f(M')$ $Z$
Egy adott üzenethez és funkcióhoz nehéz olyan üzenetet találni , amely . $M$ $f(M)$ $M'\neq M$ $f(M)=f(M')$

Történelem

Egyirányú funkciók fejlesztése titkos bejárattal

Az egyirányú hátsó ajtó funkció fogalmát az 1970-es évek közepén vezették be, miután Whitfield Diffie , Martin Hellman és Ralph Merkle cikkét publikálták az aszimmetrikus titkosítási módszerekről (nyilvános kulcsú titkosítás). Diffie és Hellman alkotta meg a kifejezést [1] . De az első rendszer, amelyben ilyen ötleteket alkalmaztak , a kormányzati kommunikációs központban ( GCHQ ) dolgozó Clifford Cox által 1973 -ban feltalált rendszernek tekinthető , de ezt a munkát csak a központ belső dokumentumaiban őrizték meg. , így létezését 1977 -ig nem ismerték [2] .

A cikk egy új módszert írt le a kulcsok biztonságos csatornákon történő átvitelének minimalizálására, valamint szétszedte a digitális aláírás létrehozásához használható kriptográfiai rendszert [3] .

A szerzők kimutatták, hogy egy egyirányú titkos beviteli funkció használható nyilvános kulcsú kriptorendszerekben és digitális aláírási eszközökben [4] . A nyilvános kulcsú kriptorendszer olyan rendszer, amelyben a nyilvános kulcsot egy nem biztonságos csatornán továbbítják. A digitális aláírás jelentése az, hogy amikor aláírt üzenetet küld Alice-től Bobnak , Bob ellenőrizheti, hogy az üzenetet valóban Alice küldte-e.

Az egyirányú titkos beviteli funkcióknak köszönhetően különféle titkos beviteli rejtjelek valósíthatók meg , amelyek kriptográfiailag biztonságosak [1] .

Számos függvényosztályt javasoltak, de hamar világossá vált, hogy nehezebb megfelelő függvényeket találni, mint azt eredetileg gondolták. Például először az volt a cél, hogy a részhalmazösszeg-problémán alapuló függvényeket használjon . Hamar kiderült, hogy ez a módszer elfogadhatatlan. Egy ilyen megvalósításra példa a Merkle-Hellman háti kriptorendszer .

2005-ben a legalkalmasabb jelöltek egyirányú backdoor funkciókra az RSA és a Rabin osztályok voltak [5] . Ezek a függvények egy összetett szám modulo hatványozást használnak , és mindkettő az egész számok faktorizációs problémáján alapul .

2008-ban bevezették a hátsó ajtó egyirányú funkciókat, amelyek lehetővé tették az eredeti üzenettel kapcsolatos információk elvesztését.

Egyirányú, veszteséges, hátsó ajtó funkciók fejlesztése

Ezt a fajta funkciót ( veszteséges csapóajtó funkció ), amely az információ jelentős részének megrongálódásán alapul [6] , különösen Chris Peikert és Brent Waters [7] vezette be eszközként. nyilvános kulcsú titkosítási séma létrehozása egy kiválasztott titkosított szöveggel.

Ezeknek a függvényeknek a halmaza két függvénycsaládból áll:

Megismétlik egy egyirányú függvény munkáját titkos bemenettel anélkül, hogy elveszítenék az információ egy részét, vagyis ha van „kiskapu”, akkor az értékéből hatékonyan kiszámolható . $x$ $f(x)$
Elveszítik az input információinak egy részét, ekkor a kimenetnek sok előképe van (vagyis nem lehet egyedileg invertálni a függvényt). $f(x)$

A lényeg az, hogy a választott függvénycsaládok polinomiálisan megkülönböztethetetlenek . Ezért a kulcsok kicserélhetők veszteséges kulcsokra anélkül, hogy erről bárkit értesítenének. De miután az összes kulcs elveszett, a titkosított szöveg már nem tartalmaz (jelentős) információt a titkosított üzenetről. Ugyanakkor, ha egyszerűen lecseréljük a kiskapu függvényt egy veszteséges függvényre, akkor még egy jól formált visszafejtési kérésre sem lehet válaszolni, mert a nyílt szöveges információ elveszik. Ezért teljesebb absztrakciókat használnak

Egyirányú funkciók titkos bejárattal "Minden, kivéve egy"

Egy all-but-one (ABO) függvény építhető fel egyirányú függvények halmazából titkos belépéssel és elegendő információvesztéssel.

Az ABO függvények halmaza a halmazhoz van társítva , melynek elemeit ágaknak nevezzük. Az ABO függvénygenerátor vesz egy további paramétert , amelyet veszteséges ágnak neveznek, és egy függvényt és egy t hátsó ajtót ad ki. A függvénynek megvan az a tulajdonsága, hogy bármely ág esetén a függvény rejtett bemenettel rendelkezik (és invertálható -vel ), de a függvény veszteséges függvény. Ráadásul a veszteséges ágat (számításilag) elrejti a leírása . [8] . $B$ $b^{*}\in B$ $g({\cdot },{\cdot })$ $g$ $b\not =b^{*}$ $g(b,\cdot )$ $t$ $g(b^{*},\cdot )$ $g$

Egyirányú funkciók titkos bejárattal "All-but-N"

A minden, de N (ABN) függvényeknek pontosan veszteséges ágai vannak; minden más fióknak van titkos bejárata. Ez használható a rejtjelezett szövegek pontos meghatározására veszteséges ágak használatával - minden más rejtjelezett szöveg illeszkedik a hátsó ajtó függvényeihez, és visszafejthető. Vegye figyelembe, hogy az ABN-ek veszteséges ágak halmazát kódolják a kulcsukkal. Ez azt jelenti, hogy egy számításilag korlátlan számú ellenfél mindig nyers erőt alkalmazhat, hogy megtalálja a veszteséges függvényhez vezető ágakat. $N$

Ezért az ABN függvényeknek van egy komoly hátránya: a billentyűk térbeli összetettsége lineáris a [9]-ben. $N.$

Egyirányú, minden, de sok titkos beviteli funkciók

A mindent, de sok (ABM) függvény veszteséges ágak szuperpolinom halmazával rendelkezik, amelyek speciális hátsó ajtót igényelnek.

A legfontosabb különbség az ABN függvényhez képest az, hogy az ABN-nél a veszteséges ágak halmaza kezdetben, a felépítési időben van megadva, míg az ABM függvényeknél van egy kiskaput, amely lehetővé teszi a visszafejtést menet közben a veszteséges ágak nagy készletéből. E titkos átjáró nélkül, és még a veszteséges ágak tetszőleges ismert halmaza esetén sem lehet másik ágat találni, amely nem tartozik az ismert halmazba. Ez különösen lehetővé teszi ABM példányok létrehozását kompakt kulcsokkal és képekkel, amelyek mérete nem függ a veszteséges ágak számától.

Ezek a kialakítások a Boneh-Boyen (BB) jeláramkörök "álcázott" változatainak tekinthetők. Különösen a veszteséges ágak felelnek meg a valódi aláírásoknak. Ahhoz azonban, hogy a veszteségjelek és a titkos áthaladási jelek megkülönböztethetetlennek tűnjenek, vak aláírásokat kell készíteni , akár titkosítással, akár az alcsoport véletlenszerű elemével való megszorzással. [9]

Egyirányú funkciók felépítése rejtett veszteséges bemenettel

Az alapelvek megjegyezéséhez tegyük fel, hogy egy általános CPA-képes kriptorendszer rendelkezik néhány speciális (de informálisan leírt) tulajdonsággal.

Az első tulajdonság feltételezi, hogy a mögöttes kriptorendszer additív-homomorf. A függvényt (egyirányú kiskapu vagy veszteséges függvény) négyzetmátrix elemenkénti titkosításával határozzuk meg . $f$ ${\displaystyle \{0,1\}^{n))$ $M$

A becsléshez megadunk egy bemenetet - egy n-dimenziós bináris vektort, és kiszámítjuk (szakaszokban) egy lineáris szorzat titkosítását homomorf műveletek titkosított rekordokra történő alkalmazásával . $f(x)$ ${\displaystyle x\in \{0,1\}^{n))$ $x*M$ $M$

A titkos beviteli funkció esetében a titkosított mátrix az identitásmátrix , a kiskapu pedig a titkosítási rendszer visszafejtési kulcsa. A függvény titkos bemenettel visszafordítható, mivel a bemeneti titkosítást minden bit értékére vissza lehet fejteni . $M$ $én$ $f$ $f(x)$ $x*I=x$ $x$

Veszteséges függvény esetén a titkosított mátrix egy nullákból álló mátrix: . Ezután minden bemeneti üzenetnél az érték a null-vektor elemenkénti titkosítása, így "elveszíti" a következővel kapcsolatos információkat . Ez azonban nem elegendő a teljes veszteség biztosításához, mivel a kimeneti titkosított üzenetek továbbra is tartalmaznak néhány belső véletlen információt, amely adatforrásként szolgálhat a bemeneti üzenettel kapcsolatban. Ezért további ellenőrzésre van szükség viselkedésük felett. Ehhez a kriptorendszer speciális tulajdonságai vannak: $M$ $M=0$ $x$ $f(x)$ $f$ $x$

a véletlenszerűség újrafelhasználható különböző billentyűkkel kombinálva anélkül, hogy az erőt veszélyeztetné.
a homomorf művelet elkülöníti a véletlenszerűséget, vagyis a kimeneti rejtjelszöveg véletlenszerűsége csak a bemeneti üzenet véletlenszerűségeitől függ (és nem a nyilvános kulcstól vagy a titkosított üzenetektől). Sok ismert kriptorendszer homomorf a véletlenszerűség tekintetében.

Ezzel a két tulajdonsággal speciális módon titkosítjuk a mátrixot. A mátrix minden oszlopa más kulccsal van társítva , és a kiskapu a megfelelő visszafejtési kulcsok halmaza. Minden soron keresztül titkosítjuk a kulcs alatti bejegyzést és ugyanazt a véletlenszerűséget (minden sorhoz új véletlenszerűséget használunk). Megállapodás szerint biztonságos a véletlenszerűség újrafelhasználása egy kulccsal , így a mátrix számításilag rejtve van. Továbbá, mivel a homomorfizmus izolálja a véletlenszerűséget, a végső vektorban lévő összes rejtjelezett szöveg is ugyanazzal a véletlenszerűséggel van titkosítva (ami csak a . $M$ $j$ $p_{kj}$ $én$ $m_{i,j}$ $p_{kj}$ $r_{i}$ $p_{kj}$ $M$ $f(x)$ $R$ $(r_{1},r_{2}...r_{m})$

Amikor , továbbra is megfordíthatjuk a függvényt (egy kiskapun keresztül), dekódolhatunk minden titkosított bejegyzést . Másrészt, amikor a mátrix nulla , a függvény kimenete mindig titkosított null üzenetek vektora, ahol minden bejegyzés azonos véletlenszerűséggel (de különböző fix kulcsokkal) van titkosítva. Ezért a lehetséges kimenetek számát korlátozza a lehetséges véletlenszerű karakterláncok száma. Ha olyan dimenziót választunk , hogy a bemenetek száma lényegesen nagyobb, mint a véletlenszerű sorok száma, biztosíthatjuk, hogy a függvény sok információt tartalmazzon. $M=I$ $f(x)$ $M=0$ $f$ $n$ $2^{n}$

All-But-One funkciók létrehozása

A titkos bejárattal rendelkező „Minden, kivéve egy” funkciók felépítése valamivel általánosabb. Minden függvényág egyszerűen egy másik mátrixnak felel meg , amelynek titkosítása a függvény nyilvános leírásából érhető el. A függvényt úgy állítják elő, hogy invertálható mátrix (és titkos bejegyzéssel számítva) az összes ágra , míg a veszteséges ágakra $b$ ${\displaystyle M_{b))$ ${\displaystyle M_{b))$ $b$ $M_{b^{*}}=0$ $b^{*}$

Példák rejtett bejáratú egyirányú funkciókra

rsa

Vegyünk egy számot , ahol és tartozik a prímszámok halmazához . Úgy gondolják, hogy egy adott szám esetében a számítás matematikailag nehéz feladat. Az RSA titkosítási függvény , ahol a coprime és a . A számok és egy titkos bejárat, amelyek ismeretében könnyű kiszámítani az inverz függvényt . Az RSA elleni legjobb támadás a számfaktorizálás [ 10] [11] . $n=p\cdot q$ $p$ $q$ $n$ $p$ $q$ $E(m)=m^{e}\mod n$ $e$ ${\megjelenítési stílus (p-1) (q-1)}$ $p$ $q$ $E^{-1}$ $n$

Rabin függvény

Tekintsük a függvényt , ahol , valamint p és q a prímek halmazához tartoznak. Rabin megmutatta, hogy akkor és csak akkor könnyű függvényt kiszámítani, ha egy összetett szám faktorálása két prímből egyszerű feladat [12] . $F(x,n)=x^{2}mod(n)$ $n=p\cdot q$ $f^{-1}$

Az ElGamal sémája

Ezt a sémát Taher El-Gamal javasolta 1984 - ben . Ez a diszkrét logaritmus feladaton alapul [13] .

Algoritmus

Alice kiválaszt egy p prímszámot és egy tetszőleges a számot .
Alice kiszámítja a nyilvános kulcsát ( a , b ) , ahol ${\displaystyle b=a^{c))$ $1<c<p$
Bob kiválaszt és titkosít egy üzenetet m : $1<d<p$ $(m_{1},m_{2})=(a^{d},m\cdot b^{d})$
Alice visszafejti az üzenetet $m=m_{2}\cdot (m_{1}^{c})^{-1}.$

Cryptosystem Polly Cracker

Algoritmus [14]

Alice véletlenszerűen kiválaszt egy vektort egy véges mezőben .
Alice polinomokat épít, amelyek eltűnnek a vektor által megadott pontban.
Bob generál egy összeget $p=\sum {q_{i}\cdot b_{i}}$
Bob küld $p+m$

Egyéb példák

Ismeretes, hogy a diszkrét logaritmus -problémához kapcsolódó függvények nem egyirányú, titkos bemenetű függvények, mivel nincs információ a "kiskapuról", amely lehetővé tenné a diszkrét logaritmus hatékony kiszámítását. A diszkrét logaritmus-probléma azonban felhasználható egy „kiskapu” alapjául, mint például a számítási Diffie-Hellman-probléma (CDH) és annak változatai. A digitális aláírás algoritmusa ezen a számítási problémán alapul.

Jegyzetek

Az egyirányú titkos beviteli funkciók nagyon speciálisan használhatók a kriptográfiában , és nem szabad összetéveszteni a hátsó ajtóval (gyakran az egyik fogalmat egy másik helyettesíti, de ez téves). A hátsó ajtó egy titkosítási algoritmushoz (például kulcspár -generáló algoritmushoz, digitális aláírási algoritmushoz stb.) vagy operációs rendszerekhez szándékosan hozzáadott mechanizmus, amely lehetővé teszi egy vagy több harmadik fél számára a rendszer biztonságának megkerülését vagy veszélyeztetését.

Lásd még

Egyirányú funkció

Jegyzetek

↑ 1 2 Diffie, Hellman, 1976 , p. 652.
↑ Cliff Cocks. Cliff Cocks papír (nem elérhető link) . Letöltve: 2017. november 23. Az eredetiből archiválva : 2017. február 16.. (határozatlan)
↑ Diffie, Hellman, 1976 , p. 644.
↑ Diffie, Hellman, 1976 , pp. 647-649.
↑ Katja Schmidt-Szamoa. A faktorozással egyenértékű új Rabin típusú csapóajtó permutáció és alkalmazásai // Elektronikus jegyzetek az elméleti számítástechnikában. - Elsevier, 2006. - Vol. 157 . - 79-94 . o . — ISSN 1571-0661 . - doi : 10.1016/j.entcs.2005.09.039 .
↑ Peikert, Waters, 2008 , pp. nyolc.
↑ Peikert, Waters, 2008 , pp. 6.
↑ Peikert, Waters, 2008 , pp. 13-14.
↑ 1 2 Chris Peikert, Brent Waters. Veszteséges csapóajtó-függvények és alkalmazásaik∗ // STOC '08 Proceedings of the 40th Years ACM symposium on Theory of Computing. - 2008. - Vol. 41 . - 79-94 . o . — ISSN 1571-0661 . - doi : 10.1145/1374376.1374406 .
↑ Daniel Lerch Hostalot. Factorization Attack to RSA (angol) // Hakin9 : folyóirat. – 2007.
↑ S. Goldwasser, M. Bellaret. Lecture Notes on Cryptography (angol) : folyóirat. – 2008.
↑ Katja Schmidt-Szamoa. A faktorozással egyenértékű új Rabin típusú csapóajtó permutáció és alkalmazásai : napló . – 2005.
↑ Elgamal T. Egy nyilvános kulcsú kriptorendszer és egy diszkrét logaritmuson alapuló aláírási séma, egy nyilvános kulcsú kriptorendszer és egy diszkrét logaritmuson alapuló aláírási séma // IEEE Trans . inf. Elmélet / 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 , pp. 105-106.

Irodalom

Xavier Boyen, Xiaofeng Chen. A Chameleon All-But-One Trapdoor Functions általános felépítése // Provable Security: 5th International Conference . - Springer, 2011. - P. 257-261 . — ISBN 9783642243158 .
Giuseppe Longo. 4.2. szakasz: Kriptográfiai funkciók // Biztonságos digitális kommunikáció (neopr.) . - 1983. - S. 29-30. — ISBN 0-387-81784-0 .
Chris Peikert, Brent Waters. Veszteséges csapóajtó-funkciók és alkalmazásaik . - 2008. - ISBN 978-1-60558-047-0 .
Julien Cathalo, Christophe Petit. Egyszeri csapóajtó egyirányú funkciók . - Springer, 2011. - ISBN 9783642181771 .
Ronald C. Mullin, Gary L. Mullen. Véges mezők: elmélet, alkalmazások és algoritmusok: Negyedik nemzetközi konferencia a véges mezőkről: elmélet, alkalmazások és algoritmusok . – Providence, RI: American Mathematical Society, 1998. – ISBN 0821808176 .
Neal Koblitz . A kriptográfia algebrai vonatkozásai. — Springer. - 1998. - ISBN 3540634460 .
Diffie W. , Hellman M. E. Új irányok a kriptográfiában // IEEE Trans . inf. Elmélet / F. Kschischang - IEEE , 1976. - 1. kötet. 22, Iss. 6. - P. 644-654. — ISSN 0018-9448 ; 1557-9654 - doi:10.1109/TIT.1976.1055638