Egy kis kriptográfiai múlt és jelen

Többször is előfordult, hogy előadtam különböző konferenciákon, meetupokon. Az alábbi írás az egyik gyakori előadásom egy kis részét fedi le, amely a kriptográfiával foglalkozik. Az egyik nagyobb kriptos portálnak is írtam 2018-ban egy hasonlót oktatási célokra.

Titkosítás

A kriptográfia főként rejtjelezéssel, titkosítással és ezek megfejtésével foglalkozó tudományág. Általában abban az esetben használunk kriptográfiai módszereket, ha valamit (pl. egy üzenetet) el szeretnénk rejteni a világ a elől.

Erre általában két dolog adott okot, az egyik a szerelem a másik pedig a háború. Bár mind a kettő körülbelül egy idős az emberiséggel, az első írásos feljegyzések amelyek titkosításról vallanak Julius Caesar idejéből származnak. Suetonius jegyezte le Caesarról a róla elnevezett Caeser rejtjel használatát. A rejtjel mai szemmel nézve nagyon primitív. Használatához nincs más dolgunk, mint az ABC betűit eltolni 3 betűvel jobbra. Így az A betűből C, Á-ból CS, B-ből D lesz…

Példa:

Kódolatlan szöveg: “ÉN ELMENTEM A VÁSÁRBA FÉL PÉNZZEL”

Titkosított szöveg: “hö goógöügó c ydúduec iho shöbbgo”

A kódolás a maga idejében hatékony lehetett, mivel az ellenfelek általában nem voltak írástudók és idegen nyelveket sem nagyon beszéltek, így azt hitték, hogy a szöveg egy számukra ismeretlen nyelven íródott. Ma azonban már mi is fel tudjuk törni, ehhez  csak azt kell tudunk, hogy milyen nyelven íródott. Minden nyelv rendelkezik azzal a tulajdonsággal, hogy bizonyos betűk elég gyakran előfordulnak benne, míg mások ritkábban. Ha ezeket az előfordulási arányokat nem tudjuk fejből, akkor magunk is ki tudjuk számolni. Fogjunk egy oldalnyi szöveget és számoljuk meg, hogy melyik betű hányszor fordul elő benne. A magyar nyelvben pl. a leggyakoribb betű az “e”. Ezek után meg kell számolnunk a betűket a kódolt szövegben is, majd a párokat behelyettesíteni. Ezt nevezik gyakoriság elemzéses kód fejtésnek.

A kód feltörésében nagy segítséget nyújtott, hogy a kódok ismétlődnek, hogy a szöveg hossza egyenlő a kódolt szöveg hosszával és, hogy ismertük a kódolást. Ha nem ismerjük a kódolást, azaz nem tudjuk, hogy ez egy Caesar rejtjel akkor is sikerrel alkalmazhatjuk az előbbi gyakoriság elemzéses fejtést..

Azért vagyunk ennyire hatékony kódfejtők, mert a kódolt üzenetünknek alacsony az entrópiája. Ez nagyon leegyszerűsítve azt jelenti, hogy maga a kódolt üzenet nagyon sok információt tartalmaz az eredeti üzenetről. Minél magasabb az entrópia, minél kevesebb információ áll rendelkezésre és minél kevésbé tudjuk megbecsülni, hogy a következő üzenet mit tartalmaz, annál nagyobb biztonságban vagyunk.

Érdekesség, hogy a Caesar rejtjelezést még 1915-ben is használták. Az orosz katonai vezetés számára a többi titkosítás túl bonyolult volt, ezért ezt alkalmazták, így a németeknek nem volt nehéz dolga az üzenetek dekódolásában

Később aztán persze elkezdték továbbfejleszteni a Caesar módszert, a betűket oszlopokba helyezték, forgatták, stb., de végül mindig is csak az egyszerű helyettesítéses mód maradt, ezért a feltörése nem okozott sokkal nagyobb kihívást. Idővel aztán megjelentek a sokkal bonyolultabb kódolások amelyeket egy bonyolultabb kulccsal lehetett kódolni és ugyanazzal a kulccsal lehetett dekódolni is. Leegyszerűsítve a kulcs mondta meg, hogy mit mire kell cserélni, azonban ez csak az érthetőség miatt elfogadható példa, valójában ennél kicsit bonyolultabb a dolog.
Mivel ugyanazt a kulcsot használjuk a kódoláshoz és a dekódoláshoz is, ezért ezt szimmetrikus kódolásnak nevezzük, mind a két oldalon ugyanaz a kulcs van, tehát fenn áll a szimmetria.

