Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

3. A nem feltáró bizonyítás

3. A nem feltáró bizonyítás

3.1. A tudás bizonyítása

Legyen n két – legalább százjegyű – prímszám szorzata. Tegyük fel, hogy Bianka ismeri n két prímtényezőjét. Hogyan tudná e tudását bizonyítani Elemérnek anélkül, hogy a két prímet elárulná? Az előző fejezetben mondottak szerint jó bizonyítás lenne, ha egy véletlenül választott y számból rövid időn belül négyzetgyököt tudna vonni modulo n . Feltesszük, hogy ( y , n ) = 1 , azaz feltesszük, hogy a véletlen y elemet Z n * -ből választjuk. Ha ( y , n ) //>// 1 volna, aminek igen kicsi a valószínűsége, akkor n -nek azonnal ismernénk egy prímtényezőjét, és a kérdés érdektelenné válna. Kérdés, hogy Bianka az y négy gyöke közül melyiket adja meg Elemérnek válaszul. Mind a négyet nem adhatja meg, hisz ezek ismeretében Elemér is hamar meg tudná határozni n prímtényezőit. Olyan T tulajdonságot kell tehát találni, melyet mindig pontosan egy gyök elégít ki a négy közül és amelyet Elemér is könnyen tud ellenőrizni. Elemér tehát választ egy T tulajdonsággal rendelkező számot, a négyzetét elküldi Biankának, aki kiszámítja a gyökeit, és kiválasztja közülük az egyetlen T tulajdonsággal rendelkezőt, amit bizonyságul visszaküld Elemérnek.

Megmutatjuk, hogy ha n Blum-egész, azaz n = p q , p és q prímek, p ? q ? 3 ( mod 4 ) , akkor egy n -nel relatív prím y négyzetelem négy modulo n vett négyzetgyöke között pontosan egy négyzetelem van. A bizonyítás előtt oldjuk meg az alábbi feladatot!

8. feladat. A 4. feladatban kiszámoltuk 53 négyzetgyökeit modulo 77. A négy gyök közül melyik négyzetelem?

Ha x 0 a négy négyzetgyök egyike és négyzetelem, azaz az x 2 ? x 0 ( mod n ) kongruenciának van megoldása, akkor van az x 2 ? x 0 ( mod p ) és az x 2 ? x 0 ( mod q ) kongruenciáknak is, azaz, az (1)(4) kongruenciarendszerekben is használt jelölésekkel, x 2 ? x p ( mod p ) és x 2 ? x q ( mod q ) megoldható. Eszerint tehát x p modulo p , míg x q modulo q négyzetelem. Minthogy p és q 3-mal kongruensek modulo 4, ezért az Euler-feltételből azt kapjuk, hogy ( - 1 ) p - 1 2 = ( - 1 ) q - 1 2 = - 1 , tehát - 1 nem négyzetelem. Mivel egy négyzet és egy nem négyzet szorzata nem négyzet, így - x p , illetve - x q sem négyzetelem. Azt kaptuk tehát, hogy az (1)(4) kongruenciarendszerek közül pontosan egy van, melynek megoldása négyzetelem.

9. feladat. Mutassuk meg, hogy ha n = p q Blum-egész, és S jelöli a modulo n vett négyzetelemek halmazát, akkor az f : a ? S ? a 2 mod n függvény S egy permutációját adja, melynek inverze:

a ? S ? a ( p - 1 ) ( q - 1 ) + 4 8 mod n .

