Kriptográfia a középiskolában

Csirmaz László
Közép Európai Egyetem

Az elmúlt évtizedben a kriptográfia -- a titkosírás tudománya -- mindennapjaink fontos elemévé vált. Az internetes vásárlásról vagy internetes banki szolgáltatásokról természetesen mindenki hallott. De a kriptográfiának nélkülönözhetetlen szerepe van a mobil telefóniában, a kábeltévénél, az elektronikus adóbevallásnál, az egyablakos ügyintézésnél, sőt minden egyes bankkártyával való fizetésnél is. Nagyon fontos tehát, hogy ha nem is részleteiben, de nagy vonalakban a diákok is megismerjék és megértsék a kriptográfiai eljárások mögötti gondolatokat. Ez annál is fontosabb, mert a nagyközönség számára a kriptográfia fekete mágia, amihez csak a beavatottak értenek. Amennyiben mindenki pontosan tudná, mit lehet megcsinálni, mi az, ami szükséges és mi az, ami szükségtelen, sokkal kevésbé tudnának a nagy rendszerek gazdái (állami hivatalok, nagyvállalatok, bankok) visszaélni a kezükben összpontosuló hatalommal. Ha biztonságos bankkátyás fizetéshez nincs szükség sem a pin kódra, sem a személyi igazolványra, akkor miért kötelező ezek használata? Ha egy banknak minden eszköz rendelkezésére áll ahhoz, hogy lehetetlenné tegye a jogtalan bankkártyahasználatot, akkor miért az ártatlan és gyakran semmiről sem tudó ügyféllel fizetteti meg a bank gondatlanságából származó kárt?

A cikkben több különböző kriptográfiai eljárás modellje szerepel; ezeket egy-egy osztályfoglalkozáson dolgozhatjuk fel. Megpróbáltam rámutatni a lényeges, fontos tulajdonságokra, illetve némi kitekintést is adni az "igazi" módszerekre is.

1. Első titkos üzenet

Elsőként a kulcsegyeztetésről lesz szó. Ez a modern kriptográfia egyik első, talán legmeglepőbb alkalmazása. Arról szinte mindenki hallott, hogy hogyan lehet titkos üzeneket küldeni. A két fél megegyezik valamilyen módszerben, majd megválasztják a titkosíráshoz használt kulcsot, amit mindketten használnak: az egyik a titkosításra, a másik a titkosított üzenet visszafejtésére. Ahhoz tehát, hogy egyátalán titkos üzeneteket tudjanak egymásnak küldeni, meg kell egyezniük egy közös kulcsban, amit csak ők ketten tudnak. Ezt az eljárást hívják kulcsegyeztetésnek.

A feladat tehát az, hogy ketten, akik korábban soha nem találkoztak, egyezzenek meg egy közös titokban (a kulcsban). Ennek eléréséhez egymásnak üzeneteket tudnak küldeni, de ezeket az üzeneteket bárki le tudja hallgatni. Hogyan tudják mégis elérni, hogy legyen olyan közös titkuk, amit a lehallgató nem tud kitalálni?

A demostráláshoz osszuk az osztály tanulóit három csoportba. A két szélső csoport kapja a két fél szerepét, akik egy közös kulcsban akarnak megállapodni, de csak a középsőn keresztül tudnak egymásnak üzenni. A feladat az, hogy az egyik szélső csoport juttasson el egy üzenetet a másik oldalra úgy, hogy a középső társaság ne tudja meg, mi is az üzenet.

A kulcs megállapításához küldött üzenetet egy másfél méteres lánc jelképezi, aminek a két vége a jobb megkülönböztethetőség kevéért más-más színű. Az üzenetet azzal titkosíthatjuk -- azaz más számára értelmezheteten zagyvasággá változtathatjuk --, ha a lánc két végét egy lakattal lezárjuk. Mindhárom csoport kap egy-egy lakatot a hozzá tartozó kulccsal; persze egy lakatot csak a hozzá tartozó kulcs tud kinyitni.

A nyitott láncot az egyik szélső csoport kapja meg, és ezt kell átjuttatnia a másik oldalra. Persze a láncot nem szabad dobni, csak átadni. Sőt, minden lépést előre meg kell beszélni, hogy mindenki (beleértve a középső csoport tagjait is) pontosan tudja, hogy mi fog történni. Közben el kell érni, hogy a középső csoport ne kapja meg a láncot lelakatolatlanul, és ne is tudja egyszer sem kinyitni.

A középső csoport ráadásul mindent "lemásol," ami átmegy a kezén. Ez azt jelenti, hogy a lakat, a kulcs, vagy a lelakatolt lánc képét megtarthatja magának. Ha a lelakatolt lánc képe és a megfelelő kulcs képe is nála van, a láncot kinyithatja, és megnyerte a játékot.

Az nem jó módszer, hogy a láncot az első csoport a saját lakatjával lezárja, a lakat kulcsát átküldi, majd mikor a kulcs megérkezett, a lelakatolt láncot küldi el. Az sem működik, hogy elkéri a másik csoporttól a lakatot a kulccsal együtt, és azzal zárja le a láncot, hiszen ekkor a lakatot nyitó kulcs képe már ott van a középső csoportnál. A megoldás: az első csapat lelakatolja a láncot, és azt így átküldi a harmadiknak. A harmadik felteszi saját lakatját is, majd a láncot a két lakattal visszaküldi. Az első csapat leszedi saját lakatját, és a most már csak a harmadik csapat lakatjával lezárt láncot küldi vissza. Ekkor a harmadik csapat ki tudja nyitni a láncot. A középső csapat nem látott egyetlen kulcsot sem, tehát nem tudja kinyitni a láncot.

A két lakat kinyitása nem a természetes sorrendben történt, hanem "fordítva". A zoknit előbb vessszük fel mint a cipőt, viszont amikor levetkőzünk, előbb a cipőt kell levenni. Ebben az esetben varázslatosan előbb a zokni került le a lábról és csak utána a cipő!

