Titkosítási rendszerek CCA-biztonsága

Titkos´ıtási rendszerek CCA-biztonsága Doktori (PhD) értekezés

´ szerz˝o: MARTON Gyöngyvér témavezet˝o: Dr. Peth˝o Attila Debreceni Egyetem Természettudományi Doktori Tanács Informatikai Tudományok Doktori Iskola Debrecen, 2013

Ezen értekezést a Debreceni Egyetem Természettudományi Doktori Tanács Informatikai Tudom´ anyok Doktori Iskola Elméleti szám´ıt´ astudom´ any, adatvédelem és kriptográfia programja keretében kész´ıtettem a Debreceni Egyetem természettudományi doktori (PhD) fokozat´ anak elnyerése célj´ ab´ ol. Debrecen, 20 . . . . . . ........................ Márton Gyöngyvér jelölt

Tan´ us´ıtom, hogy M´ arton Gy¨ ongvér doktorjelölt 20 . . . - 20 . . . között a fent megnevezett Doktori Iskola Elméleti szám´ıtástudomány, adatvédelem és kriptogr´ afia programjának keretében irány´ıtásommal végezte munk´ aj´ at. Az értekezésben foglalt eredményekhez a jelölt önálló alkot´ o tevékenységével meghatározóan hozzájárult. Az értekezés elfogad´ as´ at javasolom. Debrecen, 20 . . . . . . ........................ Dr. Peth˝o Attila témavezet˝o

Titkos´ıtási rendszerek CCA-biztonsága ´ Ertekez´ es a doktori (PhD) fokozat megszerzése érdekében az informatika tudományágban Írta: M´ arton Gy¨ ongyvér okleveles informatikus Készz¨ ult a Debreceni Egyetem Informatikai Tudományok Doktori Iskolája, Elméleti sz´ am´ıt´ astudom´ any, adatvédelem és kriptográfia programja keretében Témavezet˝ o: Dr. Peth˝o Attila A doktori szigorlati bizotts´ ag: elnök:

Dr.

.....................

.....................

tagok:

Dr.

.....................

.....................

Dr.

.....................

.....................

A doktori szigorlat id˝ opontja: 20 . . . . . . . . . . . . . . . Az értekezés b´ır´ al´ oi: Dr. . . . . . . . . . . . . . . . . . . . . .

.....................

Dr.

.....................

.....................

Dr.

.....................

.....................

A b´ırálóbizotts´ ag: elnök:

Dr.

.....................

.....................

tagok:

Dr.

.....................

.....................

Dr.

.....................

.....................

Dr.

.....................

.....................

Dr.

.....................

.....................

Az értekezés védésének id˝ opontja: 20 . . . . . . . . . . . . . . .

Tartalomjegyzék 1. Bevezet˝ o 1.1. Titkos´ıt´ asi alapfogalmak . . . . . . . . . . . . . . . . . . . . ´ 1.2. Attekint˝ o . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3. Defin´ıci´ ok, jel¨ olések . . . . . . . . . . . . . . . . . . . . . . .

11 11 15 17

2. Szimmetrikus titkos´ıtási rendszerek biztonsága 2.1. Bevezet˝ o. . . . . . . . . . . . . . . . . . . . . . . . 2.2. Passz´ıv t´ amad´ oval szembeni biztonság . . . . . . . 2.3. Akt´ıv t´ amad´ oval szembeni biztonság . . . . . . . . 2.3.1. V´ alasztott ny´ılt sz¨ oveg alap´ u támadás . . . 2.3.2. V´ alasztott rejtjelezett szöveg alap´ u támadás 2.4. Szimmetrikus titkos´ıt´ asi rendszerek osztályozása . 2.4.1. Folyamtitkos´ıt´ o rendszerek . . . . . . . . . 2.4.2. Blokktitkos´ıt´ o rendszerek . . . . . . . . . .

. . . . . . . .

21 21 22 24 25 26 27 27 28

3. Hash f¨ uggvények és u ¨zenethiteles´ıt˝o kódok 3.1. Hash f¨ uggvények . . . . . . . . . . . . . . . . . . . . . . . . ¨ 3.2. Uzenethiteles´ ıt˝ o k´ odok . . . . . . . . . . . . . . . . . . . . .

31 31 35

4. Aszimmetrikus titkos´ıtási rendszerek biztonsága 4.1. A matematikai modell . . . . . . . . . . . . 4.2. Egyir´ any´ u f¨ uggvények . . . . . . . . . . . . 4.3. Kriptogr´ afiai feltételezések . . . . . . . . . . 4.3.1. A faktoriz´ aci´ os feltételezés . . . . . .

41 41 43 44 44

7

. . . .

. . . .

. . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . . . . . .

. . . .

. . . .

4.3.2. Az RSA-feltételezés . . . . . . . . . . . . . 4.3.3. A kvadratikus maradék feltételezés . . . . . 4.3.4. A diszkrét logaritmus feltételezés . . . . . . 4.3.5. A d¨ ontési Diffie–Hellman-feltételezés . . . . 4.4. Biztons´ agértelmezések . . . . . . . . . . . . . . . . 4.4.1. V´ alasztott ny´ılt sz¨ oveg alap´ u támadás . . . 4.4.2. V´ alasztott rejtjelezett sz¨ oveg alap´ u támadás 4.5. Hibrid rendszerek . . . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

45 45 46 46 47 47 48 50

5. CCA-biztonság´ u kulcsbeágyazási mechanizmusok 5.1. Az RSA-rendszer . . . . . . . . . . . . . . . 5.2. A Rabin-rendszer . . . . . . . . . . . . . . . 5.3. A Blum–Goldwasser-rendszer . . . . . . . . 5.4. Az ElGamal-rendszer . . . . . . . . . . . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

. . . .

55 55 59 62 67

6. Az u ´j kulcsbeágyazási mechanizmus 6.1. Bevezet˝ o. . . . . . . . . . . . . . 6.2. Az u ´j CPA-biztons´ ag´ u rendszer . 6.2.1. A rendszer le´ır´ asa . . . . 6.2.2. A rendszer helyessége . . 6.2.3. A rendszer biztons´ aga . . 6.2.4. A rendszer hatékonys´ aga . 6.3. Az u ´j CCA-biztons´ ag´ u rendszer . 6.3.1. A rendszer le´ır´ asa . . . . 6.3.2. A rendszer helyessége . . 6.3.3. A rendszer biztons´ aga . . 6.3.4. A rendszer hatékonys´ aga .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

73 73 74 74 75 76 78 78 78 80 81 87

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

7. Kulcsbeágyazási mechanizmusok implementációja

89

¨ 8. Osszefoglal´ o

95

9. Summary

99

Irodalomjegyzék

103

8

A. Referált nemzetk¨ ozi foly´ oiratban megjelent cikkek

111

B. Lektorált egyetemi jegyzet

113

C. Tudományos konferencia k¨ otetben megjelent cikkek

115

D. Tudományos konferenciákon elhangzott el˝oadások

117

E. Köszönetnyilván´ıtások

119

10

1. fejezet

Bevezet˝ o 1.1. Titkos´ıtási alapfogalmak A kriptogr´ afi´ an bel¨ ul két, k¨ ul¨ onböz˝o elven m˝ uköd˝o titkos´ıtási rendszert k¨ ul¨ onb¨ oztet¨ unk meg: a szimmetrikus vagy titkos kulcs´ u (privatekey/symmetric encryption) és az aszimmetrikus vagy nyilvános kulcs´ u titkos´ıtási (public-key/asymmetric encryption) rendszert. A gyakorlatban legtöbbsz¨ or hibrid rendszereket alkalmaznak, azaz ezek egy¨ uttes használata mer¨ ul fel, ha két egym´ ast´ ol t´ avol es˝o fél (szám´ıtógép, táblagép, mobiltelefon) szeretne bizalmas inform´ aci´ ocserét megvalós´ıtani. Ezt els˝osorban azért teszik, mert a szimmetrikus titkos´ıtók hatékonysága messzemen˝oen jobb, mint az aszimmetrikus titkos´ıt´ okké, a szimmetrikus titkos´ıtók, pedig nem tudják megoldani a két t´ avoli fél biztonságos kulcscseréjét. Mindkét rendszer esetében a titkos´ıtandó információt a szakirodalom ny´ılt szövegnek (plaintext) nevezi, a titkos´ıtott információt, pedig rejtjelezett szövegnek (ciphertext) ([29], [18], [44]). Ahhoz, hogy a rendszerben a megfelel˝ o titkos´ıtott inform´ aci´ ot létrehozzuk egy kulcsnak nevezett információ ker¨ ul felhaszn´ al´ asra, amelynek alkalmazási módja, a fent le´ırtak alapján két nagy csoportra osztja a titkos´ıtó algoritmusokat. A rejtjelezett szöveg el˝o´ all´ıt´ as´ at rejtjelezésnek vagy titkos´ıtásnak (encryption) nevezz¨ uk, a ny´ılt szöveg vissza´ all´ıt´ as´ anak folyamatára a visszafejtés (decryption) megnevezést fogjuk haszn´ alni. A Kerckhoffs-elv szerint [37] a rendszerek által 11

el˝o´ırt titkos´ıtó algoritmusok nyilv´ anosak, s˝ot standard el˝o´ırások alapján kell ˝oket implement´ alni, protokollokban felhasználni. A titkos´ıtó rendszerek esetében éppen ezért pontosan specifikált formában kell megadni a kulcsgenerálás, titkos´ıt´ as és visszafejtés algoritmusait, illetve matematikai eszközökkel kell bizony´ıtani ezen algoritmusok helyes m˝ uködését és biztonságát. Titkos´ıtó rendszerek esetében, tulajdonképpen kétféle biztonságról beszélhet¨ unk, feltétel nélk¨ uli biztons´ agról vagy információelméleti biztonságról (information-theoretic security) vagy másképpen mondva tökéletes biztons´ agr´ ol (perfect security) és szám´ıtástechnikai biztonságról (computational security). Ezen fogalmak alatt a következ˝o bekezdésekben le´ırtakat értj¨ uk ([7], [45]). Az inform´ aci´ oelméleti biztons´ ag esetében a kriptorendszert támadó fél szám´ıtási kapacit´ as´ ara nem adunk korlátot, azaz azt feltételezz¨ uk, hogy a támad´ o korl´ atlan sz´ am´ıt´ asi kapacitással rendelkezik. A fentiek alapján, inform´ alisan azt mondjuk, hogy egy titkos´ıtó rendszer tökéletesen biztonságos, ha egy t´ amad´ o korl´ atlan szám´ıtási kapacitását feltételezve sem törhet˝o fel a rendszer. Az OTP (one-time pad) titkos´ıtó rendszert leszám´ıtva, amelynek egyik v´ altozat´ at Vernam mutatta be 1917-ben [63], és amely implement´ al´ as szempontj´ ab´ ol számos nehézséget vet fel, a létez˝o titkos´ıtó rendszerek egyike sem rendelkezik információelméleti biztonsággal. Gyakorlati megval´ os´ıthat´ os´ ag szempontjából a modern kriptográfia feladja az olyan titkos´ıt´ o rendszerek szerkesztésének igényét, amelyek tökéletesen biztons´ agosak. Az inform´ aci´ oelméleti biztonság helyett a gyakorlatban is kivitelezhet˝ o sz´ am´ıt´ astechnikai biztonság´ u rendszerek megvalós´ıtása a cél. A szám´ıtástechnikai biztons´ ag azt jelenti, hogy a kriptorendszerek biztonságát olyan feltételek mellett garantálják, amikor a támadónak szám´ıtástechnikai kapacit´ asa korl´ atozott. Ez oly módon valós´ıtható meg, hogy a rendszerek biztons´ ag´ at olyan matematikai problémák biztos´ıtják, amelyek megold´ asa nehéz, pontosabban megoldásukra nem ismert polinomiális idej˝ u algoritmus. Sz´ am´ıtástechnikai biztonság esetében, természetesen a t´ amad´ o er˝ oforr´ asair´ ol is azt feltételezz¨ uk, hogy polino´ miálisan korlátozottak. Eppen ezért egy kriptorendszer szám´ıtástechnikai biztonsága szoros kapcsolatban ´ all a visszavezethet˝oség fogalmával, azaz ha 12

egy kriptorendszer biztons´ aga visszavezethet˝o valamely jól ismert feladatra, amely nem oldhat´ o meg polinomiális id˝oben, akkor azt mondjuk, hogy a kriptorendszer sz´ am´ıt´ astechnikailag biztonságos. Ezek alapj´ an természetesen mer¨ ul fel az NP-teljes nehézség˝ u matematikai feladatok alkalmaz´ asa kriptográfiai rendszerekben, Az els˝o titkos´ıtó rendszerek k¨ oz¨ ott, éppen ezért sz´ amos olyan rendszert is találunk amelyeknek h´ atterében NP-teljes problémáj´ u feladat áll. Legismertebb ezek között a h´ atizs´ ak feladaton alapul´ o titkos´ıtó rendszer [42]. Ezen feladatok alkalmazása, azonban nem mindig vezetett sikerre, mert az NP-teljes feladatok megoldhat´ os´ aga ´ altal´ aban a legrosszabb bemenet esetén szám´ıt nehéz feladatnak, a kriptogr´ afi´ aban pedig olyan matematikai problémák alkalmasak, amelyek az ´ atlagos esetben is nehezen megoldhatónak szám´ıtanak [57]. A nagy dimenzi´ oj´ u r´ acsokban, a legrövidebb vektor megkeresésén alapuló kriptorendszerek, azonban kivételt képeznek. Az 1990-es évek végén, több ilyen kriptorendszert is kidolgoztak, például az Ajtai-Dwork kriptorendszert [2]. Ezeknek a rendszereknek a kidolgozása több szempontból is lényeges, az egyik szempont, hogy fontos széles´ıteni a nehéz matematikai problémákon alapuló kriptorendszerek ter¨ uletét, a másik szempont, hogy ezek a rendszerek lényegesen gyorsabbak, mint a széleskörben elterjedt, a faktorizáción és diszkrét logaritmuson alapul´ o kriptorendszerek. Az értekezés tov´ abbi részében a titkos´ıtó rendszerek biztonsága alatt mindig sz´ am´ıt´ astechnikai biztons´ agot fogunk érteni. A titkos´ıt´ o rendszerek esetében a támadó lehet˝oségei k¨ ulönböz˝o szám´ıtástechnikai biztons´ agi szintet határoznak meg, általában négy nagy csoportba szokt´ ak felosztani a lehetséges támadási t´ıpusokat [40]: • • • •

rejtjelezett sz¨ oveg alap´ u t´ amadás (ciphertext-only attack) ismert ny´ılt sz¨ oveg alap´ u t´ amadás (known-plaintext attack) választott ny´ılt sz¨ oveg alap´ u támadás (chosen-plaintext attack) választott rejtjelezett sz¨ oveg alap´ u támadás (chosen-ciphertext attack)

A rejtjelezett sz¨ oveg alap´ u t´ amadás esetén a támadó egyetlen kiindulási pontja a rendelkezésére ´ all´ o rejtjelezett szöveg, illetve adott esetben a rejtjelezett sz¨ ovegek. Ez alapj´ an pr´ obálja meghatározni a ny´ılt szöveget, a rendszerben alkalmazott kulcsot vagy következtetni ezekre. 13

Az ismert ny´ılt sz¨ oveg alap´ u t´ amad´ as esetén a támadó több ny´ılt szöveg és ezeknek megfelel˝ o rejtjelezett sz¨ oveg p´ arral rendelkezik. A támadó ezeknek az informáci´ oknak a birtok´ aban pr´ obál következtetni a rendszerben alkalmazott kulcsra vagy egy rejtjelezett szöveg tartalmára. A jelenlegi szabv´ anyok szerint, azok a rendszerek, amelyek nem állnak ellen a fenti két t´ amad´ asi t´ıpusnak, a legkisebb biztonsági szintet sem biztos´ıtják. A fenti két t´ amad´ asi t´ıpust passz´ıv támadásként kategorizálja a kriptográfia ([7], [36], [24]). A választott ny´ılt sz¨ oveg alap´ u t´ amadás esetében a támadónak lehet˝osége van tetsz˝ oleges sz´ am´ u rejtjelezést végezni, a saját maga által kiválasztott, szerkesztett ny´ılt sz¨ ovegen és ezek alapján próbál következtetni a rendszer bemeneti paramétereire, azaz a kulcsra vagy a ny´ılt szövegre. A továbbiakban azokat a rendszereket, amelyek biztonságosak a választott ny´ılt szöveg alap´ u t´ amad´ assal szemben CPA-biztonság´ u rendszereknek fogjuk h´ıvni. A választott rejtjelezett sz¨ oveg alap´ u támadás esetében a támadónak lehet˝osége van tetsz˝ oleges sz´ am´ u visszafejtést végezni, a saját maga által kiválasztott, szerkesztett rejtjelezett sz¨ ovegen és ezek alapján próbál következtetni a rendszer bemeneti paramétereire, azaz a kulcsra vagy a ny´ılt szövegre. A tov´ abbiakban azokat a rendszereket, amelyek biztonságosak a választott rejtjelezett sz¨ oveg alap´ u t´ amadással szemben, CCA-biztonság´ u rendszereknek fogjuk h´ıvni. Az utolsó két t´ amad´ asi t´ıpus esetében megk¨ ulönböztetj¨ uk ezek adapt´ıv formáját is, mint sokkal er˝ osebb t´ amad´ asi t´ıpusokat, ami azt jelenti, hogy a támadónak arra is lehet˝ osége van, hogy a kiválasztásra ker¨ ul˝o ny´ılt, illetve rejtjelezett sz¨ oveget az alapj´ an hat´ arozza meg, hogy mi volt a korábbi rejtjelezés, illetve visszafejtés eredménye. Ez utóbbi támadási t´ıpust akt´ıv támadásként tartja sz´ amon a kriptogr´ afia ([7], [36], [24]). Fontos megjegyezni, hogy napjainkban is számos olyan titkos´ıtó rendszert használnak, amelyek nem ´ allnak ellen a választott rejtjelezett szöveg alap´ u támadásnak. Sok´ aig ez a t´ amad´ asi t´ıpus, valóban csak az elméleti kriptográfiának jelentett megoldatlan problémát, de az 1998-as RSA elleni sikeres Bleichenbacher-t´ amad´ as ´ ota [9] az aszimmetrikus titkos´ıtó rendszerek alkalmazásakor figyelembe kell venni a választott rejtjelezett szöveg ´ alap´ u támadással szembeni biztons´ agot is. Eppen ezért az elm´ ult t´ız 14

évben fokozott hangs´ uly tev˝ od¨ ott az aszimmetrikus titkos´ıtó rendszerek átalak´ıtás´ ara, oly m´ odon hogy azok ellenálljanak a fenti két támadási t´ıpusnak, ugyanakkor pedig, hogy meg˝orizzék a megfelel˝o hatékonyságukat [50]. Mint eml´ıtett¨ uk, a gyakorlatban titkos´ıtó rendszerekként legtöbbször hibrid rendszereket alkalmaznak, ami azt jelenti, hogy a tulajdonképpeni adathalmaz titkos´ıt´ as´ ara szimmetrikus kriptográfiai technikákat alkalmaznak, a titkos´ıt´ o kulcsok cseréjét, pedig aszimmetrikus kriptográfiai technikával oldj´ ak meg. Ez ut´ obbira a szakirodalom bevezette a kulcsbeágyazási mechanizmus (key encapsulation mechanism) elnevezést [21]. Jelen értekezés keretén bel¨ ul t¨ obb aszimmetrikus titkos´ıtási rendszert fogunk megvizsg´ alni, fokozott hangs´ ulyt fektetve arra is, hogy mit jelent a választott ny´ılt sz¨ oveg alap´ u, illetve a választott rejtjelezett szöveg alap´ u támadás egy szimmetrikus titkos´ıt´ asi rendszerben, illetve egy aszimmetrikus titkos´ıt´ asi rendszerben. Mivel a fenti elméleti fogalmakhoz nem kapcsolódik széles k¨ orben elfogadott magyar terminológia, az els˝o három fejezetben fokozott hangs´ ulyt fektet¨ unk az ide kapcsolódó értelmezések és tételek prec´ız, magyar megfogalmazására. Az értekezés keretén bel¨ ul javasolunk egy u ´j kulcsbeágyazási, mechanizmust, amelynek megadjuk a specifikációját, hatékonyságát, bizony´ıtjuk helyességét, CPA és CCA-biztons´ agát, és részletezz¨ uk implementációs lehet˝oségeit. Az értekezésben kitér¨ unk arra is, hogy összehasonl´ıtsuk implementációs lehet˝oségek, illetve hatékonys´ ag szempontjából az u ´j kulcsbeágyazási mechanizmust az elm´ ult években publikált CCA-biztonság´ u aszimmetrikus rendszerekkel, pontosabban a Cramer–Shoup [20], az RSA–OAEP [6], az SAEP [14], és a Hofheinz- és t´ arsai [35] rendszerekkel.

´ 1.2. Attekint˝ o Az értekezés els˝ o fejezete jelen bevezet˝ot tartalmazza, amely felvázolja az értekezés f˝ obb mondanival´ oj´ at kitérve általános jelleg˝ u informális értelmezések, jel¨ olések megad´ as´ ara.

15

A második fejezet a szimmetrikus titkos´ıtási rendszerek matematikai modelljének bemutat´ asa ut´ an r´ atér a passz´ıv és akt´ıv támadóval szembeni biztonságfogalmak form´ alis értelmezésére. Az akt´ıv támadóval szembeni biztonság esetében k¨ ul¨ onbséget tesz¨ unk a választott ny´ılt szöveg alap´ u, illetve a választott rejtjelezett sz¨ oveg alap´ u támadások között. A harmadik fejezetben a hash f¨ uggvényekkel és u ¨zenethiteles´ıt˝o kódokkal szembeni k¨ ovetelményeket fogalmazzuk meg, kihangs´ ulyozva az univerzális hash f¨ uggvény (universal hash function), a cél u ¨tközésmentes hash f¨ uggvény (target collision-resistant hash function) és az u ¨tközésmentes hash f¨ uggvény (collision-resistant hash function) közötti k¨ ulönbségeket, ezt els˝osorban azért tessz¨ uk, mert az értekezésben tárgyalásra ker¨ ul˝o titkos´ıtó rendszerek cél-¨ utk¨ ozésmentes hash f¨ uggvényt használnak. A negyedik fejezet az aszimmetrikus titkos´ıtó rendszerek matematikai modelljének a le´ır´ asa ut´ an megadja az egyirány´ u f¨ uggvények értelmezését, majd az értekezésben t´ argyal´ asra ker¨ ul˝ o titkos´ıtó rendszerek biztonságát meghatározó kriptogr´ afiai feltételezéseket: a faktorizációs feltételezést (factorization assumption), az RSA-feltételezést (RSA assumption), a kvadratikus maradék feltételezést (quadratic residuosity assumption), a diszkrét logaritmus feltételezést (discrete logarithm assumption), és a döntési Diffie– Hellman-feltételezést (Decisional Diffie–Hellman assumption). Az akt´ıv és passz´ıv támadóval szembeni biztons´ agértelmezések megadása után a hibrid rendszerek biztons´ ag´ at is t´ argyaljuk. Az ötödik fejezet azokat az aszimmetrikus titkos´ıtó rendszereket mutatja be, amelyeknek CCA-biztons´ ag´ u verzi´ oját implementáltuk, és amelyek hatékonyságát ¨ osszevetett¨ uk az ´ altalunk szerkesztett kulcsbeágyazási mechanizmus hatékonys´ ag´ aval. Ezek a rendszerek a következ˝oek: • • • •

az ElGamal- és Cramer–Shoup-rendszer, az RSA- és RSA–OAEP-rendszer, a Rabin- és SAEP-rendszer, a Blum–Goldwasser és Hofheinz- és társai rendszere.

A hatodik fejezet az értekezés legf˝ obb eredményét az u ´j kulcsbeágyazási mechanizmus CPA, illetve CCA-biztons´ ag´ u verzióját mutatja be. A kulcsbeágyazási mechanizmus alapj´ aul a Rabin-titkos´ıtó [54] és a Hofheinz és

16

társai [35], ´ altal szerkesztett rendszerek szolgáltak. A CCA-biztonság´ u kulcsbeágyaz´ asi mechanizmus a [48] cikkben ker¨ ult publikálásra. A fejezet keretén bel¨ ul megadjuk az u ´j mechanizmus specifikációját, helyességét, hatékonys´ ag´ at, illetve bizony´ıtjuk a rendszer biztonságát. A hetedik fejezet az ¨ ot¨ odik fejezetben, illetve a hatodik fejezetben le´ırt CCA-biztons´ ag´ u rendszerek implementációjára tér ki. Itt megadjuk az implement´ aci´ ohoz haszn´ alt hardver- és szoftverkonfigurációt, majd rendszerenként kitér¨ unk az implement´ al´ as specifikusabb részeire és táblázatokba foglalva felt¨ untetj¨ uk a fut´ asi id˝ ok eredményeit.

1.3. Defin´ıci´ ok, jel¨ olések A polinomi´ alis idej˝ u algoritmus, illetve a probabilisztikus és determinisztikus algoritmus fogalmak az értekezés fejezeteiben fontos szerepet fognak ´ játszani. Eppen ezért megadjuk ezek formális értelmezését. 1.1. defin´ıci´ o. Egy A(·) algoritmus fut´ asi ideje, az n bithossz´ us´ ag´ u bemenet f¨ uggvényében polinomi´ alis, ha lépéssz´ ama O(nk ), ahol n és k nem negat´ıv egész sz´ amok. Ekkor azt mondjuk, hogy az algoritmus polinomi´ alis idej˝ u, ([24], [36]). 1.2. defin´ıci´ o. Egy A(·) algoritmus, a bemenet f¨ uggvényében determinisztikus, ha el˝ ore meghat´ arozott lépésekb˝ ol ´ all, ahol a végrehajt´ as minden helyzetében egyértelm˝ uen meghat´ arozhat´ o az aktu´ alis lépés ut´ ani k¨ ovetkez˝ o lépés, ([24], [36]). 1.3. defin´ıci´ o. Egy A(·) algoritmus, az x bemenet f¨ uggvényében probabilisztikus, ha ([24], [36]): • az x bemenet mellett, egy x-t˝ ol f¨ uggetlen, véletlenszer˝ uen gener´ alt r bitsorozatot is megadunk, ahol az r bitsorozat a 0 és 1 értékeket egym´ ast´ ol f¨ uggetlen¨ ul, 1/2 val´ osz´ın˝ uséggel veheti fel, • az A(x) algoritmusnak megadhat´ o egy determinisztikus kiterjesztése, amelynek a x bemenet mellett az r bitsorozat is a bemenete lesz, jel¨ olj¨ uk ezt AD (x, r)-rel, 17

• az A(·) algoritmus kimenete nem egy konstans érték, hanem egy val´ osz´ın˝ uségi v´ altoz´ o lesz, pontosabban annak az eseménynek a val´ osz´ın˝ usége, hogy az A algoritmus az x bemeneten az y kimenetet hat´ arozza meg a k¨ ovetkez˝ o lesz: Pr[A(x) = y] = Pr[{r|AD (x, r) = y}]. 1.1. megjegyzés. Egy probabilisztikus algoritmus véletlen d¨ ontéseket hozhat a fut´ asi ideje alatt, és minden olyan algoritmus, amely véletlen sz´ amokat haszn´ al probabilisztikus algoritmus. 1.2. megjegyzés. A probabilisztikus, illetve determinisztikus algoritmus prec´ızebb definici´ oja a probabilisztikus, illetve determinisztikus Turing-gép fogalm´ anak bevezetésével adhat´ o meg [39], amire jelen értekezésben nem tér¨ unk ki. Az elhanyagolhat´ o f¨ uggvény fogalma több helyen is megtalálható a kriptográfiai szakirodalomban ([21], [18], [64]), jelen értekezésben ez alatt a következ˝oket fogjuk érteni: 1.4. defin´ıció. Egy f f¨ uggvény elhanyagolhat´ o (negligible), ha b´ armely (·) polinom esetében létezik egy k0 egész sz´ am u ´gy, hogy b´ armely k > k0 egész 1 sz´ amra fenn´ all: f (k) < (k) . Az értekezésben haszn´ alt jel¨ olések k¨ oz¨ ul, pedig fontosnak tartjuk megeml´ıteni az alábbiakat. R

1. Ha A egy halmaz, akkor x ← − A jel¨ oli, hogy x véletlenszer˝ uen, egyenletes eloszl´ as esetén lett kiv´ alasztva. R 2. Ha A egy probabilisztikus algoritmus, akkor az x ← − A jelölés azt jelenti, hogy az A algoritmus x kimenetét véletlenszer˝ uen határozta meg. 3. Az 1k , k darab egym´ as mellé ´ırt 1-est jelöl, amelyet a szakirodalomnak megfelel˝ oen gyakran fogunk algoritmusoknak megadni bemeneti paraméterként ([21][36]). Ezt a jel¨ olést akkor alkalmazzuk, amikor azt szeretnék jelezni, hogy az algoritmus futási ideje akkor is polinomiális k szerint, ha nincs az algoritmusnak bemenete vagy ez nagyon rövid. 18

4. A | · | jel¨ oléshez h´ aromféle jelentést is társ´ıtunk, melyet az adott helyeken nem jel¨ ol¨ unk explicit módon, feltételezve, hogy a kontextus alapj´ an ez kik¨ ovetkeztethet˝ o. Az eml´ıtett három jelentéstartalom a következ˝ o: abszol´ utérték, bithossz, és elemszám. 5. Az || oper´ ator ¨ osszef˝ uzést jelent.

19

20

2. fejezet

Szimmetrikus titkos´ıtási rendszerek biztonsága 2.1. Bevezet˝ o Szimmetrikus titkos´ıt´ as m´ ar az ´ okorban is létezett, azonban a legtöbb XX. század el˝ otti titkos´ıt´ o rendszer (Caesar, Playfair, Vigenere, stb.) a mai szám´ıtógépes eszk¨ oz¨ okkel k¨ onnyen feltörhet˝o. A jelenleg, gyakorlatban használt rendszerek (3DES, AES, Salsa20) ([40], [22], [8]) jól meghatározott biztonsági k¨ ovetelményeknek tesznek eleget. Ezen követelmények formális megadásához el˝ osz¨ or sz¨ ukséges a szimmetrikus rendszerek matematikai értelmezése ([17], [36]). 2.1. defin´ıci´ o. Jel¨ olje SKE azt a szimmetrikus titkos´ıt´ asi rendszert, amely egy (K, M, C) halmazh´ armas felett, h´ arom algoritmussal értelmezhet˝ o, ahol M a ny´ılt sz¨ ovegek egy véges halmaza, C a rejtjelezett sz¨ ovegek egy véges halmaza, K a titkos´ıt´ o kulcsok egy véges halmaza. A h´ arom eml´ıtett algoritmus, pedig a k¨ ovetkez˝ o: • Gen, a kulcsgener´ al´ o probabilisztikus algoritmus, amely polinomi´ alis R k id˝ oben az 1 bemeneten meghat´ arozza a key titkos´ıt´ o kulcsot: key ← − k Gen(1 ), ahol key ∈ K, k ∈ Z≥0 a rendszer biztons´ agi paramétere (legt¨ obb esetben a gener´ alt kulcs bithossza), 21

• Enckey a probabilisztikus rejtjelez˝ o algoritmus, amely polinomi´ alis id˝ oben végzi a rejtjelezést, a key titkos´ıt´ o kulcs alapj´ an, az m ∈ M R ny´ılt sz¨ ovegen, meghat´ arozva a c ∈ C rejtjelezett sz¨ oveget: c ← − Enckey (m), • Deckey a determinisztikus, visszafejt˝ o algoritmus, amely polinomi´ alis id˝ oben végzi a visszafejtést, a key titkos´ıt´ o kulcs alapj´ an a c rejtjelezett sz¨ ovegen: m ← Deckey (c). A rendszer helyessége érdekében megkövetelj¨ uk, hogy teljes¨ uljön Deckey (Enckey (m)) = m, minden key ∈ K és minden m ∈ M esetében. Fontos megjegyezni, hogy a kulcs és ny´ılt szöveg értékének a meghatározása egym´ ast´ ol f¨ uggetlen események, tulajdonképpen el˝obb rögz´ıtj¨ uk a kulcsot, majd azt´ an ker¨ ul meghat´ aroz´ asra a ny´ılt szöveg. A szimmetrikus titkos´ıt´ asi rendszerek biztonságának értelmezését többféleképpen is meg lehet adni, els˝ osorban aszerint csoportos´ıtják a biztonságértelmezéseket, hogy milyen t´ıpus´ u támadóval kell számolni egy adott titkos´ıtási rendszer esetében. A k¨ ovetkez˝o fejezetben formálisan megadjuk a passz´ıv t´ amad´ oval szembeni biztonságértelmezést, majd az akt´ıv támadóval szembeni biztons´ agértelmezést.

2.2. Passz´ıv támad´ oval szembeni biztonság A passz´ıv támad´ oval szembeni biztons´ ag értelmezéséhez sz¨ ukség van egy k´ısérletre. Az al´ abbi k´ısérletben az A t´ amadó egy probabilisztikus, polinomiális idej˝ u algoritmust jelent, ahol a k´ısérlet az A támadó és környezete, a kih´ıvó között j´ atsz´ odik le. 2.1. k´ısérlet. 1. A kih´ıv´ o a Gen kulcsgener´ al´ o algoritmussal meghat´ arozza a key titkos´ıt´ o kulcsot, 2. az A t´ amad´ o, két azonos hossz´ us´ ag´ u u ¨zenetet hat´ aroz meg, jel¨ olj¨ uk ezeket m0 , m1 -gyel, amelyeket ´ atad a kih´ıv´ onak, R 3. a kih´ıv´ o b ← − {0, 1} v´ alaszt´ as alapj´ an az Enckey (·) titkos´ıt´ o algorit∗ R mussal meghat´ arozza az mb titkos´ıtott értékét: c ← − Enckey (mb ), 22

amelyet ´ atad az A t´ amad´ onak; nevezz¨ uk ezt a c∗ titkos´ıtott értéket kih´ıv´ o rejtjelezett sz¨ ovegnek (challenge ciphertext), 4. az A t´ amad´ o meghat´ aroz egy ˆb ∈ {0, 1} kimeneti értéket. 2.2. defin´ıci´ o. Az SKE szimmetrikus titkos´ıt´ asi rendszerben az A t´ amad´ o pas 1 ˆ el˝ onye a k¨ ovetkez˝ oképpen adhat´ o meg: AdvSKE,A (k) = | Pr[b = b] − 2 |, ahol a b és ˆb értékeket a 2.1. k´ısérletben hat´ aroztuk meg. A passz´ıv t´ amad´ oval szembeni biztonságot a következ˝o értelmezés adja meg [21]: 2.3. defin´ıci´ o. Az SKE szimmetrikus titkos´ıt´ asi rendszer akkor biztons´ agos egy passz´ıv t´ amad´ oval szemben, ha b´ armely A probabilisztikus, polinomi´ alis idej˝ u, passz´ıv t´ amad´ o esetében létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy Advpas SKE,A (k) ≤ f (k), ahol Advpas ertelmezésnél adtuk meg. SKE,A (k)-t a 2.2. ´ Az SKE szimmetrikus titkos´ıtási rendszer passz´ıv támadóval szembeni biztons´ ag értelmezésének megadhatjuk egy alternat´ıv defin´ıcióját is [21]. Jelölj¨ uk a tov´ abbiakban Expr(0)-val azt az eseményt, amikor ˆb = 1, azon feltétel mellett, hogy a kih´ıv´ onak b = 0 volt a választása, és jelölj¨ uk Expr(1)-gyel azt az eseményt, amikor ˆb = 1, azon feltétel mellett, hogy a kih´ıvó a b = 1 értéket v´ alasztotta. Ekkor az A t´ amad´ o el˝ onye a k¨ ovetkez˝oképpen értelmezhet˝o: Adv0

pas SKE,A (k)

= 21 | Pr[Expr(0)] − Pr[Expr(1)]|.

2.4. defin´ıci´ o. Az SKE szimmetrikus titkos´ıt´ asi rendszer akkor biztons´ agos egy passz´ıv t´ amad´ oval szemben, ha b´ armely A probabilisztikus, polinomi´ alis idej˝ u, passz´ıv t´ amad´ o esetében létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy Adv0

pas SKE,A (k)

23

≤ f (k)

A két értelmezés k¨ oz¨ otti ekvivalencia a következ˝o egyenl˝oség alapján látható be: Adv0

pas SKE,A (k)

=

1 2

· | Pr[ˆb = 1|b = 0] − Pr[ˆb = 1|b = 1]|

1 2

· |1 − Pr[ˆb = 0|b = 0] − Pr[ˆb = 1|b = 1]| =

1 2

· |1 − 2 · Pr[b = ˆb]|

=

− Pr[b = ˆb]|

=

| 12

=

Advpas SKE,A (k). 2.1. megjegyzés. A kés˝ obbi biztons´ agértelmezések esetében is megadhat´ o hasonl´ o alternat´ıv defin´ıci´ o.

2.3. Akt´ıv támad´ oval szembeni biztonság Szimmetrikus titkos´ıt´ asi rendszerek esetében az akt´ıv támadó jelenléte két k¨ ulönböz˝o támad´ asi t´ıpust hat´ aroz meg, az egyikben a támadó lehet˝oségei korlátozva vannak, oly m´ odon, hogy csak titkos´ıtást tud végezni, ez lesz a választott ny´ılt sz¨ oveg alap´ u t´ amad´ as. A második esetben a támadó tetsz˝oleges rejtjelezett sz¨ ovegek visszafejtését is tudja kérni, kivéve a kih´ıvó rejtjelezett szöveg visszafejtését. Ezt fogjuk választott rejtjelezett szöveg alap´ u támadásnak h´ıvni. Az akt´ıv támad´ oval szembeni biztonság esetében a támadó, a kih´ıvón kereszt¨ ul egy titkos´ıt´ o, illetve egy visszafejt˝o orákulum igényeit veheti igénybe. Ez azt jelenti, hogy a kih´ıv´ o a megfelel˝o kulcs felhasználásával, amely természetesen nem ismert a t´ amadó által, megadja a támadó által szolgáltatott bemenetre, a k´ıv´ ant titkos´ıt´ as, illetve visszafejtés eredményét. Megjegyezz¨ uk, hogy az or´ akulumra, mint fekete dobozként viselked˝o algoritmusra, a tov´ abbiakban az ¨ osszes biztonságértelmezésnél sz¨ ukség van.

24

2.3.1. Választott ny´ılt szöveg alap´ u támadás A választott ny´ılt sz¨ oveg alap´ u támadással szembeni biztonság értelmezéséhez sz¨ ukséges megadni a következ˝o k´ısérlet lépéssorozatát, amely k´ısérlet az A t´ amad´ o és k¨ ornyezete, a kih´ıvó között játszódik le. 2.2. k´ısérlet. 1. A kih´ıv´ o a Gen kulcsgener´ al´ o algoritmussal meghat´ arozza a key titkos´ıt´ o kulcsot, 2. az A t´ amad´ o tetsz˝ oleges bemeneten, tetsz˝ oleges sz´ am´ u titkos´ıt´ ast végez, ahol a titkos´ıt´ ast a kih´ıv´ o Enckey (·) algoritmus´ aval végzi, 3. az A t´ amad´ o, két azonos hossz´ us´ ag´ u u ¨zenetet hat´ aroz meg, jel¨ olj¨ uk ezeket m0 , m1 -gyel, amelyeket ´ atad a kih´ıv´ onak, R 4. a kih´ıv´ ob← − {0, 1} v´ alaszt´ as alapj´ an meghat´ arozza az mb titkos´ıtott ∗ R értékét: c ← − Enckey (mb ), amelyet ´ atad az A t´ amad´ onak, 5. az A t´ amad´ o tetsz˝ oleges bemeneten, tetsz˝ oleges sz´ am´ u titkos´ıt´ ast végez, ahol a titkos´ıt´ ast a kih´ıv´ o Enckey (·) algoritmus´ aval végzi, 6. az A t´ amad´ o meghat´ aroz egy ˆb ∈ {0, 1} kimeneti értéket. 2.5. defin´ıci´ o. Az SKE szimmetrikus titkos´ıt´ asi rendszerben az A t´ amad´ o cpa 1 ˆ el˝ onye a k¨ ovetkez˝ oképpen adhat´ o meg: AdvSKE,A (k) = | Pr[b = b] − 2 |, ahol a b és ˆb értékeket a 2.2. k´ısérletben hat´ aroztuk meg. A választott ny´ılt sz¨ oveg alap´ u támadással szembeni CPA-biztonságot a következ˝ o értelmezés adja [21]: 2.6. defin´ıci´ o. Az SKE szimmetrikus titkos´ıt´ asi rendszer CPA-biztons´ ag´ u, ha b´ armely A probabilisztikus, polinomi´ alis idej˝ u t´ amad´ o esetében létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy Advcpa SKE,A (k) ≤ f (k), ahol Advcpa ertelmezésnél adtuk meg. SKE,A (k)-t a 2.5. ´

25

2.3.2. Választott rejtjelezett szöveg alap´ u támadás A választott rejtjelezett sz¨ oveg alap´ u támadással szembeni biztonság értelmezéséhez sz¨ ukséges megadni a k¨ ovetkez˝o k´ısérlet lépéssorozatát, amely k´ısérlet az A t´ amad´ o és k¨ ornyezete, a kih´ıvó között játszódik le. 2.3. k´ısérlet. 1. A kih´ıv´ o a Gen kulcsgener´ al´ o algoritmussal meghat´ arozza a key titkos´ıt´ o kulcsot, 2. az A t´ amad´ o tetsz˝ oleges sz´ am´ u titkos´ıt´ ast, illetve visszafejtést végez, a kih´ıv´ o Enckey (·) titkos´ıt´ o és Deckey (·) visszafejt˝ o algoritmus´ aval, 3. az A t´ amad´ o, két azonos hossz´ us´ ag´ u u ¨zenetet hat´ aroz meg, jel¨ olj¨ uk ezeket m0 , m1 -gyel, amelyeket ´ atad a kih´ıv´ onak, R 4. a kih´ıv´ ob← − {0, 1} v´ alaszt´ as alapj´ an meghat´ arozza az mb titkos´ıtott ∗ R értékét: c ← − Enckey (mb ), amelyet ´ atad az A t´ amad´ onak, 5. az A t´ amad´ o tetsz˝ oleges sz´ am´ u titkos´ıt´ ast, illetve visszafejtést végez, a kih´ıv´ o Enckey (·) titkos´ıt´ o és Deckey (c) visszafejt˝ o algoritmus´ aval, ahol a visszafejtést k¨ ul¨ onb¨ oz˝ o c bemenetekre kéri, azzal a megk¨ otéssel, hogy c 6= c∗ , 6. az A t´ amad´ o meghat´ aroz egy ˆb ∈ {0, 1} kimeneti értéket. 2.7. defin´ıció. Az SKE szimmetrikus titkos´ıt´ asi rendszerben az A t´ amad´ o cca 1 ˆ el˝ onye a k¨ ovetkez˝ oképpen adhat´ o meg: AdvSKE,A (k) = | Pr[b = b] − 2 |, ahol ˆ a b és b értékeket a 2.3. k´ısérletben hat´ aroztuk meg. A választott rejtjelezett sz¨ oveg alap´ u támadással szembeni CCAbiztonságot a k¨ ovetkez˝ o értelmezés adja [21]: 2.8. defin´ıció. Az SKE szimmetrikus titkos´ıt´ asi rendszer CCA-biztons´ ag´ u, ha b´ armely A probabilisztikus, polinomi´ alis idej˝ u t´ amad´ o esetében létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy Advcca SKE,A (k) ≤ f (k), ahol Advcca ertelmezésnél adtuk meg. SKE,A (k)-t a 2.7. ´

26

2.4. Szimmetrikus titkos´ıtási rendszerek osztályozása A szimmetrikus titkos´ıt´ o rendszereken bel¨ ul megk¨ ulönböztet¨ unk folyamtitkos´ıtó (stream-cipher) és blokktitkos´ıtó (block-cipher) rendszereket. Mindkét rendszer esetében a titkos´ıtáshoz sz¨ ukséges egy titkos adat, a titkos´ıtó kulcs. Amiben eltér egym´ astól a két rendszer az az adathalmaz feldolgozás´ anak m´ odja. A két k¨ ul¨ onb¨ oz˝ o titkos´ıt´ asi rendszer természetesen k¨ ulönböz˝o biztonsági el˝ o´ır´ asokat hat´ aroz meg, éppen ezért k¨ ulön tárgyaljuk a folyamtitkos´ıt´ okkal, illetve a blokktitkos´ıtókkal szembeni biztonsági követelményeket.

2.4.1. Folyamtitkos´ıtó rendszerek A folyamtitkos´ıt´ o rendszerek alatt azokat a rendszereket értj¨ uk, amelyek valamely probabilisztikus algoritmus seg´ıtségével, kiindulva egy kezdeti titkos adatból, a titkos´ıt´ o kulcsb´ ol, gener´ alnak egy 0 és 1 értékekb˝ol álló álvéletlen bitsorozatot. A gener´ alt bitsorozatot kulcsfolyamnak nevezik, amelyet aztán legt¨ obbsz¨ or bitenkénti (mod 2) összeadást végezve hozzáadnak a ny´ılt szöveghez. E m˝ uveletre a továbbiakban a ⊕ jelet fogjuk használni. Megjegyezz¨ uk, hogy a kulcsfolyam és ny´ılt szöveg összeadása történhet (mod 2n ) szerint is, ahol n pozit´ıv egész szám, pl. a Salsa20 esetében n = 32. Közismert azonban, hogy szoftver szintjén nem lehet véletlen biteket el˝oáll´ıtani, ezért azon algoritmusokat amelyekr˝ol azt áll´ıtjuk, hogy véletlen bitsorozatot ´ all´ıtanak el˝ o u ´gy h´ıvjuk, hogy álvéletlen bitsorozat generátorok, hiszen az ´ altaluk el˝ oa´ll´ıtott bitsorozatok igazából álvéletlen értékek. A titkos´ıtott rendszer biztons´ aga f¨ ugg az álvéletlen bitsorozat generátor kimenetét˝ ol, illetve meghat´ arozza a ⊕ m˝ uvelet tulajdonsága. A következ˝o tétel [61] magyar´ azatot ad arra, hogy titkos´ıtó rendszerek esetében miért használhat´ o a ⊕ m˝ uvelet: 2.1. tétel. Legyen X ∈ {0, 1}k és Y ∈ {0, 1}k két f¨ uggetlen, egyenletes eloszl´ as´ u val´ osz´ın˝ uségi v´ altoz´ o. Akkor a Z = X ⊕ Y val´ osz´ın˝ uségi v´ altoz´ o k is egyenletes eloszl´ as´ u lesz a {0, 1} halmazon. 27

A fenti tétel alapj´ an levonhatjuk azt a következtetést, hogy a folyamtitkos´ıtók biztons´ aga igaz´ ab´ ol az ´ alvéletlen bitsorozatot generáló algorit´ mustól f¨ ugg. Eppen ezért az elm´ ult években folyamtitkos´ıtó rendszerek alatt azokat az elj´ ar´ asokat értj¨ uk, amelyek meghatározzák az álvéletlen bitsorozat el˝oáll´ıt´ as´ anak m´ odj´ at. Ilyen generátorok az RC4 [28], a Salsa20 [8], a Legendre szimb´ olumot felhasználó Goubin, Mauduit és Sárközy által le´ırt gener´ atorcsal´ ad [33] vagy a négyzetreemelés f¨ uggvényen alapuló Blum-Blum-Shub [10] gener´ ator, stb. A továbbiakban megadjuk az ´ alvéletlen bitsorozat generátor azon értelmezését, amelynek ha eleget tesz az álvéletlen generátor, akkor biztonságosan alkalmazhat´ o kriptogr´ afiai rendszerekben ([36], [61]). 2.9. defin´ıció. Legyen G egy determinisztikus polinomi´ alis idej˝ u algoritmus, amely az x ∈ {0, 1}k bemeneten egy y ∈ {0, 1}l hossz´ us´ ag´ u kimeneti bitsorozatot ´ all´ıt el˝ o, ahol k < l. Ha b´ armely probabilisztikus polinomi´ alis idej˝ u R D algoritmusra és b´ armely r ← − {0, 1}l bitsorozat esetében létezik egy f (k) elhanyagolhat´ o f¨ uggvény, a k¨ ovetkez˝ o tulajdons´ aggal: R

| Pr[D(r) = 1] − Pr[D(G(x)) = 1]| ≤ f (k), ahol x ← − {0, 1}k , akkor azt mondjuk, hogy a G algoritmus kriptogr´ afiailag biztons´ agos ´ alvéletlen bitsorozat gener´ ator.

2.4.2. Blokktitkos´ıtó rendszerek Blokktitkos´ıtó rendszerek esetében egyszerre több byte-tömböt titkos´ıtunk, a titkos´ıtás pedig ugyannak a f¨ uggvénynek vagy permutációnak a többszöri végrehajtását jelenti, a k¨ ul¨ onb¨ oz˝ o byte-t¨ ombökön. A rendszer biztonságát az alkalmazott f¨ uggvény vagy permut´ ació határozza meg, illetve a titkos´ıtott byte-tömb¨ ok ¨ osszef˝ uzésének m´ odja. A byte-tömb¨ ok ¨ osszef˝ uzésének m´ odjára számos jól kidolgozott biztonságos technika létezik [61], amelyre jelen értekezésben nem tér¨ unk ki, az alkalmazott f¨ uggvény vagy permut´ aci´ o biztonságának vizsgálata, pedig az álvéletlen f¨ uggvények fogalm´ ahoz kapcsolódik. Az álvéletlen f¨ uggvény fogalmának a bevezetéséhez a k¨ ovetkez˝ okre van sz¨ ukség ([7], [24], [36]):

28

Jelölj¨ uk F uncX,Y -al azon halmazt, amely tartalmazza az összes olyan f¨ uggvényt, amely az X = {0, 1}N bemenetet az Y = {0, 1}M kimenetbe képezi le, ahol |X| = N és |Y | = M . Legyen F a k¨ ovetkez˝ o, két bemeneti paraméterrel rendelkez˝o f¨ uggvény: F : {0, 1}k × {0, 1}N → {0, 1}M . Minden egyes key ∈ {0, 1}k -ra, melyet el˝ore rögz´ıt¨ unk meghatározunk egy Fkey : {0, 1}N → {0, 1}M kulcsos f¨ uggvényt, u ´gy hogy: Fkey (x) = F (key, x). A kiválasztott key érték lesz a titkos´ıtó kulcs, Fkey pedig, eleget kell tegyen azon tulajdons´ agnak, hogy az Fkey (x), x ∈ {0, 1}N bemenetre polinomiális id˝oben meghat´ arozza az y ∈ {0, 1}M kimeneti értéket. Abban az esetben ha N = M , akkor Fkey permut´ aci´ o. Inform´ alisan az F ´ alvéletlen f¨ uggvény azt jelenti, hogy a f¨ uggvény polinomiális id˝ oben meg tudja hat´ arozni tetsz˝oleges bemenete esetén a kimeneti értékét, és nem szerkeszthet˝o olyan polinomiális idej˝ u algoritmus, amely k¨ ul¨ onbséget tudna tenni az Fkey és egy, a F uncX,Y f¨ uggvénycsaládból véletlenszer˝ uen kiv´ alasztott f¨ uggvény között. Az F f¨ uggvény ´ alvéletlen viselkedését, pedig a következ˝o formális defin´ıcióval adhatjuk meg [7]: 2.10. defin´ıci´ o. Az F f¨ uggvény ´ alvéletlen f¨ uggvény, ha b´ armely probabilisztiR kus, polinomi´ alis idej˝ u D algoritmusra és b´ armely key ← − {0, 1}k esetében, létezik egy f (k) elhanyagolhat´ o f¨ uggvény, a k¨ ovetkez˝ o tulajdons´ aggal: | Pr[D(G(·)) = 1] − Pr[D(Fkey (·)) = 1]| ≤ f (k), R

ahol G ← − F uncX,Y . A blokktitkos´ıt´ o rendszereknek a folyamtitkos´ıtókkal szembeni egyik el˝onye, hogy a titkos´ıt´ as folyamata párhuzamos´ıtható, a biztonsági kritériumok sokkal jobban tanulmányozottak, hátrányuk, pedig, hogy lass´ ubbak.

29

30

3. fejezet

Hash f¨ uggvények és u ¨zenethiteles´ıt˝ o k´ odok A lehetséges t´ amad´ asi t´ıpusok alapj´ an a bizalmas információcsere nem mindig biztos´ıtja egy adott u ¨zenet hiteles voltát. Abban az esetben, ha egy akt´ıv támad´ oval is sz´ amolni kell, akkor a rejtjelezés mellett sz¨ ukséges mind a k¨ uld˝o fél, mind az elk¨ uld¨ ott u ¨zenet hiteles´ıtése. Ennek megvalós´ıtására többféle technika is létezik, az egyik a hash f¨ uggvények alkalmazása, a másik az u ¨zenethiteles´ıt˝ o k´ odok.

3.1. Hash f¨ uggvények A hash f¨ uggvényeket (hash function) a kriptográfia több ter¨ uletén is alkalmazzák. A kriptogr´ afi´ aban alkalmazott hash f¨ uggvények az adatok integritás´ anak vizsg´ alat´ at biztos´ıtj´ ak. Gyakorlatban, leginkább a digitális alá´ırásokn´ al alkalmazz´ ak, de a CPA-biztonság´ u, illetve CCA-biztonság´ u titkos´ıtó rendszereknél is fontos szerepet kapnak. A hash f¨ uggvény egy tetsz˝ oleges hossz´ uság´ u u ¨zenetre egy rögz´ıtett hossz´ uság´ u kimenetet hat´ aroz meg, amelyet ellen˝orz˝o összegnek, lenyomatnak is szoktak h´ıvni ([41], [53]).

31

Jelölje, ahogy a 2.4.2. szakaszban is, F uncX,Y az összes olyan f¨ uggvény halmazát, amelyek értelmezési tartom´ anya X, és értéktartománya Y . Feltételezve, hogy |X| = N, |Y | = M és N ≥ M , akkor nyilvánvaló, hogy teljes¨ ul: |F uncX,Y | = M N . A H : X → Y hash f¨ uggvényt mindig a F uncX,Y halmazból választjuk ki. Feltételezve, hogy az u ¨zenet, amelynek meg szeretnénk határozni a hash értékét x, akkor y = H(x)-szel jel¨ olj¨ uk a kiszámolt hash értéket. A kriptogr´ afi´ aban alkalmazhat´ o hash f¨ uggvények három fontos tulajdonságnak kell eleget tegyenek, ami azt jelenti, hogy az alábbi három feladat egyike se legyen megoldhat´ o polinomi´ alis id˝oben: 1. feladat, egyir´ any´ u, ˝ oskép tulajdons´ ag (preimage, one-way property): BEMENET: legyen H : X → Y hash f¨ uggvény és y ∈ Y egy elem. KIMENET: az x érték, azzal a tulajdonsággal, hogy H(x) = y. 2. feladat, gyengén u ¨tk¨ ozésmentes, m´ asodik ˝oskép tulajdonság (second preimage property): BEMENET: legyen H : X → Y hash f¨ uggvény és x ∈ X egy elem. KIMENET: az x1 érték, azzal a tulajdonsággal, hogy x 6= x1 és H(x) = H(x1 ). 3. feladat, u ¨tk¨ ozésmentes tulajdons´ ag (collision-resistant property): BEMENET: legyen H : X → Y hash f¨ uggvény KIMENET: az x, x1 értékek, azzal a tulajdonsággal hogy x 6= x1 és H(x) = H(x1 ). 3.1. megjegyzés. B´ armely hash f¨ uggvény, amely u ¨tk¨ ozésmentes tulajdons´ ag´ u ugyanakkor gyengén u ¨tk¨ ozésmentes tulajdons´ ag´ u is. B´ armely hash f¨ uggvény, amely gyengén u ¨tk¨ ozésmentes tulajdons´ ag´ u ugyanakkor egyir´ any´ u tulajdons´ ag´ u is. A CPA, CCA-biztons´ ag értelmezéseknél a szakirodalom [5] bevezeti a véletlen orákulum modellt, amely a hash f¨ uggvények egy ideális esetét modellezi. Inform´ alisan ez azt jelenti, hogy a hash f¨ uggvény, az F uncX,Y f¨ uggvényhalmazb´ ol véletlenszer˝ uen ker¨ ul kiválasztásra és a hash érték meghatározása egy or´ akulum megkérdezése során valós´ıtható meg, azaz nem alkalmazható matematikai formula vagy algoritmus a hash érték meghatározására. A val´ os életben természetesen nem létezik ilyen f¨ uggvény, 32

viszont szerkeszthet˝ o olyan hash f¨ uggvény, amelynek viselkedése hasonló a véletlen or´ akuluméhoz. Form´ alisan ezt azt jelenti, hogy [61]: R

3.1. tétel. Legyen H : X → Y hash f¨ uggvény, ahol H ← − F uncX,Y és legyen X0 ⊆ X. Feltételezz¨ uk tov´ abb´ a, hogy a H(x) érték csak az x ∈ X0 esetekben ker¨ ult meghat´ aroz´ asra. Ha a hash f¨ uggvény viselkedése hasonl´ oa véletlen or´ akuluméhoz, akkor fenn´ all, hogy Pr[H(x) = y] = 1/M , minden x ∈ X \ X0 és y ∈ Y elemre. Mivel az u ¨tk¨ ozésmentes tulajdonság a hash f¨ uggvények legfontosabb tulajdons´ aga, az u ´jabb szakirodalom [7] a hash f¨ uggvények u ¨tközésmentes tulajdons´ ag´ ara vonatkoz´ oan, ´ arnyaltabb értelmezéseket is megad. Ahhoz, hogy ezek form´ alis értelmezését meg lehessen adni, a hash f¨ uggvény fogalma mellett be kell vezetni a kulcsos hash f¨ uggvény fogalmát [7]. A kulcsos hash egy olyan f¨ uggvény, amely a következ˝o hash f¨ uggvénycsal´ adb´ ol ker¨ ul kiv´ alaszt´ asra: Hash : K × X → Y . Minden egyes key ∈ K-ra meghat´ arozható egy Hkey : X → Y kulcsos hash f¨ uggvény, ahol a key meghat´ aroz´ asa egy probabilisztikus, polinomiális idej˝ u algoritmussal t¨ orténik. Ilyenkor azt mondjuk, hogy a kulcsos hash f¨ uggvény a f¨ uggvénycsal´ ad egy péld´ anya. Egy hash f¨ uggvénycsal´ ad biztonságának vizsgálatakor legf˝oképpen azt figyelik, hogy egy t´ amad´ onak milyen esélye van arra, hogy u ¨tközést találjon a f¨ uggvénycsal´ ad egy péld´ anya esetén. Aszerint, hogy mikor ker¨ ul a támadó birtokába a key érték t¨ obbféle tulajdonság´ u hash f¨ uggvény értelmezhet˝o [7]. Ha a key érték birtokl´ asa el˝ ott ker¨ ulnek kiválasztásra az x, illetve x1 értékek, akkor univerz´ alis (universal) hash f¨ uggvény értelmezhet˝o, amelyet a szakirodalom a CR0-val jel¨ ol (ahol az x és x1 értékek jelentése a 3. feladatnak megfelel˝ o). Form´ alisan az A támadó el˝onyét a következ˝o valósz´ın˝ uséggel értelmezhetj¨ uk: R

R

AdvCR0,A (Hkey ) = Pr[(x, x1 ) ← − A(·), key ← −K: x 6= x1 , Hkey (x) = Hkey (x1 )].

33

3.1. defin´ıció. Egy Hkey : X → Y kulcsos hash f¨ uggvény univerz´ alis hash f¨ uggvény, ha b´ armely probabilisztikus polinomi´ alis idej˝ u A algoritmus esetén létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy AdvCR0,A (Hkey ) ≤ f (k), ahol az A algoritmus fut´ asi ideje k f¨ uggvénye. Ha az x érték a key birtokl´ asa el˝ ott, az x1 érték pedig a key birtoklása után ker¨ ul kiv´ alaszt´ asra akkor a cél-¨ utközésmentes hash (target collision-resistant) f¨ uggvény értelmezhet˝ o, amelyet a szakirodalom CR1gyel jelöl. Form´ alisan az A t´ amad´ o el˝ onyét a következ˝o valósz´ın˝ uséggel értelmezhetj¨ uk: R

R

R

AdvCR1,A (Hkey ) = Pr[(x, st) ← − A(·), key ← − K, x1 ← − A(key, st) : x 6= x1 , Hkey (x) = Hkey (x1 )], ahol st azt az inform´ aci´ ot jelenti, amelyet a támadó megpróbál megszerezni. 3.2. defin´ıció. Egy Hkey : X → Y kulcsos hash f¨ uggvény cél-¨ utk¨ ozésmentes hash f¨ uggvény, ha b´ armely probabilisztikus polinomi´ alis idej˝ u A algoritmus esetén létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy AdvCR1,A (Hkey ) ≤ f (k), ahol az A algoritmus fut´ asi ideje k f¨ uggvénye. Ha az x és x1 értékek a key birtoklása után ker¨ ulnek kiválasztásra, akkor az u ¨tközésmentes hash f¨ uggvény (collision-resistant) értelmezhet˝o, amelyet a szakirodalom CR2-vel jel¨ ol. Formálisan az A támadó el˝onyét a következ˝o valósz´ın˝ uséggel értelmezhetj¨ uk: R

R

AdvCR2,A (Hkey ) = Pr[key ← − K, (x, x1 ) ← − A(key) : x 6= x1 , Hkey (x) = Hkey (x1 )]. 3.3. defin´ıció. Egy Hkey : X → Y kulcsos hash f¨ uggvény u ¨tk¨ ozésmentes hash f¨ uggvény, ha b´ armely probabilisztikus polinomi´ alis idej˝ u A algoritmus esetén létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy AdvCR2,A (Hkey ) ≤ f (k), ahol az A algoritmus fut´ asi ideje k f¨ uggvénye. Megállap´ıthat´ o, hogy egy CR2 t´ıpus´ u hash f¨ uggvény egyben CR1 t´ıpus´ u is, egy CR1 t´ıpus´ u, pedig CR0 is egyben, ami alapján fennállnak a következ˝o egyenl˝ otlenségek: 34

AdvCR0,A0 (Hkey ) ≤ AdvCR1,A1 (Hkey ), ahol A0 tetsz˝oleges t´ amad´ o algoritmus, amelynek futási ideje ugyanaz mint az A1 támad´ o algoritmusnak. AdvCR1,A1 (Hkey ) ≤ AdvCR2,A2 (Hkey ), ahol A1 tetsz˝oleges t´ amad´ o algoritmus, amelynek futási ideje ugyanaz mint az A2 támad´ o algoritmusnak. A kriptogr´ afi´ aban széles k¨ orben alkalmazott SHA hash f¨ uggvénycsalád példányair´ ol azt feltételezik, hogy CR2 t´ıpus´ u hash f¨ uggvények. ¨ ozésmentes tulajdons´ Utk¨ aggal rendelkez˝o hash f¨ uggvényeket norma f¨ uggvényekb˝ ol kiindulva Bérczes, Ködmön és Peth˝o is szerkesztett [16], amelyet a Kripto Kft. Codefish néven hozott kereskedelmi forgalomba. A f¨ uggvény viselkedését a kés˝obbiekben is tanulmányozták [15] és bizony´ıtott´ ak el˝ oképellen´ all´ os´ agát, illetve hogy jó statisztikai tulajdonságokkal rendelkezik. Meg´ allap´ıtották azt is, hogy a f¨ uggvény nem rendelkezik a lavinahat´ as tulajdonsággal a szigor´ uan vett értelemben, de ezt aszimptotikusan megk¨ ozel´ıti.

¨ 3.2. Uzenethiteles´ ıt˝ o k´ odok Az u ¨zenethiteles´ıt˝ o k´ od (messages authentication code) egy olyan f¨ uggvény, amely egy titkos inform´ aci´ o, a MAC-kulcs alapján, a bemeneti u ¨zenetre (bit-szekvenci´ ara) egy r¨ ogz´ıtett hossz´ uság´ u ellen˝orz˝o összeget egy MACértéket hat´ aroz meg [52]. Az u ¨zenethiteles´ıt˝o kód egyike a legfontosabb kriptográfiai primit´ıvnek, hiszen a bizalmas információcsere lehet˝osége mellett az u ¨zenet val´ odis´ ag´ at is garantálni kell, amit u ¨zenethiteles´ıt˝o kódok alkalmazás´ aval lehet elérni. Az u ¨zenethiteles´ıt˝o kód szerepe tehát, hogy ne lehessen a bemeneti u ¨zenet egyetlen bitjét se megváltoztatni, se kitörölni, se u ´j bitet hozz´ aadni. A tov´ abbiakban MAC-kódként fogunk hivatkozni az u ¨zenethiteles´ıt˝ o k´ odra, amelynek formális értelmezése a következ˝o [36]:

35

3.4. defin´ıció. Egy MAC-k´ od h´ arom algoritmussal értelmezhet˝ o, egy (K, M, T ) halmazh´ armas felett, ahol K a MAC-kulcsok halmaza, M az u ¨zenetek halmaza, T a MAC-értékek (a ”tag”-ek) halmaza. A h´ arom eml´ıtett algoritmus, pedig a k¨ ovetkez˝ o: • Gen, a kulcsgener´ al´ o, probabilisztikus algoritmus, amely polinomi´ alis id˝ oben az 1k bemeneten meghat´ arozza a MAC-kulcsot, jel¨ olj¨ uk a R tov´ abbiakban ezt key-el: key ← − Gen(1k ), ahol key ∈ K, és k a rendszer biztons´ agi paramétere, a gener´ alt kulcs bithossza, • M ackey , az u ¨zenethiteles´ıt˝ o k´ odot el˝ o´ all´ıt´ o, probabilisztikus algoritmus, a MAC-f¨ uggvény, amely polinomi´ alis id˝ oben a key, MAC-kulcs R alapj´ an meghat´ arozza az m ∈ M u ¨zenetre a t MAC-értéket: t ← − M ackey (m), ahol t ∈ T , • V erkey , a determinisztikus, ellen˝ orz˝ o algoritmus, amely az key, m, t bemeneti értékekre leellen˝ orzi a t MAC-érték validit´ as´ at: V erkey (m, t) → 1, ha az u ¨zenet sértetlen, m´ asképp null´ at hat´ aroz meg. Ha a MAC-f¨ uggvény bemenetének hossza N bit, akkor a lehetséges bemenetek száma 2N . Ha a MAC-f¨ uggvény kimenete egy M -bites érték, akkor ez azt jelenti, hogy 2M k¨ ul¨ onb¨ oz˝ o MAC-értéket lehet meghatározni. Mivel N általában sokkal nagyobb, mint M , a lehetséges u ¨zenetek 2N száma M ´ is sokkal nagyobb, mint a lehetséges MAC-értékek 2 száma. Atlagosan N −M minden MAC-értéket 2 k¨ ul¨ onb¨ oz˝ o bemenet határoz meg. A MAC-f¨ uggvény, hasonl´ o egy titkos´ıtó f¨ uggvényhez, azzal a k¨ ulönbséggel, hogy az inverz, a visszafejt˝ o f¨ uggvényt nem kell értelmezni. Ezekb˝ol a tulajdons´ agokb´ ol kifoly´ olag a biztonsági el˝o´ırások egy MACf¨ uggvénnyel szemben m´ asok és nem is olyan szigor´ uak, mint egy titkos´ıtó f¨ uggvény esetében. A MAC-f¨ uggvénnyel szemben a következ˝o követelmények állap´ıthat´ oak meg [47]: • A MAC-f¨ uggvény bemenete egy olyan m u ¨zenet, amelynek hosszára nincs korl´ at meg´ allap´ıtva, a kimenet hossza, amelyet jelölj¨ unk M -mel, pedig sokkal r¨ ovidebb. Biztons´ agi okokból az M ≥ 128, 256, . . . bit. • A Kerchoffs-elv alapj´ an a MAC-f¨ uggvény le´ırása nyilvános, a rendszer egyetlen titkos inform´ aci´ oja a key. 36

• Adott MAC-f¨ uggvény, adott m bemenet és key esetében a M ackey (m) érték polinomi´ alis id˝ oben meghatározható kell, hogy legyen. • Adott MAC-f¨ uggvény és adott m bemenet esetében sem a M ackey (m) érték, sem a key kulcs nem határozható meg polinomiális id˝oben 1/2N -nél nagyobb val´ osz´ın˝ uséggel; még abban az esetben sem, ha a támad´ o t¨ obb (mi , M ackey (mi )) párral rendelkezik, ahol az mi bemenetek a t´ amad´ o´ altal tetsz˝ olegesen szerkesztett u ¨zenetek. Ahhoz, hogy a kommunik´ aci´ oban résztvev˝o felek számára egyaránt biztos´ıtva legyen a bizalmas inform´ aci´ ocsere és az ny´ılt szöveg sértetlensége, kétféle technika létezik a MAC-érték és a rejtjelezett szöveg egy¨ uttes meghatározás´ ara. Az els˝ o technika szerint a ny´ılt szöveg után hozzáf˝ uzz¨ uk a ny´ılt szövegre kiszámolt MAC-értéket és ezen u ´j értékre alkalmazunk egy Enc titkos´ıtó f¨ uggvényt. A m´ asodik technika szerint el˝obb alkalmazzuk az Enc titkos´ıtó f¨ uggvényt a ny´ılt sz¨ ovegen és az ´ıgy kapott rejtjelezett szövegre számoljuk ki a MAC-értéket, majd ezt a két értéket egymás után f˝ uzz¨ uk. Mindkét esetben a titkos´ıt´ o f¨ uggvény és a MAC-f¨ uggvény kulcsa k¨ ulönböz˝ o kell legyen. A két technika k¨ ul¨ onb¨ oz˝ o t´ amadási lehet˝oségeket határoz meg. A MAC-érték kisz´ am´ıt´ asa sor´ an az u ¨zenetet blokkokra osztják, amelyeket standard el˝ o´ır´ asoknak megfelel˝oen összeláncolnak [7]. A támadási lehet˝oségeket az u ¨zenet blokkjaira alkalmazott láncolási technika is meghatározza. A MAC-f¨ uggvények elleni t´ amadási lehet˝oségeket a szakirodalom [60] két csoportra osztja: kriptoanal´ızisen alapuló támadások és brute-force t´ıpus´ u támad´ asok. A kriptoanal´ızis sor´ an a t´ amad´ o a MAC-f¨ uggvények szerkesztésénél alkalmazott technik´ ak gyengeségeit veszi támadásba. A brute-force t´ıpus´ u t´ amad´ asok esetében a támadó vagy a MAC-kulcsot próbálja meghat´ arozni vagy egy érvényes MAC-értéket akar el˝oáll´ıtani a bemeneti u ¨zenet ismeretének hi´ any´ aban. A támadó keresési technikát alkalmaz az ¨ osszes lehetséges bemeneti, kimenetei értékpárok között.

37

Abban az esetben, ha a MAC-kulcs meghatározása a cél, akkor a támadó a következ˝ oképpen j´ ar el. Ha feltételezz¨ uk, hogy a MAC-kulcs hossza |key| bit és a t´ amad´ o rendelkezik egy u ¨zenet és a neki megfelel˝o MAC-érték párral, akkor a t´ amad´ as abb´ ol áll, hogy a támadó meghatározza az összes lehetséges kulcs értékekre a megfelel˝o MAC-értéket és összehasonl´ıtja, hogy melyik tal´ al az eredeti MAC-értékkel. Ez azt jelenti, hogy minden kulcsértékre meg kell hat´ arozza a MAC-értéket, azaz 2|key| MACértéket kell el˝o´ all´ıtson. A MAC-érték szerkesztési módjából kifolyólag fennáll az a lehet˝ oség, hogy t¨ obb kulcsértékre ugyanazt a MAC-értéket kapja, ebben az esetben egy u ´j (¨ uzenet, MAC-érték) párra kell elvégezni a szám´ıtásokat. Abban az esetben, ha egy érvényes MAC-értéket akar el˝oáll´ıtani, akkor a MAC-érték nagys´ agrendje hat´ arozza meg a brute-force támadás kivitelezhet˝oségét. Ha a MAC-érték bithossza M , akkor az el˝oáll´ıtható MACértékek száma 2M . Figyelembe véve a sz´ am´ıt´ ogépek jelenlegi szám´ıtási kapacitását, a minimális biztons´ agi k¨ ovetelmény egy MAC-kóddal szemben az, hogy fennálljon: min(|key|, M ) ≥ 128 bit. A MAC-k´ odok biztons´ ag´ anak formális értelmezése is megadható [36] amelyr˝ol azonban fontos megjegyezni, hogy er˝os megkötést tartalmaz, melyet nem minden gyakorlatban használt MAC-kód teljes´ıt. Az értelmezéshez sz¨ ukséges megadni egy k´ısérlet lépéssorozatát, ahol a k´ısérlet az A támadó és k¨ ornyezete, a kih´ıv´ o k¨ oz¨ ott játszódik le. 3.1. k´ısérlet. 1. A kih´ıv´ o a Gen kulcsgener´ al´ o algoritmussal meghat´ arozza az key MAC-kulcsot, 2. az A t´ amad´ o tetsz˝ oleges sz´ am´ u MAC-értéket hat´ aroz meg a kih´ıv´ o M ackey (·) algoritmusa seg´ıtségével; jel¨ olj¨ uk a meghat´ arozott MACértékek halmaz´ at M-el, 3. az A t´ amad´ o meghat´ aroz egy (m, t) értékp´ art, amelyet ´ atad a kih´ıv´ onak, 4. ha V erkey (m, t) = 1 és m 6∈ M, akkor az A t´ amad´ o megadja a b = 1 értéket, m´ asképp egy b 6= 1 értéket hat´ aroz meg.

38

3.5. defin´ıci´ o. Az AdvM AC,A (k) = P r[b = 1] val´ osz´ın˝ uséggel az A t´ amad´ o el˝ onyét értelmezz¨ uk, ahol a b értéket a 3.1. k´ısérletben hat´ aroztuk meg. 3.6. defin´ıci´ o. A MAC-k´ od biztons´ agos, ha b´ armely A probabilisztikus, polinomi´ alis idej˝ u t´ amad´ o esetében létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy hogy: AdvM AC,A (k) ≤ f (k). A gyakorlatban két fajta MAC-f¨ uggvényt szoktak alkalmazni, az egyik hash f¨ uggvényeken alapul´ o MAC-f¨ uggvény, a HMAC [4], a másik a CBC módban alkalmazott blokktitkos´ıt´ o rendszereken alapuló MAC-f¨ uggvény [60].

39

40

4. fejezet

Aszimmetrikus titkos´ıtási rendszerek biztonsága 4.1. A matematikai modell Aszimmetrikus vagy nyilv´ anos kulcs´ u titkos´ıtási rendszereket az 1970-es évek közepe ´ ota alkalmaznak a kriptográfiában, pontosabban Diffie és Hellman 1976-os cikke ´ ota [25]. A legt¨ obb ma is széles körben alkalmazott rendszer matematikai alapjait ekkor fektették le, viszont a létez˝o rendszerekkel szembeni biztons´ agi elv´ ar´ asok az´ ota igencsak megváltoztak [38]. Ezért számos algoritmus, protokoll implementálása az els˝o specifikációk óta, jelenleg más m´ odon t¨ orténik. Péld´ aul az RSA esetében a jelenlegi standardok az RSA–OAEP alapj´ an adj´ ak meg a titkos´ıtó algoritmus specifikációját [6]. Az ElGamal-titkos´ıt´ onak a Cramer és Shoup által ajánlott rendszer jelenti a biztons´ agos verzi´ oj´ at [21], a Rabin-titkos´ıtó egyik biztonságos verzióját, pedig Boneh ´ırta le [14]. A t¨ obbsz¨ or¨ os titkos´ıtás (multiple encryption) egyik biztonságos haszn´ alat´ anak m´ odj´ at Dodis és Katz adták meg [26], amelyre a korábbi szakirodalomban t¨ obbsz¨ or találunk nem biztonságos ajánlásokat is. Hogy megadhassuk a jelenlegi biztonsági elvárásoknak is megfelel˝o biztonsághoz kapcsol´ od´ o értelmezéseket el˝oször az aszimmetrikus titkos´ıtási rendszerek matematikai értelmezését adjuk meg. 41

4.1. defin´ıció. Jel¨ olje P KE azt az aszimmetrikus titkos´ıt´ asi vagy nyilv´ anos kulcs´ u titkos´ıt´ asi rendszert, amely h´ arom algoritmussal értelmezhet˝ o, a ((P K, SK), M, C) felett, ahol M a ny´ılt sz¨ ovegek egy véges halmaza, C a rejtjelezett sz¨ ovegek egy véges halmaza, P K a nyilv´ anos kulcsok egy véges halmaza, és SK a titkos kulcsok véges halmaza. A h´ arom eml´ıtett algoritmus, pedig a k¨ ovetkez˝ o: • Gen, a probabilisztikus kulcsgener´ al´ o algoritmus, amely polinomi´ alis id˝ oben, az 1k bemeneten meghat´ arozza a (pk, sk) kulcsp´ art: R k (pk, sk) ← − Gen(1 ), ahol pk ∈ P K a nyilv´ anos kulcs és sk ∈ SK a titkos kulcs és k ∈ Z≥0 a rendszer biztons´ agi paramétere, amely legt¨ obb esetben a gener´ alt kulcs bithossza, • az Encpk a probabilisztikus rejtjelez˝ o algoritmus, amely polinomi´ alis id˝ oben végzi a rejtjelezést, az m ∈ M bemenetre; a pk nyilv´ anos R kulcs ismeretében meghat´ arozza a c ∈ C rejtjelezett sz¨ oveget: c ← − Encpk (m), • a Decsk a visszafejt˝ o algoritmus, amely polinomi´ alis id˝ oben, determinisztikusan végzi a visszafejtést, az sk titkos kulcs alapj´ an a c ∈ C rejtjelezett sz¨ ovegen: m ← Decsk (c); hiba esetében, kimenetként visszautas´ıt´ ou ¨zenetet ad. A rendszer helyessége érdekében megkövetelj¨ uk, hogy adott (pk, sk) kulcspár és m ny´ılt sz¨ ovegre fenn´ alljon, hogy Decsk (Encpk (m)) = m. A rendszer helyességét illet˝ oen, a jelenlegi szakirodalom [21] ennél sokkal árnyaltabban fogalmaz, mégpedig a k¨ ovetkez˝o követelményeket ´ırja el˝o meg: • adott m ∈ M ny´ılt sz¨ oveg és c ∈ C rejtjelezett szöveg esetében a (pk, sk) ∈ P K × SK kulcspár nem megfelel˝o, ha fennáll: Decsk (Encpk (m)) 6= m, • annak a val´ osz´ın˝ usége, hogy a Gen kulcsgeneráló algoritmus nem megfelel˝o (pk, sk) kulcsp´ art gener´ al a k bemenet f¨ uggvényében elhanyagolhat´ oan n˝ o.

42

4.2. Egyirány´ u f¨ uggvények Aszimmetrikus rendszerek szerkesztéséhez egyirány´ u f¨ uggvényekre (oneway function) van sz¨ ukség. Az egyirány´ u f¨ uggvények olyan f¨ uggvények, amelyekre fenn´ all, hogy a f¨ uggvény bármely bemeneti értékére hatékony kiértékelési algoritmus adhat´ o meg, másfel˝ol az inverz elem meghatározás´ ara nem ismert hatékony algoritmus. Form´ alisan a k¨ ovetkez˝ o értelmezés adható meg [18]: 4.2. defin´ıci´ o. A g : X → Y f¨ uggvény egyir´ any´ u, ha fenn´ all a k¨ ovetkez˝ o két tulajdons´ ag: 1. (hatékony kiértékelés) létezik egy polinomi´ alis idej˝ u algoritmus, amely az x ∈ X bemenetre meghat´ arozza a g(x) ∈ Y értéket, 2. (nehéz az inverz elem meghat´ aroz´ asa) b´ armely probabilisztikus polinomi´ alis idej˝ u A algoritmus esetében létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy: R

Pr[g(A(g(x), 1k )) = g(x)] ≤ f (k), ahol x ← − X. A gyakorlatban egyir´ any´ u f¨ uggvények csak bizonyos feltételezések mellett léteznek. Ahhoz, hogy feltételezések nélk¨ uli egyirány´ u f¨ uggvények létezésér˝ol beszélhess¨ unk sz¨ ukséges lenne a h´ıres N P 6= P áll´ıtás bizony´ıtása ([39], [56]). Az eml´ıtett feltételezések az angol kriptográfiai terminológiában basic assumption néven ismertek. Abban az esetben, ha a g f¨ uggvény bijekt´ıv, és az X értelmezési tartomány megegyezik az Y érték tartománnyal, azt mondjuk, hogy a g egyirány´ u permut´ aci´ o. Kriptorendszerek szerkesztéséhez, azonban nem mindig elégségesek az egyirány´ u f¨ uggvények, sz¨ ukséges az egyirány´ u csapóajtó f¨ uggvény (one-way trapdoor function) fogalm´ anak értelmezése. Az egyir´ any´ u csap´ oajt´ o f¨ uggvények olyan f¨ uggvények, amelyekre igaz, hogy a f¨ uggvény b´ armely bemeneti elemére hatékony kiértékelési algoritmus adható meg, m´ asfel˝ ol az inverz elem meghatározására nem ismert hatékony algoritmus, csak abban az esetben ha adott egy plusz információ is. Form´ alisan a k¨ ovetkez˝ o értelmezés adható meg [18]: 43

4.3. defin´ıció. A g : X → Y f¨ uggvény egyir´ any´ u csap´ oajt´ o f¨ uggvény, ha fenn´ allnak a k¨ ovetkez˝ o tulajdons´ agok: 1. létezik egy Gen algoritmus, amely polinomi´ alis id˝ oben, az 1k bemeneten meghat´ arozza a td plusz inform´ aci´ ot, 2. létezik egy polinomi´ alis idej˝ u algoritmus, amely az x ∈ X bemenetre meghat´ arozza a g(x) ∈ Y értéket, 3. b´ armely probabilisztikus polinomi´ alis idej˝ u A algoritmus esetében létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy: R

Pr[g(A(g(x), 1k )) = g(x)] ≤ f (k), ahol x ← − X, 4. létezik egy determinisztikus polinomi´ alis idej˝ u B algoritmus, amely esetében fenn´ all: R

g(B(g(x), td, 1k )) = g(x), ahol x ← − X.

4.3. Kriptográfiai feltételezések A következ˝okben megadjuk azokat a feltételezéseket, amelyeket az értekezés során tanulmányozott rendszerek esetében használunk ([36], [18]). Ezen feltételezések alapj´ an kijelenthet˝ o, hogy létezik egyirány´ u f¨ uggvény.

4.3.1. A faktorizációs feltételezés A faktorizációs feltételezés (factoring assumption) a következ˝oket áll´ıtja: legyen Genf act egy algoritmus, amely polinomiális id˝oben, az 1k bemeneten R meghatározza az (n, p, q) sz´ amh´ armast: (n, p, q) ← − Genf act (1k ) u ´gy, hogy p, q k-bites pr´ımsz´ amok és n = p · q. 4.4. defin´ıció. A faktoriz´ aci´ os feltételezés, a Genf act algoritmus ´ altal gener´ alt értékek f¨ uggvényében, azt jelenti, hogy b´ armely probabilisztikus, polinomi´ alis idej˝ u A algoritmus esetében, létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy Pr[A(n) = (p, q)] ≤ f (k). 44

4.3.2. Az RSA-feltételezés Az RSA-feltételezés (RSA assumption) a következ˝oket áll´ıtja: legyen GenRSA egy algoritmus, amely polinomiális id˝oben, az 1k bemeneten megR határozza az (n, p, q, e, d) sz´ am¨ ot¨ ost: (n, p, q, e, d) ← − GenRSA (1k ) u ´gy, hogy: • n = p · q, és p, q k-bites pr´ımszámok, R all: e · d ≡ 1 (mod (p − 1) · (q − 1)). • e← − Z∗n , és d-re fenn´ 4.5. defin´ıci´ o. Az RSA-feltételezés, a GenRSA algoritmus ´ altal gener´ alt értékek f¨ uggvényében, azt jelenti, hogy b´ armely probabilisztikus, polinomi´ alis idej˝ u A algoritmus esetében, létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy Pr[A(n, e) = d] ≤ f (k).

4.3.3. A kvadratikus maradék feltételezés A kvadratikus maradék feltételezés (quadratic residuosity assumption) a következ˝ oket ´ all´ıtja: legyen GenQR egy algoritmus, amely polinomiális id˝ oben, az 1k bemeneten meghatározza az (n, p, q) számhármast: R (n, p, q) ← − GenQR (1k ) u ´gy, hogy p, q k-bites pr´ımszámok és n = p · q. Jelölj¨ uk QRn -el a kvadratikus maradékok halmazát (mod n) szerint, formálisan: QRn = {x ∈ Z∗n |∃z ∈ Z∗n : z 2 = x (mod n)}.