Ahhoz, hogy a tudás bizonyítására kigondolt algoritmusunk teljes legyen, már csak azt kell biztosítanunk, hogy Elemér egy véletlen négyzetelemet válasszon, és annak négyzetét küldje gyökvonásra Biankának. A legegyszerűbb módszer az, ha Elemér választ egy véletlen v egészt ( 0 //<// v //<// n , ( v , n ) = 1 ), és v 4 -t küldi Biankának, míg v 2 -t titokban tartja, hisz épp ez lesz a v 4 négyzetgyökei közül a négyzetelem. Így tehát a tudás bizonyítására kitalált protokollunk, a tudását bizonyító Bianka és az azt ellenőrző Elemér részvételével zajló alábbi lépésekből áll:

  1. lépés. Elemér választ egy véletlen v ? Z n * számot, kiszámolja y = v 2 mod n és z = v 4 mod n értékét és z -t elküldi Biankának, míg y -t titokban tartja.

  2. lépés. Bianka kiszámítja z négyzetgyökeit modulo n és kiválasztja közülük azt a w számot, amelyik négyzetelem (vagy egyszerűen alkalmazza a 9. feladatbeli képletet), és ezt visszaküldi Elemérnek.

  3. lépés. Elemér a kapott w számot összeveti y -nal. Ha azonosak (illetve kongruensek modulo n ), elfogadja Biankának az n prímtényezőinek ismeretére vonatkozó állítását.

Jó-e Bianka tudásának ez a bizonyítása? Vizsgáljuk meg alaposan. Ellenőrizzük néhány feltétel teljesülését!

  1. Elemér a protokoll szabályai szerint eljárva nem tudhat meg semmit Bianka titkáról; amit megtudhat, az az egyetlen bitnyi információ, hogy Bianka tudja-e a titkot, vagy nem. Ez rendben van, Elemér valóban nem tudott meg semmit, hisz Bianka olyan számot küldött vissza, amit Elemér már egyébként is ismert.

  2. Bianka nem csaphatja be Elemért. Erre Biankának valóban nincs módja. Az egyetlen lehetősége, hogy v 4 -re v 2 -tel válaszol.

  3. Elemér nem adhatja ki magát egy harmadik személy előtt, mint Bianka titkának tudója. Ha ki tudná adni magát, az azt jelentené, hogy meg tudja határozni egy szám négyzetgyökét, akkor pedig n felbontását is meg tudja adni, azaz tud(hat)ja a titkot. Az természetesen előfordulhat, hogy Elemér egy olyan számot kap, amelynek négyzetgyökére „véletlen” próbálkozással rátalál, ennek valószínűsége azonban rendkívül kicsi. (Olyan támadás persze elképzelhető, hogy valaki Bianka felé ellenőrnek, míg vele egy időben Elemér felé bizonyítónak adja ki magát, és Elemér üzenetét változatlanul átküldi Biankának, míg az ő válaszát Elemérnek küldi. Az ilyen támadás ellen más, e protokollon kívüli módszert kell használni.)

  4. Elemér nem csaphatja be Biankát. Ez azt jelenti, hogy Elemér a protokoll szabályaitól való eltéréssel nem juthat információhoz. Ez a feltétel sajnos esetünkben nem teljesül! Ha Elemér egy olyan y számot választ (és ilyet 1 / 2 valószínűséggel véletlenül is találhat, mint a 6. feladatban), mely nem négyzetelem, és - y sem, akkor a válaszul kapott w és ellentettje, - w , együtt megadják y 2 négy négyzetgyökét, aminek ismeretében Elemér már felbonthatja n -et tényezői szorzatára.

  5. A protokollt ismerő külső megfigyelő még azt sem tudhatja meg, hogy Bianka tudja-e a titkot [14]. Ez másként fogalmazva azt jelenti, hogy a valóságos párbeszédek könnyen szimulálhatók olyannal, melyek a titok ismerete nélkül készültek és megkülönböztethetetlenek a valóságosaktól. Esetünkben e feltétel is fennáll, hisz ( v 4 , v 2 ) párokat bárki generálhat a prímtényezők ismerete nélkül is, és e számokkal lejátszhatja a fenti protokollt.

E részben sikertelen, de tanulságos próbálkozás után másik módszerrel próbálkozunk.

3.2. Használjuk, amit a varázslóktól tanultunk

Látjuk, az előző megoldás nem volt jó abban az értelemben, hogy Elemér – igaz, csak a protokoll szabályainak be nem tartásával – megszerezhette Bianka titkát. Eszerint olyan megoldást kell találnunk, melyben Bianka nem vállalja, hogy egy Elemér által javasolt számból négyzetgyököt von. Ez hasonló ahhoz, ahogy Bebió sem vállalta, hogy bármely állatot átvarázsol bármivé. ő azt tette, hogy előbb az Ellea által adott állatot titokban átvarázsolta valami mássá. Meg tudjuk ezt mi is valósítani az Elemér által választott négyzetszámmal?

Az ötlet az, hogy a megadott négyzetszámot Bianka először beszorozza egy véletlenül választott szám négyzetével, és csak ebből vállalja a modulo n vett négyzetgyökvonást. A javított protokoll tehát a következő. Adva van x ? Z n * , ahol n két különböző prím szorzata. Bianka bizonyítja, hogy ismer olyan t ? Z n * számot, melyre x ? t 2 ( mod n ) , azaz ismeri x valamely négyzetgyökét.

  1. lépés. Bianka választ egy véletlen v ? Z n * számot, és elküldi Elemérnek az y = v 2 x mod n számot. (Bianka „átvarázsolja” az x négyzetszámot egy másik négyzetszámmá.)

  2. lépés. Elemér választ egy véletlen b bitet (azaz b = 0 vagy 1), és azt elküldi Biankának. (A b = 0 eset felel majd meg a „viszka”-kérés esetének.)

  3. lépés. Bianka visszaküldi a w = v t b mod n értéket Elemérnek. (Eszerint b = 0 esetén Elemér megtudja, hogy melyik v szám négyzetével „varázsolta” Bianka x -et y -ná, b = 1 esetén pedig megtudja y egy négyzetgyökét.)

  4. lépés. Elemér ellenőrzi, hogy b = 0 esetén fennáll-e a w 2 x ? y ( mod n ) , míg b = 1 esetén a w 2 ? y ( mod n ) kongruencia. Ha nem áll fenn, nem fogadja el Bianka állítását.

Vizsgáljuk meg ezt a protokollt is!

  1. Aki tudja t értékét, b bármilyen választása mellett sikeresen le tudja játszani a protokollt. Valóban, t ismeretében y és w kiszámítása b egyik értéke mellett sem okoz nehézséget.

  2. Bárki, aki t értékét nem ismeri (például az imposztor Imre), minden körben csak 1/2 valószínűséggel jár sikerrel a bizonyító szerepében. Ha Imre megsejti, hogy b értéke 0 lesz, választ egy véletlen r számot, s a protokoll szabályait követve sikerrel jár. Ha Imre megsejti, hogy b = 1 lesz, akkor választ egy véletlen w számot, és az 1. lépésben Elemérnek az y = w 2 mod n számot küldi. A 3. lépésben a w számot küldi, ami a 4. lépésben sikert hoz számára.

  3. A protokoll során semmi új információhoz sem lehet jutni. Fidél, aki nagyon figyeli a párbeszédeket, és persze semmit nem tud a titokból, b = 0 esetén lát egy ( y , w ) = ( v 2 x , v ) számpárt, míg b = 1 esetén egy ( y , w ) = ( w 2 , w ) számpárt. Ezek mind olyan számpárok, amilyeneket maga is tudna generálni tetszőleges, akár előre adott bitsorozathoz, b = 0 esetén egy véletlenül választott v , míg b = 1 esetén egy véletlen w szám segítségével.

E protokoll nemcsak akkor használható, ha Bianka bármely szám négyzetgyökét ki tudja számolni, de akkor is, ha csak egyetlen x szám egyetlen g négyzetgyökét tudja, amiből még nem tudja meghatározni n prímfelbontását. Egy ilyen tudás bizonyításának egy lehetséges alkalmazásáról szól a következő fejezet.

3.3. Személyazonosítás

Ez a protokoll takarékosabban fog bánni azzal az információval, amit egy nagy szám prímtényezős alakjának ismerete jelent, itt ugyanis nem a prímtényezők ismerete lesz a titok, vagy ami ezzel ekvivalens, a gyököt vonni tudás, hanem csak egyetlen szám négyzetgyökének ismerete.

A következő protokoll egyszerre több ember számára is lehetővé teszi, hogy személyazonosságukat igazolják. Egy megbízható központ keres két nagy – legalább százjegyű – p és q prímet, kiszámítja az n = p q számot, a p és q számokat megsemmisíti, majd nyilvánosságra hozza n -et. Minden azonosítandó S személynek ad egy t számot, mely 0 és n - 1 közé esik, és amelyre ( t , n ) = 1 . Ez lesz a személy titkos kódja. Az x = t 2 mod n számot S nevével együtt nyilvánosságra hozza, ez lesz S nyilvános azonosító száma.

Ha Elemér azonosítani akarja Biankát, akkor megkéri, bizonyítsa be, hogy tudja a neki adott titkos t számot. E bizonyítás több körben, a következő lépések néhányszori megismétlésével történik:

  1. lépés. Bianka választ egy véletlen v egészt, és elküldi Elemérnek az y = v 2 mod n számot.

  2. lépés. Elemér választ egy véletlen b bitet, azaz a 0 vagy az 1 számok valamelyikét, és ezt elküldi Biankának.

  3. lépés. Bianka válaszul elküldi az w = v t b számot, vagyis ha b = 0 , akkor a v , ha b = 1 , akkor a v t számot.

  4. lépés. Elemér ellenőrzi, hogy fennáll-e a w 2 ? y x b ( mod n ) kongruencia. Ha nem, nem fogadja el, hogy Bianka ismeri t -t, azaz nem hiszi el, hogy valóban ő Bianka.

3.4. Pénzfeldobás telefonon keresztül

Lehet-e telefonon keresztül „fej vagy írás”-t játszani? Bianka feldob egy érmét, Elemér megtippeli telefonon keresztül, majd Bianka megmondja, hogy jó-e a tipp. Nem tűnik valami biztonságos játéknak. Arra volna szükségünk, hogy Bianka, miután feldobta a pénzt, küldje el a dobás eredményét Elemérnek, de úgy kódolva, hogy Elemér azt semmiképpen se tudja megfejteni, majd Elemér tippje után küldje el Elemérnek a dekódoláshoz szükséges kulcsot is, amivel Elemér megtudhatja, hogy mi volt Bianka dobásának eredménye. Ráadásul Elemérnek a dekódolás után látnia kell azt is, hogy Bianka nem rendelkezhet egy másik kulccsal is, aminek segítségével a másik eredmény jönne ki. Ez épp olyan, mint amikor a sakkozók borítékolják a lépést, amelyet majd csak egy későbbi időpontban lehet felnyitni, tartalmát addig nem lehet megtudni, utána viszont nem lehet letagadni. Először egy bitnyi információ borítékolására mutatunk egy protokollt, mely a négyzetes maradék problémáról írtakra épül.[15]

Bianka választ egy n = p q alakú számot, ahol p , q //>// 2 prímek, és egy m ? Z n * álnégyzetelemet. p és q értékét titokban tartja, de n és m értékét nyilvánosságra hozza. Ezután Bianka a következőképpen tud egy b bitet borítékolni. Először választ egy véletlen x ? Z n * egészt, és elküldi Elemérnek az m b x 2 mod n számot (ez lesz a borítékolt bit). Egy későbbi időpontban Bianka elküldi a b és x számokat Elemérnek, amivel „felnyitja” a borítékot.

Vegyük észre, hogy m 0 x 2 négyzetelem, m 1 x 2 viszont álnégyzet. Amennyiben a négyzetes maradék probléma „nehéz”, Elemér nem tudja megállapítani, hogy a Biankától kapott szám négyzet vagy álnégyzet, tehát nem tudja, hogy b értéke 0 vagy 1. Másrészt Bianka nem tud csalni, ahhoz ugyanis az kéne, hogy egy borítékolt üzenetet kétféleképpen is fel tudjon nyitni, úgy is, hogy b = 0 , úgyis, hogy b = 1 legyen. Ha ez lehetséges volna, akkor létezne két x 1 és x 2 szám, hogy m x 1 2 ? x 2 2 ( mod n ) , és így m ? ( x 2 x 1 - 1 ) 2 ( mod n ) volna, ami nem lehet, hisz m nem négyzetelem.

E protokollal már nem lesz nehéz a „fej vagy írás” játékot lejátszani telefonon. Legyen például 0 a fej, 1 az írás. Legyen p = 271 , q = 479 , így n = 129 809 . p és q ismeretében könnyen ellenőrizhető, hogy például m = 68 017 álnégyzet. Bianka választ egy véletlen x számot, legyen ez mondjuk 1000, feldob egy pénzt, fej esetén ( b = 0 ) a 91 337-et, írás esetén a 69 607-et mondja a telefonba Elemérnek. Elemér tippel, ezután Bianka elküldi a b értékét, ami 0 vagy 1, és a véletlenül választott x számot[16].

A borítékolás nemcsak a pénzfeldobásban használható protokoll. Utolsó feladatunkban arra kérjük az Olvasót, hogy maga konstruáljon egy bizonyos matematikai ismerethez nem feltáró bizonyítást.

Legyen G egy gráf, mely csúcspontok egy V halmazából és bizonyos csúcspárokat összekötő élek egy E halmazából áll. A kérdés: kiszínezhetők-e a gráf csúcsai 3 színnel úgy, hogy bármely két – E -beli él mentén – szomszédos csúcs különböző színű legyen.

10. feladat. Bianka azt állítja, hogy ismeri egy adott G gráf csúcsainak 3-színezését (ami azt jelenti, hogy a gráf csúcsai úgy vannak kiszínezve, hogy bármely él két végpontja különböző színű legyen). Adjunk meg egy kriptográfiai protokollt, mellyel Bianka nem feltáró bizonyítását adhatja tudásának. A protokollban az alábbi jelöléseket használjuk: a csúcsok száma | V | = v , az éleké | E | = k . V elemei, azaz a csúcsok 1-től v -ig meg vannak sorszámozva. A három színt 2-jegyű bináris sorszámukkal jelöljük, nevezetesen az első, második, illetve harmadik színt a 01, 10, illetve 11 bináris szám jelöli. A gráf színezését egy b 1 b 1 ' b 2 b 2 ' b v b v ' bitsorozat formájában adják meg, ahol b i b i ' az i -edik csúcs színének 2-jegyű kódja.



[14] E feltételt nevezik angolul „zero knowledge condition”-nek.

[15] Hasonló kérdésről – a kártyaosztás telefonon keresztül való megvalósíthatóságáról – szól a KöMaL egy érdekes cikke [1].

[16] Bár e számok lényegesen kisebbek, mint amekkorákat a biztonság megkövetel, bizonyos körülmények között a fentihez hasonló nagyságú számokkal is működik a játék, például ha Bianka csak a játék kezdetén közli Elemérrel n és m értékét, és Elemérnél csak egy – a négy alapművelet kiszámolására képes – zsebszámológép van.