Ez az oka annak, hogy lánc helyett nem használhatunk lelakatolható dobozt, mondjuk a következőképpen. Az első csoport az átküldendő üzenetet egy dobozba teszi, amit lelakatol. A dobozt átküldi a harmadik csoportnak. Ők ezt a dobozt egy nagyobb dobozba teszik, amit ők lakatolnak le. A nagy dobozt, benne a kicsit, és abban az üzenetet visszaküldik az első csoportnak. Most az első csoportnak ki kellene nyitni a saját dobozát -- de nem fér hozzá, hiszen az be van zárva a nagy dobozba. A cipő most nem engedi, hogy a zoknit levegyük a lábunkról.

Most képzeljük el, hogy a lánc pontos útjának megbeszélése után a két szélső csoportot külön-külön terembe küldjük, a középső csoport tagjai pedig a folyosón járkálhatnak. A két szélső csoport tagjai a láncot a folyosóra nyíló ajtón adhatják át a középső csoport tagjainak, de azt, hogy azok mit csinálnak a lánccal, már nem látják. Hogyan tudná ezt a lehetőséget a középső csoport kihasználni?

Megtehetik, hogy egyáltalán nem adják tovább a láncot, hanem saját lakatjukat teszik rá, és így adják vissza az első csoportnak. Ők leveszik sajátjukat, és ekkor a középső csoport ki tudja nyitni a láncot. Ha pedig még egy láncuk is van, akkor a középső csoport ezt a másik láncot használva saját lakatjával át tudja adni a harmadiknak, mintha az jött volna az elsőtől. Ezzel a középső társaság mindkét oldal láncát ki tudja nyitni, a két szélső csoport pedig nem tudja, hogy a másik nem az ő láncát látta.

Hogyan tudná a két szélső csoport elérni, hogy a középsők ne csapják be őket? Nyilván elég, ha mindketten ismerik a másik lakatját. De az is elegendő, ha csak az egyik tudja, milyen lakatja van a másiknak. De mi a helyzet, ha a középső csoport lakatja megszólalásig hasonlít valamelyik szélső csoport lakatjához?

További érdekes lehetőséget jelent, ha egy lakathoz több kulcsunk is van, vagy ha egy kulcs egyszerre több lakatot is ki tud nyitni. Hogyan lehetne ezeket ügyesen felhasználni akár az átvitel biztonságosabbá tételére, akár annak támadására?

Az itt ismertetett eljárás az úgynevezett aszimmetrikus kódolású kulcsegyeztetés protokollja. A két résztvevő -- a két szélső csoport -- a protokoll végére olyan közös információval rendelkezik (ez a közös titkos kulcs), amiről az üzenetek lehallgatójának (középső csoport) semmi információja nincsen. A további üzenetváltáshoz a résztvevők már az így rendelkezésre álló közös adatot használhatják titkosírási kulcsként

A protokoll előbb bemutatott támadása -- amikor a középső csoport saját lakatját használva az első csoportot becsapja -- tulajdonképpen azonosítási probléma. Az első csoport a protokoll végére nem csak azt szeretné tudni, hogy valakinek sikerrel elküldte az információt úgy, hogy közbülső személy nem tudhatta meg annak tartalmát, hanem azt is szeretné tudni, hogy ez a valaki éppen a harmadik csoport, és nem más. A protokoll a bemutatott formájában ezt nem tudja garantálni. Ez a támadás annyira általános, hogy külön neve is van: valaki középen (men in the middle). A közkézen forgó térténet szerint ugyanezt a módszert használta az a kislány, aki két sakknagymesterrel vívott levelező játszmájának egyikét megnyerte: mindkét ellenfelének lépését elküldte a másiknak mintha azt ő lépte volna.

2. Csak amit muszáj -- milliomosok vetélkedője

A feladat megoldásához egy többrésztvevős protokollt kell terveznünk. Mindegyik résztvevő rendelkezik valamilyen információval, amit nem kíván a többivel megosztani, ugyanakkor mindannyian kíváncsiak egy olyan értékre, amit ezekből az adatokból lehet kiszámítani. A milliomosok az alábbi függvény értékét szeretnék kiszámítani:

	1   ha x >= y és x >= z
f(x,y,z) =	2   ha x < y és y >= z
	3   egyébként

ahol x helyébe az első, y helyébe a második, z helyébe pedig a harmadik milliomos vagyona kerül, hiszen ez a függvény éppen azt mondja meg, amire kíváncsiak. Olyan eljárást keresünk tehát, ami résztvevők adataiból kiszámítja a kért végeredményt, miközben a résztvevők a végeredményen (és az abból levonható következtetéseken) kívül semmi mást nem tudnak meg. A kriptográfia egyik gyönyörű eredménye, hogy ezt el lehet érni. Ha egy hitelfelvételhez igazolnom kell, hogy van rendszeres, adott értéket meghaladó havi jövedelmem, akkor ezt az igazolást úgy is meg lehet tenni, hogy a hitelező ezen az egyetlen információn kívül mást ne tudjon meg -- nevezetesen azt sem, hogy ki a munkáltatóm, és pontosan mennyi is a rendszeres jövedelmem. Ezeket szükségtelen tudnia, és hitelező könnyen visszaélhet ezekkel az adatokkal.

Bemelegítésként nézzünk egy olyan, sokakat izgató feladatot, ami viszonylag egyszerűen megoldható. A feladat: számítsuk ki egy összejövetelen a megjelent hölgyek életkorának átlagát. A probléma az, hogy a hölgyek közül senki sem akarja elárulni, hogy pontosan hány éves. Vagy határozzuk meg mennyi az osztály zsebpénzének átlaga, amit anélkül kell kiszámítanunk, hogy bárki megmondaná saját zsebpénzének összegét.

A megoldáshoz mindössze egy jegyzettömb és egy ceruza kell. A résztvevő holgyek közül valaki a jegyzettömb legfelső lapjára írjon fel egy véletlen, mondjuk hatjegyű egész számot anélkül, hogy azt bárki másnak megmutatná. A lapot letépi, és elteszi a zsebébe. Ezután a saját életkorát hozzáadja a véletlen számhoz, felírja a jegyettömb legfelső lapjára, és továbbadja a következő résztvevőnek.

Mindenki más, amikor megkapja a jegyzettömböt, leveszi a felső lapot, a rajta levő számhoz hozzáadja saját életkorát, és az összeget felírja a jegyzettömb legfelső, üres lapjára. A levett lapot pedig apró fecnikre tépi szét, majd a jegyzettömböt továbbadja a társaság következő tagjának.

Mikor a jegyzettömb már mindenkinél volt, az visszakerül az első résztvevőhöz. Ő levonja az összegből az általa kitalált véletlen számot, és megkapták az életkorok összegét. Ezt már csak el kell osztani a résztvevők számával ahhoz, hogy a keresett átlag meglegyen.

A protokoll természetesen a helyes értéket számítja ki, és biztonságos is, ha a résztvevők becsületesen játszanak: mivel az első hölgy egy nem kitalálható véletlen számot választ, senki sem tud meg semmit a többiek életkoráról. De ha néhány játékos titokban koalícióra lép, többlet információhoz tudnak jutni. Például két másodszomszédos játékos összebeszél, az első megjegyzi, hogy milyen számot írt a jegyzettömbre amikor továbbadta, a másik meg megjegyzi, mekkora szám volt rajta, amikor megkapta. A két szám különbsége éppen a közöttük álló életkora. Ezeket az ügyeskedéseket ki lehet védeni bizonyos többlet feltevésekkel és a protokoll elbonylításával.

Az életkorok átlagát egyszerűen kiszámítottuk. A milliomosok kérdésének eldöntésére is létezik protokoll, de sokkal bonyolultabb. Az itt következő, korántsem tökéletes megoldás is kellően bonyolult, viszont tartalmazza azokat az általánosan használható ötleteket, amiket ügyesen használva már minden feladatot meg lehet oldani.

Legyen a három gazdag ember Alíz, Bob és Cecil, vagyonuk piculában kifejezve A, B illetve C. Mindegyik tudja, hogy mennyi a saját vagyona, és kíváncsiak arra, hogy melyiküké a legnagyobb -- anélkül, hogy bármelyiküknek meg kellene mondania ezt az értéket. Az ötlet az, hogy együttesen meghatároznak két pozitív a és b számot úgy, hogy ezek pontos értékét egyikük sem tudja, majd közösen kiszámolják az f(x) = ax+b függvény értékét az x=A, az x=B és az x=C helyen. Minthogy az f(x) függvény szigorúan monoton növekszik, és mindnyájan ismerik az f(A), f(B), f(C) értékeket, meg tudják határozni, hármójuk közül ki a leggazdagabb, ki a következő és ki az utolsó. Ugyanakkor mivel sem az a sem a b értékét nem ismerik, nem tudják megmondani, kinek mekkora a vagyona. A protokoll eredményeképpen azonban milliomosaink nem csak azt tudják meg, hogy az A, B, C számok milyen nagyságrendben követik egymást, hanem valamivel többet. Tételezzük fel, hogy a számolás végeredménye úgy adódik, hogy az f(A), f(B), f(C) értékek számtani sorozatot alkotnak. Ekkor Bob nem csak azt tudja meg, hogy az ő vagyona a másik kettő között van, hanem azt is, hogy az egyinek pontosan annyival van több pénze, mint amennyivel a masiknak kevesebbje (vagyis ekkor az A, B, C értékek is számtani sorozatot alkotnak). Ez azért van így, mert az f(x) függvény lineáris. Ha f(x)-nek egy pozitív együtthatós másodfokú függvényt választanánk, a protokoll még kevesebb extra információhoz juttatná a résztvevőket.

De hogyan tudják a milliomosok kiszámítani az ax+b függvény értékét, ha sem az a, sem az x, sem a b értékét nem tudja egyikük sem? Az ötlet az, hogy mindhárman tudnak valamit, ami külön-külön nem elég ahhoz, hogy kérdéses értékeket meghatározzák, viszont együttesen már elegendő. A műveleteket ezeken a részadatokon kell ügyesen elvégezniük.

Minden értéket, amivel számolni fognak, három szám összegeként írunk fel. Mindhárman e három szám közül kettőt ismernek. A hiányzó harmadik szám biztosítja, hogy a kérdéses számot -- vagyis az összeget -- egyikük sem ismeri. A protokoll folyamán mindannyian egy-egy háromoszlopos táblázat sorait töltik ki. A három oszlopot A-val, B-vel, C-vel jelölve Alíznél az A oszlop, Bobnál a B, és Cecilnél a C oszlop hiányzik.

	Aliz				Bob				Cecil
A vagyona	Aa	Ab	Ac		Aa	X	Ac		Aa	Ab	X
B vagyona	X	Bb	Bc		Ba	Bb	Bc		Ba	Bb	X
C vagyona	X	Cb	Cc		Ca	X	Cc		Ca	Cb	Cc

A protokoll kezdetekor mindhárman kitöltik a táblázat első három sorát, melyben a megfelelő vagyonok összege szerepel. Természetesen Alíz ismeri saját vagyonát, ezt felírja mint három (nem feltétlenül pozititív) szám összegét: A = A_a+A_b+A_c. Ezek közül A_b-t és A_c-t beírja a saját táblázatába, majd elküldi az A_a és A_c értékeket Bobnak, az A_a és A_b értékeket Cecilnek. Az elő sor kitöltődött mindhárom táblázatban, és persze sem Bob, sem Cecil továbbra sem ismert Alíz vagyonának értékét. Hasonlóan Bob is felbontja saját vagyonát három szám, B_a, B_b és B_c összegére, a megfelelőket elküldi Alíznek és Cecilnek, a saját táblázatába pedig beírja a B_a és B_c értékeket.

Következő lépésként az f(x) függvény a és b pozitív együtthatóit választják meg. Az kell elérniük, hogy egyikük se tudja, mik ezek az értékek. A legegyszerűbben ezt úgy tudják megtenni, hogy Alíz választ két pozitív a1 és b1 értéket, Bob választja a pozitív a2 és b2 számokat, Cecil pedig az a3, b3 számokat. Ekkor a=a1+a2+a3 és b=b1+b2+b3 megfelelő lesz: ezek pozitívak, és egyikőjük sem tudja a és b pontos értékét.

A táblázat következő nyolc sora ezeket az értékeket tartalmazza. Az a1, b1 jelű sorok tartalmát Alíz mondja meg a többieknek (és saját magának); az a2, b2 sorokét Bob, az a3, b3 sorokét pedig Cecil, persze mindenki mindenki másnak csak annyit árul el, amennyit azoknak tudniuk kell. Alíz tehát felbontja a1-et és b1-et három-három pozitív szám összegére: a1=a1_a+a1_b+a1_c valamint b1=b1_a+b1_b+b1_c, és a megfelelő értékeket a saját táblázatába beírja, illetve elküldi Bobnak és Cecilnek:

	Aliz				Bob				Cecil
a1	a1a	a1b	a1c		a1a	X	a1c		a1a	a1b	X
b1	b1a	b1b	b1c		b1a	X	b1c		b1a	b1b	X
a2	X	a2b	a2c		a2a	a2b	a2c		a2a	a2b	X
b2	X	b2b	b2c		b2a	b2b	b2c		b2a	b2b	X
a3	X	a3b	a3c		a3a	X	a3c		a3a	a3b	a3c
b3	X	b3b	b3c		b3a	X	b3c		b3a	b3b	b3c
a=a1+a2+a3	X	ab	ac		aa	X	ac		aa	ab	X
b=b1+b2+b3	X	bb	bc		ba	X	bc		ba	bb	X

Az a és b sorok kitöltéséhez nincs szükség további üzenetre: az a jelű sor minden oszlopába az a1, a2, a3 sorok megfelelő oszlopaiban álló számok összege kerül; a b jelű sorba pedig a b1, b2, b3 sorok összege. Mivel mindhárom milliomos az a1, a2, a3 sorok közül kettőben nem ismeri a saját oszlopában álló számot, azért egyikük sem tudja, hogy az $a$ sorban a saját oszlopában milyen szám fog állni. Vagyis együttesen kitaláltak egy olyan $a$ számot, aminek értékét egyikük sem tudja, de hárman együtt már meg tudják határozni.

Már csak az f(x)= ax+b függvény értékét kell kiszámítaniuk az x=A, x=B és x=C helyeken. Nézzük például az f(A) értéket:

f(A)	=
	=   aA+b
	=   ( aa+sb+ac )( Aa+Ab+Ac ) + ( ba+bb+bc )
=   ( ab*Ab+ab*Ac+ac*Ac+bb )	+ ( ac*Ac+ac*Aa+aa*Ac+bc )	+ ( aa*Aa+aa*Ab+ab*Aa+ba )
	=   A1	+ A2	+ A3

Ha megnézzük a táblázatot, A1 értékét Alíz ki tudja számítani, hiszen nincs benne olyan érték, ami ő ne ismerne. Hasonlóan A2 értékét Bob, A3 értékét pedig Cecil tudja kiszámítani. Táblázatunk következő három sora tehát az A1, A2, A3 értékeket fogja tartalmazni, az azt követő pedig ezek összegét, vagyis f(A) értékét:

	Aliz				Bob				Cecil
A1	A1a	A1b	A1c		A1a	X	A1c		A1a	A1b	X
A2	X	A2b	A2c		A2a	A2b	A2c		A2a	A2b	X
A3	X	A3b	A3c		A3a	X	A3c		A3a	A3b	A3c
f(A)	X	fAb	fAc		fAa	X	fAc		fAa	fAb	X

Ismét Alíz az általa kiszámított A1 értéket felírja három szám összegeként: A1=A1_a+A1_b+A1_c, saját táblázatába beírja az A1_b és A1_c számokat, Bobnak és Cecilnek meg elküldi az ő táblázatukba kerülőket. Mikor mindhárman kitöltötték az A1, A2 és A3 sorokat, a sorok összegét be tudják írni az f(A) sor megfelelő helyeire. Végezetül Alíz elküldi az f(A) sorából a Bob oszlopában álló számot Bobnak, Bob elküldi a Cecil oszlopában álló számot Cecilnek, és Cecil elküldi Alíz oszlopában álló számot Alíznek. Ezek után mindhárman ki tudják számítani az f(A) értéket.

Hasonlóan számítják ki az f(B), valamint f(C) értékeket is, és végül mindhárman el tudják dönteni, hogy ki a leggazdagabb anélkül, hogy az eredeti összegeket megtudták volna.

A táblázatokban csillaggal jelöltük meg azokat a "letakart" mezőket, ahol álló értékeket a megfelelő résztvevő ismeri. Ezek azokban a sorokban állnak, amelyeket ő töltött ki. Az összes többi letakart helyen álló értékről senkinek sincs további információja.

Hasonló, de egyszerűbb módszerrel tudják eldönteni például, hogy Alíz gazdagabb-e mint Bob. Most csak Alíz és Bob küldi el a másik kettőnek a vagyonukat kifejező A_a, A_b, A_c, illetve B_a, B_b, B_c értékek közül kettőt-kettőt. Ezek után mindeki kivonja a táblázat első sorából a másodikat. Alíz gazdagabb mint Bob, ha a harmadik sorban álló számok összege pozitív, és szegényebb, ha ez az összeg negatív.

	Aliz				Bob				Cecil
