- Miért kell újragondolni a kriptográfiát a kvantumszámítógépek korában?
- Klasszikus titkosítási módszerek korlátai
- Kvantumrezisztens algoritmusok
- Post-kvantum kriptográfia fő irányzatai: áttekintés
- A klasszikus és kvantum kriptográfia összevetése
- Miért kell időben váltani a post-kvantum kriptográfiára?
- A kódalapú kriptográfia alapjai
- McEliece- és Niederreiter-rendszer működési elve
- Szindrómakódolás mint egyirányú függvény
A McEliece-kriptoszisztéma lényege, hogy egy hibajavító kódot használunk nyilvános kulcsnak álcázva. Ez a kód belül jól strukturált – például egy Goppa-kód –, de kívülről véletlenszerűnek tűnik. A felhasználó olyan transzformációkat alkalmaz a kódrendszer generátormátrixán, amelyek elrejtik annak valódi szerkezetét. A támadó nem lát mást, csak egy véletlenszerű mátrixot – és ez teszi a visszafejtést gyakorlatilag lehetetlenné.
A kulcsgenerálás három részből áll
- Választunk egy kódot, amely hatékonyan dekódolható. Ez jellemzően egy bináris Goppa-kód, amelyet a kódelmélet jól ismer, és amelyhez létezik gyors dekódoló algoritmus (pl. Patterson-algoritmus).
- Generálunk egy S mátrixot, amely véletlenszerű, invertálható és elrejti az eredeti kód szerkezetét soronkénti keveréssel.
- Alkalmazunk egy P permutációs mátrixot, amely az oszlopokat keveri össze.
A nyilvános kulcs ezek után a következő lesz:
G_pub = S × G × P,
ahol G az eredeti kód generátormátrixa. Az így keletkezett G_pub véletlenszerűnek tűnik, és alkalmas titkosításra.
A titkosítás menete egyszerű, de hatékony
A küldő (pl. Alice) először vesz egy üzenetet m, amely egy bináris vektor. Ezt megszorozza a nyilvános kulccsal:
c = m × G_pub + e,
ahol e egy előre meghatározott számú hibát (például t darab 1-est) tartalmazó vektor. Ez a hiba biztosítja, hogy a titkosított üzenet ne dekódolható legyen egy ismeretlen támadó számára.
A dekódolás kulcsa az, hogy a címzett (pl. Bob) ismeri az S, G és P mátrixokat. Ezek segítségével lépésről lépésre:
- Először kiszámolja c’ = c × P⁻¹, így visszaállítja a hibás kódolt üzenetet az eredeti kódrendszerhez igazítva.
- Ezután a hibajavító dekódoló algoritmussal (pl. Patterson) visszafejti az m’ üzenetet.
- Végül m = m’ × S⁻¹, és ezzel megkapja az eredeti titkosítatlan üzenetet.
A Niederreiter-variáns: ugyanaz másképp
A Niederreiter-verzió tulajdonképpen ugyanazon alapelven működik, de mátrix-transzformáció helyett a szindróma-alapú dekódolást használja. Itt a nyilvános kulcs egy paritásellenőrző mátrix, és a titkosított üzenet a hibavektor szindrómája:
c = H × eᵗ.
A dekódolás során a titkos kulcs segítségével visszaállítható a hibavektor, és ezzel az eredeti üzenet. A két rendszer matematikailag ekvivalens, de különböző optimalizálási lehetőségeket kínálnak a gyakorlatban.
Miért nehéz feltörni ezeket a rendszereket?
A támadó a nyilvános kulcsot és a titkosított üzenetet ismerheti, de a hibajavító kód strukturálatlannak tűnik számára, így nincs kapaszkodója az értelmezéshez. Az egyetlen lehetősége, hogy próbál megoldani egy szindrómadekódolási problémát, amely ismert NP-nehéz, még akkor is, ha kvantumalgoritmusokat is alkalmaz.
Sebesség és hatékonyság: nem csak biztonságról van szó
A McEliece-rendszer nemcsak biztonságos, hanem gyors is: a kulcsgenerálás és a dekódolás kis számítási erőforrással végrehajtható. Ez különösen vonzó lehet alacsony fogyasztású eszközökön, például okoskártyákon vagy IoT-rendszerekben. Az egyetlen akadály a kulcsméret, amely továbbra is jelentős – de a hardver fejlődésével ez egyre kevésbé jelent problémát.
Összegzés
A McEliece- és Niederreiter-rendszerek valódi példái annak, hogyan lehet egy klasszikus matematikai struktúrát (hibajavító kód) titkosítási célra alkalmazni. A rendszer egyszerű, gyors, és az egyik leginkább kvantumbiztos megközelítés, amit ismerünk. Bár a kulcsméret kihívást jelent, a rendszer stabilitása és időtállósága miatt az egyik legkomolyabb jelölt a kvantum utáni korszakban.