Az informatikában az első ismertebb és elterjedt szimmetrikus kódolás a DES (Data Encryption Standard). A DES-t az 1970-es évek elején fejlesztette ki az IBM majd szabvánnyá is vált. A gond az volt vele, hogy az NSA szerette volna, hogy előtte ne maradjon semmi sem titokban, ezért limitálták a titkosító kulcs méretét 56 bitben, illetve, hogy nem volt teljesen nyilvános az algoritmusa, ezért felmerült a gyanú, hogy hátsó kaput építettek bele. A kulcs hossza azért érdekes számunkra, mert minél kisebb a kulcs, annál kisebb az entrópia, annál könnyebben vissza tudjuk fejteni az üzenetet. A helyzet még rosszabb, ha tudjuk, hogy létezik egy születésnapi támadás nevű elv. E szerint egy 56 bites kulcs feltöréséhez nem szükséges a 256 kombináció, csupán 228. Ezt kihasználva már 1999-ben fel tudták törni pár számítógéppel a DES kulcsokat hozzávetőleg 22 óra alatt. Az algoritmus azonban nem veszett el teljesen, megalkották a Triple DES-t, ami három menetben alkalmazza a titkosítást, ezzel valamivel nagyobb biztonságot nyújtva.

A szimmetrikus titkosító algoritmusokkal vannak problémák. A legnagyobb, hogy mindkét félnek a birtokában kell lennie a kulcsnak, így aki olvasni tudja az üzeneteket az titkosítani is tudja őket, s a kulcsokat is el kell juttatni a másik félhez. A kulcs eljuttatása elég nehéz feladatnak tűnhet. Hogyan tudunk úgy eljuttatni valakinek egy titkos információt, hogy azt csak ő láthassa, de nem tudunk titkosítást alkalmazni, hiszen pont ahhoz van szükség erre az információra?

A megoldás erre is megszületett 1976-ban, méghozzá Whitfield Diffie és Martin Hellman fejében. Róluk nevezték el a módszert Diffie–Hellman kulcs cserének. A lényege, hogy egymásnak csak olyan számokat küldünk ami egy harmadik fél számára önmagában használhatatlan, de mi össze tudjuk belőle rakni a kulcsokat. Persze ezzel is lehetnek problémák (pl. Man In the Middle attack, stb.), de azokra is létezik megoldás (pl. nonce challenge, stb. alkalmazása)

Nem sokkal ezelőtt, ugyancsak 1976-ban született egy teljesen új szemléletű titkosítási eljárás is, az RSA. Ron Rivest, Adi Shamir és Len Adleman fejlesztette ki az RSA nevű algoritmust, a nevét szerényen a neveik kezdőbetűiből rakták össze. Az eljárás lényege, hogy nem csak egy kulcsot használ, hanem kettőt. Egy privát kulcsot és egy nyilvános, publikus kulcsot.

A publikus kulcsot bárkivel megoszthatjuk, míg a privát kulcsot titokban kell tartanunk. Ha valamit titkosítunk a publikus kulcs használatával akkor csak a privát kulcs birtokában tudjuk azt visszafejteni, a privát kulccsal pedig alá is írhatunk, amit a publikus kulccsal tudunk ellenőrizni, de erről később még lesz szó.

Az RSA már sokkal hosszabb kulcsokat használ, mint a DES. 512, 1024, 2048… bit hosszú is lehet egy kulcs. Mivel ez az algoritmus két külön kulcsot használ (privát és publikus) így aszimmetrikus titkosításnak nevezzük.

Az algoritmusa nagyon nagy prímszámokkal dolgozik és a biztonságát az adja, hogy nagy számokat nagyon nehéz prímtényezők szorzatára bontani. Az egyetlenegy hátránya, hogy nagyon lassú, ezért leginkább csak arra használták, hogy a szimmetrikus kulcsokat kicseréljék egymás közt és utána már valamilyen szimmetrikus titkosítással dolgoztak tovább.

A következő nagy lépés az AES (Advanced Encryption Standard) volt. A U.S. National Institute of Standards and Technology úgy látta, hogy ideje a frissítés a titkosítások világában és kiírt egy versenyt amit Vincent Rijmen és Joan Daemen nyert meg az ugyancsak a nevükből eredő Rijndael titkosítással amiből az AES megszületett. Az AES egy szimmetrikus kulcsú titkosítás, 128, 192, és 256 bites kulcsokkal képes dolgozni.

Kiváló a sebessége, azonban pár sikeres támadás már érte ami miatt időnként módosítani kellett rajta.

Hitelesítés

A titkosítás mellett van egy másik része is a kriptográfiának amit a következő probléma szült:

Tegyük fel, hogy kapunk egy titkosított üzenetet X-től amit csak mi tudunk elolvasni. Az üzenet teljesen helyes, azonban:

  • Honnan tudjuk, hogy valóban X küldte? Lehet, hogy más volt?
  • Mi történik, ha X letagadja a küldését?
  • Mi történik, ha X azt állítja, hogy valami mást küldött?