A vagyona	Aa	Ab	Ac		Aa	X	Ac		Aa	Ab	X
B vagyona	X	Bb	Bc		Ba	Bb	Bc		Ba	Bb	X
A-B	X	Ab-Bb	Ac-Bc		Aa-Ba	X	Ac-Bc		Aa-Ba	Ab-Bb	X

Ahhoz, hogy eldöntsék, mi is a helyzet, először választanak egy a pozitív véletlen számot, melynek értékét egyikük sem tudja. Ezt ugyanúgy tehetik meg, mint korábban. Majd a fenti trükk segítségével kiszámítják az a*(A-B) értéket, amit már mindhárman megismerhetnek. Ennek előjele megegyezik az A-B előjelével, tehát megmondja, hogy Alíz gazdagabb-e vagy Bob. Mivel az a pozitív számot egyikük sem ismeri, nem fogják tudni, hogy Alíz és Bob vagyona között mekkora is a különbség.

3. Kockadobás telefonon, avagy vegyen el a gép kettőt

Hogyan lehet telefonon kockát feldobni? Hogyan tud Alíz és Bob megegyezni abban, hogy melyik menjen a másikhoz? Ha mindketten ugyanazon a helyen vannak, akkor az egyik feldob egy pénzdarabot, a másik meg megtippeli, hogy az írásra esett-e vagy fejre.

-- Feldobtam egy pénzt, most mondd meg mire esett -- mondja Alíz telefonba.

-- Fej -- tippeli Bob.

-- Sajnos vesztettél, mert írásra esett.

Hát ez nem volt meglepő, hiszen eshetett akár fejre is. Hogyan lehet elérni, hogy mindkét fél biztos legyen benne, hogy a másik nem csal?

A megoldás a kriptográfia egyik igen hasznos eszköze: az elkötelezés (commitment). Alíz elkötelezi magát a fej vagy írás mellett, és ezt egy lezárt borítékban Bobnak odaadja. Ezután Bob megtippeli a boríték tartalmát, majd kinyitják a borítékot és eldöntik, ki nyert. Itt persze a "boríték" nem igazi borítékot jelent, hiszen azt nem lehetne a telefonon átküldeni (még képként sem).

Ahhoz, hogy a borítékolást meg tudják csinálni, Alíznek és Bobnak mindössze két azonos kalkulátorra van szüksége. Megállapodnak egy bizonyos gombnyomás sorozatban: például a négyzetgyök kétszer, azután szinusz, koszinusz, szorozva pi-vel, majd négyzetgyök megint.

Alíz beír egy négyjegyű számot a kalkulátorba úgy, hogy az utolsó előtti számjegy mutatja, hogy fejre vagy írásra gondolt-e: ha ez a számjegy 0, akkor fej (mert a nulla kerek), ha 1, akkor írás. Ezután végrehajtja a megállapított gombnyomásokat, és a kijelzőn álló szám utolsó négy jegyét bediktálja Bobnak. Ez a négyjegyű szám biztosítja, hogy Alíz nem gondolhatja meg magát; viszont csak ebből Bob nem tudja kitalálni, mire is gondolt Alíz. Miután az "elkötelezettséget" felírta, Bob megmondja Alíznek saját tippjét. Válaszul Alíz kinyitja a borítékot, vagyis bediktálja Bobnak azt a számot, amit eredetileg írt a kalkulátorba. Ennek harmadik számjegye mutatja, hogy Alíz fejre vagy írásra gondolt-e, és Bob is ellenőrizheti, hogy Alíz nem csalt-e. Ugyanazokat a gombnyomásokat kell végrehajtania saját kalkulátorán, és összevetni az eredményt Alíz elkötelezettségével.

Ahhoz, hogy az eljárás biztonságos legyen, Alíznek biztosnak kell lennie abban, hogy Bob nem tudja kinyitni a borítékot, Bobnak meg azt kell tudnia, hogy Alíz nem tud olyan borítékot készíteni, amit többféleképpen is ki tud nyitni. Bob biztonságához nem az kell, hogy a borítékot egyátalán ne lehessen többféleképpen kinyitni, hanem csak annyi, hogy Alíz ne tudjon olyan borítékot csinálni, amit ő többféleképpen is ki tudna nyitni. Esetünkben Alíz a fej/írás mellé még három számjegyet választ, tehát 2000 különböző lehetőség van. A gombnyomogatás eredményeképpen négy számjegyet diktál le Bobnak, ami 10000 lehetőség valamelyike. Tehát azt várjuk, hogy nagy valószínűséggel Alíz elkötelezettségét -- a négyjegyű számot -- csak egyetlen módon lehet kinyitni. Ezért, ha Bobnak van ideje mind a 2000 lehetőséget végigpróbálni, megtalálja ezt a számot, és így megtudhatja mire gondolt Alíz. Minden próbálkozásnál a megfelelő számot be kell írni a kalkulátorba, lenyomni a megfelelő műveleti gombokat, azután ellenőrizni az eredményt. Ha mindez csak egyetlen másodpercig tartana (nem valószínű), akkor is több mint fél óráig tartana a lehetőségeken végigmenni. Ezért a biztonsághoz Bobnak azonnal kell tippelnie, miután meghallgatta Alíz "elkötelezettségét."

A kocka fordul, ha az első lépésben Alíz nem négyjegyű, hanem hatjegyű számmal kezd. Ekkor ugyanis várhatóan minden elkötelezettséget (négyjegyű számot) sokféleképpen is ki lehet nyitni, úgy is, hogy az eldugott számjegy 0, és úgy is, hogy ez a számjegy 1. Hiába számol Bob akármennyit, nem fogja tudni, hogy Alíz mire gondolt. Ekkor viszont Alíznek van előnye: ha ő tud nagyon gyorsan nagyon sokat számolni, akkor tud választani olyan négyjegyű elkötelezettséget, amit írásként is és fejként is ki tud nyitni. Ezért miután Alíz és Bob megállapodtak hogy a kalkulátoron milyen gombokat milyen sorrenben kell lenyomni, Alíznak gyorsan el kell küldeni az elkötelezettségét, hogy ne legyen ideje ravaszkodni.

Nem létezik olyan módszer, ami mind Alíz, mind Bob számára abszolút biztonságot jelentene. Itt és más kriptográfiai alkalmazásoknál meg kell becsülni a résztvevők lehetőségeit, rendelkezésükre álló erőforrásokat, és a feladatok bonyolultságát ezekhez kell illeszteni. Ha Alíz egy ügyfél, és Bob egy bank, akkor a második módszert választjuk, hiszen feltehetően egy bank jóval több erőforrást tud pillanatok alatt igénybe venni, mint bármelyik ügyfele.

Amikor Alíz és Bob megállapodtak abban, hogy milyen gombokat milyen sorrenben nyomjanak le a kalkulátoron, akkor egy függvényt definiáltak: az argumentum a kalkulátorba beírt szám, a függvény értéke a gomnyomások eredménye. Ez egy olyan függvény, aminek értékét könnyű kiszámolni, de nehéz invertálni: ha a adott a függvény értéke, nehéz megkeresni a hozzá tartozó (egyik) inputot. Ilyen egyirányú függvények nagyon fontos szerepet játszanak a kriptográfiában, és szinte mindegyikből lehet elkötelezettségi sémákat gyártani. Általános módszer egyirányú függvény gyártására egy hálózat készítése.

A "hálózat" nevét az elektronikából kapta. A hálózat alján a bemenő kapuk fogadják az input értékeket. A hálózat további szintjein ÉS valamint VAGY kapuk vannak; midegyik kettő (esetleg több) alatta levő kapuval van összekötve. A hálózat legfelső szintjén álló kapuk adják a hálózat kimenetét. Minden kapu értéke vagy 0 vagy 1. Ha tudjuk az alsó szinten álló kaput értékét, a hálózat többi kapujának értéket lentről fölfelé számíthajuk ki. Egy ÉS kapuba akkor kerül egyes, ha mindazon lentebb levő kapukban, amikkel ő össze van kötve, egyes áll. Egy VAGY kapuba akkor kerül egyes, ha valamelyik lentebb levő, vele összekötött kapuban van egyes. Az ábrán egy öt szintű hálózatot látunk; a jobb oldalon számítjuk ki, hogy mit is ad a hálózat az 101010 inputra.

Ilyen bináris (két értékű) hálózatoknál szokás még további kapukat is használni. A NÉS kapu eredménye az ÉS kapu eredményének ellentettje, hasonlóan NVAGY a VAGY kapu eredményének ellentettje. Ezek jölölése abban különbözik az ÉS valamint VAGY kapukétól, hogy a tetejükön még egy kis gombóc is van. Az összeadó vagy paritáskapu eredménye pedig akkor egyes, amikor a bementei között páratlan sok egyes található. Mivel az ÉS valamint VAGY kapukkal is megfelelő bonyolultságú hálózatokat tudunk készíteni, legalábbis eleinte, nem érdemes további kapukat is használni.

Alíz és Bob megállapodnak egy hálózatban -- például úgy, hogy Alíz készíti el a hálózat egyik felét, Bob meg a másikat. Ezek után Alíz a következőképpen rejti el a fej/írás eredményt: ha az inputban található egyesek száma páros, akkor fej, ha az egyesek száma páratlan, akkor írás. Alíz kiszámítja a hálózat értékét (vagyis a legfelső szinten álló kapuk értékét), és azt megmondja Bobnak.

Ahhoz, hogy a kezdeti értéket ne lehessen egyszerűen az összes lehetőség kipróbálásával könnyen megkeresni (ezt hívják a nyers erő alkalmazásának), a bemenő kapuk számát viszonylag nagyra kell választani. Hat bemenő kapu esetén mindössze 64 lehetséges input van, amiket nem nehéz mind végigpróbálni. Tíz bemenő kapunál ez a szám már 1024, húsz kapunál pedig már egymillió fölötti ez a szám. Ahogy a bemenő kapuk számát növeljük, a hálózat is egyre bonyolultabb és áttekinthetetlenebb. Így ahelyett, hogy a kapuk számát növelnénk, inkább megengedjük, hogy az egyes kapuk ne csak 0-t és 1-et, hanem tetszőleges számjegyet tartalmazhassanak. Az ÉS kapuk mondjuk az inputjukba írt számjegyek szorzatának utolsó jegyét adják eredményül, a VAGY kapuk pedig mondjuk az inputok összegének utolsó számjegyét. Ezzel hat bemenő kapunál a lehetséges inputok száma egymillióra nőtt, ami már meghaladja a kipróbálható inputok számát, ugyanakkor a hálózat értékét még mindig könnyen ki lehet számítani.

Egy lehetséges iskolai alkalmazásban a hálózatot minden tanuló ismeri. A bemenő számjegyek helyére mondjuk a dolgozat két példájának a végeredményét kell beírni. A tanár megadja a hálózat kimenetét, és így a tanulók ellenőrizhetik, hogy helyes eredményt kaptak-e. És mindezt anélkül, hogy az eredményt előre tudták volna!

