Szemantikai kitartás

A kriptográfiában a szemantikailag biztonságos kriptorendszer olyan kriptorendszer, amely nem engedi meg az eredeti nyílt szöveggel kapcsolatos értelmes információk kiszivárgását a titkosított szövegből . Vegyünk egy tetszőleges PP osztályú valószínűségi algoritmust , amelynek bemenete az első esetben valamilyen véletlenszerű üzenet titkosított szövege és ennek az üzenetnek a hossza, a második esetben pedig csak az üzenet hossza. Ha az első és a második esetben elhanyagolható a különbség az eredeti üzenetről megbízható információ megszerzésének valószínűsége között, akkor a titkosítást előállító kriptorendszert szemantikailag biztonságosnak tekintjük. [1] Ami a következőt illeti: A számítási bonyolultság miatt ez a fogalom analóg az abszolút biztonságos Shannon - rejtjellel . A tökéletesen biztonságos titkosítás azt jelenti, hogy az eredeti üzenetről egyáltalán nem lehet információt szerezni, míg a szemantikai biztonság azt jelenti, hogy az eredeti üzenetre vonatkozó, a titkosított szövegben található információ nem használható fel az üzenet bármely töredékének visszafejtésére. [2] [3] :378–381

Történelem

A szemantikai erő fogalmát Goldwasser és Micali vezette be a kriptográfiába 1982-ben. [1] Az általuk eredetileg javasolt definíció azonban nem adott becslést a valódi kriptorendszerek erejéről . Később Goldwasser és Micali kimutatta, hogy a szemantikai biztonság egyenértékű a titkosított szöveg megkülönböztethetetlenségével az illesztett egyszerű szövegű támadásoknál . [4] A szemantikai erősségnek ez a definíciója elterjedtebb, mivel segít felmérni a használt kriptorendszerek erősségét.

Szimmetrikus kriptográfia

Szimmetrikus titkosítási rendszerek esetén az ellenfélnek nem szabad tudnia megtudni a titkosított szövegből semmilyen információt a nyílt szövegről. Ez azt jelenti, hogy a két nyílt szöveggel és két megfelelő titkosított szöveggel rendelkező ellenfél nem tudja pontosan meghatározni, hogy melyik titkosított szöveg melyik nyílt szövegnek felel meg.

Nyilvános kulcsú titkosítás

A nyilvános kulcsú kriptorendszerről azt mondják, hogy szemantikailag biztonságos, ha egy ellenfél a titkosított szöveg és a nyilvános kulcs birtokában nem tud semmilyen értelmes információt szerezni az eredeti nyílt szövegről. A szemantikus biztonság csak a passzív titkosítási támadások eseteit veszi figyelembe, például amikor a kriptoanalizátor csak a továbbított rejtjelszövegeket tudja megfigyelni, és saját titkosítást generál a nyilvános kulcs segítségével. A biztonság más fogalmaitól eltérően a szemantikai biztonság nem veszi figyelembe a választott titkosított szöveges támadásokat , ahol a kriptoanalizátor képes visszafejteni néhány kiválasztott rejtjelezett szöveget, és számos szemantikailag erős titkosítási séma gyengének bizonyult az ilyen típusú támadásokkal szemben. Ezért a szemantikai erősség nem tekinthető elégséges feltételnek egy általános célú titkosítási séma erőssége szempontjából.

A titkosított szöveg megkülönböztethetetlenségét a választott egyszerű szövegen alapuló támadásoknál általában a következő kísérlet határozza meg: [5]

1. Véletlenszerű kulcspár jön létre .
2. Egy ellenfél, polinomiális időkorlát kap egy nyilvános kulcsot , amellyel tetszőleges számú titkosított szöveget generálhat (a polinomiális időhatárokon belül).
3. Az ellenfél két azonos hosszúságú üzenetet generál , és a nyilvános kulccsal együtt elküldi a feladónak.
4. A feladó véletlenszerűen kiválaszt egy üzenetet, titkosítja azt a kapott nyilvános kulccsal, és a kapott titkosított szöveget elküldi az ellenfélnek.

A vizsgált kriptorendszer rendelkezik a rejtjelezett szöveg megkülönböztethetetlenségi tulajdonságával (és így szemantikailag ellenáll a választott egyszerű szöveges támadásoknak), ha az ellenfél nem tudja meghatározni, hogy a két üzenet közül melyiket választotta a küldő a (véletlenszerű találgatás valószínűsége) -nél lényegesen nagyobb valószínűséggel.

Mivel az ellenfél rendelkezik a nyilvános kulccsal, a szemantikailag biztonságos sémának értelemszerűen valószínűséginek kell lennie, azaz véletlenszerű összetevővel kell rendelkeznie. Ellenkező esetben a nyilvános kulcs segítségével az ellenfél egyszerűen kiszámíthatja az üzenetek rejtjelezett szövegét , összehasonlíthatja azokat a visszaadott rejtjelezett szöveggel , és sikeresen meghatározhatja a küldő választását.

A szemantikailag biztonságos algoritmusok példái a Goldwasser-Micali kriptorendszer , az ElGamal séma és a Peye kriptorendszer . Ezeket a sémákat bizonyíthatóan biztonságosnak tekintjük , mivel a szemantikai biztonság bizonyítása minden esetben megoldhatatlan matematikai problémává redukálható. A szemantikailag törékeny algoritmusok, mint például az RSA , szemantikailag biztonságossá tehetők kitöltési sémák (pl . OAEP ) segítségével.

Jegyzetek

1. ↑ 1 2 S. Goldwasser és S. Micali , Valószínűségi titkosítás és mentális pókerezés, minden részleges információ titokban tartásával Archiválva : 2020. március 31., a Wayback Machine , Annual ACM Symposium on Theory of Computing, 1982.
2. ↑ Shannon, Claude. A titkossági rendszerek kommunikációelmélete  // Bell System Technical  Journal : folyóirat. - 1949. - 1. évf. 28 , sz. 4 . - P. 656-715 . - doi : 10.1002/j.1538-7305.1949.tb00928.x .
3. ↑ Goldreich, Oded. A kriptográfia alapjai: 2. kötet, Alapvető alkalmazások. Vol. 2. Cambridge University Press, 2004.
4. ↑ S. Goldwasser és S. Micali , Valószínűségi titkosítás . Journal of Computer and System Sciences, 28:270-299, 1984.
5. ↑ Katz, Jonathan; Lindell, Yehuda. Bevezetés a modern kriptográfiába : alapelvek és protokollok  . — Chapman és Hall/CRC, 2007. Archiválva : 2017. március 8. a Wayback Machine -nál