Jelölj¨ uk QNR+1 amok halmazát, amelyek nem kvadratikus n -el azon sz´ maradékok (mod p) és (mod q) szerint sem, ahol formálisan: ∗ ∗ 2 QNR+1 es u2 = x (mod q)}. n = {x ∈ Zn |¬∃z, u ∈ Zn : z = x (mod p) ´

4.6. defin´ıci´ o. Annak az eld¨ ontése, hogy egy sz´ am kvadratikus maradék vagy sem, a GenQR algoritmus ´ altal gener´ alt értékek f¨ uggvényében, azt jelenti, hogy b´ armely probabilisztikus, polinomi´ alis idej˝ u A algoritmus esetében, létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy | Pr[A(n, xqr ) = 1] − Pr[A(n, xqnr ) = 1]| ≤ f (k), ahol R

R

xqr ← − QRn és xqnr ← − QNR+1 n . 45

4.3.4. A diszkrét logaritmus feltételezés A diszkrét logaritmus feltételezés (discrete logarithm assumption, DL assumption) a k¨ ovetkez˝ oket ´ all´ıtja: legyen GenDL egy algoritmus, amely polinomiális id˝ oben, az 1k bemeneten meghatározza az (G, p, g) elemeket R − GenDL (1k ) u (G, p, g) ← ´gy, hogy: • G egy ciklikus csoport, amelynek rendje egy k-bites szám: p, • g a G csoport gener´ ator eleme. 4.7. defin´ıció. Az diszkrét logaritmus feltételezés, a GenDL algoritmus ´ altal gener´ alt értékek f¨ uggvényében, azt jelenti, hogy b´ armely probabilisztikus, polinomi´ alis idej˝ u A algoritmus esetében, létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy Pr[A(G, p, g, h) = x] ≤ f (k), ahol fenn´ all, hogy g x = h.

4.3.5. A döntési Diffie–Hellman-feltételezés A döntési Diffie–Hellman-feltételezés (Decisional Diffie-Hellman assumption, DDH assumption) a k¨ ovetkez˝ oket ´ all´ıtja: legyen GenDDH egy algoritmus, amely polinomi´ alis id˝ oben, az 1k bemeneten meghatározza az (G, p, g) R elemeket (G, p, g) ← − GenDDH (1k ) u ´gy, hogy: • G egy ciklikus csoport, amelynek rendje egy k-bites szám: p, • g a G csoport gener´ ator eleme. 4.8. defin´ıció. A d¨ ontési Diffie–Hellman-feltételezés, a GenDDH algoritmus ´ altal gener´ alt értékek f¨ uggvényében, azt jelenti, hogy b´ armely probabilisztikus polinomi´ alis idej˝ u A algoritmus esetében, létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy | Pr[A(G, p, g, g x , g y , g z ) = 1] − Pr[A(G, p, g, g x , g y , g xy ) = 1]| ≤ f (k), ahol R

x, y, z ← − Zp .

46

4.4. Biztonságértelmezések Az aszimmetrikus titkos´ıt´ ok esetében a biztonság értelmezésekor figyelembe kell venni, hogy a t´ amad´ o rendelkezik a nyilvános kulccsal, ezért bármikor, tetsz˝oleges sz´ am´ u titkos´ıt´ ast tud végrehajtani, amelynek eredményét megvizsgálva sikeres t´ amad´ ast kezdeményezhet. A támad´ as sor´ an, azon plusz információ, amely a nyilvános kulcs ismeretét jelenti, lényegesen megv´ altoztatja az aszimmetrikus titkos´ıtás esetében a biztons´ agi kritériumokat [43]. Ez a plusz információ azt is jelenti, hogy az aszimmetrikus rendszereknél a két legfontosabb támadási t´ıpus amelyet meg kell vizsg´ alni a választott ny´ılt szöveg alap´ u támadás ´ és a választott rejtjelezett sz¨ oveg alap´ u támadás. Eppen ezért, jelen értekezésben nem tér¨ unk ki a passz´ıv támadóval szembeni biztonsági kritériumokra. Mindkét t´ amad´ asi t´ıpus esetében megfogalmazhatóak az általános biztons´ agi k¨ ovetelmények, megadhatóak a biztonságértelmezések, amelyek azonban sokszor nagyon er˝ os megkötéseket tartalmaznak, ´ıgy egy adott helyzetben a kriptogr´ afiai rendszer tervezésekor d˝ol el, hogy hogyan érdemes betartani ezeket a biztons´ agi kritériumokat.

4.4.1. Választott ny´ılt szöveg alap´ u támadás A választott ny´ılt sz¨ oveg alap´ u támadás esetében feltételezz¨ uk, hogy a támad´ o a titkos´ıt´ o algoritmus seg´ıtségével meg tudja határozni egy tetsz˝oleges ny´ılt sz¨ oveg rejtjelezett értékét, ahol a kiválasztásra ker¨ ul˝o ny´ılt szövegeket a t´ amad´ o hat´ arozza meg. A támadás adapt´ıv formája azt jelenti, hogy a t´ amad´ o´ altal aszerint ker¨ ulnek kiválasztásra a ny´ılt szövegek, hogy mi volt egy kor´ abbi titkos´ıt´ as eredménye. Ahogy a szimmetrikus titkos´ıtásnál, u ´gy itt is a biztons´ agértelmezés megadása egy k´ısérlet kimeneti eredményének a vizsg´ alat´ aval t¨ orténik [21]. A sz¨ ukséges lépéssorozat, a megfelel˝o k´ısérlet esetében a következ˝o, ahol a k´ısérlet az A t´ amad´ o és k¨ ornyezete, a kih´ıvó között játszódik le. 4.1. k´ısérlet. 1. A kih´ıv´ o a Gen kulcsgener´ al´ o algoritmussal meghat´ arozza a (pk, sk) kulcsp´ art, majd a pk nyilv´ anos kulcsot ´ atadja az A t´ amad´ onak, 47

2. az A t´ amad´ o tetsz˝ oleges sz´ am´ u titkos´ıt´ ast végez a pk nyilv´ anos kulcs ismeretében, ahol a titkos´ıt´ ast a kih´ıv´ o Encpk (·) algoritmus´ aval végzi, 3. az A t´ amad´ o, két azonos hossz´ us´ ag´ u u ¨zenetet hat´ aroz meg, jel¨ olj¨ uk ezeket m0 , m1 -gyel, amelyeket ´ atad a kih´ıv´ onak, R 4. a kih´ıv´ ob← − {0, 1} v´ alaszt´ as alapj´ an az Encpk (·) algoritmussal megR hat´ arozza az mb titkos´ıtott értékét: c∗ ← − Encpk (mb ), amelyet ´ atad az ∗ A t´ amad´ onak; nevezz¨ uk ezt a c titkos´ıtott értéket kih´ıv´ o rejtjelezett sz¨ ovegnek (challenge ciphertext), 5. az A t´ amad´ o tetsz˝ oleges sz´ am´ u titkos´ıt´ ast végez a pk nyilv´ anos kulcs ismeretében, ahol a titkos´ıt´ ast a kih´ıv´ o Encpk (·) algoritmus´ aval végzi, 6. az A t´ amad´ o meghat´ aroz egy ˆb ∈ {0, 1} kimeneti értéket. 4.9. defin´ıció. A P KE aszimmetrikus titkos´ıt´ asi rendszerben a A t´ amad´ o ˆb] − 1 |, ahol el˝ onye a k¨ ovetkez˝ oképpen adhat´ o meg: Advcpa (k) = | Pr[b = P KE,A 2 a b és ˆb értékeket a 4.1. k´ısérletben hat´ aroztuk meg. A választott ny´ılt sz¨ oveg alap´ u t´ amadással szembeni CPA-biztonságot a következ˝o értelmezés adja: 4.10. defin´ıció. A P KE aszimmetrikus titkos´ıt´ asi rendszer CPA-biztons´ ag´ u, ha b´ armely A, probabilisztikus, polinomi´ alis idej˝ u t´ amad´ o esetében létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy Advcpa P KE,A (k) ≤ f (k).

4.4.2. Választott rejtjelezett szöveg alap´ u támadás Egy sokkal er˝osebb biztons´ agértelmezés a választott rejtjelezett szöveg alap´ u támadással szembeni biztons´ agot értelmezi, amely során a támadó tetsz˝oleges szám´ u rejtjelezést és visszafejtést is el tud végezni egy rejtjelez˝o, illetve visszafejt˝ o or´ akulum seg´ıtségével ([21], [11]). A támadás adapt´ıv formája azt jelenti, hogy a t´ amad´ onak arra is lehet˝osége van, hogy a kiválasztásra ker¨ ul˝ o ny´ılt sz¨ ovegeket, illetve rejtjelezett szövegeket az alapján határozza meg, hogy mi volt a korábbi rejtjelezés, illetve visszafejtés eredménye.

48

A v´ alasztott rejtjelezett sz¨ oveg alap´ u támadással szembeni biztonságértelmezéséhez, a megfelel˝ o k´ısérlet, a következ˝o lépéssorozatból fog állni, ahol a k´ısérlet az A t´ amad´ o és környezete, a kih´ıvó között játszódik le. 4.2. k´ısérlet. 1. A kih´ıv´ o a Gen kulcsgener´ al´ o algoritmussal meghat´ arozza a (pk, sk) kulcsp´ art, majd a pk nyilv´ anos kulcsot ´ atadja az A t´ amad´ onak, 2. az A t´ amad´ o tetsz˝ oleges sz´ am´ u titkos´ıt´ ast, illetve visszafejtést végez a kih´ıv´ o Encpk (·) titkos´ıt´ o és Decsk (·) visszafejt˝ o algoritmus´ aval, 3. az A t´ amad´ o, két azonos hossz´ us´ ag´ u u ¨zenetet hat´ aroz meg, jel¨ olj¨ uk ezeket m0 , m1 -gyel, amelyeket ´ atad a kih´ıv´ onak, R 4. a kih´ıv´ ob← − {0, 1} v´ alaszt´ as alapj´ an az Encpk (·) titkos´ıt´ o algoritmus∗ R sal meghat´ arozza az mb titkos´ıtott értékét: c ← − Encpk (mb ), amelyet ´ atad az A t´ amad´ onak; nevezz¨ uk ezt a c∗ titkos´ıtott értéket kih´ıv´ o rejtjelezett sz¨ ovegnek (challenge ciphertext), 5. az A t´ amad´ o tetsz˝ oleges sz´ am´ u titkos´ıt´ ast, illetve visszafejtést végez a kih´ıv´ o Encpk (·) titkos´ıt´ o és Decsk (·) visszafejt˝ o algoritmus´ aval, k¨ ul¨ onb¨ oz˝ o c bemenetekre, azzal a megk¨ otéssel, hogy c 6= c∗ , 6. az A t´ amad´ o meghat´ aroz egy ˆb ∈ {0, 1} kimeneti értéket. 4.11. defin´ıci´ o. A P KE aszimmetrikus titkos´ıt´ asi rendszerben az A t´ amad´ o ˆb] − 1 |, ahol el˝ onye a k¨ ovetkez˝ oképpen adhat´ o meg: Advcca (k) = | Pr[b = P KE,A 2 a b és ˆb értékeket a 4.2. k´ısérletben hat´ aroztuk meg. A választott rejtjelezett sz¨ oveg alap´ u támadással szembeni CCAbiztonságot a k¨ ovetkez˝ o értelmezés adja: 4.12. defin´ıci´ o. A P KE aszimmetrikus titkos´ıt´ asi rendszer CCA-biztons´ ag´ u, ha b´ armely A, probabilisztikus, polinomi´ alis idej˝ u t´ amad´ o esetében létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy Advcca P KE,A (k) ≤ f (k). A fenti két biztons´ agértelmezés alapján a következ˝o következtetéseket vonhatjuk le [32]: 49

• Azok az aszimmetrikus titkos´ıt´ o rendszerek amelyeknél a titkos´ıtó Encpk (·) algoritmus determinisztikus nem biztos´ıtják se a CPAbiztonságot, se a CCA-biztons´ agot, • nem lehet olyan aszimmetrikus titkos´ıtó rendszert szerkeszteni, amely tökéletes biztons´ ag´ u.

4.5. Hibrid rendszerek A bizalmas inform´ aci´ ocsere megval´ os´ıt´ asa érdekében, a gyakorlatban gyakran alkalmaznak hibrid rendszereket. Ez els˝osorban azt jelenti, hogy a tulajdonképpeni inform´ aci´ o titkos´ıt´ as´ ahoz szimmetrikus titkos´ıtási technikát, a titkos´ıt´ ashoz sz¨ ukséges kulcs, a titkos´ıtó kulcs cseréjéhez, pedig aszimmetrikus titkos´ıt´ asi technik´ at haszn´ alnak. Ennek sz¨ ukségessége azért fontos, mert nagy adathalmaz titkos´ıt´ as´ ahoz nem vehet˝ok igénybe a nagy szám´ıtási kapacit´ ast igényl˝ o aszimmetrikus titkos´ıtó rendszerek, viszont a szimmetrikus titkos´ıt´ asi technik´ ak nem biztos´ıtják hatékonyan a kulcscserét. Az aszimmetrikus titkos´ıt´ o rendszerek megoldják a szimmetrikus titkos´ıtó rendszerek problém´ aj´ at: lehet˝ oséget adnak hogy két, egymással, egy nyilvános csatorn´ an kereszt¨ ul kommunik´ aló egység kicserélje a titkos´ıtáshoz sz¨ ukséges titkos´ıt´ o kulcsot u ´gy, hogy az ne ker¨ ulhessen illetéktelen egység birtokába. Titkos´ıtási rendszerek esetében fontos k¨ ulönbséget tenni a következ˝o két eset között: • megengedett a titkos´ıt´ ashoz gener´ alt kulcs többszöri felhasználása, • nem megengedett a titkos´ıt´ ashoz generált kulcs többszöri felhasználása, azaz minden egyes titkos´ıtáshoz más és más kulcsot kell generálni. A fenti két eset m´ as biztons´ agi kritériumokat határoz a szimmetrikus, illetve az aszimmetrikus titkos´ıt´ o rendszerek esetében, éppen ezért fontosnak tartjuk a k¨ ovetkez˝ oket megjegyezni [36]:

50

4.1. megjegyzés. Egy determinisztikus, szimmetrikus titkos´ıt´ o rendszer nem tudja biztos´ıtani a passz´ıv t´ amad´ oval szembeni biztons´ agot, ha megengedett a kulcs t¨ obbsz¨ ori felhaszn´ al´ asa. 4.2. megjegyzés. Egy szimmetrikus titkos´ıt´ o rendszer, amely biztons´ agos egy passz´ıv t´ amad´ oval szemben, elvesz´ıti passz´ıv t´ amad´ oval szembeni biztons´ ag´ at, ha megengedj¨ uk a kulcs t¨ obbsz¨ ori felhaszn´ al´ as´ at. 4.3. megjegyzés. Egy szimmetrikus titkos´ıt´ o rendszer, amely CPAbiztons´ ag´ u meg˝ orzi CPA-biztons´ ag´ at, ha megengedj¨ uk a kulcs t¨ obbsz¨ ori felhaszn´ al´ as´ at. 4.4. megjegyzés. Egy aszimmetrikus titkos´ıt´ o rendszer, ha biztons´ agos egy passz´ıv t´ amad´ oval szemben, akkor CPA-biztons´ ag´ u is lesz, mivel a t´ amad´ onak mindig lehet˝ osége van tetsz˝ oleges sz´ am´ u titkos´ıt´ ast végezni, hiszen a titkos´ıt´ o kulcs, azaz a nyilv´ anos kulcs publikus. Ez természetesen nem ´ıgy van a szimmetrikus titkos´ıt´ o rendszerek esetében. 4.5. megjegyzés. Egy aszimmetrikus titkos´ıt´ o rendszer, amely CPAbiztons´ ag´ u meg˝ orzi CPA-biztons´ ag´ at, ha megengedj¨ uk a nyilv´ anos kulcsok t¨ obbsz¨ ori felhaszn´ al´ as´ at. 4.6. megjegyzés. Egy determinisztikus, aszimmetrikus titkos´ıt´ o rendszer nem lehet CPA-biztons´ ag´ u. 4.13. defin´ıci´ o. Azokat a rendszereket, ahol minden egyes titkos´ıt´ ashoz m´ as kulcsot gener´ alnak egyszeri titkos´ıt´ o (one-time encryption) rendszereknek h´ıvj´ ak. Ugyanez alkalmazhat´ o a M ac-kódokra is, azaz: 4.14. defin´ıci´ o. Azokat a M ac-k´ odokat, ahol minden M ac-érték el˝ o´ all´ıt´ as´ ahoz m´ as kulcsot gener´ alnak egyszeri M ac-k´ odoknak (one-time message authentication code) h´ıvj´ ak. Hibrid rendszerek, prec´ız matematikai defin´ıcióját, és CCA-biztonság´ u hibrid rendszerek szerkesztési m´ odját, többek között Cramer és Shoup is megadt´ ak [21]. Az ´ altaluk ismertetett eljárás aszimmetrikus titkos´ıtási technik´ aval biztos´ıtja, a kommunikálni k´ıvánó felek között, egy 51

véletlenszer˝ uen gener´ alt érték, a titkos´ıt´ o kulcs megosztását amely kulcs felhasználásával, szimmetrikus titkos´ıt´ ast alkalmazva, megoldható két egység között a bizalmas inform´ aci´ ocsere. Cikk¨ ukben bevezették a kulcsbeágyazási mechanizmus (key encapsulation mechanism) fogalmát, amely a titkos´ıtó kulcs generálás´ at és megoszt´ as´ at biztos´ıtja. Bebizony´ıtott´ ak, hogy egy CCA-biztonság´ u aszimmetrikus titkos´ıtási rendszert kombin´ alva egy CCA-biztons´ ag´ u egyszeri szimmetrikus titkos´ıtási rendszerrel CCA-biztons´ ag´ u hibrid rendszert eredményez. CCA-biztons´ ag´ u szimmetrikus rendszerek szerkesztésénél sz¨ ukség van egyszeri szimmetrikus titkos´ıt´ o rendszerekre, illetve egyszeri M ac-kódokra. CCA-biztons´ ag´ u aszimmetrikus rendszerek szerkesztésénél sz¨ ukség van egyirány´ u csap´ oajt´ o f¨ uggvényekre és hash f¨ uggvényekre. Jelen értekezésben, ahogyan az u ´jabb szakirodalom is teszi, a hibrid rendszereken bel¨ ul az aszimmetrikus titkos´ıtás illetve visszafejtés megnevezések helyett a kulcsbe´ agyaz´ asi algoritmus (key encapsulation algorithm), illetve kulcskibont´ asi algoritmus (key decapsulation algorithm) neveket fogjuk használni. Ezek után form´ alisan is megadhat´ o egy hibrid titkos´ıtó rendszer matematikai modellje: 4.15. defin´ıció. Jel¨ olje HKE azt a hibrid titkos´ıt´ asi rendszert, amely h´ arom algoritmussal értelmezhet˝ o, a ((P K, SK), M, C) felett, ahol • Gen, a probabilisztikus kulcsgener´ al´ o algoritmus, amely polinomi´ alis R k id˝ oben, az 1 bemeneten meghat´ arozza (pk, sk) kulcsp´ art: (pk, sk) ← − Gen(1k ), ahol pk ∈ P K a nyilv´ anos kulcs és sk ∈ SK a titkos kulcs és k ∈ Z≥0 a rendszer biztons´ agi paramétere, • Az EncHKE (pk, m) titkos´ıt´ o a k¨ ovetkez˝ o két algoritmusb´ ol ´ all: – az EncKEM egy CCA-biztons´ ag´ u kulcsbe´ agyaz´ asi algoritmus, amely polinomi´ alis id˝ oben, probabilisztikusan, a pk bemeneten el˝ o´ all´ıt egy értéket, a titkos´ıt´ o kulcsot és annak egy titkos´ıtott értékét: (key, cipher) ← EncKEM (pk), – az EncSKE egy CCA-biztons´ ag´ u egyszeri szimmetrikus titkos´ıt´ asi rendszer, amely a key és m bemenetre meghat´ arozza az m titkos´ıtott értékét: c ← EncSKE (key, m). 52

– Az EncHKE (pk, m) algoritmus kimenete: (c, cipher). • A DecHKE (sk, c, cipher) visszafejt˝ o algoritmus a k¨ ovetkez˝ oket végzi: – ha a (c, cipher) nem egy helyes titkos´ıtott érték, akkor az algoritmus REJECT, elutas´ıt´ o kimeneti értékkel le´ all, – ellenkez˝ o esetben megh´ıvja a DecKEM , determinisztikus, kulcskibont´ asi algoritmust: ∗ ha a DecKEM REJECT, elutas´ıt´ o kimeneti értékkel le´ all, akkor a visszafejt˝ o DecHKE algoritmus is le´ all REJECT, elutas´ıt´ o kimeneti értékkel, ∗ ellenkez˝ o esetben az sk, cipher bemenetre meghat´ arozza a key értékét: key ← DecKEM (sk, cipher), – megh´ıvja a determinisztikus, egyszeri szimmetrikus titkos´ıt´ o algoritmust, amely a key, c bemenetre meghat´ arozza az m értékét: m ← DecSKE (key, c), – DecHKE (sk, c, cipher) algoritmus kimenete: m. A rendszer helyessége érdekében megkövetelj¨ uk, hogy mind a kulcsbeágyazási mechanizmus, mind a szimmetrikus titkos´ıtó rendszer helyes legyen. A szimmetrikus titkos´ıt´ o rendszer helyességét az 2.9. defin´ıciónál adtuk meg, a kulcsbe´ agyaz´ asi mechanizmus helyessége, pedig az aszimmetrikus titkos´ıt´ ok matematikai modelljénél le´ırt helyesség alapján adható meg. Egy kulcsbe´ agyaz´ asi mechanizmus esetében, tehát a rendszer helyességét a k¨ ovetkez˝ o k¨ ovetelmények ´ırják le: • a (pk, sk) ∈ P K × SK kulcspár nem megfelel˝o, ha bármely R (key, cipher) ← − EncKEM (pk) esetében fennáll: DecKEM (sk, cipher) 6= key • annak a val´ osz´ın˝ usége, hogy a Gen kulcsgeneráló algoritmus nem megfelel˝ o (pk, sk) kulcsp´ art generál, a k bemenet f¨ uggvényében, elhanyagolhat´ oan n˝ o. Ezek ut´ an megadhat´ o a hibrid rendszerek formális CCA-biztonság értelmezése [21]: 53

4.1. tétel. A 4.11. defin´ıci´ oval megadott HKE hibrid rendszer CCA-biztons´ ag´ u, ha az EncSKE , DecSKE algoritmusok ´ altal defini´ alhat´ o szimmetrikus titkos´ıt´ asi rendszer CCA-biztons´ ag´ u, és ha a Gen, EncKEM , DecKEM algoritmusok ´ altal defini´ alhat´ o kulcsbe´ agyaz´ asi mechanizmus, azaz aszimmetrikus titkos´ıt´ asi rendszer is CCA-biztons´ ag´ u. 4.7. megjegyzés. Egy CCA-biztons´ ag´ u szimmetrikus titkos´ıt´ asi rendszer u ´gy szerkeszthet˝ o, ha egy passz´ıv t´ amad´ oval szemben biztons´ agos szimmetrikus titkos´ıt´ o rendszerhez hozz´ acsatolunk egy egyszeri u ¨zenethiteles´ıt˝ o k´ odot. Fontos megjegyezni, azt is hogy a szimmetrikus titkos´ıt´ ashoz haszn´ alt kulcs és az u ¨zenethiteles´ıt˝ o k´ od létrehoz´ as´ ahoz sz¨ ukséges kulcs k¨ ul¨ onb¨ oz˝ o kell, hogy legyen. A CCA-biztons´ ag´ u kulcsbe´ agyaz´ asi mechanizmusok szerkesztéséhez hash f¨ uggvényeket alkalmaznak. Aszerint, hogy az alkalmazásra ker¨ ul˝o hash f¨ uggvény viselkedése milyen feltételezések seg´ıtségével van definiálva megk¨ ulönböztetj¨ uk a véletlen or´ akulum modellt és a standard modellt. A véletlen or´ akulum (random oracle) modellben olyan hash f¨ uggvény alkalmazásával bizony´ıthat´ o a CCA-biztonság, amelyr˝ol feltételezik, hogy teljesen véletlenszer˝ uen viselkedik. Ebben a modellben nem követelik meg a hash f¨ uggvényt˝ ol, hogy a 3.1. alfejezetben ismertetett tulajdonságoknak ´ eleget tegyen. Eppen ezért a véletlen orákulum modellben bizony´ıtott CCA-biztonság´ u titkos´ıt´ o rendszerek heurisztikus bizony´ıtások, és sokszor nem bizonyulnak biztons´ agosnak. Hatékonyság szempontjából viszont nagyon el˝onyös az alkalmaz´ asuk. A standard modellben bebizony´ıtott CCA-biztonság esetén a hash f¨ uggvényt˝ol azt kell elv´ arni, hogy a f¨ uggvény a 3.1. alfejezetben ismertetett tulajdons´ agoknak tegyen eleget. Ezek a bizony´ıtások megb´ızható biztonságot garant´ alnak csup´ an a standard feltételezéseket, mint pl. u ¨tközésmentesség, faktoriz´ aci´ os feltételezés, diszkrét logaritmus feltételezés ´ stb. elfogadva. Eppen ezért a standard modellben elért CCA-biztonság´ u rendszerek sokkal er˝ osebb biztons´ agot garantálnak, mint a véletlen orákulum modellben bizony´ıtott CCA-biztonság´ u rendszerek. Hatékonyság szempontjából viszont kevésbé el˝ ony¨ os az alkalmazásuk.

54

5. fejezet

CCA-biztonság´ u kulcsbeágyazási mechanizmusok Ebben a fejezetben azokat az aszimmetrikus titkos´ıtó rendszereket ismertetj¨ uk, amelyek alapul szolg´ altak több, napjainkban használatos CCAbiztonság´ u kulcsbe´ agyaz´ asi mechanizmusnak. Fontosnak tartjuk megjegyezni, hogy az értekezés 7. fejezetében ezen rendszerek mindegyikének megvizsg´ altuk implement´ aci´ os lehet˝oségét, összevetve ˝oket hatékonyság szempontj´ ab´ ol a 6. fejezetben bemutatásra ker¨ ul˝o u ´j kulcsbeágyazási mechanizmus hatékonys´ ag´ aval. Mindegyik rendszernél bemutatjuk a sz¨ ukséges algoritmusokat, és azt a sikeres támadási lépéssorozatot, amely alapján kijelenthet˝ o, hogy a rendszer nem CCA-biztonság´ u. Ezeket követ˝oen, pedig megadunk egy-egy, az u ´jabb szakirodalom által számon tartott, CCA-biztons´ ag´ u kulcsbe´ agyazási verziót ([6], [14], [35], [20]).

5.1. Az RSA-rendszer Az RSA titkos´ıt´ o rendszert 1978-ban publikálták [55], a rendszer eredeti formájában nem ´ all ellen se a CPA-támadásnak, se a CCA-támadásnak. Szám´ıtástechnikai biztons´ aga az RSA-feltételezésen alapszik, ahol az ehhez kapcsol´ od´ o értelmezést a 4.3.2. szakaszban adtuk meg. Megjelenése

55

o´ta számos kitétel létezik a kulcsgener´ al´ o, a titkos´ıtó, illetve visszafejt˝o algoritmusok biztons´ agos haszn´ alat´ ara vonatkozóan. Klasszikusan szám´ıtó kitételek, amelyek részletes t´ argyal´ asa megtalálható a ([13], [34], [65]) cikkekben, a következ˝ ok: • • • • •

a kis n modulus problematika, a kis e exponens problematika, közeli pr´ımek haszn´ alata, kis d exponens haszn´ alata, az n modulus t¨ obbsz¨ ori alkalmaz´ asa, stb.

A rendszer [55]-ben publik´ alt verzi´ oja alapján és a 4.1. értelmezés szerint a következ˝ o algoritmusok adhat´ ok meg: R

• Gen, a kulcsgener´ al´ o algoritmus meghatározza az (e, n, d) ← − Gen(1k ) értékeket, ahol – n = p · q, és p, q k-bites pr´ımsz´ amok, R ∗ arozzuk d-t u ´gy hogy: e · d = 1 – legyen e ← − Zn , és meghat´ (mod (p − 1) · (q − 1)), – pk = (e, n), sk = d. • az Enc(e,n) rejtjelez˝ o algoritmus polinomiális id˝oben, végzi a rejtjelezést, az m ∈ M bemenetre elvégez egy moduláris hatványozást: c ← me (mod n), • a Decd visszafejt˝ o algoritmus, polinomiális id˝oben végzi a visszafejtést a c ∈ C rejtjelezett sz¨ ovegen elvégez egy moduláris hatványozást: m ← cd (mod n). Az RSA biztons´ agos és hatékony implementációjának érdekében sz¨ ukséges megjegyezn¨ unk a k¨ ovetkez˝ oket ([30], [44]): • az RSA kulcsgener´ al´ o algoritmus nagy pr´ımek generálását ´ırja el˝o, amit a probabilisztikus Miler-Rabin vagy Solovay-Strassen algoritmusok implement´ al´ as´ aval lehet megoldani, • a d titkos kulcs meghat´ aroz´ as´ ahoz a kiterjesztett euklideszi algoritmust lehet alkalmazni, 56

• a visszafejtés id˝ oigényének gyors´ıtása a k´ınai maradéktétel alkalmaz´ as´ aval oldhat´ o meg, • a modul´ aris hatv´ anyoz´ as algoritmusának bonyolultsága, ismételt négyzetre emelések és szorz´ asok alkalmazásával: O((log n)3 ). A sikeres CCA-t´ amad´ as lépéssorozata a következ˝o lesz, amely egy polinomiális idej˝ u, probabilisztikus A t´ amadó algoritmus és környezete, a kih´ıvó között játsz´ odik le: 5.1. k´ısérlet. 1. A kih´ıv´ o futtatja a Gen kulcsgener´ al´ o algoritmust meghat´ arozza az e, n, d értékeket, majd a ´tadja az (e, n) nyilv´ anos kulcsot az A t´ amad´ onak, 2. az A t´ amad´ o, két azonos hossz´ us´ ag´ u u ¨zenetet hat´ aroz meg, jel¨ olj¨ uk ezeket m0 , m1 -gyel, amelyeket ´ atad a kih´ıv´ onak, R 3. a kih´ıv´ o a b← − {0, 1} v´ alaszt´ as alapj´ an az Enc(e,n) titkos´ıt´ o algorit∗ R mussal meghat´ arozza az mb titkos´ıtott értékét: c ← − Enc(e,n) (mb ), amelyet ´ atad az A t´ amad´ onak; 4. az A t´ amad´ o elvégzi a k¨ ovetkez˝ oket: R

• gener´ al egy m értéket: m ← − Z∗n , • kisz´ am´ıtja a c = c∗ · me értéket, • futtatja a c 6= c∗ bemenetre, a kih´ıv´ o Decd visszafejt˝ o algoritmus´ at, meghat´ arozva ezzel az m ˆ értéket, • ha m ˆ · m−1 = m0 , akkor ˆb = 0, m´ asképp ˆb = 1 lesz az A t´ amad´ o v´ alaszt´ asa. Az A t´ amad´ o, 4.11. értelmezés szerinti el˝onye 12 , mert fennáll: m ˆ = (c∗ · me )d = (c∗ )d · me·d = (c∗ )d · m = mb · m. 1 1 1 ˆ es ˆb Form´ alisan Advcca RSA,A (k) = | Pr[b = b] − 2 | = |1 − 2 | = 2 , ahol a b ´ értékeket az 5.1. k´ısérletben hat´ aroztuk meg. Azok a titkos´ıt´ o rendszerek, ahol a titkos´ıtó algoritmus determinisztikus, nem rendelkezhetnek a CPA, illetve a CCA-biztonság egyikével sem.

57

Ezért sz¨ ukséges, hogy a titkos´ıt´ o algoritmust átalak´ıtsuk. Ez a folyamat sz¨ ukségszer˝ uen a rejtjelezett sz¨ oveg adat expanziójával fog járni. Több ilyen biztonságtulajdons´ aggal rendelkez˝ o RSA verzió létezik, de ezek köz¨ ul az egyik legjelent˝ osebb és leghatékonyabb az RSA–OAEP (RSA-Optimal Asymmetric Encryption Padding). Az RSA–OAEP verziót Bellare és Rogaway dolgozták ki [6], és megadt´ ak a véletlen orákulum modellben a CCA-biztonság bizony´ıt´ as´ at. Az RSA–OAEP-titkos´ıt´ o rendszerben alkalmazásra ker¨ ul két, egymástól f¨ uggetlen véletlen or´ akulum, a G és H f¨ uggvény, ahol • G : {0, 1}lH → {0, 1}lG , egy hash f¨ uggvényen alapuló ál-véletlenszám generátor, • H : {0, 1}lG → {0, 1}lH , egy probabilisztikus hash f¨ uggvény. A rendszer h´ arom algoritmusa a (P, C, K) halmazhármas felett van értelmezve, ahol P = {0, 1}lP , C = {0, 1}lH +lG , K = {0, 1}lH +lG , és lG , lH pozit´ıv egész sz´ amok, ahol lP < lG , lG < k, lH < k és k = lH + lG . • A Gen(1k ) kulcsgener´ al´ o algoritmus, a már le´ırt módon meghatározza R az e, n, d értékeket: (e, n, d) ← − Gen(1k ), ahol pk = (e, n) és sk = d. • Az EN C(e,n) (m) titkos´ıt´ o algoritmus probabilisztikusan, polinomiális id˝oben meghat´ arozza a c rejtjelezett értéket, ahol – – – – –

x = m||0lG −lP , R r← − {0, 1}lH , y1 = x ⊕ G(r), y2 = r ⊕ H(x ⊕ G(r)), c = (y1 ||y2 )e (mod n),

• DECsk (c) visszafejt˝ o algoritmus – determinisztikusan, polinomi´ alis id˝oben meghatározza az y = cd (mod n) értéket, majd felosztja y-t yˆ1 ||yˆ2 -re u ´gy, hogy |yˆ1 | = lG és |yˆ2 | = lH , – meghat´ arozza r = H(yˆ1 ) ⊕ yˆ2 , – meghat´ arozza yˆ = yˆ1 ⊕ G(r), – ellen˝ orzi, hogy yˆ utols´ o lG − lP bitje nulla-e: 58

∗ ha nem, akkor REJECT kimeneti értékkel leáll, ∗ ellenkez˝ o esetben visszatér´ıti az els˝o lP bitjét yˆ-nak. A rendszer helyessége elemi sz´ am´ıtások során ellen˝orizhet˝o, figyelembe véve, az ⊕ oper´ ator idempotens tulajdonságát. A rendszer CCA-biztons´ ag´ anak bizony´ıtása a következ˝oképpen vázolható fel, részletes bizony´ıt´ as´ ara, amely megtalálható [6]-ben, jelen értekezés keretén bel¨ ul nem tér¨ unk ki. Ahhoz, hogy az esetleges t´ amadó az m ny´ılt szöveg bármilyen bitjére vonatkoz´ oan inform´ aci´ ot szerezhessen sz¨ ukséges a G(r) teljes bitszekvenciájának a meghat´ aroz´ asa. Ez ut´ obbi, csak két esetben lehetséges: • ha siker¨ ul az r = H(yˆ1 ) ⊕ yˆ2 meghatározása, azaz ha siker¨ ul invertálni az RSA egyir´ any´ u f¨ uggvényt vagy ha siker¨ ul u ¨tközést találni a H hash f¨ uggvény esetében, • ha siker¨ ul u ¨tk¨ ozést tal´ alni a G f¨ uggvény esetében.

5.2. A Rabin-rendszer A Rabin titkos´ıt´ o rendszert 1979-ban publikálták [54], a rendszer eredeti formáj´ aban nem ´ all ellen a CCA-támadásnak, ahol a támadás során nem a ny´ılt sz¨ oveget, hanem a titkos kulcsot határozza meg az A támadó. Szám´ıtástechnikai biztons´ aga a faktorizációs feltételezésen alapszik, ahol az ehhez kapcsol´ od´ o értelmezést a 4.3.1. szakaszban adtuk meg. A rendszer [54]-ben publik´ alt verzi´ oja a k¨ ovetkez˝o: R

• Gen, a kulcsgener´ al´ o algoritmus meghatározza: (n, p, q) ← − Gen(1k ) értékeket, ahol – legyenek p, q k-bites pr´ımszámok u ´gy, hogy p ≡ q ≡ 3 (mod 4), – n = p · q, – pk = n, sk = (p, q). • az Encn rejtjelez˝ o algoritmus polinomiális id˝oben, végzi a rejtjelezést, az m ∈ M bemenetre: c ← m2 (mod n), • a Dec(p,q) visszafejt˝ o algoritmus, polinomiá√lis id˝oben végzi a visszafejtést a c ∈ C rejtjelezett sz¨ ovegen: m ← c (mod n). 59

√ 5.1. megjegyzés. A visszafejtés, azaz c meghat´ aroz´ asa nem egyértelm˝ u: 4 lehetséges visszafejtett sz¨ oveg k¨ oz¨ ul kell kiv´ alasztani a megfelel˝ ot. Ennek érdekében alkalmazzuk a k´ınai maradéktételt, ahol a 4 lehetséges visszafejtett sz¨ oveg a k¨ ovetkez˝ o: m1 , −m1 , m2 , −m2 és ahol: • m1 = (p−1 · p · mq + q −1 · q · mp ) (mod n), • m2 = (p−1 · p · mq − q −1 · q · mp ) (mod n), ahol fenn´ all: mp = c(p+1)/4 (mod p), mq = c(q+1)/4 (mod q) és p · p−1 = 1 (mod q), q · q −1 = 1 (mod p). A Rabin-titkos´ıt´ o CCA-biztons´ ag´ u verzióját, a véletlen orákulum modellben Boneh dolgozta ki [14], ahol biztonságát a faktorizációs feltételezés alapján bizony´ıtotta. A rendszer SAEP (Simplified Asymmetric Encryption Padding) néven ismert. A rendszer az RSA–OAEP-titkos´ıtóhoz képest jóval egyszer˝ ubb, egyetlen hash f¨ uggvényt alkalmaz: H : {0, 1}lr → {0, 1}lH . A rendszer h´ arom algoritmusa a (P, C, K) halmaz hármas felett van értelmezve, ahol P = {0, 1}lP , C = {0, 1}lH +lr , K = {0, 1}lH +lr , és lH , lr pozit´ıv egész sz´ amok, lP < lH , és k = lH + lr . • A Gen(1k ) kulcsgener´ al´ o algoritmus, meghatároz egy (k + 2) bites n = p · q sz´ amot, ahol – az n legfels˝ obb helyérték˝ u két bitje 1 és 0, – p, q pedig két k/2 + 1 bites pr´ımszám u ´gy, hogy: p ≡ q ≡ 3 (mod 4), – pk = n és sk = (p, q). • Az EN Cpk (m) titkos´ıt´ o algoritmus probabilisztikusan, polinomiális id˝oben meghat´ arozza a c rejtjelezett értéket, ahol – – – –

x = m||0lH −lP , ahol az || oper´ ator összef˝ uzést jelent, R lr r← − {0, 1} , y = (x ⊕ H(r))||r, c = y 2 (mod n),

• DECsk (c) visszafejt˝ o algoritmus a következ˝oket végzi: 60

– meghat´ arozza yp = c(p+1)/4 (mod p), yq = c(q+1)/4 (mod q) értékeket, majd alkalmazza a k´ınai maradéktételt, y1 , −y1 , y2 , −y2 lesz a 4 megoldás: ∗ y1 = (p−1 · p · yq + q −1 · q · yp ) (mod n), ∗ y2 = (p−1 · p · yq − q −1 · q · yp ) (mod n). – megvizsg´ alja, melyik igaz: yp2 = c (mod p), yq2 = c (mod q), – ha egyik sem teljes¨ ul, akkor REJECT kimeneti értékkel leáll, – ezut´ an feltételezhet˝ o, hogy a 4 lehetséges négyzetgyök köz¨ ul kett˝ o biztosan nagyobb mint n/2, marad 2 lehetséges megoldás, legyenek ezek y1 , y2 , – ellen˝ orzi, hogy, ha y1 és y2 is nagyobb mint 2k , akkor REJECT kimeneti értékkel le´ all, – ellen˝ orzi, hogy ha csak az egyik kisebb mint 2k , akkor legyen ez y1 , majd a k¨ ovetkez˝ o pontnál megadott szám´ıtássorozatot kell k¨ ovetni, de az y2 értékkel nem kell számolni, – ezut´ an feltételezhet˝ o, hogy y1 is és y2 is kisebb mint 2k : ∗ fel´ırjuk y1 = v1 ||r1 y2 = v2 ||r2 u ´gy, hogy r1 , r2 ∈ {0, 1}lr ∗ meghat´ arozzuk x1 = v1 ⊕ H(r1 ) x2 = v2 ⊕ H(r2 ), ∗ fel´ırjuk x1 = m1 ||t1 és x2 = m2 ||t2 u ´gy, hogy m1 , m2 ∈ {0, 1}lP ∗ ha t1 = 0lH −lP és t2 = 0lH −lP , akkor REJECT kimeneti értékkel le´ all, ∗ ha t1 6= 0lH −lP és t2 6= 0lH −lP , akkor REJECT kimeneti értékkel le´ all, ∗ ha t1 = 0lH −lP , akkor visszatér´ıti m1 -et, mint visszafejtett értéket, ∗ ha t2 = 0lH −lP , akkor visszatér´ıti m2 -et, mint visszafejtett értéket. A rendszer CCA-biztons´ ag´ anak bizony´ıtása a következ˝oképpen vázolható fel, részletes bizony´ıt´ asra jelen értekezés keretén bel¨ ul nem tér¨ unk ki [14]. Ha siker¨ ul egy olyan A t´ amadó algoritmust szerkeszteni, amely az R n, lP , lH − lP , lr , c = y 2 (mod n) bemeneti értékekre, ahol y ← − {0, . . . , 2k − 1}, meghat´ arozza c egy y ∗ 6= y négyzetgyökét, akkor lehetséges az n 61

faktorizálása az n és y − y ∗ értékek legnagyobb közös osztójának a meghatározásával. Coppersmith egy cikke alapj´ an [19] Boneh-nek siker¨ ult, azt bebizony´ıtani, hogy elégséges egy olyan A támadó algoritmust szerkeszteR ni, amely ha 1/3-n´ al nagyobb val´ osz´ın˝ uséggel megmondja, hogy a c ← − {0, . . . n − 1} sz´ amnak két k¨ ul¨ onb¨ oz˝ o négyzetgyöke van az {0, . . . 2k − 1} halmazon (mod n) szerint, akkor 1/6-n´ al nagyobb a valósz´ın˝ usége annak, hogy az A támad´ o algoritmus ´ altal meghatározott y, y ∗ -ra fennálljon, hogy: y 6= y ∗ , ami alapj´ an lehetséges az n faktorizálása.

5.3. A Blum–Goldwasser-rendszer A Blum–Goldwasser titkos´ıt´ o rendszert, amelyre BG-titkos´ıtó néven fogunk a továbbiakban hivatkozni, 1985-ban publikálták [12]. A rendszer eredeti formájában CPA-biztons´ ag´ u, viszont nem áll ellen a választott rejtjelezett szöveg alap´ u t´ amad´ asnak. A BG-titkos´ıtó egy álvéletlen bitsorozat generátoron alapszik, a Blum-Blum-Shub generátoron, amelyre BBS-generátor néven fogunk a tov´ abbiakban hivatkozni. A BBS generátort 1982-ben publik´ alt´ ak [10] és bebizony´ıtott´ ak róla, hogy kriptográfiailag biztonságos. Biztons´ ag´ at a kvadratikus maradék feltételezés (lásd a 4.3.3. szakaszban), alapj´ an bizony´ıtott´ ak. A 2.9. form´ alis értelmezés egy alternat´ıv megközel´ıtése a következ˝o [61]: egy álvéletlen bitsorozat gener´ atorról, akkor mondjuk, hogy kriptográfiailag biztons´ agos, ha az els˝ o l ´ alvéletlen bit meghatározása után, a kezdeti seed (kezd˝ oérték) ismeretének hiányában, nem lehet 1/2 + ε-nál nagyobb valósz´ın˝ uséggel megmondani, hogy mi lesz az (l + 1)-ig bit, ahol ε nem elhanyagolhat´ o érték. A BG-titkos´ıt´ o a BBS ´ altal gener´ alt byte-okat összeadja a ny´ılt szöveg byte-jaival, bitenkénti (mod 2) szerinti o¨sszeadást végezve. A továbbiakban el˝ obb a BBS-gener´ atort mutatjuk be. Legyen n = p · q, ahol p, q tetsz˝ oleges k-bites pr´ımszámok, azzal a tulajdonsággal, hogy p ≡ q ≡ 3 (mod 4). Jelölj¨ uk QRn -el a kvadratikus maradékok halmaz´ at (mod n) szerint, amelyet formálisan a 4.3.3. fejezetnél adtunk meg. 62

R

Legyen r ← − Z∗n , és legyen r0 = r2 (mod n), ekkor teljes¨ ulni fog, hogy r0 ∈ QRn . Az ´ alvéletlen bitsorozat generátor kiindulva a kezdeti r0 , mint seed értékb˝ ol ismételten alkalmazza a moduláris négyzetreemelés f¨ uggvényt. A véletlenszer˝ uen gener´ alt biteket: b1 , b2 , . . . , bl -el jelölve, az algoritmus a következ˝oképpen végzi ezek meghatározását: ri+1 = ri2 (mod n), minden 0 ≤ i ≤ l, és bi = ri (mod 2), minden 1 ≤ i ≤ l. Jelölj¨ uk BBS(r0 , l)-el a BBS ´ alvéletlen bitsorozat generátor által meghatározott bitsorozatot, azaz a b1 ||b2 || . . . ||bl -t, ahol r0 a kezdeti seed érték és l a gener´ alt bitsorozat hossza. Ezek ut´ an megadhat´ o a BG-titkos´ıtó, a 4.1. értelmezés szerinti három algoritmus alapj´ an: R

• A Gen, a kulcsgener´ al´ o algoritmus meghatározza az (n, p, q) ← − Gen(1k ) értékeket, ahol – legyenek p, q k-bites pr´ımszámok u ´gy, hogy p ≡ q ≡ 3 (mod 4), – n = p · q, – pk = n, sk = (p, q), • az Encn probabilisztikus, rejtjelez˝o algoritmus polinomiális id˝oben, végzi a rejtjelezést, az m = (m1 ||m2 || . . . ||ml ) ∈ Zl2 bemenetre, ahol mi , i ∈ {1, . . . l} a ny´ılt sz¨ oveg bitjei: Encn (m1 ||m2 || . . . ||ml , r0 ) = c1 ||c2 || . . . ||cl ||rl+1 , ahol – – – –

ci = (mi ⊕ bi ), 1 ≤ i ≤ l, r0 a BBS gener´ ator kezdeti értéke, b1 , b2 , . . . , bl a BBS gener´ ator által generált álvéletlen bitek, l+1 rl+1 = r02 (mod n),

• a Dec(p,q) determinisztikus, visszafejt˝o algoritmus, polinomiális id˝oben végzi a visszafejtést a c = (c1 ||c2 || . . . ||cl ||rl+1 ) ∈ Zl2 × Z∗n rejtjelezett sz¨ ovegen: 63

Dec(p,q) (c1 ||c2 || . . . ||cl ||rl+1 ) = m1 ||m2 || . . . ||ml , ahol – mi = ci ⊕ bi , 1 ≤ i ≤ l, – b1 , b2 , . . . , bl a BBS gener´ ator a´ltal generált álvéletlen bitek, – a BBS gener´ ator kezdeti r0 értéke, alkalmazva a k´ınai maradéktételt, a k¨ ovetkez˝ oképpen határozható meg: a1 r0 = rl+1 (mod p), ahol a1 = ((p + 1)/4)l+1 (mod p − 1), a2 r0 = rl+1 (mod q), ahol a2 = ((q + 1)/4)l+1 (mod q − 1).

Bebizony´ıthat´ o, hogy minden egyes moduláris négyzetre emelés esetén egyetlen bit helyett, ak´ ar log2 (log2 (n)) bit is felhasználható [62]. A Blum–Goldwasser-titkos´ıt´ o CCA-biztonság´ u verzióját, a standard modellben, mint egy hibrid rendszer kulcsbeágyazási mechanizmusa Hofheinz, Kiltz és Shoup dolgozt´ ak ki [35]. A rendszer matematikai alapj´ at a moduláris négyzetreemelés f¨ uggvény többszöri alkalmaz´ asa képezi, amelyet az algoritmus egy véletlenszer˝ uen generált értéken alkalmaz, amelyhez hozz´ a társul egy konzisztencia ellen˝orz˝o elem. A négyzetreemelés f¨ uggvény bemeneti értékét a QR+ ol veN halmazb´ szi, ahol a QR+ halmaz a kvadratikus marad´ e kok egy lesz˝ u k´ ıtett csoportj´ at N fogja jelenti, és N Blum-egész. A CCA-biztons´ ag´ u kulcsbe´ agyaz´ asi mechanizmus esetében a következ˝o Gen kulcsgener´ al´ o algoritmusra van sz¨ ukség¨ unk: 5.1. algoritmus. A Gen kulcsgener´ al´ o algoritmus az 1k bemeneten megR hat´ arozza az (N, P, Q) sz´ amh´ armast: (N, P, Q) ← − Gen(1k ) u ´gy, hogy: • N = P · Q, ahol P ≡ Q ≡ 3 (mod 4), és • P = 2 · p + 1, Q = 2 · q + 1, ahol p, q pr´ımsz´ amok, azaz P és Q biztons´ agos pr´ımek lesznek, • a p és a q bithossza k/2 − 1, • az ´ıgy gener´ alt N sz´ amot Blum-egésznek, a P, Q pr´ımeket biztons´ agos (safe) pr´ımeknek h´ıvj´ ak. A már eml´ıtett, QR+ uk´ıtett kvadratikus maradékok halmazának N lesz˝ formális értelmezéséhez felhaszn´ aljuk a 4.3.3. szakasznál értelmezett QRN halmazt, ahol N az 5.1. algoritmus ´ altal generált összetett szám: 64

5.1. defin´ıci´ o. QR+ am abszol´ ut értékét N = {|x| : x ∈ QRN }, ahol |x| az x sz´ jel¨ oli. A kulcsbe´ agyaz´ asi mechanizmus egy cél-¨ utközésmentes hash f¨ uggvényt lH is használ, amelyet a k¨ ovetkez˝ oképpen jelöl¨ unk: H : QR+ → {0, 1} . N A kulcsbe´ agyaz´ asi mechanizmus három algoritmusa, pedig a következ˝o, ahol a m˝ uveleteket QR+ egezz¨ uk: N -ben v´ • A Gen kulcsgener´ al´ o algoritmus az 1k bemeneten meghatározza az (N, P, Q, g, X, α) sz´ am¨ ot¨ ost, ahol – az (N, P, Q) értékeket az 5.1. algoritmussal határoztuk meg, l +l R R – g← − QR+ − {1, . . . , (N − 1)/4}, és X = g α·2 H L , N, α ← – az lH az alkalmazott hash f¨ uggvény kimenetének bithossza, az lL érték, pedig a BBS ´ altal generált bitek számát jelenti, – az algoritmus kimeneti értékei a pk = (N, g, X), és sk = α. • Az Encpk probabilisztikus kulcsbeágyazási algoritmus, polinomiális id˝oben meghat´ arozza (key, cipher) kimenetet, ahol: R

– r← − {1, . . . , (N − 1)/4}, l – K = g r·2 H , key = BBS(K, lL ), – cipher = (R, S), ahol l

R = g r·2 H

+lL

, h = H(R), S = (g h · X)r .

• A Decsk (cipher) determinisztikus kulcskibontási algoritmus, polinomiális id˝ oben a k¨ ovetkez˝ oket végzi: – ha nem teljes¨ ul, hogy R ∈ QR+ es S ∈ QR+ N, ´ N , akkor REJECT kimeneti értékkel le´ all az algoritmus, – ellenkez˝ o esetben meghatározza h = H(R), – ha nem teljes¨ ul az lH +lL

S2

lH +lL

= Rh+α·2

(5.1)

egyenl˝ oség, akkor az algoritmus REJECT kimeneti értékkel leáll, – ellenkez˝ o esetben meghatározza a K értéket, mint kimeneti értéket a k¨ ovetkez˝ oképpen: lH −c

K = (S a · Rb−aα )2 65

, ahol

(5.2)

az a, b, c értékeket a k¨ ovetkez˝ o diofantikus egyenletb˝ol, a kiterjesztett euklideszi algoritmussal [3] lehet meghatározni: 2c = a · h + b · 2lH +lL . A rendszer helyessége a k¨ ovetkez˝ o elemi szám´ıtások elvégzése során látható be. Az R és S értékek a k¨ ovetkez˝ o form´ aban ´ırhatóak fel: l

S = (g h · g α·2 H l +l R = g r·2 H L .

+lL

)r ,

Az (5.1) egyenl˝ oség helyességének a belátásához a következ˝ok ´ırhatóak fel:

l

S2 H

+lL

lH +lL

Rh+α·2

l

+l

l

+l

= g (h+α·2 H L )·r·2 H L , l +l l +l = g r·2 H L ·(h+α·2 H L ) .

A kulcs kisz´ am´ıt´ as´ anak helyessége a következ˝oképpen ellen˝orizhet˝o: S a · Rb−a·α S · R−α S a · Rb−a·α l −c a (S · Rb−a·α )2 H

= = = =

(S · R−α )a · Rb , l +l l +l g hr · g rα·2 H L · g −rα·2 H L = g hr , l +l l +l c g hra · g br·2 H L = g r(ha+b·2 H L ) = g r·2 , c l −c g r·2 ·2 H = g rlH .

A rendszer CCA-biztons´ ag´ anak bizony´ıtása a következ˝oképpen vázolható fel, részletes bizony´ıt´ asa, amelyre nem tér¨ unk ki, a [35] cikkben található meg. Ha feltételezz¨ uk, hogy létezik egy D támadó algoritmus, amely egy véletlenszer˝ uen gener´ alt N érték ismeretében 1/2 + ε valósz´ın˝ uséggel, ahol ε nem elhanyagolhat´ o érték, meg tudja k¨ ulönböztetni egymástól a BBS által generált biteket egy ugyanolyan lL hossz´ u, véletlenszer˝ uen generált bitsorozattól, akkor szerkeszthet˝ o egy olyan probabilisztikus, polinomiális A támadó algoritmus, amely nem elhanyagolható valósz´ın˝ uséggel faktorizálni tudja az N sz´ amot; ezzel, pedig ellent mondunk a faktorizációs feltételezésnek.

66

5.4. Az ElGamal-rendszer Az ElGamal titkos´ıt´ o rendszert T. ElGamal publikálta, és bizony´ıtotta, hogy a rendszer ellen´ all a CPA-t´ amadásnak, viszont a CCA-támadásnak nem [27]. CPA-biztons´ ag´ at a diszkrét logaritmus feltételezés alapján bizony´ıtotta, ahol az ehhez kapcsol´ odó értelmezést a 4.3.4. szakaszban adtuk meg. A diszkrét logaritmus problémához kapcsolódó felvetések egyik részletes t´ argyal´ asa a [51] cikkben is olvasható. A rendszer minden olyan ciklikus algebrai csoportban implementálható, ahol fennáll a döntési Diffie– Hellman-feltételezés, ahol az ehhez kapcsolódó értelmezést pedig a 4.3.5. szakaszban adtuk meg. A rendszer [27]-ben publik´ alt verziója alapján és a 4.1. értelmezés szerint a k¨ ovetkez˝ o algoritmusok adhatók meg: • Gen, a kulcsgener´ al´ o algoritmus meghatároz egy G ciklikus csoportot, amelynek rendje a q, majd R

– meghat´ arozza a g gener´ ator elemet és az α ← − {0, . . . , q − 1} sz´ amot, – legyen A = g α , és – pk = (g, A), sk = α. • az Enc(G,g,A) probabilisztikus rejtjelez˝o algoritmus polinomiális id˝oben végzi a rejtjelezést az m ∈ G bemenetre: c ← Enc(G,g,A) (m), ahol R

– β← − {0, . . . , q − 1}, B = g β , – c = (c1 , c2 ), ahol c1 = B, c2 = Aβ · m. • a Decα determinisztikus visszafejt˝o algoritmus polinomiális id˝oben végzi a visszafejtést a c ∈ G rejtjelezett szövegen: m ← Decα (c), ahol – m = (cα1 )−1 · c2 . A sikeres CCA-t´ amad´ as lépéssorozata a következ˝o lesz, amely egy polinomiális idej˝ u, probabilisztikus A t´ amadó algoritmus és környezete, a kih´ıvó között játsz´ odik le: 5.2. k´ısérlet. 67

1. A kih´ıv´ o futtatja a Gen kulcsgener´ al´ o algoritmust, meghat´ arozza a G, q, g, α, A értékeket, majd ´ atadja az (G, g, A) nyilv´ anos adatokat az A t´ amad´ onak, 2. az A t´ amad´ o, két azonos hossz´ us´ ag´ u u ¨zenetet hat´ aroz meg, jel¨ olj¨ uk ezeket m0 , m1 -gyel, amelyeket ´ atad a kih´ıv´ onak, R 3. a kih´ıv´ o a b ← − {0, 1} v´ alaszt´ as alapj´ an az Enc titkos´ıt´ o algoritR ∗ mussal meghat´ arozza az mb titkos´ıtott értékét: c = (c∗1 , c∗2 ) ← − Enc(G,g,A) (mb ), amelyet ´ atad az A t´ amad´ onak, 4. az A t´ amad´ o elvégzi a k¨ ovetkez˝ oket: • véletlenszer˝ uen gener´ alja β-t és m-t: R

R

β← − {0, . . . , q − 1}, m ← − {0, . . . , q − 1}, • kisz´ am´ıtja c1 = c∗1 · g β , és c2 = c∗2 · m · Aβ értékeket, • futtatja a c = (c1 , c2 ) bemenetre, ahol c 6= c∗ , a kih´ıv´ o Decα (·) visszafejt˝ o algoritmus´ at, meghat´ arozva ezzel az m ˆ értéket, • ha m ˆ · m−1 = m0 , akkor ˆb = 0, m´ asképp ˆb = 1 lesz az A t´ amad´ o v´ alaszt´ asa. Az A támad´ o 4.11. értelmezés szerinti el˝onye 12 , mert fennáll: m ˆ (cα1 )−1 · c2 ((c∗1 · g β )α )−1 · c∗2 · m · Aβ ((c∗1 )α )−1 · g −β·α · c∗2 · m · g α·β ((c∗1 )α )−1 · c∗2 · m mb · m.

= = = = =

1 1 1 ˆ Formálisan Advcca ElGamal,A (k) = | Pr[b = b] − 2 | = |1 − 2 | = 2 , ahol a b és ˆb értékeket a 5.2. k´ısérletben hat´ aroztuk meg. Standard modellben az ElGamal CCA-biztonság´ u verzióját Cramer és Shoup dolgozták ki [21]. Az ElGamal egy másik fontos CCA-biztonság´ u verziója a DHIES [1]. A Cramer és Shoup által szerkesztett rendszer CCA-biztonság´ at, a szerz˝ ok a d¨ ontési Diffie–Hellman-feltételezés alapján bizony´ıtották, illetve feltételezték, hogy az alkalmazott hash f¨ uggvény célu ¨tközésmentes hash f¨ uggvény (l´ asd a 3.2. értelmezést). Fontos megjegyezni, hogy ez volt az els˝ o hatékony CCA-biztonság´ u kulcsbeágyazási

68

mechanizmus. T¨ obb verzi´ oja is létezik, aszerint hogy az alkalmazásra ker¨ ul˝o hash f¨ uggvény milyen tulajdonság´ u: univerzális hash f¨ uggvény, célu ¨tközésmentes hash f¨ uggvény vagy u ¨tközésmentes hash f¨ uggvény. Abban az esetben amikor az alkalmazásra ker¨ ul˝o hash f¨ uggvény célu ¨tközésmentes hash f¨ uggvény a Cramer és Shoup titkos´ıtó három algoritmusa a k¨ ovetkez˝ o: • Gen, a kulcsgener´ al´ o algoritmus meghatároz egy G ciklikus csoportot, amelynek rendje q, majd: – meghat´ arozza a g1 , g2 generátor elemeket, – véletlenszer˝ uen meghat´ aroz öt számot: R

(x1 , x2 , y1 , y2 , α) ← − {0, . . . , q − 1}, amelyek alapj´ an kisz´ am´ıtja a következ˝o értékeket: e = g1x1 · g2x2 , f = g1y1 · g2y2 és A = g1α – a nyilv´ anos adatok: (G, q, g1 , g2 ), – a nyilv´ anos kulcs: pk = (e, f, A), – a titkos kulcs: sk = (x1 , x2 , y1 , y2 , α). • az Enc(G,q,g1 ,g2 ,e,f,A) probabilisztikus rejtjelez˝o algoritmus polinomiális id˝ oben, végzi a rejtjelezést az m ∈ G bemenetre: (a1 , a2 , c, d) ← Enc(G,q,g1 ,g2 ,e,f,A) (m), ahol – – – –

R

legyen β ← − {0, . . . , q − 1}, a1 = g1β , a2 = g2β , β c = A · m, h = H(a1 , a2 , c), ahol H cél-¨ utközésmentes hash f¨ uggvény, β β·h d=e ·f .

• a Dec(x1 ,x2 ,y1 ,y2 ,α) determinisztikus visszafejt˝o algoritmus polinomiális id˝oben végzi a visszafejtést az (a1 , a2 , c, d) rejtjelezett szövegen: m ← Dec(x1 ,x2 ,y1 ,y2 ,α) (a1 , a2 , c, d), ahol – meghat´ arozza: h = H(a1 , a2 , c),

69

– ha nem ´ all fenn a k¨ ovetkez˝ o egyenl˝oség: d = a1x1 +y1 ·h · a2x2 +y2 ·h ,

(5.3)

akkor REJECT elutas´ıt´ o kimeneti értékkel leáll az algoritmus, ellenkez˝ o esetben ∗ meghat´ arozza: m = c · (aα1 )−1 . (5.4) A rendszer helyessége néh´ any elemi szám´ıtás során ellen˝orizhet˝o, a d értéke, a (5.3) egyenl˝ oségben a k¨ ovetkez˝ o formában ´ırható fel: d eβ · f β·h (g1x1 · g2x2 )β · (g1y1 · g2y2 )β·h g1β·x1 · g2β·x2 · g1β·y1 ·h · g2β·y2 ·h ax1 1 +y1 ·h · ax2 2 +y2 ·h .

= = = =

Az 5.4 egyenl˝ oség pedig a k¨ ovetkez˝ o formában ´ırható fel: c · (aα1 )−1 = (Aβ · m) · (aα1 )−1 = g1αβ · m · (g1βα )−1 = m. A rendszer CCA-biztons´ ag´ anak bizony´ıtása a következ˝oképpen vázolható fel, részletes bizony´ıt´ asra jelen értekezés keretén bel¨ ul nem tér¨ unk ki [20]. Ha feltételezz¨ uk, hogy létezik egy A t´ amadó, amely egy véletlenszer˝ uen generált nyilvános kulcs ismeretében 1/2 + ε valósz´ın˝ uséggel (ahol ε nem elhanyagolható érték) meg tud k¨ ul¨ onb¨ oztetni egymástól bizonyos rejtjelezett szövegeket, akkor szerkeszthet˝ o egy olyan probabilisztikus, polinomiális B támad´ o algoritmus, amely nem elhanyagolható valósz´ın˝ uséggel β βλ β λ λ z k¨ ulönbséget tesz a (g1 , g1 , g1 ) és (g1 , g1 , g1 ) között amellyel ellent mondunk a döntési Diffie–Hellman-feltételezésnek, ahol β, z véletlenszer˝ uen meghatározott értékek. 5.2. megjegyzés. A CS rendszerben az (5.3) egyenl˝ oség a k¨ ovetkez˝ o form´ aban is fel´ırhat´ o, ahol alkalmazhat´ o a g2 = g1λ jel¨ olés: 70

(g1β )x1 +y1 ·h · (g2β )x2 +y2 ·h = ax1 1 +y1 ·h · a2x2 +y2 ·h .

(5.5)

Az (5.5) egyenl˝ oséget csak azok a rejtjelezett sz¨ ovegek elég´ıtik ki, amelyek esetében fenn´ all, hogy logg1 a1 = logg2 a2 , és nagyon kicsi a val´ osz´ın˝ usége annak, hogy egy olyan rejtjelezett sz¨ oveg is teljes´ıtse az (5.5) egyenl˝ oséget, amelyre ez nem ´ all fenn, ami alapj´ an megszerkeszthet˝ o a B algoritmus. 5.3. megjegyzés. Abban az esetben, ha az m értéke valamely hibrid rendszer keretén bel¨ ul véletlenszer˝ uen ker¨ ul kiv´ alaszt´ asra, a fenti titkos´ıt´ o, kulcsbe´ agyaz´ asi mechanizmusnak tekinthet˝ o. Ez a kor´ abban t´ argyalt titkos´ıt´ o rendszerek mindegyikére igaz.

71

72

6. fejezet

Az u ´j kulcsbeágyazási mechanizmus 6.1. Bevezet˝ o Az értekezés keretén bel¨ ul bemutatásra ker¨ ul˝o CPA-biztonság´ u és CCAbiztonság´ u kulcsbe´ agyaz´ asi mechanizmusok alapjául a Rabin-titkos´ıtó és a Hofheinz és t´ arsai [35], ´ altal szerkesztett rendszerek szolgáltak. A CCAbiztonság´ u kulcsbe´ agyaz´ asi mechanizmus a [48] cikkben ker¨ ult publikálásra. Kriptogr´ afiai rendszerek szerkesztésénél Rabin [54] alkalmazta el˝oször a négyzetreemelés f¨ uggvényt és bebizony´ıtotta, hogy ennek a f¨ uggvénynek az invertálása ugyanolyan nehéz matematikai feladat, mint az egész számok faktorizáci´ os problém´ aja. Az 5.2. alfejezetben bemutattuk, hogy az eredeti rendszer teljesen védtelen egy választott rejtjelezett szöveg alap´ u támadással szemben. A fejezetben bemutatásra ker¨ ul˝o kulcsbeágyazási mechanizmusok szintén a négyzetreemelés f¨ uggvényen alapulnak, azzal a k¨ ulönbséggel, hogy az alkalmazott egyirány´ u f¨ uggvények, bemeneti érték¨ uket egyik esetben a QRN halmazból, másik esetben a QR+ ol N halmazb´ + veszik, ahol a QRN halmazt az 5.1. értelmezéssel adtuk meg. A rendszerek CPA-biztons´ ag´ at, illetve CCA-biztonságát be tudtuk bizony´ıtani

73

a faktorizációs feltételezésb˝ ol, illetve az alkalmazott hash f¨ uggvény célu ¨tközésmentes tulajdons´ ag´ ab´ ol kiindulva. A faktorizációs feltételezésen alapuló titkos´ıt´ o rendszerek biztons´ ag´ at a [49] cikkben tárgyaltuk. A továbbiakban el˝ osz¨ or megadjuk a CPA-biztonság´ u kulcsbeágyazási mechanizmus szerkesztésének lépéssorozatát, majd a fejezet második felében a CCA-biztons´ ag´ u kulcsbe´ agyaz´ asi mechanizmust mutatjuk be. Mindkét kulcsbe´ agyaz´ asi mechanizmus esetében a következ˝o Gen kulcsgeneráló algoritmusra van sz¨ ukség¨ unk: 6.1. algoritmus. A Gen kulcsgener´ al´ o algoritmus az 1k bemeneten megR hat´ arozza az (N, P, Q) sz´ amh´ armast: (N, P, Q) ← − Gen(1k ) u ´gy, hogy: • N = P · Q, ahol P, Q pr´ımsz´ amok, u ´gy hogy – P ≡ Q ≡ 3 (mod 4),és – P = 2 · p + 1, Q = 2 · q + 1, ahol p, q szintén pr´ımsz´ amok, • A p és a q bithossza k/2 − 1, A fenti Gen kulcsgener´ al´ o algoritmus által generált értékek f¨ uggvényében a faktoriz´ aci´ os feltételezés a következ˝o formában jelenthet˝o ki: 6.1. defin´ıció. B´ armely probabilisztikus polinomi´ alis idej˝ u A algoritmus esetében, létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy AdvF AC,A (k) = Pr[A(N ) = (P, Q)] ≤ f (k),

6.2. Az u ´j CPA-biztonság´ u rendszer 6.2.1. A rendszer le´ırása Az u ´j kulcsbeágyaz´ asi mechanizmus egy cél-¨ utközésmentes hash f¨ uggvényt lG fog használni, jel¨ olj¨ uk ezt G : QRN → {0, 1} -val. Az u ´j CPA-biztons´ ag´ u kulcsbe´ agyazási mechanizmus, a 4.15. értelmezés szerinti h´ arom algoritmusa a következ˝o: • A Gencpa al´ o algoritmus, amely meghatározza az KEM egy kulcsgener´ R k (N, P, Q) ← − Gen(1 ) értékeket, ahol 74

– az N, P, Q értékeket a 6.1. algoritmussal határozta meg, – pk = N , és sk = (P, Q). • Az Enccpa agyaz´ asi algoritmus az N bemeneten a követKEM kulcsbe´ kez˝ oket végzi: R

– gener´ alja r-t: r ← − {1, . . . , (N − 1)}, – meghat´ arozza: K = r2 (mod N ) ∈ QRN , és key = G(K), ahol G : QRN → {0, 1}lG cél-¨ utközésmentes hash f¨ uggvény, 2 – meghat´ arozza: cipher = K (mod N ), – az algoritmus kimeneti értéke (key, cipher). • A Deccpa asi algoritmus a (P, Q) és cipher bemeneti KEM kulcskibont´ értékeken a k¨ ovetkez˝ oket végzi: – a K´ınai maradéktételt alkalmazva meghatározza a K értékét, megoldva a k¨ ovetkez˝ o kongruencia rendszert: K = cipher(P +1)/4 (mod P ), K = cipher(Q+1)/4 (mod Q), – az algoritmus kimeneti értéke a key = G(K) lesz.

6.2.2. A rendszer helyessége A rendszer helyességének bizony´ıt´ asához sz¨ ukség van a f˝o négyzetes gyök fogalmának az értelmezésére [61]: 6.2. defin´ıci´ o. Az x ∈ {1, . . . , N } sz´ amot az y kvadratikus maradék f˝ o négyzetes gy¨ okének nevezz¨ uk, ha x szintén kvadratikus maradék (mod N ) szerint. Sz¨ ukséges tov´ abb´ a a k¨ ovetkez˝ o tételt is kijelenten¨ unk, amelynek bizony´ıtása megtal´ alhat´ o [61]-ben. 6.1. tétel. Ha a P, Q pr´ımsz´ amokra teljes¨ ul, hogy P ≡ Q ≡ 3 (mod 4), akkor b´ armely x kvadratikus maradék esetén egyetlen olyan négyzetes gy¨ oke van az x-nek, amely szintén kvadratikus maradék (mod N ) szerint. Ezut´ an bel´ athat´ o az u ´j rendszer helyessége a következ˝ok alapján: 75

• mivel N = P · Q és P ≡ Q ≡ 3 (mod 4), igaz, hogy a cipher tetsz˝oleges, kvadratikus maradék (mod P ) szerinti négyzetes gyöke meghatározhat´ o a k¨ ovetkez˝ o képlettel: ±cipher(P +1)/4 (mod P ), • de cipher-nek (mod P ) szerint cipher(P +1)/4 (mod P ) a f˝o négyzetes gyöke, • hasonlóan cipher-nek (mod Q) szerint cipher(Q+1)/4 (mod Q) a f˝o négyzetes gy¨ oke, • alkalmazhat´ o ezek ut´ an a k´ınai maradéktétel, tehát K = r2 (mod N ) 2 a cipher = K (mod N ) f˝ o négyzetes gyöke, (mod N ) szerint.

6.2.3. A rendszer biztonsága Az u ´j rendszer CPA-biztons´ ag´ anak bizony´ıtásához a következ˝o k´ısérletet értelmezz¨ uk, amely k´ısérlet egy polinomiális idej˝ u, probabilisztikus A támadó és a környezete k¨ oz¨ ott, a kih´ıv´ o között játszódik le: 6.1. k´ısérlet. k 1. A kih´ıv´ o futtatja a Gencpa al´ o algoritmust, megKEM (1 ) kulcsgener´ hat´ arozza az (N, (P, Q)) értékeket, majd a az N értéket ´ atadja az A t´ amad´ onak, 2. az A t´ amad´ o tetsz˝ oleges sz´ am´ u alkalommal megh´ıvja a kih´ıv´ o Enccpa (N ) ´ e s G(·) algoritmusait, KEM 3. a kih´ıv´ o elvégzi a k¨ ovetkez˝ oket:

• • • • •

meghat´ arozza: (key ∗ , cipher∗ ) ← Enccpa KEM (pk), R gener´ al egy u értéket: u ← − QRN , a (key ∗ )-t c0 -val jel¨ oli, a (G(u))-t c1 -gyel jel¨ oli, ´ atadja az A t´ amad´ onak a (cb , cipher∗ ) titkos´ıtott értékp´ art, ahol R b← − {0, 1},

4. az A t´ amad´ o tetsz˝ oleges sz´ am´ u alkalommal megh´ıvja a kih´ıv´ o Enccpa (N ) ´ e s G(·) algoritmusait, KEM 5. az A t´ amad´ o meghat´ aroz egy ˆb ∈ {0, 1} kimeneti értéket. Jelölj¨ uk a tov´ abbiakban Expr(0)-val azt az eseményt, amikor ˆb = 1, azon feltétel mellett, hogy a kih´ıv´ onak b = 0 volt a választása, és jelölj¨ uk 76

Expr(1)-gyel azt az eseményt, amikor ˆb = 1 azon feltétel mellett, hogy a kih´ıvó a b = 1 értéket v´ alasztotta. A tov´ abbiakban a k¨ ovetkez˝ o f¨ uggvényt definiáljuk: 1 Advcpa KEM,A (k) = 2 | Pr[Expr(0)] − Pr[Expr(1)]|,

amely alapj´ an a CPA-biztons´ ag értelmezése a következ˝o lesz: 6.3. defin´ıci´ o. Az u ´j kulcsbe´ agyaz´ asi mechanizmus CPA-biztons´ ag´ u, ha b´ armely probabilisztikus, polinomi´ alis idej˝ u A t´ amad´ o esetében létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy Advcpa KEM,A (k) ≤ f (k). Ezek ut´ an a k¨ ovetkez˝ o tételt jelenthetj¨ uk ki: 6.2. tétel. Ha a fenti k´ısérletben a G a 3.2. értelmezés szerint defini´ alt célu ¨tk¨ ozésmentes hash f¨ uggvény, azaz ha fenn´ all, hogy b´ armely probabilisztikus polinomi´ alis B t´ amad´ o algoritmus esetén létezik egy fB (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy R

R

AdvCR1,B (G) = P r[x ← − QRN , y ← − B(x) : x 6= y, G(x) = G(y)] ≤ fB (k) és ha a 6.1. értelmezés szerint megadott faktoriz´ aci´ os feltételezést elfogadjuk, akkor létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy Advcpa KEM,A (k) ≤ f (k). Bizony´ıt´ as. Minden olyan esetben, amikor az A támadó a G hash f¨ uggvény kiértékelését a K pontra kéri ismernie kell a K értékét, amelyet r2 -b˝ol tud kiszám´ıtani (ez azért igaz, mert r értékét véletlenszer˝ uen határozzuk meg, és mert feltételezt¨ uk, hogy G u ¨tközésmentes hash f¨ uggvény). Ha azonban a fenti esemény nem elhanyagolható valósz´ın˝ uséggel következik be, akkor szintén nem elhanyagolható valósz´ın˝ uséggel következett be, hogy az A támad´ o meghat´ arozta a K értékét K 2 és N ismeretében. Ez viszont akkor következhet be, ha az A t´ amadó nem elhanyagolható valósz´ın˝ uséggel oldotta meg a faktoriz´ aci´ os problémát.

77

6.2.4. A rendszer hatékonysága Biztonságos pr´ımek gener´ al´ asa ´ altal´ aban id˝oigényes feladat, de gyors´ıtani lehet az algoritmust a [66] alapj´ an. A kulcsbeágyaz´ asi algoritmus két moduláris négyzetre emelést végez a kulcskibontási algoritmus, pedig két moduláris hatványozást végez. Következésképpen mindkét algoritmus futási ideje nagyon jó hatékonyság´ u.

6.3. Az u ´j CCA-biztonság´ u rendszer 6.3.1. A rendszer le´ırása Az u ´j kulcsbeágyaz´ asi mechanizmus két cél-¨ utközésmentes hash f¨ uggvényt lH → {0, 1} -val, a m´ a sikat G : fog használni, jel¨ olj¨ uk az egyiket H : QR+ N + lG QRN → {0, 1} -vel. A QR+ ertelmezéssel definiáltunk, több N halmaznak, amelyet az 5.1. ´ olyan tulajdons´ aga is van, amely kriptográfiai szempontból hasznos, és amelyekre a tov´ abbi bizony´ıt´ asok sor´ an sz¨ ukség¨ unk lesz [35]. Ezek a következ˝oek: • QR+ ıv m˝ uveletre nézve ciklikus csoportot alkot, amelyN a multiplikat´ nek rendje φ(N )/4, ahol φ(N ) = (P − 1) · (Q − 1), • hatékonyan eld¨ onthet˝ o, hogy egy elem hozzátartozik a QR+ N halmazhoz vagy sem: az adott elemr˝ ol ellen˝orizni kell, hogy benne van-e az {1, . . . , (N − 1)/2} halmazban, illetve, hogy a Jacobi szimbóluma (mod N ) szerint 1-e. • a QR+ uli kvadratikus maradékok meghatározásának N halmazon bel¨ problémáj´ anak nehézsége ekvivalens a faktorizációs problémával, • a QR+ uli négyzetreemelés f¨ uggvény egy permutáció lesz N halmazon bel¨ + a QRN -ben, • egy egyenletes eloszl´ as szerint, véletlenszer˝ uen generált g ∈ QR+ N elem nagy valósz´ın˝ uséggel gener´ ator elem lesz; annak a valósz´ın˝ usége, hogy a g nem lesz gener´ ator elem, a k¨ ovetkez˝o: (p + q − 1)/(p · q) ≤ 2−k+2 . 78

6.1. megjegyzés. Megjegyezz¨ uk, hogy a fenti korl´ at bizony´ıt´ as´ an´ al fontos szerepet kap, az hogy P = 2 · p + 1, Q = 2 · q + 1, ahol p, q is pr´ımsz´ amok [35] éppen ezért az u ´j CCA-biztons´ ag´ u rendszer szerkesztéséhez, a fenti m´ odon el˝ o´ all´ıtott pr´ımeket kell haszn´ alni. A szakirodalom, ahogy a 5.1. algoritmusn´ al is eml´ıtett¨ uk, az N sz´ amot Blum-egésznek, a P, Q pr´ımeket, pedig biztons´ agos (safe) pr´ımeknek nevezi. Az u ´j CCA-biztons´ ag´ u kulcsbeágyazási mechanizmus, a 4.15. értelmezés szerinti h´ arom algoritmusa a következ˝o, ahol a m˝ uveleteket QR+ -ben v´ e gezz¨ u k:: N k aló algoritmus, amely egyenletes eloszlás A Gencca KEM (1 ) egy kulcsgener´ szerint, véletlenszer˝ uen az 1k bemeneten a következ˝oképpen generálja a pk nyilvános kulcsot és az sk titkos kulcsot: • gener´ al egy N ¨ osszetett sz´ amot a 6.1. algoritmus szerint, R R • gener´ alja g-t és α-t a k¨ ovetkez˝ oképpen: g ← − QR+ − {1, . . . , (N − N, α ← lH α·2 2 1)/4}, majd meghat´ arozza X-t: X = (g ) • az algoritmus kimeneti értékei a pk = (N, g, X), és sk = α. Az Enccca agyaz´ asi algoritmus az N, g és X bemeneti KEM kulcsbe´ értékeken a k¨ ovetkez˝ oket végzi: R

• gener´ alja r-t: r ← − {1, . . . , (N − 1)/4}, l lG • meghat´ arozza: K = g r·2 H , és key = G(K), ahol G : QR+ N → {0, 1} cél-¨ utk¨ ozésmentes hash f¨ uggvény, lH • meghat´ arozza S = (g h ·X)r , ahol h = H(K 2 ), és H : QR+ N → {0, 1} , cél-¨ utk¨ ozésmentes hash f¨ uggvény, 2 • meghat´ arozza az R = K értéket, • az algoritmus kimeneti értéke (key, cipher), ahol cipher = (R, S). A Deccca asi algoritmus az α és cipher = (R, S) bemeneti KEM kulcskibont´ értékeken a k¨ ovetkez˝ oket végzi: • ha a k¨ ovetkez˝ o tartalmaz´ as nem áll fenn: + (R, S) ∈ QR+ N × QRN ,

79

akkor az algoritmus REJECT elutas´ıtó kimeneti értékkel leáll, ellenkez˝o esetben – meghat´ arozza a h = H(R) értéket, – ha a k¨ ovetkez˝ o egyenl˝ oség nem áll fenn: 1+lH

S2

1+lH

= Rh+α·2

,

(6.1)

akkor az algoritmus REJECT elutas´ıtó kimeneti értékkel leáll, ellenkez˝ o esetben ∗ kiterjesztett euklideszi algoritmussal, meghatározza az a, b, c értékeket a k¨ ovetkez˝ o diofantikus egyenletb˝ol: 2c = a · h + b · 21+lH , ahol 2c a h és 21+lH legnagyobb közös osztója lesz (a diofantikus egyenlet megoldhat´ o lesz, mert fennáll 0 < h < 2lH , amib˝ ol k¨ ovetkezik, hogy c < lH ), ∗ az algoritmus kimenete a key érték lesz, ahol l −c key = G((S a · Rb−a·α )2 H ). A Deccca asi algoritmusnak, ha az α és cipher = (R, S) KEM kulcskibont´ bemeneti értékek mellett megadjuk bemeneti paraméterként a P és Q értékeket is, akkor a (6.1) egyenl˝ oség elvégzése után a key értékének, hatékonyabb m´ odon val´ o meghat´ aroz´ asa, a következ˝oképpen is történhet: • a k´ınai maradéktételt alkalmazva meghatározzuk a K értékét, megoldva a k¨ ovetkez˝ o kongruencia rendszert: K = R(P +1)/4 (mod P ), K = R(Q+1)/4 (mod Q), • az algoritmus kimeneti értéke a key = G(K) lesz.

6.3.2. A rendszer helyessége Az u ´j rendszer helyessége néh´ any elemi szám´ıtás során ellen˝orizhet˝o. Egyszer˝ uen bel´ athat´ o, hogy az S és R értékek a következ˝o formában ´ırhatóak fel: 80

l

S = (g h · X)r = g r·(h+2·α·2 H ) , l R = g 2·r·2 H . Az (6.1) egyenl˝ oség helyességének a belátásához a következ˝o szám´ıtások végezhet˝oek el: 1+lH

S2 R

h+α·21+lH

l

l

= g 2·2 H ·r·(h+2·α·2 H ) , l l = g (h+α·2·2 H )·2·r·2 H .

A kulcs kisz´ am´ıt´ as´ anak helyessége a következ˝oképpen ellen˝orizhet˝o: S a · Rb−a·α = = = l −c (S a · Rb−a·α )2 H =

l

l

l

g a·r·h+a·r·2·α·2 H · g b·2·r·2 H −a·α·2·r·2 H l g r·(a·h+b·2·2 H ) c g r·2 , l g r·2 H .

6.3.3. A rendszer biztonsága Az u ´j rendszer CCA-biztons´ ag´ anak bizony´ıtásához a következ˝o k´ısérletet értelmezz¨ uk, amely k´ısérlet egy polinomiális idej˝ u probabilisztikus A támadó és a k¨ ornyezete, a kih´ıv´ o k¨ ozött zajlik: 6.2. k´ısérlet. k 1. A kih´ıv´ o futtatja a Gencca al´ o algoritmust, megKEM (1 ) kulcsgener´ hat´ arozza az N, g, X, α értékeket, majd az N, g, X értékeket, ´ atadja az A t´ amad´ onak, 2. az A t´ amad´ o tetsz˝ oleges sz´ am´ u alkalommal megh´ıvja a kih´ıv´ o Deccca (α, ·) ´ e s G(·), H(·) algoritmusait, KEM 3. a kih´ıv´ o elvégzi a k¨ ovetkez˝ oket:

• • • • •

meghat´ arozza (key ∗ , cipher∗ ) ← Enccca KEM (N, g, X), R + gener´ al egy u értéket: u ← − QRN , a (key ∗ )-t c0 -val jel¨ oli, a (G(u))-t c1 -gyel jel¨ oli, R ´ atadja az A t´ amad´ onak a (cb , cipher∗ ) értékp´ art, ahol b ← − {0, 1}, 81

4. az A t´ amad´ o tetsz˝ oleges sz´ am´ u alkalommal, k¨ ul¨ onb¨ oz˝ o cipher értékekre megh´ıvja a kih´ıv´ o Deccca (α, cipher) ´ e s G(·), H(·) algoKEM ritmusait, azzal a megk¨ otéssel, hogy cipher 6= cipher∗ , 5. az A t´ amad´ o meghat´ aroz egy ˆb ∈ {0, 1} kimeneti értéket. Jelölj¨ uk a tov´ abbiakban Expr(0)-val azt az eseményt, amikor a támadó a´ltal meghatározott kimeneti érték 1, azon feltétel mellett, hogy a kih´ıvónak b = 0 volt a választ´ asa, és jel¨ olj¨ uk Expr(1)-gyel azt az eseményt, amikor a támadó által meghat´ arozott kimeneti érték 1, azzal a feltétellel, hogy a kih´ıvó a b = 1 értéket v´ alasztotta. A továbbiakban a k¨ ovetkez˝ o f¨ uggvényt definiáljuk: 1 Advcca KEM,A (k) = 2 | Pr[Expr(0)] − Pr[Expr(1)]|,

amely alapj´ an a CCA-biztons´ ag értelmezése a következ˝o lesz: 6.4. defin´ıció. Az u ´j kulcsbe´ agyaz´ asi mechanizmus CCA-biztons´ ag´ u, ha b´ armely probabilisztikus, polinomi´ alis idej˝ u A t´ amad´ o esetében létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy Advcca KEM,A (k) ≤ f (k). Ezek után a k¨ ovetkez˝ o tételt jelenthetj¨ uk ki: 6.3. tétel. Ha a fenti k´ısérletben a H és G a cél-¨ utk¨ ozésmentes hash f¨ uggvények, azaz ha fenn´ all, hogy b´ armely probabilisztikus polinomi´ alis B1 t´ amad´ o algoritmus esetén létezik egy fB1 (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy R

R

AdvCR1,B1 (H, k) = P r[x ← − QRN , y ← − B1 (x) : x 6= y, H(x) = H(y)] ≤ fB1 (k) és ha fenn´ all, hogy b´ armely probabilisztikus polinomi´ alis B2 t´ amad´ o algoritmus esetén létezik egy fB2 (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy R

R

AdvCR1,B2 (G, k) = P r[x ← − QRN , y ← − B2 (x) : x 6= y, G(x) = G(y)] ≤ fB2 (k) és ha a 6.1. értelmezés szerint megadott faktoriz´ aci´ os feltételezést elfogadjuk, akkor létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy 82

Advcca KEM,A (k) ≤ f (k). Ahhoz, hogy a 6.3. tétel bizony´ıtását megadhassuk, el˝obb további két tételt jelent¨ unk ki és bizony´ıtunk be, a 6.4. és a 6.5. tételt. 6.4. tétel. Ha elfogadjuk a 6.1. értelmezés szerinti faktoriz´ aci´ os feltételezést, és ha a G hash f¨ uggvény cél-¨ utk¨ ozésmentes tulajdons´ ag´ u, akkor létezik egy f (k) elhanyagolhat´ o f¨ uggvény u ´gy, hogy b´ armely probabilisztikus polinomi´ alis idej˝ u D t´ amad´ o algoritmus esetén fenn´ all: AdvDDS,D (k) = | Pr[D(N, K 2 , G(K)) = 1] − Pr[D(N, K 2 , G(u)) = 1]| ≤ f (k), R

ahol K a kulcsbe´ agyaz´ asi algoritmus sor´ an meghat´ arozott érték és u ← − + QRN . Inform´ alisan ez azt jelenti, hogy ha szerkeszt¨ unk egy olyan D algo2 ritmust, amely k¨ ul¨ onbséget tud tenni az (N, K , G(K)) és (N, K 2 , G(u)) számhármasok k¨ oz¨ ott, akkor a D algoritmus alkalmas lesz arra, hogy faktorizálja az N értékét. A tov´ abbiakban ezt a t´ıpus´ u algoritmust D-tulajdonság´ u algoritmusnak fogjuk h´ıvni. Bizony´ıt´ as. Legyen D egy olyan algoritmus, amelyr˝ol feltételezz¨ uk, hogy k¨ ulönbséget tud tenni az (N, K 2 , G(K)) és (N, K 2 , G(u)) számhármasok között • bemeneti értékként a D algoritmusnak megadjuk az (N, K 2 , V ) számh´ armast, ahol V vagy a G(K) vagy G(u) értéket veszi fel, és R ahol u ← − QR+ N, • a D algoritmus t¨ obb, egyenletes eloszlás szerint véletlenszer˝ uen gener´ alt bemeneti értékekre meghatározza a G hash f¨ uggvény kimenetét, • minden olyan esetben, amikor a D algoritmus a G f¨ uggvény kiértékelését a K pontban végzi ismernie kell a K értékét, amelyet K 2 -b˝ ol tud kisz´ am´ıtani (ez azért igaz, mert feltételezt¨ uk, hogy G u ¨tk¨ ozésmentes hash f¨ uggvény),

83

• ha azonban a fenti esemény nem elhanyagolható valósz´ın˝ uséggel következik be, akkor szintén nem elhanyagolható valósz´ın˝ uséggel következett be az az esemény is, hogy a D algoritmus meghatározta a K értékét K 2 és N ismeretében, • ha a D algoritmus nem elhanyagolható valósz´ın˝ uséggel határozta meg a K értékét a K 2 és N ismeretében, akkor a D algoritmus nem elhanyagolhat´ o val´ osz´ın˝ uséggel oldotta meg a faktorizációs problémát, ami viszont ellentmond a faktoriz´ aciós feltételezésnek. A fenti gondolatmenet alapj´ an kijelenthet˝o, hogy: AdvDDS,D (k) ≤ AdvF AC,A (k) + AdvCR1,B (k).

azaz a AdvDDS,D (k) f¨ uggvény k szerint elhanyagolható. 6.5. tétel. Ha A egy probabilisztikus, polinomi´ alis idej˝ u t´ amad´ o algoritmus, amely felt¨ ori az u ´j rendszer CCA-biztons´ ag´ at, akkor szerkeszthet˝ o egy probabilisztikus polinomi´ alis idej˝ u D algoritmus, amely D-tulajdons´ ag´ u vagy szerkeszthet˝ o egy probabilisztikus polinomi´ alis idej˝ u B algoritmus, amely felt¨ ori a H f¨ uggvény u ¨tk¨ ozésmentes tulajdons´ ag´ at. Form´ alisan ez a k¨ ovetkez˝ oket jelenti: Advcca KEM,A (k) ≤ AdvDDS,D (k) + AdvCR1,B (k) + f (k),

ahol f (k) elhanyagolhat´ o f¨ uggvény. Bizony´ıt´ as. A tétel bebizony´ıt´ asa érdekében a következ˝oképpen járunk el: szerkeszt¨ unk egy D algoritmust, amely szimulálja az A támadó bemenetét. Tudjuk, hogy a D algoritmus bemenete vagy (N, K 2 , G(K)) vagy (N, K 2 , G(u))), ahol a D algoritmus megh´ıvja az A algoritmust a következ˝o bemenetekkel: • az (N, g, X) nyilv´ anos kulccsal, és a • (key ∗ , cipher∗ ) bemenettel, ha a D bemenete (N, K 2 , G(K)) vagy a (G(u), cipher∗ ) bemenettel, ha a D bemenete (N, K 2 , G(u)), ahol a g, X, key ∗ , cipher∗ értékeket a D határozta meg, a következ˝oképpen: R

R

– g← − QR+ es β ← − {1, . . . (N − 1)/4)}, N, ´ 84

∗

l

– h∗ = H(K 2 ), X = g β·2·2 H −h , – cipher∗ = (R∗ , S ∗ ), ahol R∗ = K 2 , és S ∗ = (K 2 )β , – key ∗ = G(K). Mivel g ∈ QR+ osz´ın˝ uséggel generátor elem, a 6.3.1. szakaszN nagy val´ ban megadott tulajdons´ agok szerint, feltételezhetj¨ uk, hogy: l

• X fel´ırhat´ o mint: (g α·2 H )2 , ahol α ismeretlen, de α fel´ırható β − h∗ /(2 · 2lH ) alakba, ∗ l • R∗ fel´ırhat´ o mint: g r ·2·2 H , ahol r∗ ismeretlen, ∗ ∗ • S ∗ fel´ırhat´ o mint: (g h · X)r , mert fennáll: ∗

∗

∗

∗

l

(g h · X)r = (g h · g β·2·2 H −h )r • key ∗ fel´ırhat´ o mint: g r

∗

·2lH

∗

.

Amikor az A elk¨ uldi a cipher = (R, S) értékét D-nek, hogy D meghatározza a key értékét, D le tudja ellen˝orizni, hogy az cipher érték konzisztens-e vagy sem, elvégezve a következ˝o egyszer˝ u szám´ıtásokat: ∗

l

S 2·2 H = Rh−h

+β·2·2lH

,

ahol a h értéke meghat´ arozhat´ o, mert h = H(R). Ha az (R, S) érték p´ ar nem konzisztens, akkor REJECT visszautas´ıtó kimeneti értékkel le´ all. Ha az (R, S) érték p´ ar konzisztens, akkor D két k¨ ulönböz˝o esetet tud megk¨ ulönb¨ oztetni: 1. h 6= h∗ . Ebben az esetben a következ˝o diofantikus egyenletb˝ol, a kiterjesztett euklideszi algoritmussal, D megtudja határozni az a1 , b1 , c1 értékeket: 2c1 = a1 · (h − h∗ ) + b1 · 2 · 2lH . A key meghat´ aroz´ as´ at, pedig a következ˝oképpen végzi: l

G(S a1 · Rb1 −a1 ·β )2 H

−c1

.

2. h = h∗ . Ebben az esetben tov´ abbi két alesetet k¨ ulönböztet¨ unk meg: 85

• Ha fenn´ all a k¨ ovetkez˝ o egyenl˝oség: R = R∗ , akkor igaz az is ∗ hogy S = S , viszont nem megengedett az (R∗ , S ∗ ) bemenet. • Ha fenn´ all R 6= R∗ , akkor a D algoritmus u ¨tközést talált, ami csak kis val´ osz´ın˝ uséggel k¨ ovetkezhet be. Következésképpen a pk = (N, g, X), és (R∗ , S ∗ ) értékek eloszlása abban az esetben, amikor D algoritmus szimulálja az A bemenetét, majdnem mindig ugyanolyan eloszl´ as´ u, mint a 6.2. k´ısérlet esetében. Annak a valósz´ın˝ usége, hogy nem ugyanolyan eloszlás´ uak a pk, és (R∗ , S ∗ ) értékek a következ˝o: 2−k+3 [35]. Ezek alapj´ an kijelenthet˝ o, hogy: | Pr[D(N, K 2 , G(K)) = 1] − Pr[Expr(0)]| ≤ AdvCR1,B (k) + 2−k+3 , | Pr[D(N, K 2 , G(u)) = 1] − Pr[Expr(1)]| ≤ AdvCR1,B (k) + 2−k+3 , ahol Expr(0) és Expr(1) ugyanazokat az eseményeket jelölik, mint a 6.2. k´ısérletben. Ebb˝ol következik: Advcca KEM,A (k) =

1 | Pr[Expr(0)] 2

− Pr[Expr(1)]|

≤ 12 (AdvDDS,D (k)+ +| Pr[D(N, K 2 , G(K)) = 1] − Pr[Expr(0)]|+ +| Pr[D(N, K 2 , u) = 1] − Pr[Expr(1)]|) ≤ AdvDDS,D (k) + AdvCR1,B (k) + 2−k+3 . Korábban azonban bebizony´ıtottuk, hogy: • AdvCR1,B (k) elhanyagolhat´ o k szerint, • AdvDDS,D (k) elhanyagolhat´ o k szerint. Ezeknek k¨ ovetkezményeként, a 6.4. értelmezésnek megfelel˝oen az u ´j kulcsbeágyazási mechanizmus CCA-biztonság´ u. 86

6.3.4. A rendszer hatékonysága Biztonságos pr´ımek gener´ al´ asa ´ altalában id˝oigényes feladat, de gyors´ıtani lehet az algoritmust [66] alapj´ an. A kulcsbe´ agyaz´ asi algoritmus két moduláris hatványozást végez, nagy hatv´ anykitev˝ ovel és néh´ any szorzást, illetve hatványozást kis hatványkitev˝ ovel. A kulcskibont´ asi algoritmus egy moduláris hatványozást végez nagy hatványkitev˝ ovel és hasonl´ oan a kulcsbeágyazási algoritmushoz néhány szorzást, illetve hatv´ anyoz´ ast kis hatványkitev˝ovel. Az algoritmus futási ideje gyors´ıthat´ o a k´ınai maradéktétel alkalmazásával, ha megadjuk a P és Q pr´ımeket, mint bemeneti értékeket az algoritmusnak. Következésképpen a kulcskibontási algoritmus majdnem kétszer olyan gyors, mint a kulcsbe´ agyaz´ asi algoritmus, ami nagyon alkalmassá teszi az algoritmust olyan alkalmaz´ asok sz´ amára, ahol a szerver végzi a kulcskibontási folyamatot (mint ahogyan az általában történni szokott).

87

88

7. fejezet

Kulcsbeágyazási mechanizmusok implementáci´ oja Ebben a fejezetben t¨ obb CCA-biztonság´ u kulcsbeágyazási algoritmus implement´ aci´ oj´ at mutatjuk be, C++ programozási környezetben, illetve összehasonl´ıtjuk ezen rendszerek hatékonyságát, futási id˝oket mérve a kulcsgener´ al´ as, kulcsbe´ agyaz´ asi és kulcskibontási algoritmusok esetében. Konkrétan • • • • •

a Cramer–Shoup, a tov´ abbiakban mint CS-rendszer, az RSA–OAEP, az SAEP, a Hofheinz- és t´ arsai, a tov´ abbiakban mint HKS-rendszer, a 6. a fejezetben bemutatott kulcsbeágyazási mechanizmus implement´ aci´ oj´ ara tér¨ unk ki.

Kriptográfia rendszerek implement´ aciójával, pontosabban az RSA-titkos´ıtó implement´ aci´ oj´ aval funkcion´ alis programozási nyelvben a [46] cikkben is foglalkoztunk. Az eredményeket amelyeket itt tesz¨ unk közzé a következ˝o konfigurációj´ u géppel mért¨ uk, ahol a rendszer hardverkonfigurációja a következ˝o volt:

89

processzor: Intel(R)CoreTM i3-2310M 2.10GHz, a rendszer t´ıpusa: 64-bites oper´ aci´ os rendszer, RAM mem´ oriaméret: 4.00GB. A rendszer szoftverkonfigur´ aci´ oja: operációs rendszer: Windows 7 Enterprise, Service Pack 1, programoz´ asi k¨ ornyezet: Visual Studio 2010 Professional, Microsoft Visual C++ 2010. Az implement´ aci´ o sor´ an a k¨ ovetkez˝ o ny´ılt forráskód´ u programcsomagokat, könyvtárcsomagokat haszn´ altuk: • NTL, static library [58], • SHA1, SHA2, HMAC and Key Derivation in C [31], • Crypto++ [23]. A nagy sz´ amok ´ abr´ azol´ as´ ara és a vel¨ uk végzett aritmetikai m˝ uveletek elvégzésére, a Shoup ´ altal fejlesztett, NTL ny´ılt forráskód´ u könyvtárcsomagot haszn´ altuk. Az NTL magas hatékonyság´ u C++ könyvtárcsomag, amely lehet˝ ové teszi k¨ ulönböz˝o adatszerkezetek és algoritmusok alkalmaz´ as´ at tetsz˝ oleges nagys´ agrend˝ u egész számok, vektorok, mátrixok, polinomok esetében. A k¨ onyvt´ arcsomag könnyedén installálható Unix, Windows és Macintosh gépekre egyaránt. A tetsz˝oleges hossz´ uság´ u, el˝ojeles nagy sz´ amok ´ abr´ azol´ as´ ara haszn´ alt osztály a ZZ nevet viseli. Az osztály keretén bel¨ ul alkalmazhat´ oak az alapvet˝o aritmetikai m˝ uveletek, de a kriptográfi´ aban hasznos, komplexebb f¨ uggvények egy része is implementálva van, pl: pr´ımtesztelés, modul´ aris hatványozás, moduláris inverz meghatározás, stb. A rendszerek implement´ al´ asa sor´ an az SHA-256, illetve SHA-384 hash f¨ uggvények ker¨ ultek alkalmaz´ asra. A biztonság növelése érdekében ezen könnyedén lehet v´ altoztatni, nagyobb kimeneti értéket el˝oáll´ıtó SHA hash f¨ uggvényt alkalmazva. Megjegyezz¨ uk, hogy a jelenlegi standard követelmények a 256, illetve 384 bites kimenti hash értékeket megfelel˝onek tartják. A továbbiakban minden egyes rendszernél k¨ ulön felt¨ untetj¨ uk, hogy milyen nagyságrend˝ u kimeneti hash értékekkel dolgoztunk, azaz mikor alkalmaztuk az SHA-256, és mikor az SHA-384-es hash f¨ uggvényeket.

90

A hash f¨ uggvény ny´ılt forr´ askódja B. Gladman munkája, a hash f¨ uggvények hatékonys´ aga pedig a fejleszt˝o nyilvános weboldalán találhatóak meg [31]. A Cryptoo++ kriptogr´ afiai sémák implementálását tartalmazó C++ osztálykönyvt´ ar. A val´ os alkalmaz´ asok esetében használt kriptográfiai primit´ıvek szinte mindegyikét implementálták a fejleszt˝ok. Wei Dai kezdte el, napjainkban azonban t¨ obben is bekapcsolódtak a fejlesztésébe. Több platformon futtathat´ o, pl. MSVC 6.0-2012, GCC 3.3 - 4.7, stb. Az osztálykönyvt´ ar t¨ obb verzi´ oj´ at szabványként fogadta el a NIST. Az általunk implement´ alt rendszerek esetében az osztálykönyvtár primit´ıvei köz¨ ul az RSA–OAEP implement´ aci´ ot haszn´ altuk fel. A Cramer–Shoup-rendszer A CS rendszer implement´ al´ asa sor´ an a Z∗p ciklikus csoporttal dolgoztunk, ahol a p pr´ımsz´ am, alakja 2·q+1, ahol q szintén pr´ımszám. Ez a kitétel a generátor elemek meghat´ aroz´ as´ an´ al is fontos szerepet kap. A szakirodalom a p pr´ımet biztons´ agos (safe) pr´ımnek h´ıvja, a q pr´ımet pedig Sophie–Germainpr´ımnek. Az NTL k¨ onyvt´ arcsomag több olyan f¨ uggvénnyel rendelkezik, amely pr´ımeket gener´ al, A k¨ ovetkez˝o f¨ uggvény, amelynek három alakja is használhat´ o, egy l hossz´ us´ ag´ u Sophie–Germain pr´ımet generál, ahol annak a valósz´ın˝ usége, hogy sem a q, sem a 2·q +1 szám nem lesz összetett kisebb, mint 2−err : void GenGermainPrime(ZZ& q, long l, long err = 80); ZZ GenGermainPrime_ZZ(long l, long err = 80); long GenGermainPrime_long(long l, long err = 80); Biztons´ agos pr´ımek gener´ al´ asa id˝oigényes feladat, ahogy ez a mérési eredményekb˝ ol is leolvashat´ o, de sz´ amos rendszer biztonsága érdekében ez fontos követelmény. A kulcsgener´ al´ as id˝oigényét még az is lass´ıtja, hogy a titkos´ıtás sor´ an sz¨ ukség van két generátor elemre. A Z∗p ciklikus csoportban a generátor elem meghat´ aroz´ as´ at a következ˝o tulajdonságot figyelembe véve végezt¨ uk: egy g 6= ±1 (mod p) sz´ am akkor és csakis akkor lesz generátor elem (mod p) szerint, ha fenn´ all a következ˝o egyenl˝oség ([61], [59]): g q 6= 1 (mod p). 91

A két generátor elem meghat´ aroz´ asa érdekében el kell tehát végezni egy-egy moduláris hatv´ anyoz´ ast. A rendszerre vonatkoz´ o mérési eredmények a 7.1. táblázatban találhatóak, ahol a q nagys´ agrendje a kulcsméret oszlopban felt¨ untetett érték. A rendszer implement´ al´ asa sor´ an az NTL könyvtárcsomagot és B. Gladman SHA-256 hash f¨ uggvény implementációját használtuk fel. A ny´ılt szöveg egy véletlenszer˝ uen generált p-nél kisebb pozit´ıv egész szám lesz. Az RSA–OAEP-rendszer Az RSA–OAEP implement´ aci´ o, a standardként elismert Crypto++ könyvtárcsomag része. A kulcsgener´ al´ as egy n = p · q összetett számot határoz meg, ahol p, q nem lesz biztons´ agos-pr´ım, éppen ezért ennél az implementáción´ al a kulcsgener´ al´ as ideje j´ oval kisebb nagyságrend˝ u. A rendszerre vonatkoz´ o mérési eredmények a 7.2. táblázatból olvashatóak le. A ny´ılt szöveg egy véletlenszer˝ uen generált, 256 bites pozit´ıv egész szám lesz. Az SAEP rendszer A kulcsgenerálás egy n = p · q ¨ osszetett számot határoz meg, ahol p, q nem lesz biztonságos pr´ım. A rendszer azonban el˝o´ırja, hogy a p, q pr´ımekre fennálljon: p ≡ q ≡ 3 (mod 4), illetve, hogy az n = p · q összetett szám legfels˝obb helyérték˝ u két bitje 1, illetve 0 legyen. Ezek természetesen lass´ıtják a kulcsgenerálás id˝ oigényét. A rendszer implement´ al´ asa sor´ an az NTL könyvtárcsomagot és B. Gladman SHA-384 hash f¨ uggvény implementációját használtuk fel. A rendszerre vonatkoz´ o mérési eredmények a 7.3. táblázatban találhatóak. A ny´ılt szöveg egy véletlenszer˝ uen generált, 256 bites pozit´ıv, egész szám lesz. A véletlenszer˝ uen gener´ alt r érték (ahol az r szerepét a 5.2. fejezetben megadott SAEP rendszernél specifikáltuk) nagyságrendje aszerint fog változni, hogy mekkora k értékkel (kulcs mérettel) dolgozik az algoritmus. Fenn´ all, hogy r = k − 384, ahol a k a 7.3. táblázatban megadott kulcsméret.

92

A HKS rendszer A kulcsgener´ al´ as egy N = P · Q ¨ osszetett számot határoz meg, ahol P, Q biztonságos pr´ımek lesznek, azaz fennáll: P = 2 · p + 1, Q = 2 · q + 1 és p, q is pr´ımsz´ amok. A rendszer azt is el˝ o´ırja, hogy a P, Q pr´ımekre fennálljon: P ≡ Q ≡ 3 (mod 4). A kulcsgener´ al´ as id˝ oigényét lass´ıtja az is, hogy a P, Q értékek mellett további két értéket kell meghat´ arozni, az X-et és az α-t, ahol az X esetében sz¨ ukséges egy modul´ aris hatv´ anyoz´ as elvégzése. A rendszer implement´ al´ asa során az NTL könyvtárcsomagot és B. Gladman SHA-256 hash f¨ uggvény implementációját használtuk fel. A rendszerre vonatkoz´ o mérési eredmények a 7.4. táblázatban találhatóak. A kulcsbe´ agyaz´ asi algoritmus egy 256 bites hossz´ uság´ u kulcsot fog meghatározni. Az u ´j rendszer A kulcsgener´ al´ as egy N = P · Q ¨ osszetett számot határoz meg, ahol P, Q biztonságos pr´ımek lesznek, azaz fennáll: P = 2 · p + 1, Q = 2 · q + 1 és p, q is pr´ımsz´ amok. A rendszer azt is el˝ o´ırja, hogy a P, Q pr´ımekre fennálljon: P ≡ Q ≡ 3 (mod 4). A kulcsgener´ al´ as id˝ oigényét, az N értékének a meghatározása mellett az is befoly´ asolja, hogy sz¨ ukséges további két érték meghatározása: az X és az α el˝ o´ all´ıt´ asa. Az X esetében sz¨ ukséges egy moduláris hatványozás elvégzése, kisebb hatv´ anykitev˝ ovel, mint a HKS rendszer esetében. A titkos´ıt´ as és visszafejtés id˝ oigényét a moduláris hatványozáshoz sz¨ ukséges exponens nagys´ agrendje határozza meg, ami az u ´j rendszer esetében kisebb nagys´ agrend˝ u lesz, mint a HKS rendszer esetében. Az u ´j rendszer implement´ al´ asa során az NTL könyvtárcsomagot és B. Gladman SHA-256 hash f¨ uggvény implementációját használtuk fel. A rendszerre vonatkoz´ o mérési eredmények a 7.5. táblázatban találhatóak. A kulcsbe´ agyaz´ asi algoritmus egy 256 bites hossz´ uság´ u kulcsot fog meghatározni. A 7.1, 7.2, 7.3, 7.4, 7.5. t´ abl´ azatokban található mérési eredmények 20 bemeneti adat ´ atlag´ anak az értékét mutatják, ahol a kulcsméret bitben, a kulcsgener´ al´ as, a titkos´ıt´ as és a visszafejtés ideje másodpercben ker¨ ult meghatároz´ asra. 93

7.1. tábl´ azat. A Cramer–Shoup-rendszer mérési eredményei kulcsméret kulcsgener´ al´ as titkos´ıtás visszafejtés 256 0.21 0 0.01 512 4.30 0.04 0.05 1024 50.47 0.24 0.26

7.2. tábl´ azat. Az RSA–OAEP-rendszer mérési eredményei kulcsméret kulcsgener´ al´ as titkos´ıtás visszafejtés 512 0.02 0 0 1024 0.07 0 0 2048 0.31 0 0.01 4096 2.55 0 0.04

7.3. t´ abl´ azat. Az SAEP-rendszer mérési eredményei kulcsméret kulcsgener´ al´ as titkos´ıtás visszafejtés 512 0.15 0 0 1024 2.07 0 0.01 2048 11.30 0 0.09

7.4. t´ abl´ azat. A HKS-rendszer mérési eredményei kulcsméret kulcsgener´ al´ as titkos´ıtás visszafejtés 512 0.40 0.04 0.02 1024 8.07 0.11 0.11 2048 131.33 0.68 0.53

7.5. táblázat. Az u ´j CCA-biztons´ ag´ u rendszer mérési eredményei kulcsméret kulcsgener´ al´ as titkos´ıtás visszafejtés 512 0.39 0.02 0.01 1024 8.13 0.09 0.06 2048 125.59 0.66 0.44 94

8. fejezet

¨ Osszefoglal´ o Jelen értekezés a titkos´ıt´ o rendszerek választott ny´ılt szöveg alap´ u támadással (chosen plaintext attack), illetve választott rejtjelezett szöveg alap´ u t´ amad´ assal (chosen ciphertext attack) szembeni biztonságát tárgyalta. A választott téma aktualit´ as´ at az adja, hogy a létez˝o titkos´ıtó rendszerek átalak´ıt´ asa oly m´ odon, hogy azok ellenálljanak a választott rejtjelezett szöveg t´ıpus´ u t´ amad´ asnak a jelen kriptográfia akt´ıv kutatási ter¨ uletét képezik ([6], [7], [13], [20], [35]). Az értekezés els˝ o felében megadtuk a témához kapcsolódó értelmezések és tételek form´ alis defin´ıci´ oit, és mivel a tárgyalt fogalmakhoz nincsen széles körben elfogadott magyar terminológia fokozottan oda figyelt¨ unk ezek prec´ız, magyar megfogalmaz´ as´ ara. Konkrétan a következ˝o fogalmakkal foglalkoztunk: • a szimmetrikus titkos´ıt´ asi rendszerek matematikai modelljével, a passz´ıv és akt´ıv t´ amad´ oval szembeni biztonság fogalmakkal, ahol az akt´ıv t´ amad´ oval szembeni biztonság esetében k¨ ulönbséget tett¨ unk a választott ny´ılt-sz¨ oveg alap´ u, illetve a választott rejtjelezett-szöveg alap´ u t´ amad´ asok k¨ oz¨ ott, • a hash f¨ uggvényekkel és u ¨zenethiteles´ıt˝o kódokkal szembeni követelményekkel, kihangs´ ulyozva az univerzális hash f¨ uggvények (universal hash function), a cél u ¨tközésmentes hash f¨ uggvények (target 95

collision-resistant hash function) és az u ¨tközésmentes hash f¨ uggvények (collision-resistant hash function) k¨ ozötti k¨ ulönbségeket, • az aszimmetrikus titkos´ıt´ o rendszerek matematikai modelljével, a választott ny´ılt-sz¨ oveg alap´ u, illetve a választott rejtjelezett-szöveg alap´ u támad´ ashoz kapcsol´ od´ o biztonságértelmezésekkel, • a hibrid rendszerek matematikai modelljével és a választott rejtjelezett-sz¨ oveg alap´ u t´ amadáshoz kapcsolódó biztonság értelmezésével. Az értekezés tov´ abbi részében azokat a matematikai problémákat tárgyaltuk amelyek alapj´ aul szolg´ alnak a mai biztonságos kriptorendszereknek, és amelyeket a szakirodalomban feltételezések formájában fogalmaztak meg. Jelen értekezésben a k¨ ovetkez˝ o feltételezések formális defin´ıcióit adtuk meg ([18], [24], [36]): • • • • •

faktorizáci´ os feltételezés, RSA feltételezés, kvadratikus maradék feltételezés, diszkrét logaritmus feltételezés, döntési Diffie–Hellman-feltételezés.

Ezek után megadtunk egy u ´j kulcsbeágyazási mechanizmus CPA, illetve CCA-biztons´ ag´ u verzi´ ot. Megjegyezz¨ uk, hogy az u ´j kulcsbeágyazási mechanizmus alapj´ aul a Rabin-titkos´ıt´ o [54] és a Hofheinz és társai [35], által szerkesztett rendszerek szolg´ altak. A CCA-biztonság´ u kulcsbeágyazási mechanizmus a [48] cikkben ker¨ ult publikálásra. Az értekezés keretén bel¨ ul megadtuk az u ´j kulcsbeágyazási mechanizmus specifik´ aci´ oj´ at, helyességét, hatékonyságát, illetve bizony´ıtottuk a rendszer biztons´ ag´ at. Kitért¨ unk még a szakirodalom által számon tartott CCA-biztons´ ag´ u kulcsbe´ agyaz´ asi mechanizmusok specifikációira, összehasonl´ıtva ezen rendszereket, hatékonyság szempontjából, az u ´j kulcs beágyazási mechanizmus hatékonys´ ag´ aval. Megadtuk C++ programozási környezetben a rendszerek mindegyikének implementációját, futási id˝oket mérve a megfelel˝ o algoritmusok esetében. Az implement´ aci´ o k´ odja let¨ olthet˝ o a következ˝o c´ımr˝ol: http://www. ms.sapientia.ro/~mgyongyi/PhD/PhdSource.zip 96

A tárgyalt rendszerek a k¨ ovetkez˝oek voltak, ahol vizsgáltuk az eredeti titkos´ıtó rendszert, és annak CCA-biztonság´ u verzióját: • • • •

az ElGamal- és Cramer–Shoup-rendszer ([27], [20]), az RSA- és RSA–OAEP-rendszer ([55], [6]), a Rabin- és SAEP-rendszer ([54], [14]), a Blum–Goldwasser és Hofheinz- és társai rendszere ([12], [35]).

Megjegyezz¨ uk, hogy: • A Cramer–Shoup-rendszer biztonsága a döntési Diffie–Hellmanfeltételezésen és az alkalmazott hash f¨ uggvény u ¨tközésmentes tulajdons´ ag´ an alapszik. • Az RSA–OAEP-rendszer biztonsága az RSA feltételezésen és az alkalmazott véletlenszer˝ u hash f¨ uggvény u ¨tközésmentes tulajdonságán alapszik. • Az SAEP-rendszer biztons´ aga a faktorizációs feltételezésen és az alkalmazott véletlenszer˝ u hash f¨ uggvény u ¨tközésmentes tulajdonságán alapszik. • A Hofheinz- és t´ arsai kulcsbe´ agyazási mechanizmusa a faktorizációs feltételezésen és az alkalmazott hash f¨ uggvény u ¨tközésmentes tulajdons´ ag´ an alapszik. • Az u ´j kulcsbe´ agyaz´ asi mechanizmus biztonsága a faktorizációs feltételezésen és az alkalmazott hash f¨ uggvény u ¨tközésmentes tulajdons´ ag´ an alapszik. Az u ´j kulcsbe´ agyaz´ asi mechanizmus biztonságát, az u ´jabb szakirodalomban haszn´ alt bizony´ıt´ asi m´ odszer alapján adtuk meg, amely szerint definiálni kell egy k´ısérletet, amely egy polinomiális idej˝ u, probabilisztikus támad´ o és a k¨ ornyezete, a kih´ıv´ o között játszódik le. A CCA-biztonság a k´ısérlet lehetséges kimeneti értékeinek a vizsgálatával bizony´ıtható. Következtetésképpen az u ´j kulcsbeágyazási mechanizmusról elmondhatjuk, hogy biztons´ agos, hatékonyság szempontjából pedig nem marad alul a jelenleg standardként haszn´ alt rendszerekhez képest. Fontosnak tartjuk azt is megeml´ıteni, hogy az u ´j kulcsbeágyazási mechanizmussal széles´ıtett¨ uk a CCA-biztonság´ u kulcsbeágyazási mechanizmusok terét. 97

98

9. fejezet

Summary This thesis examines the security of encryption systems, it focuses mainly on two types of attacks on chosen plaintext attack and chosen ciphertext attack. The importance of the chosen topic relies in the fact that transforming encryption systems so as to be secure against chosen ciphertext attack in cryptography is an active research field ([6], [7], [13], [20], [35]). In the first half of the the thesis we give the formal definitions of the concepts used in the dissertation. Namely we introduce the followings: • the mathematical model of symmetric encryption systems, the formal definition of security against passive and active attack where, in the case of active attack, we make a distinction between chosen plaintext attack and chosen ciphertext attack, • the hash functions and message authentication codes and the requirements on them, highlighting the differences between universal hash function, target collision resistant hash function and collision resistant function, • the mathematical model of asymmetric encryption systems, the formal definition of security against chosen plaintext attack and chosen ciphertext attack, • the mathematical model of hybrid encryption systems, the formal definition of security against chosen ciphertext attack. 99

We mention that in most of the protocols asymmetric encryptions are used to generate and interchange the keys of two remote parties. And for the encryption of actual data symmetric encryption technics are used. The newer literature introduces key-encapsulation, respectively the dataencapsulation terms for these. In the next chapter we introduce the mathematical problems that are the basis of many cryptosystems and are known in cryptography as basic assumptions. We give the formal definition of the following basic assumptions ([18], [24], [36]): • • • • •

factorization assumption, RSA assumption, quadratic residuosity assumption, discrete logarithm assumption, decisional Diffie–Hellman-assumption.

Consequently we describe the main result of the dissertation, the CPA and CCA version of a new key encapsulation mechanism. We mention that the mechanism is based on Rabin-encryption [54] and on the system constructed by Hofheinz et al [35]. The new CCA-secure key encapsulation mechanism was published in [48]. Within the framework of the thesis we give a detailed description of the proposed mechanism, we present its soundness and efficiency as well as the proof of security. We present some CCA-secure key encapsulation mechanisms, which are considered important in the recent area of cryptography, and we compare these systems with the new key encapsulation mechanism. We give the C++ implementations of the systems and we measure the running times of the corresponding algorithms. The implementation can be downloaded from the following address: http://www.ms.sapientia.ro/~mgyongyi/PhD/PhdSource.zip The asymmetric encryption systems and the corresponding CCA-secure versions of them implemented are the following: • the ElGamal, and Cramer–Shoup system ([27], [20]), • the RSA and RSA–OAEP system ([55], [6]), • the Rabin and SAEP system ([54], [14]), 100

• the Blum–Goldwasser and HKS system ([10], [35]). We mention the following: • The security of the Cramer–Shoup-cryptosystem relies in the decisional Diffie–Hellman-assumption and the collision-resistant properties of the underlying hash function. • The security of the RSA–OAEP-scheme relies in the RSA assumption and in the security of hash functions maintained as a random oracle. • The security of the SAEP-system depends on the factorization assumption and on the security of hash functions maintained as a random oracle. • The security of the HKS key encapsulation mechanism relies in the factorization assumption and the underlying target collision-resistant hash function. • The security of the new key encapsulation mechanism relies in the factorization assumption and the underlying target collision-resistant hash function. The security proof of the new key encapsulation mechanism given in the thesis is based on the proof technic used in the recent literature. So we define an experiment going on between a probabilistic polynomial time adversary and his environment, called a challenger. The CCA-security can be proved by examining the possible outputs of the experiment. Consequently, the new key encapsulation mechanism is secure and in terms of efficiency does not lag behind the systems accepted as standard. It is important to mention that the new key encapsulation mechanism broadens the space of CCA-secure key encapsulation mechanisms.

101

102

Irodalomjegyzék [1] M. Abdalla, M. Bellare, and P. Rogaway. The Oracle Diffie-Hellman Assumptions and an Analysis of DHIES. Topics in Cryptology - CTRSA 2001, LNCS 2020, pages 143–158, 2001. [2] M. Ajtai and C. Dwork. A public-key cryptosystem with wortscase/awerage-case equivalence. In STOC ’97 (El Paso, TX), ACM (electronic), pages 284–293, 1999. [3] A. Bege and Z. K´ asa. Algoritmikus kombinatorika és sz´ amelmélet. Presa Universitar˘ a Clujean˘ a, 2006. [4] M. Bellare, R. Canetti, and H. Krawczyk. Keying hash functions for message authentication. Advances in Cryptology, CRYPTO ’96, 1996. [5] M. Bellare and P. Rogaway. Random oracles are practical: A paradigm for designing efficient protocols. Proceedings of 1st ACM Conference on Computer and Communications Security, pages 62–73, 1993. [6] M. Bellare and P. Rogaway. Optimal Asymmetric Encryption. Advances in Cryptology, EUROCRYPT ’94, pages 92–111, 1994. [7] M. Bellare and P. Rogaway. Introduction to Modern Cryptography. 2005. [8] D.J. Bernstein. The salsa20 family of stream ciphers. http://cr.yp.to/snuffle/salsafamily-20071225.pdf.

103

[9] D. Bleichenbacher. Chosen Ciphertext Attacks Against Protocols Based on the RSA encryption Standard PKCS#1. Advances in Cryptology, Proceedings of CRYPTO ’98, pages 1–12, 1998. [10] L. Blum, M. Blum, and M. Shub. Comparison of two pseudo-random number generators. Advances in Cryptology, Proceedings of CRYPTO ’82, pages 61–78, 1982. [11] M. Blum, P. Feldman, and S. Micali. Proving Security Against Chosen Ciphertext Attacks. Advances in Cryptology, Proceedings of CRYPTO ’88, pages 256–268, 1984. [12] M. Blum and S. Goldwasser. An effcient probabilistic public-key encryption scheme which hides all partial information. Advances in Cryptology, Proceedings of CRYPTO ’84, pages 289–302, 1985. [13] D. Boneh. Twenty Years of attacks on the RSA cryptosystem. Notices of the American Mathematical Society, 46 (2):203–213, 1999. [14] D. Boneh. Simplified OAEP for the RSA and Rabin functions. Lecture Notes in Computer Science, Proceedings of CRYPTO ’01, 213:275–291, 2001. [15] A. Bérczes, J. Foll´ ath, and A. Peth˝o. On a family of collision-free functions. Tatra Mountains Mathematical Publications, 47:1–13, 2010. [16] A. Bérczes, J. K¨ odm¨ on, and A. Peth˝o. A one-way function based on norm form equations. Periodica Mathematica Hungarica, 49:1–13, 2004. [17] J.A. Buchmann. Introduction to cryptography. Springer, 2002. [18] L. Buttyán and T. Vajda. Kriptogr´ afia és alkalmaz´ asai. Typotex, 2004. [19] D. Coppersmith. Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities. Journal of Cryptology, 10 (4):233–260, 1997.

104

[20] R. Cramer and V. Shoup. A practical practical public-key cryptosystem provably secure against adaptive chosen ciphertext attack. Advaces in Cryptology, Proceedings of CRYPTO ’98, 33:13–25, 1998. [21] R. Cramer and V. Shoup. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM Journal of Computing, pages 167–226, 2003. [22] J. Daemen and V. Rijmen. The Block Cipher Rijndael. Proceedings of the The International Conference on Smart Card Research and Applications, pages 277–284, 2000. [23] W. Dai. Crypto++ Library. http://www.cryptopp.com/. [24] H. Delfs and H. Knebl. Introduction to cryptography. Principles and Applications. Springer, 2002. [25] W. Diffie and M.E. Hellman. New Directions in Cryptography. IEEE Transactions on Information Theory, IT–22:644–654, 1976. [26] Y. Dodis and J. Katz. Chosen-Ciphertext Security of Multiple Encryption. 3378:188–209, 2005. [27] T. ElGamal. A Public-Key Cryptosystem and a Signatures Scheme Based on Discrete Logarithms. IEEE Transactions on Information Theory, IT–31:469–472, 1985. [28] S.R. Fluhrer, I. Mantin, and A. Shamir. Weaknesses in the Key Scheduling Algorithm of RC4. Proceeding SAC ’01 Revised Papers from the 8th Annual International Workshop on Selected Areas in Cryptography, pages 1–24, 2001. [29] J. Foll´ ath, A. Huszti, and A. Peth˝o. Informatikai biztons´ ag és kriptogr´ afia. 2010. http://www.inf.unideb.hu/∼pethoe/Jegyzet PA 20110508.pdf. [30] R. Freud and E. Gyarmati. Sz´ amelmélet. Nemzeti Tankönyvkiadó, 2000. 105

[31] B. Gladman. SHA1, SHA2, HMAC and Key Derivation in C. http://gladman.plushost.co.uk/oldsite/cryptography technology/sha. [32] S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270–299, 1984. [33] L. Goubin, C. Mauduit, and A. S´ ark¨ ozy. Construction of large families of pseudorandom binary sequences. J. Number Theory, 106:59–69, 2004. [34] J. Hastad. On using RSA with Low Exponent in a Public Key Network. CRYPTO ’85 Advances in Cryptology, pages 403–408, 1985. [35] D. Hofheinz, E. Kiltz, and V. Shoup. Practical Chosen Ciphertext Secure Encryption from Factoring. Journal of Cryptology, Online FirstT M , 2011. [36] J. Katz and Y. Lindell. Introduction to Modern Cryptograhy. Chapman & HallCRC Press, 2008. [37] A. Kerckhoffs. La cryptographie militaire. Journal des sciences militaires, IX:5–38, 1883. [38] N. Koblitz and A. J. Menezes. A survey of public-key cryptosystems. SIAM Review, 46:599–634, 2004. [39] L. Lovász. Algoritmusok bonyolults´ aga. Nemzeti Tankönyvkiadó, 2001. [40] A. J. Menezes, P. C. van Oorschot, and S.A. Vanstone. Handbook of applied cryptography. CRC Press, Boca Raton, Florida, 1997. [41] R. C. Merkle. A fast software one-way hash function. Journal of Cryptology, 3:43–48, 1990. [42] R. C. Merkle and M. Hellman. Hiding information and signatures in trapdoor knapsacks. Information Theory, IEEE Transactions, 24 (5):525–530, 1978.

106

[43] S. Micali, C. Rackoff, and B. Sloan. The notion of security for probabilistic cryptosystems. SIAM Journal on Computing, pages 412–426, 1988. [44] Gy. M´ arton. Kriptogr´ afiai alapismeretek. Scientia Kiadó, 2008. [45] Gy. M´ arton. Nyilv´ anos kulcs´ u kriptorendszerek biztonságához kapcsolod´ o értelmezések. Sz´ amokt 2010 konferenciak¨ otet, 20. Nemzetk¨ ozi sz´ am´ıt´ astechnika és oktat´ as konferencia, pages 183–187, 2010. [46] Gy. M´ arton. Public-key cryptography in functional programming context. Acta Universitatis Sapientiae, Informatica, 2:99–111, 2010. ¨ [47] Gy. M´ arton. Uzenethiteles´ ıt˝ o k´ odok és a CCA támadás. Sz´ amokt 2011 konferenciak¨ otet, 21. Nemzetk¨ ozi sz´ am´ıt´ astechnika és oktat´ as konferencia, pages 229–233, 2011. [48] Gy. M´ arton. CCA-secure key-encapsulation mechanism based on the factoring assumption. Tatra Mountains Mathematical Publications, 53:137–146, 2012. [49] Gy. M´ arton. A faktoriz´ aci´ os problémán alapuló titkos´ıtó rendszerek biztons´ aga. Sz´ amokt 2012 konferenciak¨ otet, 22. Nemzetk¨ ozi sz´ am´ıt´ astechnika és oktat´ as konferencia, pages 314–315, 2012. [50] M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attack. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 427–437, 1990. [51] A. M. Odlyzko. Discrete logarithms: The past and the future. Designs, Codes, and Cryptography, 19:129–145, 2000. [52] B. Preneel. Analysis and Design of Cryptographic Hash Function. PhD thesis, Katholieke Universiteit Leuven. [53] B. Preneel. The state of cryptographic hash functions. Lecture Notes in Computer Science, 1561:158–182, 1999.

107

[54] M. O. Rabin. Digitalized Signatures and Public-Key Functions as Intractable as Factorization. MIT Laboratory for Computer Science LCS/TR-212, 1979. [55] R.L. Rivest, A. Shamir, and L.M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21 (2):120–126, 1978. [56] L. Rónyai, G. Ivanyos, and R. Szab´ o. Algoritmusok. Typotex, 2004. [57] A. Shamir. A polynomial-time algorithm for breaking the basic Merkle - Hellman cryptosystem. Information Theory, IEEE Transactions, 30 (5):699–704, 1984. [58] V. Shoup. A library for doing number theory. http://www.shoup.net/ntl/. [59] V. Shoup. Searching for primitive roots in finite fields. Mathematics of Computation, 58:369–380, 1992. [60] W. Stallings. Cryptography and Network Security. Principles and Practice. Prentice Hall, 2010. [61] D. R. Stinson. Cryptography. Theory and Practice. HallCRC Press, 2006.

Chapman &

[62] U.V. Vazirani and V. Vazirani. Efficient and secure pseudo-random number generation. Advances in cryptology, Proceedings of CRYPTO 84, pages 193–202, 1985. [63] G.S. Vernam. Cipher printing telegraph systems for secret wire and radio telegraphic communications. Journal of the IEEE, 55:109–115, 1926. [64] V. Villányi. RSA signatures schemes with sublimal-free public-key. Tatra Mountains Mathematical Publications, 41:19–32, 2008. [65] M.J. Wiener. Cryptanalysis of short RSA secret exponents. Information Theory, IEEE Transactions, 36 (3):553–558, 1990. 108

[66] M.J. Wiener. Safe prime generation with a combined sieve. Crypto Eprint Archive entry 2003: 186, 2003.

109

110

A f¨ uggelék

Referált nemzetk¨ ozi foly´ oiratban megjelent cikkek ´ 1. MARTON Gy¨ ongyvér: Public-key cryptography in functional programming context, Acta Universitatis Sapientiae Informatica, vol 2. Nr. 1, 2010, 99-112, ISSN 1844-6086 [Zbl 1197.68043] ´ ´ ´ ´ 2. KATAI Zolt´ an, KOVACS Lehel István, KASA Zoltán, MARTON Gyöngyvér, FOGARASI Kinga and FOGARASI Ferenc: Cultivating algorithmic thinking: an important issue for both technical and HUMAN sciences, Teaching Mathematics and Computer Science, 2011, 9/1. [Zbl MathEduc 2012a.00772] ´ 3. MARTON Gy¨ ongyvér: CCA-secure key-encapsulation mechanism based on factoring assumption, Tatra Mountains Mathematical Publications, vol 53, 2012, 137–146, ISSN 1210-3195 [Zbl 06135378]

111

112

B f¨ uggelék

Lektorált egyetemi jegyzet ´ 1. MARTON Gy¨ ongyvér: Fundamentals of cryptography (in Hungarian), Sapientia-EMTE, Scientia, Cluj-Napoca, 2008, ISBN 978-9731970-00-4

113

114

C f¨ uggelék

Tudományos konferencia k¨ otetben megjelent cikkek ´ 1. MARTON Gy¨ ongyvér, The security of electronic voting, Proceedings of Sz´ amokt 2007, 17th International Conference on Computers and Education, Oradea (Nagyv´ arad), Romania, 2007, ISSN 1842-4546. ´ 2. MARTON Gy¨ ongyvér, Recursion, dynamic programming, functional programming, Proceedings of Számokt 2008, 18th International Conference on Computers and Education, Sumuleu Ciuc (Cs´ıksomlyó), Romania, 2008, ISSN 1842-4546. ´ 3. MARTON Gy¨ ongyvér, Methods and tools for teaching cryptography, Proceedings of Infodidact 2009, 2th Methodological Conference on Informatics, Szombathely, Hungary, 2009. ´ 4. MARTON Gy¨ ongyvér, Eligible problems in cryptography, Proceedings of Sz´ amokt 2009, 19th International Conference on Computers and Education, Tg. Mures (Marosvásárhely), Romania, 2009, ISSN 1842-4546.

115

´ 5. MARTON Gy¨ ongyvér, Definitions related to the security of publickey cryptosystems, Proceedings of Számokt 2010, 20th International Conference on Computers and Education, Satu-Mare (Szatmárnémeti), Romania, 2010, ISSN 1842-4546. ´ 6. MARTON Gy¨ ongyvér, Message authentication codes and CCAattack, Proceedings of Sz´ amokt 2011, 21th International Conference on Computers and Education, Cluj-Napoca (Kolozsvár), Romania, 2011, ISSN 1842-4546. ´ 7. MARTON Gy¨ ongyvér, Security of Encryption Systems based o Factoring Assumptions, Proceedings of Számokt 2012, 22th International Conference on Computers and Education, Alba-Julia (Gyulafehérvár), Romania, 2012, ISSN 1842-4546

116

D f¨ uggelék

Tudományos konferenciákon elhangzott el˝ oadások ´ 1. MARTON Gy¨ ongyvér: Functional programming and cryptography, ”The day of science in Transylvania” conference, Miercurea Ciuc, Romania, 2006. ´ 2. MARTON Gy¨ ongyvér: Experience in teaching functional programming, ”MINICONF” conference, Tg-Mures, Romania, 2007. ´ 3. MARTON Gy¨ ongyvér: The role of functional programming in cryptography, Central European Functional Programming School, Cluj Napoca, Romania, 2007. ˝ ´ 4. GYORFI Eugen, MARTON Gyöngyvér: Algebra of the 2D and 3D Cutting/Packing patterns, 6th ESICUP international conference, Valencia, Spain, 2009. ´ 5. MARTON Gy¨ ongyvér: Cryptography based on problems of graph theory, 1st ”Sapientia MatInfo” International Conference, Tg.Mures, Romania, 2009.

117

´ 6. MARTON Gy¨ ongyvér: Technics used in cryptosystems to achieve CCA-security, 2nd ”Sapientia MatInfo” international conference, Tg.Mures, Romania, 2011. ´ 7. MARTON Gy¨ ongyvér: Remarks on Blum-Goldwasser public-key encryption system, 11th Central European Conference on Cryptology, Debrecen, Hungary, 2011. ´ 8. MARTON Gy¨ ongyvér: Chosen ciphertext security of public-key encryption systems, 9th Joint Conference on Mathematics and Computer Science, Si´ ofok, Hungary, 2012. ´ 9. MARTON Gy¨ ongyvér: CCA-secure key-encapsulation mechanism based on the factoring assumption, 12th Central European Conference on Cryptology - TatraCrypt, Smolenice, Slovakia, 2012.

118

E f¨ uggelék

K¨ osz¨ onetnyilván´ıtások Ez´ uton szeretném megk¨ osz¨ onni mindazon személyeknek a seg´ıtségét, akik közvetlen¨ ul vagy k¨ ozvetett módon hozzájárultak PhD értekezésem elkész´ıtéséhez. ´ Köszönöm Dr. Peth˝ o Attila Tan´ ar Urnak, hogy témavezet˝om volt, hogy számos alkalommal seg´ıtette tudományos munkámat u ´gy szakmai szigor´ usággal, mint erk¨ olcsi és anyagi támogatással. Köszönöm a Sapientia Egyetem vezet˝oségének és a Matematika-Informatika Tanszék tan´ arainak azt a kitart´ o bizalmat mellyel az elm´ ult években, mint kollégák t´ amogatt´ ak tudom´ anyos tevékenységemet. Köszönöm a Debreceni Egyetemnek, hogy biztos´ıtotta számomra a tand´ıjmentességet a Doktori Iskola levelez˝o programjának keretén bel¨ ul. Köszönöm a Kutat´ asi Programok Intézetének (Kolozsvár) azon anyagi ¨ ond´ıjprogram keretén bel¨ támogatást, amelyet a Sapientia Doktori Oszt¨ ul ny´ ujtott sz´ amomra. Köszönöm csal´ adomnak azt a felel˝ osségteljes hozzáállást mellyel seg´ıtették ezen értekezés elkész¨ ulését. 119

Titkosítási rendszerek CCA-biztonsága

Recommend Documents