Cramer–Shoup kriptorendszer
A Cramer – Shoup rendszer egy nyilvános kulcsú titkosítási algoritmus . Az első algoritmus, amely ellenállónak bizonyult az adaptívan választott rejtjelezett szövegen alapuló támadásokkal szemben . Ronald Kramer és Victor Shoup tervezte 1998-ban. Az algoritmus biztonsága a Diffie–Hellman diszkriminációs feltételezésen alapul . Ez az ElGamal séma kiterjesztése , de az ElGamal sémával ellentétben ez az algoritmus kezelhetetlen(A hacker nem tudja lecserélni a rejtjelezett szöveget egy másik rejtjelezett szövegre, amely az eredetihez kapcsolódó szöveggé lenne dekódolva, vagyis annak valamilyen funkciója lenne). Ezt a robusztusságot egy univerzális egyirányú hash-függvény és további számítások használatával érik el, ami az ElGamal-séma kétszeresének megfelelő titkosított szöveget eredményez.
Választott titkosított szöveges támadás
Olyan kriptográfiai támadás, amelyben a kriptoanalizátor információkat gyűjt a rejtjelről úgy, hogy kitalálja a rejtjelszöveget, és egy ismeretlen kulccsal visszafejti. A rejtjelelemző többször is használhatja a visszafejtőt a visszafejtett rejtjelezett szöveg beszerzéséhez. A kapott adatok felhasználásával megpróbálhatja visszaállítani a titkos kulcsot a visszafejtéshez. A titkosított szöveges támadás lehet adaptív vagy nem adaptív.
Köztudott volt, hogy sok széles körben használt kriptorendszer ki van téve egy ilyen támadásnak, és sok éven át azt hitték, hogy a támadás nem praktikus, és csak elméleti jelentőséggel bír. A dolgok az 1990-es évek végén kezdtek megváltozni, különösen akkor, amikor Daniel Bleichenbacher egy gyakorlati rejtjelezett szöveg alapú támadást mutatott be az SSL -kiszolgálók ellen az RSA -titkosítás egy formájával .
Nem adaptív támadás
Nem adaptív támadásnál a kriptoanalizátor nem használja fel a korábbi visszafejtések eredményeit, vagyis a titkosított szövegeket előre kiválasztja. Az ilyen támadásokat ebédidő támadásoknak (lunchtime vagy CCA1) nevezik.
Adaptív támadás
Adaptív támadás esetén a kriptoanalizátor adaptív módon választ ki egy rejtjelezett szöveget, amely a korábbi dekódolások (CCA2) eredményétől függ.
Az adaptív támadásokkal szembeni ellenálló képesség a játék példáján látható:
- A kulcsgeneráló algoritmus a titkosítási sémában indul el, a megfelelő kulcshosszúság bemenetként.
- Az ellenfél egy sor tetszőleges kérést intéz a visszafejtő orákulumhoz, így dekódolja az általa választott titkosított szövegeket.
- Az ellenfél kiválaszt két üzenetet , és elküldi a titkosító orákulumnak.
- A titkosító orákulum véletlenszerűen kiválaszt egy bitet , majd titkosítja a -t, amelyet továbbít az ellenfélnek (a bit kiválasztásához szükséges érmefeldobás rejtve van az ellenfél elől).
- Az ellenfél ismét egy sor tetszőleges kérést intéz a visszafejtő orákulumhoz, azzal az egyetlen megkötéssel, hogy a kérésnek különböznie kell attól az üzenettől, amelyet a titkosító orákulumtól kapott.
- Az ellenfél megad egy bitet - a titkosítási orákulum által a 4. lépésben kiválasztott bit várható értékét . Ha , akkor az ellenfél fölénye egyenlőnek számít .
A Diffie-Hellman diszkriminációs probléma
A Diffie-Hellman diszkriminációs problémának több egyenértékű megfogalmazása létezik. Így néz ki az, amit használni fogunk.
Legyen egy sorrendi csoport , ahol egy nagy prímszám. Szintén - . És két disztribúció van:
- A véletlenszerű négyesek eloszlása .
- A négyesek eloszlása , ahol - véletlenszerűek, és véletlenszerűek .
A Diffie-Hellman problémát megoldó algoritmus egy valószínűségi algoritmus , amely hatékonyan képes megkülönböztetni a felsorolt két eloszlást. Vagyis annak az algoritmusnak, amely a két eloszlás egyikét veszi bemenetként, 0-t vagy 1-et kell visszaadnia, és szintén 0- ra kell törekednie .
A Diffie-Hellman diszkriminációs probléma nehéz, ha nem létezik ilyen polinomiális valószínűségi algoritmus.
Alapséma
Legyen egy sorrendi csoportunk , ahol egy nagy prímszám. Az üzenetek elemek . Használjuk az egyirányú hash függvények általános családját is, amelyek a hosszú bitláncokat elemekre képezik le , ahol — .
Kulcsgenerálás
A kulcsgeneráló algoritmus a következőképpen működik:
- Alice véletlenszerű és véletlenszerű elemeket generál
- Alice kiszámolja .
- A hash függvényt az egyirányú hash függvények univerzális családjából választják ki. A nyilvános kulcs , a privát kulcs pedig .
Titkosítás
Üzenet adott . A titkosítási algoritmus a következőképpen működik
- Bob véletlenszerűen választ .
- Bob a következő értékeket számítja ki:
- ;
- ;
- , ahol egy univerzális egyirányú hash függvény;
- ;
- Bob elküldi a titkosított szöveget Alice-nek.
Dekódolás
A titkosított szöveg vétele és a privát kulcs használata után :
- Alice kiszámolja .
- Alice ellenőrzi az állapotot . Ha a feltétel nem teljesül, akkor a protokoll visszafejtési sikertelenséggel fejeződik be. Ellenkező esetben egy üzenet jelenik meg .
Protokoll helyesség
Ellenőrizzük a titkosítási séma helyességét (a titkosított üzenet visszafejtése ugyanazt az üzenetet adja). Figyelembe véve ezt és , van . Szintén és . Ezért a visszafejtési ellenőrzés sikeres, és megjelenik az eredeti üzenet .
Egyszerűsített diagram
Eltérések az alapsémától
A nem adaptív támadások (és csak azok) elleni biztonság érdekében a protokoll használata nélkül jelentősen leegyszerűsíthető . A titkosításnál a -t használjuk , a visszafejtésnél pedig azt ellenőrizzük .
Példa egy egyszerűsített áramkörre
Tegyük fel, hogy van egy csoportunk . Ennek megfelelően - .
Kulcsgenerálás
A kulcsgeneráló algoritmus a következőképpen működik:
- Alice véletlenszerű és véletlenszerű elemeket generál
- Alice kiszámolja .
- A nyilvános kulcs , a privát kulcs pedig .
Üzenet adott . A titkosítási algoritmus a következőképpen működik
- Bob véletlenszerűen választ .
- Bob a következő értékeket számítja ki:
- ;
- ;
- ;
- Bob elküldi a titkosított szöveget Alice-nek.
A titkosított szöveg vétele és a privát kulcs használata után :
- Alice ellenőrzi az állapotot .
- A feltétel teljesül, így megjelenik a Bob által titkosított üzenet .
Biztonsági igazolás
Tétel
A Cramer-Shope kriptorendszer ellenáll az adaptívan választott rejtjelezett szövegen alapuló támadásoknak a következő feltételek mellett:
- A hash függvényt az egyirányú hash függvények univerzális családjából választjuk ki.
- A Diffie-Hellman diszkriminációs probléma nehéz a csoport számára .
Bizonyítás : A tétel bizonyításához feltételezzük, hogy van egy ellenfél, aki meg tudja törni a protokollt, és megmutatjuk, hogy ha a hash függvény feltétele teljesül, akkor ellentmondást kapunk a Diffie-Hellman probléma feltételével. A valószínűségi algoritmusunk bemenetét a vagy eloszlásból adjuk meg . Felületes szinten a konstrukció a következőképpen fog kinézni: építünk egy szimulátort, amely egy közös disztribúciót fog készíteni, amely a támadássorozatot követően a cracker által a kriptorendszerről alkotott vízióból és a generáló orákulum által generált rejtett b bitből áll (nem tartalmazza a cracker látomása, rejtve előtte). A bizonyítás ötlete: megmutatjuk, hogy ha a bemenet eloszlása , akkor a szimuláció sikeres lesz, és az ellenfélnek nem triviális előnye lesz a b véletlenszerű bit kitalálásában. Megmutatjuk azt is, hogy ha a bemenet a -ból származó eloszlás , akkor az ellenség látása nem függ és -től, és ezért az ellenség fölénye elhanyagolható lesz (kisebb, mint az inverz polinom). Innen megszerkeszthetjük a disztribúciós megkülönböztetőt és : egyszerre futtatjuk a kriptorendszer-szimulátort (prints ) és a crackert (prints ), és kinyomtatja , ha és nem.
Szimulátor építése
A kulcsgenerációs szimulációs séma a következő:
- A szimulátor bemenete .
- A szimulátor a megadott .
- A szimulátor véletlen változókat választ ki .
- A szimulátor kiszámítja .
- A szimulátor véletlenszerű hash függvényt választ, és létrehoz egy nyilvános kulcsot . Szimulátor rejtett kulcsa: .
Látható, hogy a szimulátor kulcs generálása eltér a protokollban lévő kulcs generálásától (ott ).
Dekódolási szimuláció . Ugyanúgy jár el, mint a jegyzőkönyvben, azzal a különbséggel, hogy
Titkosítási szimuláció . Adott bemenettel a szimulátor kiválaszt egy véletlenszerű értéket , kiszámítja és kiadja . Most a következő két lemmából következik a tétel bizonyítása.
Lemmák
1. lemma. Ha a szimulátor terjesztést kap , akkor a támadó kriptorendszerről alkotott elképzelésének és a rejtett bitnek a közös eloszlása statisztikailag megkülönböztethetetlen a kriptorendszer elleni valós támadástól.
2. lemma. Ha a szimulátor eloszlást kap -ból , akkor a rejtett bit eloszlása nem függ a cracker látásmódjának eloszlásától.
Linkek
- Cramer–Shoup kriptorendszer
- Ronald Cramer és Victor Shoup "Egy gyakorlati nyilvános kulcsú kriptorendszer bizonyíthatóan biztonságos az adaptív választott titkosítási támadások ellen." Crypto 1998, LNCS 1462, p. 13ff ( ps , pdf )
- Kamerabolt protokoll