Az üzleti életben egyik sem elfogadható. Ezért a titkosítás mellett nagyon fontos, hogy tudjunk hitelesíteni, azaz a fenti kérdéseket ki tudjuk küszöbölni. Erre a problémára nyújt megoldást a digitális aláírás. A dokumentumokat a privát kulcsunkkal tudjuk aláírni. Ekkor kapunk egy digitális aláírásnak nevezett bájtsorozatot amit hozzá tudunk fűzni az adott dokumentumhoz. Amikor valaki megkapja ezt az üzenetet, a publikus kulcsunk használatával le tudja ellenőrizni, hogy az üzenetet valóban a mi privát kulcsunkkal írták alá és, hogy a tartalma pontosan ugyanaz, mint amit aláírtak.

Ha a mi privát kulcsunkkal írták alá, akkor csak mi küldhettük. Le sem tudjuk tagadni, hiszen csak nekünk van meg a privát kulcs és nem állíthatjuk, hogy mást küldtünk, vagy módosítottak rajta, mert akkor nem lenne érvényes a aláírás.

Ez sok problémát megoldott, de nagy üzenetek esetén bizony komoly számítási teljesítményt követelt egy-egy üzenet aláírása, vagy annak ellenőrzése. Erre kellett

valami megoldást találni és megszületett a Message Digest, vagy hash, magyarul üzenet pecsét, vagy kivonat. A hash lényege, hogy nagyon gyorsan ki lehet számítani az üzenetből és sokkal rövidebb, mint maga az üzenet, a hossza 128-256 bit között van általában ami pár betűnek (kb. egy sor szöveg) felel meg.

A hashnek pár alapkövetelménye van:

  • A hashból ne lehessen visszaállítani az eredeti üzenetet
  • Legyen szinte lehetetlen két olyan különböző tartalmú üzenetet találni, aminek a hashe ugyanaz
  • Ugyanannak az üzenetnek mindig ugyanaz legyen a hash értéke.

Mivel ezeket teljesítik a kivonatoló algoritmusok, így nincs szükségünk már arra, hogy az egész üzenetet aláírjuk. Kiszámítjuk hozzá a hasht és elegendő azt aláírni. A másik fél amikor megkapja az üzenetet ugyanígy kiszámítja a hasht és ellenőrzi, hogy arra érvényes-e az aláírás. Ha igen akkor biztos lehet benne, hogy az üzenet sértetlen, mi küldtük. Ezzel időt / teljesítményt spóroltunk.

Ezeket az eljárásokat használja a blockchain is. Amikor bányászunk akkor ilyen hash-eket számolunk a blokkokhoz, bár ott van némi nehezítés a dologban.

Amikor pedig tranzakciót indítunk (utalunk) akkor a privát kulcsunkkal digitálisan aláírjuk azt. Így valójában a privát kulcs nem ahhoz szükséges, hogy a walletünkhöz hozzáférjünk, hanem ahhoz, hogy a pénzünket el tudjuk költeni. Ha nincs meg a privát kulcsunk akkor nem tudjuk a tranzakciókat digitálisan aláírni. A többi csomópont és a bányászok akkor fogadják el a tranzakciót és akkor teszik bele egy blokkba, ha annak érvényes a digitális aláírása.

A bitcoin és sok más kriptovaluta az ECDSA (Elliptic Curve Digital Signature Algorithm) nevű algoritmust használja digitális aláírásra és az ECDH-t (Elliptic Curve Diffie – Hellman) kulcs cserére.

Az EC algoritmusok lényege, hogy elliptikus görbékkel dolgoznak és a diszkrét logaritmus elliptikus görbék feletti kiszámolásának problémája adja a biztonságukat.

Így, már tudjuk, hogy aki beküldte a tranzakciót az valóban az akinek állítja magát, de semmi sem gátolja meg, hogy azt később kitörölje, vagy egy másikat tegyen a helyére. Erre ad megoldást a blokklánc.

A blokkláncban minden blokk tartalmazza az előző blokk kivonatát (hashét), így ennek köszönhetően vissza tudjuk ellenőrizni, hogy az adott blokk módosítva lett, vagy érvényes. Ha kiszámoljuk az 1345. blokk hashét és az nem egyezik a következő blokkban (1346) tárolt hash értékével, akkor tudjuk, hogy érvénytelen az adatunk. Az, hogy az 1345-ös, vagy az 1346-os blokk az érvénytelen könnyen le tudjuk ellenőrizni, ehhez csak ugyanazt az ellenőrzést kell futtatni az 1346-os blokkra is.

Ahhoz, hogy egy blokkot módosítsunk, minden utána következő blokkot meg kell módosítani. Mivel a blokkot létrehozásához magas számítási teljesítmény kell, így erre nem sok esélyünk van. Csak akkor tudjuk megtenni, ha az összes számítási teljesítmény 51%-ával mi rendelkezünk. Ez olyan magas érték, hogy, ha lehetőségünk is lenne elérni, pénzügyileg már nem érné meg csalni.

Az ECDSA matematikájáról itt írtam korábban.

Szólj hozzá és MicroCoinnal jutalmazunk! Nézd meg mennyi MicroCoint gyűjtöttél eddig az oldalon!

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük