Aszimmetrikus kriptorendszerek

Budapesti M szaki F iskola – Kandó Kálmán Villamosmérnöki F iskolai Kara Számítógéptechnikai Intézet - Székesfehérvár

Aszimmetrikus kriptorendszerek Segédlet az Információtechnika c. tárgy Kriptográfia fejezetéhez

Dr. Tóth Mihály f iskolai tanár és Prof. Randall K. Nichols George Washington University

Táskaszám:

2000. október

SKITALI Spártai vezéri pálca, amit a rátekert szalaggal titkosításra is használtak. Az American Cryptogram Association (ACA) hivatalos szimbóluma

El szó az Információtechnika c. tárgy segédlet-sorozatához.

A Budapesti M szaki F iskola Kandó Kálmán Villamosmérnöki F iskolai Karán az 1998/99 tanévben (akkor még az integráció el tt a Kandó F iskolán) a f iskola székesfehérvári Számítógéptechnikai Intézetében (SzGTI) vezették be a villamosmérnök hallgatók számára az Információtechnika c. tárgyat, ami azzal foglalkozik, hogy mi is jellemzi a digitális (diszkrét) információt annak a forrásánál és milyen lényeges dolgok történnek vele a továbbítása során. Nem foglalkozik a tárgy a jelfeldolgozás kérdéseivel és a távközlési informatikával is csak annyit, amennyi a többi fejezethez feltétlenül szükséges. Megérett azonban az id arra, hogy az információ kódolásának, titkosításának, elrejtésének és tömörítésének legfontosabb kérdéseit egy külön tárgyban foglaljuk össze. A következ blokkvázlat szemlélteti, hogy hogyan is kapcsolódnak egymáshoz az említett fogalomkörök. HIBAVÉDELMI KÓDOLÁS ILLESZT4 KÓDOLÁS INFORMÁCIÓ VÉDELEM ÉS TITKOSÍTÁS

INFORMÁCIÓ FORRÁS

Csatorna

TÖMÖRÍTÉS

Tárolás, vagy továbbítás

Az INFORMÁCIÓ ELREJTÉSE (Szteganográfia)

A blokkvázlat jobboldali három funkciója közül a titkosítás meg is el zheti a hibavédelmi kódolást és a titkosítást követheti is az információ elrejtése. E három funkció közül akár mindegyik is alkalmazható egy folyamatban. Itt, az aszimmetrikus kriptorendszerek bevezet jében mindössze elhelyezni szerettük volna ezt a stúdiumot a vázolt folyamatban, megjegyezve, hogy az aszimmetrikus kriptorendszerek az információvédelem és a titkosítás témakörébe tartoznak. Az Információtechnika c. tárgyhoz készül f iskolai jegyzet egy-egy „kerek” fejezetét annak elkészültekor segédletként jelenteti meg a f iskola és mind e segédletek anyaga, mind a hozzájuk kapcsolódó el adói prezentációk, hallgatói projektmunkák, feladatok és egyéb segédanyagok (egy kivétellel) elérhet k az SzGTI hálózatán. Kivétel az a kjereken 10 évvel ezel tt megírt segédlet, amelynek címe: Bevezetés a hibavédelmi kódolás és áramkörök elméletébe és a szerz i dr. Tóth Mihály és dr. Hudoba György. Tervezzük azonban, hogy ehhez a témakörhöz is írunk egy újabb segédletet.

1

Az Információtechnika c. tárgyhoz eddig elkészült új segédletek a következ k: 1. Bevezetés az információelméletbe. Dr. Tóth Mihály, 2000. február. 2. A DES (Data Encryption Standard) – Randall K. Nichols könyve alapján interpretálta dr. Tóth Mihály; 2000 február. (Ez a fejezet kés bb valószín leg a „Szimmetrikus kriptorendszerek” címet kapja majd.) Az els felöleli az információforrással és az illeszt kódolással kapcsolatos studiumok anyagát, a második pedig az un. szimmetrikus kriptorendszerekkel kapcsolatos 1 studiumok többségét. Az utóbbi az Információtechnika c. tárgy Kriptográfia fejezetének része a jelen segédlettel együtt. Meg kell említeni, hogy az aszimmetrikus kriptográfia (a ma használatos algoritmusai leírásaival együtt) akkora anyag, hogy ez a segédlet csak az els részét öleli fel. A megkezdett felsorolás tehát imígyen folytatódik majd 1. Aszimmetrikus kriptorendszerek: Az elvi alapok és a knapsack titkosítás. Dr. Tóth Mihály és Randall K. Nichols (GWU) 2000. október 2. Aszimmetrikus kriptorendszerek alkalmazásai: hibrid rendszerek. A digitális aláírás és a PKI. Az üzenetrejtés (szteganográfia) és az elektronikus vízjelek. (Várhatóan 2001 tavaszán.) valószín , hogy az I. és a II. rész összetartozása (pl. a szószedet) miatt a két rész egyben fog megjelenni. Már most megjósolható egyrészt, hogy az Információtechnika c. tárgy egyes studiumai kés bb majd önálló tárgyként is megjelennek és az ábrán vázoltnál sokkal tágabb környezetben. Pl. a kriptográfiával szoros kapcsolatban álló elektronikus kereskedelem, fizet eszközök és módok, valamint a személyi kulcsok infrastruktúrája bizonyosan tantárgy lesz a m szaki menedzser szakos hallgatók számára is. Másrészt a tárgykör olyan új fejezetekkel fog b vülni, mint a titkosított információk megfejtése (=feltörése), azaz a kriptanalízis, a számítógéphálózatok biztonsági kérdései, kódolási kérdések a telekommunikációban és a m sorszórásban és így tovább.

1

Egy-két kiegészít írással együtt, amelyek az SzGTI hálózatán –vagy más megadott webkiköt kön- magyarul hozzáférhet k. 2

Tartalomjegyzék El"szó az Információtechnika c. tárgy segédlet-sorozatához...................................... 1 Tartalomjegyzék.......................................................................................................... 3 Bevezetés ................................................................................................................... 5 Az egyirányú függvények............................................................................................ 8 Kiszámíthatatlanság (kikövetkeztethetetlenség, intractability) .................................... 9 A lefedési probléma .................................................................................................. 12 A titkosított szöveg megfejtése ................................................................................... 5 A.1 Gyakorló feladat ................................................................................................. 10 A.2 Gyakorló feladat ................................................................................................. 10 Összefoglalás a Knapsack titkosításhoz................................................................... 11 Néhány gondolat a nyiltkulcsú kriptorendszerekrõl................................................... 13 Az aszimmetrikus üzenet-titkosítás mûködése.......................................................... 17 Az egyirányú függvények.......................................................................................... 21 Az aszimmetrikus kriptográfia általános elvei............................................................ 24 A nyíltkulcsú titkosításhoz használt számelméleti problémák összefoglalása........... 29 A munkatényezõ (=Work Factor) .............................................................................. 30 A kriptorendszerek élettartama ................................................................................. 33 A nyiltkulcsú kriptográfia elõnyei. A kulcs-menedzsment.......................................... 34 Az aszimmetrikus kriptorendszerekben alkalmazott matematikai módszerek nehézségei ............................................................................................................... 38 A kriptográfiai funkcionalitás ..................................................................................... 39 Az egészszámok faktorizációján alapuló rendszerek ................................................ 39 Az RSA rendszer biztonsága .................................................................... 40 Az RSA rendszer implementációja............................................................ 40 Az RSA algoritmus.................................................................................................... 42 Összefoglalás és köszönetnyílvánítás ...................................................................... 46 I. FÜGGELÉK A lineáris helyettesítés matematikai háttere ................................ 48 II. FÜGGELÉK Az m modulusra és a t szorzóra valamint az utóbbi inverzére vonatkozó néhány hasznos tétel........................................................................... 53 III. FÜGGELÉK A Knapsack titkosítás algoritmusa. ............................................ 54 Kulcs generálás Knapsack titkosításhoz. ............................................................ 54 A publikus kulcs: A ................................................................................................... 57 Titkosított szöveg (ciphertext) elõállítása adott publikus kulccsal (= Enciphering)............................................................................................................ 58

3

A blokkhosszúság ..................................................................................... 58 A címzett nyilvános kulcsa........................................................................ 58 A titkosítandó nyílt szöveg ........................................................................ 58 A titkosítás ................................................................................................ 58 Titkosított szöveg megfejtése saját privát kulccsal (Deciphering) .................... 59 A rutin kiinduló adatai: .............................................................................. 59 A saját titkos kulcs adatai ......................................................................... 59 A megfejtendõ ciphertext és az az A vektor,............................................. 59 A nyílt kulcs ellenõrzése ........................................................................... 59 A C vektor transzformációja...................................................................... 59 A nyíltszöveg betüpárjaihoz tartozó bináris blokkok meghatározása ........ 59 A.4. Példa ................................................................................................. 60 IV. FÜGGELÉK Rövid áttekintés a matematikai bonyolultságelméletrõl a kriptográfia szempontjából. ................................................................................... 64 V. FÜGGELÉK Az RSA titkosítás demo programja.............................................. 77 TÁRGYMUTATÓ ...................................................................................................... 80 SZAKIRODALOM ..................................................................................................... 83

4

Bevezetés A szerz alapvet en Randall K. Nichols professzor Guide to Cryptography c. könyvének [1] a gondolatmenetét követte, ezért is jelölte meg Nichols professzort —az beleegyezésével— társszerz ként. Ez a segédlet azonban nagyon sok helyen jelent sen eltér Nichols professzor könyvét l és kitér egy csomó olyan részletre is, amellyel Nichols professzor nem foglalkozik. A lábjegyzetek pl. kivétel nélkül a magyar szerz magyarázó kommentárjai, de sok olyan rész van a f szövegben is, amely a magyar szerz önálló munkája, vagy más forrásokat használt hozzájuk. Hadd hangsúlyozzuk itt, hogy lényeges megállapítások/kijelentések vannak a lábjegyzetekben is. Ezek többnyire csak azért kerültek lábjegyzetbe, hogy egy logikus gondolatkör „f ágától” ne térjünk el, s a lábjegyzetek állításainak fontossága egyáltalán nem kisebb mint a f szövegé. A lábjegyzetekben leírtak nem másodrend fontosságúak és azoknak a hallgatóknak, akiknek vizsgázniuk kell ebb l az anyagból, vizsgaköteles a lábjegyzetek anyaga is. A jegyzet megírásakor problémát jelentett az, hogy milyen elméleti háttérre számíthat a szerz az ebb l készül hallgatóknál. Egy csomó elvi kérdést megtanulnak az SzGTI hallgatói a Számítástechnika matematikai alapjai c. tárgyban, továbbá itt is hivatkozott alapismeretekre tettek szert a 2 Digitális technika I. c. tárgyban . Egy az Információtechnikával kapcsolatos hallgatói felmérés javasolta, hogy az elvi alapokat a konkrét alkalmazáshoz köt d en kellene megtanítani. Ez persze általában nem lehetséges és nem is szokásos. Mégis, az ismeretek felfrissítését szolgálják ebben a jegyzetben az „Álljunk meg egy szóra...” kezdet keretes betétszövegek. Ezek maguk nem részei az éppen tárgyalt gondolatmenetnek, de rövid magyarázatot adnak az ott és akkor el forduló fogalmakra. Ha olyan hosszú háttérmagyarázatra volt szükség, ami semmiképp sem fért bele egy lábjegyzetbe, vagy egy keretes betétszövegbe, akkor a szerz ezeket függelékekben közölte. Ezt tette Nichols professzor is az említett könyvében s van olyan függeléke, amelyet egy-az egyben átvett egy matematikus szerz t l, de sejtetni engedi, hogy saját maga nem feltétlenül vállal felel sséget az átvett szövegért. Egy ilyen függeléket (nevezetesen a XIV. Függeléket) e sorok szerz je Nichols professzor idézett könyvének C. Függelékéb l interpretálta. A magyar szerz nincs arról meggy z dve, hogy a függelékekben tárgyalt matematikai háttér ismerete feltétlenül szükséges a f iskolai hallgatóknak, ezért nem tekinti azt vizsgaanyagnak. Ha a f szöveg olvasója egyszerüen tudomásul vesz egyes új fogalmakat és nem érdekli azok mélyebb matematikai háttere, akkor a függelékek nélkül is megértheti, hogy mir l van szó. A függelékek általában szervesen kapcsolódnak a f szöveghez és lényeges ismereteket tartalmaznak, de a f szövegbe való beépítésük egyrészt megszakította volna a f mondanivaló logikai gondolatsorát, másrészt a függelékek azért b vebbek annál mintsem, hogy lábjegyzetként lehetett volna azokat a szöveghez kapcsolni. 2

Többek között a formális nyelvek és a hozzájuk rendelhet absztrakt automaták alapfogalmairól van szó, amelyeket az 1999/2000. tanévi tantervmódosításkor –sajnoskivettek a Digitális technika c. tárgyból s most nincs más tárgy (az Információtechnikát megel z en), amelyben ezekr l szó lenne. 5

A szerz a III. Függelékben egy titkosítási eljárás komplett algoritmusát is leírta. Ehhez egy professzionális programozó (Tóth Zsolt – Ictus Bt.) jóvoltából egy három rutinból álló Delphi program is tartozik, amely az SzGTI hálózatán szintén hozzáférhet . A III. Függelék azt példázza, hogy ha egy kriptográfiai módszer (mint amilyen pl. a knapsack titkosítás) nem is látszik túl bonyolultnak, az azt megvalósító algoritmus megvalósításakor mégis nagyon sok mellékkörülményre kell tekintettel lenni. Az aszimmetrikus kriptográfiával kapcsolatban el kell mondani, hogy a korábban tárgyalt „történelmi” kriptorendszerek alkalmazásakor a megfejt nek (kriptanalizátornak) nincs különösebb gondja a megfejtéssel, ha ismeri a titkosítás módszerét. Képletesen szólva a titkosítási módszer ismerete az az ék, amellyel el lehet kezdeni az üzenetet véd titkos burok feltörését. A szimmetrikus (klasszikus) kriptorendszerek els rend célja a titkosság biztosítása volt. Még a nagyon is kifinomult DES rendszer esetében is azonos a titkosítás és a 3 megfejtés kulcsa. Ha magát a titkosítási módszert nyilvánossá tesszük ez bizonyos szempontból magát 4 a védett titkot szolgáltatja ki. Vannak azonban kriptorendszerek amelyek esetében a módszer nyugodtan publikussá tehet és mégis megfelel titkosítási biztonságot nyújtanak. A kriptoanalitikusnak rendelkezésére áll maga a titkosítási rendszer, mégsem képes az azzal titkosított üzenetet feltörni. Tulajdonképpen így m ködik a nyilvános kulcsú kriptográfia. A titkosítás módja nyugodtan nyilvánosságra hozható. A kriptográfia e formáját más néven aszimmetrikus kriptográfiának nevezik, mert két különböz kulcsot alkalmaz. Ezek közül egyiket a küld , a másikat pedig az üzenet fogadója alkalmazza. 1974-75-ben a Stanfordon dolgozó Whitfield Diffie és Martin Hellman, valamint Ralph 5 Merkle a Californiai Berkeley egyetemr l új módszert fedeztek fel a kriptográfiában, amelynek mélyreható hatása volt az abban alkalmazott technikákra. Forradalmi ötletük az volt, hogy biztonsággal közreadható a titkosítási módszer és az említett két titkosítási kulcs közül is az egyik (de csakis az egyik). Ezt a nyilvánosságra hozott kulcsot –mily meglep - nyilvános (publikus) kulcsnak nevezik. Lényeges, már itt megemlíteni, hogy maga a módszer két kulcsot alkalmaz és teljesen mindegy, hogy e két kulcs közül melyiket tesszük publikussá. A lényeg, hogy a másikat titokban tartsuk (= privát kulcs). Ez a brilliáns ötlet egy újfajta kriptográfia megszületését jelentette. Az, hogy kiadják a titkosítási módszert, tulajdonképpen kiadja a megfejtési módszert is, mert az egyik a másiknak a matematikai inverze. 3

Ez persze nem egészen igaz, de a részletekre alább még visszatérünk. Elég itt annyit említeni, hogy bizonyos esetekben a megfejtéshez nem magátba titkosítási kulcsot, hanem annak valamilyen értelemben vett inverzét használjuk.

4

Persze éppen a DES rendszer részletes tárgyalásakor láttuk, hogy akkor sem volt hozzá feltörési algoritmus, ha maga a módszer (a teljesen nyilvános szabvány miatt) mindenki által megismerhet volt. A kulcs ismerete nélkül egyedüli feltörési módszer maradt a nyers er módszere annak az irreálisan nagy számítási igényével együtt.

5

New Directions in Cryptography. IEEE Transactions on Information Theory, IT-22 Vol 6. pp.644-654. (1976) 6

A nyilvános kulcsú rendszerekben —a korábbiakhoz képest— a nagy különbség az un. munka-tényez (work factor), amit a megfejtés igényel akkor, ha az (illetéktelen) megfejt nem ismeri a kulcsot. Ehhez, ti. az illetéktelen megfejtéshez még a mai legmodernebb számítástechnika mellett is esetleg száz év nagyságrend id szükséges, vagy még ennél is sokkal hosszabb. Ha valóban ez a helyzet, akkor nyugodtan nyilvánossá tehetjük a titkosítás módját, mert gyakorlatilag úgy sem megy semmire vele az illetéktelen kiváncsiskodó. Ez a nyilvánossá-tétel gyakorlatilag nem kompromittálja a kriptorendszert. Végeredményben tehát a megfejtés munkaigényessége a biztonság záloga. A DES-szel foglalkozó fejezetben bemutattuk egy táblázatban, hogy 40 és 56-bites kulcsok esetében mekkora nagyságrend számítástechnikai beruházás és mennyi id szükséges a kulcsok nyers er vel való feltöréséhez. Természetesen a táblázatban megadott adatok a számítástechnika fejl désével javulnak, de közben maga a kriptográfia is fejl dik és amellett, hogy egyre bonyolultabb, egyre nehezebben feltörhet módszereket alkalmaz, a kulcsok hossza is egyre növekszik. Pl. a „szimpla” DES-t 2001-ben felváltó AES minimális kulcshosszúsága legalább 128 bit lesz, de ennél hosszabb kulcsokkal is m ködhet. A matematika egy külön ága az un. bonyolultságelmélet, amely különböz számítások bonyolultságával foglalkozik. Segít abban, hogy megértsük, hogy mennyi id re van szükség és milyen számítási kapacitást kell adott esetben alkalmazni. A XIV. Függelék rövid áttekintést ad a matematika e fejezetér l. Hadd jegyezzük meg azonban mindjárt itt az elején, hogy ezt a függeléket Nichols professzor egy az egyben vette át Arto Salomaa-tól, aki világhír finn matematikus és hírnevét a formális nyelvek és az absztrakt automaták matematikai alapjainak kidolgozásával vívta ki. Annak az olvasónak a számára, aki korábban nem foglalkozott ezekkel a területekkel, igen nehezen, vagy sehogysem érthet Salomaa bonyolultságelméleti összefoglalója. A gond az, hogy Nichols professzor használja pl. a „polinomiális id ” fogalmát s a XIV. Függelékb l kellene kiderülnie annak, hogy ez pontosan mit jelent, honnan ered az elnevezés. A XIV. Függelék azonban sokmindent megvilágít, de erre a fogalomra pl. nem ad megnyugtató magyarázatot, mert feltételezi olyan absztrakt algebrai fogalmak ismeretét, amelyekket manapság rendszerint nem tanítanak a m szaki fels oktatásban. Legalább is a f iskolákon nem. A bonyolultságelméletet a formális nyelvekkel és az azokhoz rendelhet absztrakt automatákkal (közülük is a Turing géppel) teszi matematikailag precízzé, de sokszorosan több új fogalommal találkozik az olvasója, mint az az egy-két új fogalom, amit megmagyarázni hivatott volna. Mindezek ellenére azonban, ha az Olvasó megelégszik a heurisztikus értelmezésekkel, akkor a XIV. Függelék nélkül is megérthet ek a magyarázatok.

7

Az egyirányú függvények

Nem csak a való életben, hanem a matematikában is léteznek egyírányú utcák. 6 Nagyon egyszer A-tól B-ig eljutni, de gyakorlatilag lehetetlen B-t l A-ig. A titkosítási folyamatot úgy tekinthetjük, mint az A-ból B-be való eljutás folyamatát. Ha ez a folyamat egyirányú, akkor aránylag könnyen eljuthatunk A-ból B-be, de gya7 korlatilag lehetetlen B-b l A-ba eljutni. Ha csak a szokásos telefonkönyv áll a rendelkezésünkre, akkor abban könnyen megtalálható egy barátunk telefonszáma, de (ha nem fordulunk a tudakozóhoz, amelynek van „inverz telefonkönyve” is) akkor igen nehéz lenne a közönséges telefonkönyv alapján meghatározni, hogy ki egy adott telefonszám birtokosa. Ezen az alapon tulajdonképpen egy aszimmetrikus kriptorendszert is felépíthetünk.

8

Vegyük egy adott város telefonkönyvét (ez lesz az egyik kulcs) és titkosítsuk a nyílt szövegünk minden egyes betüjét úgy, hogy keresünk a telefonkönyvben egy nevet, amely éppen a titkosítandó betüvel kezd dik, s a hozzátartozó telefonszámot írjuk a titkosított szövegbe. Figyeljünk fel arra, hogy egy-egy betühöz általában nagyon sok név és telefonszám tartozhat, ezért ugyanaz a nyíltszöveg nagyon sokféleképpen titkosítható. Ezért ez a rendszer amellett, hogy többábécés (polyalfabetikus) rendszer 9 ráadásul még nondeterminisztikus is. A legális címzett (és csakis ) persze rendelkezik egy olyan telefonkönyvvel, amelyben a telefonszámok vannak (pl. növekv sorrendben) felsorolva és bármelyik telefonszámhoz megkeresheti benne az ahhoz tartozó nevet. (pontosabban ez esetben csak a név kezd betüjét). Ez az „inverz telefonkönyv” a másik kulcs.

6

A közlekedési szabályokat kevésbé tisztel (és gyalogosan is sokat közleked ) magyar állampolgárnak valószín
7

Sokkal meggy z bb mindjárt egy matematikai példával élni, amit (némi módosítással) ténylegesen alkalmaznak is a nyilvános kulcsú kriptográfiában: Nem különösebben nehéz pl. prímszámokat összeszorozni még akkor sem, ha nagyon sok prímtényez szorzataként igen nagy számot állítunk el . 300 éve nem találnak azonban olyan algoritmust, amellyel egy összetett szám egyszer<en prímtényez ire lenne bontható. Pl. egy 10100 nagyságrend< összetett szám prímtényez inek meghatározása szinte reménytelen feladat. Nos a prímszámok szorzatának kiszámítása tipikusan egyirányú matematikai m
8

Ez a telefonkönyves példa Arto Salomaa-tól származik és nagyon közérthet en szemlélteti az aszimmetrikus kriptográfia jellemz tulajdonságait. Alább majd még többször hivatkozunk rá.

9

Figyeljünk fel arra, hogy, hogy a nyílt szöveg minden egyes betüjét egy-egy véges halmazból véletlenszer<en választott egy-egy elemre (ti. egy telefon-el fizet telefonszámára) képezzük le. A nyílt szöveg betüi és az említett halmazok között persze determinisztikus kapcsolat van. A nondeterminisztikus jelleget az viszi bele ebbe a leképezésbe, hogy a determinisztikusan meghatározott halmaz elemei közül véletlenszer<en választunk ki egyet az éppen kódolni kívánt betühöz. (Lásd az ábrát a 52. oldalon!) 8

Szokás az ilyen egyirányú eljárásokat „csapóajtónak” (trapdoor function) is nevezni annak a jelzésére, hogy egy ilyen ajtón az egyik irányban könny keresztülhaladni, de az ellenkez irányban annál nehezebb, s csak az illetékes képes erre, aki ismeri a csapóajtó nyitját. Kiszámíthatatlanság (kikövetkeztethetetlenség, intractability)

A nyilvános kulcsú kriptográfia tanulmányozása szorosan kapcsolódik az egyirányú függvények ötletéhez. Ha egy x argumentum értéke adott, akkor aránylag könnyen kiszámíthatjuk az f(x) függvényértéket, de az egyirányú függvények esetén igen nehéz f(x) ismeretében kiszámítani az x argumentum értékét. 10

Ezt a tulajdonságot nevezzük kiszámíthatatlanságnak, bár pontosabb kifejezés lenne a „kikövetkeztethetetlenség” kifejezést használni, csak éppenséggel igen körülményes.

KÖNNYEN KISZÁMÍTHATÓ

x

f(x) GYAKORLATILAG KISZÁMÍTHATATLAN

Ez a kiszámíthatatlanság az oka annak, hogy a kulcs ismerete nélkül a titkosított szöveg feltörése csak úgy lehetséges, hogy minden elképzelhet kulcsot kipróbálunk. 56 56 bites kulcs esetében nyilván 2 különböz kulcs lehetséges, ami igen nagy szám ugyan, de véges. Ezt a módszert, nevezetesen minden lehetséges kulcs kipróbálását, nevezik a nyers er" (brute force) módszerének. f(x) egy sor titkosító függvény bármelyike lehet – köztük nemdeterminisztikus függvényeké is. Ezek között olyan, a matematikai tanulmányokból egyáltalán nem ismer s függvény is lehet, mint amit a fenti telefonkönyves példában szemléltetésképp bemutattunk. A következ kben az un. lefedési probléma kapcsán majd példaként bemutatunk egy ilyen f(x) függvényt, amely szintén nem hasonlít a matematikai analízisben megszokott függvényekre. Ezért a kriptográfiában alkalmazott függvényeket szokás transzformációknak is nevezni.

10

Nevezetesen azt, hogy f(x) ismeretében reális id és/vagy számítási kapacitással kalkulálva nem tudunk visszakövetkeztetni az x argumentum értékére. A gyakorlatban használnak olyan egyirányú függvényeket is,, amelyek tényleg nem számolhatók ki viszafelé. 9

Az egyirányú függvények biztosítják, hogy az illetéktelen megfejt szempontjából a transzformációt gyakorlatilag ne lehessen visszafejteni. A legális címzettnek persze rendelkeznie kell a „csapóajtó” nyitjával, amellyel f(x) –b l aránylag könnyen vissza tud következtetni x –re. Még egyszer összefoglalva az elmondottakat a kriptográfiai egyirányú függvénynek alapvet en a következ két tulajdonsággal kell rendelkeznie: 1. f(x) –nek aránylag könnyen kiszámíthatónak kell lennie adott x –b l.

11

2. x –nek gyakorlatilag kiszámíthatatlannak (intractable) kell lennie f(x) –b l. Nem létezik azonban egzakt bizonyítás a 2. pontban említett kiszámíthatatlanságra. Ez azt a tényt tükrözi, hogy a bonyolultságelméletben igen nehéz alsó határt megszabni valaminek a bonyolultságára. A nyíltkulcsú kriptográfia szempontjából azonban minden olyan függvény alkalmazható, amely a fenti két kritériumot legalább gyakorlatilag kielégíti (ha elméletben nem is). Másrészr l azonban a kiszámíthatatlanság megitélése eléggé szubjektív dolog. El fordulhat, hogy a kriptorendszer megalkotója kiszámíthatatlannak itél egy általa csakis egyirányúnak vélt függvényt és mégis el kerül egy kriptoanlitikus, aki képes a rendszert feltörni. Ezért van aztán, hogy egyegy új rendszer szabványosítása el tt igen komoly díjakat t znek ki a rendszer feltörésére. Ennek az a célja, hogy ha van a rendszernek gyenge pontja, akkor az derüljön ki, miel tt szabványosítanák. 12

Salomaa a Nyiltkulcsú kriptográfia c. m vében nagyszer példákat mutat be az egyirányú függvényekre. Az meghatározása szerint egy problémát akkor nevezünk kikövetkeztethetetlennek (intractable), ha nem létezik algoritmus a probléma megol13 dására. Ha viszont létezik megoldási algoritmus, akkor a probléma kikövetkeztethet (tractable).

11

Itt külön nem említjük, de determinisztikus esetekben f(x)-nek egyérték< függvénynek kell lennie, azaz minden x-hez csak egyetlen f(x) függvényérték tartozhat. A szimmetrikus kriptorendszereknél f(x) inverzének is léteznie kell, az aszimmetrikus kriptorendszereknél nem f(x) inverz függvényének kell léteznie, hanem ennél bonyolultabb feltételeknek kell teljesülnie.

12

Ugyanarról a finn szerz r l van szó, aki vagy 25 évvel korábban, amikor a kriptográfia elméleti háttere még nem alakult ki, a formális nyelvek és az absztrakt automaták elmélete területén írt alapvet m
13

Érdemes megjegyezni, hogy az absztrakt automaták körében a Turing géppel nem megoldható problémák éppen azok, amelyeknek nincs megoldási algoritmusuk. (Ekkor a Turing gép sohasem áll meg.) A következ kben látni fogjuk, hogy a kiszámíthatatlanság matematikai definiciója éppen azzal hozható kapcsolatba, hogy van-e olyan Turing gép, amely végesszámú lépésben képes megoldani az adott problémát. (Ha létezik ilyen Turing gép, akkor az egy polinommal definiálható.) 10

KönnyNnek nevezzük egy probléma megoldását, ha létezik hozzá olyan megoldó 14 algoritmus, amely polinomiális id"ben számolva aránylag rövid id alatt (low polynomial time) megoldja azt. Ilyenkor feltétlenül létezik egy a megoldást realizáló 15 Turing gépet meghatározó polinom. Az un. nem polinomiális NP problémák esetében viszont nincs olyan Turing gép, amely végesszámú lépésben megoldani képes az NP problémát és persze nincs olyan polinom sem, amely meghatározná az adott problémát megoldó Turing gépet. Jegyezzük meg a teljesség kedvéért, hogy az ilyen (kiszámíthatlan) problémára az NP komplett kifejezést használjuk. Az NP komplett problémák tehát kiszámíthatatlanok (kikövetkeztethetetlenek).

16

A mondottak miatt az egyirányú függvényekre felírt két követelmény közül a másodikat egy kevésbé szigorú feltétellel szokás helyettesíteni: beérjük azzal, hogy az inverz transzformáció látszólag kiszámíthatatlan. A matematikai kiszámíthatatlanság szemléltetésére kiváló példát ad az un. lefedési 17 problémák osztálya. A lefedési problémák lényegének a megértése segít abban, hogy megértsük azokat az általános elveket, amelyek megalapozzák a nyiltkulcsú kriptográfiát.

14