A televízós műveltségi vetélkedőben az izgalom a tetőfokára hág. A tét több millió forint. A játékos a négy lehetséges válasz közül kettő között ingadozik, a másik kettőről biztosan tudja, hogy rossz. A két lehetőség közül az egyik jó. De melyik? Két segítsége már elment, maradt a felezés: a négy lehetséges válasz közül kettő rossz eltűnik, és csak a helyes és egy helytelen válasz marad meg. Ha a "felezés" véletlenszerű, akkor 2/3 esélye van arra, hogy az általa kiválasztott két, még lehetséges válasz közül az egyik eltűnjön, és immár biztos legyen abban, mi is a jó válasz. Igen ám, de honnan tudhatja, és honnan tudhatja a tévé előtt ülő sok néző, hogy a felezés tényleg véletlenszerűen történik, és sem a játékvezető, sem a műsor készítői nem manipulálják azt? Tudna az olvasó egy egyszerű, de mégis meggyőző eljárást ajánlani?

4. A fagylaltos kocsik hová álljanak?

Az ábrán egy kisváros úthálózatát láthatjuk; a csomópontokat a kis körök jelzik, ezeket utak kötik össze. Ha két út a térképen nem csomópontban keresztezné egymást, akkor a valóságban ott nincs is útkereszteződés, az egyik út a másik fölött vagy alatt vezet. Amikor nagyon meleg van, fagylaltoskocsik jelennek meg. Mindegyik egy-egy csomópontban árulja a finom hűsítő fagyit. Azért, hogy ne rontsák egymás üzletét, szomszédos csomópontokba nem állnak. Viszont az sem volna jó, ha valahonnan a legközelebbi fagylaltoskocsi túl messze kerülne. Így az lenne a legjobb, hogy ha valamelyik csomópontban nincs fagylaltoskocsi, akkor annak valamelyik szomszédjában már van. Meg lehet ezt csinálni? Ha igen, akkor hány fagylaltoskocsira van szükség?

A feladat tehát az, hogy egy gráf csúcsai közül válasszunk ki néhányat úgy, hogy a) a kiválasztott csúcsok között ne fusson él, de b) minden nem kiválasztott csúcs össze legyen kötve valamelyik kiválasztottal. Csúcsoknak ilyen halmazát lefogó rendszernek nevezik. Annak eldöntése, hogy egy gráfban létezik lefogó rendszer, NP-teljes probléma. Ez azt jelenti, hogy ilyet találni, ha van is, nagyon nehéz. Az összes lehetséges esetet -- vagyis a gráf csúcsainak összes részhalmazát -- végig kell próbálni, ennél lényegesebb gyorsabban nem tudunk célhoz érni. Az sem segít, hogy sok részhalmazról azonnal látszik, hogy nem lehet lefogó rendszer; sajnos túl sok megvizsgálandó eset marad. A diákok is meggyőződhetnek a feladat nehézségéről, ha néhányszor tíz-tizenöt csúcsú gráfban megpróbálnak lefogórendszert keresni.

Ilyen nehéz, szinte megoldhatatlan feladatot nagyon könnyen tudunk gyártani. Először kigondoljuk, mi lesz a megoldás: felrajzoljuk a csomópontokat, kijelöljük a fagylaltoskocsik helyét, és minden további csomópontot pontosan egy fagylaltoskocsit tartalmazó csúccsal kötünk össze (5.ábra). Azok között a csúcspontok között, ahol nincsenek fagylaltoskocsik, még további éleket húzunk be véletlenszerűen, hogy a végén nagyjából egyenletes legyen az úthálózat (6.ábra). A térképet szinte pillanatok alatt elkészíthetjük, a hozzá tartozó megoldás pedig a mi titkunk marad (5+6.ábra).

Alíz egy ilyen térképet használhat arra, hogy elkötelezze magát. Felrajzol egy térképet, amiben a fagylaltoskocsikat el lehet helyezni. Fejre gondol, ha a fagylaltoskocsik száma páros, és írásra, ha ez a szám páratlan. Könnyű látni, hogy ha van két lefogó rendszer is, akkor a benne levő csúcsok száma ugyanakkora kell legyen, ezért ez a módszer Bob számára abszolút biztonságos. Alíz számára az jelenti a biztonságot, hogy a feladat NP-teljes. Az ugyan nincs bizonyítva, hogy nincs gyors eljárás, ami minden gráfban megkeresné a lefogó rendszert, de ha Bob mégis találna ilyen eljárást, annak nagyon sok olyan következménye lenne, amiről a matematikusok nem hiszik, hogy igazak volnának. Ráadásul olyan fantasztikus matematikai eredményt érne el, amire sok tízezer kiváló elme több évtizedes kitartó munkával sem volt képes.

Alíz úgy tudja meggyőzni Bobot arról, hogy elkötelezettsége helyes volt, hogy megmutatja neki, mely csúcsokba kell tenni az adott számú fagylaltoskocsit -- vagyis megmutatja a feladat megoldását. Az, hogy ez tényleg jó megoldás, gyorsan és könnyen ellenőrizhető.

Azt, hogy minden lefogó rendszerben ugyanannyi elem van, a következőképpen láthatjuk be. Legyen $F_1$, $F_2$, ... és $G_1$, $G_2$, ... egy-egy lefogórendszer. Mindegyik $G_i$-hez pontosan egy olyan $F_j$ található, amitől legfeljebb egy távolságra van (mert az $F_j$-k lefogó rendszert alkotnak), és mindegyik $F_j$-hez pontosan egy ilyen $G_i$ (mert a $G_i$ csúcsok is lefogó rendszer alkotnak). Az egymáshoz tartozó $F$-beli és $G$-beli csúcsok mindkét esetben ugyanazok, hiszen csak így lehetnek vagy ugyanabban vagy szomszédos csúcsban. Ezért ez egy kölcsönösen egyértelmű leképezés, és így a két lefogó rendszer ugyanannyi elemű.

5. Nyilvános kulcsú titkosírás -- maszek alapon

Mi is a nyilvános kulcsú titkosírás? Olyan titkosítási eljárás, amelynél a nyilvános kulcs birtokában bárki tud titkosítani, de a titkosított üzenetet csak a titkos kulcs birtokában lehet visszafejteni.

