Episode I
Alice és Bob
Kivonat
Az írásbeliség megjelenése óta létezik annak igénye, hogy titkainkat elrejtsük a kíváncsiskodó szemek elöl, illetve hogy mások titkairól lerántsuk a leplet. A kriptográfia, azaz a rejtjelezés és rejtjelfejtés lebilincselő története az idők folyamán drámai hatással volt birodalmak sorsára, háborúk kimenetelére és egyéni sorsok alakulására egyaránt. Napjaink információs társadalmában pedig különösen fontos szerepet játszik, mivel nélküle – sok egyéb dolog mellett – nem létezne Internet, mobiltelefon, vagy bankkártyás fizetés...
Tartalom
I. Információelmélet és kriptográfia
Alice és Bob színrelép
Mi az a rejtjelezés és miért van rá szükség? Mivel foglalkozik a kriptográfia tudománya? Hogyan működik az Enigma, és a feltörése hogyan befolyásolta a 2. világháború kimenetelét? Melyek azok a problémák, amelyek megoldása nélkül ma nem létezne mobiltelefon, bankkártyás fizetés és Internet?
Alice és Bob számítógépezik
Mi a különbség az adat és az információ között? Mivel foglalkozik az információelmélet? Hogyan mérhető az információ mennyisége? Mitől függ, hogy mennyire tömöríthető egy adathalmaz? Mik a tömöríthetőség elvi korlátai? Mi a különbség az analóg és a digitális információ között? Hogyan működik a digitalizálás?
Alice és Bob számolni tanul
Hogyan történik a digitális információ reprezentációja az informatikai rendszerekben? Mik azok a számrendszerek? Hogyan kell elképzelni a számítógépek memóriáját és mi van benne? Hogyan épül fel egy képet tartalmazó file és mit tartalmaz?
Alice és Bob félreérti egymást
Milyen negatív hatással van a csatorna a rajta átküldött bitsorozatra? Hogyan védekezhetünk e negatív hatás ellen? Miért lehet elolvasni egy CD-t akkor is, ha megkarcolódott? Mi az a hibajavító kódolás és ennek mik az elvi korlátai?
Alice és Bob ellenségei
Létezik-e abszolút feltörhetetlen titkosítás? Hogyan működik és mik a limitációi? Milyen képességekkel rendelkeznek a támadók? Hogyan tud Alice és Bob biztonságosan üzenni egymásnak úgy, hogy nem használnak közös kulcsot?
II. Algoritmuselmélet és kriptográfia
Alice és Bob a kiszámíthatóság határán
Mit jelent az, hogy „algoritmus”? Minden feladat megoldható algoritmussal? Mik azok a formális nyelvek? Mikor mondjuk egy problémára, hogy algoritmikusan kiszámíthatatlan vagy eldönthetetlen? Mik az algoritmikus eldönthetőség határai?
Alice és Bob egymillió dolláros kérdése
Mikor tekinthető egy algoritmikus probléma „nehéznek” vagy „könnyűnek”? Mi számít vízválasztónak ilyen tekintetben? Valóban léteznek igazán „nehéz” problémák, vagy csupán ügyetlenek vagyunk? Mit mond erről a számítástudomány legfontosabb megoldatlan sejtése?
Alice és Bob biztonsága
Hogyan tudjuk az algoritmikus problémák nehézségét összehasonlítani egymással? Mit nevezünk Karp-redukciónak és mikor mondjuk egy problémára, hogy NP-nehéz? Kicsoda Babai László és mi a jelentősége 2015-ös felfedezésének? Alice és Bob valóban biztonságban érezheti magát?
Alice és Bob nyilvános kulcsot használ
Hogyan tud Alice és Bob megegyezni egy titkos kulcsban egy nembiztonságos csatornán keresztül? Mik azok az egyirányú függvények és a moduláris aritmetika? Hogyan működik és hogyan támadható a Diffie-Hellman kulcscsere protokoll? Mi az az aszimmetrikus kulcsú rejtjelezés?
Alice és Bob szerződést köt
Hogyan tud Alice és Bob elektronikus szerződést kötni? Lehet-e ilyen szerződéseket hamisítani? Mi a születésnap paradoxon? Mit nevezünk kriptográfiai hash függvényeknek? Mik azok a digitális aláírások és tanúsítványok? Mit nevezünk bizalmi modellnek és hogyan épül fel egy ilyen?
III. A matematika építménye
Alice és Bob számelméletet épít
Hogyan építhető fel egy matematikai elmélet gyakorlatilag a semmiből? Mit nevezünk axiómáknak, amelyek egy ilyen elmélet kiindulópontjai? Mi az a 4 axióma, amelyből következik minden, amit az egész számokról tudunk – és az is, amit még nem tudunk? Hogyan lesz egy állításból tétel?
Alice és Bob rendet tesz
Milyen alaptulajdonságai vannak a szorzás műveletének és mi az oka, hogy ezek valóban teljesülnek? Mik azok a relációk és mit értünk rendezett halmaz alatt? Mi köze ennek a „kő-papír-olló” nevű játékhoz? Hogyan vezetjük be a „kisebb-nagyobb” fogalmát a természetes számok között?
Alice és Bob eladósodik
Mi volt az az absztrakciós folyamat, amelyet őseink is követtek, amikor elkezdtek a „semminél kevesebb” mennyiségekről elmélkedni? Mit lehet az ilyen mennyiségekkel modellezni? Tulajdonképpen mik azok a negatív számok? Hogyan köthető egy ilyen látszólag értelmetlen fogalom a valósághoz?
Alice és Bob gyűrűje
Hogyan tudjuk a szorzás műveletét is ésszerű módon kiterjeszteni a számegyenes 0-tól balra eső részére? Mit jelent az absztrakt algebrában a „neutrális elem”, az „inverz”, a „gyűrű” és a „test” fogalma? Hogyan definiálható a kivonás művelete az egész számok között? Mi a helyzet az osztással?
Alice és Bob az absztrakció útján
Mit jelent a „nullosztómentesség” és az „integritástartomány” fogalma? Hogyan terjesszük ki a „kisebb-nagyobb” fogalmát a negatív számok körére is, és miért fontos ez a kriptográfiai eljárások szempontjából? Milyen absztrakt algebrai megfontolások állnak ennek hátterében, és mit jelent ez általános gyűrűk esetén?
IV. A számelmélet alapjai
Alice és Bob alaptétele
Mit kezdjünk azzal, hogy az „osztás” művelete általában nem végezhető el gyűrűkben? Mit jelent az „oszthatóság”? Mikor mondjuk egy gyűrű valamely elemére, hogy „felbonthatatlan” és mely elemeket nevezzük „prímeknek”? Miért van ezeknek kitüntetett szerepük bizonyos gyűrűkben? Mi a helyzet az egész számok gyűrűjében?
Alice és Bob ókori haverja
Mi az oka annak, hogy minden egész szám egyértelműen felbontható prímszámok szorzatára? Mit jelent a „legnagyobb közös osztó”, és hogyan lehet az iskolában tanult módszernél sokkal gyorsabban kiszámolni az euklidészi algoritmus segítségével? Mik azok az euklidészi gyűrűk és mi közük a számelmélet alaptételéhez?
Alice és Bob felcsavarja a számegyenest
Hogyan lehet „felcsavarni” a számegyenest úgy, hogy az alkalmas legyen kriptográfiai kódoló és dekódoló függvények képzéséhez? Mit jelent a „kongruencia” fogalma, és hogyan lehet ezt általánosítani az úgynevezett „ideálok” és „gyűrűhomomorfizmusok” segítségével? Mik azok a „maradékosztálygyűrűk” és hogyan kell bennük számolni?
Alice és Bob ideáljai
Hogyan néznek ki az egész számok gyűrűjének ideáljai? Mi a kapcsolat az ideálok és az oszthatósági alapfogalmak között? Mik azok a főideálgyűrűk, és ezeknek milyen jó tulajdonságaik vannak? Mi közük az euklidészi gyűrűkhöz? Hogyan zárható le a számelmélet alaptételének kérdése végérvényesen az ideálok segítségével?
Alice, Bob, Euler és Fermat
Mit jelent a kongruencia és a maradékosztálygyűrű fogalma az egész számok esetén? Mik azok a teljes és redukált maradékrendszerek, és milyen tulajdonságaik vannak? Mit mér az Euler-függvény? Mit nevezünk lineáris kongruenciának és mikor létezik megoldása? Mit állít az Euler-Fermat tétel és miért olyan fontos?
V. Az RSA algoritmus és prímtesztelés
Alice és Bob titkosít
Hogyan működik az Internet biztonságát adó RSA nevű aszimmetrikus kulcsú rejtjelező eljárás? Hogyan kell előállítani a publikus és titkos kulcsokat? Hogyan lehet az euklidészi algoritmust lineáris kongruenciák megoldásához is használni? Hogyan kell kiszámítani az Euler-függvény értékét egy adott számra, és milyen információra van ehhez szükség?
Alice, Bob és a kínaiak
Vajon varázslat helyett valójában mi áll az RSA-algoritmus helyes működésének hátterében? Mit állít a kis Fermat-tétel és a kínai maradéktétel, és mi közük van ehhez az egészhez? Mit értünk egy maradékosztálygyűrű dekompozíciója alatt? Hogyan lehet ennek segítségével lényegesen felgyorsítani az RSA-dekódolási algoritmust?
Alice és Bob prímszámok után nyomoz
Hogyan képes Alice és Bob az RSA-kulcsgeneráláshoz szükséges többszázjegyű prímszámokat találni? Hogyan tudják ezt megtenni anélkül, hogy az idők végezetéig osztáspróbákat kellene végezniük? Mik azok a prímtesztek, és pontosan hogyan működnek? Mely számokat nevezzük univerzális álprímeknek, és hogyan tudunk megszabadulni tőlük?
VI. Csoportelmélet és alkalmazásai
Alice és Bob komolyabb fegyverekhez nyúl
Mi az oka annak, hogy a Miller-Rabin-prímtesztre nézve egyáltalán nem léteznek univerzális álprímek? Milyen fegyverek állnak Alice és Bob rendelkezésére egy ilyen jellegű kérdés megválaszolásához? Mik azok a csoportok és mivel foglalkozik a csoportelmélet? Mit állít a Lagrange-tétel, és mi köze a Miller-Rabin-prímteszthez?
Alice és Bob fontos párhuzamokat talál
Mik azok a csoporthomomorfizmusok, normálosztók és faktorcsoportok? Milyen párhuzam mutatható ki ezek és a korábban már ismertetett gyűrűhomorfizmusok, ideálok és maradékosztálygyűrűk között? Milyen szép struktúratartó tulajdonságai vannak egy csoporthomomorfizmusnak? Mik azok a ciklikus csoportok, és összesen hány ilyen létezik?
Alice és Bob átlépi a célvonalat
Mit nevezünk primitív gyöknek, és mi köze ennek a Diffie-Hellman kulcscsere protokollhoz? Milyen esetekben ciklikus egy maradékosztálygyűrű multiplikatív csoportja? Mit állít az úgynevezett Korselt-kritérium a Carmichael-számokról? Hogyan lehet igazolni, hogy a redukált maradékosztályoknak legalább a háromnegyede Miller-Rabin-tanú? Mi a következménye, ha az RSA kulcsok generálásához véletlenül prímek helyett Carmichael-számokat használunk?
Felhasznált irodalom
- BUTTYÁN, Levente – VAJDA, István (2012) Kriptográfia és alkalmazásai. Budapest, Typotex Kiadó. ISBN 978-963-2796-96-3
- CHILDS, Lindsay N. (2009) A Concrete Introduction To Higher Algebra, Springer. ISBN 978-038-7745-27-5
- CONRAD, Keith (2009) Remarks About Euclidean Domains
- CONRAD, Keith – The Miller-Rabin Test
- CORMEN, Thomas – LEISERSOR, Charles – RIVEST, Ronald (1999) Algoritmusok, Budapest, Műszaki Könyvkiadó. ISBN 963-16-3029-3
- DEMETROVICS, János – KATONA, Gyula (2000) Az algoritmusok bonyolultsága. Természet világa, 2000. II. különszám. ISSN 0040-3717
- FOLLÁTH, János – HUSZTI, Andrea – PETHŐ, Attila (2011) Informatikai biztonság és kriptográfia. Budapest, Kempelen Farkas Hallgatói Információs Központ
- FREUD, Róbert – GYARMATI, Edit (2000) Számelmélet. Budapest, Nemzeti Tankönyvkiadó. ISBN 963-19-0784-8
- GYÖRFI, László – GYŐRI, Sándor – VAJDA István (2010) Információ- és kódelmélet. Budapest, Typotex Kiadó. ISBN 978-963-2791-15-9
- KISS, Emil (2007) Bevezetés az algebrába. Budapest, Typotex Kiadó. ISBN 978-963-9664-48-7
- RÓNYAI, Lajos – IVANYOS, Gábor – SZABÓ, Réka (2000) Algoritmusok. Budapest, Typotex Kiadó. ISBN 978-963-2790-14-5
- SINGH, Simon (2007) Kódkönyv – A rejtjelezés és rejtjelfejtés története. Budapest, Park Könyvkiadó. ISBN 978-963-5307-98-2