Elég itt annyit tudni err l a fogalomról, hogy összefüggésben van azzal, hogy egy Turing gép hány lépésben oldja meg az adott problémát és nem jelent tényleges id t. Alkalmas azonban arra, hogy a mindenkori számítási technológia szintjén összehasonlítsa két különböz megoldás id igényét, meghatározza a megoldási id k arányát. Tehát relatív mértékr l van szó, mint ahogyan a „könny<” fogalommal kapcsolatban is joggal kérdezhetjük, hogy mihez képest könyny< a megoldás.

15

Ahhoz, hogy a „polinom” kifejezés itt használt fogalmát megértsük, elég mély absztrakt algebrai ismeretekre, nevezetesen az un. Galois test-tel kapcsolatos tételek ismeretére van szükség. Olyan polinomokról van szó ugyanis, amelyek számelméleti gyürüt alkotnak és az együtthatóik egy prímhatvány rend< Galois test elemei.

16

Ezzel –és a Turing gép, valamint az ahhoz tartozó polinom fogalmának a segítségével- elvileg definiáltuk a kiszámíthatatlanságot. Lényegében azonban a kiszámíthatatlanság nem kezelhet fogalma helyett az ugyanúgy kezelhetetlen NP komplettség fogalmát vezettük be. Itt kell (el ször) megemlíteni, hogy e problémakör fogalmait (így a polinomiális id fogalmát is) a XIV. Függelék hivatott összefoglalni úgy, ahogyan azt Arto Salomaa leírta. És eléggé kemény elvi szinten írta le!

17

Az angol eredetiben „class of knapsack problems” azaz a „hátizsák problémák osztálya”. Mármost vagy nem szabad lefordítani a „knapsack” (hátizsák) szót, vagy pedig egy a magyarban szemléletesebb szót kell találni a fogalom megnevezésére. A magyarázatból kiderül majd, hogy miért választotta a magyar szerz a „lefedés” szót (ami itt sz
A lefedési probléma

A lefedési probléma a következ képp definiálható: Adott egy n elem sorvektor (amit szám n-esnek is neveznek) és adott egy k pozitív 18 szám. A sorvektor

A = (a1, a2,... ... an) Ahol valamennyi ai elem egy-egy egészszám. A probléma az, hogy találunk-e A elemei között egy olyan szám-sorozatot, amely számok összege éppen k. Szemléletes, ha mind a k számot, mind az A sorvektor ai elemeit távolságoknak tekintjük. Ekkor a probléma úgy fogalmazható, hogy található-e az ai távolságoknak

egy olyan (rész)sorozata, amellyel a k távolság pontosan lefedhet . Ebben az értelemben neveztük ezt a problémát lefedési problémának.

Az angol terminológia szerinti „hátizsák” (knapsack) elnevezés alapja ugyancsak egy szemléletes megközelítés, amelynél mind a k számot, mind az A sorvektor ai elemeit térfogatoknak tekintik s az a kérdés, hogy a k térfogatú hátizsák mely ai térfo19 gatelemekkel tölthet ki tökéletesen. A probléma szemléltetésére tekintsük az alábbi 10 elem sorvektort:

A = (43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523,) Legyen adott továbbá

k = 3231 Ellen rízhetjük, hogy ebben az esetben megoldás a következ :

3231 = 129 + 473 + 903 + 561 + 1165 Kérdés persze, hogy hogyan bukkantunk rá erre a lefedésre és az adott elemkészletet használva csak ez az egyetlen megoldás létezik-e. Ami a kérdés els részét illeti ha egyáltalán létezik megoldás azt elvileg mindíg megtalálhatjuk úgy, hogy az adott elemkészlet valamennyi részhalmazával végigpróbálgatjuk a lefedést, azaz valamennyi részhalmaz elemeit összeadogatva minden ilyen

18

Kés bb ezt a vektort (amit itt látszólag találomra felveszünk) „a lefedési vektornak” (az angol eredetiben knapsack vector) nevezzük, jóllehet nem magát a teljes A vektort használjuk a lefedéshez, hanem annak minden esetben más-más komponenseit, méghozzá esetenként általában egynél több komponensét.

19

Aki már a valóságban próbált hátizsákba pakolni az tudja, hogy nincs olyan tele hátizsák, amibe ne lehetne még valamit belegyömöszölni. Lényegében ezért választottuk inkább a „lefedési probléma” megnevezést. Van olyan interpretáció is, amely a kitölt elemek súlyával számol. 12

összeadásnál megnézzük, hogy az egyezik-e k –val. Az adott tízelem 10 esetében 2 = 1024 ilyen részhalmaz van.

sorvektor

Ha a triviális eseteket (azaz az üres és az 1 elem részhalmazokat, valamint az összes elemet tartalmazó nem valódi részhalmazt is) beszámítjuk, akkor legfeljebb 1024 próbálkozással megtalálható a lefedés, ha az egyáltalán létezik. Sokkal nehezebb lenne megoldást találni pl. egy 300 elem szám n-es esetében. 300 Nyilvánvaló, hogy 2 részhalmazzal gyakorlatilag hiábavaló lenne próbálkozni. A bemutatott lefedési probléma eleget tesz az egyirányú függvényekkel szemben támasztható követelményeknek. Persze egyel re nyitott kérdés a megoldás kulcsa, annak unicitása (=csak egyetlen megoldás létezik-e) és az, hogy hogyan alkalmazzuk ezt információ titkosításra. A következ kben ezeket igyekszünk bemutatni. Az n elem képpen:

A vektor segítségével egy f(x) függvényt definiálhatunk a következ n

Az 1 és a 2 -1 (zárt) intervallumon belüli valamennyi x egészszám egy-egy n-jegy bináris számmal is megadható. (A kis számok 0-ás jegyekkel kezd dnek, de azokat is n-jegy bináris számok ábrázolják.)

1 ? x ? 2n - 1 Tekintsük most valamely x szám bináris alakját (amit Bx-szel jelölünk) egy maszknak, amelynek 1-es számjegyei kijelölik az A sorvektornak azokat az ai elemeit, 20 amelyeket összeadva x –hez hozzárendeljük az f(x) függvényértéket. Ha biztosítható, hogy A -nak ne legyen két olyan különböz részhalmaza, amelynek elemei ugyanazt az összeget adják (azaz biztosított f(x) unicitása), akkor ezzel az eljárással n titkosíthatjuk az 1 ? x ? 2 -1 intervallumba es valamennyi x számot . Az el bbi példában, amelyben A egy tízelem vektor volt az adott k számot kijelöl maszk a következ képp m ködik: A = (43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523,) x= 0

1

0

1

1

0

1

1

0

0

k = 0+ 129 + 0 + 473+903+ 0 +561+1165 + 0 + 0 =3231 tehát az „eredeti” x2 = 0101101100 = 36410 számhoz a k = 3231 számot rendeli hozzá az f(x) transzformáció. n

Ez a maszkolási technika egy n komponens vektorral összesen 2 bináris szám maszkolását teszi lehet vé. Ez fontos. Itt nyilvánvaló, és kés bb hivatkozunk is erre a megállapításra.

20

Tulajdonképpen itt és most kapott értelmet az, hogy miért is tekintjük A-t vektornak ahelyett, hogy egyszer<en egy n elem< halmaznak tekintenénk. Nyilvánvaló ugyanis, hogy a maszkolásnak csak akkor van értelme, ha az elemek sorrendje szigorúan kötött, ami akkor teljesül, ha azok egy vektor komponensei. 13

A leírt maszkolás matematikailag (is) megfogalmazható: Az adott esetben a 10 komponens A sorvektor és az ugyancsak 10 komponens Bx bináris szám, mint oszlopvektor skalárszorzatát kellett kiszámolni ahhoz, hogy az x argumentumhoz megkapjuk a k = f(x) függvényértéket, azaz

f(x) = A Bx ahol Bx —mint említettük— az x szám bináris oszlopvektora. Írjuk le most az 26 bet s (+ szóköz) angol ábécé un. természetes bináris kódjait: Betü

Dec.Sorsz .

Bináris kód

Betü

Dec.Sorsz .

Bináris kód

Sp

0

00000

N

14

01110

A

1

00001

O

15

01111

B

2

00010

P

16

10000

C

3

00011

Q

17

10001

D

4

00100

R

18

10010

E

5

00101

S

19

10011

F

6

00110

T

20

10100

G

7

00111

U

21

10101

H

8

01000

V

22

10110

I

9

01001

W

23

10111

J

10

01010

X

24

11000

K

11

01011

Y

25

11001

L

12

01100

Z

26

11010

M

13

01101

Titkosítsuk most a bemutatott eszközökkel (és a két oldallal korábban megadott 10 komponens A sorvektorral) a következ angol szöveget: SAUNAspANDspHEALTH

14

Tegyük ezt úgy, hogy 10 jegy bináris számokat kapjunk mert a sorvektorunk is 10 komponens . Mivel az ábécé betüihez ötbites bináris kódokat rendeltünk hozzá, nyilván a betüpárok adnak egy-egy 10 jegy bináris kódot a következ képp: Betü pár

Bináris kód

x decimális értéke

f(x) érték e

SA

100110000 1

609

2942

UN

101010111 0

686

3584

Asp

000010000 0

32

903

AN

000010111 0

46

3326

Dsp

001000000 0

128

215

HE

010000010 1

261

2817

AL

000010110 0

44

2629

TH

101000100 0

648

819

A táblázat második oszlopában a tízjegy bináris számok az f(x) függvény argumentumai. A táblázat harmadik oszlopában megadtuk a 10 jegy bináris számok decimális megfelel it is (nem mintha erre a ciphertext el állításához szükség lenne). A fenti nyolc betüpárhoz az utolsó oszlopban feltüntetett nyolc számérték tartozik, (amelyeket a maszkolási technikával kaptunk,) azaz a ciphertext vektor a következ : (2942, 3584, 903, 3326, 215, 2817, 2629, 819) Látható tehát, hogy hogyan titkosítjuk a szöveget, de (egyel re) nem esett szó arról, hogy hogyan fogja a legális címzett megfejteni a ciphertextet. Itt lehet megemlíteni, hogy az A vektorhoz hasonló lefedési (=knapsack) vektorok jól alkalmazhatók mind a klasszikus, mind a nyilvános kulcsú kriptográfiában. A kriptanalítikusnak az a feladata, hogy megkeresse a titkosítás alapját képez A’’ vektort azaz, hogy megoldja a lefedési problémát. A titkosítási rendszer tervez jének viszont az a célja, hogy minél nehezebbé tegye az illegális megfejt számára a megoldást. Mindemellett a ciphertextnek csak egyetlen megfejtése lehet. Ez a bemutatott példánk esetében azt jelenti, hogy A elemei közül nem választható ki két különböz részhalmaz úgy, hogy azok elemeinek összege mindkét részhalmaz esetében ugyanaz legyen. Ezt a tulajdonságot nevezzük f(x) unicitásának.

15

A fenti táblázatban egyel re még mindíg hallgatólagosan feltételezzük azt is, hogy az f(x) függvény unicitása valamilyen módon biztosított. Foglalkozzunk el ször ezzel a problémával! Ellenpéldaként titkosítsuk most az ábécé betüihez tartozó ötbites kódokat a következ A’ lefedési vektor segítségével: A’ = (17, 103, 50, 81, 33) Az F betühöz tartozó ciphertext: (00110) › 50 + 81 = 131. Az S betühöz tartozó ciphertext pedig (10011) › 17 + 81 +33 = 131, azaz a megfejtéskor mind az F betü, mind az S betü matematikailag jó megoldást ad. Ebben az esetben tehát a transzformáció alapjául szolgáló A’ vektor nem biztosítja az f’(x) függvény unicitását. Más szóval ez az A’ vektor nem megfelel a titkosításhoz. Kérdés, hogy hogyan kell az A vektort megszerkeszteni (azaz a komponenseit felvenni) ahhoz, hogy a segítségével alkalmazott f(x) transzformáció unicitása biztosított legyen. Másképpen fogalmazva ez azt jelenti, hogy akárhány komponense is van A-nak, ne legyen a komponensekb l alkotható két, különböz részhalmaza, amelyek 21 komponenseinek összege ugyanaz lenne. A-nak e tulajdonsága úgy biztosítható, hogy a komponensek un. szupernövekv" sorozatát választjuk. Az ai egészszám’ok sorozatát szupernövekv"nek nevezzük akkor, ha bármelyik tagja nagyobb, mint az összes el z tag összege, azaz

i

ai +1

> aj j =1

A komponensek így választott sorozata persze monoton növekv lesz, nem úgy, mint a példaként választott A vektor esetén, de erre a kérdésre azonnal kitérünk. A lefedés vektorának bonyolultsági szintjét növelhetjük ha a komponenseken egy 22 modulo m-szorzást hajtunk végre.

21

Figyeljünk fel arra, hogy, hogy az ellenpéldánál az okozott gondot, hogy az A’ vektornak volt olyan komponense (nevezetesen az 50) amely két másik komponens (nevezetesen 17 + 33) összege volt. Eléggé kézenfekv , hogy ez a gond kiküszöbölhet , ha úgy választjuk meg az A vektor komponenseit, hogy egyik se’ legyen el állítható másik két —vagy több— komponens öszszegeként.

22

A mod m szorzás –mint a neve is mutatja- a mod m maradékos osztás inverz m
nehezen megoldhatóvá transzformálja. (Ld. még az összefoglalást is a 5oldalon.) A mod m osztás (ill. inverze) alkalmazásának azonban a számítási munka szempontjából jelent s el nyei is vannak. Ezért gyakorlatilag valamennyi, az itt példaként bemutatottól kölönböz kriptográfiai egyirányú függvény esetében is el fordul, amint kés bb látni fogjuk majd. 17

Válasszunk ehhez egy olyan m számot, amely nagyobb, mint a szupernövekv sorozatunk összes tagjának összege. Gyakorlati okokból azonban nincs szükség arra, hogy akármennyivel nagyobb legyen. A 13. oldalon megállapítottuk, hogy egy n komn ponens vektor összesen 2 bináris szám maszkolását teszi lehet vé. Ezért a modun lusnak sem kell feltétlenül nagyobbnak lennie 2 –nél. Ez gyakorlatilag azt jelenti, hogy a modulust az n-elem szupernövekv sorozat „folytatásával” meghatározható két további tag között kell felvenni, azaz an+1 < m < an+2 Legyen pl. egy tízelem szupernövekv szám-sorozatból alkotott lefedési vektor a 23 következ : A’’ = (1, 3, 5, 11, 21, 44, 87, 175, 349, 701) Ennek a sorozatnak az összege 1397. Mint kijelentettük, az m modulust úgy kell megválasztanai, hogy a sorozat összegénél nagyobb legyen. Tehát az adott esetben 1398 már megfelel szám lenne. Mégis ebben a titkosítási rendszerben (mint más, hasonló rendszerekben is) a kulcs megválasztásának sok szabadságfoka van és nem célszer a triviális választásokra építeni a rendszert. Ezért itt sem az „éppen, 24 hogy megfelel ” 1398-as modulust választjuk. Legyen a modulus: m = 1590 amire teljesül a fent megfogalmazott intervallumfeltétel: 1397 < 1590 < 2794 Alább hasznos lesz, ha ismerjük m valódi osztóit is. Törzstényez inek szorzatával el állítva: 1590 = 2×3×5×53

23

„Miért éppen ezt” —kérdezhetné valaki— „amikor az (1, 2, 4, 8, 16, 32, 64, 128, 256, 512) vektor is szupernövekv ?” Nos, tényleg az, de úri kedvünknek úgy tetszett, hogy az eljárás demonstrálásához ne a legegyszer
24

A következ kben látni fogjuk, hogy szükség lesz erre a modulusra vonatkoztatott un. multiplikatív inverzek kiszámítására is és ahhoz, hogy ezek eléggé „kényelmesen” kezelhet számok legyenek nem mindegy, hogy mekkora modulust választunk. Ezért —gyakorlati okokból— mégsem annyira szabad a modulus megválasztása, mint amennyire szabadnak az elvileg látszik. 18

Álljunk meg egy szóra a kongruenciák kedvéért! Két egészszámot, amelyeket jelöljön itt a és b, egymással kongruensnek mondunk egy m modulusra nézve, ha mindegyiket külön-külön elosztva m-mel, ugyanazt a maradékot adják. Ezt így jelöljük: a ? b (mod m) Ezt a következ képp olvassuk: „a kongruens b-vel az m modulusra nézve.” Nyilvánvaló, hogy itt maradékos osztásról van szó. Az m-mel való maradékos osztáskor azonos maradékot adó valamennyi szám egyetlen maradékosztályba tartozik. Így a mod m kongruenciák összesen m maradékosztályba képezik le valamennyi természetes számot. Ugyanakkor a maradékosztályok meg rzik az eredeti szám egynéhány tulajdonságát, s így a természetes számok megszámlálhatóan végtelen halmazát egy m elem véges halmazra képezik le. Az m=2-es modulus például a páros (azaz 0 maradékot adó) és a páratlan (azaz 1 maradékot adó) számok halmazára képezi le a természetes számokat. A modulo m összeadással a kriptográfiai tanulmányok során már de Vigenere titkosítási módszerének ismertetésekor találkoztunk. De Vigenere módszere a legegyszerübb (pl. a Caesar-féle) helyettesítéses titkosítás egy bonyolultabb változata. Láttuk azt is, hogy ha csupa azonos betüb l álló kulcsszót választunk de Vigenere módszerénél, akkor az éppen a Caesar-féle helyettesítésbe megy át. Nem véletlen tehát, hogy ha a modulo m összeadásról, szorzásról és hatványozásról b vebb ismereteket kívánunk szerezni, akkor ezt a helyettesítéses titkosítás kissé mélyebb matematikai tárgyalásával kapcsolatban tehetjük meg. Itt ez megzavarná a tárgyalás gondolatmenetét, ezért a legfontosabbakat az II. Függelékben foglaltuk össze. Két szám (a és b ) kongruenciája nem m velet, hanem a két szám (ti a és b ) egymáshoz való viszonyát, relációját fejezi ki. Ezért a kongruencia nem m velet hanem reláció. Azt is itt kell megjegyezni, hogy a kongruencia un. ekvivalencia (tipusú) reláció és mint ilyen a következ három kritériumot kell kielégítenie: •

1.

Reflexív, azaz a = a, vagyis bármi ekvivalens önmagával

•

2.

Szimmetrikus, azaz ha a =b akkor b = a

•

3.

Tranzitív, azaz ha a =b és b = c akkor a = c

Bármilyen reláció, amely kielégíti mindhárom fenti feltételt ekvivalencia (tipusú) reláció, mint pl. a háromszögek hasonlósága. Ha egy G halmaz egymással ekvivalens elemeit egy-egy S részhalmazba soroljuk, akkor a G halmazon értelmezett ekvivalencia reláció diszjunkt részhalmazokra particionálja a G halmazt.

2

Keressünk szorzót a választott m = 1590-es modulushoz. Ehhez m+1 = 1591-et kell 25 törzstényez ire bontani : 1591 = 43×37

Álljunk meg egy szóra a multiplikatív inverz kedvéért! Válasszunk egy t egészszámot m-hez úgy, hogy relatív prímek legyenek. t és m -1 ismeretében határozzunk meg egy t egészszámot úgy, hogy -1

t t = 1 (mod m) -1

legyen. Ebben az egyenletben a t egészszám’ t –nek az m modulusra vonatkozta-1 tott multiplikatív inverze., vagyis t –t t –gyel szorozva olyan számot kell, hogy kapjunk, amely az m modulussal osztva éppen 1-et ad maradékul. Itt mindjárt meg kell jegyezni, hogy a multiplikatív inverz –tetsz leges m modulus és tetsz legesen választott t egészszám esetén– nem mindíg létezik. A knapsack titkosításnál a t egészszámot úgy szokás megválasztani, hogy a szupernövekv sorozatunkon belül legyen (de nem kell, hogy megegyezzen a sorozat egyetlen tagjával sem). A multiplikatív inverz t és m ismeretében könnyen kiszámítható. (Ha egyáltalán létezik.) Hogy hogyan? Nos, adjunk hozzá 1-et a választott m modulushoz és határozzuk meg az így kapott egészszám törzstényez it, majd válasszuk ezek közül azt vagy azokat, amelyek nem törzstényez i m-nek. Ezek szorzata (vagy közülük akár egyetlen egy is) m-hez képest relatív prím lesz, tehát megfelel arra, hogy t-nek válasszuk. m neve –mint láttuk– modulus t neve: szorzó. -1

t neve: (m-re vonatkoztatott) multiplikatív inverz A modulus és a multiplikatív inverz mélyebb kapcsolatára az I. Függelék, gyakorlati megválasztásukra vonatkozó néhány hasznos tételre pedig a II. Függelék ad némi útmutatást, a tényleges kiszámítási algoritmust pedig a III. Függelék írja le.

Mivel m = 1590 = 2×3×5×53 törzstényez i között sem 37 sem 43 nem fordul el , ezért bármelyiket választhatjuk szorzónak. Legyen most a szorzó t = 43

25

Itt láthatjuk, hogy miért nem biztos, hogy akármilyen m-hez (és t-hez) létezik multiplikatív inverz. m+1 –nek ugyanis összetett számnak kell lennie, azaz kell, hogy legyenek törzstényez i. Ugyanakkor m-nek egyetlen egy törzstényez je sem lehet közös t törzstényez ivel, mert csak ekkor lehetnek relatív prímek. Persze, ha m történetesen prímszám, akkor ez eleve biztosított 3

Könny belátni a fentiek alapján, hogy ennek az m = 1590-es modulusra vonatkoztatott inverze: -1

t = 37 -1

Mert t.t =43×37 = 1591, amit 1590-nel osztva éppen 1 a maradék.

26

Térjünk vissza most a példában felvett A’’ = (1, 3, 5, 11, 21, 44, 87, 175, 349, 701) szupernövekv sorozat transzformációjára. Ehhez szorozzuk meg minden egyes 27 tagját t-vel és képezzük az m = 1590-es modulusra vonatkoztatott maradékot: A transzformált sorozat egyes tagjai rendre a következ k: 43× 1 =

43

43× 3 = 129 43× 5 = 215 43× 11 = 473 43× 21 = 903 43× 44 = 1892 mivel ez már nagyobb mint a modulus, azzal elosztva a maradékát kell szerepeltetni, azaz 43× 44 =1892 = 1×1590 + 302 43× 87 =3741 = 2×1590 + 561 43×175 = 7525 = 4×1591 + 1165 43×349 =15007= 9×1590+

697

43×701 =30143=18×1590+ 1523

26

Csak az érdekesség kedvéért érdemes utánaszámolni, hogy mi lehetne a szorzó és mi a multiplikatív inverze, ha az „éppen, hogy csak megfelel ” minimális m’ = 1398-at választjuk modulusnak. Nos 1398+1=1399 maga is prímszám, tehát nincs valódi osztója, azaz nem választhatunk hozzá szorzót s inverzet sem. Az eggyel nagyobb 1400 azonban nem törzsszám (1400 = 23×52×7). Mivel ekkor a modulus m’ = 1399 lenne –ami maga törzsszám– bármilyen szám a szupernövekv sorozatunk nagyságrendjében megfelelne szorzónak. Így az adott példához gyakorlatilag választható legkisebb modulus 1399 lenne. Ehhez nyugodtan választhatnánk pl. t’ = 35 =5×7 –et szorzónak és ekkor az m’ = 1399-es modulusra vonatkoztatott inverze t’ -1 = 40 lenne.

27

Úgy is fogalmazhatunk, hogy a szupernövekv sorozat minden egyes tagja helyett azt az m modulusra vonatkoztatott maradékosztályt szerepeltetjük, amelybe az éppen aktuális tag tartozik. Itt ugyan nem bizonyítjuk, de higyje el az Olvasó, hogy ett l még megmarad az f(x) függvény unicitása. Amíg 43×ai nem nagyobb a modulusnál (itt és most 1590-nél) az eredeti szupernövekv sorozat megfelel tagjának 43-szorosa szerepel a transzformált sorozatban. 4

Tehát a transzformált (knapsack) vektor: A = (43, 129, 215, 473, 903, 302, 561, 1165, 697, 1523) Figyeljünk fel arra, hogy ez éppen az az A vektor, amelyet a 12. oldalon (ott látszólag találomra) felvettünk. Nem más tehát, mint az A’’ szupernövekv , tízkomponens vektornak a t = 43-as szorzóval és az 1590 modulussal létrehozott transzformáltja.

Állítjuk (de itt nem bizonyítjuk), hogy ha az eredeti –szupernövekv komponensekb l 28 álló- vektor biztosította f(x) unicitását , akkor a bemutatott transzformáltja is biztosítja ezt az unicitást. Ezzel f(x) unicitásának kérdését elintézettnek tekintjük. Marad még az a kérdés, hogy hogyan tudja a legális címzett sokkal könnyebben megfejteni a titkosított szöveget, mint az illetéktelen kíváncsiskodó. A titkosított szöveg megfejtése. Az adott példában az A vektor a publikus kulcs (azaz A’’ transzformáltja). A megfejtéshez A-ból el kell állítani az A’’ vektort. Emlékezzünk rá, hogy a szupernövekv komponensekb l álló A’’-b l a t=43 szorzó és az m=1590 modulus segítségével állítottuk el az A vektort. A visszaállításhoz -az A a publikus kulcs mellett- szükséges és elegend az m modulus és a t-1 inverz ismerete. Az utóbbi két adatot csak a legális címzett ismeri, de ha a címzett történetesen az „eredeti” A’’ szupernövekv , tízkomponens vektor bírtokában van, akkor A és A’’ ismeretében már visszaszámolhatja mind a modulust, mind a szorzót és, persze, annak inverzét is. Mondhatjuk tehát, hogy A a publikus kulcs , A’’ pedig a titkos (=privát) kulcs.

29

Összefoglalva tehát •

A lefedési problémát alkalmazó titkosítás alapja egy olyan A’’ sorvektor, amelynek a komponensei szupernövekv egészszám-sorozatot alkotnak. A szupernövekv komponensek biztosítják az f(x) titkosítási transzformáció unicitását.

•

Az A’’ sorvektor n komponens . A komponensek száma egyúttal meghatározza a titkosítás blokkhosszúságát. (A példán láthattuk, hogy 10 bites nyíltszöveg-blokkokat titkosítottunk.) Tehát blokk-titkosító módszerr"l van szó. Következésképp ugyanúgy léteznek különböz –esetleg láncolt– üzemmódjai, 30 ahogyan a DES-nél bemutattuk annak az üzemmódjait.

28

Márpedig minden olyan vektor biztosítja ezt az unicitást, amelynek a komponensei egy szupernövekv egészszám-sorozat elemei.

29

Az így megválasztott titkosítási algoritmusnál történetesen nem mindegy, hogy a két kulcs közül melyiket tesszük nyilvánossá és melyiket tartjuk titokban.

30

Ez a titkosítási módszer ezen a ponton kettéágazik, mert mind szimmetrikus (= egykulcsos), mind pedig aszimmetrikus (=kétkulcsos vagy nyilvános kulcsos) módszerként alkalmazható. 5

•

Az n komponens A’’ sorvektorból egy t szorzó és egy m modulus segítségével el állítunk egy A vektort, amely egyáltalán nem hasonlít az „eredeti” A’’ vektorra mert nemhogy nem szupernövekv , hanem még csak nem is monoton növekv komponensekb l áll, jóllehet ugyanannyi komponense van, mint az „eredeti” A’’ vektornak.

•

A t szorzó és az m modulus ismeretében könnyen kiszámíthatjuk a t-1 inverzet is. Ezek összefüggése egymással a következ : -1

t t ? 1 (mod m) ezek a számok nem publikus, vagyis titkos adatok. •

Az „eredeti” A’’ vektor transzformáltját, vagyis az A vektort nyugodtan publikussá tehetjük. A modulus és a szorzó (vagy annak inverze), vagy az „eredeti” A’’ vektor ismerete nélkül az illetéktelen megfejt nem sokra megy magával 31 az A vektorral.

Térjünk vissza azonban a numerikus példánkhoz! Példánkban az els betüpár „SA” volt, a hozzátartozó 10 bites bináris blokk pedig 10011000001 (=60910). Ez az A vektor komponensei közül kiválasztotta balról az els t, a negyediket és az ötödiket, valamint az utolsót. (Lásd a táblázatot a 15. oldalon.) Ezek összege 43+473+903+1523=2942 volt. Az „SA” nyíltszöveg ugyancsak nyílt kódja tehát a decimális 609. Ennek pedig a titkosított kódja 2942. Az illetéktelen megfejt nek rá kellene jönnie, hogy az egyébként nyilvános A vektor tíz komponense közül melyek összegéb l kaphatja meg ezt a számot. Erre nincs más módja, mint a próbálgatás, amir l már szóltunk.

Ha szimmetrikus módszerként alkalmazzuk, akkor a szupernövekv komponensekb l álló A’’ vektor a (tikos) kulcs, mert ez biztosítja a titkosító transzformáció unicitását és ezáltal az invertálhatóságát is. 31

Ehelyt nem tudjuk még, hogy a legális címzett majd milyen módszerrel találja meg, hogy a titkosított blokk A-nak mely komponensei összeadásából áll el , de azt tudjuk, hogy az illegális megfejt ismeri ugyan A-t (mert azt publikussá tettük), de nincs más lehet sége, mint kipróbálni, hogy a komponensekb l alkotott valamennyi részhalmazra jellemz összeg nem egyezik-e az adott blokk kódjával. 10 komponens esetén ez aránylag gyorsan megy, de pl. 300 komponens esetén már 2300 próbálkozásra is szükség lehet s az már tényleg reménytelen. 6

Egyébként magából a titkosított szövegb l (=ciphertextb l) még azt sem látná, hogy blokk titkosításról van szó és, hogy mekkora a blokkhosszúság. A publikus A vektorból azonban kitalálhatja, hogy blokk-titkosítást alkalmazunk és azt is, hogy mekkora a blokkhosszúság. (Legalább is jó hipotézist alkothat a megfejtéshez.) Nyilvánvaló, hogy a legális címzettnek valamilyen más, ennél sokkal egyszer bb megfejtési módszert kell alkalmaznia. Tegyük fel, hogy a legális címzett ismeri az eredeti A’’ szupernövekv komponensekb l álló vektort és egy ciphertext blokkot megkapva meg szeretné találni a hozzátartozó nyílt szöveget, azaz példánkban egy 10 bites bináris számot, ami „maszkolja” a szupernövekv sorozatot. Emlékezzünk arra, hogy a nyíltszöveg titkosításakor a 10 bites bináris számokkal nem ezt a vektort maszkoltuk, hanem az A vektort, amit úgy kaptunk A’’-b l, hogy a t szorzóval megszoroztuk és képeztük a szorzatok mod m kongruenciáit. Ezért most -1 szorozzuk a titkosított szöveg minden egyes blokkjának a kódját a t inverzzel és képezzük a mod m maradékosztályokat. Legyen pl. a kapott titkosított szöveg a következ szám-sorozat: C = (2942, 3584, 903, 3326, 215, 2817, 2629, 819) Általános jelöléssel: C = (c1, c2, ... ... cj) -1

Számítsuk ki mind a nyolc tagnak a t =37 inverzzel való mod m = 1590 szorzatát. Ezek a szorzatok és a maradékosztályok a következ k: 37×2942 = 108854 =68 × 1590 + 734; tehát a maradékosztály 734; 37×3584 = 132608 =83 × 1590 + 638; tehát a maradékosztály 638; 37× 903 =

33411 = 21× 1590 + 21; tehát a maradékosztály 21;

37×3326 = 123062 = 77× 1590 + 632; tehát a maradékosztály 632; 37× 215 =

7955 =

5×1590 +

5; tehát a maradékosztály

5;

37×2817 =104229 = 65×1590 + 879; tehát a maradékosztály 879; 37×2629 = 97273 = 61×1590 + 283; tehát a maradékosztály 283; 37× 819 = 30303 = 19×1590 + 93; tehát a maradékosztály

93;

A visszatranszformált ciphertext vektor tehát a következ : T

C = (734; 638; 21; 632; 5; 879; 283; 93) 32

Általános jelöléssel :

CT = (c1T; c2T; ...

32

... cjT)

Az általános jelölésekre alább, az általános algoritmus leírásakor lesz szükségünk. Az általános algoritmust egyébként a III. Függelékben írtuk le. 7

Most már „csak” azt kell megkeresnünk e sorozat minden egyes tagjához, hogy az az eredeti, szupernövekv komponensekb l álló sorvektor mely komponenseinek öszszegével fedhet le. Egy-egy ilyen lefedés meghatároz egy-egy tízbites bináris számot (mint maszkot) és ezzel tulajdonképpen meg is fejtettük az üzenetet. Hogyan lehet azonban a fedéshez használandó komponenseket megkeresni? Ezt csakis akkor hajthatjuk végre egyértelm en, ha a lefedéshez használt vektor szupernövekv komponensekb l áll. (Ezért van szükség a megfejtéshez az eredeti szupernövekv komponens vektorra és ezért nem alkalmas a megfejtéshez annak a transzformációjával kapott A vektor.) Az eljárást az adott példán mutatjuk be. Emlékeztet ül: példánkban a szupernövekv komponensekb l álló sorvektor a következ volt: A’’ = (1, 3, 5, 11, 21, 44, 87, 175, 349, 701) Általános jelöléssel: A’’ = (a1, a2, ...

... an)

Tekintsük az inverzzel szorzott üzenetvektor els komponensét (azaz 734-et). Nyilvánvaló, hogy ennek a számnak a lefedésében az A’’ vektor legnagyobb komponense (azaz 701) részt vesz:. Osztva ezzel 734-et és képezve a maradékot: 734 = 1× 701 + 33 (Ehhez jobbról az els komponenset használtuk fel.) Mi a helyzet a maradék lefedésével? Jobbról a második, a harmadik, a negyedik, és az ötödik komponens mindegyike nagyobb a fenti maradéknál tehát egyik sem használható a 33 lefedéáséhez. Jobbról a hatodik komponens (=21) azonban igen: 33 = 1 ×21 + 12 (Ehhez jobbról a hatodik komponenset használtuk fel.) A maradék (12) fedéséhez használnunk kell jobbról a hetedik komponenset: 12 = 1× 11 + 1 (Ehhez jobbról a hetedik komponenset használtuk fel.) A maradék (1) fedéséhez nem használható sem 5, sem 3 (mert mindkett nagyobb a legutolsó maradéknál, de 0 maradékkal lefedhet jobbról a tizedik komponenssel: 1 = 1×1 + 0 (Ehhez jobbról a tizedik komponenset használtuk fel.) A korábban bemutatott „maszk” tehát 1-es azokon a helyeken, ahol egy-egy komponenset felhasználtunk a lefedéshez és 0 mindazon komponenseknél, amelyeket nem használtunk a lefedéshez. Az A’’ vektornak tehát a következ komponensei szerepeltek a bemutatott eljárásban (Figyeljünk fel arra, hogy mindegyik komponens csakis egyszer használható!): 701, 21, 11, és 1 Növekv sorrendben: 1, 11, 21, 701 Az a maszk, amelyik ezeket a komponenseket kijelöli az A’’ sorvektorban a következ bináris szám: 1001100001 Ehhez pedig a 14. oldalon felírt kódtábla szerint az „SA” betüpáros tartozik, ami éppen a keresett nyílt szöveg els betüpárosa. 8

Nyilván nincs szükség arra, hogy ugyanilyen részletesen kiszámoljuk a megfejtés további betüpárjait is a (734; 638; 21; 632; 5; 879; 283; 93) vektor második és további komponenseib l. Ehelyett összefoglalásul fogalmazzuk meg a megfejtési eljárás algoritmusát! A titkosított szöveg (ciphertext) megfejtési algoritmusa tehát a következ : -1

•

A t inverz és az m modulus ismeretében számítsuk ki a ciphertext-vektor vala-1 mennyi elemének t inverzzel való mod m szorzatát.

•

A kapott eredmény-vektor legels eleméhez ( c1 –hez )határozzuk meg, hogy az eredeti, szupernövekv komponensekb l álló, n elem A’’ vektor mely elemeivel fedhet le ez a komponens. A lefedést meghatározó algoritmus a következ : A szupernövekv komponensekb l álló, n elem A’’ vektor jobboldali (azaz a legnagyobb) an komponensét l kiindulva és balra sorravéve a komponenseket

T

T

o

Vizsgáljuk meg, hogy a lefedni kívánt szám (= c1 ) nem kisebb-e az éppen aktuális an A’’ komponensnél. Ha kisebb, akkor írjunk 0-át, ha nem, akkor írjunk 1-et és képezzük a lefedni kívánt szám, valamint az éppen aktuális an komponens különbségét. Jelöljük ezt a különbséget d-vel. A leírt 0-ás vagy 1-es a meghatározni kívánt n-legy bináris szám legkisebb helyiérték számjegye lesz. Ennek az n jegy bináris számnak a további számjegyeit az itt meghatározott LSB-t l rendre balra írjuk, de ezt a tényt továbbiakban nem említjük.

o

Vizsgáljuk meg, hogy d = 0 -e. Ha igen, akkor fejezzük be a lefedés komponenseinek keresését és egészítsük ki balra a bináris számunkat csupa 0-ás jeggyel úgy, hogy összesen n jegy bináris számot kapjunk.

o

Ha d > 0, akkor vegyük az A’’ vektor következ ( an-1 ) komponensét és ismételjük az eljárást a 2.1 pont elejét l mindaddig, amíg d = 0 –át kapunk 2.2 –ben. T

T

•

Végezzük el a 2. pontban leírt eljárást C további ci elemeire is ( 2 ? i ? j )

•

Az eredményül kapott n bites blokkokat a kódtáblázat segítségével konvertáljuk vissza olvasható (nyílt) szöveggé.

Figyeljünk fel arra, hogy a megfejtéshez szükség volt •

Az m modulusra

•

A t inverzre és

•

A szupernövekv elemekb l álló „eredeti” A’’ vektorra

-1

Végül is nincs szükség ennyiféle adat tárolására, mert az „eredeti” szupernövekv komponens A’’ vektor (= a titkos kulcs) és a transzformáltja, vagyis az A vektor (= publikus kulcs) ismeretében a modulus, a szorzó és az utóbbi inverze már egyértelm en kiszámítható. A kulcsszámítás, a titkosítás és a megfejtés teljes algoritmusát a III. Függelékben részletesen leírtuk. Az ott leírt algoritmushoz Tóth Zsolt (Ictus Bt.) programot is írt, amely az SzGTI hálózatán hozzáférhet . 9

A.1 Gyakorló feladat •

Írjunk fel a 32 betüs magyar ábécéhez ötbites „természetes” kódtáblázatot. (a csupa 0-ás kód itt is feleljen meg a szóköznek!)

•

Legyen a titkosítandó szöveg a feladat megoldójának a teljes neve egy szóköz után kiegészítve annak a csillagképnek a nevével, amelyben született. Határozzuk meg ennek a szövegnek a betüpárjaihoz tartozó 10 bites bináris számokat. (Ha az utolsó betü magában állna, f zzünk a nyílt szöveg végéhez is egy szóközt!)

•

Használjuk ehhez a feladathoz is ugyanazt az n = 10 elem szupernövekv sorvektort, amelyet a mintapéldához használtunk az el bb.

•

Válasszuk azonban most a gyakorlatilag választható legkisebb modulust, azaz m = 1399-et és legyen t = 35 (Ezek relatív prímek, mert 1399 maga is prímszám.)

•

Határozzuk meg a publikus kulcsot, azaz a tízelem , szupernövekv vektorunk transzformáltját!

•

Titkosítsuk a 2. pont alatti nyílt szöveget a nyilvános kulccsal!

•

Írjuk fel a titkosított szöveget!

•

Ellen rzésképp hajtsuk végre a dekódolást is a mintapéldában leírtak szerint lépésr l lépésre.

•

Még jobb, ha ketten, mondjuk András és Béla oldják meg a feladatot úgy, hogy mindketten más-más publikus kulcsot alkalmaznak. (mondjuk módosítják egy kissé a szupernövekv sorvektor elemeit úgy, hogy az elemek szupernövekv tulajdonsága azért megmaradjon és a tizedik elem is ugyanaz maradjon.)

•

Adja meg András ezek után az nyilvános kulcsát Bélának, Béla pedig András nyilvános kulcsával titkosítsa a saját nyílt szövegét. Ezek után ezt a titkosított szöveget fejtse meg András a saját titkos kulcsával ( ti. a saját szupernövekv sorozatával, modulusával és inverzével.)

•

Tegyék meg ugyanezt felcserélt szereposztásban is!

•

Hasonlítsák össze a megfejtéseket az eredeti nyílt szövegekkel. Ha hibás a megfejtés, akkor keressék meg, hogy hol számolták el a dolgot. (Könny számítási hibát véteni s rossz megfejtést kapni.)

A.2 Gyakorló feladat A 12. oldalon megadott A vektort és a 14. oldal kódtáblázatát használva állítottuk el a következ titkosított szöveget: C = (5322, 4202, 2039, 3248, 1867, 2342, 4143) Fejtse meg a fentiek alapján az ennek megfelel nyílt szöveget!

10

Összefoglalás a Knapsack titkosításhoz. Az üzenet k ld je a publikus A vektort használja a titkosításhoz úgy, ahogyan azt -1 bemutattuk. Nem ismeri sem az m modulust, sem a t szorzót, sem a t inverzet, de nincs is ezekre szüksége ahhoz, hogy el állítsa a titkosított szöveget. Igaz, hogy nem is tudja visszafejteni azt (pl. azért, hogy ellen rízze, hogy nem tévedett-e). Az üzenet legális címzettje persze ismeri mind az eredeti, szupernövekv komponen-1 sekb l álló A’’ vektort, mind az m modulust, mind a t inverzet és szüksége is van ezekre a megfejtéshez. Elegend azonban, ha csak az A nyilvános kulcsot és az A’’ titkos kulcsot tárolja, mert ezekb l a modulus, a szorzó és az utóbbi inverze egyértelm en kiszámítható. (Kevesebb módja is van a tévedésre.) A knapsack módszer érdekessége, hogy a titkosításhoz nem a szupernövekv komponensekb l álló A’’ vektort használjuk, hanem annak a transzformált változatát (ti. az A vektort), a megfejtést mégis csakis a szupernövekv komponens A’’ vektor segítségével kaphatjuk meg, a titkosításhoz használt A vektorral nem, legfeljebb 33 csak a nyers er próbálgatásos módszerével -1

A szupernövekv komponensekb l álló A’’ vektor persze az m modulus éa a t inverz ismeretében kiszámítható a transzformált A vektorból is. Mindenesetre a szupernövekv komponensekre azért van szükség a megfejtésnél, mert a lefedési probléma megoldásához szükséges komponenseket csakis ekkor találhatjuk meg az ismertetett módszerrel (és nem ismerünk más módszert). Tehát csakis ekkor alkalmazhatjuk a példában bemutatott és az algoritmusban leírt ismételt maradékos osztást és a különbségek további maradékos osztásait a komponensek csökken sorrendjében és csakis úgy. Ennek a feltételnek pedig csakis a szupernövekv komponensekb l álló (sor)vektor felel meg, a transzformáltja pedig nemcsak nem szupernövekv , hanem –ha megfelel szorzót választottunk– még csak nem is monoton növekv .

33

El Gamalnak sikerült a Knapsack titkosításhoz polinomiális id ben megoldható algoritmust találnia. Ez a feltörési módszer azon alapul, hogy az illetéktelen megfejt nek nincs is szüksége arra, hogy megtalálja ugyanazt az m modulust és t-1 inverzet, amelyekkel a legális címzett dolgozik. Elegend , ha talál egy olyan m’ modulust és egy hozzátartozó t-1’ inverzet, amellyel mod m’ szorozva a publikus A vektort, egy szupernövekv komponensekb l álló A’ vektort kap (amelynek nem kell azonosnak lennie az eredeti A’’-vel). Emiatt a feltörési algoritmus miatt aztán a gyakorlatban nem is vélik eléggé megbízhatónak a Knapsack titkosítást és nem is igen alkalmazzák. Fontos azonban, hogy ha az m modulust úgy választjuk meg, hogy m+1-nek csak 2 prímszám törzstényez je legyen, akkor az El Gamal-féle feltörési algoritmus nem találhat A-hoz másik modulust és inverzet, tehát a Knapsack titkosítás mégis megbízhatóan m
A mondottak lényege másképpen is megfogalmazható: Egy szupernövekv komponens vektort választva a lefedési probléma könnyen megfejthet , de a titkosítási alkalmazásnál csak a legális címzett számára lehet könny a megfejtés. Ezért az „eredeti” szupernövekv komponens A’’ vektort egy cseles transzformációval olyan A vektorrá alakítjuk, amellyel a lefedési probléma visszafelé már egyáltalán nem könnyen megoldható. Egy „könnyN” problémához (PkönnyK) keresünk tehát egy vele affin kapcsolatban lév „nehéz” problémát ( Ptitkos ) és ezt alkalmazzuk a titkosítási módszernél. Lényegében ennek az általános elvnek az alkalmazási lépéseit foglaltuk össze a 26. oldalon. A knapsack problémának ezt a megfogalmazását Merkle-Hellman sémának is nevezik, azokról az inventorokról, akik el ször alkalmazták nyiltkulcsú titkosításra.

Mi a mod m kongruenciák szerepe? A maradékosztályok véges halmazára képezi le a természetes számok végtelen halmazát. Gyakorlatilag korlátozza a számítások során kapott eredményeket is, s ezzel biztosítja, hogy ne forduljon el túlcsordulás. Ezért a (mod m) szorzás (vagy hatványozás) más nyiltkulcsú kriptorendszereknél is visszaköszön, amelyekben gyakorlatilag ugyanez az alapvet szerepe. A mondottak miatt fontos az I. Függelékben leírt fogalomkör és a mod m összeadás, szorzás és hatványozás tulajdonságaira vonatkozó tételek, amelyeket ugyancsak az I. Függelékben fejtettünk ki.

12

Néhány gondolat a nyiltkulcsú kriptorendszerekr l 34

A szimmetrikus (mono- vagy polyalfabetikus) kriptorendszerek valamilyen kulcsot alkalmaznak a nyíltszöveg titkosítására is és a megfejtésére is. Általában a következ két lehet ség áll fenn: •

Csak egyetlen kulcs van. Ezt az egyetlen kulcsot (persze) másként használják a nyíltszöveg titkosításakor és megint másként a titkosított szöveg megfejtésekor (azaz a nyíltszöveg visszaállításakor). Titkosító gépek alkalmazásakor tehát van valahol egy kapcsoló, amelynek az egyik állásában a gép titkosítja a betáplált nyílt szöveget, a másik állásában pedig a ciphertextb l visszaállítja az eredeti nyílt szöveget. A kapcsoló tehát vált a titkosítási (=encryption) és a megfejtési (=decryption) üzemmódok között.

•

Két kulcs van. Az egyiket a titkosításhoz, a másikat pedig a titkosított szöveg megfejtéséhez használjuk. A titkosító berendezésnek ekkor csak egyetlen üzemmódja van, mert a m ködtetésekor alkalmazott kulcs maga meghatározza, hogy titkosítania vagy megfejtenie kell-e a betáplált szöveget. A megfejtési kulcs el állítása a titkosítási kulcsból azonban külön er feszítést igényel, ha egyáltalán lehetséges. (Az egyirányú függvények alkalmazásával éppen az a célunk, hogy ez gyakorlatilag ne legyen lehetséges.)

Mindezt pl. a klasszikus de Vigenere titkosítási módszer is szemléltetheti. Az els esetben Titkosításkor (= Encryption) egy modulo N összeadást Megfejtéskor (=Decryption) egy modulo N kivonást alkalmazunk, tehát más-más módszert E-hez és D-hez. (Ez elvileg még akkor is igaz, ha bizonyos esetekben a mod N összeadás és a mod N kivonás gyakorlatilag ugyanazt jelenti.) A második esetben viszont a de Vigenere-féle titkosítás értelmezhet úgy is, hogy ugyanannak a kulcsnak, amit titkosításkor alkalmaztunk, megfejtéskor az inverzét

34

amelyeket „klasszikus” vagy „egykulcsos” rendszereknek is szokás nevezni. Ezek az elnevezések azonban megtéveszt ek. Egyrészt a szimmetrikus rendszerek többségére is igaz, hogy ugyanazt a kulcsot használják ugyan a megfejtéshez, mint amit a titkosításhoz használtak, de nem egészen ugyanúgy. Erre sok példa említhet . Pl. az igazán kifinomult DES rendszernél a szubkulcsok generálási sorrendje felcserél dik a megfejtésnél a titkosítási eljárás szubkulcsgenerálási sorrendjéhez képest. Másrészt a ma használatos szimmetrikus eljárásoknál is alkalmaznak pl. kulcs-megosztási módszereket, amelyek pontosan megfelelnek annak az igazán klasszikus biztonsági eljárásnak, hogy egy bank széfjét csak több kulcs egyidej< alkalmazásával lehet kinyitni, s az egyes kulcsokat más-más személyek birtokolják. Így az igazán modern szimmetrikus titkosítási módszerek egyáltalán nem nevezhet k egykulcsos rendszereknek. Ezért inkább a „szimmetrikus” és az „aszimmetrikus” megnevezéseket használjuk a kétféle kriptorendszer megkülönböztetésére, bár az el bbire egyértelm< a „titkos kulcsos” megnevezés is (akárhány kulcsot is alkalmaz) az utóbbira pedig a nyilt (nyilvános vagy publikus) kulcsos megnevezés, mert a több kulcs közül legalább egy nyílvános, bárki által hozzáférhet . 13

alkalmazzuk. Persze ebben az esetben az inverz kulcsot elég egyszer en el lehet állítani a titkosításkor alkalmazott kulcsból, ezért mindkett t titokban kell tartatani. Abban az esetben azonban, ha az inverz (ti. a megfejtéshez szükséges) kulcsot gyakorlatilag lehetetlen el állítani a titkosításkor alkalmazott „egyenes” kulcsból, akkor a 35 titkosítási kulcs akár nyilvánosságra is hozható. Ekkor egy un. nyitott titkosítási rendszerrel rendelkezünk. Tulajdonképpen meglep , hogy ilyenek ma már ténylegesen léteznek is. A kérdés az, hogy egy ilyen nyitott titkosítási kulcsos (röviden: nyíltkulcsú) rendszer milyen el nyökkel rendelkezik, és ha tényleg el nyös, akkor vajon miért csak az 1970-es évek közepén kezdtek vele foglalkozni, ami igazán kés nek számít a titkosírások ezerévekben mérhet történetéhez képest. Erre az a válasz, hogy a kereskedelmi célú kriptográfiának olyan sajátságos tulajdonságai vannak, amelyekkel a klasszikus (két partner közötti titkos információcserére 36 való) titkosírásoknál még nem merült fel igény. Ma már ténylegesen el nyt jelent egy kommerciális célú kommunikációs rendszerben ha abban több partner vesz részt és a hozzá szükséges technológia is rendelkezésre áll. Ugyanakkor ez a fajta szervezés egy csomó olyan új problémát is felvet, amelyeknek még nyomuk sem volt a klasszikus, két partner közötti titkos üzenetváltásnál. Nevezetesen az illetékesség (authentikáció) biztosítása ma nehezebbnek látszik, mint a titkosítás maga. Ez a probléma pedig igen fontos, különösen a modern financiális rendszerekben. Nagyon sok (10 vagy 100 ezres nagyságrend ) ügyfélkör esetén ugyanis nagyon nehéz eldönteni, hogy a személyesen nem ismert partner tényleg az-e, akinek mi gondoljuk. Nem illetéktelene a tranzakcióban való részvételre.

35

Itt egyszerüen arról van szó, hogy a titkosítási kulcsot nyugodtan nyilvánossá lehet tenni ha az „inverz” kulcs el állítása számítási kapacitásban és id ben ugyanannyiba kerül, mint a titkosított szöveg bármilyen más, a legális kulcs ismerete nélküli feltörése.

36

Ezt a választ F.L.Bauer fogalmazta meg így és szerintem nem teljesen igaz, mert a haditengerészeti hírközlésben (minekutána a rádió-kommunikációt feltalálták) már évtizedekkel korábban fennállt az az igény, hogy egy kommunikációs körben többen vegyenek részt titkosított üzenetváltásban. Ugyancsak több partnerrel kellett (volna) számolni a nagytávolságú kábeles távirati üzenetváltásnál is, pl. a kontinensek közötti tengeralatti kábelek üzembehelyezése után. Kényszerüségb l történt, hogy mégis inkább a kétpartneres üzenetváltási rendszerek szervezési elveit igyekeztek alkalmazni. Valószín
14

Manapság nagyon lényeges rendszertechnikai kérdés az un. PKI megoldása a hozzátartozó, rendezett jogi háttérrel együtt.

37

rendszertechnikai

Két partner (mondjuk András és Béla) közötti titkos üzenetváltásnál az aszimmetrikus kriptográfiáben négy kulcsra van szükség: •

András publikus kulcsa, amit Béla (vagy akárki) arra használ, hogy a kizárólag Andrásnak szánt üzeneteit titkosítsa vele;

•

András saját titkos kulcsa, amellyel a kizárólag neki szánt, titkosított üzeneteket meg tudja fejteni, legyen annak k ld je Béla, vagy bárki más.

•

Béla publikus kulcsa amit András (vagy akárki) arra használ, hogy a kizárólag Bélának szánt üzeneteit titkosítsa vele;

•

Béla saját titkos kulcsa, amellyel a kizárólag neki szánt, titkosított üzeneteket meg tudja fejteni, legyen annak k ld je András, vagy bárki más.

András nyilvános és titkos kulcsa. András a nyilvános kulcsok adatbázisából ismeri Béla nyilvános kulcsát is és ugyanott elhelyezi a saját nyilvános kulcsát is 37

Béla nyilvános és titkos kulcsa. Béla a nyilvános kulcsok adatbázisából ismeri András nyilvános kulcsát is és ugyanott elhelyezi a saját nyilvános kulcsát is

Personal Key Infrastructure, ami itt a személyhez kötött titkosítási kulcsok megbízható rendszerét jelenti 15

Ez így persze bonyolultabbnak látszik, mint a két személy közötti titkosított kommunikációra a klasszikus szimmetrikus rendszerekben használt egyetlen kulcs. N-felhasználós rendszerekben azonban a szimmetrikus szisztéma azt követelné, hogy A-nak B-vel, C-vel, D-vel...N-nel legyen egy-egy titkos kulcsa és ugyanígy a rendszer valamennyi tagjának is mindenkivel. Vagyis összesen N×N kulcsra van szükség. Nem beszélve arról a nehézségr l, hogy a rendszer minden egyes tagjának –a saját titkos kulcsán kív l– (N-1) kulcsot kell a hozzájuk tartozó nevekkel együtt nyilvántartania, kezelnie és használnia, egy ilyen rendszer gyakorlatilag alkalmazhatatlan lenne egy 38 kereskedelmi hálózatban. Praktikus okokból azonban az aszimmetrikus kriptorendszer alkalmazója mégis csak egy un. kulcskarikán tárolhatja a legközvetlenebb partnerei nyilvános kulcsait, hogy ne kelljen minden alkalommal a lassú interneten keresztül a kulcs szerverhez fordulnia egy-egy nyilvános kulcsért. A nyiltkulcsú rendszerekben a rendszer minden tagjának van egy-egy nyilvános és egy-egy titkos kulcsa, azaz összesen ugyancsak N×N kulcs van a rendszerben, de egyetlen felhasználónak sem kell tárolnia és menedzselnie a rendszer összes tagjának a (nyilvános) kulcsát, mert azokat bármikor megkeresheti egy „telefonkönyvben” 39 amely ráadásul tartalmazza a keresett kulcs autenticitásának igazolását is. A nyiltkulcsú rendszer tehát a rendszerben használt összes kulcsok számát tekintve nem egyszer bb a titkos kulcsos (szimmetrikus) rendszereknél, de nem is bonyolultabb azoknál és ráadásul a nagy hálózatok olyannyira kritikus autenticitási problémáit is megnyugtatóan kezelni tudja. Emellett azonban még más szolgáltatásokat is 40 képes nyújtani, amelyek szóba sem kerülhettek egy szimmetrikus rendszernél. Például András titkosított üzenetet k ldhet Bélának akkor is, ha el z leg nem állapodtak meg egymással, hogy titkosított kommunikációt fognak folytatni és, hogy milyen rendszerben milyen kulcsot fognak használni. Tehát az aszimmetrikus rendszerben mód van un. spontán (kezdeményezett) kommunikációra is.

38

Vagy talán nem is annyira lehetetlen. Végül is manapság mindennapi gyakorlat az, hogy pl. egy bank minden egyes ügyfelét külön-külön nyilvántartja és ha az illet a bankszámláját ATM automatáról is el akarja érni, akkor ehhez a bankjától egyedi bankkártyát kap, amit azonban csakis személyesen, a személyazonossága autentikus igazolásával kaphat meg. Egy bank ügyfelévé válni azonban mindenesetre sokkal bonyolultabb dolog, mint pl. bemenni egy (elektronikus) könyváruházba és vásárolni egy könyvet. Az elektronikus keresked ház éppen ellenérdekelt abban, hogy a potenciális vev körének bonyolult legyen a kapcsolatfelvétel vele.

39

Egy a hitelesít hatóság (Certification Authority=CA) által üzemeltetett –vagy általa igazolt- un. kulcs szerverr l van szó, amely a világhálón keresztül elérhet .

40

A már említett kulcs-hitelesítés(=autenticitás-biztosítás) mellett pl. nem kell a kommunikáló partnereknek a szimmetrikus rendszerekben az illetéktelenek számára feltétlenül titkos kulcsot valamilyen, a „normál titkosított” kommunikációs csatornánál sokkalta biztosabb csatornán eljuttatni a partnerhez – ami sokszor teljességgel megoldhatatlan. Emellet módot nyújt pl. az un. elektronikus aláírás alkalmazására is. 16

P

Jelölje K i egy n résztvev s rendszer i-edik tagjának nyilvános (=publikus) kulcsát, KTi pedig ugyannak a személynek a titkos (=privát) kulcsát.

KPi az i-edik személyhez hozzárendeli az Ei titkosítási eljárást (=Encryption), KTi pedig a csak adott személy által ismert Di megfejtési eljárást (Decryption). P T Gyakorlatilag nem lehet K i –b l K i –t kiszámítani. •

Ha Ei és Di kielégíti a következ összefüggést

Di (Ei ( x )) = x akkor olyan aszimmetrikus titkosítási módszerr l beszélünk, amely titkos üzenetváltásra való. •

Ha az el bbi feltételen kívül Ei és Di kielégíti a következ

összefüggést is

Ei (Di ( x )) = x akkor olyan elektronikus aláírási rendszerr l beszélünk, amellyel ugyanúgy hitelesíteni lehet valamit, mint ahogyan azt a mindennapi értelemben vett alá41 írással hitelesíteni lehet. •

Ezek alapján az aszimmetrikus üzenet-titkosítás a következ"képp mNködik: o

Ha András akar titkosított üzenetet (m, mint message) küldeni Bélának akkor a nyilvános kulcsszerveren a B betü alatt megkeresi Béla nyilvános kulcsát, KPB –t, amely kulcs egyértelm en meghatározza az EB titkosítást.42

o

Ezzel András titkosítja a Bélának szánt üzenetet és egy nyilvános csatornán elküldi neki.

c = EB (m) o

T B

Az így titkosított üzenet csakis Béla privát kulcsával (K

–vel) fejthet meg:

DB ( c) = DB (EB (m)) = m T

Mindaddig, amíg a K B privát kulcsot kizárólag Béla birtokolja, a neki címzett üzenetet csakis képes megfejteni. A titkosítás biztonsága tehát attól függ, hogy mennyire sikerül a privát kulcs titkosságát meg"rízni.

41

s t: sokkal jobban – mint látni fogjuk. Hadd jegyezzük meg itt mindjárt, hogy a hitelesítés (beleértve magának az elektronikus aláírásnak a hitelesítését is) nem technikai kérdés. Az, elektronikus aláírásunk hitelesítése, lényegében ugyanúgy történik, ahogy azt a mindennapi joggyakorlatban megszoktuk. Különösen fontos esetekben pl. közjegyz el tti aláírással, tanukkal igazolva, stb. Hangsúlyozzuk, hogy a hitelesítésnek ez a része nem kriptográfiai kérdés.

42

Itt persze feltételezzük, hogy a kulcsszerveren tárolt kulcsok valamennyi tulajdonosa ugyanazt a mindnyájuk által ismert titkosítási eljárást használja, csak a kulcsaik különböz k. 17

•

Az aszimmetrikus titkosítási és aláírási módszer a következ"képp mNködik: o

Ha András olyan titkosított üzenetet akar küldeni Bélának, amelyet a saját aláírásával (jelölje András saját szignóját SA) is ellát, akkor el ször is a saját T titkos kulcsával (K A –val, amely bmint láttukb egyértelm en meghatározza DA-t) titkosítja az m üzenetet:

d = DA ( m ) o

Ez után hozzákapcsolja az üzenethez a saját aláírását (SA-t), majd ezt a párost ugyanúgy titkosítja Béla nyilvános kulcsával, mint ahogyan azt el bb az 1.2 pontban bemutattuk. (Béla nyilvános kulcsához most is a kulcsszerverr l jut hozzá.)

e = EB (SA , d) = EB (SA , DA ( m )) o

és ugyanúgy elk ldi Bélának egy nyilvános csatornán, mint ahogyan azt az 1.2 pontban tette.

o

Béla a saját titkos kulcsát használva megfejti az (összetett) üzenetet:

DB ( e ) = DB (EB (SA , d)) = SA , d o

Persze Béla észleli, hogy a saját titkos kulcsával való megfejtés után látja ugyan András aláírását (SA –t, s ebb l tudja, hogy feltételezhet en tényleg András k ldte neki az üzenetet), de észleli azt is, hogy az üzenet maga (mármint d ) még mindíg titkosított. Ezért aztán a kulcs-szerverr l lekéri András nyilvános kulcsát és megpróbálja azzal megfejteni a d üzenetet.

EA (d) = EA (DA ( m )) = m Ha tényleg jelentéssel bíró szöveget kap, akkor ez biztosíték arra, hogy az 43 üzenetet tényleg András k ldte. Hadd zárjuk ezt a fejezetet néhány lényeges megjegyzéssel: •

43

Az elektronikus aláírás valójában több információt tartalmaz, mint az aláíró csakis reá jellemz szignóját. Nyilvánvaló ugyanis, hogy amíg a tradicionális aláírás tulajdonképpen az információt hordozó papírt hitelesíti, a számítógép hálózaton keresztül történ okirat-k ldésnél magát az okirat tartalmát kell hitelesítenie, mert semmi értelme nem lenne az üzenethordozó hitelesítésének. Ezen túlmen en azonban pl. az aláírás dátumát és id pontját (un. time stamp) is tartalmazza, de ezekre a kérdésekre még visszatérünk. Figyeljünk fel arra, hogy, hogy Béla csakis akkor lehet biztos András személyazonosságában ebben az eljárásban (=e protokollnál), ha a kulcsszerver üzemeltet je és hitelesít je (=CA) egészen biztosan és megbízhatóan gondoskodik arról, hogy a nyilvános kulcsok tulajdonosai tényleg azok legyenek, akiknek mondják magukat. Nyilvánvaló, hogy ez nem technikai, hanem sokkal inkább szervezési és közigazgatási/közjogi kérdés. 18

19

44

•

Megmutattuk, hogy egy sokfelhasználós nyíltkulcsú rendszerben sincs szükség több kulcsra, mint egy szimmetrikus rendszerben lenne ugyanannyi felhasználó esetén. Mindeddig nem említettük azonban, hogy a nyíltkulcsú rendszerekben használt kulcsok hosszúsága a kell kriptográfiai biztonság miatt rendszerint többszöröse a szimmetrikus rendszerekben használt kulcsokénak és a titkosításhoz, valamint a megfejtéshez szükséges számítási kapacitás sem kisebb, mint a szimmetrikus rendszerek alkalmazásakor, s t: rendszerint nagyobb azokénál. A nyiltkulcsú rendszereket tehát nem azért alkalmazzák, mert azok egyszer bbek a szimmetrikus rendszereknél, hanem azokért az el nyökért, amelyek szimmetrikus rendszerekkel egyáltalán nem érhet ek el. Pl. a „spontán” titkos kommunikáció lehet ségéért vagy azért, mert a nyiltkulcsú rendszerekben a kulcs-menedzsment sokkal egyszerübb, mint a klasszikus titkos kulcsos 44 kriptorendszerekben .

•

Az aszimmetrikus rendszerek valójában annyira bonyolultak, hogy egyáltalán nem lenne gazdaságos, ha mindenféle titkosított kommunikációra aszimmetrikus rendszert használnánk. Ezért ma inkább az un. hibrid rendszerek terjedtek el, amelyekben aszimmetrikus titkosítással k ldik meg egymásnak a partnerek azt az egyedi kulcsot, amelyet az éppen aktuális üzenetváltásban egyébként szimmetrikus szisztéma szerint alkalmaznak. Fogalmazhatunk úgy is, hogy az üzenetek titkosságának foka, min sítése természetszer en különböz , ezért a legnagyobb számításigény , tehát legköltségesebb titkosítást (t.i. az aszimmetrikus rendszereket) csakis a legtitkosabbnak min sül információk titkosítására alkalmazzák. Ilyenek pl. a szimmetrikus rendszerek véletlenszer en választott és csak egyszer használatos titkosítási kulcsai. A hibrid rendszerek (mint pl. a PGP) pontosan ezt az elvet valósítják meg. Manapság, amikor igen divatos az aszimmetrikus rendszerekr l beszélni, nem lehet eléggé hangsúlyozni, hogy a kifinomult, modern szimmetrikus titkosító rendszerek is használatosak és megvan a maguk jelent sége.

•

Különböz szerz k különböz hasonlatokat használnak az aszimmetrikus titkosítás lényegének a bemutatására. F.L. Bauer olyan, egyirányba nyíló csapóajtóról beszél, amelynek a „bels oldalán” azért van egy titkos gomb, amelyet megnyomva a másik irányban is át lehet haladni azért a csapóajtón, de ehhez persze ismerni kell a titkos gombot. Randall K. Nichols a halászok varsáját említi, amelybe könnyen bemegy a gyanútlan áldozat, de jószerivel reménytelen ugyanazon az úton kitalálnia bel le és maguk a halászok is egy csak általuk nyitható másik „ajtón” veszik ki a zsákmányt. E sorok szerz jének kedvenc hasonlata egy olyan lakat, amelyhez két, különböz kulcs tartozik és a lakat úgy m ködik, hogy ha az egyik kulccsal bezárták, akkor csakis a másikkal nyitható ki. (Egyébként pedig mindegy, hogy melyik kulccsal zárják be.)

Lásd még a 36. oldalon ezzel kapcsolatban leírtakat is. 20

Ezzel a hasonlattal mind a titkosítás, mind az elektronikus aláírás „m ködése” jól szemléltethet , bár a knapsack titkosítás leírásánál láttuk, hogy a titkosító (E) és a megfejt (D) algoritmusok megválasztása után már egyáltalán nem mindegy, hogy melyik kulcsot tartjuk meg titkos kulcsként és melyiket tesszük publikussá. Az egyirányú függvények

Az aszimmetrikus rendszerek (mai) sikere lényegében azon alapul, hogy sikerül-e olyan titkosítási kulcsot (és módszert) találni, amelyb l gyakorlatilag nem lehet a megfejtési kulcsot (és módszert) visszavezetni. Említettük, hogy magát az elvet Diffie és Hellman publikálta 1976-ban, de az els , gyakorlatban is használatos rendszert nem k dolgozták ki. Igaz, hogy kés bb k maguk is találtak és publikáltak olyan nyiltkulcsú rendszert, ami máig is használatos, s a követ ik több ilyen rendszert is kitaláltak. Ezekre az algoritmusokra alább még visszatérünk de itt el bb az un. egyirányú függvények néhány általános jellemz jével foglalkozunk. A szigorúan egyirányú függvények. Az X

45

Y leképezést , azaz f:X

Y

-et szigorúan egyirányúnak nevezzük, ha a következ két feltétel teljesül: •

Létezik olyan gazdaságos és hatékony számítási módszer, amellyel minden x X hez kiszámítható f ( x ) értéke, viszont

•

Nincs olyan hatékony számítási módszer amellyel az f (x ) képtartomány minden eleméb l visszaszámolható lenne x értéke.

Arto Salomaa már többször említett telefonkönyves titkosítási példája (Lásd a 8. oldalt!) nagyon közérthet en, f ( x ) nondeterminisztikus jellegét is szemléltetve mutaja be, hogy mir l is van szó. A UNIX rendszerben pl. a password-öket ilyen szigorúan egyirányú függvényekkel rejtik el és tárolják, de ilyen szisztémát alkalmazott már az 1980-as évek közepén a Digital VMS rendszere és ilyen visszafejthetetlen formában tárolja a password-öt az MS Windows 2000-es rendszere is. A jelszó ellen rzésekor az egyirányú függvénynyel el állítják a hozzátartozó cryptotext-et és azt hasonlítják össze a tárolt cryptotext-tel.

45

Mivel definició szerint az f függvény az X halmaz (= alaphalmaz vagy startomány) elemeit egy irányban egyértelm<en leképezi az Y halmazba (= képhalmaz vagy képtartomány), az ilyen, egyik irányban egyértelm< leképezést (és magát az f függvényt is) injektívnek nevezzük. Lásd az I. Függelékben közölt ábrát is. 21

A csapóajtó-szerN egyirányú függvények. Kriptográfiai célra (az említett password példáktól eltekintve) nem alkalmasak a szigorúan egyirányú függvények, mert legalább az üzenet legális fogadója hatékony megfejtési módszerrel kell, hogy rendelkezzen. Egy injektív f (x ) f :X

Y

függvényt csapóajtó-szer egyirányú függvénynek nevezünk, ha az alábbi két feltételt kielégíti: •

Létezik olyan gazdaságos és hatékony számítási módszer, amellyel minden x X hez kiszámítható y = f ( x ) értéke, és emellett

•

Létezik f (x ) inverze is, amelyet f –gyel jelölünk, de ezt az inverz függvényt 46 nem lehet el állítani a képtartomány elemeinek ismeretében , azaz (algoritmikus módszerrel) nem fejthet meg a titkosított kommunikációt lehallgató illetéktelen által. A legális címzett természetesen rendelkezik az inverzzel, amellyel az

-1

x=f

-1

(y)

összefüggéssel megfejtheti a neki szóló üzeneteket. Matematikai értelemben persze óvatosan kell bánni az ilyen kijelentésekkel: „létezik ugyan az inverz, de nincs módszer, amellyel megtalálható lenne.” Elvileg ugyanis mindíg van valamilyen módszer. A gyakorlatban az dönti el a kérdést, hogy van-e elegend számítási kapacitás és id a megfejtésre. A skála egyik végén vannak a „kikövetkeztethetetlen” problámák, a skála másik végén pedig a „hatékony” módszerek. Az átmenet nem éles, de ha lenne is valamilyen határ közöttük, akkor a számítási technológia fejl désével egyre több, korábban kikövetkeztethetetlennek tartott probléma kerülne át azok közé, amelyek megoldására van „hatékony” módszer. Az 1990-es évtizedben nagyjából minden második évben megduplázódott a leggyorsabb egyedi számítógépek átlagos m veleti sebessége és nagyjából 15 havonta felez dtek az eszközök árai. (Lásd még a 30. oldalon az un. Moore törvényr l mondottakat és kommentárjait.) A kriptográfia úgy igyekszik kompenzálni ennek a fejl désnek a titkosított szövegek feltörését egyre hatékonyabbá tev hatását, hogy alkalmas módon növeli azokat a titkosítási paramétereket, amelyek egyre nehezebbé teszik a feltörést. Erre már a DES tárgyalása kapcsán adtunk példát, amelyb l az derült ki, hogy a blokk-titkosító módszereknél a kulcshosszúság növelésével igen hatékonyan növelhet a feltöréshez szükséges id .

46

s t: az összetartozó x – y nyíltszöveg – titkosított szöveg blokkok ismeretében sem, legalább is a mindenkori számítási kapacitással, valamely reális id alatt. 22

Álljon itt egy másik példa (F.L. Bauert l) [2], amely az el bb említett technológiai fejl dés tükrében mutatja a feltörés nehézségeit. Egy n szám aránylag könnyen kiszámítható a törzstényez inek összeszorzásával, ha ismertek ezek a törzstényez k. Összehasonlíthatatlanul nehezebb dolog azonban igen nagy n számok esetén azok törzstényez it (= prím faktorait) megkeresni. Ehhez a ma ismert leggyorsabb keresési algoritmus alkalmazása esetén is nagyságrendileg

ln n × ln ( ln n )

e m velet szükséges 70

n = 10 esetén 1984-ben egy akkor leggyorsabbnak számító CRAY X-MP gépnek 9,5 órájába került a prímfaktorok meghatározása. (Ennek a gépnek a sebessége durván 8 1,1×10 makro számítási lépés volt másodpercenként.) Ha bamint említettükb feltételezzük, hogy a világ leggyorsabb gépeinek a számítási sebessége kétévenként kb. megduplázódik, akkor közelít en a következ faktorizációs id ket kapjuk: n

A prímfaktorok megkereséséhez szükséges Id$ 1984-ben

1994-ben

2004-ben

10

50

181 sec

5,66 sec

181 ms

10

70

9,5 óra

0,297 óra

34,2 sec

10

100

344 nap

10,75 nap

8,3 óra

10

140

2200 év

68,75 év

803 nap

10

200

48×10 év

10

250

74×10 év

10

300

62×10

6

1,5×10 év

9

2,3×10 év

12

év

1,9×10

6

48×10 év

9

74×10 év

12

év

3 6

62×10

10

év

Randall K. Nichols professzor felhívja azonban a figyelmünket arra, hogy a nyers er vel való feltörés módszerénél nem mindíg szükséges valamennyi próbát elvégezni mert lehet, hogy már el bb eredményt kapunk. Mindenesetre ennek véges és kiszámítható valószín sége van. 1994-ben pl. szenzáció volt, amikor egy 129 számjegy decimális szám törzstényez it (összesen két, egyenként 65 decimális jegy prímfaktora volt) sikerült 1600, az Interneten keresztül összekapcsolt géppel 8 hónap alatt megfejteni, holott az egyetlen leggyorsabb géppel számolva akkor ehhez 3330 nap kellett volna. Ebb l kiindúlva arra következtetnek, hogy 2004-t l az 512 bites bináris számokkal ábrázolható egészszámok nem nyújtanak majd kell biztonságot a faktorizáció ellen. Ezek a nagy számok azonban megtéveszt ek, mert nem csak technikai, hanem fizikai 60 korlátok is léteznek. A jelenlegi ismereteink szerint pl. egy 10 bit kapacitású tár meg70 valósításához szükség lenne a Naprendszer teljes tömegére. Hasonlóképpen 10 m velet elvégzéséhez több id kellene, mint amennyi a Világegyetem keletkezése óta eltelt 18 ( = 10 sec.), még akkor is, ha egy-egy m velelethez felhasznált id nem hosz-szabb, -43 mint az un. Planck id (= 10 sec). Egyébként a Planck id az a legrövidebb id tartam, aminek még van valamilyen jelentése a fizikában. 23

Az aszimmetrikus kriptográfia általános elvei A klasszikus és a modern nyiltkulcsú kriptorendszerek összehasonlításának legegyszer bb analógiája (Randall K. Nichols szerint) a lakattal lezárt doboz, amely az üzenetet rejti. A klasszikus rendszerben a címzett valamilyen nyilvános módon (pl. postán) megkapja ezt a dobozt, amelyet egyetlen lakat zár le és valamely abszolute megbízható, egyáltalán nem nyilvános úton-módon megkapja a lakat kinyitásához szükséges kulcsot. Ezért a kulcs-menedzsment nagyon fontos kérdés a klasszikus 47 kriptográfiában. A nyilvános kulcsú rendszerekben az EK titkosítási kulcsból semmilyen (gyakorlati) módon nem lehet levezetni a DK megfejtési kulcsot. Az el bbi hasonlattal élve, olyan lakatot kell elképzelni, amely kulcs nélkül is bekattantható. Béla nyitott lakatjai nyilvánosan rendelkezésére állnak bárkinek, aki üzenetet akar küldeni neki. Ha András küld üzenetet Bélának, akkor Béla egy ilyen nyitott lakatját kattantja rá az üzenetet tartalmazó dobozra, amit aztán maga (ti. András) sem tud többé kinyitni. Az üzenethez csakis Béla férhet hozzá. Létezik azonban olyan protokoll is, amely nem igényli, hogy az üzenetk ldést megel z en Béla elküldje a nyitott lakatját Andrásnak (és mindenki másnak, aki neki titkosított üzenetet akar k ldeni). Ez a következ : El ször András k ldi el az üzenetet tartalmazó dobozt Bélának úgy, hogy azt András a saját lakatjával zárja le (amihez Bélának nincs kulcsa). Béla a saját lakatjával (is) lezárja a dobozt és visszak ldi azt Andrásnak. Béla lakatjához persze Andrásnak nincs kulcsa, de mind András lakatjáról bárki tudhatja, hogy az csakis Andrásé, mind Béláéról, hogy az csakis Béláé. Ezek után András a saját kulcsával kinyitva leszedi a saját lakatját a dobozról és ismét elküldi a dobozt Bélának. Most már csak Béla lakatja van a dobozon, amit Béla a saját kulcsával kinyitva végül hozzáférhet a neki szánt üzenethez. Mindezt a következ ábra szemlélteti:

47

Már utaltunk arra korábban, hogy a modern, nyiltkulcsú kriptográfiában is fontos kérdés a kulcs-menedzsment s ráadásul egyáltalán nem technikai, hanem sokkal inkább szervezési (és adminisztrációs) kérdés. 24

A

A

A

A

B

Publikus üzenetközvetít csatorna

B

B

A

B

B

25

Figyeljünk fel arra, hogy egyetlen egyszer sem megy keresztül a dobozba zárt üzenet a nyilvános csatornán úgy, hogy legalább egy lakat ne legyen rajta. Ezzel a passzív lehallgatás kiküszöbölhet . Ezzel az analógiával mindössze az a gond, hogy mi van akkor, ha a postás is ráteszi a dobozra a saját lakatját? 48

Mindenesetre az elmondottak alapján megfogalmazhatjuk egy nyiltkulcsú kriptorendszer megalkotásának általános elveit (ill. lépéseit), melyek a következ k: 1. lépés

Válasszunk egy bonyolult matematikai problémát, amit jelöljünk itt P-vel. P-nek bonyolultságelméleti szempontból polinomiális id"ben* kikövetkeztethetetlennek kell lennie, azaz nem létezhet olyan algoritmus, amely P-t minden esetben polinomiális id ben megoldani képes. Mind az átlagos komplexitásnak, mind a legrosszabb esetben fennálló komplexitásnak magasnak kell lenni.

2. lépés

Választanunk kell P-hez egy (aránylag) könny alproblémát ( = PkönnyK ), amely polinomiális id ben megoldható és –ha lehetséges- lineáris.

3. lépés

Titkosítsuk ( = Encryption) a PkönnyK alproblémát úgy, hogy a titkosítás eredményéül kapott Ptitkos ne is emlékeztessen PkönnyK –re.

4. lépés

Tegyük nyilvánossá Ptitkos –t leírva, hogy az hogyan használható titkosítási kulcsként. Tartsuk viszont titokban azt, hogy a PkönnyK nyíltszöveget hogyan lehet visszanyerni a Ptitkos cyphertextb l. Ez a visszanyerési mód a titkos csapóajtó.

*

A polinomiális id fogalma sokszor el fordul ebben az anyagban. Tulajdonképpen a XIV. Függelék lenne hivatott ezt a fogalmat pontosan definiálni és megmagyarázni, de az abban leírt bés eredetileg Arto Salomaa-tól származób magyarázat igen messzire vezet és feltételez olyan el tanulmányokat is, amelyekkel a f iskolai hallgatók nem rendelkeznek. Ezért egyszerübb, ha a polinomiális id alatt nem is id t, hanem egy számítógéppel elvégzend m veletek olyan mennyiségét értjük, amely valamilyen reális számítási kapacitással reális id alatt elvégezhet .

48

Lásd még a 13. oldalon a Merkle-Hellman sémával kapcsolatban mondottakat is.

26

Az elnevezést kénytelenek vagyunk megtartani és használni, mert az egész jelölésrendszer és a rövidítések erre épülnek és a nemzetközi szakirodalom is ezeket használja. Mindezek mellett a XIV. Függelék igen hasznos ismereteket tartalmaz és a mélyebben érdekl d olvasónak feltétlenül ajánlható.

27

5. lépés

6. lépés

A rendszer részleteinek olyanoknak kell lenniük, hogy a nyíltszöveg visszanyerése nagyon különböz legyen az illetéktelen megfejt és a legális címzet számára. A legális címzett PkönnyK ismeretében aránylag könnyen kinyithatja a csapóajtót. Az illetéktelen megfejt nek azonban meg kell találnia Ptitkos megfejtését. A rendszert minden elképzelhet szempontból le kell tesztelni és nem szabad meglep dni, ha az a gyakorlati teszteléskor megbukik.

Kevésbé meghatározott fogalom a titkosítási folyamat elvonatkoztatására P könny sége, a csapóajtó specifikációja, és ellenállóképessége az el zetes számításokkal szemben és hasonló dolgok. A bemutatott knapsack titkosítási példa jól illeszkedik a fentiekben felsorolt hat lépéshez. A következ oldalon feltüntetett táblázat felsorol néhány olyan számelméleti tételt és fogalmat, amit a nyíltkulcsú kriptográfia használ. Ezekkel a fogalmakkal kapcsolatban komoly er feszítéseket tettek, hogy valamilyen módon definiálják a 49 bonyolultságukat. Ezeknek a fogalmaknak egyébként igen jelent s szerepük van a nyiltkulcsú (=aszimmetrikus) kriptográfia fogalomkörében, mint a kés bbiekben látni fogjuk. A táblázatban felsorolt problémáknak nincs determinisztikus polinomiális id ben eredményt adó algoritmusuk és nem komplettek egyetlen természetes bonyolultsági osztályra nézve sem. A táblázat ráadásul némi egyszerüsítésekkel sorolja fel ill. nevezi meg ezeket a matematikai problémákat, de így is eléggé nyilvánvaló a bonyolultságuk. Mindezek ellenére azonban bizonyos összehasonlításokat végeztek már közöttük arra nézve, hogy a felsorolt problémákat sorrendbe állítsák a megoldási 49

mondja Randall K. Nichols professzor a Guide-ban, de azért ez a dolog számos kívánnivalót hagy. A legnagyobb probléma az, hogy jelöléseket és fogalmakat alkalmaz (már XIV. Függelékben is), amelyekr l nem mondja meg, hogy mit jelentenek. E sorok szerz jének a véleménye szerint a legnagyobb probléma a sokat használt polinomiális id fogalmának a meghatározási bizonytalansága, ami egyáltalán nincs elintézva azzal, hogy egy adott Turing gépet egy algebrai polinommal lehet definiálni.

28

nehézségeik szempontjából és a legnehezebben megoldhatónak az elliptikus görbével kombinált diszkrét logaritmus bizonyult. Ez más szóval azt jelenti, hogy azonos kulcshosszúságok esetén az utóbbi nyújtja a legnagyobb kriptográfiai biztonságot. ( Az RSA rendszernél pl. több nagyságrenddel nagyobb biztonságot.) A nyíltkulcsú titkosításhoz használt számelméleti problémák összefoglalása Faktor (n)

Keressük meg n törzstényez it (= prímfaktorait)

Prímszám-ellen rzés (n)

Ellen rízzük, hogy a megadott n szám törzsszám-e vagy összetett szám, azaz törzstényez kre bontható

Találjuk meg az els nnél nagyobb prímszámot

Ehhez nem kell kommentár

Négyzetes-mentesség Squre-Freeness (n)

Ellen rizzük, hogy van-e olyan prímszám, amelynek a négyzete n-nek valódi osztója

Kvadratikus residuum (a,n)

Vizsgáljuk meg, hogy van-e olyan x szám, amelyre 2 x ? a (mod n)

Négyzetgyök (a,n)

Ha létezik egyáltalán, akkor találjunk olyan x számot, (azaz egész négyzetgyököt) amenek a négyzetgyökére fennáll, fennáll, hogy ? x ? a (mod n)

Diszkrét logaritmus (a, b, n)

Ha lehetséges, akkor találjunk olyan x számot, amelyre fennáll, hogy x a ? b (mod n)

Elliptikus görbe diszkrét-logaritmus (a, b, x, y, P, Q)

Egy a modulussal és egy p prímszámmal definiált elliptikus görbe a megoldása az (x,y) számpárok halmazának úgy, hogy 2 3 y ? x +ax + b (mod p) ahol a és b adottak. Ha egy (x, y) koordináta kielégíti az el bbi egyenletet, akkor P(x, y) egy pont az elliptikus görbén. Rögzített a és p prímszám valamint elliptikus görbe esetén xP jelöli azt, hogy a P pontot x-szer össze50 adtuk saját magával . Jelölje a görbén így kapott 50

Persze semmi értelme sincs arról beszélni, hogy egy pontot akárhányszor hozzáadunk saját magához. Az [1] könyv az algoritmusok leírása kapcsán pontosabb definiciót is ad erre a módszerre. Itt úgy lehet értelmezni xP-t, hogy az ellipszisen magán x-szer továbbhaladunk annyival, amennyit a kiindulópont és a P pont közötti görbeszakasz meghatároz. 29

pontot Q, tehát Q = xP.

A feladat az, hogy adott P-hez és Q-hoz találjunk ilyen x-et. A munkatényez (=Work Factor)

Whitfield Diffie szerint a számítási igény szempontjából az id a leglényegesebb. A kérdés a következ : „Mennyibe kerül, hogy választ kapjak, amikor éppen szükségem van rá?” Moore tapasztalati törvénye szerint a számítási teljesítmény 18 havonta 51 megduplázódik. Eszerint egy ma 1000 dollárért megvehet számítógép számítási kapacitása a kétszerese annak, amit ugyanennyiért másfél éve megvehettünk. Moore törvénye figyelemreméltóan pontosnak bizonyult az elmúlt évtizedben. Ez a gyors fejl dés igen mélyrehatóan befolyásolja a kriptorendszereket. Egy adott kriptográfiai rendszer feltöréséhez szükséges m veletek számát nevezik munkatényez"nek, de az nincsen pontosan meghatározva, hogy ezen belül mit nevezünk m veletnek. Lehetnek e m veletek pl. dekódolási m veletek (=encryptions), mint ahogyan a nyers er alkalmazásakor végigpróbáljuk a dekódolást az összes lehetséges kulccsal és egy m veletnek tekintjük egy kulcs kipróbálását, de lehet a m velet valamilyen ett l teljesen különböz dolog is. A túl-egyszerüsítés szellemében a következ kben feltételezzük, hogy a m veletek mindíg párhuzamosíthatóak. Eszerint ha két processzor 5 másodperc alatt képes 1 millió m velet elvégzésére, akkor 10 processzornak 1 másodpercre van szüksége ugyanehhez. A mi céljainkra meglehet sen konzervatív ez a feltételezés és ha történetesen nem megvalósítható (mármint a párhuzamosítás) akkor „csupán” arról van szó, hogy bonyolultabbá válik a probléma megoldása. Azt is feltételezzük, hogy az adott probléma megoldására szabott speciális hardver rendelkezésünkre áll és az elemei párhuzamosan dolgoz52 hatnak éppen az adott speciális kriptográfiai megoldáson. Nagyon lényeges azonban, hogy itt olyanfajta párhuzamosításról van szó, amelynél az egyes célprocesszoroknak nem kell egymással kommunikálni, csak egy olyan központi egységgel, amely kiosztja nekik a munkát. Ellenkez esetben ugyanis nem a processzorok sebessége szab határt az egész rendszer sebességének, hanem a kommunikációs busz sebessége. A mai (2000-es) technológiai szinten pl. 6-8 processzornál többet nem is érdemes úgy párhuzamosítani, hogy mindegyik kommunikáljon mindegyikkel, mert az ket összekapcsoló busz úgy sem engedi meg ennél több processzor kell kihasználását. Ilyen, egy központi egységgel való kommunikációt valósít meg pl a SETI@HOME program, amely több tízezer PC-t használ párhuzamosan az igen lassúnak számító világhálón keresztül. 30

10 3

3 3

9

Ha egy rendszer munkatényez je pl. 2 = (2 ) ? ( 10 ) = 10 , azaz 1 milliárd m veletet képes végrehajtani az id egység alatt. Speciális hardver m veleti elemek esetében azonban minden egyes ilyen m velet olyan összetett lehet, amelyet az általános célú számítógépeken esetleg csak utasítások százaival lehetne megvaló9 sítani. Még így is az a helyzet, hogy specializált feltör gépek képesek 10 ilyen

51

F.L Bauernek a 24. oldalon bemutatott táblázatánál az ahhoz használt forrás alapján a számítási teljesítmény kb. kétévenkénti duplázódásával számoltunk. Itt viszont a Nichols professzor által említett Moore törvény szerint kb. másféléves duplázódási id vel.

52

Emlékezzünk rá, hogy a DES feltörési történetének leírásakor szó is volt egy DES-Cracker-nek nevezett ilyen gépr l, amelyhez kifejezetten a feltörési algoritmus részm
komplex m veletet elvégezni 5 másodperc alatt.

31

30

Egy szó, mint száz, nem nyilvánvaló, hogy egy adott kriptorendszer egy 2 munkatényez j célgéppel feltörhet , de mindenesetre el fordulhat, hogy elfogadható id n belül feltörheti az adott kriptográfiai rendszert. 60

Egy 2 –os munkatényez más szóval azt jelenti, hogy egymillió olyan processzor, amelyek mindegyike egymillió m veletet hajt végre másodpercenként (egymillió másodperc azaz valamicskével több, mint 11,5 nap alatt képes a problémát megoldani.) Manapság reálisnak tekintik egy ilyen monstrum megépítését ha a feltörési algoritmus komplex lépésenek végrehajtására lehet célprocesszorokat építeni, vagy már léteznek is ilyen célprocesszorok (és a megoldás során nem kell egymással kommunikálniuk). 90

Továbbhaladva ezen a gondolatsoron kb. a 2 -es munkatényez látszik az els olyannak, amelynek a megoldása nem valószín a belátható jöv n belül. Egymilliárd párhuzamos célprocesszor nem látszik teljesen irreálisnak és elképzelhet a másodpercenkénti egymilliárd m velet is, még ha olyan bonyolult is egy-egy m velet, mint amilyen pl. a DES titkosítás igen-igen összetett, sokrundos m veletsora. Az egymilliárd másodperc azonban kereken 30 évet jelent, ami elegend en hosszú id ah90 hoz, hogy a 2 -es munkatényez j mai kriptorendszereket elegend en biztonságosnak tekinthessük. 120

A 2 munkatényez j kriptorendszer feltörése egyáltalán nem látszik valaha is elér120 10 12 3 12 12 3 het nek. 2 = (2 ) ? ( 10 ) = ( 10 ) -12 10 másodperc egy pikoszekundum milliomod része és minden ma ismert logikai eszköz (beleértve a legszéls ségesebb kisérleti eszközöket is) igen-igen messze áll attól, hogy ilyen rövid id alatt képes legyen akár egyetlen logikai alapm velet elvégzésére is, nem is beszélve az eddig emlegetett igen komplex m veletekr l. Milliószor millió processzor párhuzamosan ma fizikailag teljesen lehetetlennek t nik. (Egygrammos processzorokkal számolva a processzorok össztömege 1 millió tonna lenne, s akkor nem szóltunk egy szót sem az ezt befogadó szerkezetr l, energia12 igényr l ill. a h disszipációról.) Mindemellett 10 másodperc kereken 30 ezer évet tesz ki ami, ugye, képtelen megoldási id lenne. A kriptográfusok között egyfajta sporttá vált kulcsok végigpróbálásának és validálásának költség- és id -becslése. Az USA törvényei tiltották bizonyos kulcshosszúságnál hosszabb kulcsokat alkalmazó rendszerek exportját. 1995 szén ez a korlát a max 40 bit hosszúságú kulcsokat jelentette. Ekkor egy kriptográfiai szimpoziumon kimondták, hogy a nyers er módszerével (és az akkori technikával) a max 40 bites kulcsok könnyen feltörhet k és a kereskedelmi alkalmazásokhoz kielégít biztonságot nyujtó kulcsoknak 70-90 bit hosszúságúaknak kell lenniük. A modern titkos kulcsos rendszerek feltörésével kapcsolatos versengésr l már a DES kapcsán szóltunk. Talán érdemes itt is néhány ilyen „sporteredményt” felsorolni. A párizsi Ecole Polytechnique hallgatói már 1994 augusztusában feltörtek egy 40 bites DES kulcsot. 1995 januárjában az MIT hallgatói megismételték a 40 bites kulcsú DES feltörési kisérletet. Ehhez egy (akkor) 83 000 dolláros grafikus számítógépet használtak és az egy kulcsra es átlagos költség 584 dollár/kulcs volt. Az 1995 szén tartott kriptográfiai szimpoziumon versenyt is hírdettek a különböz hosszúságú kulcsok feltörésére. A 40-bites kulcsot már a szimpozium alatt feltörték, a 48 bites kulcsot, pedig egy héttel a konferencia befejezése után. Az 56 bites DES kulcs feltörése is csak 5 hónapot váratott magára. Végül az Electronic Frontier Foundation (EEF) hírdetett meg egy pályázatot olyan DES feltör gépre, amelyet „mindössze” 32

negyedmillió dollárból ki lehet hozni s végül is 1998 májusában megdöntöttek vele minden addigi rekordot. (B vebben lásd a DES c. jegyzetrészben.) A kriptorendszerek élettartama

Diffie és Landau két élettartam-fogalmat definiált a kriptorendszerekre: II. III.

Mennyi ideig van ill. lesz a rendszer használatban Mennyi ideig maradnak ténylegesen titokban azok az üzenetek, amelyeket az adott rendszerrel titkosítanak.

Mind a kriptográfiai rendszereknek, mind a titkosító berendezéseknek gyakran igen hosszú az élettartama. Pl. a II. világháború el tt bevezetett Sigaba rendszert a háború után is, egészen az 1960-as évek elejéig használták. Az egyik háború utáni rotoros titkosítógép, az un. KL-7-es 1950-t l 1980-ig volt alkalmazásban. A DES több, mint 20 éve szabvány már az Egyesült Államokban és csak 2001 nyarára igérik a helyette bevezetend új szabványt (ti. Az AES-et). Van egy csomó más rendszer is, amelyeket se nem szabványosítottak, se nem katonai rendszerek s ezek élettartama még az említettekénél is hosszabb. Maguknak a titkosított üzeneteknek az igen hosszú élettartamára is vannak példák. Pl. Az un. Veronai üzenetek megfejtésével közel 40 évig kisérleteztek abban a reményben, hogy felfedi azoknak a kémeknek a kilétét, akik az 1930-as években még fiatal emberek voltak, de valószín , hogy mire az üzeneteket megfejtették, már nem is éltek, vagy rég nyugdíjba vonultak a titkosszolgálatoktól. A Sigaba titkosító rendszer elvét az 1930-as évek közepe táján fedezték fel és legel ször csak 1996-ban publikálták. A H-bombával kapcsolatos kutatásokat az 1950-es évek elején végezték és az ezekkel kapcsolatos eredményeket máig is titokban tartják. Sok ipari folyamatot min sítettek kereskedelmi titoknak és tartják titokban már sokkal régebben, mint a H bomba kutatás/fejlesztési eredményeit. Az Amerikai Egyesült Államokban a választási adatokat, a személyi jövedelemadó bevallásokat, a személyiséghez kötött orvosi adatokat és más személyi adatokat (feltehet en) élethosszig titokban tartják. Ha ma hozzálátunk, hogy egy kriptográfiai berendezést fejlesszünk ki, akkor az USAban is legalább 2-3 év kell ahhoz, hogy annak a használata szélesebb körben elterjedjen és ha beválik, akkor 20-25 éves élettartamot lehet neki jósolni. Persze nem magának az egyedi berendezésnek, hanem annak a módszernek, amelyet megvalósít és esetleg szabványosítanak is. Ha ezzel a rendszerrel az üzleti kommunikáció széles körét szándékoznak titkosítani, akkor az így titkosított adatok közül jónéhányat még évtizedekig titokban is akarnak tartani majd azután is, hogy magát a rendszert felváltotta valamilyen újabb és modernebb rendszer. Vegyük pl. a 2001-ben bevezetésre kerül AES szabványt. Eszerint ezt a titkos kulcsos rendszert kb. 2025-ig használni szándékoznak és a vele titkosított adatokat kb. 2050-ig még titokban akarják tartani. Tehát 2050-ig ellen kell állnia a kriptoanalitikusok feltörési kisérleteinek, pedig fogalmunk sem lehet arról, hogy 50 éves távlatban milyen matematikai és számítástechnikai er források állnak majd a kriptoanalitikusok rendelkezésére.

33

A nyiltkulcsú kriptográfia el nyei. A kulcs-menedzsment A nyiltkulcsú kriptográfiának óriási el nyei vannak. A publikus kulcsok talán legmeszszebbre ható innovációja az, hogy hogyan lehet titkosítási kulcsokat k ldeni nyilvános csatornán és hogyan kell a nyílt kulcsokat menedzselni. Gondoljunk bármelyik klasszikus, vagyis szimmetrikus kriptorendszerre. A titkosítási kulcs megadja egyúttal a megfejtés kulcsát is, tehát a titkosítási kulcsot nem lehet nyilvánossá tenni. Ez más szóval azt jelenti, hogy a titkos üzenetváltásban résztvev partnereknek el re meg kell állapodniuk a titkosítási módszerben, beleértve az alkalmazott kulcsot is. Ezt meg lehet tenni vagy úgy, hogy az üzenetváltás el tt személyesen találkoznak egymással, vagy pedig úgy, hogy valamilyen abszulut biztonságos és titkos csatornán küldik el a titkosítási kulcsot a másiknak. Amint már a 16. oldalon is említettük, egy nyiltkulcsú kriptorendszerben nem kell annak a két félnek el zetesen találkoznia, amely titkosított üzenetet akar váltani, azaz mód van un. spontán kezdeményezett üzenetküldésre (is). Még csak ismerniük sem kell egymást és semmilyen megel z üzenetváltásra nincs szükségük. Ez roppant nagy el ny. Például egy nagy adatbank esetén, amelyben igen nagyszámú felhasználó van regiszrálva és egy adott felhasználó üzenetet akar váltani egyetlen másik felhasználóval, akkor ezt megteheti úgy, hogy semmilyen más adatra sincs szüksége, mint ami úgyis megvan az adatbázisban. A klasszikus és a nyiltkulcsú kriptorendszerek összehasonlíthatók az alkalmazott kulcsok tekintetében is. Mivel minden kulcsot le kell írni valahogyan, a kulcs leírása egy specifikus ábécé betüivel történik. Ebb l a szempontból a kulcs egy szónak tekinthet . Ilyen szempontból beszélhetünk a kulcs hosszúságáról a klasszikus és a nyiltkulcsú rendszerekben. E tekintetben jelent s különbség van a klasszikus és a nyiltkulcsú kriptorendszerek között. Tekintsük el ször a klasszikus kriptorendszereket. Ha a kulcs hosszabb, mint a nyíltszöveg, akkor lényegében semmit sem nyertünk az egésszel. Tekintettel arra, hogy a kulcsot valami abszolut biztonságos csatornán kell továbbítanunk, a kulcsnál rövidebb nyíltszöveggel ezt ráadásul egyszer bben meg lehet tenni. Természetesen vannak olyan esetek, amikor a kulcsot már korábban úgyis elküldtük az abszolut biztos csatornán, s ekkor mégis csak érdemes a kulcsnál rövidebb nyíltszöveget is ugyanazzal a kulccsal titkosítani. (feltéve, hogy több üzenet titkosításához is ugyanazt a kulcsot használjuk, ami bizony rendszerint nem így van. Ami a nyiltkulcsú kriptorendszereket illeti, a titkosító kulcs hossza igen nagy mértékben irreleváns. Ezt végül is csak az használja, aki titkosított üzenetet akar küldeni és még tárolnia sem kell, mert a kulcs-szerveren akármikor elérheti. Az egyetlen feltétel az, hogy az üzenet fogadójának valamilyen nagyon biztonságos helyen és módon tá53 rolnia kell a (privát) kulcsot, mert ett l függ az egész rendszer biztonsága. A nyiltkulcsú rendszerek legf bb el nye a kulcs-menedzsment egyszer sége.

53

Ezt már a 18. oldalon az 1.3 ponttal kapcsolatban is megállapítottuk, de –a fontossága miatt- itt megismételjük 34

A következ ábra felsorol náhány, a kommerciális kriptográfiában használatos alapfüggvényt ill. a megnevezéseiket. Van olyan ezek között, amelyet a kriptográfiával kapcsolatban korábban már b vebben tárgyaltunk. Ilyen pl. A DES és az ábrán csak zárójelben jelölt utódja, az AES. Ismer s lehet pl. A DES kapcsán megemlített IDEA is, amely a DES-hez hasonlóan sokrundos, algoritmus és a Zürichi M szaki Egyetemen fejlesztették ki, de mindeddig nem tárgyaltuk részletesebben. A hibrid rendszerek kapcsán említettük a PGP-t is és más tanulmányokból nyilván nem ismeretlen a PKZIP sem. Mégis, a felsorolt transzformációk (algoritmusok) többsége nyilván nem ismert. Meg kell itt említeni, hogy a felsorolás esetleges, mert pl. Az AES pályázat során további olyan titkosítási algoritmusokat is kifejlesztettek, amelyeket itt meg sem említettünk.

TITKOSÍTÁS (Encryption) (Magánügy és bizalmas)

Szimmetrikus kulcsú algoritmusok

Folyamatos titkosítás

RC4 SEAL WAKE A5 PKZIP

Blokk titkosítás

DES 3 DES RC2 RC5 IDEA CAST Blowfish Rijndael (AES)

DIGITÁLIS ALÁÍRÁSOK (Autentikus/Letagadhatatlan) (Az üzenet integritása)

Nyíltkulcsú (aszimmetrikus) algoritmusok

Diszkrét logaritmus

Faktorizáció

DSA ECC Diffie-Hellman (El Gamal)

RSA LUC

Üzenetjellemzõ (Hash) algoritmusok

A nyilvános kulcsok infrastruktúrája (PKI)

PKIX SPKI SDSI PGP DNSSEC

Kulcs menedzsment

MD 2 MD 5 SHA SHA-1 RIPEMD-160

ISA/KMP SKIP Photuris Diffie-Hellman (El Gamal)

A kriptorendszerek módszeres tárgyalása azt igényelné, hogy a következ kben ismertessük az itt megnevezett algoritmusokat. Erre azonban nincsen mód. (Sem hely, sem id , sem magának az Informácótechnika c. tárgynak nem célja, hogy ilyen mélyen foglalkozzék a kriptográfiával.) Ehelyett reprezentatív mintaként bemutatunk itt egy jellemz eljárást, nevezetesen az RSA algoritmust, amely a legels gyakorlatban is bevezetett és máig is használt egyirányú titkosítási transzformáció volt. Az egyéb alkalmazásokat pedig, mint amilyen pl. a digitális aláírás, vagy az információ elrejtése „ártatlannak” látszó más információban (szövegben vagy képben) vagy egy szabványos Hash függvényt, amelyet a digitális aláírásoknál alkalmaznak, az Aszimmetrikus kriptográfia c. segédlet II. részében írjuk majd le a kulcs-menedzsment aktuális problémáinak vázlatos bemutatásával és még néhány kapcsolódó probléma leírásával együtt.

35

El bb azonban a (konvencionális) szimmetrikus és az nyiltkulcsú (vagyis aszimmetrikus) titkosítási módszerek egy-egy blokkvázlaton való ábrázolásával hasonlítsuk össze a két titkosítási módszert. El ször nézzük a konvencionális szimmetrikus titkosítási kriptorendszer blokkvázlatát:

Szimmetrikus (konvencionális) titkosítás András

A

E

Nyílt szöveg

Béla

Azonos kulcsot használnak (osztoznak ugyanazon a kulcson)

Kódolás (titkosítás)

B D

Kódolt (titkosított) szöveg

Dekódolás (megfejtés)

Nyílt szöveg

Persze egy ilyen, egyszerüsített blokkvázlat nem mutathatja meg ennek a titkosítási módszernek sem a jellemz részleteit sem az alkalmazási területeit, sem azt, hogy az alkalmazott transzformációknak milyen tulajdonságokkal kell rendelkezniük. Mégis alkalmas talán az összehasonlításra és arra is, hogy megmutassuk, hogy a tradicionális (történeti) rendszerek mely tulajdonságait hordozzák a legmodernebb alkalmazásaik is.

36

Az aszimmetrikus (un. nyiltkulcsú) kriptorendszerek egyszerüsített m ködési blokkvázlata a következ :

Nyiltkulcsú (aszimmetrikus) titkosítás András

A

Nyílt szöveg 1

2

András elhelyezi a nyíltszövegû dokumentumát egy kétkulcsos páncélkazettába

András bezárja a páncélkazettát Béla nyilvános kulcsával

A páncélkazettát publikus módon továbbítják Bélához

3

4

Béla

és kiveszi bel le a neki szánt nyíltszöveg dokumentumot

Nyílt szöveg

5

B

Béla kinyitja a páncélkazettát a saját titkos (privát) kulcsával

37

Az aszimmetrikus kriptorendszerekben alkalmazott matematikai módszerek nehézségei.

Ha gondosan átvizsgáljuk a kriptográfia szakirodalmát azt találjuk, hogy a módszerek alapköve, alfája és omegája az alkalmazott algoritmusok kérdése. A szakirodalom rengeteg energiát fordít ezekre és arra is, hogy matematikai szempontból precízen megalapozza ezeket az algoritmusokat. Másrészr l láttuk, hogy a modern kriptorendszerek akkor nehezítik meg igazán az illetéktelen megfejt dolgát, ha a kulcs ismerete nélkül gyakorlatilag feltörhetetlenek. Ezt btöbbek közöttb azzal érik el, hogy igenigen bonyolult algoritmusokat alkalmaznak, amelyeknek persze a matematikai alapjai is igen-igen bonyolultak. Ez mind a modern szimmetrikus, mind az aszimmetrikus rendszerekre igaz. Ennek a f iskolai jegyzetnek az a célja, hogy megmutassuk, hogy hogyan m ködnek a kriptorendszerek, vagy legalább is valamilyen fogalmat adjunk a m ködésükr l anélkül, hogy olyan elmélyült matematikai háttérre támaszkodnánk, amelyet a m szaki f iskolai fels oktatásban nem szoktak tanítani. Ki kell, hogy jelentsük azonban, hogy igazán precíz tárgyaláshoz nem lehet ezt a matematikai hátteret nélkülözni és itt els sorban az absztrakt algebrai háttérre gondolunk. E sorok szerz je úgy kisérli meg áthidalni az elmélyült matematikai háttér elkerülését a bonyolult kriptográfiai algoritmusok m ködési leírása kapcsán, hogy a szükséges háttérismeretek közül a legfontosabbakat függelékekben közli, amelyek megtanulása nélkül is követhet a kiválasztott algoritmusok m ködése. Legalább is nagyjából. Nichols professzor szintén a gyakorlati megközelítés híve és a következ két szempontot javasolja a kriptográfiai algoritmusok osztályozására: II. A kriptográfiai algoritmusok osztályozhatók aszerint, hogy mennyire bonyolult a matematikai hátterük. III.

Osztályozhatók továbbá a kriptográfiai funkcióik szerint is.

54

Az els osztályozási szempont szerint három olyan matematikai problémakör van, amelyeket manapság biztonságosnak és hatékonynak tartanak a kriptográfiában. Ezek a következ k:

54

II.

Egésszámok törzstényez kre bontásának problémája (Integer Factorisation Problem: IFP) Ebben a kategóriában az RSA a legismertebb és egyébként is alapvet módszer.

III.

A diszkrét logaritmusok problémaköre (DLP). Ismert alkalmazási köre pl. az Egyesült Államok kormánya által szabványosított digitális aláírási algoritmus (Digital Signature Algorithm: DSA), a Diffie-Hellman kulcs-megegyezési séma,

Algoritmusokat használunk mind a szimmetrikus, mind az aszimmetrikus kriptorendszerekben, de olyan kapcsolódó területeken is, mint pl. a digitális aláírásoknál használt egyedi szövegjellemz k (un. Hash függvények) el állítása, a tömörítési, vagy az információt „ártatlannak látszó” üzenetben elrejt módszereknél. Itt mindezekre az algoritmusokra gondolunk, amelyeket pl. a 37. oldalon bemutatott ábrán nevükön neveztünk. 38

az El Gamal-féle titkosítási és digitális aláírási rendszer és a Schnorr-féle digitális aláírási módszer. IV.

Az elliptikus görbén alkalmazott diszkrét logaritmus problémakör (Elliptic Curve Discrete Logarithm Problem: ECDLP) Közismert alkalmazásai pl. az el z pontban említett DSA-nak az ECDLP megfelel je, amit ECDSA-nak rövidítenek, a Diffie-Hellman kulcs megegyezési sémának az elliptikus görbe analógja (ECDH), továbbá az El Gamal, valamint a Schnorr-féle aláírási rendszerek elliptikus görbe megfelel je. (ECEG ill. ECSS).

Ha valakit nem gy zött volna meg a 35. oldal ábrájának algoritmus-felsorolása arról, hogy messze meghaladná egy f iskolai jegyzet kereteit ezeknek az algoritmusoknak akár csak a vázlatos tárgyalása is, akkor a fenti osztályozás bizonyára indokolja, hogy miért csak mintaként szándékozunk bemutatni egy-egy leginkább jellemz algoritmust. Nichols professzor véleménye szerint a leghatékonyabb kriptográfiai technika ma az ECC elven alapuló rendszereké. Egyrész azért mert az általa nyújtott biztonság ma a legnagyobb, másrészt pedig azért, mert az alkalmazása a számításigény szempontjából hatékonynak mondható. A kriptográfiai funkcionalitás A másik klasszifikáció az algoritmusokat a kriptográfiai szerepük szerint osztályozza a következ képp: II.

Szimmetrikus

III.

Aszimmetrikus

IV.

Az autentikáció (iratokkal való valódiság-igazolás)

V.

Digitális aláírás, Hash függvények, un. szövegkivonatok

rendszereiben való alkalmazásuk ill. alkalmazhatóságuk szerint. Egészen nyilvánvaló, hogy vannak olyan algoritmusok, amelyek a fentiek közül több rendszerben is alkalmazhatók. Ez a klasszifikáció tehát egymást részben átfed osztályokat határoz meg. Az egészszámok faktorizációján alapuló rendszerek. 55

Már többször említettük korábban, hogy Diffie és Hellman 1976-ban fedezték fel a nyiltkulcsú kriptográfia elvét, de az els használható ilyen rendszert Ron Rivest, Adi Shamir és Len Adleman publikálták alig fél évvel Diffie és Hellman publikációja után. Mindhárman az MIT hallgatói voltak akkor. Az neveik kezd betüi után nevezték el 56 ezt a titkosítási módszert RSA módszernek . Kés bb a nyiltkulcsú titkosítási 55

Nem tudni, miért Merkle nevét gyakran elfelejtik megemlíteni. Talán azért mert Diffie és Hellman a Stanfordon dolgoztak, míg Merkle egy másik ugyancsak híres egyetemen Berkeleyben.

56

A magyar olvasónak talán kissé furcsa is, hogy ez az azóta világhír
módszerek továbbfejlesztésére céget is alapítottak RSA Laboratories néven, amelynek ma is létez webkiköt jén ma is sok érdekes információt találhat az érdekl d böngész . Az RSA rendszer biztonsága Az RSA a legismertebb azok közül a rendszerek közül, amelyek biztonsága az egészszámok faktorizációján alapul. (Integer Factorisation Problem = IFP) Ezt a problémát a következ képp fogalmazhatjuk meg: Adott egy n egészszám, amely két nagy prímszám szorzata. Jelöljük ezeket a tözsszámokat p-vel és q-val. Ekkor tehát n=p×q Az RSA nyilvános kulcs egy (n,e) párból áll, amelyben 1 ? e ? n-1 és n a fenti két 57 nagy prímszám szorzata. Széles körben úgy gondolják, hogy az RSA rendszer feltöréséhez meg kell keresni az n szám törzstényez it. Az a helyzet azonban, hogy egy n szám tözstényez i megkeresésének (=faktorizációjának) a problémáját több, mint 300 éve tanulmányozzák és azóta nem találtak semmilyen szuperhatékony ,módszert a prímfaktorok meghatározására. Ennél a titkosítási módszernél „mindössze” arról van szó, hogy n-et elég nagyra kell választani ahhoz, hogy a faktorizációja gyakorlatilag reménytelen legyen. Néha túlzásnak t nik, de manapság „rövid idej ” biztonságnak tekintik, ha n értéke egy legalább 150 jegy decimális szám, aminek a bináris megfelel je egy kb. 500 bites bináris szám. Az ilyen titkosítási rendszerek feltörésére célhardver-berendezéseket „szokás” építeni (lásd a DES Crackert a DES c. fejezetben) és ezért 1998 óta a 1028 bites bináris kulcs (vagy az ennek kb. megfelel 300 digites decimális szám) jobb alternatívának t nik. Az RSA rendszer implementációja Az RSA és az egészszám-faktorozáció családjának más tagjai mind titkosításra, mind digitális aláíráshoz alkalmazhatók. El ször is a modulus-aritmetikát kell definiálni ahhoz, hogy az itt említett alkalmazási folyamatokat leírjuk. A modulus-összeadás és a modulus-szorzás majdnem úgy m ködik, mint a mindennapi gyakorlatban megszokott összeadás és szorzás. Az egyetlen különbség az, hogy az eredményt a m velet maradéka jelenti (mármint az eredményt osztva az n modulussal). Persze minderr l ennek a fejezetnek a korábbi pontjaiban már szóltunk. Ha az Olvasó történetesen nem emlékezne rá, akkor ajánljuk az II. Függelék (különösen annak végén lév tételek az 52 . oldalon), valamint a II. Függelék áttekintését. Ezért az eredmény mindíg a 0-tól az n-1-ig terjed számtartományba esik és (a m veleteket alkalmas módon definiálva) túlcsordulás nem fordulhat el . (Lásd a 12. oldalon mondottakat is!) A „mod n” kifejezést mindegyik számítás után odaírjuk, hogy jelölük, hogy ott modulus aritmetikáról van szó. Ennek a modulus aritmetikának kulcsszerepe van mind a három kriptorendszer tipusnál, ahogyan azt már a 12. oldalon leírtuk. (Ti. azt, hogy miért.) 57

Figyeljünk fel arra, hogy, hogy ez a gondolatmenet igen sok részletében emlékeztet arra, amit a knapsack titkosítás –pontosabban annak algoritmusa- során már megmutattunk. Itt emlékeztetünk arra, hogy egyáltalán nem véletlen, hogy némely alapmódszerek (mint pl. a modulusm
Amikor az RSA rendszert akár titkosításra, akár digitális aláírásra használjuk, modulo n hatványozást kell végrehajtani. Tegyük fel, hogy egy m szám egy üzenetet jelent m pedig 0 és n-1 közé esik: 0 ? m ? n-1. Ekkor egy x

m (mod n) x

hatványozást kell kiszámítani valamilyen adott x-re úgy, hogy m végül is a [0, n-1] tartományba transzformálódik. Ez a modulus-hatványozás domináns szerepet játszik az RSA rendszerben végrehajtandó transzformációkban. Következésképpen ennek x az m mod n m veletnek az id igénye az, ami lényegében meghatározza az RSA kriptorendszer számítási id igényét. Más szóval az RSA rendszer (és ugyanehhez a családhoz tartozó egyéb rendszerek) biztonsága az egészszámok faktorizációjának bonyolultságától függ, és ugyanezeknek a rendszereknek a m ködési sebessége attól függ, hogy milyen gyorsan képesek elvégezni a mod n hatványozást. Ami a törzstényez k megkereséséhez szükséges algoritmus (azaz a feltörés) id igényét illeti érdekes, hogy 1985 óta a leggyorsabb faktorizáló algoritmus az elliptikus 58 görbe fektorizációs elvet követi, amelynek a futási ideje attól függ, hogy milyen nagy számok a keresett törzstényez k. Ezért hajlamos arra, hogy el ször az adott n szám kisebb prímfaktorait találja meg. 1995-ben Andreas Mueller (Saarvidéki Egyetem) közzétette, hogy ezzel a módszerrel sikerült egy 99 decimális számjegy ( 329 bites) összetett szám egy 44 digites ( 147 bites) prímfaktorát meghatároznia. A számítást egy munkaállomás-hálózaton végezte el, amelynek összesített számítási sebessége 60 MIPS volt. Jóllehet a számítási id nem ismert pontosan az kb. 2-3 nap lehetett. Még ugyanebben az évben egy 135 decimális számjegy összetett számnak egy 47 digites prímfaktorát is sikerült az ECM-mel meghatározni egy másik kutatónak. A következ táblázat megmutatja, hogy MIPS×években mérve hogyan fejl dött az integer faktorizáció.

58

Elliptic Curve Method: ECM, amelyet Hendrik Lenstra Jr. publikált 1985-ben, tehát több, mint tíz évvel azel tt, hogy az els nyiltkulcsú titkosítási algoritmust kitalálták. Diffie és Hellmann ECDH módszerének feltalálásakor tehát már egy évtizede ismert volt ez a faktorizációs módszer és valószín
Dátum (év)

n decimális számjegyeine k száma

n bitszám a

MIPS × évek szám a

1984

71

236

0,1

1988

106

352

140

1993

120

399

825

1994

129

429

5000

1995

119

395

250

1996

130

432

750

Az érdekesség kedvéért megjegyezzük, hogy az ECDLP módszeren alapuló titkosí50 tásoknál a 400 bit körüli kulcshoszúság esetén a feltörési id meghaldja a 10 12 MIPS×évet, de még a sokkal rövidebb 160 bites kulcs esetében is majdnem 10 MIPS×év. Nem véletlen, hogy ma az ECDLP titkosításokat tartják a leghatékonyabbnak. Az RSA algoritmus Az RSA módszer blokk-titkosítással dolgozik. Jelölje M a nyíltszöveg-blokkot és C a neki megfelel titkosított szövegblokkot (a ciphertext rövidítéseként). Ezekkel

C = Me (mod m) M = Cd (mod m) = (Me )d (mod m) = Med (mod m) Mind az üzenet küld jének, mind az üzenetet fogadó címzettnek ismernie kell m értékét. A küld ismeri e értékét, de d értékét csakis az üzenet legális címzettjének szabad és kell ismernie. Figyeljünk fel arra, hogy a dolog sokban hasonlít a korábban részletesen tárgyalt knapsack titkosításra. Az RSA rendszer tehát olyan titkosítási rendszer, amelyben a nyilvános kulcs:

KNy = [e, m] A titkos privát kulcs pedig

KT = [d, m]

42

A rendszernek ki kell elégítenie a következ három követelményt: II.

Feltétlenül szükséges, hogy létezzen olyan [e, d, n] számhármas, amelyre igaz, hogy

Med ? M (mod m); minden M < m -re d

e

III.

Mind C (mod m) -nek, mind M (mod m)–nek könnyen kiszámíthatónak kell lennie minden M < m esetén.

IV.

Ismert e és mesetén számítástechnikailag valószín tlennek kell lennie annak, hogy ezekb l d kiszámítható legyen.

Az RSA algoritmus esetében ugyanazt a fogalmat használjuk egy természetes szám valamely m modulusra vonatkoztatott inverzeként, mint amit a knapsack titkosítás kapcsán már alkalmaztunk. Emlékeztet ül: definició szerint az a és b egészek egymás inverzei valamely m' modulusra nézve, ha szorzatuk a modulussal 1 maradékot ad, azaz: ab = 1 (mod m') Kiindulásul válasszunk két, meglehet sen nagy, egymástól különböz (p1, p2). Szorzatukat

prímszámot

m = p1,p2 és ú.n. Euler-függvényüket (m) = ( p1 ,p2) = (p1 -1)( p2 -1) használni fogjuk az algoritmus során. Válasszunk egy, kell en nagy, e számot nek:

59

úgy, hogy e és (m) relatív prímek legye-

(e, (m)) = 1

59

Azért jelöljük e-vel, mert a rejtjelzéshez (encription) fogjuk használni, az alább bevezetend d számot pedig a megfejtéshez (decription) 43

Képezzük továbbá az így választott e érték d inverzét a ( m) modulusra nézve, azaz ed = 1 (mod (m)) Az inverz nem mindíg létezik. Ha azonban e és biztosítja, hogy az inverz létezzen.

( m) relatív prímek, akkor ez

Az ilyen módon megválasztott e és m értékeket közzétesszük, míg a d, p1 és p2 értékeket titokban tartjuk és (m)-et sem tesszük közzé. Ebben az értelemben a publikus kulcs az (e,m) számpár, míg a privát kulcs a (d, p1, p2) számhármas. A kódolás és dekódolás m velete a következ képpen definiált: Egy adott x üzenet (0 < x < m) kódolására az y := xe (mod m ) függvényt használjuk, míg a dekódolásra az x := yd (mod m ) leképezést. Bebizonyítható, hogy az így definiált kódolás és dekódolási m veletek valóban egymás inverzei, azaz a kódolt üzenetet dekódolva valóban az eredeti szöveget kapjuk vissza. Hogy az elmondottakat egy egyszer példán illusztráljuk, válasszuk p1 és p2 értékeinek a 17 és 19 prímszámokat. Ezek a prímszámok sok nagyságrenddel kisebbek a gyakorlatban alkalmazottaknál, de már elegend en nagyok ahhoz, hogy a teljes 8bites kiterjesztett ASCII karakterkészlet kódolható legyen, ugyanis m = p1p2 = 17×19 = 323 > 255 (A kétbyte-os UNICODE karakterkészlet kódolásához természetesen ennél jóval nagyobb értékeket kellene választanunk). A kódoláshoz válasszuk az e =11 értéket. A dekódoláshoz képezzük ennek inverzét a (p1 -1)(p2 -1) = 288 értékre mint modulusra: -1

d = 11 = 131 (mod 288) (Itt a kitev ben szerepeltetett "–1" jel nem negatív hatványt jelöl, hanem az inverzképzésre vezettük be ezt a jelölést, amint már a knapsack titkosításnál is tettük.) Nyilvános kulcsként közzétesszük a (11, 323) számpárt, míg a (131, 17, 19) számhármast titokban tartjuk. Kódolási példaként válasszuk egy tetsz leges karakter ASCII kódját, legyen az például a „@” karakter (ASCII 64). Titkosítsuk ezt az üzenetet most a nyilvános kulccsal. (Megfejteni majd a privát kulccsal fogjuk.) A titkosítás eredménye ekkor a 64

11

mod 323 = 106

érték lesz. A titkos üzenetet a privát kulcs segítségével dekódolhatjuk: 106

131

mod 323 = 64

Az utóbbi hatványozási m veletet látva jogosan merülhet fel bennünk, hogy elvégezhet -e egyáltalán a hatványozás nagy számok esetében és ha el is végezhet a hatványozás, elvégezhet -e elfogadható id n belül. 44

Szerencsére mindkét kérdésre igenl válasz adható. Az els kérdésre a megoldást a modulus használata adja. Ugyanis igen könnyen megmutatható, hogy a hatvány osztási maradéka az osztási maradék hatványa (pontosabban annak osztási maradéka. Lásd az II. Függelékbe a 52. oldalon mondottakat is). Emiatt a hatványozás lépéseiben rendre csak az osztási maradékokkal továbbszámolva biztosítható, hogy a hatványozás részeredményei soha se n jenek minden határon túl. A hatványozás m veletigénye is viszonylag alacsony szinten tartható. Annak ellenére, hogy a m velet reális id n belül elvégezhet , nem lesz kifejezetten „olcsó”. Éppen ezért a gyakorlatban az RSA algoritmust nem feltétlenül alkalmazzák a teljes üzenetre. Általános gyakorlat, hogy az üzenet kódolására használt privát (szimmetrikus) kulcsot küldik el az RSA algoritmussal titkosítva, majd a konkrét üzenetet már az átküldött kulccsal kódolják, illetve dekódolják. (Lásd a hibrid rendszerekr l mondottakat.) Mit l lesz az RSA algoritmus gyakorlatilag visszafejthetetlen? Figyeljünk fel arra, hogy az inverz képzéséhez nem a prímek szorzatát, hanem Euler függvényüket használtuk. Ahhoz, hogy az (e,m) publikus kulcs ismeretében meghatározható legyen a privát kulcs d értéke, el tte meg kell határozni a p1 és p2 értéke60 ket, ami pontosan az m szám prímfaktorizációját jelenti. Csakis a p1 és p2 prímek ismeretében határozható meg a (p1-1)(p2-1) szorzat, ami viszont az inverz képzés200 hez szükséges. Ennek a faktorizációnak a számításigénye 10 nagyságrend m választása esetén 100 ezer években mérhet még a mai számítástechnikai technológiát feltételezve is. Joggal merülhet fel az a kérdés, hogy ha az RSA módszer a nyílt szöveg egyes karaktereit külön-külön képezi le a titkosított szöveg karaktereire, akkor a kulcs ismerete nélkül, a nyílt szöveg statisztikai szerkezetéb l is megfejthet ez a megfeleltetés. Ezért a titkosítás el tt tenni kell valamit a nyílt szöveggel, ami elrejti annak a statisztikai tulajdonságait. Ehhez elegend pl. a nyílt szöveget tömöríteni, blokkonként titkosítani, alkalmazni a láncolás elvét, stb. Persze, ha egy hibrid rendszerben csak a szimmetrikus titkos kulcsot kódoljuk az RSA módszerrel, akkor mindezekre nincs szükség. Az II. Függelékben ismertetünk egy demo programot is ehhez az eljáráshoz.

60

A prímfaktorizáció nehézségeir l írtunk már és említettük, hogy az ismert módszereknél a megoldás lépéseinek száma növekszik a prímfaktorok nagyságával. Ezért a gyakorlatban az RSA módszer alkalmazásakor mind a p1, mind a p2 prímszámot az igen nagy ( 10100 nagyságrend<) prímszámok közül választják és lényeges az is, hogy az m modulusnak csak két prímfaktora legyen. 45

Összefoglalás és köszönetnyílvánítás. Ennek az írásnak az el zményeként jelent meg 2000 tavaszán a szerz DES (Data Encryption Standard) c. jegyzete, amelynek ma inkább a Szimmetrikus kriptorendszerek címet adná, és mindenesetre az aszimmetrikus rendszerek itt megírt anyagát hivatott valamilyen módon el készíteni. Ez a jegyzetrész azt szeretné bemutatni, hogy milyen alapelveken és hogyan m ködnek az aszimmetrikus kriptorendszerek. Jóllehet e rendszerek alapelvét csak 1976-ban fogalmazták meg el ször, ma, 2000ben, már többféle rendszer is m ködik a gyakorlatban. Több közös jellemz jük is van, és mindegyikre igaz, hogy az elvi, matematikai hátterük meglehet sen bonyolult. Ezért nem könny a matematikai háttér nélkül bemutatni e rendszereket. Ebben a jegyzetben egyáltalán nem törekedtünk teljességre. Az alapelvek többnyire verbális megfogalmazása mellett mintaként mutattuk be az un. knapsack titkosítás m ködési elvét, amely a végletekig leegyszerüsített formában akár zsebkalkulátorral is demonstrálható. Erre a módszerre alkalmazási algoritmust is megfogalmaztunk s azt is annyira leegyszerüsítve, hogy a m ködés demonstrációjára alkalmas ugyan, de komolyabb kriptográfiai biztonságot nyújtó alkalmazásokra már nem. A knapsack titkosítást egyébként éppen az egyszerüsége miatt nem igen alkalmazzák a gyakorlatban. A matematikai háttér kérdéseit igyekeztünk az alapszövegt l elkülönítve tárgyalni. Esetenként a függelékekben, de még azokban sem olyan igényességgel, ahogyan azt egy precíz matematikai leírás megkövetelte volna. Bocsássák meg ezt a matematikus olvasók a szerz knek. Az els és mindmáig elterjedten használt aszimmetrikus titkosítási algoritmus az RSA módszer, jóllehet ma már nála nagyságrendekkel nagyobb biztonságot nyújtó kriptográfiai rendszer is létezik, pl. a Diffie és Hellmanról elnevezett DH algoritmus. Nem vállalkozhattunk arra, hogy az utóbbit is bemutassuk itt, de a knapsack titkosítás után az RSA titkosítás m ködésér l is igyekeztünk rövid áttekintést adni és ehhez is készült demonstrációs algoritmus. A matematikai háttéranyagokat igyekeztünk a szöveg f többnyire a függelékekben felvázolni.

vonulatától elválasztva,

Az aszimmetrikus kriptográfia kiterjedt alkalmazásairól és az azokhoz kapcsolódó problémákról gyakorlatilag szinte semmit sem írtunk ebben a jegyzetrészben. Mindezekr l egy kés bb megírandó anyagban szándékozunk majd szólni, amelynek az itt alkalmazott munkacíme (egyel re) Aszimmetrikus kriptográfia II. (Az elektronikus aláírás, a szövegtömörítvény, a kulcs menedzsment, az információ rejtése, az elektronikus vízjel, stb.) Egyel re nem áll szándékunkban az un. hibrid rendszerekr l írni, mert pl. a PGP-r l már jelent meg könyv magyar szerz tollából. Mind az Intézetben született írott el zmények, mind a hallgatók által készített néhány kapcsolódó projekt, mind a demo programok, mind az egyéb aktuális oktatási anyagok megtalálhatók az SzGTI honlaján keresztül a http://szgti.bmf.hu/~mtoth/segedanyagok elérési úton az ott hozzáférhet további mappákban.

46

A magyar szerz sokmindenkinek tartozik köszönettel. El ször is a BMF KKVFK Számítógéptechnikai Intézete vezet ségének, amely nem csak a kriptográfia felé irányította figyelmét, hanem módot és lehet séget is biztosítottak arra, hogy elmélyedjen e területen. A vezet k közül is els sorban dr. L rincz Péter f iskolai tanár igazgatónak és dr. Györök György f iskolai docens igazgatóhelyettesnek kell köszönetet mondanom, akik szakmai szempontból is folyamatosan támogatták a munkám. Rajtuk kívül az Intézet több munkatársától is segítséget kaptam. Közülük Fellegi József és Fellegi Tíor adjunktusoknak tartozom köszönettel konzultatív segítségükért, értékes gondolataikért, valamint Makó Margit adjunktusnak az anyag gondos átnézéséért és javításáért. Köszönet illeti Tóth Gergely és Tóth Zsolt programozókat, akik gratis elkészítették és dokumentálták a demo-programokat. Végül, de talán legels sorban köszönettel tartozom Randall K. Nichols profeszszornak (George Washington University), akit l számos forrást kaptam minden ellenszolgáltatás nélkül és akivel szoros munkakapcsolatban voltam mind a korábbi DES jegyzet, mind ennek az anyagnak a megírása során.

47

II.

FÜGGELÉK A lineáris helyettesítés matematikai háttere

Egy lineáris

61

helyettesítés nem más, mint egy speciális poligrafikus

62

helyettesítés.

Nevezetesen arról van szó, hogy a lineáris helyettesítés esetében a nyílt szöveg minden egyes blokkjához egyetlen jelsor (pl. egy többjegy szám) tartozik a titkosított szövegben is. Ez a nyíltszöveg szókészletének halmaza és a titkosított szimbólumok halmaza között egy egyirányban egyértelm (injektív) leképezést hoz létre: n

m

U:V ›W

63

Ez a leképezés a szimmetrikus kriptorendszereknél determinisztikus . Amint a DES (titkos kulcsos) kriptorendszer leírásakor megemlítettük, az ilyen leképezéseknél a leképezés inverze is létezik. A titkos kulcsos rendszereknél az inverz transzformáció létezése alapvet feltétel volt, de ha jobban belegondolunk, ez teljesen általános esetben egyáltalán nem nyilvánvaló követelmény. Más szóval követelmény ugyan, n hogy a legális címzett aránylag könnyen vissza tudja fejteni a V –beli nyíltszöveget a m W –beli ciphertextb l, de miért is kellene ezt feltétlenül a titkosításhoz (=encryption) -1 használt f(x) transzformáció matematikai inverz függvényével f (x)-szel tennie? Ha pedig valamilyen más transzformációt használ a megfejtésre (=decryption), akkor annak a kulcsa is más lehet, mint a titkosításé. Ezzel aztán adott is az aszimmetrikus (kétkulcsos) kriptorendszerek egyik alapötlete. Persze ma, amikor már léteznek aszimmetrikus kriptorendszerek, nagyon egyszer nek látszik ez a felismerés, mégis évszázadokon keresztül kellett fejl dnie a kriptográfiának ahhoz, hogy Diffie, Hellman és Merkle 1976-ban felismerje az aszimmetrikus kriptorendszerek létrehozásának alapelvét. A sors iróniája talán, hogy az els gyakorlatban máig is használt ilyen aszimmetrikus rendszert mégsem k, hanem az MIT három hallgatója. Ron Rivest, Adi Shamir és Leon Adleman találta fel Diffie, Hellman és Merkle publikációja után és az inventorok nevének kezd betüi nyomán nevezik máig is RSA rendszernek.

61

A geometriai megfelel jével megnevezve: affin

62

Itt egy csomó egymással összefügg fogalomról van szó, amelyeket tulajdonképpen a titkosírások történeti fejl dése során vezettek be és kés bb matematikailag precízen megfogalmaztak. A következ oldalon az “Álljunk meg egy szóra...” keretes megjegyzésnél olyan röviden foglajuk össze ezeket, amennyire csak lehet, de ehhez fel kellett adni a matematikai precizitás igényét.

63

Arto Salomaa telefonkönyves titkosítási példája jól szemlélteti, hogy a : Vn › Wm leképezésnek nem kell feltétlenül determinisztikusnak lennie, mint ahogyan az aszimmetrikus kriptorendszereknél sokszor nem is az. 48

Álljunk meg egy szóra az itt alkalmazott fogalmak kedvéért. Vocabulary= ábécé, Word-set= szókészlet, chiffre, encoding, enciphering, cipher, encipher, kód, cipher, crypt, monoalfabetikus, polyalfabetikus, singleton, kulcstér, monografikus, polygrafikus, bigram, trigram, tetragram, bifid, trifid Jelölje V a nyíltszöveg (véges) karakterkészletét (nem egészen következetesen a Vocabulary rövidítéseként) és W az ebb l megszerkeszthet szavak (Words) készletét. Legyen az n elem< ábécé i-edik eleme V(ni) és az m elem< szókészlet i-edik eleme W(mi) . A V(ni) W(mi) leképezést egy kódtáblával lehet definiálni. Egy adott kódtáblát gyakran neveznek kódnak vagy cipher-nek (franciául chiffre). A titkosítási lépést ezek után encoding-lépésnek, vagy enciphering- lépésnek is nevezik. Mindazonáltal nincs éles határ a cipher, az encipher, a kód és még általánosabban a kódolás (enciphering) , a dekódolás (deciphering) és az ezekb l származtatott kifejezések között. Lényegében ezeknek a kifejezéseknek a történetileg kialakult használata határozza meg, hogy mir l is van szó egy adott történeti pallanatban. W(mj) elemeinek megnevezésére egyaránt használatosak a kód, a ciphertext és általában a crypt megnevezések. Egy = [ i1, i2, i3,...] kódolást véges módon generálhatunk egy M rendszerb l. Ez a kódolás monoalfabetikus, ha egyetlen kódolási lépést (ti. ábécét) használ. Máskülönben pedig polyalfabetikus. Ha M egy un. singleton, (azaz egyetlen szimbólum/karakter: \ = 1), akkor minden olyan kódolás, amit M segítségével generálunk monoalfabetikus. Ez a megközelítés F.L Bauert l származik. Más szerz k (pl. Randall K. Nichols) a jelölésrendszerükben is hangsúlyozzák, hogy egy dolog a titkosítási módszer (itt M) és más dolog, hogy éppen milyen kulcsot alkalmazunk hozzá. Itt, ti, Bauernél az kulcstér i1, i2, i3,... elemei jelentik a különböz kulcsok alkalmazását ugyanannál az M titkosítási módszernél. Bauer „nagyon matematikus” megközelítése lényegében általánosabb és ezért megengedi, hogy ugyanannál a titkosítási módszernél nagyon különböz , esetleg ciklikusan sohasem ismétl d véletlen kulcsokat használjunk. Egy véges módon generált titkosítást monografikusnak nevezünk akkor, ha a titkosítás valamennyi lépésében használt ni =1.Ha nem ez a helyzet, akkor polygrafikus. Valójában sokkal egyszer
49

Visszatérve a leképezések fogalomkörébe van tehát egy a nyíltszöveg ábécéjét tartalmazó véges V halmaz és a titkosított szöveg ábécéjét alkotó W halmaz és, általános esetben, e két halmaz nem azonos. A V ábécéb l alkotott szavakat az n elem n V halmaz tartalmazza, a W ábécé elemeib l alkotott cyphertext szavakat pedig az m m elem W halmaz. m és n aránylag nagy, de minden gyakorlati esetben valamilyen módon mégis korlátozott számok. Nem szükséges, hogy n=m legyen. m-nek azonban vagy egyenl nek, vagy nagyobbnak kell lennie n-nél. Ha m=n, akkor a n m U : V › W leképezés kölcsönösen egyértelm . Egyébként azonban az U leképezés n m V elemeit W valódi részhalmazaira képezi le és ezeknek a részhalmazoknak diszjunktaknak kell lenni ahhoz, hogy a visszafelé történ leképezés is egyértelm legyen, ami viszont az egyértelm megfejthet ség feltétele.

Az n elem Vn halmaz

Injektív leképezés

Az m elem Wm halmaz

50

Az ábra is szemléltetni igyekszik, hogy mir l van szó és nagyon szemléletes példa erre a leképezésre Arto Salomaa telefonkönyves titkosítási példája. A gyakorlati kriptorendszerekben persze más-más leképezést alkalmazunk és egy leképezés-tipuson belül is kulcsfügg a leképezés. Talán felesleges is hangsúlyozni, hogy a fenti ábra a nyíltszöveg szavait képezi le a titkosított szöveg szavaira. Blokk-titkosítás esetén a nyíltszöveg blokkjainak a leképezésér l van szó. Lépjünk most vissza még egy szintet és foglalkozzunk a nyíltszöveget alkotó V és a 64 65 ciphertextet alkotó W ábécékkel. Ezek mindegyike véges halmazt alkot (és nem szerepelnek az el bbi halmaz-diagramokon). Tekintsük az ábécéket rendezett halmazoknak, amelyekben mindegyik betünek van 66 megel z (el d) és t követ (utód) betüje . A „normál” latinbetüs ábécében pl. a „c” betü el dje a „b” betü, utódja pedig a „d” betü. Képzeljük el továbbá, hogy a saját farkába harapó kígyó módjára mindegyik ábécé utolsó betüjének utódja ugyanannak az ábécének a legels betüje és ekkor nyilvánvaló, hogy mindegyik ábécé legels betüjének el dje ugyanannak az ábécének a legutolsó betüje. Ennek a tulajdonságnak a hardver megvalósítása (különösen bináris rendszerekben) nagyon egyszer en megoldható egy lineáris, visszacsatolt léptet regiszterrel. Már a legegyszer bb helyettesítéses kriptorendszerek egyikében (nevezetesen a Caesar-féle titkosításnál alkalmazott Caesar-kerékkel) is megvalósították ezt a fajta ábécét. Definiáljuk ezek után az így elképzelt ábécéken az összeadást mod N összeadásként (ahol N az adott ábécé betüinek bés egyéb jeleinekb a száma), ami pl. két, 67 egymáshoz képest elforgatható betükerékkel igen könnyen kivitelezhet . Nagyon könnyen belátható, hogy ez az összeadás meg rzi a betük egymáshoz viszonyított sorrendjét és a 0-tól N-1-ig terjed maradékosztályokba képezi le valamennyi összeadás eredményét függetlenül attól, hogy hány tagú az összeg. A V-beli és a W-beli összeadások megfeleltethet k e maradékosztályoknak. Kissé elvont ugyan, de kés bb hasznos lesz ha formálisan is hivatkozhatunk az itt említett leképezésre. Jelöljük ezt -vel. Eszerint tehát a leképezés

x,y

ZN :

(x+y) = (x) + (y)

64

Sem ez a fogalomkör sem a jelölésrendszer nem idegen azoknak, akik foglalkoztak már valamennyit a formális nyelvekkel és az absztrakt automatákkal, de ezeknek az el tanulmányoknak a hiányában is megérthet , hogy mir l van szó. Monoalfabetikus rendszerekben éppenséggel ugyanazt az ábécét használja mind a nyíltszöveg, mind a titkosított szöveg. Itt azért különböztetjük meg ezeket az ábécéket, mert az általános esetet kívánjuk tárgyalni.

65

Ez persze nem mondható el ezekb l az ábécékb l alkotott szavak halmazaira (tehát Vn és Wmre), ha a szóhosszúság nem korlátozott, de ebbe itt nem kívánunk belemenni.

66

Az angol terminológiában az el d jelölésére a „predecessor” szó rövidítéséb l a „pred” el tagot, az utód jelölésére pedig a „successor” szó rövidítéséb l a „succ” el tagot használják.

67

Pontosan ezt teszi a Caesar kerék ill. a De Vigenere-féle titkosítás alapváltozata is. 51

ahol ZN egy N elem halmazt jelöl. Esetünkben tehát mind V-t, mind W-t jelölheti. Szavakkal megfogalmazva ez a tétel azt jelenti, hogy két szám (mod N) összegének a maradékosztálya megegyezik a számok 68 (mod N) maradékosztályainak összegével. A szorzás m veletét ismételt összeadásként értelmezve már közvetlenül következik, hogy

x

ZN :

(x+x+... +x) = (x) + (x)... ... + (x) = (k×x) = k × (x)

azaz ha egy x számot (mod N) szorzunk egy k számmal, akkor a szorzás eredménye 69 x maradékosztályának a k-szorosa. (Mivel a szorzat tényez i felcserélhet k, ugyanez k-ra is igaz.) Az utóbbi tétel akkor érdekes igazán, ha az x egészszámot saját magával szorozzuk, azaz hatványozzuk. A fentiek szerint ugyanis x-nek tetsz leges k-adik (egész) hatványa ugyanabba a maradékosztályba 70 tartozik, mint x maradékosztályának a k-adik hatványa. Tehát

(xk) = (x)k Mivel a maradékosztályok mind a 0-tól (N-1)-ig terjed tartományba esnek, ezért az x egészszám tetsz legesen nagy (mod N) hatványa sem okoz túlcsordulást a számítások során. (Pl. ha a Horner formulát használjuk a hatvány kiszámítására.) Csak a teljesség kedvéért jegyezzük meg, hogy algebrai terminológiával ZN egy gyürü. Ha N prímszám akkor, és csakis akkor ZN egy test, méghozzá a GF(N) Galois test. Az aszimmetrikus kriptográfiában azonban nem kell N-nek feltétlenül prímszámnak lennie, de az utóbbi esetben a (mod N) m veletek helyett más, bonyolultabb csoportm veletekre van szükség.

68

Pl. legyen N=7 és válasszuk a 8-as és a 9-es számot. Ekkor (8) = 1 és (9) = 2. (8+9) = (17) = 3 = (8) + (9) mert 17 = 2×7 + 3.

69

Az el bbi számokkal: (8×9) = (72) = 2 = (8) × (9) mert 72 = 10×7 + 2.

70

Pl. 8-at hatványozva: (82) = (64) =12 = 1 mert 64 = 9×7 + 1, de (92) = (81) = 22 = 4 mert 81 = 11×7 + 4 A tétel folyománya viszont, hogy ha valamely N modulus esetén egy x szám az 1 maradékosztályba esik, akkor x-nek tetsz leges hatványa is az 1 maradékosztályba esik. 52

II.

FÜGGELÉK Az m modulusra és a t szorzóra valamint az utóbbi inverzére vonatkozó néhány hasznos tétel.

Bizonyítás nélkül (de az II. Függelék végére is hivatkozva) közöljük, hogy ha az N modulus prímszám, akkor 0 ? t ? (m-1) -1

egészszámhoz tartozik egy olyan t egész, hogy -1

t×t

1 (mod m)

azaz ha a modulus prímszám, akkor a képtartományban lév minden egészszámnak létezik inverze. ( Ebben az esetben a képtartomány algebrai értelemben egy GF(m) számtest.) Mint említettük azonban, az aszimmetrikus kriptográfiában nem feltétlenül kell a választott modulusnak prímszámnak lennie. Ha a modulus (és/vagy a t szorzó) nem prímszám, akkor t-nek akkor, és csakis akkor létezik inverze ha t és m legalább relatív prímszámok. Technikai okokból –bináris rendszerekhez- gyakran választják a modulust úgy, hogy az 2-nek egész (ti. k-adik) hatványa, vagy annál 1-gyel kisebb szám legyen. Tehát k

k

m = 2 vagy m = 2 -1 Ezzel analóg módon pedig decimális rendszereknél k

k

m = 10 vagy m = 10 -1 k

Bináris esetben, ha m = 2 akkor a számítás eredménye közvetlenül kinyerhet a processzor akkumulátorának alsó feléb l. k m = 2 esetében csak a páratlan számoknak létezhet inverzük. k m = 2 -1 esetén pedig a nem prímszám modulusokat ajánlatos mell zni.

53

III.

FÜGGELÉK A Knapsack titkosítás algoritmusa.

Ez a függelék azt példázza, hogy ha egy kriptográfiai módszer (mint amilyen pl. a knapsack titkosítás) nem is látszik túl bonyolultnak, az azt megvalósító algoritmus megvalósításakor mégis nagyon sok mellékkörülményre kell tekintettel lenni. Egyúttal megoldott példa is az ehhez hasonló projekteken dolgozó hallgatók számára. Az algoritmus 3 rutinból áll, amelyek általában külön-külön futnak, de használják egymás egyes részeit. Ezeknek a rutinoknak a nevei a következ k: IV.

Kulcs-generálás Knapsack titkosításhoz

V.

Titkosított szöveg (ciphertext) el állítása adott publikus kulccsal

VI.

Titkosított szöveg megfejtése saját privát kulccsal

A titkosítási algoritmus feltételezi, hogy maga a számítógép 1-1 (egyenként nyolcbites) byte-ot használ mindegyik karakterhez és ezért 8 bites kóddal számol. Egyébként a karakterkód kétszerese adja meg az un. blokk-hosszúságot a titkosításhoz. Ezt a blokk hosszúságot n-nel jelöltük a következ kben. (Itt, ebben a demo programban értelemszerüen páros szám.) VII.

Kulcs generálás Knapsack titkosításhoz.

A bemenetek (amelyeket a program használója ad meg, de bizonyos ellen rzéseket végre kell hajtani az adatokon). n:

Pozitív egész, amely a továbbiakban egy vektor komponenseinek a számát határozza meg, továbbá n jegy bináris számokban a számjegyek számát is. Ellen rizni kell, hogy 1-nél nagyobb pozitív egészszám-e. Az el z ekben mondottak alapján szükségképpen páros szám és ha a karakterkód 1 byte, akkor ebben az alkalmazásban n = 16.

A’’

Egy n komponens sorvektor , amelyben a komponensek pozitív egész72 számok és un. szupernövekv sorozatot kell, hogy alkossanak. A sorozat tagjait (pozitív egészeket, amelyek valószín leg nem növekednek 5 jegy decimális számoknál nagyobbra) a program használója adja meg. Hasznos, ha az A’’ vektor betáplálásakor a program kijelzi, hogy b hány tagot adott meg addig a felhasználó b mennyi az addig megadott tagok összege b kérje a következ tagot mindaddig, amíg a felhasználó be nem fejezi

71

71

Tulajdonképpen csakis azért nevezzük ezt (és a kés bbiekben A-val jelölt sorozatot) sorvektornak, mert számít, hogy a komponensek bamelyek pozitív egésszámokb milyen sorrendben vannak felsorolva. A vektor-jelleg kés bb kihasználható, ha az alkalmazott programnyelv egyszer<en tud egy sorvektort egy oszlopvektorral összeszorozni (skalárszorzatról van szó).

72

Pozitív egészekb l álló szám-sorozatot akkor mondunk szupernövekv nek, ha bármelyik tagja nagyobb, mint az azt megel z valamennyi tag összege. 54

A’’ összes tagjának a megadását. Ha olyan tagot ad meg, amely nem felelne meg a szupernövekedés feltételének, akkor azt a program ne fogadja el, s kérjen nagyobb számot, mint az el z összes tag összege. Csak a továbbiak kedvéért jelöljük e sorozat tagjait ai-vel, ahol i megy 1-t l n-ig. Ha a felhasználó befejezte az A’’ vektor megadását, azaz megadta az nedik komponenset (an-et) is, akkor a program számolja ki an+1 = Xai+1 –et, valamint az utóbbihoz hasonlóan an+2 –t úgy, hogy éppen csak 1-gyel növeli a sorozat összes megel z tagjának összegét. an-et és an+1 -et azonban nem kell megjelenítenie, hanem a továbbiakban használja majd. Ha a felhasználó befejezte az A’’ vektor megadását, akkor a program kiírja neki az összes megadott komponenset a megadás (szupernövekv ) sorrendjében és kéri a sorozat jóváhagyását. Ha a felhasználó azt mondja, hogy nem hagyja jóvá a sorozatot, akkor kérdezze meg, hogy hányadik komponenset akarja újra megadni, s adjon erre módot, majd újra kéri a sorozat konfirmálását. Akárhány javítás megengedett. m

A program úgy kérje az m modulus megválasztását, hogy megadja, hogy mely számok közé kell esnie. Nevezetesen a modulusnak an+1 -nél nagyobbnak kell lennie, s elvileg lehetne ugyan nagyobb, mint an+2 de gyakorlatilag nem célszer nagyobbnak lennie. Modulusnak az a pozitív egészszám felel meg, amely a fenti tartományba esik és eleget tesz a következ feltételeknek is: 73 m maga lehet prímszám, de m+1-nek nem szabad prímszámnak lennie és kell, hogy legyen a1 és an közé es törzstényez je (is). A kulcsgeneráló rutin felajánl a felhasználónak több használható modulust. El ször megkeresi és megjeleníti az els tíz olyan, an+1-nél nagyobb számot, ami megfelel az itt megadott feltételeknek. (Feltéve, hogy ezek közül egy sem haladja meg an+2 értékét, ami egyébként nem is valószín .) Ha a felhasználónak egyik sem tetszik a felajánlott 10 lehetséges modulus közül, akkor kérheti a következ tizes csoportot és így tovább. A felhasználónak persze el bb vagy utóbb ki kell választania az ajánlott modulusok közül egyet. A program már a modulusok ajánlásakor kijelzi az azoknál 1-gyel nagyobb számok (tehát m+1-nek a) törzstényez it is. 3 2 Pl: m+1 = 2664 = 2 × 3 × 37 -1

t és t

73

-1

A szorzó (t) és az inverz (t ) Az algoritmus a felhasználótól kéri a szorzó (t) értékét. A mondottak alapján szükséges, hogy t valódi osztója legyen m+1-nek. Ezt az algoritmus (a t szorzó kérésekor) úgy biztosítja, hogy a felhasználó kiválaszthatja m+1 azon törzstényez it, amelyek szorzata alkotja t értékét. A t szorzónak ez a választása automatikusan biztosítja, hogy az m-hez képest relatív prím-

Persze minden 1-nél nagyobb számra igaz, hogy csakis páratlan szám lehet prímszám és ha m történetesen prímszám, akkor m+1 biztosan nem az. 55

szám lesz.

56

El fordulhat azonban, hogy m+1-nek nincs olyan valódi osztója, amely a1 és an közé esik és akkor vissza kell térni ahhoz, hogy új modulust kell választani. A kulcsgeneráló algoritmus maga nem is ajánl az el z pontban olyan modulust, amelynél ez az eset bekövetkezhet. Ha a (ki)választott szorzó megfelel a kritériumoknak, akkor a rutin kiszá-1 -1 molja az inverz (t ) értékét úgy, hogy t = (m+1)/t. Ez feltétlen egésszám, ha a felsorolt feltételek teljesülnek. A publikus kulcs: A Ez az a pont, ahol érdemes egy modulo m szorzásra szubrutint csinálni, amit aztán a program kés bbi részében is használni lehet. A következ r l van szó: Két természetes szám (jelöljük itt ket x-szel és y-nal) mod m szorzása azt jelenti, hogy az x számhoz (y-1)-szer hozzáadjuk saját magát. Minden egyes összeadás után ellen rízzük, hogy a kapott összeg nem nagyobb-e az m modulusnál. Ha igen, akkor az m modulust ki kell vonni a rész-összegb l és a kapott különbséggel kell folytatni a ciklust, amíg azt (y-1)–szer végre nem hajtottuk. Ez az eljárás biztosítja, hogy akármilyen nagy számok esetén sem következik be túlcsordulás. Jelöljük az így kapott végeredményt r-rel. A kulcsgeneráló rutin kiszámolja az A’’ vektor transzformáltját (az A vektort) úgy, hogy A’’-nek minden egyes komponensét modulo m megszorozza a t szorzóval és az így kapott egészszámok lesznek rendre az A vektor komponensei. Nyilvánvaló, hogy b Csupa egész m veletet kell végrehajtani, b Az A vektornak ugyancsak n komponense lesz, mint az A’’ vektornak volt b Az A vektor mindegyik komponense kisebb lesz az m modulusnál, de egyik komponense sem lesz nulla vagy negatív szám. b Az A vektor egyáltalán nem lesz szupernövekv , de még monoton növekv sem A lényeg az, hogy ha mindez megvan, akkor az algoritmus közli a felhasználóval egy képerny n b A blokkhosszúságot (n-et) b A szupernövekv komponensekb l álló A’’ vektort b A modulust (m-et) b A szorzót (t-t) -1 b Az inverzet (t -et) b A publikus kulcsot (azaz az A vektort a komponenseivel) Elegend a nyilvános kulcsot, azaz az A vektort és a titkos kulcsot, azaz az A’’ vektort, tárolni, mert ebb l a két vektorból bármikor visszaszámolható mind az m modulus, mind a t szorzó és annak inverze.

57

VIII. Titkosított szöveg (ciphertext) el állítása adott publikus kulccsal (= Enciphering) A blokkhosszúság A felhasználónak módja van megadni, hogy egy-egy karaktert hány nyolcbites byte-on ábrázol (alapértelmezésben persze 1 byte-on), és azt is módja van megadni, hogy a blokkhosszúság hány karakter legyen (alapértelmezésben 2 karakter, azaz 2 byte.) Ennek a bináris számnak a számjegyei határozzák meg n értékét a továbbiakban. A címzett nyilvános kulcsa A titkosításhoz használt nyilvános kulcs ( azaz az A vektor) komponenseinek a száma ( =n). Az algoritmus kéri a felhasználótól a címzett nyilvános kulcsát. Ez nem más, mint az összesen n komponensével megadott A vektor. (Mód van arra is, hogy az 1. rutinnal kiszámolt A vektort használja itt a felhasználó, de csak akkor, ha annál éppen az itt definiált n-nel egyezik A komponenseinek a száma. A titkosítandó nyílt szöveg A rutin kéri a felhasználótól a titkosítandó nyílt szöveget. Ezt a felhasználó egy szövegfile-lal adja meg. A titkosítás A rutin karakterpárokat alkot a megadott nyílt szövegb l és minden egyes ilyen karakterpárhoz meghatározza a hozzátartozó bináris kódot. Az utóbbival maszkolja az A vektort és összeadja az A vektornak azokat a kom74 ponenseit, amelyeket a maszk 1-es számjegyei kijelölnek. Ezek a számok lesznek a nyíltszöveg karakterpárjainak a kódjai. Ha páratlan számú karakter volt a szövegfile-ban, akkor a rutin az utolsó karakterhez hozzáf z egy szóközt, hogy az is „rendes” karakterpár legyen. A titkosított szöveg (=ciphertext) tehát egy annyi számból álló számsorozat lesz, ahány karakterpár volt a nyílt szövegben. Jelöljük ezt a ciphertextet egy j komponens vektorral (ahol j a nyílt szöveg karakterpárjainak a száma): C = (c1; c2; ... ck; ... ...cj) A rutin kijelzi ezt a C vektort és ezt külön, egymagában is el lehet menteni. (Azzal az A vektorral, mint nyilvános kulccsal, együtt, amelyet az el állításához felhasználtunk.) Amikor a program használója elküldi a titkosított üzenetét, az azonosítás kedvéért küldje el az A vektort is.

74

Tulajdonképpen az n komponens< A sorvektor és az n bites szám, mint oszlopvektor skaláris szorzatáról van szó. 58

IX.

Titkosított szöveg megfejtése saját privát kulccsal (Deciphering)

A rutin kiinduló adatai: A saját titkos kulcs adatai -1 azaz A’’; m; t és t valamint az els rutinban kiszámított A vektor. A megfejtend ciphertext és az A vektor, amelyet az el állításához használtak. Jelezzük azt itt A’-vel, mert nem feltétlenül azonos az el z pontban említett A vektorral. A nyílt kulcs ellen rzése A rutin ellen rzi, hogy az A’ vektor egyezik-e A-val. Ha nem, akkor közli, hogy a titkosításhoz nem a saját nyílt kulcsunkat használták, tehát a privát kulcsunkkal nem tudjuk az üzenetet megfejteni. Ha a két vektor (ti. A és A’) megegyezik, akkor nekikezd a C vektorral megadott ciphertext megfejtésének. A C vektor transzformációja A rutin megállapítja, hogy hány komponensb l áll a C vektor (A komponensek számát ennél korábban j-vel jelöltük) és elindít egy ciklust, amelyben -1 mindegyik komponenset mod m szorozza t -gyel. T

Az eredmény egy ugyancsak j komponens C vektor lesz, amelynek komponensei az el bb végrehajtott mod m szorzás maradékai, azaz mindegyik komponens m-nél kisebb egészszám lesz. A nyíltszöveg betüpárjaihoz tartozó bináris blokkok meghatározása A feladat az, hogy az A’’ vektor mely komponenseivel lehet lefedni az épT pen adott c i vektor-komponenset. Ezeknek a komponenseknek a helye határozza meg az n bites maszkban az 1-es számjegyek helyét, a többi számjegy pedig 0 lesz. Az eljárás a következ : T T A C vektor legels eleméhez ( c1 –hez ) határozzuk meg, hogy az eredeti, szupernövekv komponensekb l álló, n elem A’’ vektor mely elemeivel fedhet le ez a komponens. A lefedést meghatározó algoritmus a következ : A szupernövekv komponensekb l álló, n elem A’’ vektor jobboldali (azaz a legnagyobb) an komponensét l kiindulva és balra sorravéve a komponenseket a.

T

vizsgáljuk meg, hogy a lefedni kívánt szám (= c1 ) nem kisebb-e az éppen aktuális an A’’ komponensnél. Ha kisebb, akkor írjunk 0-át, ha nem, akkor írjunk 1-et és képezzük a lefedni kívánt szám, valamint az éppen aktuális an komponens különbségét. Jelöljük ezt a különbséget d-vel. A leírt 0-ás vagy 1-es a meghatározni kívánt n-legy bináris szám legkisebb helyiérték számjegye lesz. Ennek az n jegy bináris számnak a további számjegyeit az itt meghatározott LSB-t l rendre balra írjuk, de ezt a tényt továbbiakban nem említjük.

59

b.

Vizsgáljuk meg, hogy d = 0 -e. Ha igen, akkor fejezzük be a lefedés komponenseinek keresését és egészítsük ki balra a bináris számunkat csupa 0-ás jeggyel úgy, hogy összesen n jegy bináris számot kapjunk.

c.

Ha d > 0, akkor vegyük az A’’ vektor következ ( an-1 ) komponensét és ismételjük az eljárást a 1.1 pont elejét l mindaddig, amíg d = 0 –át kapunk 1.2 –ben. T

T

X.

Végezzük el az 1. pontban leírt eljárást C további ci elemeire is (2?i?j)

XI.

Az eredményül kapott n bites blokkokat a kódtáblázat segítségével konvertáljuk vissza olvasható (nyílt) szöveggé.

A titkosított szöveg (ciphertext) megfejtési algoritmusa tehát a következ XII.

75

:

-1

A t inverz és az m modulus ismeretében számítsuk ki a ciphertext-vektor -1 valamennyi elemének t inverzzel való mod m szorzatát. T

XIII. A kapott eredmény-vektor legels eleméhez ( c1 –hez )határozzuk meg, hogy az eredeti, szupernövekv komponensekb l álló, n elem A’’ vektor mely elemeivel fedhet le ez a komponens. A lefedést meghatározó algoritmus az, amit a fenti 1.1; 1.2; 1.3; valamint a 2. és a 3. pontban leírtunk. T

Ha az eredményvektor k-adik komponenséhez, azaz ck –hez tartozó számot Sk-val T jelöljük, akkor ck lefedése a következ képp formalizálható:

xi =

1 ha S k 0

n

x j a j ai

j =i +1

máskülönben

A komponens lefedésének kezdeti lépésében xn = 1 ha Sk? an, máskülönben pedig xn = 0 A.4 Példa Az itt következ példához Tóth Zsolt (Ictus Bt.) programját használjuk. Használjunk a titkosításhoz olyan karakterpárokat, amelyeknél egy-egy karaktert egy-egy 8-bites byte jelöl a keyboard-kulcs szerint. Eszerint tehát 16 bites blokkokat titkosítunk. Válasszuk szupernövekv vektornak a létez legegyszer bb 16 komponens vektort, 0 (k-1) és a 16. (vagyis utolsó) amelynek els komponense 2 =1, k-adik komponense 2 15 16 komponense 2 . Így a modulusnak 2 -nál (=65536) nagyobbnak kell lennie. Olyan modulust keresünk, amelynek 1-gyel megnövelt értéke csak két törzstényez szorzata és e törzstényez k nagyságrendileg nem is nagyon különböznek 75

Ezt valósítja meg az el bbiekben leírt harmadik rutin (Decryption.) 60

egymástól. Sok ilyen szám van 65536 és 131072 között. Ezeket könny megkeresni az el bbi algoritmus szerinti programmal. Válasszuk modulusnak a 66012 számot: m = 66012 amelynek 1-gyel megnövelt értéke a következ két tözsszám szorzata: m + 1 = 66013 = 251 × 263 Nyilvánvaló, hogy a két törzstényez közül az egyik lesz a szorzó, a másik pedig az inverze. Legyen -1

t = 251 és t = 263 Ezekkel az „eredeti” szupernövekv vektor (=A’’) és a nyilvános kulcsként közzétett 76 transzformáltja (= A ) a következ k : A’’ = (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768) A = (251, 502, 1004, 2008, 4016, 8032, 16064, 32128, 64256, 62500, 58988, 51964, 37916, 9820, 19640, 39280) A két sorba írt publikus kulcs els felében persze nagyon könny felfedezni, hogy a komponensek duplázódnak. Ha a módszer ismert, akkor az els tagból a szorzó is felismerhet . (Lévén 251 prímszám, a szupernövekv sorozat els tagja nem is lehet más, mint 1.) Imígyen az „eredeti” szupernövekv sor is könnyen kitalálható. Látszik az is, hogy a publikus knapsack vektorban ( A-ban) a tagok monoton növekedése a sorozat 10. tagjától törik meg. Mindebb l már elég könnyen visszafejthet az egész kulcs, de itt éppen azt (is) szerettük volna szemléltetni, hogy a titkos kulcs megválasztásakor azért lehet ség szerint kerülni kell az olyan triviális eseteket, mint a 2 egész hatványai szerint szupernövekv sorozat. Legyen a titkosítandó példa-szövegünk az ábécé b ötbetüs csoportonként egy-egy szóközzel megszakítva. Tehát a tesztszöveg most a következ : AÁBCD EÉFGH IJKLM NOÖPQ RSTUÜ VWXYZ Írjuk a nyíltszöveget egy txt kiterjesztés file-ba pl. a Windows Notepad-jét használva és mentsük el valamely általunk erre kijelölt mappában. (a program alapértelmezésben a saját „Knapsack” nev mappájába ment mindent, de természetesen ezt nem kell feltétlenül követni.) A tesztszöveg szóközökkel együtt összesen 35 karakter, tehát a program egy végjelként egy szóközt tesz majd hozzá, hogy egész karakterpárokat kapjon. A 36 karakterhez tehát összesen ennek a felét, vagyis 18 kódszámot kell kapnunk.) A példához választott adatokkal a fenti nyíltszöveg titkosított formája a következ : 198666, 137986, 67522, 244614, 155838, 63506, 156702, 162946, 103666, 197770, 141321, 93626, 191958, 174106, 73797, 209810, 198186, 61870 A megfejt (=Decryption) rutint alkalmazva a megfejtés a következ : AÁBCD EÉFGH IJKLM NOÖPQ RSTUÜ VWXYZ_ 76

A programmal el is menthet k ezek, ha a generálásuk után az egér jobb gombjával megnyitjuk a mentés párbeszéd-ablakát. 61

Látható, hogy a program egy végjelet is hozzáf z a megfejtéshez, ami az eredeti nyílt szövegben nem volt benne. Jóllehet a programban alkalmazott filenevek önmagukért beszélnek, azért itt is felsoroljuk azokat: Alapértelmezésben tehát a Knapsack elnevezés mappába ment mindent a program és ott találhatók a három rutin exe file-jai is:

KeyGen.exe

ksEncryption.exe

ksDecryption.exe

A kulcs-generáló rutin (KeyGen.exe) segít a titkos kulcsot el állítani. Alapértelmezésben 8 bites byte-okkal és karakterenként 1-1 byte-tal dolgozik, továbbá karakterpáronként kódol. A karakterpáronkénti kódolás azonban a forrásprogramban átállítható, de utána újra kell fordítani a programot. A rutintól tizes csoportokban kérhet k a lehetséges m modulusok és mindegyikhez megadja az 1-gyel megnövelt érték (m+1) prímfaktorait is. A választott modulust kijelölve a t szorzóhoz ki kell pipálni, hogy m+1 mely törzstényez inek a szorzata legyen t. Nyilvánvaló, hogy a ki -1 nem jelölt törzstényez k szorzata adja ki a t inverzet. Mindezek megválasztása után a program bkérésreb generálja a publikus kulcsot. A rutin párbeszéd-ablakában van egy xxx-szel jelölt ablak, ami debugging célokra való. A program mindennapi használatakor nem használjuk semmire. Az egér jobb gombjával klikkelve elmenthet a privát kulcs, azaz az „eredeti” szupernövekv komponens vektor, amit generáltunk. A filenév:

filename.PrivKey

Ezek után ki lehet szállni a kulcs-generáló programból. Mind a címzett nyilvános kulcsát, mind a titkosítani kívánt szöveget .txt kiterjesztés szövegfile-ban kell megadni abban a mappában, amelyben dolgozunk. A szöveget a legegyszerübb pl. a Windows Notepad-jébe begépelni és ugyanott nyithatók meg a titkosított valamint a visszakonvertált szövegfileok is. File nevek: A nyilvános kulcsé:

filename.PubKey

A titkosítandó nyíltszöveg egy egyszer .txt kiterjesztés szövegfile: filename.txt A titkosító rutin (ksEncryption.exe) akkor kéri a titkosításhoz használandó publikus kulcsot, ha a megfelel ablakban az egér jobb gombjával megnyitjuk a párbeszédablakot. Beolvassa a megadott file-t és ki is írja a publikus kulcs valamennyi komponensét. Ezek után a megfelel gombra kattintva kéri a titkosítandó szövegfile-t. Külön gombra kell kattintani ahhoz, hogy a titkosítást el is végezze. Ha befejezte, egy ablakban közli, hogy készen van vele s egyúttal el is menti ugyanabba a mappába, amelyb l a titkosítandó szöveget vette. A titkosított szöveg file neve:

filename.txt.KSE

62

Azt is mondhatjuk, hogy a titkosítandó nyílt szöveg kiterjesztett file nevéhez hozzáf zi a KSE (= Knapsack Encryption) kiterjesztést. Ezek után ki is lehet szállni a ksEncryption rutinból. A titkosított szöveg (=szám-sorozat) pl. a Notepad-ben megnyitva elolvasható. A megfejt rutin (ksDecryption.exe) nagyon hasonlóan m ködik, de itt a saját titkos kulcsot (filename.PrivKey) és a titkosított szöveget (filename.txt.KSE) kell megadni. Külön gombra-kattintásra végzi el a dekódolást és a dekódolt nyílt szöveget filename.txt_D név alatt ugyanabban a mappában menti el, amelyb l a titkosított szöveget kiolvasta. Itt érdemes elmondani, hogy a program a privát kulcs (=A’’) és a nyilvános kulcs (=A) ismeretében hogyan számolja vissza a t szorzót és az m modulust. Az A vektor (=publikus kulcs) els komponensét úgy kapjuk meg A’’ (privát kulcs) els komponenséb l, hogy szoroztuk azt a t szorzóval. Ez a szorzat nem lehet nagyobb, mint a modulus, ezért A els komponensét osztva A” els komponensével, megkapjuk a t szorzót. A többi komponenset is úgy kapjuk A’’-b l, hogy rendre mod m szorozzuk azokat tvel. A sorozat mindaddig növekszik, amíg a szorzat meg nem haladja a modulus értékét. Meg kell tehát figyelni, hogy az A vektor komponenseinek monoton növekedése hol „törik meg” el ször. Ekkor már ismert a t szorzó, tehát kiokoskodható, hogy mennyi volt a modulus értéke, amit a t×ai-b l le kellett vonni (ha ai volt az els olyan komponens , amely már nem volt nagyobb, mint az t balról megel z ). Az els ilyen helyen valószín leg még csak egyszer kell levonni a modulust, de a kapott érték az A’’ és az A vektorok további tagjainak összehasonlításával ellen rizhet . Az m modulus és a t szorzó ismeretében már könny kiszámolni az inverz értékét: -1

t = (m+1)/t Elegend tehát bmint korábban állítottukb csak a titkos kulcsot (A’’) és a nyilvános kulcsot (A) ismerni a megfejtéshez.

63

XIV.

FÜGGELÉK Rövid áttekintés a matematikai bonyolultságelméletr l a kriptográfia szempontjából.

A matematikai bonyolultságelmélet ( = Complexity Theory) itt következ összefoglalóját Randall K. Nichols professzor The Guide to Cryptogrphy c. könyvéb l vettem át. 77 j maga azonban Arto Salomaara és William Stallingsra hivatkozva írta meg ezt az összefoglalót (á la Salomaa – ahogyan állítja). A központi kérdés az, hogy hogyan lehet meghatározni, hogy egy titkosítási eljárás mennyire áll ellen a feltörési kisérleteknek. Más szóval mennyi id szükséges ahhoz, hogy egy adott támadás a kriptorendszer ellen sikeres legyen. Úgy képzelhetjük, 78 hogy egy kriptanalítikai támadáshoz szükséges er feszítés szintje egy bizonyos magnitúdóval kifejezhet , azzal mérhet . Megkiséreljük ezeket a magnitúdókat összevetni a jelenlegi és a jöv beli processzálási kapacitásokkal azért, hogy valamely adott algoritmus biztonsági szintjét meg tudjuk határozni. A kriptográfia klasszikus matematikai problémái véges sok bizonyítással mind megoldhatók. A „véges sok” esetre való visszavezetés azonban gyakorlatilag semmire sem jó, ha az esetek száma olyan nagy, hogy gyakorlatilag nem tudjuk azokat kezelni. Ha képtelenek vagyunk egy titkosított szöveget bizonyos id határon belül megoldani, akkor akár el is felejthetjük az egészet, mert az id el rehaladtával a titkosított szöveg tartalma úgyis általánosan ismertté válik. 79

Egy algoritmus id"beli komplexitása az n bemenet hosszának a függvénye. Ez más 80 szóval azt jelenti, hogy az algoritmus végrehajtása legfeljebb f(n) lépést igényel akármilyen is egyébként a bemenet és akármekkora is n értéke.

77

Arto Salomaa nevét már többször említettük az eddig leírtak során. Érdemes megjegyezni azonban William Stallings nevét is, aki különösen a kódoláselméletben számít világhír< szakért nek. Az Információtechnika c. tárgyban másutt már találkozhatott az olvasó Stallings nevével.

78

Itt és másutt is a szerz k nem illegális feltörésr l beszélnek, hanem a kriptanalítikus megoldási kisérletér l. A szövegekben tehát a kriptanalítikus az a személy, aki eleve nem rendelkezik a titkosítás megoldási kulcsával, de anélkül is rá akar jönni az eredeti nyíltszöveg visszanyerésének a módjára. Magyarul: mégis csak fel akarja azt törni, bármilyen indítékból is teszi. Talán a kriptográfusok szolidaritása miatt használják a szerz k az „illetéktelen megfejt ” helyett a „kriptanalítikus” megnevezést. Itt, legalább ebben a Függelékben így kell ezt érteni.

79

Az id beli komplexitás fogalma egy adott algoritmusra is értelmezhet és egy adott problémakörre is, amelynek több megoldási algoritmusa is lehet. Az utóbbi esetben az id beli komplexitástól azt várjuk, hogy adjon meg egy id beli korlátot arra, hogy mi az a legrövidebb id , amely alatt bármilyen algoritmussal megoldható az adott probléma. Ez igen nehéz ügy, mert szinte mindíg nyitott kérdés, hogy igaz ugyan, hogy esetleg többszáz éve nem fedeztek fel elég gyors algoritmust egy adott probléma (pl. a faktorizáció) megoldására, de nem is bizonyították, hogy nincs ilyen algoritmus. Mi van, ha holnap felfedez valaki egyet?

80

Kérdés, persze, hogy mit nevezünk bemenetnek. Ha arra gondolunk, hogy n a kulcshosszúságot jelöli, akkor egészen biztos, hogy az id beli komplexitás, azaz f(n) n , ha n növekszik 64

Ha n egy egészszám, akkor a hosszúsága a benne lév számjegyek száma. Bináris esetben természetesen n bitr l beszélünk, de a meghatározások nem bináris esetekre is érvényesek. Van tehát a bemenet n hossza és az id beli komplexitás ennek 81 a hossznak a függvénye: f(n). Maguknak a lépéseknek a definiciója többértelm is lehet. Lehetnek továbbá gyors és lehetnek lassú algoritmusok ugyanannak a problémának a megoldására. Bizonyos esetekben lehet ség nyílhat a megoldás szinte korlátlan felgyorsítására is. Általában igen nehéz a komplexitásra alsó határt megállapítani. Például nagyon nehéz kimutatni, hogy egy adott probléma megoldására szolgáló valamennyi algoritmus legalább is négyzetes id"beli komplexitású. Fontos, hogy a relatív végrehajtási sebesség milyen mértékben (pontosabban: arányban) növekszik. Ha pl. az RSA módszernél 50 digites kulcsot vagy 100 digites kulcsot használunk, akkor nem feltétlenül szükséges tudnunk, hogy mennyi id szükséges az egyik ill. a másik kulccsal titkosított üzenet feltöréséhez. Elegend , ha azt tudjuk, hogy hányszor több er feszítésre van szükség akkor, ha a titkosításhoz a hosszabb kulcsot alkalmazták. Ehhez „csak” az egyik ill. a másik kulcs alkalmazásakor érvényes bonyolultságok magnitúdóit kell összevetni egymásal. f(n) pontos formulájának a meghatározása nehéz, mert az id beli komplexitás függ attól az algoritmustól is, amit éppen a vizsgálat tárgyává tettünk. Nyilvánvaló, hogy kevesebb lépésre van szükség akkor, ha egy-egy lépésben több feladatot oldunk meg. Az alapvet terminológia azonban, mint pl. a polinomiális id" nagymértékben független az aktuális algoritmustól. Az algoritmusaink alapvet modelljének a klasszikus Turing gépet választhatjuk, 82 amely diszkrét id lépésekben m ködik. A diszkrét id lépték itt azt jelenti, hogy az automata tranziens folyamatait nem kisérjük figyelemmel. Ha valamilyen változás történik akár a bemeneten, akár az automatán belül, akkor megvárjuk amíg a tranziensek lejátszódnak és csak az azokat követ , az automata (viszonylag) stacionárius állapotában írja le a modellünk a rendszer un. állapotait. (Bemeneti és un. bels állapotokról van szó.)

81

A számítási technológia persze fejl dik s ezért az a megoldási (feltörési) id , ami ma szükséges egy bizonyos titkosítás esetén, nos ez a feltörési id id vel rövidül majd. Ezért sokkal pontosabb, ha a feltöréshez szükséges lépések (=m
82

Hát erre a fogalomra —nevezetesen a diszkrét id fogalmára— itt aztán egészen biztosan nem térhetünk ki. Azok a hallgatók, akik Digitális technikát tanultak találkoztak már a digitális rendszerek statikus modelljeivel, amelyek diszkrét id -intervallumokban, a rendszer kvázistacionárius állapotaiban írják le a rendszer m
Az absztrakt automaták modelljében az egyik „nagy csel”, hogy a végtelen nyelvek problémáit úgy oldja meg, hogy egy véges bels állapotú automatához egy elméletileg végtelen háttértárat rendel hozzá. Végül is a Turing gép is ezt teszi. A Turing gép tehát egy véges (bels ) állapotú automata és egy elméletileg korlátlanul használható bemenet és háttértár együttese. A Turing gép a megoldandó problémát jelent bemeneti „szót” egy bemeneti szalagról olvassa le. A szalagra írni is képes. Képes az olvasó/író szerkezetét a bemeneti szalagon jobbra vagy balra mozgatni egy-egy lépéssel egy-egy id szakaszban. Képes a bemeneti szalagon lév információt felülírni és képes a bemeneti szalag használt tartományát mindkét irányban kiterjeszteni. Elvi (vagy matematikai) szempontból az a kérdés, hogy létezik-e egyáltalán olyan Tu83 ring gép , amely képes a problémát megoldani. Azaz kérdés a megoldás elvi egzisztenciája, létezése. Ezt persze jó lenne tudni, miel tt egyáltalán nekilátunk a megoldásnak. A kriptográfia gyakorlati aspektusa azonban különbözik ett l az elvi kérdést l. Nem „csak” az a kérdés ugyanis, hogy létezik-e egyáltalán megoldás, hanem az, hogy ha van is elvi megoldás, megkaphatjuk-e azt gyakorlatilag elfogadható lépésszám-korláton belül. Ez az, amit mindeddig polinomiális id"ben való megoldásnak neveztünk. Figyeljünk fel arra, hogy ez nem csak elvi kérdés s t, nem is els sorban az, hanem gyakorlati, a mindenkori számítási technológiától függ kérdés is, ezért nagyon nehéz, vagy nem is lehetséges rá egzakt matematikai definiciót adni. Ajánlatos inkább elfogadni, hogy a polinomiális id" kifejezés valamilyen létez , de nagyon nehezen meghatározható korlátot jelent a megoldásra, azaz a kód feltörésére, és vannak számítástechnikai aspektusai is. Visszatérve a Turing géphez, az egy adott stacionárius diszkrét id szakban rendelkezik egy q bels állapottal és egy a bemeneti szalagról éppen leolvasott a bemeneti szimbólummal. Ezt az absztrakciót egy ábrán is ábrázolhatjuk:

83

Ha valahol, hát itt egészen nyilvánvaló, hogy a Turing gép alatt inkább módszert (=algoritmust) kell érteni mintsem valamilyen hardver eszközt. 66

Az a cella (karakter) amit az adott állapotban éppen olvas (vagy ír) a véges automata író/olvasó feje Az aktuális munkaterület baloldali végét jelzõ jel

Üres hely a munkaszalagon

Az aktuális munkaterület jobboldali végét jelzõ jel

Üres hely a munkaszalagon

a0

ai

an

m Az automata író/olvasó feje

Mozgás a szalag mentén celláról-cellára egyet-egyet lépve bármelyik irányban

Végesállapotú automata

A Turing gép modellje

Jelölje a véges automata aktuális belsõ állapotát qj

Az automata bels állapota (=qj) és a szalagról éppen leolvasott bemeneti állapota (=ai) meghatározza a következ bels állapotot (=qj+1) és az író/olvasó fej elmozdulását (=m) valamint azt, hogy ebben a következ állapotban vajon olvasni fog-e az automata a szalagról, vagy el bb felülírja-e annak a cellának a tartalmát, amelyet éppen kiolvasott az író/olvasó fej. Így fogalmazva a dolgot a Turing gép, amelyr l beszélünk, un. determinisztikus automata. Erre még visszatérünk alább (t.i. a 70. oldalon), mert van a gépnek nemdeterminisztikus változata is. A Turing automata képes a bemeneti szalag minden celláját akárhányszor használni, azokat tetszése szerint többször is felülírni és képes a végjeleket odébbhelyezni, más szóval a munkatartományát tetszése szerint kiterjeszteni. Ebb l a modell-leírásból nem következik egyenesen, de ténykérdés, hogy a Turing 84 gép képes minden algoritmizálható problémát véges sok lépésben megoldani. Azokkal a problémákkal azonban, amelyek megoldására nem adható algoritmus, a Turing gép „a végtelenségig elmolyol”, soha nem fejezi be a munkáját. Persze sok esetben nem mondható meg el re, hogy melyik osztályba (ti. algoritmizálható vagy sem) esik az adott probléma s így nem mondható meg el re, hogy ha a Turing gép nekikezdett egy aktuális probléma megoldásának, akkor megáll-e valaha. Ezt nevezik a Turing gép megállási problémájának.

84

Ti. van olyan Turing gép, 67

A Turing gép megállási problémája persze nem az (mármint az aktuális Turing gép) saját belügye, hanem annak a problémája, aki a feladatot adta neki, vagyis a mienk. A bemeneti szalagot tekinthetjük egy gyakorlatilag végtelen memóriának is, de tekinthetjük a bemenet és a kimenet hordozójának is. A gép a számítást valamely specifikus (kezdeti) bels állapotból kiindulva és a szalag legels jelét (mondjuk a baloldali legszéls (nem végjelet tartalmazó és nem üres) cella leolvasásával kezdi. A gép problémamegoldó képessége attól specifikus, hogy a véges automata része mit csi85 nál ezek után. Pontosabban szólva a véges automata un. állapotfüggvénye micsoda. Ebb l következik, hogy sokféle Turing gép van. Ezek a felsorolt általános sajátságaikban megyeznek, de állapotfüggvényeikben különböznek és eszerint más és más problémák megoldására valók. Magát az aktuális Turing gépet le lehet írni —többek között— a programjával is, ami nem más, mint egy bináris számsorozat, de meghatározható a gép egy algebrai polinommal is. A Turing gép számítási folyamatának a végét az jelenti, hogy a gép elérkezik az 86 el re specifikált végállapotok valamelyikébe. A végeredményt nem csak az automata bels állapota jelentheti, hanem a szalag egy részére az automata által felírt szó is. A Turing gépr l elmondottak alapján definiálhatjuk, hogy mit jelent az id"beli komplexitás-függvény. (Emlékezzünk rá, hogy a bemenet hosszát n-nel jelöltük és használjuk itt egy adott probléma megoldására való Turing gépre az A indexet.) fA(n) = max { m | A megáll m lépés után, ha a bemenete egy legfeljebb n hosszúságú w szó} A matematikai bonyolultság ( = komplexitás) fogalmát így egy Turing gép megállási problémájával definiáljuk, pontosabban azzal, hogy hány lépés után (= m) áll meg. 87 Feltéve, hogy egyáltalán megáll valaha.

85

Az állapotfüggvény tehát —determinisztikus automata esetén— az ai bemenet és a qj bels állapotpárhoz —mint argumentumhoz— hozzárendeli a következ bels állapotot. Az állapotfüggvénnyel együtt jellemz az automata viselkedésére az is, hogy az ai bemenet és qj bels állapot hatására milyen kimenetet produkál. Ezt egy másik függvény, t.i a kimeneti függvény határozza meg. Ha mind az ai bemeneti állapotokat, mind a qj bels állapotokat egy-egy halmaz elemeinek tekintjük, akkor az el bbi függvények argumentuma e két halmaz (direkt) szorzathalmazának elemei.

86

Figyeljünk fel arra, hogy, hogy nem csak egy végállapota lehet. Pl. ha az a feladata, hogy állapítsa meg, hogy a bemenetként megadott bináris „szóban” páros, vagy páratlan az 1-es számjegyek száma, akkor természetesen más végállapot jelenti a páros és egy másik végállapot a páratlan eredményt.

87

Ezzel a komplexitás (új) fogalmát egy matematikailag pontosan definiált fogalomkörre, nevezetesen a Turing gép fogalmára vezettük vissza. Ez persze nem túl vígasztaló azoknak, akiknek a Turing gép ugyanolyan, az ismeretlenség ködébe burkolódzó fogalom, mint a komplexitás.

68

Felfoghatjuk azonban úgy is, hogy Salomaa a bonyolultságot végül is egy elvileg jól definiálható gép megoldási lépéseivel definiálta, s milyen más gépet is válszthatott volna erre a célra, mint a Turing gépet, mint absztrakciót. 69

Ha a titkosítás fogalomkörében akarjuk a mondottakat megfogalmazni, akkor azt 88 mondhatjuk, hogy vesszük az n hosszúságú titkosított szövegekb l az összes n hosszúságú w szót. Ha van olyan algoritmus ( ez jelenti ti. az A Turing gépet), amely m lépésben sorra megfejti valamennyi w hosszúságú szót, akkor e megfejtésekhez különböz m lépésszámok tartoznak és az m lépésszámok közül a maximális adja meg az fA(n) komlexitás függvény értékét. A Turing gép fogalmára való visszavezetés matematikailag rendbeteszi a bonyolultság fogalmát. Hangsúlyozzuk, hogy a Turing gép egy (matematikai) absztrakció és ezért az ábrán bemutatott változatát sem úgy kell eképzelni, mintha az feltétlenül hardver változata lenne. (Bár az sem kizárt.) Itt és a továbbiakban az A Turing gép az adott titkosítási feladat megoldására való algoritmust jelenti, amelynek analítikus matematikai alakja bármilyen lehet, s mint 89 ilyen, felírható egy algebrai polinom alakjában is. Ez fontos a továbbiak megértése szempontjából. Egy A Turing gép polinomiálisan behatárolt, ha létezik olyan p(n) tagú polinom, amelyre bármely n esetén igaz, hogy fA(n) ? p(n). Jelölje továbbá P mindazon problémák halmazát, amelyek megoldhatók egy polinomiálisan behatárolt Turing géppel. Egy problémát számításigényét tekintve kiszámíthatatlannak (néha megoldhatatlannak) nevezünk, ha nem tartozik a P halmazhoz. A P halmazba tartozó kiszámítható (vagy, bonyolultabb kifejezéssel: kikövetkeztethet") problémáknak számos alosztálya van, amelyek mind P valódi részhalmazai. Ezeknek az alosztályoknak a definiciója nyilvánvaló kell, hogy legyen: olyan problémákról van szó, amelyek id"beli komplexitása lineáris, négyzetes, köbös, exponenciális, és így tovább. Arról van szó, hogy f(n) milyen jelleg függvénye n-nek. Ha egy problémáról (informálisan) azt állítjuk, hogy az „könnyN”, akkor ez alatt azt értjük, hogy a polinom értékei (t.i mind a fokszáma, mind az együtthatói, mind az 90 exponensei, stb.) kicsik, legalább is a vizsgált tartományban azok. A korábban említett és modellként használt Turing gép determinisztikus, ha a bemeneti szalagról éppen leolvasott karakter és az aktuális bels állapot egyértelm en meghatározza a gép következ lépését. Ilyenkor mind az állapotfüggvény, mind a

88

Vegyük az egyszerüség kedvéért azt az esetet, amikor blokk-titkosításról van szó és a blokkhosszúság éppen n. Valójában ez a problémakör nagyon leegyszerüsített modellje, mert blokktitkosítás esetén sem nyilvánvaló a cyphertextb l, hogy mi a blokkhosszúság (ezt éppen a Knapsack titkosítás szemléltette igen jól), másrészt pedig általános esetben nem csak a blokkhosszúságról van szó, hanem az adott titkosítási rendszerben egyáltalán el forduló titkosított szövegek maximális hosszáról.

89

Itt azonban nem a matematikai analízis alapértelmezése szerinti polinomokról van szó, hanem a számelméleti értelmezés szerintiekr l, amelyekkel a Kódoláselmélet c. segédlet Galois test c. függelékében foglalkoztunk .

90

Gondoljunk pl. arra, hogy „köztudott”, hogy egy exponenciális függvény pl. gyorsabban növekszik, mint egy lineáris függvény. Ha azonban az argumentum vizsgált tartománya a nagyon kis pozitív számok tartománya, akkor ez a „közhiedelem” máris nem igaz. 70

kimeneti függvény egyérték . Ennek megfelel en szokás determinisztikus id"beli komplexitásról beszélni. Egy nemdeterminisztikus Turing gép esetében az aktuális bemeneti állapot (= ai) és bels állapot (= qj) nem csak egyetlen következ lépést tesz lehet vé, hanem többet is. Ez azt jelenti, hogy az automata bármely állapotában szerteágazó, további számítási lépések lehetségesek. Tulajdonképpen csoda, hogy ennek ellenére is megoldásra juthatunk (azaz a gép mégis csak „megérkezik” valamely el re specifikált végállapotába). A gyakorlatban ez azt (is) jelenti, hogy a gép valamely közbens állapotában becsléseket tehet, vagy az adott lépésben általa meghatározott számú, párhuzamosan m ködtetett mikroprocesszorral valamennyi továbblépési lehet séget kiszámítja és (m ködése során minden lépésénél) kihasználva az összes lehet séget, megvizsgálja, hogy egy adott w bemeneti szó esetén mi az a legrövidebb út (shortest way), ami a végs megoldáshoz vezet. Jelöljük ezt s(w)-vel. Ezek után egy nemdeterminisztikus A Turing gép esetén az id beli komplexitás definiciója a következ : fA(n) = max {1, m | s(w) -hez m lépés tartozik, ha a bemenet egy legfeljebb n hosszúságú w szó} Az (1, m) pár azt jelenti, hogy létezhetnek olyan n-ek, amelyekhez nem tartozik semmilyen eredményes számítási módszer. Ezekkel a polinomiálisan behatárolt nondeterminisztikus Turing gép és a neki megfelel NP osztály matematikailag ugyanúgy pontosan definiált, mint azt a determinisztikus Turing gép kapcsán megtettük. Végeredményben tehát a P osztályba tartozó problémák kikövetkeztethet k, míg az NP osztályú problémák esetében legalább arra lehet ségünk van, hogy valamilyen id korláton belül megvizsgáljuk, hogy ha egy n hosszúságú bemeneti szóval rendelkezünk, akkor a probléma egy jó becsléssel meghatározott módszerrel megoldható-e vagy sem. Legalább is valamilyen id korláton belül. És bizony el fordulhat, hogy nincs megoldás. 91

A P és az NP osztályok —elnevezésük logikája ellenére— nem diszjunkt halmazok. Ez azonban nem bizonyítás, hanem definició kérdése, tehát P definició szerint részhalmaza NP-nek.

91

Aki foglalkozott valamennyit a formális nyelvek és a hozzájuk rendelhet absztrakt automaták fogalmával, annak a számára nem meglep , hogy itt (is) egymásba épül osztályokról van szó. A P osztály NP-nek részhalmaza. Az egész eszmefuttatás a következ kben is nagyon emlékeztet a formális nyelvek (Chomskyféle) osztályokba-sorolásának problémakörére. Salomaa, akit l ez a gondolatmenet ered, nem véletlenül alkalmazta a korábbi formálnyelvi matematikáját a bonyolultságelméletben. 71

P Egy adott probléma, amely történetesen kikövetkeztethet

Egy kemény NP-komplett probléma

NP

Nem ismert pl, hogy egy egészszám faktorizációja P-ben van-e, de egészen bizonyos, hogy az NP halmazban benne van. Eszerint becslést lehet tenni arra, hogy a faktorizáció adott id limiten (=m veletszámon) belül elvégezhet -e vagy sem. A tényleges számítás aztán megmutatja, hogy sikerült-e a törzstényez kre való bontást a becsült id n belül elvégezni, vagy sem. Meg kell enni tehát a puddingot ahhoz, hogy el tudjuk dönteni, hogy megehet -e. Kikövetkeztethet problémák esetén az NP halmaz „lesz kül” P-re. Tulajdonképpen elvi kérdés, hogy mikor áll fenn a P = NP egyenl ség. A matematikusok úgy vélik, hogy általános esetben nem áll fenn. Ilyenkor aztán az a gond, hogy el kellene dönteni, hogy az éppen vizsgált probléma P-ben is benne van-e, vagy csak NP-ben úgy, hogy P-be nem tartozik bele. Az utóbbi esetnek nevet is adtak: kemény NP-komplett problémának nevezik. A kemény NP problémák tehát (polinomiális id ben) nem kikövetkeztethet k. Az NP osztályon belül az NP-komplett és a kemény NP kifejezéseket azonos értelemben használják.

Ha egy adott probléma visszavezethet egy korábbról már ismert és bizonyítottan kemény NP problémára, akkor az a bizonyos adott probléma is kemény NP probléma. Mindennek azonban csakis akkor vehetjük valamilyen hasznát, ha ki tudunk indulni valami olyan problémából, amelynek NP-komplettsége valamilyen közvetlen indokolással (direkt argumentummal) bizonyítható anélkül, hogy azt (mármint a problémát) bármire is visszavezetnénk.

72

Igen alkalmasak erre a célra a kijelentéskalkulus jól formált formulái (kkjff).

92

Az itt következ példa Salomaa-tól származik. Jelölje a predikátum-kalkulus alkalmazásakor a konjunkció m veletét diszjunkcióét pedig . Jelölje továbbá a negációt a változó elé írt ~ jel.

a

Vizsgáljuk meg ezekkel a jelölésekkel felírva a következ összetett kijelentés igazságértékét (amely kifejezés mellesleg egy kkjff): (X1

~X2

X3)

(X2

X3)

(~X1

X3)

~X3

A m veleti jel helyett a Boole algebra logikai szorzását (= ÉS m velet), a jel helyett pedig a Boole algebra logikai összeadását ( = VAGY m velet) alkalmazva azonos átalakításokkal könnyen bizonyítható, hogy az el bbi kifejezés igazságértéke minden változó-kombinációhoz HAMIS (=FALSE) értéket rendel hozzá. Az egész dolog úgy is értelmezhet , hogy egy ilyen (az adott esetben háromváltozós) kifejezés a kijelentések (=logikai változók) minden kombinációjához egy-egy igazságértéket rendel hozzá, tehát a mondott kombinációkat leképezi egy kétérték (ti. IGAZ ill. HAMIS) halmazra. 93

Közvetlen indokolással megmutatható, hogy egy kkjff kielégíthet ségének a problémája NP-komplett. Egy adott Turing gép számítási munkája (adott bemenet esetén) sikeres, ha hozzá egy kielégíthet kkjff tartozik. A kkjff kielégíthet sége mindig ellenrizhet úgy, hogy a (független) változók valamennyi kombinációja esetén megvizsgáljuk az összetett kifejezés igazságértékét. Ez a predikátum-kalkulus esetén exponenciális id"-komplexitást eredményez, mert k k változó esetén 2 kombinációt kell megvizsgálni.

92

Az eredeti angol kifejezéssel: well-formed formulas of the propositional calculus wffpc. Az eredeti elnevezés és rövidítése tehát semmivel sem kevésbé idétlen, mint a magyarra fordított változatáé. A dolog azonban egyáltalán nem annyira bonyolult, mint amennyire els pillanatban t
93

Arról van szó, hogy egy ilyen összetett állításnak van-e legalább egy olyan változókombinációja, amelyre IGAZ az összetett állítás igazságértéke. Ha van ilyen, akkor az adott formula kielégíthet . 73

A terjedelem-komplexitás (=Space complexity) az el bbivel analóg módon definiálható. Ha egy Turing gép bemenete n hosszúságú szalag (lásd az ábrát az 67. oldalon!), akkor a problémamegoldás kezdetén a bemeneti szalagon n cella foglalt. Lehetséges, hogy a számítások során a gépnek ezeken kívül, újabb cellákra lesz szüksége. Ezeknek az újabb celláknak a száma jelzi a terjedelem komplexitást. Persze figyelembe vehet k a polinomiális határok. Ezekkel definiálható a P-TERJ és az NP TERJ (P-SPACE and NP-SPACE) fogalma. Ez a terjedelem-fogalom szoros kapcsolatban van az id beli komplexitással, mert a Turing gép a munkaszalag aktuális munkatartományának minden egyes kiterjesztéséhez egy-egy m veletet igényel. (Ezt az 67. oldal ábrájával kapcsolatban ott megmutattuk.) Ami a terjedelem-komplexitást illeti, bebizonyítható, hogy P-TERJ = NP TERJ Következésképp az alábbi következtetési láncot kapjuk: P

NP

P-TERJ = NP-TERJ

Tulajdonképpen nyitott kérdés, hogy ezek valóban teljesülnek-e vagy sem. A Co-NP problémák osztályát olyan problémák alkotják, amelyek „komplemense” NP probléma. Pl. annak a problémának, hogy egy adott szám prímszám-e, a komplemense az, hogy egy adott szám összetett szám-e. Formális definició rendelhet a problémákhoz, ha azokat (formális) nyelveknek te94 kintjük. Az nyilvánvaló, hogy ha egy probléma a P halmazba tartozik, akkor a komplemense is P eleme. (Más szóval: ha egy probléma kiszámítható, akkor a komplemense is kiszámítható és fordítva is igaz.) Ez azonban nem feltétlenül igaz a nemdeterminisztikus esetekre. Valójában nem ismert a kapcsolat az NP és a Co-NP problémák között, de az az általános hiedelem, hogy NP Co-NP. Ha egy NP- komplett probléma komplemen95 se is NP komplett, akkor persze NP = Co-NP.

94

E kijelentés kapcsán visszaköszön az, hogy Arto Salomaa a bonyolultságelmélet matematikai modelljének a megalkotásához a korábbi formálnyelvi studiumait alkalmazta. Egyébként e sorok szerz jének az a tapasztalata, hogy több olyan módszer „visszaköszön” valamely modern alkalmazásban, amelyet korábban valami egészen más célra használtak és a korábbi gyakorlati alkalmazás esetleg mára már idejét múlta. Így az egyszer megtanult módszerek többsége újra hasznosítható, s a megtanulásukra fordított id nem válik elvesztegetett id vé. Tipikusan ilyen problémakör pl. a logikai hálózatok minimalizálása.

95

Az el bb azt fejtegettük, hogy ha egy probléma kiszámítható (azaz a P halmazban van), akkor a komplemense is kiszámítható. Itt most az NP problémák kapcsán nem ezt a logikát követjük. Vagyis ha egy probléma nem kikövetkeztethet , abból még nem következik, hogy a komplemense is kiszámíthatatlan. ( Az olvasó ne keseredjen el, ha ez a számára egyáltalán nem nyilvánvaló!) 74

Vannak dolgok, amikre ügyelni kell, amikor a bonyolultságelméletet a kriptográfiában alkalmazzuk. Amikor például az id beli komplexitást vizsgáljuk a polinom fokszáma 1000 loglogn sokkal-sokkal lassabban növekszik, mint n , de fontos jellemz . Például n ennek ellenére el fordulhat, hogy az utóbbi érték még mindíg nagyon szerény becslés a vizsgált értékek fels határára. A kriptográfiában az átlagos komplexitás sokkal fontosabb, mint a legrosszabb eset komplexitása. Tegyük fel például, hogy egy felhasználó egy nyiltkulcsú kriptorendszerben véletlenszer en választja meg a titkosítási kulcsot. Ezek után nincs jelent sége annak, hogy a megoldási kulcs megkeresése néhány ritkán el forduló esetben kiszámíthatatlan, 96 de (aránylag) könnyen meghatározható a legtöbb esetben. ValószínNségi vagy sztohasztikus algoritmusokat gyakran használnak a kriptográfiában. Ráérezhetünk, hogy ez azt jelenti, hogy véletlenszer en választunk meg bizo97 nyos értékeket, amelyeket a számítások során felhasználunk. Ilyen esetekben olyan algoritmusokról beszélünk, amelyek véletlenszerN polinomiális id"ben (Random Polynomial Time) futnak. E problémák osztályát gyakran nevezik BPP-nek. Úgy sejtik, hogy általában BPP NP. Az véges valószín séggel el fordulhat, hogy egy sztochasztikus algoritmus nem vezet eredményre, de ennek a valószín sége tetsz legesen kicsinnyé tehet . Rendszerint persze az id beli komplexitás növekedése árán csökkenthet a sztochasztikus algoritmusok eredménytelenségének a valószín sége. Az eredménytelenség egyébként éppen a sztochasztikus elem következménye. Mellesleg az eredménytelen eseteket is különböz osztályokba sorolják és ezekre a következ terminológiát alkalmazzák: A Monte Carlo algoritmusok néhány esetben hibás eredményre vezethetnek. Az un. Las Vegas algoritmusok mindig korrekt választ adnak a problémára, de ilyen korrekt válasz lehet az is, hogy „nem tudom a választ”. Amikor id beli bonyolultságról beszélünk, akkor a gyakorlatban rendszerint nem egy Turing gép lépéseinek a számát vizsgáljuk, hanem sokkal inkább valamilyen más, ismétl d elemi m velet számát, pl. a bit szorzást. A P és az NP osztályok invariánsak az ilyen változtatásokkal szemben, de pl az alkalmazott polinomok fokszáma és/vagy az együtthatói változhatnak.

96

Ezért állítja Nichols professzor a Knapsack titkosításról, hogy az nem eléggé megbízható. Ténykérdés, hogy az általa leírt szempontokon kívül még további, járulékos szempontokat is érvényesíteni kell a modulus megválasztásakor ahhoz, hogy El Gamal algoritmikus feltörési módszere ne legyen alkalmazható. Nevezetesen arról van szó, hogy célszer< olyan modulust alkalmazni, amelynek 1-gyel megnövelt értéke mindössze két prímfaktorral rendelkezik. Nichols professzor leírt eljárása ezt nem köti ki, bár e jegyzetben bemutatott mintapéldájához pontosan így választotta meg a modulust. A III. Függelék végén bemutatott példában mi is így választottuk meg a modulust.

97

A kriptográfia bevezetésekor volt is szó arról, hogy csakis valódi véletlenszámokkal dolgozhatunk és az un. kvázivéletlenszám-generátorok nem alkalmazhatók, vagy csak olyan korlátozással, hogy a generálás un. kiinduló „magja” (= seed) esetr l esetre változik és ezeket a „magokat” tényleg véletlenszer<en generáljuk. 75

A következ táblázat azt mutatja, hogy különböz bonyolultságok esetén milyen szint er feszítésekre van szükség a probléma megoldásához. Figyeljünk fel arra, hogy a bemenetek száma milyen módon korlátozott a faktoriális és az exponenciális esetekben, miközben különböz bonyolulultságú algoritmusokat kezelünk. Bonyolultság (komplexitás) log2 n

Méret

12

10

12

10

12

12

10

12

2^10 = 10^ e

e^

A mLveletek száma

150

= 10

65

n

10

n

2

10

6

10

12

n

6

10

2

10

12

2

n

28

10

12

n!

15

10

12

76

II.

FÜGGELÉK Az RSA titkosítás demo programja

Tóth Gergely programozó matematikus (Ker-Soft Kft.) jóvoltából az SzGTI intranet hálózatán megtalálható egy RSA demo program, amely NT alapú Windows rendszerek alá a Windows installer segítségével telepíthet és itt, ebben a függelékben, leírjuk a használatát. A program szemlélteti az RSA titkosításhoz használt matematikai apparátus valamennyi elemét, valamint pontosan azt a titkosítási algoritmust, amit „Az RSA algoritmus” c. fejezetben (az 55. oldalon) leírtunk. Az egyes funkciók a program eszköztárán található ikonokkal vagy az „Eszközök” menüben található menüpontokkal indíthatók. Az RSA algoritmus szempontjából dönt fontosságú prímszámok meghatározását a „Prímszámok keresése” menüpontból indíthatjuk. A program maga az Eratoszthenészi szita algoritmusát használva keresi a prímszámokat egy a felhasználó által el re meghatározott fels korlátig. Hasonlóképpen alapvet fontosságú a számok törzstényez kre bontása, a faktorizációs probléma megoldása. A probléma maga az el bbi prímszám keresés problémájára vezethet vissza. Az el bb felépített prímszám táblázat segítségével egy adott szám prímfaktorainak meghatározása elég könnyen elvégezhet . A harmadik segédeszköz, amelyre az RSA algoritmus implementálása során szükségünk lesz, egy szám modulo m' inverzének meghatározása. Emlékeztet ül: definició szerint az a és b egészek egymás inverzei valamely m' modulusra nézve, ha szorzatuk a modulussal 1 maradékot ad, azaz: ab = 1 mod m'

77

E három eszköz segítségével bátran nekiláthatunk implementálásának. Az „RSA varázsló” menüpont lépésr l lépésre vezet végig a kezdeti adatok megadásától egészen a tényleges kódolásig és dekódolásig.

az

RSA

algoritmus

Az els panelen az RSA algoritmus alapjául szolgáló p1 és p2 prímszámokat adhatjuk meg. Az adatok bevitelét követ en a panelen látható a prímek szorzata m = p1,p2

78

és ú.n. Euler-függvényük értéke (m) = ( p1 ,p2) = (p1 -1)( p2 -1) melyeket használni fogunk az algoritmus során. A következ panelen határozhatjuk meg a rejtjelzéshez használandó e számot – publikus kulcs - úgy, hogy e és (m) relatív prímek legyenek: (e, (m)) = 1 A publikus kulcs megválasztása után a panelen megnik az e érték d inverze a (m) modulusra nézve, alyet a dekódoláshoz fogunk használni. Természetesen a „Publikus” és „Privát” jelz k szerepe abszolult önkényes, hiszen e és d szerepe nyilvánvaló módon felcserélhet . A harmadik lépésben magára a kódolásra és dekódolásra láthatunk példát. Az „Üzenet” kifejezést ugyanolyan értelemben használjuk, mint ahogy az az algoritmus leírásában szerepel: egy 0 < x < m közötti numerikus értéket kell megadni. Kódoláskor az „Eredmény” mez ben az y := xe mod m függvény értéke jelenik meg, míg dekódoláskor az y := xd mod m függvény értékét kapjuk.

79

TÁRGYMUTATÓ absztrakt automata

63

elektronikus aláírás

16, 17, 18, 20

AES

33

élettartam (kriptorendszereké)

31

affin

46

alaphalmaz

20

Elliptic Curve Discrete Logarithm Problem: ECDLP

37

állapotfüggvény

65

aszimmetrikus kriptográfia

23

aszimmetrikus titkosítási módszer

17

aszimmetrikus üzenet-titkosítás

17

átlagos komplexitás

elliptikus görbe diszkrét-logaritmus 28 elõd

49

Euler-függvény

41

exponenciális idõ-komplexitás

69

71

Faktor (n)

28

authentikáció

14

faktorizáció

belsõ állapot

64

hatvány maradékosztálya

bemeneti állapot

64

Hellman

bemeneti szalag

63

hibrid rendszerek

19

bit szorzás

71

IDEA

33

idõbeli komplexitás

61

illetékesség

14

injektív leképezés

20

blokk-titkosító módszer

5

bonyolultságelmélet

7, 61, 70

bonyolultsági osztály

27

brute force method

9

37, 39, 61, 68 50

6, 20, 36, 37, 39, 46

Integer Factorisation Problem: IFP 36

Certification Authority( CA)

16

intractability

Complexity Theory

61

inverz

51

kemény NP-komplett probléma

68

csapóajtó függvény

9, 10, 21, 26, 27

9

DES

33

képhalmaz

20

DES-Cracker

29

képtartomány

20

determinisztikus automata

64

kijelentéskalkulus jól formált formulái (kkjff) 69

determinisztikus idõbeli komplexitás 67 Diffie

6, 20, 29, 31, 36, 37, 39, 46

Digital Signature Algorithm: DSA

36

diszkrét idõlépték

62

diszkrét logaritmus

28

El Gamal

65

kiszámíthatatlan probléma

66

Kiszámíthatatlanság

9

knapsack megfejtési algoritmus

57

knapsack problems

11

Knapsack titkosítás

11

9, 10, 13, 20, 21

knapsack vector

12

11, 36, 37, 71

knapsack vektor

15

diszkrét logaritmusok problémaköre (DLP). 36 egyirányú függvény

kimeneti függvény

80

kommunikációs busz komplexitás

29

26, 61, 62, 65, 67, 70-72

NP TERJ

70

nyers erõ módszere

9

kompromittál

7

nyiltkulcsú kriptorendszerek

13

kongruencia

3

nyitott titkosítási rendszer

14

12

osztályozás (kriptográfiai algoritmusoké)

36

Kongruenciák szerepe könnyû probléma

11, 12

kriptanalítikus

61

õstartomány

20

kriptográfiai funkcionalitás

37

összeg maradékosztálya

50

kulcs szerver

16

P osztály

67

kulcs-hitelesítés

16

párhuzamosítás

29

kulcskarika

16

password

20

kulcs-menedzsmen

32

passzív lehallgatás

25

kulcs-menedzsment

19, 23, 32, 33

Personal Key Infrastructure

15

kvadratikus residuum

28

PGP

33

Las Vegas algoritmusok

71

PKI

14

lefedési probléma

12

legrövidebb út

67

polinomiális idõ 68, 71

lineáris helyettesítés

46

maradékosztály

3

7, 11, 26, 27, 62, 63,

polinomiálisan behatárolt (Turing gép) 66

maszk

13

polinomiálisan behatárolt nondeterminisztikus Turing gép

megállási probléma

64

polyalfabetikus rendszer

megfejtési algoritmus Merkle

9 6, 37, 46

67 8

polynomial time

11

predecessor

49

Merkle-Hellman séma

12

Prímszám-ellenõrzés

28

mod m szorzás

16

P-TERJ

70

Monte Carlo algoritmusok

71

Random Polynomial Time

71

Moore törvény multiplikatív inverz

21, 29 3

reláció

3

RSA

37

munkatartomány

64

RSA algoritmus

40

munkatényezõ

29

RSA titkosítás demo

73

nem polinomiális problémák

11

nemdeterminisztikus Turing gép

67

Salomaa 7, 8, 10, 11, 20, 26, 46, 49, 61, 65, 67, 69, 70

NP komplettség

11

Schnorr-féle digitális aláírási módszer. 36

NP osztály

67

sorvektor

13

NP problémák

11

Space complexity

70 81

spontán kezdeményezett üzenetküldés 32 spontán kommunikáció

16

successor

49

számelméleti problémák

28

szigorúan egyirányú függvények

20

szorzat maradékosztálya

50

sztohasztikus algoritmus

71

szupernövekvõ sorozat terjedelem-komplexitás

többábécés rendszer

8

tractable problems

10

transzformációk

9

trapdoor function

9

Turing gép

7, 10, 62, 66

unicitás

13, 15

utód

49

16

well-formed formulas of the wffpc propositional calculus

69

70

work factor

7, 29

82

SZAKIRODALOM [1]

Randall K. Nichols: ICSA (= International Computer Security Association) Guide to Cryptography. McGraw-Hill, 1999. ISBN 0-07-913759-8

[2]

F.L.Bauer: Decrypted Secrets. Methods and Maxims of Cryptology. Springer Verlag 1997. ISBN 3-540-60418-9

[3]

Randall K. Nichols, Daniel & Julie Ryan: Defending Your Digital Assets. McGraw-Hill, 2000. ISBN 0-07-212285-4

[4]

Randall K. Nichols: Classical Cryptography Course Vol.1 & Vol2. Aegean Park Press CA-USA 1996. ISBN 0-89412-263-0 & 0-89412-264-9

[5]

Bernard Sklar: Digital Communications – Fundamental and Applications Prentice Hall Inc. 1998. ISBN 0-13-212713-x025

[6]

Ködmön József: Kriptográfia. Computer Books Kiadói Kft, Budapest 1999/2000. ISBN 963 618 224 8

[7]

New Directions in Cryptography. IEEE Transactions on Information Theory, IT22 Vol 6. pp.644-654. (1976)

[8]

T.Dénes Tamás: Kódtör ABC (Titoktan Trilógia 1.rész) Bagolyvár Könyvkiadó. Bp.2002. ISBN: 963 9447 04 8

[9]

Handbook of Applied Cryptography by Alfred J. Menezes at Al CRC Press, 1997. ISBN: 0-8493-8523-7

[10] Practical Cryptography by Niels Ferguson & Bruce Schneier Wiley Publishing Inc.2003. ISBN: 0-471-22357-3 (Paperback)

83