Alíz nyilvános kulcsa egy várostérkép, amit mindenkinek odaad, aki titkosan üzenni akar neki. A titkos kulcs pedig a csúcsoknak az a részhalmaza, ahová a fagylaltoskocsikat el kell helyezni. Azt már láttuk, hogy a nyilvános kulcs -- vagyis a várostérkép -- ismeretében a titkos kulcsot csak kivitelezhetetlenül nagy munka árán lehet megkapni. Hogyan lehet a nyilvános kulcsot titkosításra használni, és hogyan lehet az üzenetet a titkos kulcs segítségével visszafejteni?

Viszonylag egyszerű térkép esetén az üzenet egyetlen számjegy, nagyobb térképnél ez akár két- vagy háromjegyű szám is lehet. Mondjuk Alíz nyilvános térképét a 9. ábrán láthatjuk, és az üzenetünk a 6-os számjegy. Ezt a következőképpen titkosítjuk: minden egyes csúcshoz az utolsót kivéve írjunk véletlenszerűen egy 0 és 9 közötti számjegyet; az utolsót pedig válasszuk meg úgy, hogy a felírt számjegyek összegének utolsó jegye az üzenet legyen. Egy lehetséges felírást a csúcsoknál álló kis méretű számjegyek mutatnak, mivel ezek összege 56 és az üzenet a 6 volt. Ezek után ezeket a számjegyeket elrejtjük: minden egyes csúcsba felírjuk az ottani és a csúcs szomszédaiban álló számjegyek összegének utolsó jegyét. Például a bal felső csúcsba 7-es kerül, mert 8+3+5+1=17; a jobb alsó sarokba pedig nulla, mert 5+4+6+5 nullára végződik. A kódolt üzenet a csúcsokhoz írt nagy számjegyekből áll. Mivel az előállításhoz csak a térképet használtuk, mindenki, aki ismeri a térképet (vagyis Alíz nyilvános kódját), tud titkosított üzenetet készíteni.

Hogyan tud Alíz megfejteni egy ilyen üzenetet? Ehhez újból össze kellene adnia a csúcsokhoz írt kisméretű számjegyeket. És itt segít neki a titkos kulcs. A titkos kulcs ugyanis a csúcsoknak egy olyan részét jelöli ki, hogy az ezek és ezek szomszédai minden csúcsot pontosan egyszer tartalmaznak. Tehát az itt álló nagy számok összegének utolsó hegye megegyezik az összes kis szám összegének utolsó jegyével. A példában Alíz kulcsa a bekarikázott csúcsok. A titkosított üzenetnek az ide eső értékei 7, 9, 6 és 4, ezek összege 26, aminek utolsó jegye 6, az elrejtett szám.

Használhatjuk a 6. ábrát is nyilvános kulcsnak. Mondjuk most a titkos üzenet a kétjegyű 75. A csúcsokhoz véletlen kétjegyű számokat írunk úgy, hogy az összegük utolsó két számjegye kiadja a titkos 75 számot (7. ábra). Minden egyes csúcsba beírjuk az ott és a szomszédaiban álló számok összegének utolsó két számjegyét. Például a bal felső csúcsnál ez az összeg 32+81+61+16+74=264, így az oda kerülő szám 64 lesz. Minden csúcsnál elvégezve az összeadást megkapjuk az üzenetet (8. ábra). A titkosított üzenet megfejtéséhez összeadjuk azoknál a csúcsoknál álló számokat, ahová a fagylaltoskocsikat kell elhelyezni (9. ábra)

19+89+55+36+36+62+56+80+42 = 475,

tehát az üzenet 75 volt.

A nagy, "igazi" rendszerek is hasonló elveken működnek. A most ismertetett nyilvános kulcsú rendszer kiválóan alkalmas a módszer illusztrálására. A gondos és részletes vizsgálatok azonban a rendszer gyengeségeit is megmutatják. Azt be tudjuk bizonyítani, hogy nincs olyan hatékony algoritmus, ami a nyilvános kulcsból meghatározná a titkos kulcsot. (Pontosabban csak azt tudjuk, hogy ha mégis létezne ilyen algoritmus, akkor egyátalán nem volnának nehéz feladatok.) De nem lehetséges, hogy az elrejtett értéket a kulcs ismerete nélkül is meg tudjuk határozni? Térjünk vissza a 9. ábrához, ahol egy ismeretlen értéket rejtettünk el. Az ismeretlen érték a csúcsokhoz írt (ugyancsak ismeretlen) számjegyek összegének utolsó jegye. Amit ismerünk, az a csúcsokhoz írt számok. Az ábrán 16 csúcs van, a csúcsokhoz írt számjegyeket jelöljük sorban x_11,x_12,x_13,x_14, ..., x_44-gyel, attól függően hogy a csúcs hányadik sorban és oszlopban van. A bal felső sarokban álló érték 7, tehát fennáll a következő kongruencia:

x_11 + x_12 + x_21 + x_34 == 7 (mod 10)

Hasonlóan az összes többi csúcsra fel tudjuk írni a megfelelő kongruenciát, például a jobb alsó csúcsban álló szám nulla, ezért

x_43 + x_44 + x_34 + x_32 == 0 (mod 10)

Van összesen 16 lineáris kongruenciánk és 16 ismeretlenünk, azt várjuk, hogy az összes ismeretlent meg tudjuk határozni (valóban ez is a helyzet), és ekkor az x_11, ..., x_44 ismeretlenek összege megadja az elrejtett üzenetet. A 6. ábrát használva a "titok" meghatározásához egy 36 ismeretlenes kongruenciarendszert kellene megoldani, ami szinte ugyanannyira reménytelen vállalkozás, mint a lefogó rendszer megkeresése.

Irodalom