Informatika | Informatikai biztonság » Wettl Ferenc - Asszimetrikus nyílt kulcsú titkosítás

Aszimmetrikus (nyílt) kulcsú titkosítás Wettl Ferenc 2014-06-25 1 Tartalomjegyzék Jelölések 4 Bevezetés 5 1. Elméleti alapok 6 1.1 Algoritmikus számelméleti alapok . Euklideszi algoritmus . Z� Z*� és a moduláris hatványozás 8 és a moduláris inverz . 11 A modern kriptográa alapja, a bizonyítható biztonság 15 17 . . 18 Az aszimmetrikus rejtjelez® és biztonsága . 20 Makacs számelméleti problémák . 23 Faktorizáció . 23 . 24 Négyzetgyökvonás, a Rabin-probléma . 26 Diszkrét logaritmus . 27 DieHellman-problémák . 28 . 31 Egyirányú függvény a faktorizációs problémából . 33 Az RSA-függvény . 33 Moduláris négyzetre emelés, a Rabin-függvény . 33 Diszkrét logaritmus . 34

DieHellman függvény 34 Egyirányú kiskapufüggvények . Kriptográai hash függvények 1.5 12 14 Számítási biztonság  gyakorlati megközelítés Moduláris gyökvonás, az RSA-probléma 1.4 . Tökéletes biztonság . Számítási biztonság  aszimptotikus megközelítés 1.3 6 . Kínai maradéktétel . 1.2 6 . 34 A DieHellman hash függvény . 36 Támadások az RSA-függvény ellen . 36 kicsi . 37 közös üzenettel . 37 Hastad támadása . 37 Amikor Kis � Amikor Amikor � � kicsi . � kicsi  gyökös támadás Közös modulus . 38 . 39 . 39 2 Megváltoztathatóság . Implementációk elleni támadások 1.6 . 40 Ciklikus csoportok az elliptikus görbéken . 41

Elliptikus görbék . 42 A végtelen távoli pont: an és projektív koordináták . 42 Pontm¶velet az elliptikus görbén . 45 Az elliptikus görbe csoport . 47 Er®s és biztonságos prímek . 49 2. A nyílt kulcsú titkosítás alapfogalmai 2.1 40 50 El®zmények, kezdetek . Merkles puzzle . 50 50 Die-Hellman kulcscsere . 50 2.2 Aszimmetrikus rejtjelez® egyirányú kisk.-permutációból 52 2.3 OAEP  Optimal Asymmetric Encryption Padding 2.4 Hibrid rejtjelez®k Véletlen orákulum . 57 . 60 3. Nyílt kulcsú rejtjelezők 3.1 3.2 RSA 62 . 62 RSA rejtjelez® . 62 CCA-biztonságú RSA . 62 . 66 ElGamal és ECC Az ElGamal rejtjelez® . Csoport generálása az

ElGamal számára 3.3 54 . . 66 67 Elliptikus görbére épül® rejtjelez® . 68 Összehasonlítások . 71 3 Jelölések � mod � � ≡ � (mod � ) Z� az Z*� az az az � egész � -nel való osztási maradéka � és � egészek � -nel való osztási maradéka azonos � -nel való osztás maradékosztályainak additív csoportja (vagy gy¶r¶je) � -hez relatív prímek maradékosztályainak multiplikatív csoportja GF(�), F� F� [�] F� [�]� 1� � elem¶ véges test F� feletti polinomok gy¶r¶je � -nél kisebb fokú F� feletti polinomok � csupa 1-esb®l álló bitlánc, általában a biztonsági paramé- ter átadására |�| ℓ(�) exp(�, �, � ) inv(�, � ) log, ln log� � az az � � karakterlánc hossza bináris ábrázolásban szám bináris alakjában a számjegyek száma � moduláris hatványozás, értéke � mod � −1 moduláris

inverz, értéke � mod � 2-es és természetes alapú logaritmus diszkrét logaritmus, � = �� (ciklikus csoport- kulcsgenerátor, függvénygenerá- log� � = �, ha ban) � � RSA � mod � group � prime E� D� Expxx �,� Advxx �,� generátorfüggvény RSA paramétergenerátor két prím szorzatát generáló algoritmus (� prímet generáló algoritmus a � kulccsal rejtjelez®/kódoló függvény (encoding ) dekódoló függvény (decoding ) kísérlet (experiment ): � támadja � -t az xx cél/feltétel/körülmény mellett az � támadó el®nye a � (algoritmus/kriptorendszer/. ) xx cél/feltétel/körülmény mellett egy véletlen � elem választása az értékadás, melyben � � halmazból értéke egy véletlen algoritmus eredmé- nye � = � (�) ‖ ⊕ = �� ) ciklikus csoportot generáló algoritmus ellen az �←� � ← � (�) (pl. tor,. ) értékadás determinisztikus

� függvénnyel az összef¶zés (konkatenáció) m¶velete bitenkénti XOR m¶velet 4 Bevezetés E jegyzet célja, hogy a nyilt kulcsú titkosítás ma használt, és használatra ajánlható típusait, és az azokkal kapcsolatos biztonsági kérdéseket, mindenekel®tt a bizonyítható biztonság kérdéseit áttekintse, és a felhasználás szempontjai szerint értékelje. A kriptográa történetében mérföldk®nek számít a nyilvános vagy nyílt kulcsú rejtjelezés 70-es évekbeli föltalálása. Ebben az üzenet titkosítása olyan kulccsal történik, melynek megszerzése nem jelent segítséget a támadónak, olyannyira nem, hogy akár nyilvánosságra is lehet hozni. A rejtjelezett üzenet visszafejtése ugyanis másik kulccsal történik. Els® alkalmazói a titkosszolgálatok voltak, a kémeknek adott kulcs ellenséges területen való használata nem jelentett biztonsági kockázatot, csak a kémközpontban ®rzött titkos kulcsra kellett vigyázni. A nyílt

kulcsú rejtjelezés ötletét Kerckhos elvének kiterjesztéseként is felfoghatjuk. Az ® XIX. században megfogalmazott elve az volt, hogy a titkosítás módja nem lehet a titok része, nem okozhat veszélyt, ha azt az ellenség megszerzi, így akár teljesen nyilvános is lehet. A 80-as évekt®l kezd®d®en a kriptográában több további forradalmi változás történt. ∙ Korábban a kriptográa f® alkalmazói a katonai biztonsági szervezetek, a szerelmes párok és a magányos naplóírók voltak. Mára a kommunikáció formáinak radikális megsokszorozódása  legf®képpen az internet kialakulása  után a kriptográa eszközeinek használata általánossá, és mindannyiunk életét nem elhanyagolható módon befolyásoló tényez®vé vált. ∙ Korábban a kriptográa alkalmazása a titkos üzenetküldésre szorítkozott, a kriptográa csak minél feltörhetetlenebbnek hitt rejtjelez®k kitalálásából, és megszerzett titkos üzenetek

feltöréséb®l állt. Mára a kriptográa az adatkezelésnek egy lényegesen szélesebb körét öleli fel. Egyrészt nem csak a titkosság meg®rzése, de a küld® azonosíthatósága, az üzenet sértetlensége, hitelessége, az elküldött üzenet utólagos letagadhatatlansága is a kívánalmak közé került. Másrészt számtalan új protokoll jelent meg a kriptográában. felsorolunk néhányat: – titokmegosztás, 5 A teljesség igénye nélkül – digitális pénz, – digitális hitelesítés, digitális id®pecsét, – biztonságos közös sokrésztvev®s számítások (pl. elektronikus választás), – digitális jogok kezelése, biztosítása,. ∙ Végül egy rendkívül fontos változás: a bizonyítható biztonság fogalmának és matematikai technikáinak megszületésével a kriptográa elmés m¶vészetb®l, tapasztalatokra épül® mesterségb®l egzakt tudománnyá vált a 2000-es évekre. Ma ezt tekintjük a modern kriptográának E rövid

írásban igyekszünk a modern kriptográa tudományának alapfogalmait precízen deniálni és a gyakorlati alkalmazások szempontjából is fontos eredményeit áttekinteni. 1. Elméleti alapok 1.1 Algoritmikus számelméleti alapok A nyílt kulcsú titkosítás szinte minden ma használt eljárása az algoritmikus számelmélet nehéz problémáira épül. Ezért els®ként e téma alapismereteit foglaljuk össze. Euklideszi algoritmus Két egész szám legnagyobb közös osztóját gcd(�, �) gratest common divisor kifejezésb®l). Ez az a legnagyobb pomely � és � mindegyikének osztója Ha a két szám egyike 0, jelöli (az angol zitív egész, a másik abszolút értéke lesz a legnagyobb közös osztó. Kiszámítására lé- tezik hatékony algoritmus, mely arra az egyszer¶ összefüggésre épül, hogy bármely két �, � egészre gcd(�, �) = gcd(�, � mod �). Könnyen igazolható, hogy a következ® rekurzív algoritmusban a rekurzív

függvényhívások száma legföljebb 2 · ℓ(�), azaz az input hosszának lineáris függvénye. Mivel voltának ellen®rzése, � abszolút értékének és � mod � � zérus értékének kiszámítása, polinom id®ben elvégezhet®, így az euklideszi algoritmus is polinom id®ben befejez®dik. A kriptográai alkalmazásokban az euklideszi algoritmust általában csak pozitív egészekre használjuk. Az algoritmus kib®vített változata nem csak a 6 function gcd(�, �) input: �, � ∈ Z output: az if � és � legnagyobb közös osztója then return |�| �=0 else return gcd(�, � mod �) end end 1. algoritmus: Euklideszi algoritmus legnagyobb közös osztót, de azt a  mindig létez®  két � és � egész számot is megadja, melyekre gcd(�, �) = �� + ��. A 2. algoritmusban az el®z®n annyit változtatunk, hogy csak pozitív egészekre szorítkozunk, így az utolsó lépés  melyben a maradék 0 

elmarad, viszont a � zérus voltának ellen®rzése helyett azt vizsgáljuk, hogy � osztható-e �-vel. function gcdx(�, �) input: �, � ∈ Z, � output: if >�>0 ((gcd(�, �), �, �), ahol gcd(�, �) = �� + �� �|� then return (�, 0, 1) else � = ⌊ �� ⌋, � := � mod � (�, �, �) = gcdx(�, �) return (�, �, � − ��) (ez az � = �� + � maradékos osztás) end end 2. algoritmus: Kib®vített euklideszi algoritmus 1.1 példa Kövessük végig a 2 algoritmust Megoldás. gcdx(40, 18) kiszámításán! A lépéseket egy táblázatba írjuk. Az (1)(3) lépések a rekurzív függvényhívásokat és a mellékszámítások eredményeit, a sorban következ® (4)(6) lépések a visszaadott számhármasokat mutatják. 7 (1) (2) (3) gcdx(40, 18), gcdx(18, 4), gcdx(4, 2), Eszerint tehát 40 = 2 · 18 + 4, 18 = 4 · 4 + 2, � = 2, � = 4 � = 4, � = 2 (6) (5) (4) (�, �, �) =

(2, −4, 9) (�, �, �) = (2, 1, −4) (�, �, �) = (2, 0, 1) gcdx(40, 18) = (2, −4, 9), azaz gcd(40, 18) = 2 és 2 = −4 · 40 + 9 · 18. és a moduláris hatványozás A nyílt kulcsú titkosítás szinte min� den típusában szerepet kap a moduláris hatványozás. Ezen az � mod � Z� hatványmaradék kiszámítását értjük, melyre az exp(�, �, � ) függvényjelölést használjuk (az argumentumok száma miatt nem téveszthet® össze a valós � exponenciális függvénnyel). Kiszámításának nyilván ügyetlen módja az � hatvány kiszámítása után venni az való osztási maradékot, hisz az al- � többszáz jegy¶ is lehet. Hasonlóképp nem elég hatékony az sem, ha az �-t �-szer megszorozzuk önmagával, de a számolás egyszer¶sítésére minden szorzás után vesszük a szorzat � -nel való osztási maradékát. Ez az algoritmus exponenciális idej¶, hisz � − 1 az ℓ(�)-nek expokalmazásokban tipikusan � �

-nel és nenciális függvénye, és a hatvány kiszámításához ennyi szorzásra van szükség. Polinomiális idej¶vé válik az algoritmus, ha a szorzást nem csak az �-val való szorzásra, hanem négyzetre emelésre is használjuk. Ennek módját mutatja a 3. algoritmus Könnyen igazolható, hogy az itt ismertetett algoritmussal a moduláris hatványozás az inputok hosszának polinomja id®ben lefut. Legyen � = ℓ(� ). Mivel a függvényhívások száma a kitev® bináris jegyeinek számával egyenl®, egy moduláris összeadás m¶veletigénye �(�), a szorzás pedig elvégezhet® �(�2 ) lépésben1 , így a moduláris hatványozás m¶veletigénye �(�3 ). 1.2 példa Számítsuk ki Megoldás. 1341 mod 53 értékét! El®bb hatványozva, majd a maradékot véve (számítógéppel szá- molva) ezt kapjuk: 1341 = 4695452425098908797088971409337422035076128813 ≡ 10 (mod 53). 41 bináris alakja 101001, így a rekurzív algoritmust a

kiértékelésekt®l kezdve akár kézzel számolva is követhetjük: 1 Kifinomult algoritmusokkal ennél is jobb, aszimptotikusan �(� log �) korlát is elérhető. 8 function exp(�, �, � ) input: � ∈ Z+ a modulus, kitev® output: �� mod if � ∈ Z� a hatványozás alapja, � ∈ Z+ a � then return � �=1 else if 2 | � then � := exp(�, �/2, � ) return (�2 mod � ) else � := exp(�, (� − 1)/2, � ) return (� · �2 mod � ) end end end 3. algoritmus: Moduláris hatványozás bit számolandó 1 10 101 1010 10100 101001 Minden részletszámítás 7 szorzás és 5 mod 53 = 10. mellett 41 13 13 = (13)2 = (10)2 13 = (28)2 = (42)2 = (15)2 13 = 3000 eredmény 13 = 169 ≡ 1300 ≡ 784 ≡ 1764 ≡ 2925 ≡ alatt maradt, és a 6 mod 53 13 10 28 42 15 10 bináris jegyb®l álló kitev® maradék kiszámolására volt szükség. Az eredmény: � > 1, akkor Z� = {0, 1, . , � − 1} halmaz elemein a

bináris (�, �) ↦ � + � mod � m¶velet kommutatív, asszociatív és minden elemnek van inverze a 0-ra, mint zéruselemre nézve (azaz Z� e m¶velettel kommutatív csoportot alkot). Hasonlóképp tudjuk, hogy Z� a bináris (�, �) ↦ �� mod � m¶velettel kommutatív, asszociatív, egységelemes algebrai struktúrát ad, de e m¶velet nem invertálható (azaz Z� e m¶velettel egységelemes kommutatív félcsoport, Z pedig e két m¶velettel kommutaTudjuk, hogy ha 9 tív gyűrűt2 alkot). Nem fog zavart okozni, ha a e két m¶veletét is az Z� egészeknél használt m¶veleti jelekkel fogjuk jelölni, tehát e jelöléssel például Z5 -ben Z� számolva 2 + 3 = 0, 2 · 3 = 1. egy másik reprezentációjához jutunk, ha elemeivel azt a maradék- osztályt jelöljük, amelynek az adott szám is tagja. jük, e rövid bekezdés alatt Z� Z� := {[0], [1], . , [� − 1]}, ahol Hogy a zavart elkerül- elemeit szögletes zárójelbe

tesszük, tehát [�] = {. , � − 2�, � − �, �, � + �, � + 2�, }, tehát [�] azon egészek halmaza, melyek � -nel osztva � maradékot adnak. E halmazokat hívjuk maradékosztályoknak. A köztük lév® m¶veletek tehát a [�]+[�] := [�+� mod � ], [�]·[�] := [�� mod � ]. E deníció azért vezet egy értelmes matematikai fogalomhoz, mert ha [�] + [�] = [�] és [�] · [�] = [�], akkor bármely [�]-beli és [�]-beli egész szám összege a [�] halmazba, szorzata a [�] halmazba, azaz maradékosztályba fog esni. A fenti Z5 -beli számolások tehát e jelöléssel felírva a [2] + [3] = [0], [2] · [3] = [1] alakot öltik. Mindenezek alapján mondhatjuk azt is, hogy Z� elemei az � következ®képp deniálhatók: modulusú maradékosztályok, melyek közt az összeadás és szorzás m¶velete kompatibilis az egészek közti m¶veletekkel. A moduláris hatványozással valójában a Z�

multiplikatív félcsoportban végzünk hatványozási m¶veletet. A 3 algoritmus tetsz®leges (multiplikatív) félcsoportban és így csoportban is használható. Ha egy � félcsoportban a m¶velet polinom id®ben elvégezhet® akkor egy tetsz®leges � ∈ � elemre és + � egy � ∈ Z pozitív egészre a � hatvány kiszámításához szükséges id® az ℓ(�) és � méretének polinomjával becsülhet®. hogy tovább számol, ha egy részhatvány Bár a fenti algoritmus gyengéje, 0, de a kriptográa gyakorlatában ez nem fordul el®, mivel ott az alap és a modulus általában relatív prímek, err®l szól a következ® néhány bekezdés. Végül megjegyezzük, hogy additív csoportban is használható az algoritmus, ha egy elem konstansszorosát kell kiszámolni. A � �·� kiszámolásához a bináris alakjából ismételt összeadásokkal kapjuk meg az eredményt. Ez az írásmód az elliptikus görbe kriptográában szokásos. 2 A

matematikai pontosság kedvéért mindig jelezhetnénk, hogy épp mely algebrai struktúrára gondolunk, a szokásos megoldások egyike, hogy az elemek halmaza mellé a műveleti Z� egy halmaz, ⟨Z� , +⟩ az additív csoport, ⟨Z� , ·⟩ a multip⟨Z� , +, ·⟩ a gyűrű. E jelölések használatára nem lesz szükségünk, ha jeleket is fölsoroljuk, ekkor likatív félcsoport és szükséges, meg fogjuk mondani, melyik struktúrára gondolunk. 10 Z*� és a moduláris inverz verzén azt a 0 és � közé es® Az � � 1. � modulus szerinti moduláris in- számot értjük, melyre �� ≡ 1 Moduláris inverz csak elem (mod � ). � -hez relatív prím � számokra létezik, azaz ha gcd(�, � ) = � és � egész, Ekkor a kib®vített euklideszi algoritmus szerint létezik olyan hogy �� + �� = gcd(�, � ) = 1, ahonnan �. �� = 1 − �� ≡ 1 (mod � ), és így � moduláris inverze � = � mod A

moduláris inverz a kib®vített euklideszi algoritmus leegyszer¶sítésével közvetlenül is számolható a 4. algoritmussal Az algoritmus helyességét az ��� ≡ �� (mod � ) összefüggés ��2 ≡ �2 (mod � ), ami �2 folyamatosan lépésen belül vagy az �2 = 1 vagy az �2 = 0 bizonyítja, hogy minden lépésben fennáll az (� = 1, 2), így az algoritmus végén csökkenése miatt véges sok értéket eléri. function inv(�, � ) input: � ∈ Z, � output: ∈ Z+ , � > 1 � mod � , ahol �� ≡ 1 (mod � ) és 0 < � < �, vagy egy üzenet, hogy Nincs ilyen szám �1 , �1 := 0, � �2 , �2 := 1, � mod � while �2 > 1 do � := ⌊ ��12 ⌋ �1 , �1 , �2 , �2 := �2 , �2 , �1 − ��2 , �1 − ��2 , if �2 = 0 then return „Nincs ilyen szám” end end return end �2 mod � 4. algoritmus: Moduláris inverz kiszámolása Mint láttuk, a moduláris szorzással nem alkot

csoportot, mert e m¶* velet nem invertálható. Tekintsük tehát a Z� := {� ∈ Z� : gcd(�, � ) = 1} halmazt. Ez tehát a 0 és � közé es®, � -hez relatív prím számokból áll Z� 11 Például Z*5 = {1, 2, 3, 4}, Általában, ha � Z*12 = {1, 5, 7, 11}, Z*14 = {1, 3, 5, 9, 11, 13}. Z*� = {1, 2, . , � − 1} Z*� elemeinek száma fí függvény. Ha � törzstényez®s alakja � = prím, akkor �(� ), ahol � az Euler-féle ��11 ��22 . ���� , ahol a �� számok különböz® prímek, akkor )︂ � (︂ ∏︁ 1 . �(� ) = � 1− � � �=1 Használni fogjuk ezt az összefüggést abban az esetben, ha � két prím szor- �(� ) = (� − 1)(� − 1). � -hez relatív prím egésznek van moduláris inverze, * fontos következménye, hogy Z� a Z� -ben már bevezetett szorzásm¶velettel * * csoportot alkot, azaz minden Z� -beli elemnek van inverze, és Z� -ban minden � · � = �

egyenletnek egyetlen � megoldása van, vagyis a szorzásm¶velet zata, azaz � = �� , ekkor Annak, hogy minden 3 invertálható. * A Z� csoport ciklikus, ha osztóval rendelkez® � esetén � egy páratlan prím hatványa. Több prímZ*� szerkezetét a kínai maradéktételr®l szóló következ® részben tárgyaljuk. * További következmény, hogy a moduláris hatványozás Z� -ban tovább � * egyszer¶södik, nevezetesen ha � ∈ Z� , és � egy pozitív egész, akkor � = � mod �(� ) � . Itt kihasználtuk az Euler-tételt, mely szerint ha � és � relatív �(� ) prímek, akkor � ≡ 1 (mod � ). Általánosságban, ha � egy csoport, melynek rendje (azaz elemszáma) �, � � = � � mod � , hisz egy �-edrend¶ csoportban bármely � elemre � � = �, akkor ahol � a csoport egységelemét jelöli. Kínai maradéktétel Az RSA kriptorendszerben is alkalmazott kínai ma- radéktétel legegyszer¶bb

alakjában azt állítja, hogy az � ≡ � (mod �) � ≡ � (mod �) ekvivalenciarendszer minden egész � és � esetén megoldható ha prímek, és e megoldás egyértelm¶ modulo � = �� , � és (︀ )︀ � = �(� −1 mod �)� + �(�−1 mod �)� mod �, 3 Az előző lábjegyzetben bevezetett jelölést használva írhatjuk, hogy 12 � relatív nevezetesen (1) ⟨Z*� , ·⟩ csoport. ahol � −1 mod � a � moduláris inverze a moduláris inverze modulo �. � modulus szerint, míg �−1 mod � a � Annak ellen®rzése, hogy ez valóban megoldás, behelyettesítéssel ellen®rizhet®, hisz �(� −1 �(� −1 �(�−1 �(�−1 Tekintsük a következ® � mod �)� ≡ � (mod �) mod �)� ≡ 0 (mod �) mod �)� ≡ 0 (mod �) mod �)� ≡ � (mod �). leképezést: � : Z� Z� × Z� ; � ↦ (� mod �, � mod �). Annak ellen®rzése, hogy az (1) egyenletbeli

� (2) az egyetlen megoldás mod �, � bijekció, és adott (�, �) párhoz az (1) képlettel �, mint leképezés épp az � inverze. Ennek igazolása arra épül, hogy |Z� | = |Z� × Z� | = �� , így ha volna olyan (�, �) ∈ Z� × Z� pár, mely semmilyen � ∈ Z� -re sem lenne egyenl® � (�)-szel, akkor létezne olyan (�, �) épp azzal ekvivalens, hogy rendelt pár is, melyre a kongruenciarendszer nem lenne megoldható. Szemléltessük ezt egy egyszer¶ példán, legyen és a Z3 × Z5 elemei közt � � = 3, � = 5. Ekkor a Z15 a következ® bijekciót létesíti: 0 ↔ (0, 0) 6 ↔ (0, 1) 12 ↔ (0, 2) 10 ↔ (1, 0) 1 ↔ (1, 1) 7 ↔ (1, 2) 5 ↔ (2, 0) 11 ↔ (2, 1) 2 ↔ (2, 2) A táblázatba az elemeket a Z3 × Z5 3 ↔ (0, 3) 9 ↔ (0, 4) 13 ↔ (1, 3) 4 ↔ (1, 4) 8 ↔ (2, 3) 14 ↔ (2, 4) elempárjai szerint rendeztük, az egy sorban lév® párok els®, az egy oszlopban lév®k második eleme azonos. A * * *

bekeretezett részbe a Z15 , illetve a Z3 × Z5 elemei kerültek. Ez az észrevétel sejteti, hogy több igaz egyszer¶ bijekciónál. Az � m¶velettartó is Legyen � és � két relatív prím egész, és legyen � = �� . Ekkor a (2) képlettel definiált � függvény izomorfizmust létesít a Z� és Z� × Z� gyűrűk, valamint a Z*� és Z� × Z� csoportok közt, azaz Z� ∼ = Z� × Z� , Z*� ∼ = Z*� × Z� . 1.3 tétel (Kínai maradéktétel) Ez azt jelenti, hogy � bijekció Z� és Z� × Z� közt, valamint Z*� és Z� × Z� közt is, és bármely két �1 , �2 ∈ Z� esetén � (�1 + �2 ) = � (�1 ) + � (�2 ) és � (�1 · �2 ) = � (�1 ) · � (�2 ). 13 Z� ×Z� elemei közti m¶veletek deníciói természetes módon, az (�, �)+ (�, �) = (� + �, � + �) és az (�, �) · (�, �) = (� · �, � · �) képletekkel vannak A deniálva. Megjegyezzük, hogy az (1)-beli �

= � −1 (�, �) képlet a kínai maradékté- telb®l adódó � −1 (�, �) = � −1 (�(1, 0) + �(0, 1)) = �� −1 (1, 0) + �� −1 (0, 1) felbontásból érthet®bbé válik, hisz � ((� −1 mod �)�) = (1, 0), � ((�−1 mod �)�) = (0, 1). A kínai maradéktétel szemléltetésére és használatának bemutatására szolgál a következ® példa: 1.4 példa Számítsuk ki az 15 értékeket, mind Megoldás. Az � -re Z15 -ben, (a) 13+7 mod 15, (b) 13·7 mod 15, (c) 137 mod mind Z3 × Z5 -ben számolva! és inverzére vonatkozó képleteket fogjuk használni, de � (13) = (13 mod 3, 13 mod 5) = (1, 3), � (7) = (7 mod 3, 7 mod 5) = (1, 2), azaz 13 ↔ (1, 3), 7 ↔ (1, 2). Másrészt � −1 (1, 0) = (5−1 mod 3) · 5 = 2 · 5 = 10, � −1 (0, 1) = (3−1 mod 5) · 3 = 2 · 3 = 6. (a) 13 + 7 = 20 ≡ 5 (mod 15), másrészt (1, 3) + (1, 2) = (2, 0) ↔ 5, ugyanis � −1 (2, 0) = 2 · � −1 (1, 0) = 2 · 10 = 20 ≡ 5

(mod 15). (b) 13 · 7 = 91 ≡ 1 (mod 15), másrészt (1, 3) · (1, 2) = (1, 1) ↔ 1, ugyanis � −1 (1, 1) = � −1 (1, 0) + � −1 (0, 1) = 10 + 6 = 16 ≡ 1 (mod 15). (c) 137 = 62748517 ≡ 7 (mod 15), másrészt (1, 3)7 = (17 mod 3, 37 mod 5) = (1, 2) ↔ 7, ugyanis � −1 (1, 2) = � −1 (1, 0) + 2 · � −1 (0, 1) = 10 + 2 · 6 = 22 ≡ 7 (mod 15). a fenti táblázatban ellen®rizhetjük is az eredményeket. Az utolsó feladat azt is mutatja, hogy a moduláris hatványozás tovább egyszer¶síthet® a kínai maradéktétel alkalmazásával. Ezt az RSA titkosításnál használni fogjuk. 1.2 A modern kriptográfia alapja, a bizonyítható biztonság A bevezet®ben említett bizonyítható biztonság, mint a modern kriptográa megteremtésének alapfogalma szükségessé teszi, hogy a biztonság lehetséges szintjeit áttekintsük. A tökéletes biztonság fogalmát el®ször Shannon 14 fogalmazta meg, aki erre vonatkozó tételével megalapozta a

kriptográa tudománnyá válását. A teljesség  és az egységes tárgyalás  kedvéért felidézzük a szimmetrikus kulcsú rejtjelezés denícióját: 1.5 definíció Legyen adva az algoritmusokból álló (�, E, D) � biztonsági paraméter. A polinom idej¶ hármasról azt mondjuk, hogy szimmetrikus (privát kulcsú) rejtjelez® vagy titkosító rendszer, ha � 1. � ← �(1 ), azaz � egy véletlen polinom idej¶ algoritmus, mely a biztonsági paraméter függvényében visszaad egy legalább � hosszú sztringet, ez lesz a szimmetrikus kulcs. 2. 3. 4. � ← E� (�), azaz a véletlen polinom idej¶ E algoritmus a � kulcshoz és * az � ∈ {0, 1} nyílt szöveghez (|�| + |�|-ben polinom id®ben) hozzárendel egy � sztringet, az ún. kriptoszöveget � = D� (�), azaz a polinom idej¶ determinisztikus D algoritmus � -hoz és �-hez (|�| + |�|-ben polinom id®ben) hozzárendel egy � sztringet. Minden �, � által generált

� és tetsz®leges � esetén fönnáll az D� (E� (�)) = � (3) összefüggés. * Az � gyakran nem a {0, 1} halmaznak, hanem a x hosszú sztringek � (�) {0, 1} halmazának eleme, ahol � (�) polinomja �-nek. A lehetséges � ℳ halmazát nyílt szöveg térnek, a lehetséges kriptoszövegek � halmazát kripto szöveg térnek, míg a lehetséges kulcsok � halmazát kulcstérnek nevezzük. Szokásos az a megfogalmazás is, hogy (�, E, D) szimmetrikus kulcsú rejtjelez® a (�, ℳ, �) hármas fölött sztringek Tökéletes biztonság ha � Egy rejtjelez®t tökéletesen biztonságosnak nevezünk, ismeretében semmilyen információt nem tudhatunk meg �-r®l. E foga- lomnak több precíz, egymással ekvivalens matematikai deníciója is létezik. Mi itt most azt említjük, mely a további biztonsági deníciókhoz a legjobban illeszkedik, bár nem ez volna a legegyszer¶bb vagy legkézenfekv®bb. ExpindCPA �,Σ (�) nyílt szöveg

megkülönböztethetetlenségi kísérlet). 1.6 kísérlet ( Legyen Σ = (�, E, D) egy szimmetrikus kulcsú rejtjelez®, � algoritmus, itt (1) most a támadó, melyet két különböz® állapotában hívunk meg, ezeket � (2) és � jelöli. 15 (�0 , �1 ) ← �(1) (1� ), ahol �0 , �1 ∈ ℳ, és |�0 | = |�1 |. � 2. � ← �(1 ), � ← {0, 1} egy véletlen bit, � ← E� (�� ) (2) ′ 3. � ← � (�) ′ ExpindCPA �,Σ (�) = 1, ha � = �, egyébként = 0 (az indCPA jelölés indistinguishability under chosen-plaintext attack ) 1. 1.7 definíció (Tökéletes biztonság) A Σ = (�, E, D) eredete: szimmetrikus kulcsú rejtjelez® tökéletesen biztonságos, ha bármely korlátlan számítási kapacitással rendelkez® � Σ rejtjelez®vel szemben 0, ⃒ ⃒ ⃒ ⃒ 1 indCPA ⃒ = 0. Adv�,Σ (�) = ⃒⃒P[ExpindCPA (�) = 1] − �,Σ 2⃒ algoritmus el®nye a A denícióbeli Adv (az advantage lenti, amekkora

valószín¶séggel �-t ismerve. szemben 0, � szóból) jelölés azt a valószín¶séget je- � �0 és �1 közt csak � el®nye a Σ rejtjelez®vel különbséget tud tenni A tökéletes biztonság azt jelenti, hogy még akkor is, ha azaz korlátlan számítási kapacitással rendelke- zik. Más szóval � el®nye Σ-val szemben �, ha a � kriptoszöveg ismeretében 1 + � valószín¶séggel eltalálja, hogy � = E� (�0 ) vagy � = E� (�1 ). Azaz 2 ekkora valószín¶séggel jut a kriptoszöveg alapján a nyílt szövegre vonatkozó információhoz. A tökéletes biztonság elérhet®, és például a one time pad (OTP) nev¶ 4 rejtjelez® meg is valósítja . A tökéletes biztonság elérésének azonban súlyos ára van. Legyen Σ = (�, E, D) egy szimmetrikus kulcsú rejtjelező a (�, ℳ, �) hármas fölött. 1.8 tétel (Shannon tétele) 1. Ha Σ tökéletesen biztonságos, akkor |ℳ| 6 |�|, és Σ elveszíti tökéletes

biztonságát, ha (� -t megkerülve) egy � kulcsot többször használunk. 2. Ha |ℳ| = |�| = |�|, akkor Σ pontosan akkor tökéletesen biztonságos, ha � egyenletes eloszlás szerint választ |�|-ból (azaz minden � kulcs kiválasztásának 1/|�| a valószínűsége), és minden � ∈ � és � ∈ ℳ elemhez pontosan egy � ∈ � kulcs létezik, melyre E� (�) = �. Azonnal következik Shannon tételéb®l, hogy nyílt kulcsú rejtjelez® nem lehet tökéletesen biztonságos, hisz a rejtjelezést végz® nyílt kulcs többször használatos, egy támadó maga tetsz®leges sokszor meghívhatja. 4 Alkalmazásának híres történelmi esete a kubai atomválság után Moszkva és Washington közt kiépített forró drót, az is az OTP-t használta. 16 Számítási biztonság – gyakorlati megközelítés A szimmetrikus kul- csú titkosítás esetén is nagyon ritkán vannak olyan körülmények, amelyek lehet®vé teszik tökéletesen biztonságos

protokoll használatát. Ezért akár a szimmetrikus, akár az aszimmetrikus kulcsú rejtjelezésben szükség van a biztonságnak egy más, nem tökéletes, de elegend® szintjét elérni, azaz ha matematikailag lehetséges is a rejtjelez® feltörése, ez a gyakorlatban ne sikerülhessen. E biztonság a számítási biztonság (computational security ), mely arra épül, hogy a támadónak ugyan lehet®sége van a rejtjelez® feltörésére, de a valóságban a ma és a várható közeljöv®ben számára rendelkezésre álló er®források igénybevétele mellett belátható id®n belül csak elhanyagolható valószín¶séggel érhessen el sikert. Egy algoritmus elvégzéséhez szükséges id®t legjobb gépi ciklusokban számolni. Szokásos mértékegység a ops (floating pont operation per second), vagyis az egy másodperc alatt elvégzett lebeg®pontos m¶veletek száma. A mai szuperkomputerek 10-es nagyságrend¶ petaops sebesség¶ek, ez azt je16 lenti, hogy egy

másodperc alatt nagyságrendileg 10 m¶veletet végeznek el. 80 Például ha egy algoritmus elvégzéséhez 2 op (floating pont operation) m¶80 16 velet elvégzésére van szükség, akkor ehhez egy szuperkomputernek 2 /10 másodpercre, azaz kb. 46 hónapra van szüksége. Ennél is kinomultabb megközelítés, ha azt próbáljuk meg egy algoritmusról megbecsülni, hogy amennyiben adott � op elvégzésére van lehet®sége, akkor mekkora a siker valószín¶sége. 1.9 definíció Azt mondjuk, hogy egy kriptográai rendszer (�, �)-biztonságú, ha bármely legföljebb � opot végrehajtó támadó algoritmus legföljebb � va- lószín¶séggel sikeres. 128 A manapság legelterjedtebb kulcshossz 2 . Ha például egy algoritmus 10 egyetlen kulcs ellen®rzését 2 op alatt elvégzi, akkor annak valószín¶sége, hogy egy brute force támadással 100 év alatt megtalálja a kulcsot egy mai szuperkomputerrel 100 · 365 · 24 · 60 · 60 · 1016 ≈ 9 ·

10−17 , 2128 · 210 ami elegend® biztonságnak t¶nik, még akkor is, ha 1000-szeresére gyorsítjuk az algoritmust. E gyakorlati megközelítésben nehéz deniálni azt, hogy mit kell elég biztonságosnak, és mit nem biztonságosnak tekintenünk. Egyrészt a hardve- rek képességei gyorsan n®nek (Moore 40 éve megfogalmazott sejtése szerint 17 exponenciálisan, leggyakrabban idézett formájában azt állítja, az integrált áramkörökben lév® tranzisztorok száma másfél évente duplázódik). Más- részt teljesen más a biztonsági igénye egy szerelmes levélnek és egy kényes 80 hadititoknak. Annyit azért általában mondhatunk, hogy ha � · � < 1/2 , 40 akkor a technika jelen állása szerint még biztonságos, ha � · � > 1/2 , akkor már nem biztonságos a rendszer. Számítási biztonság – aszimptotikus megközelítés A gyakorlati al- kalmazásokhoz készült algoritmusok megvalósításakor gyelembe kell venni az el®z®

pontban deniált biztonsági fogalmat, a bizonytalanul min®síthet® tartalma miatt viszont más megközelítésre lesz szükségünk. Az els® szempont, hogy a megközelítésnek függvényalapúnak kell lennie, hisz a rendszer használhatósága változik, ha annak biztonsági paramétere (leegyszer¶sítve az input sztring, pl. a kulcs hossza) változtatható A második szempont, hogy a támadó rendelkezésére álló er®forrás nem lehet korlátlan, s®t kimondható, a támadó algoritmusának hatékonynak kell lennie, így az is a biztonsági paraméter függvényében vizsgálandó. Végül mérnünk kell a támadó sikerességének valószín¶ségét, annyit kívánunk, hogy az elhanyagolható legyen. A függvényalapú megközelítés kényelmesen és jól kezelhet®en fölépíthet® a véletlen polinomidej¶ algoritmus fogalmára. idej¶, ha létezik egy olyan �(�) algoritmus �(|�|) � � algoritmus polinom � ∈ {0, 1}* inputra az |�| az � hosszát

jelöli. Az � Egy polinom, hogy bármely lépésben véget ér, ahol algoritmus véletlen polinom idej¶, ha polinom idej¶, és az algoritmus hoz1 1 valószín¶séggel 0, záfér egy véletlen függvényhez, mely meghívásakor 2 2 valószín¶séggel 1 választ ad (a Turing gépek nyelvén az algoritmus hozzáfér egy elegend®en hosszú véletlen 0-1 sorozatot tartalmazó szalaghoz). Azt tud- juk, hogy vannak olyan problémák, melyekre van olyan véletlen polinomidej¶ algoritmus, mely gyorsabb bármely ismert determinisztikusnál, az azonban nincs bizonyítva, hogy volna olyan probléma, melynek megoldására van véletlen polinomidej¶ algoritmus, de nincs determinisztikus. Így nem biztos, hogy szükség van-e a véletlen jelenlétére, de hátrányt nem okoz. A polinomidej¶ algoritmusok használatának f® el®nye, hogy ha egy polinom sok függvényhívásból álló � algoritmus csupa polinom idej¶ algoritmussal kiszámolható függvényt hív meg, akkor maga

is polinom idej¶. 1.10 definíció A � függvény elhanyagolható, ha minden pozitív f®együtt- 18 hatójú � polinomhoz létezik olyan �� küszöbindex, hogy ha 0 6 �(�) < � > �� , akkor 1 . �(�) �−2 , �−3 , �−1000 , �6 −�1 4 +2 függvények nem elhanyagolhatók, míg a 2−� , √ 2− � , �− log � függvények elhanyagolhatók. Az 3−� , Könnyen igazolható, hogy elhanyagolható függvények összege, és polinomszorosa is elhanyagolható. Miel®tt az aszimmetrikus kulcsú titkosítás biztonságát vizsgálnánk, egy pillanatra térjünk vissza a szimmetrikus kulcsú rejtjelez® és a tökéletes biztonság deníciójára (1.5 és 17 deníciók) A valóságos alkalmazások nagy részében le kell mondanunk a tökéletes biztonságról, mert nehézségekbe ütközik minden üzenetváltás el®tt  egy az üzenet hosszánál nem rövidebb  kulcsot cserélni, cserébe viszont a valóságos

támadónak is le kell mondania a korlátlan számítási kapacitás lehet®ségér®l, mert a valóságban ilyen nincs. Így a tökéletes biztonság deníciójának minimális megváltoztatása elvezet minket egy gyakorlatban használhatóbb új fogalomhoz, a számítási biztonság fogalmához. Ezen belül a biztonságnak több szintje is van A következ® fogalomra több ekvivalens deníció is létezik, ennek megfelel®en különböz® neveken is szokás említeni. A nyíltszöveg-megkülönböztethetetlenség alap- vet® volt a tökéletes biztonság deníciójában is, itt is erre fogjuk építeni a biztonság-fogalmunkat, melyet szokás még szemantikai biztonságnak is nevezni, mert mint látni fogjuk, azt fejezi ki, hogy egyetlen hatékony támadó sem tudhat meg nem elhanyagolható valószín¶séggel semmit a kriptoszöveg alapján a nyílt szövegr®l. 1.11 definíció (Szemantikai biztonság) A Σ = (�, E, D) szimmetrikus kul- csú rejtjelez®t szemantikailag

biztonságosnak nevezzük, ha bármely véletlen � támadó el®nye a Σ rejtjelez®vel szemben elhanyagolható, � algoritmushoz van olyan elhanyagolható � függvény, hogy ⃒ ⃒ ⃒ ⃒ 1 indCPA indCPA Adv�,Σ (�) = ⃒⃒P[Exp�,Σ (�) = 1] − ⃒⃒ 6 �(�). 2 polinom idej¶ azaz bármely A szemantikai biztonság fenti deníciójára pontosabb kifejezés az üzenetmegkülönböztethetetlenség vagy még pontosabban a nyíltszöveg-megkülönböztethetetlenség lehallgató jelenlétében kifejezések, amit az vidítés is jelöl. indCPA rö- De mivel ekvivalens fogalmakról van szó, egyszer¶bb ezt 19 használni. E lehallgató (eavesdropper ) kifejezés arra a valóságban el®forduló helyzetre utal, amelyben a támadónak van sejtése arról, hogy mi lehet az üzenetben (pl �0 = igen ↔ �1 = nem; �0 = támadunk ↔ �1 = maradunk,. ), és lehallgatja az elküldött kódolt üzenetet, azaz megszerzi a � = E�

(�� ) kriptoszöveget, és abból próbál információhoz jutni a nyílt szöveg kiválasztásához. Az aszimmetrikus rejtjelező és biztonsága Az aszimmetrikus kulcsú rejtjelezés deníciója csak annyiban különbözik a szimmetrikus kulcsúétól, hogy a kulcsgenerálás során nem egy, hanem két kulcsot kell kapnunk, egyet az E, egyet a D algoritmus részére. 1.12 definíció (Aszimmetrikus kulcsú rejtjelez®) Legyen adva az sági paraméter. � biztonA polinom idej¶ algoritmusokból álló Π = (�, E, D) hármas- ról azt mondjuk, hogy aszimmetrikus (nyílt kulcsú) rejtjelez® vagy titkosító rendszer, ha 1. (��, ��) ← �(1� ), azaz � egy véletlen polinom idej¶ algoritmus, mely a biztonsági paraméter függvényében visszaad két (legalább sztringet, �� lesz a nyílt, �� � bit hosszú) a titkos kulcs. 2. � ← E�� (�), azaz a véletlen polinom idej¶ E algoritmus a �� kulcshoz és az � ∈ ℳ nyílt

szöveghez (|��| +|�|-ben polinom id®ben) hozzárendel egy � sztringet. 3. � = D�� (�), azaz a determinisztikus polinom idej¶ D algoritmus �� -hoz és �-hez hozzárendel egy � sztringet. 4. Minden �, � által generált (��, ��) és tetsz®leges � ∈ ℳ esetén fönnáll az P[D�� (E�� (�)) = �] = 1 − �(�) összefüggés, ahol Az E és D � (4) elhanyagolható. algoritmusokra föltehet®  ami a gyakorlatban is megeshet , hogy a dekódolás valamilyen ok miatt meghiúsul, ekkor a D megkülönböztetett jelet küld (a kriptográai irodalomban a algoritmus egy ⊥ jelet szokás erre használni). A (4) biztonságos megfogalmazása az elvárt D�� (E�� (�)) = � egyenl®- ségnek, amely arra is számít, hogy akár a kulcsgenerálás, akár a rejtjelezés véletlen algoritmusában valamilyen elhanyagolható esély¶ hiba történik. 20 A megkülönböztethetetlenségi kísérlet itt is

elvégezhet®, de a kulcsgeneráláson kívül ez abban is különbözik a szimmetrikus kulcsú esett®l, hogy itt a támadó folyamatosan hozzáfér a nyílt kulcshoz, így maga nyílt szövegeket rejtjelezhet tetszése szerint. ExpindCPA �,Π (�) nyílt szöveg megkülönböztethetetlenségi kísér- 1.13 kísérlet ( let). Legyen Π = (�, E, D) egy aszimmetrikus kulcsú rejtjelez®, goritmus, melyet két különböz® állapotában hívunk meg, ezeket jelöli, és amely közben polinom sokszor meghívhatja � olyan al�(1) és �(2) E�� -t. ∙ (��, ��) ← �(1� ) ∙ (�0 , �1 ) ← �(1) (1� , ��, E�� ), ∙ � ← {0, 1} egy véletlen bit, ahol �0 , �1 ∈ ℳ, és |�0 | = |�1 |. � ← E�� (�� ). ∙ �′ ← �(2) (�, E�� ) ′ ExpindCPA �,Π (�) = 1, ha � = �, egyébként = 0. 1.14 definíció (Szemantikai biztonság, CPA-biztonság) A Π = (�, E, D) aszimmetrikus kulcsú

rejtjelez®t szemantikailag biztonságosnak vagy CPAbiztonságosnak nevezzük, ha bármely véletlen polinom idej¶ a � támadó el®nye Π rejtjelez®vel szemben elhanyagolható, azaz bármely � algoritmushoz van � függvény, hogy ⃒ ⃒ ⃒ ⃒ 1 indCPA indCPA Adv�,Π (�) = ⃒⃒P[Exp�,Π (�) = 1] − ⃒⃒ 6 �(�). 2 olyan elhanyagolható Szokás az ExpindCPA �,Π (�) kísérletet kicsit másként deniálni. argumentumos, második argumentuma a � Exp Ekkor 2′ bit, és kimenete a � bit, azaz �′ = ExpindCPA �,Π (�, �). Ekkor, az � algoritmus Π-vel szembeni el®nyére a fenti denícióbelivel lénye- gében ekvivalens más deníció adható: indCPA indCPA ⃒ ⃒ AdvindCPA �,Π (�) = P[Exp�,Π (�, 0) = 1] − P[Exp�,Π (�, 1) = 1] ⃒ ⃒ E deníció kicsit életszer¶bbnek t¶nik, itt � nem a � bitet próbálja eltalálni, hanem csak az a kérdés, van-e olyan statisztikai próba, mely különbséget

tud 21 tenni a � = 0 esetére adott 1-es válaszok és a � = 1 esetére adott 1-es válaszok között? Mert ha igen, akkor a rejtjelezés nem biztonságos! Még er®sebb támadásra ad lehet®séget, ha a támadó valamilyen módon hozzá tud jutni maga által el®állított kriptoszövegekek dekódoltatásával kapott nyílt szövegekhez, vagy legalább azokról némi információhoz juthat. A nem elég gondosan megtervezett kriptográai protokollokban számtalan olyan lehet®ség adódhat, amikor erre a támadónak lehet®sége nyílik. Például ha a támadó lehallgat egy titkosított üzenetet tartalmazó emailt, majd azt a saját nevén is elküldi a címzettnek, lehet, hogy a címzett válaszában mellékeli a dekódolt üzenetet. ExpCCA �,Π (�) 1.15 kísérlet ( Legyen Π = (�, E, D) választott kriptoszöveg alapú támadás (CCA)). egy aszimmetrikus kulcsú rejtjelez®, � olyan algo(1) (2) ritmus, melyet két különböz® állapotában hívunk

meg, ezeket � és � jelöli, és amely közben polinom sokszor meghívhatja utóbbit anélkül, hogy magát az �� -t E�� és a D�� algoritmust, is megkapná. ∙ (��, ��) ← �(1� ) ∙ (�0 , �1 ) ← �(1) (1� , ��, E�� , D�� ), ∙ � ← {0, 1} egy véletlen bit, ∙ �′ ← �(2) (�, E�� , D�� ), ahol �0 , �1 ∈ ℳ, és |�0 | = |�1 |. � ← E�� (�� ). � (2) továbbra is hozzáfér a D�� alD�� (�) függvényhívásra nincs lehet®sége. ahol tehát goritmushoz, egyedül csak a ′ ExpCCA �,Π (�) = 1, ha � = �, egyébként = 0. 1.16 definíció (nyílt szöveg megkülönböztethetetlenség választott kriptoszöveg alapú támadás mellett, CCA-biztonság) A Π = (�, E, D) aszimmetri- kus kulcsú rejtjelez®t CCA-biztonságosnak nevezzük (szokásos elnevezés még: CCA2-biztonság, adaptív CCA-biztonság), ha bármely véletlen polinom idej¶ � �

algoritmushoz van olyan elhanyagolható támadó el®nye a Adv Π rejtjelez®vel szemben elhanyagolható, azaz bármely CCA �,Π (�) � függvény, hogy ⃒ ⃒ = ⃒⃒P[ExpCCA �,Π (�) = 1] − ⃒ 1 ⃒⃒ 6 �(�). 2⃒ A CCA-biztonságnak van egy olyan gyengébb támadást feltev® deníciója is, ahol a támadónak csak az �0 és �1 kiválasztásáig van lehet®sége meghívni 22 a dekódolót, ekkor ezt CCA1-biztonságnak hívják, a fenti deniált fogalmat pedig CCA2-biztonságnak. A fenti kísérletet és deníciót aszimmetrikus rejtjelez®re fogalmaztuk meg, de ezek egyszer¶en módosíthatóak, hogy szimmetrikus rejtjelez®re is érvényesek legyenek, egyszer¶en (��, ��) pár a közös � Π egy Σ szimmetrikus rendszerre cserélend®, és a kulcsra, minden más marad. Hogyan lehet aszimmetrikus kulcsú rejtjelez®t konstruálni? Az összes fontosabb ilyen konstrukció valamelyik makacs számelméleti problémára, és

abból származó ún. egyirányú kiskapu-függvényre, illetve egyirányú kiskapupermutációra épül Ezért el®ször ezeket vesszük sorra 1.3 Makacs számelméleti problémák Makacs számelméleti problémáknak nevezzük azokat a kérdéseket, melyek megválaszolására eddig nem találtunk hatékony algoritmust, eddig makacsul ellenálltak minden próbálkozásnak, de ugyanakkor az sincs bizonyítva, hogy ilyen algoritmus nem létezik. Ráadásul nem elég, hogy a probléma bizonyos esetekben legyen nehéz, hanem hogy az esetek egy pontosan és egyszer¶en deniálható tartományán belül elhanyagolható számú esetet leszámítva mindig. Faktorizáció A számelmélet leg®sibb problémáinak egyike az egészek fak- torizációja. Egész számok összeszorzása polinomidej¶ algoritmus, tényez®kre bontására ezidáig hatékony algoritmust nem ismerünk (nem számítva a Shoralgoritmust, mely polinom id®ben fogja megoldani e problémát kvantumkomputeren  ha

valamikor lesz olyan). ExpFactor �,� (�) faktor kísérlet). 1.17 kísérlet ( � egy polinomidej¶ algoritmus, mely a biztonsági paraméter függvényében el®állít két szorzatát. A két szám prím. � � �-bites számot és azok függvényében elhanyagolható valószín¶séggel nem egy algoritmus, mely egy számpárt ad vissza: ∙ (�, �, � ) ← �(1� ) ∙ (�′ , � ′ ) ← �(� ) ′ ′ ExpFactor �,� (�) = 1, ha � � = � , egyébként 23 = 0. 1.18 definíció Azt mondjuk, hogy a faktorizáció nehéz, ha bármely véletlen polinomidej¶ vény, hogy � algoritmushoz létezik olyan elhanyagolható �(�) függ- Factor AdvFactor �,� (�) = P[Exp�,� (�) = 1] 6 �(�). Moduláris gyökvonás, az RSA-probléma Bár a faktorizáció nehéz prob- lémának t¶nik, még sincs széles körben elterjedt kriptográai alkalmazása, van azonban olyan, amely szoros kapcsolatban áll vele. Ezek

legismertebbike az RSA-probléma. Ez bizonyos korlátozó feltevések mellett lényegében az is- � kitev®vel végzett moduláris hatványozás inverzének, azaz a moduláris �-edik gyökvonás elvégzésének nehézségét feltételezi, ha a modulus két prím mert szorzata. � : Z*� Z� ; � ↦ �� függvény invertálható, ha � tetsz®leges 1-nél nagyobb egész, és gcd(�, �(� )) = 1. Másként fogal−1 * mod �(� ), mazva � a Z� egy permutációja. Megmutatjuk, hogy ha � = � � * −1 * akkor � inverze az � : Z� Z� ; � ↦ � függvény. Ennek ellen®rzéséhez csak azt kell látnunk, hogy ha � moduláris inverze �-nek, azaz �� ≡ 1 (mod �(� )), akkor van olyan � > 0 szám, hogy �� = 1 + ��(� ), és így * tetsz®leges � ∈ Z� számra Könnyen igazolható, hogy az (�� )� = ��� ≡ �1+��(� ) (mod � ) ≡ �(��(� ) )� ≡ �1� = �. Kérdés, hogy határozható

meg � (mod � ) (mod � ) ismeretében �. Ha � = �� , ahol � és � két különböz® prím  és mostantól csak erre az esetre szorítkozunk , akkor �(� ) = (� − 1)(� − 1), az � polinomidej¶ algoritmusunk. moduláris inverzének kiszámítására pedig van A nehézséget az okozza, hogy határozni épp oly nehéz, mint faktorizálni � -et. tényez®it, akkor polinom id®ben ki tudjuk számolni a értéket, ha pedig ismerjük � és �(� ) �(� )-et meg- � �(� ) = (� − 1)(� − 1) Ha ugyanis ismerjük értékét, akkor az � = �� �(� ) = (� − 1)(� − 1) egyenletrendszerb®l meghatározható � és �, nevezetesen a sítés után a második egyenletb®l a másodfokú �2 − (� − �(� ) + 1)� + � = 0 24 � = �/� helyette- egyenletet kapjuk, ami polinom id®ben megoldható. A kérdés tehát az, vane olyan algoritmus, mely � , � és � ismeretében

kiszámítja azt az � számot, � melyre � ≡ � (mod � ). Mindmáig nyitott kérdés, hogy ez a probléma ekvivalens-e a faktorizációs problémával, csak annyit tudunk, hogy nyilvánvalóan nem nehezebb nála. Nem ismeretes olyan algoritmus, mely az �-edik � -et. A függvény inverze egyszer¶ �-edik hatványozás modulo � . Ez az eljárás gyököt visszaadó függvény ismeretében faktorizálni tudná az RSA-függvény esetén kb. négyszer olyan gyors algoritmusra cserélhet® Legyen �� = � mod � − 1, és �� = = � − 1 és �(�) = � − 1, ezért � � ≡ � �� (mod �) és (mod �), és a kínai maradéktétel szerint az a kínai maradéktétel alkalmazásával. � mod � − 1. hasonlóképp Mivel �(�) � �� � ≡� � ≡ � �� (mod �) �� (mod �) �≡� egyértelm¶en megoldható, nevezetesen az (1) képletet használva (︀ )︀ � = � �� (� −1 mod �)� + � ��

(�−1 mod �)� mod �, ahol a �� , �� , � −1 mod � és �−1 mod � mind el®re számolhatók. (5) Szemléltetésül lássunk egy példát. 1.19 példa Legyen � = 3 és � = 16. � = 11, � = 17, így � = 187 � = ��,� (�) és Számítsuk ki az és az �(� ) = 160. Legyen −1 ��,� (�) értékeket, az utóbbit a kínai maradéktétellel! Megoldás. � = �187,3 (16) = 163 mod 187 = 4096 mod 187 = 169 még könnyen számolható. Az inverz függvényhez meg kell határoznunk � értékét: � = 3−1 mod 160 = 107. Az el®re kiszámolható paraméterek: �� = 107 mod 10 = 7, �� = 107 mod 16 = 11, −1 � mod � = 17−1 mod 11 = 2, �−1 mod � = 11−1 mod 17 = 14 Ha csak egyszer¶ moduláris hatványozással próbáljuk az inverzet kiszámolni, akkor ��,� (�) = �187,107 (169) = 169107 mod 187 = 16. 25 Mivel 107 bináris alakja ritmusa szerint 12 darab 1101011, ezért a moduláris

hatványozás a 3. algo187-es modulusú szorzás elvégzése után megkapjuk az eredményt. Ha a kínai maradéktétellel próbálkozunk, akkor a következ® számításokat kell elvégezni, ahol a moduláris hatványozások modulusai csak 11 és 17: �� = � �� mod � = 1697 mod 11 = (169 mod 11)7 mod 11 = 47 mod 11 = 5 �� = � �� mod � = 16911 mod 17 = (169 mod 17)11 mod 17 = 1611 mod 17 = 16 )︀ (︀ � = � �� (� −1 mod �)� + � �� (�−1 mod �)� mod � = (5 · 2 · 17 + 16 · 14 · 11) mod 187 = 16. Nagyságrendileg negyed annyi m¶veletet igényel ez utóbbi módszer alkalmazása. ExpRSA �,� (�) RSA kísérlet). 1.20 kísérlet ( � egy véletlen polinomidej¶ algo- ritmus, mely a biztonsági paraméter függvényében el®állít két számot, azok � számot, melyre �-bites prím- �(� )-hez relatív prím � számot és azt a � �� ≡ 1 (mod �(� )). Az � algoritmus egy Z*� -beli számot

szorzatát, egy ad vissza. ∙ (�, �, �) ← �(1� ) ∙ � ← Z*� ∙ � ← �(�, �, �) � ExpRSA �,� (�) = 1, ha � ≡ � (mod � ), egyébként = 0. 1.21 definíció Azt mondjuk, hogy az RSA probléma nehéz, ha bármely véletlen polinomidej¶ � algoritmushoz létezik olyan elhanyagolható � függvény, hogy RSA AdvRSA �,� (�) = P[Exp�,� (�) = 1] 6 �(�). Négyzetgyökvonás, a Rabin-probléma Ha � = �� Érdekes a helyzet a gyökvo- két páratlan prím szorzata, akkor �(� ) páros, így a * * 2 négyzetre emelés, azaz az � : Z� Z� ; � ↦ � függvény nem invertálható, s®t, minden négyzetszámnak 4 négyzetgyöke van. * Euler tételéb®l azonnal következik, hogy ha � páratlan prím, akkor Z� ban egy � elem pontosan akkor négyzetelem (kvadratikus maradék mod �), nással. 26 � (�−1)/2 ≡ 1 (mod �), ugyanis ha van olyan �, hogy �2 ≡ � (mod �), (�−1)/2

akkor � ≡ ��−1 ≡ 1 (mod �). Ebb®l adódik, hogy Z*� elemeinek fele négyzetelem, fele nem négyzetelem, továbbá ha � ≡ 3 (mod 4), akkor � (�+1)/4 * mod � számok, ugyanis négyzetgyökei Z� -ban a ±� ha (±� (�+1)/4 )2 ≡ � (�+1)/2 (mod �) ≡ � (�−1)/2 � (mod �) ≡ � (mod �) � Legyen tehát és � ≡ 3 (mod 4), �2 ≡ � és � = �� . Ekkor az (mod � ) kongruencia megoldása a kínai maradéktétel szerint ekvivalens az �2 ≡ � �2 ≡ � (mod �) (mod �) kongruenciarendszer megoldásával. Mindkett®nek két-két megoldása van, így a következ®, valójában négy különböz® kongruenciarendszer négy megoldást ad: � ≡ ±� (�+1)/4 (mod �) � ≡ ±� (�+1)/4 (mod �). � modulusú négyzetre emelés inverze könnyen szá� prímtényez®s felbontását. Meglep® módon a négy- Azt látjuk, hogy az molható, ha ismerjük zetgyökvonás nehézségér®l

tudjuk, hogy ekvivalens a faktorizációs probléma nehézségével (ellentétben az �-edik gyökvonással), az erre épül® Rabin krip- torendszer mégsem terjedt el, mert a 4 gyök közül az egyetlen helyes kivá- lasztásához az üzenetbe valamilyen redundáns információt kell tenni. Diszkrét logaritmus és � Legyen egy generátoreleme, azaz � � � -elem¶ ciklikus csoport, 0 2 �−1 halmaza {� = 1, �, � , . , � }. egy tetsz®leges elemeinek ExpDlog �,� (�), diszkrét logaritmus kísérlet). 1.22 kísérlet ( � group egy véletlen polinomidej¶ algoritmus, mely a biztonsági paraméter függvényében el®állít egy � -adrend¶ ciklikus csoportot, és annak egy csoportban a m¶velet hatékonyan számolható. Az elemet ad vissza. 27 � generátorelemét, mely � algoritmus egy �-beli ∙ (�, �, �) ← � group (1� ), ∙ ℎ←� ahol ℓ(�) = �, egy egyenletes eloszlás szerint választott

véletlen elem ∙ � ← �(�, �, �, ℎ) � ExpDlog �,� group (�) = 1, ha � = ℎ, egyébként = 0. 1.23 definíció Azt mondjuk, hogy az diszkrét logaritmus probléma � group -ra nézve nehéz, ha bármely véletlen polinomidej¶ � algoritmushoz létezik olyan elhanyagolható � függvény, hogy Dlog AdvDlog �,� group (�) = P[Exp�,� group (�) = 1] 6 �(�). A diszkrét logaritmus feltevés azt jelenti, hogy van olyan � group algorit- mus, melyre nézve a diszkrét logaritmus probléma nehéz. A modern kriptográa több � group algoritmusról is feltételezi ezt. Diffie–Hellman-problémák A diszkrét logaritmus problémához szorosan kapcsolódik a DieHellman kulcscserénél szerepl® probléma néhány válto� zata. A számítási DieHellman probléma lényege, hogy ha ismerjük a � � és � elemeket egy � generátorú ciklikus � csoportban, akkor ki tudjuk-e �·� számítani a � elemet? Ha a diszkrét

logaritmust könnyen ki tudjuk számolni, akkor igen! Azt azonban nem tudjuk, hogy ha a diszkrét logaritmus probléma nehéz, akkor a számítási DieHellman probléma is nehéz-e. ExpCDH �,� group (�), számítási (computational) DieHellman kí- 1.24 kísérlet ( sérlet). � group egy véletlen polinomidej¶ algoritmus, mely a biztonsági para- méter függvényében el®állít egy � generátorelemét. Az � � -adrend¶ ciklikus csoportot, és �-beli elemet ad vissza. algoritmus egy ∙ (�, �, �) ← � group (1� ), ahol ℓ(�) = �, ∙ �, � ← Z� ∙ � ← �(�, �, �, � � , � � ) CDH �·� ExpCDH �,� group (�) = 1, ha � = � , egyébként Exp�,� group (�) = 0. 28 annak egy 1.25 definíció Azt mondjuk, hogy a számítási Diffie–Hellman probgroup léma � -re nézve nehéz, ha bármely véletlen polinomidej¶ � algoritmushoz létezik olyan elhanyagolható � függvény, hogy CDH

AdvCDH �,� group (�) = P[Exp�,� group (�) = 1] 6 �(�). Még érdekesebb és er®sebb a döntési (decisional) DieHellman probléma � � (DDH)! Az el®bb deniált kísérletben megkonstruált (�, �, �, � , � ) ismere�·� tében itt nem az a kérdés, hogy ki tudjuk-e számítani � -t, hanem hogy egyáltalán meg tudjuk-e különböztetni egy véletlenül választott elemt®l! Legyen tehát egy � � group ugyanaz, mint el®bb, az � algoritmus pedig adjon vissza bitet, azaz legyen � ← �(�, �, �, � � , � � , �) Ha e bit statisztikai jellemz®i nem elhanyagolható eséllyel különböznek egy �·� véletlen � elemre és az � = � elemre, akkor e probléma nem nehéz. 1.26 definíció Azt mondjuk, hogy a döntési Diffie–Hellman probléma � group -re nézve nehéz, ha bármely véletlen polinomidej¶ � algoritmushoz � függvény, hogy ⃒ ⃒ � � � � �·� ⃒ 6 �(�), ⃒ group AdvDDH

(�) = P[�(�, �, �, � , � , �) = 1] − P[�(�, �, �, � , � , � ) = 1] �,� létezik olyan elhanyagolható ahol � ← �. � group -re nézve könny¶, akkor group -re nézve, akkor a DDH a CDH probléma is. Ha pedig a CDH könny¶ � probléma is. Az állítás megfordítása nem igaz, van olyan � csoport, melyben Az világos, hogy ha a diszkrét log probléma a diszkrét logaritmus és a CDH nehéznek t¶nik, de a DDH könny¶. Bár vannak olyan � group algoritmusok, melyekre nézve a DDH problémát nehéznek hisszük, mégis nem alaptalan az a félelem, hogy esetleg kés®bb �·� valaki talál olyan matematikai algoritmust, mely képes � bizonyos tulaj� donságai alapján nem elhanyagolható valószín¶séggel jól tippelni a � -val � és � -vel való kapcsolatára. Ennek esélyét csökkenti a hash DieHellman �·� feltevés. Itt egy hash-függvénnyel próbáljuk a � esetlegesen nem teljesen véletlenszer¶

viselkedését egy véletlenszer¶ hash függvénnyel eltakarni. � : �2 � egy hash-függvény. Azt mondjuk, hogy a hash Diffie–Hellman probléma � -re nézve nehéz, ha bármely véletlen polinomidej¶ � algoritmushoz létezik olyan elhanyagolható � függvény, hogy ⃒ ⃒ � � � � � �·� ⃒ ⃒ AdvHDH �,� (�) = P[�(�, �, �, � , � , �) = 1] − P[�(�, �, �, � , � , �(� , � )) = 1] 6 �(�), 1.27 definíció Legyen 29 ahol �, � ← Z� , � ← �, azaz ezek egyenletes eloszlás szerint véletlenül válasz- tott elemek. � �·� Hogy miért épp a �(� , � ) értéket választjuk, miért nem csak például �·� a �(� )-t, az csak a DieHellman feltevésekre épül® ElGamal-rejtjelez®k konstrukciójából lesz világos, ugyanis ez teszi majd lehet®vé a rendszer adott feltevések mellett való biztonságának bizonyíthatóságát. A kés®bb ismertetend® ElGamal rendszerek

választott kriptoszöveg alapú támadása elleni biztonságának bizonyíthatóságához még er®sebb feltevés szükséges. Ebben a támadó hozzáfér egy � függvényhez is, melyet többször is meghívhat, és amely megmondja, hogy két �, � ∈ � elem közt fennáll-e az �� = � összefüggés a rögzített, de a támadó számára ismeretlen � mellett. ExpIDH �,� (�), interaktív DieHellman kísérlet). � egy véletlen 1.28 kísérlet ( polinomidej¶ algoritmus, mely a biztonsági paraméter függvényében el®állít egy � -adrend¶ ciklikus csoportot, és annak egy � generátorelemét. Az � al�-beli elemet ad vissza, miután � -szor meghívja az � függvényt goritmus egy az általa választott paraméterekkel. ∙ (�, �, �) ← �(1� ), ahol ℓ(�) = �, ∙ �, � ← Z� ∙ � (�, �) = 1, ha �� = � , egyébként = 0. ∙ � ← �(�, �, �, � � , � � , � (�1 , �1 ), .

, � (�� , �� )) IDH �·� ExpIDH �,� (�) = 1, ha � = � , egyébként Exp�,� (�) = 0. 1.29 definíció Azt mondjuk, hogy az interaktív Diffie–Hellman probléma � -re nézve nehéz, ha bármely véletlen polinomidej¶ � algoritmushoz � függvény, hogy létezik olyan elhanyagolható IDH AdvIDH �,� (�) = P[Exp�,� (�) = 1] 6 �(�). Az el®z®ekben felsoroltuk a legismertebb és legfontosabb makacs számelméleti problémákat. Csak azokkal foglalkoztunk, amelyek legalább emlí- tés szintjén, vagy az összefüggések megvilágítása érdekében szükségeseknek t¶nnek ahhoz, hogy a legelterjedtebb nyílt kulcsú rejtjelez®ket megismerjük. Nem foglalkoztunk azokkal a makacs problémákkal, amelyek csak elméleti vagy történeti szempontból érdekesek, például nem ismertettük a hátizsákfeladatra épül® nyílt kulcsú titkosító rendszert, amelyet végül sikerült föltörni az LLL-algoritmussal. 30 1.4

Egyirányú kiskapufüggvények Az egyirányú függvények a legalapvet®bb kriptográai primitívek közé tartoznak. Lényegük, hogy a függvény kiértékelése könny¶, invertálása vagy ha nem invertálható, akkor az ®skép bármelyik elemének kiszámítása viszont nehéz. Azaz adott �-re � (�)-et, de melyre � (�) = � . könny¶ kiszámolni ismeretében nehéz olyan � -t találni, egy � = � (�) érték Használatuk szám- talan helyen és számtalan módon el®fordul kriptográai protokollokban, a szimmetrikus titkosítás egésze lényegében ezekre épül. Elég visszautalnunk arra, hogy a Feistel-tipusú szimmetrikus rejtjelez®k (pl. a DES) arra az ötletre építenek, mely egy nem invertálható egyirányú függvényb®l invertálható egyirányú függvényt képez. A bijektív egyirányú függvényeket szokás egyirányú permutációknak is nevezni Az angol elnevezések: one-way permutation. one-way function és A nyílt

kulcsú rejtjelez®kben az egyirányú függvény és permutáció egy speciális változata, az egyirányú kiskapufüggvény, illetve az egyirányú kiskapupermutáció játssza a kulcsszerepet. olyan információ � -r®l, Ezek is egyirányúak, viszont van egy melynek birtokában már könny¶ letve egy elem valamely ®sképét megkeresni. információhoz nem lehet könnyen hozzájutni csak ilyen � � -et invertálni, il- Természetesen ehhez a plusz � ismeretében, de könny¶ függvényt létrehozni a kiskapu-információval együtt. A formális de- níció a következ®. 1.30 definíció (Egyirányú függvény) Az � : {0, 1}* {0, 1} függvény egyirányú, ha 1. könnyen számolható, azaz létezik egy olyan polinom idej¶ hogy bármely ℱ algoritmus, �-re ℱ(�) = � (�); 2. nehezen invertálható, azaz tetsz®leges �-re, � = � (�), � = ℓ(�) jelö� algoritmushoz, mely * egy {0, 1} -beli elemet ad az lések mellet,

tetsz®leges véletlen polinomidej¶ a biztonsági paraméter és � függvényében vissza, létezik olyan elhanyagolható � függvény, hogy P[� (�(1� , �)) = � (�)] 6 �(�). Az egyirányú függvény fogalma úgy is deniálható, hogy nem egy függvényt, hanem függvények egy egész osztályát deniáljuk. Ekkor a függvényosztály deníciójában a függvényeket indexel® algoritmusnak is szerepet kell 31 kapnia. Ezt az általánosabb fogalomalkotást a következ® deníciókban meg is tesszük, de már csak az egyirányú függvények egy speciális osztályán, a kiskapu-függvényeken. 1.31 definíció (Egyirányú kiskapu-függvény és kiskapu-permutáció) Egyirányú kiskapu-függvények egy családján algoritmusoknak azt a (�, �, � −1 ) hármasát értjük, melyre: 1. (�, �, �� , ℛ� ) ← �(1� ), ahol � véletlen polinom idej¶ algoritmus, mely egy (�, �) párt, és a � -val indexelt ��

függvényhez a � � értelmezési tartományt és az ℛ� értékkészletet generálja. 2. � = �� (�), ahol � determinisztikus polinom idej¶ algoritmus, mely a � által generált � indexhez és egy � ← �� elemhez az � ∈ ℛ� elemet rendeli. 3. �� egyirányú, azaz tetsz®leges véletlen polinomidej¶ mely a biztonsági paraméter és � függvényében egy vissza, létezik olyan elhanyagolható � � algoritmushoz, �� -beli elemet ad függvény, hogy P[�� (�(1� , �)) = �� (�)] 6 �(�). � −1 algoritmus determinisztikus polinom idej¶, mely a � által ge−1 nerált � indexhez és az � = �� (�) értékhez olyan �� (�) értéket (esetleg 4. Az több ilyen értéket) rendel, mely(ek)re �� (��−1 (�)) = �. Ha �� minden � -ra bijekció, egyúttal � � = ℛ� , akkor a mast egyirányú kiskapu-permutációnak nevezzük. Ilyenkor (�, �, � −1 )

hár�(1� ) kimenete (�, �, �� ). Az egyirányú kiskapu-függvény, illetve kiskapu-permutáció angol nevéb®l származó rövidítések TDF (oneway trapdoor permutation ). trapdoor function ), illetve TDP (oneway Hamarosan látni fogunk példát egyirányú függvényre, egyirányú kiskapufüggvényre és egyirányú kiskapu-permutációra is. Ilyenek konstrukcióihoz legkönnyebben  és az alkalmazásokban is ezek a legfontosabbak  a makacs számelméleti problémák segítségével juthatunk. 32 Megjegyezzük, egyirányú függvény létezése nincs bizonyítva! Annyit tudunk, hogy ha sikerülne létezésüket bizonyítani, akkor abból következne, � � ̸= � � � , abból pedig, hogy � ̸= � � . tudjuk, hogy � ̸= � � -b®l következik-e egyirányú hogy Meglep® módon azt nem függvény létezése. Azokra a problémákra, amelyekre a legfontosabb egyirányú kiskapufüggvények épül- � � -teljesek lennének, azt

sejtik, hogy ezek � � -köztes (� � -intermediate) osztályba tartoznak. Ér- nek, az sincs bizonyítva, hogy � ̸= � � esetén egy dekes módon az NP-teljes problémákat (pl. a hátizsákfeladatot) nem sikerült igazán fölhasználni kriptográai célokra, mert bár a legrosszabb esetekben nehéz ®ket megoldani, egy átlagos feladatra lehet, hogy könny¶. Egyirányú függvény a faktorizációs problémából tunk az, hogy az � : (�, �) �� Az els® gondola- egyirányú függvény, és valóban, ha a faktorizáció nehéz, akkor e függvény egyirányú. Szépséghibája, hogy ele- ve csak prímpárokra van értelmezve. Némi ügyeskedéssel deniálható olyan függvény, mely pozitív egész prímek kiválasztása �-t®l � számokra van értelmezve, és amelyben a � és � determinisztikusan függ, de mivel nincs gyakorlati kriptográai alkalmazása, ismertetését mell®zzük. Az RSA-függvény letben deniált � Ha az

RSA-probléma nehéz, akkor az 1.20 RSA-kísér- generátorral el®állított paramétereket használva az ��,� (�) = �� mod � függvény egyirányú kiskapu-permutáció a Z*� halmazon, melynek inverze az −1 ��,� (�) = � � mod � függvény. Nyilvánvaló, hogy itt a � a kiskapu-információ. Ezt az ��,� függ- vényt szokás tankönyvi RSA-nak is nevezni, miután több tankönyv e függvényt, mint az RSA rejtjelez®t mutatja be. Fontos megjegyezni, hogy ez csak egy egyirányú kiskapu-permutáció, rejtjelezésre önmagában nem használható, amint azt kés®bb részletesen indokolni fogjuk. Moduláris négyzetre emelés, a Rabin-függvény (mod 4), és � = �� . Legyen � és � ≡ 3 Amennyiben a faktorizációs probléma nehéz, akkor az �� (�) = �2 mod � 33 függvény az � egyirányú kiskapufüggvény. Nem invertálható, a kiskapu-információ felbontása, azaz � és �. Egy �

szám mind a négy ®sképe kiszámolható az � ≡ ±� (�+1)/4 (mod �) � ≡ ±� (�+1)/4 (mod �). kongruenciarendszer megoldásával. Erre a függvényre épül a Rabin-féle kriptorendszer Diszkrét logaritmus ben deniált � � Ha a diszkrét logaritmus probléma az 1.22 kísérlet- generátorra nézve nehéz, akkor a � -adrend¶, � által generált ciklikus csoportbeli exponenciális függvény, azaz az � : Z� �; � ↦ � � egyirányú permutáció, ahol az inverz függvény � −1 (�) = Dlog� (�). E függvény tehát nem egyirányú kiskapu-permutáció, de a DieHellmanleképezés féle ötlettel ilyen is konstruálható bel®le. Tekintsük az 1.24 kísérletben deniált � által � -adrend¶, � által generált ciklikus � csoportot, legyen � ∈ Z� olyan, � hogy a ℎ = � is generátora legyen �-nek (azaz � és � − 1 legyenek relatív prímek). Ekkor, ha a számítási DieHellman probléma

� -re nézve nehéz, Diffie–Hellman függvény generált akkor az ��,�,�,ℎ : � �; ℎ� ↦ � � függvény egyirányú kiskapu-permutáció. A kiskapu-információ az v®, a függvény inverze az ℎ� elemet rendeli.5 � kite−1 ��,�,�,� (�) = �� , mely tehát � � -hez a (� � )� = (� � )� = Kriptográfiai hash függvények Az egyirányú függvények egy különle- gesen fontos osztályát alkotják a kriptográai hash függvények (magyarítása hasító függvény). Egy � függvény hash függvény, ha � : {0, 1}* {0, 1}� . Fogalmazha- tunk úgy, hogy a hash függvény egy tetsz®leges véges hosszú sztringet adott 5 Megjegyezzük, itt az � ℎ � függvényt az értelmezési tartomány, azaz � elemeinek csak alakban megadott formáján tudjuk polinom időben végrehajtani. Ez a „szépséghiba” azonban nem akadályozza meg, hogy jól használható rejtjelező készüljön belőle. 34

hosszúságúra tömörít, vagy hogy róla adott hosszúságú lenyomatot készít. � Ha � : {0, 1} {0, 1}� , ahol � > �, akkor x hosszú hash függvényr®l beszélünk. Hash függvényeket használnak az adatok számítógépes tárolásában, kezelésében. A hash-tábla egy olyan rögzített méret¶ táblázat, mely az tumra vonatkozó valamilyen adatot a táblázat az üres, ahol � �(�)-edik � és � objek- cellájába tesz, ha � függvény, ha �(�) = �(�) két külön- a hash függvény. Nyilván akkor jó egy ilyen ritkán fordul el® ütközés, azaz ritkán esik meg, hogy böz® � objektumra. A kriptográai (vagy kriptográailag biztonságos) hash függvényekre sokkal er®sebb kikötéseket kell tennünk, nem elég, hogy ütközés ritkán forduljon el®, hanem nehézzé (a gyakorlatban reménytelenné) kell tenni, hogy egy támadó egy ütköz® párt szándékosan találhasson. Az ilyen hash függvényeket

ütközésállónak fogjuk nevezni. A kriptográai, tehát ütközésálló hash függvény deníciójában függvények egy családját fogjuk deniálni. A függvényeket egy kulccsal indexeljük, ez a kulcs azonban nem a titokban tartandó kulcsot jelenti, csak a függvények megkülönböztetésére szolgál. A kulcsot pedig a szükségleteknek megfelel®en választjuk, nem feltétlenül egyenletes eloszlás szerint véletlenszer¶en. Szokás az így deniált hash függvényt kulcsolt hash függvénynek is nevezni. 1.32 definíció Hash függvényen (hash függvények egy családján) egy olyan véletlen polinomidej¶ algoritmusokból álló 1. � ← �(1� ), � = (�, ℋ) párt értünk, ahol azaz a biztonsági paraméter függvényében � generál egy kulcsot, 2. van olyan � polinom, hogy ℋ a � és �(�) függvényében tetsz®leges � ∈ {0, 1}* sztringhez egy {0, 1}�(�) -beli sztringet rendel, melyet �� (�)-szel jelölünk. Nem fog

zavart okozni, ha �� -ra, mint {0, 1}* {0, 1}�(�) függvényre te� (�) kintünk. � -t x hosszúságú hash függvénynek nevezzük, ha � ∈ {0, 1} , � (�) �(�) azaz �� : {0, 1} {0, 1} , ahol � (�) > �(�). A hash-függvény kriptográai alkalmazhatóságához szükséges, hogy a függvény ütközésálló (további elnevezések: ütközés-ellenálló, ütközésmentes, collision resistant ) legyen, mely azt � sztringet, melyre �� (�) = �� (�). jelenti, hogy nehéz találni két olyan � = (�, ℋ) hash polinomidej¶ � algoritmusra 1.33 definíció A függvény véletlen  melynek inputja a 35 � és ütközésálló ha tetsz®leges � által generál � kulcs, kimenete egy (�, �) pár , létezik olyan elhanyagolható � függvény, hogy P[�� (�) = �� (�)] 6 �(�). �� függvény szükségképha ismerünk egy (�, �� (�)) párt, akkor nehéz hogy hash értéke,

azaz �� (�) ne változzék (erre A denícióból egyrészt világos, hogy egy ilyen pen egyirányú, másrészt megváltoztatni �-et úgy, a tulajdonságra használják a gyenge ütközésálló, második ®skép ellenálló, angolul a second preimage resistant kifejezéseket). Az ütközésálló hash függvények számtalan kriptográai protokollban kapnak szerepet, a hitelesítési eljárásokban, így a nyílt kulcsú rejtjelezésben is nélkülözhetetlenek. A Diffie–Hellman hash függvény A DieHellman függvényb®l konst- ruálható ütközésálló hash függvény, mely szerepet kap az ElGamal kriptorendszer bizonyos változataiban is. 1.34 konstrukció (DieHellman hash függvény) Tekintsük az 124 kísérletben deniált � (�, �, �) ← �(1� ), � = (�, �, �, ℎ) a � = (� ′ , ℋ) algoritmust. Legyen legyen ℎ←� egy véletlen elem, és legyen hash függvény ′ deníciójában szerepl® � generátor

algoritmus kimenete, azaz a kulcs. A ℋ algoritmus eredménye legyen �� : Z� × Z� �; (�, �) ↦ � � ℎ� . Az így deniált hash függvényt DieHellman hash függvénynek nevezzük. Ha a diszkrét logaritmus probléma nehéz az 1.22 kísérletben definiált � algoritmusra nézve, akkor az 134 konstrukcióban megadott Diffie– Hellman hash függvény ütközésálló. 1.35 tétel 1.5 Támadások az RSA-függvény ellen Az egyirányú (kiskapu)függvények és permutációk elleni támadáson mindazoknak a körülményeknek és lehet®ségeknek az áttekintését értjük, amelyek mellett megsz¶nik a jelölt függvény egyirányúsága. A legtöbb és legérdekesebb támadás az RSA-függvény ellen készült, ezekre koncentrálunk mi is 36 Amikor � kicsi � választása mellett az szól, hogy ekkor igen gyors a � rejtjelezés. Ekkor azonban az � (�) = � mod � függvény könnyen invertál√ 3 ható, ha � és � is kicsi.

Például ha � = 3, és � < � , akkor � = �� = �3 < � , így Kis � -ból � egy egészek fölött elvégzett egyszer¶ köbgyökvonással megkapha- tó. Coppersmith a fenti elemi példának egy mély, és sok alkalmazással rendelkez®, bizonyításában az LLL-algoritmusra épít® általánosítását bizonyította: Legyen � pozitív egész, � ∈ Z[�] egy �edfokú polinom, és � = � , ahol � > 0. Ekkor az összes olyan � hatékonyan megtalálható, amelyre |�| < � és � (�) mod � = 0 A futási idő az LLL-algoritmusnak egy �(min( 1� , log � ))-dimenziós rácson való futási idejétől függ. 1.36 tétel (Coppersmith, 1997) 1/�−� Mindennek ellenére van az RSA-függvényre épül® rejtjelez®nek olyan implementációja, ahol � = 3, Kis � közös üzenettel �2 , �3 három páronként � de így természetesen garantáltan nem kicsi. Az egyszer¶ség kedvéért legy � = 3, és legyen �1

, relatív prím egész. A �� = �3 mod �� , � = 1, 2, 3 függvényértékekb®l  bár külön-külön nem tudnánk megkapni � értékét, e három egyenletb®l már igen, ugyanis a kínai maradéktétel szerint van olyan �* < �1 �2 �3 = � egész, melyre �* ≡ �1 �* ≡ �2 �* ≡ �3 De mivel (mod �1 ) (mod �2 ) (mod �3 ) �* = �3 mod � , � < �� (� = 1, 2, 3), ezért �3 < � * . Tehát ismét egy egyszer¶ egészek fölötti köbgyökvonás segít. Hastad támadása ha a közös Az el®z® gyenge megoldás látszólag könnyen javítható, � érték elé megkülönböztet® jelzést, paddinget teszünk, pl. legyen �� = (� · 2� + �)3 mod �� , Meglep® módon ekkor is meghatározható � a � = 1, 2, 3 �� értékekb®l. S®t, még akkor is, ha �� = (�� (�))� mod �� , 37 � = 1, 2, . , � ahol �� mindegyike polinom és � elegend®en nagy.

Az alábbi egészen általá- nos eredmény fontos kriptográai következménye, hogy a paddingnek mindig véletlennek kell lennie. Legyen �1 ,. ,�� páronként relatív prím és jelölje �min közülük a legkisebbiket. Legyen �� ∈ Z�� [�] legföljebb �-edfokú polinom (� = 1, . , � ) Tegyük fel, hogy egyetlen olyan � < �min létezik, hogy 1.37 tétel (Hastad) �� (�) ≡ 0 (mod �� ) minden � = 1, 2, . , � indexre Ha � > �, akkor � hatékonyan meghatározható az (�� , �� ) párok ismeretében. E tétel egyszer¶en fogalmazva azt mondja, hogy egyváltozós polinomkongruenciák relatív prím modulusok mellett megoldhatóak, ha elegend® számú kongruencia áll rendelkezésre. Ezt az RSA-függvény invertálásához a következ®képp használhatjuk. Te- ��� ,�� RSA-függvényeket (� = 1, 2, . , � ) Kiszámoljuk az �� = ��� ,�� (�� (�)), ahol a �� polinomok

alkalmazásával kívánjuk megakadályozni � �� kiszámíthatóságát a �� értékekb®l. Legyen �� = �� − �� mod �� Az el®z® tétel szerint ha � > max� (�� deg �� ), akkor e kongruenciarendszer megoldható, kintsük az tehát az RSA-függvényekb®l még ilyen módosítással is felfedhet® a kiértékelésre szánt közös Amikor � �. kicsi Ahogy kis � � a dekódoló futási idejét � = �� szám ismeretében meg- a rejtjelez®, kis csökkenti. Meglep® módon, csak az � szerezhet® a kiskapu-információ, azaz és az �, ha az kicsi. Ha � = �� , � < � < 2� és � < és � ismeretében � polinom időben meghatározható. 1.38 tétel (Wiener, 1990) 1 3 √ 4 � , akkor � � Az algoritmus arra a számelméleti tételre épít, hogy ha az törthöz � � létezik olyan tört, hogy � ⃒ ⃒ ⃒� ⃒ ⃒ − �⃒ < 1 , ⃒� � ⃒ �2 � � tört csak az

lánctörtalakjának egy szelete lehet. A � � fenti egyenl®tlenség pedig könnyen bizonyítható a tétel feltételeib®l. � Az lánctörtalakja összes szeletének végigpróbálása hatékonyan elvégez� √ √ 1 4 het®  tapasztalatok szerint még a � -es korlát fölött, de azért � alatt. 3 (A fels® korlát pontos meghatározása nyitott kérdés.) és � < �, akkor a 38 Amikor � kicsi – gyökös támadás Az világos, hogy ha �-r®l tudjuk, � -elem¶ halmazba esik, akkor � -ben lineáris lépésben az � = � (�) értékb®l meghatározhatjuk �-et. Tegyük fel, hogy tudjuk, 0 6 � < � � ötletes algoritmus √ = 2 , azaz � egy legföljebb �-bites szám. A következ® � lépésben nagy valószín¶séggel megtalálja a � = �� mod � rejtett szöveg ismeretében �-et! Az ötlet sok egyéb támadásnak is alapötlete. hogy egy adott input: a nyilvános kulcs output: �, ahol (�, �); a rejtett

szöveg �; � mod � = � és � hossza �. a szöveg hossza � � � ← ( 12 , 1) � = 2�� for � = 1 to � do �� = ��� mod � end (�, �� )|� �=1 a második elemek szerint for � = 1 to � do if �� mod � = �� valamelyik � -re then return � · � mod � sort end end 5. algoritmus: Gyökös támadás az RSA-függvény inverzének kiszámítására � Ha választunk egy véletlen � < 2 üzenetet, akkor nagy valószín¶séggel �� van két olyan 1 < �, � 6 2 egész, hogy � = � · �. Így � ≡ �� ≡ � � · � � (mod � ), �/�� ≡ �� (mod � ). Az algoritmus idejéb®l �(�2�� ) lépés a rendezéshez, �(�) lépés a bináris kereséshez kell 80 Ez rendkívül er®s támadás, ha belegondolunk, egy 2 bites �-b®l képzett � = � (�) invertálása kimerít® kereséssel a mai technikai körülmények közt 40 belátható id®n belül kivitelezhetetlen,

viszont 2 lépés már nem! azaz Közös modulus Két különböz® RSA-függvénynek nem szabad közös mo- dulust választani, mert az egyik kiskapu-információját ismerve a másik is 39 ��,�� RSA-függvények �� értékeit, és csak egyikük, kiskapu-információját, pl. �1 -et, akkor abból az összes többit is ki tudjuk számolni, hisz �1 �1 ≡ 1 (mod �(� )), ahonnan � felbontása, abból pedig a többi függvény �� -értéke (� = 2, 3 . ) kiszámolható Kérdés, egy tulajdonos használhat-e egy modulushoz különböz® �� -ket? A megszerezhet®. Ugyanis ha � = �� , és ismerjük az válasz erre is határozott nem! Az RSA-függvény egyirányú kiskapu-permutáció �� = ��,�� (�) értékeket relatív prím �1 és �2 �1 és �2 relatív prímek, ezért létezik ��1 + ��2 = 1, így viszont volta azonnal megsz¶nik, ha az kitev®vel is hozzáférhet®vé válnak. Mivel olyan � és �,

hogy ��1 ��2 = ���1 ���2 = ���1 +��2 ≡ �1 = � mod �. Megváltoztathatóság � Ha csak annyit tudunk, hogy argumentuma egy olyan tathatjuk � � � = � (�) = �� mod érték, mely egy számadat, akkor megváltoz- értékét úgy, hogy a változás hatását el®re ki tudjuk számolni. Például ha azt tudjuk, hogy � egy árajánlat, akkor ugyan nem tudjuk meg mennyi az �, de alá tudunk ígérni, ha ugyanis 19 � � · ( 20 ) mod � dekódolás után 0.95�-et ad Implementációk elleni támadások � 5%-a egész szám, akkor Egy-egy egyirányú függvény megva- lósítása valamely valós rendszerben sok olyan támadásra ad lehet®séget, melyek az implementációval kapcsolatosak. Ezek egy része kinomult m¶szaki megoldásokra épít, de az ezek elleni védelem nem szükségképpen m¶szaki megoldást igényel. Itt csak két egyszer¶ támadást említünk. A legfontosabb, leggyakoribb, és bizonyos

esetekben igen hatékony az id®méréses (timing) támadás. Ez nem csak az egyirányú függvények ellen, de szinte bármilyen kriptográai protokoll ellen m¶ködik, ahol egy program futási ideje, korrelációba kerülhet érzékeny adatokkal. Például az RSA-függvény dekódolásakor alkalmazott moduláris hatványozásban használt � kitev®, bitr®l bitre kitalálható a dekó- dolónak küldött  megfelel®en kiválasztott  üzenetek visszafejtésére fordított id®b®l. Az egyik általánosan elterjedt védekezés ez ellen a vakítás. A vakításnál � -t emeli �-edik hatványra, hanem választ egy � � = ��� mod � számot hatványozza, mely a támadónak � � már ismeretlen. Ekkor a számítás � = � � mod � , vagyis a keresett � = � � � mod � számot a � /� mod � képlet adja. a dekódoló nem a kapott véletlen számot, és a 40 Természetesen lehet próbálkozni azzal is, hogy minden programrész úgy

legyen megírva, hogy semelyik futási ideje se kerüljön korrelációba érzékeny adatokkal. Ilyesmi elérhet® pl felesleges ciklusok beszúrásával, melyek révén elérhet®, hogy a program mindig azonos ideig fusson. Ha támadónak nem csak a futási id®t, de az elektronikus eszköz áramfelhasználását, vagy bármely más zikai  id®ben változó  jellemz®jét mérni tudja, további támadási lehet®ségekhez jut! Még érdekesebb és veszélyesebb a helyzet, ha a támadó be is tud avatkozni az eszköz m¶ködésébe. Az ilyen támadások egyike, mely pl smart kártyákon viszonylag könnyen megvalósítható, RSA-függvény kiskapu-információjának megszerzése futási hiba okozásával. Az 1.4 példa (c) pontjában, illetve az 1.19 példában láttuk, hogyan lehet moduláris hatványozást a kínai maradéktételre építve kiszámolni Tegyük fel, hogy egy támadó annyira nyomon tudja követni egy smart kártya m¶ködését, hogy tudja mikor számolja ki az

�� = � �� mod �, illetve az �� = � �� mod � értékeket. Elég e számolás közben valamilyen gyors küls® beavatkozással megzavarni a program m¶ködését! Tegyük fel, hogy �� korrekt, de �¯� nem, azaz a bel®lük kiszámított �¯ sem korrekt, nevezetesen �¯� ≡ � (mod �), Ebb®l pedig következik, hogy de �¯� ̸≡ � gcd(�, �¯� −�) = �. (mod �). Ezzel pedig hozzájutottunk a kiskapu-információhoz. 1.6 Ciklikus csoportok az elliptikus görbéken Az eddigi számításainkat, akár a moduláris aritmetikára, akár a diszkrét logaritmus problémára gondolunk, mindig valamely ciklikus csoportban végeztük. A ciklikus csoportok egy kriptográai szempontból különösen fontos osztályával ismerkedünk meg, melyek az elliptikus görbék segítségével deniálhatók. Fontosságukat az adja, hogy a diszkrét logaritmus problémára e csoportban eddig nem ismerünk szubexponenciális

algoritmust, míg a moduláris aritmetika ciklikus csoportjaiban igen. 41 Elliptikus görbék nem 3. 6 Legyen F egy test, melynek karakterisztikája nem Tipikus alkalmazásokban e test az F� véges test, ahol �, � ∈ F olyan, hogy 4�3 + 27�2 ̸= 0. Az �>3 2 és prím. Legyen � 2 = �3 + �� + � egyenletet kielégít® nevezett � (6) (�, �) ∈ F × F pontok, valamint egy végtelen távolinak 7 3 2 pont halmaza elliptikus görbét alkot . A 4� + 27� ̸= 0 kikötés azt biztosítja, hogy az elliptikus görbén ne legyen ún. szinguláris pont, azaz 3 hogy az � + �� + � = 0 egyenletnek ne legyen többszörös gyöke. El®ször két valós test fölötti elliptikus görbe ábráját mutatjuk (ld. 1 ábra), majd három F11 fölötti görbéjét, melyek pontjait 11×11-es négyzetrácson ábrázolunk (ld. 2 ábra) Az utóbbi ábrán látható piros pontok a végtelen távoli � pontot ábrázolják, a pontok közt futó

vonalak magyarázatát kés®bb adjuk meg. 2 Az � = esetben �3 + �� + � egyenletb®l világos, hogy a függvény grakonja valós szimmetrikus az �-tengelyre. Ha véges test fölötti elliptikus görbét egy négyzetrácson ábrázolunk, akkor ez a szimmetriatulajdonság megmarad, �−1 , . , −1, 0, 1, , �−1 } elemekkel reprezentálamennyiben Z� elemeit a { 2 2 juk. Saját ábráinkon inkább a Z� = {0, 1, , � − 1} reprezentációt választottuk, így az (�, 0) alakú pontok kiesnek a szimmetriából. A végtelen távoli pont: affin és projektív koordináták sík legyszer¶bben úgy modellezhet®, hogy a 3-dimenziós A projektív tér origón átmen® egyeneseit tekintjük a projektív sík pontjainak, és az origón átmen® síkokat a projektív sík egyeneseinek. Egy origón átmen® egyenest bármely irányvektorával jellemezhetünk, tehát az [�, �, �] vektor és a [��, ��, ��] vektor (� ̸= 0) ugyanazt az

egyenest  vagyis a projektív síknak ugyanazt a pontját  hatá- [�, �, �] vektornak megfelel egy projektív pont, kivéve a � ̸= 0, akkor végigosztva vele, az [�/�, � /�, 1] vektort kapjuk, mely a � = 1 egyenlet¶ sík egy pontjába mutat, vagyis ezek a pontok megfeleltethet®k egy an sík pontjainak. Ezt az [�, �, 1] ↔ (�, �) megfeleltetéssel fejezzük ki Ha egy projektív pont koordinátás alakja [�, �, 0], akkor rozza meg. Minden nullvektort. Ha 6 Az elliptikus görbék tárgyalása némileg különbözik e két karakterisztikára. Ugyan a 2karakterisztikájú, tehát 2-hatvány elemű testekre épített elliptikus görbéket is használják kriptográfiai célokra, az utóbbi időben ellenük talált bizonyos támadások okán ezeket itt nem fogjuk tárgyalni. 7 Elliptikus görbéket más alakú egyenletekből is kaphatunk, nekünk azonban ez a spe- ciális, ún. Weierstrass-alak mindenre elég lesz 42 1. ábra Valós test

fölötti � 2 = �3 − 4� és � 2 = �3 − 2� + 4 egyenlet¶ elliptikus görbék grakonjai a �=1 egyenlet¶ sík egyik pontja sem feleltethet® meg e pontnak: az ilyen pontokat nevezzük végtelen távoli vagy ideális pontoknak. Ha az � 2 = �3 + �� + � (7) � 2 � = � 3 + ��� 2 + �� 3 (8) egyenlet helyett az �= ̸ 0 esetén, � 3 -bel való leosztás (︂ )︂2 (︂ )︂3 (︂ )︂ � � � = +� +� � � � egyenletet tekintjük, akkor után az a (7) egyenlettel. Ha viszont = �, �� = � helyettesítés után megegyezik � = 0, akkor � -nek is 0-nak kell lennie, így a ̸= 0) megfelel® végtelen távoli pont is kielégíti a (8) egyenlethez jutunk, ami az [0, �, 0] vektoroknak (� � � egyenletet. Ezt a végtelen távoli pontot �-val jelöljük, és úgy tekintjük, hogy ez is rajta van a (7) egyenlettel megadott elliptikus görbén. 43 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5

(�) � 2 = �3 + 2� + 4 (�) � 2 = �3 − 4� 6 7 8 9 10 0 1 2 3 4 5 (�) � 2 = �3 + � + 1 2. ábra Az F11 = Z11 test fölötti három különböz® elliptikus görbe gra- (�) a görbének 17 pontja van (a pontm¶velet csoportja 17 elem¶ (�) a görbe 12-elem¶ (csoportja egy 6 elem¶ ciklikus és egy 2-elem¶ ciklikus csoport direkt szorzata), (�) a görbe 14-elem¶ (csoportja ciklikus, melynek van egy nagy prímelem¶  nevezetesen 7-elem¶  ciklikus részcsoportja). Mindhárom ábrán a tengelyeket −5-t®l 5-ig számoztuk, de mivel Z11 elemeit szívesebben jelöljük a 0-tól 10-ig terjed® számokkal, a tengelyeken is e számokat használtuk, tehát −5 = 6,. , −1 = 10 Az ábrán látható piros konja: ciklikus), pontok a végtelen távoli pontot jelölik, a pontokat összeköt® színes vonalak a pontok egy ciklikus sorrendjét adják meg a következ®kben bevezetend® pontm¶veletre nézve. 44 Például az F11 fölötti � 2 =

�3 + 2� + 4 egyenlet¶ elliptikus görbe pont- halmaza (2. (a) ábra) an koordinátás alakú pontokkal megadva: � ∪ {(3, 2), (6, 1), (7, 3), (10, 10), (2, 7), (9, 6), (8, 2), (0, 9), (0, 2), (8, 9), (9, 5), (2, 4), (10, 1), (7, 8), (6, 10), (3, 9)}. Ugyanennek a görbének a pontjai projektív koordinátákkal  a pontokat azonos sorrendben felsorolva: {[0, 1, 0],[3, 2, 1], [6, 1, 1], [7, 3, 1], [10, 10, 1], [2, 7, 1], [9, 6, 1], [8, 2, 1], [0, 9, 1], [0, 2, 1], [8, 9, 1], [9, 5, 1], [2, 4, 1], [10, 1, 1], [7, 8, 1], [6, 10, 1], [3, 9, 1]}. Pontművelet az elliptikus görbén Az elliptikus görbe egy szép tulaj- donsága, hogy minden egyenes, mely két pontban metszi (a metszetszámot multiplicitással számolva), metszi azt egy harmadik pontban is. A 3 ábra bal grakonja azt mutatja, hogy ha � és � a görbe két különböz® pontja, akkor a rajtuk átmen® egyenesen lév® harmadikat összegén ennek �-tengelyre �-rel � és � � = �, akkor

jelölve, a való tükörképét fogjuk jelölni. Ha az összeköt® egyenesen az érint®t kell érteni. Két olyan pont, melyek egymás tükörképei, a végtelen távoli pontban metszik a görbét, mely megegyezik az � -tengelyen lév® ideális ponttal. A klasszikus algebrai geometria elemi ismeretei közé tartozik, hogy e m¶velettel az elliptikus görbe pontjai kommutatív csoportot alkotnak, azaz e m¶velet kommutatív, asszociatív, invertálható, zéruseleme az � pont. Az asszociativitás geometriai eszközökkel szépen igazolható, a többi azonosság bizonyítása egyszer¶, de itt mell®zzük. Legyen � = (�1 , �1 ) és � = (�2 , �2 ) az ℰ elliptikus görbe két tetsz®leges an pontja. Három esetet különböztethetünk meg: 1. �1 ̸= �2 , 2. �1 = �2 és �1 = −�2 , 3. �1 = �2 és �1 = �2 . Az 1. esetben legyen a két ponton átmen® egyenes egyenlete Az egyenes iránytangense �= �2 − �1 , �2

− � 1 45 � = �� + � . � � � � � −� 2� � +� 3. ábra � + �, 2� = � + � és −� megszerkesztése és � = �1 − ��1 = �2 − ��2 . Az elliptikus görbe és az egyenes metszéspontja kielégíti az (�� + �)2 = �3 + �� + � egyenletet, azaz harmadfokú egyenletalakba rendezve �3 − �2 �2 + (� − 2��)� + � − � 2 = 0. �2 (az �2 �2 , ezért a A gyökök és együtthatók összefüggése szerint a gyökök összege együtthatójának −1-szerese), és mivel a másik két gyök �1 és harmadik �3 = � 2 − � 1 − �2 . Ha � +� koordinátás alakja (�3 , �3 ), van, ahonnan �= akkor az egyenesen az −�3 − �1 , �3 − � 1 ahonnan �3 = �(�1 − �3 ) − �1 . 46 (�3 , −�3 ) pont A 2. esetben � + � = �. Ez az elliptikus görbe projektív alakjából könnyen ellen®rizhet®, ennek részletezését

mell®zzük. Az utolsó, 3. esetben � = �, így az érint® egyenletére van szükségünk ′ Valós test fölött � = � , de a deriválási szabályokat formálisan értelmezve ugyanez a módszer m¶ködik véges testek fölött is. A 7 egyenlet deriválásával kapjuk, hogy 2�� ′ = 3�2 + �. � koordinátáit behelyettesítve kapjuk, hogy �= 3�21 + � . 2�1 Innen a többi formula azonos az els® esetben megkapottakkal. Végül már csak azokat az eseteket kell áttekinteni, amikor legalább az egyik pont a végtelen távoli � pont. A pontok projektív alakjából azonnal adódnak a következ® összefüggések: �+� =� � + � = �, � − � = �, (�, �) ∈ ℰ esetén (�, �) + � = (�, �) bármely (�, �) ∈ ℰ pontra − (�, �) = (�, −�) azaz bármely azaz {0, 1, . , � − 1} számokkal reprezentált F� test esetén úgy kell érteni, hogy −(�, �) = (�, � − �). Azt kapjuk tehát,

hogy az ℰ elliptikus görbe pontjai a fönt bevezetett pontm¶velettel additív csoportot alkotnak, amit szokás az ⟨ℰ, +⟩ jelöléssel Az utóbbi összefüggést az kifejezni. Ráadásul láttuk, hogy e m¶velet eredménye igen egyszer¶ képletekkel igen gyorsan számolható Az elliptikus görbe csoport E csoport mérete és struktúrája is megha- tározható. Méretére a híres  nem triviális  Hasse-tétel ad becslést, mely szerint az F� fölötti ℰ elliptikus görbe pontjainak száma: √ √ � + 1 − 2 � 6 |ℰ| 6 � + 1 + 2 �. A pontos érték a hatékony Schoof-algoritmussal számolható. Ha ℰ egy F� fölötti elliptikus görbe (� porthoz létezik két olyan �1 és �2 > 3), szám, hogy ⟨ℰ, +⟩ ∼ = Z�1 × Z�2 , 47 akkor a rajta deniált cso- ahol �2 | �1 és �2 | (� − 1). A csoport struktúrájára tehát néhány különböz® esetet tudunk fölsorolni. Ha �2 = 1, akkor a csoport

ciklikus! Szerencsés esetben akár prímrend¶, ami azért érdekes, mert a diszkrét logaritmus problémához prímrend¶ csoportot használunk. A 2 ábrán az els® görbe 17 pontos, így csoportja izomorf Z17 -tel. Elemeit az egyik ciklikus sorrend szerint fölsorolva: Z17 ∼ = ℰ = {�,(3, 2), (6, 1), (7, 3), (10, 10), (2, 7), (9, 6), (8, 2), (0, 9), (0, 2), (8, 9), (9, 5), (2, 4), (10, 1), (7, 8), (6, 10), (3, 9)}, azaz (3, 2) egy generátorelem. � 2 = �3 + � + 1 az generátoreleme (1, 6): A harmadik elliptikus görbe, melynek pontú, csoportja izomorf Z14 -gyel, egyik egyenlete, 14 Z14 ∼ = ℰ = {�,(1, 6), (3, 8), (8, 9), (6, 6), (4, 5), (0, 1), (2, 0), (0, 10), (4, 6), (6, 5), (8, 2), (3, 3), (1, 5)}, E csoportból kiválasztható egy 7-edrend¶ � részcsoport: Z7 ∼ = � = {�, (3, 8), (6, 6), (0, 1), (0, 10), (6, 5), (3, 3)}, (9) Egy primitív elemet és azok többszöröseit egy vékony piros vonal mentén végig követhetjük a végtelen

távoli pontból, azaz a zéruselemb®l indulva, és végül oda érkezve. (Emlékeztetünk rá, hogy e csoport additív, azaz a m¶velet az összeadás, nem a szorzás, így a generátorelemnek nem a hatványait, hanem a többszöröseit kell számolnunk. A moduláris hatványozás technikája minden probléma nélkül átvihet® skalárral szorzásra.) E példában a 14-edrend¶ csoport 7-edrend¶ részcsoportjának elemeit kékkel jelöltük, a többit halványabb színnel különböztettük meg. 2 3 A második grakonon látható � = � − 4� egyenlet¶ elliptikus görbe két ciklikus csoport direkt szorzata, az egyik ℰ Z2 Z6 és valóban, 2 | 12 2-elem¶, a másik 6-elem¶: ∼ = Z2 × Z6 , ∼ = {�, (2, 0)}, ∼ = {�, (4, 2), (4, 9), (9, 0), (10, 5), (10, 6)}, és 2 | 6. 48 Erős és biztonságos prímek Az összes konstrukcióban fontos szerepet játszik a prímek megfelel® kiválasztása. Bármelyik rendszer elleni jöv®beni támadás

lehet®sége függhet a megfelel® prímek kiválasztásától. Az ismert támadások  akár a faktorizációs, akár a diszkrét logaritmus ellen  közt vannak olyanok, amelyek sikerét csökkenti, ha a prím úgynevezett biztonságos vagy ha er®s prím. A � prím biztonságos (safe prime ), ha � = 2� + 1 alakú, ahol � is prím. Ezek a diszkrét logaritmus problémában fontosak. Az 500 alatti biztonságos prímek: 5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479 (a sorozat sorszáma a sorozatok OEIS katalógusában A005385) A � erős prím, ha 1. (� − 1)-nek van egy nagy prím, és � pozitív egész, 2. (�1 − 1)-nek is van nagy prím, és � pozitív egész, 3. � + 1-nek is van nagy prímfaktora, azaz � = ��3 − 1, ahol �3 és � pozitív egész. � = ��1 + 1, ahol �1 nagy �1 = ��2 + 1, ahol �2 nagy prímfaktora, tehát prímfaktora, azaz nagy prím, A biztonságos prímek

és az er®s prímek kapcsolata világos, hisz � = 2� +1 esetén az er®s prímekre vonatkozó els® feltétel teljesül. A faktorizáció elleni támadásokban valójában nem nyújt nagy segítséget, ha a két prím er®s prím, mert bár a Pollard � algoritmus ellen véd, de az újabb és er®sebb számtest szita, és a Lenstra elliptikus görbe faktorizációs módszere ellen nem. Mindennek ellenére akad olyan szabvány, mely az RSAhoz er®s prímek választását javasolja, általában azonban a szabványok ezt nem írják el®, úgy t¶nik, szükségtelen RSA-hoz er®s prímeket választani. A diszkrét logaritmus probléma esetén más a helyzet. PohlingHellmantétele szerint, ha �−1 minden prímosztója kicsi, akkor polinom id®ben ki- számolható a diszkrét logaritmus. Ez annak következménye, hogy a Pohling ∏︀ �� Hellman- vagy SilverPohlingHellman-algoritmus futási ideje az � = � �� )︀ (︀∑︀ √ �� ) . Így minden

diszkrét logaritmus problémára számra � � �� (log � + épül® kriptográai rendszer esetén legalább � − 1-nek kell, hogy legyen nagy prímosztója. A gyakorlatban biztonságos prímeket szoktak választani A SECG csoport keretében a Certicom cég által a paraméterválasztáshoz adott javaslatok szerint a diszkrét logaritmus problémára épül® elliptikus görbéhez olyan ki kell elégítse � választandó, melyre � − 1 és � + 1 legnagyobb � 19 a log� (�) > feltételt. 20 49 prímfaktora 2. A nyílt kulcsú titkosítás alapfogalmai 2.1 Előzmények, kezdetek Évszázadokon át a szimmetrikus kulcsú titkosítás volt maga a titkosítás, ahol a két kommunikáló fél mindegyikének birtokolnia és ®riznie kellett a kulcsot. E kulcs cseréje és ®rzése sok nehézséget okozott és okoz ma is Ezek megoldására az els® próbálkozások az 1970-es években születtek. Az els® aszimmetrikus algoritmust valószín¶leg 1973-ban

 az angol titkosszolgálatnál (Government Communications Headquarters, GVHQ)  James H. Ellis, Cliord Cocks és Malcolm Williamson készítette el. Ez az információ csak 1997-ben került nyilvánosságra. 1974-ben egy Merkle nev¶ diák egy szemináriumon olyan ötlettel állt el®, mely lehet®vé tenné a kulcscserét nyilvános csatornán. A remek ötlet gyengéje az volt, hogy a kulcscserét végz®k számítási igényének a négyzetével arányos id® alatt egy hallgatózó támadó meg tudta szerezni a kulcsot, és ez még nem t¶nt elég biztonságosnak. Az ötletet azonban Die és Hellman továbbfejlesztette, algoritmusukban már a négyzetes helyett exponenciális volt a két igény közti függvénykapcsolat. E kulcscsere-protokollokban megjelent az aszimmetria! Innen már csak egyetlen lépés volt az aszimmetrikus kulcsú titkosítás titkosszolgálaton kívüli feltalálása. Merkle’s puzzle Merkle ötlete a következ® volt: Aliz Bobbal kíván kom30

munikálni, amihez közös kulcsot kell találni. Aliz nagy számú, mondjuk 2 darab kulcsot generál, és mindegyiket titkosítva elrejti egy üzenetben: Az �-edik kulcs �� , ahol az � sorszám 1-t®l 230 -ig változik. A titkosítás azonban annyira gyenge, hogy bármelyik feltörhet® belátható id®n belül, mondjuk 30 néhány perc alatt! Ezután a különböz® kulcsokkal titkosított 2 darab szöveget Aliz véletlen sorrendben elküldi Bobnak, aki véletlenül választ közülük egyet, azt feltöri, és a nyilvános csatornán visszaküldi Aliznak közös kulcs �� � értékét. A lesz. A támadónak átlagosan a feladványok felét fel kell törnie, hogy megtudja, melyik az �-edik Diffie-Hellman kulcscsere üzenet és ezzel megtudja a �� kulcsot. Merkle ötletét tovább fejlesztve Die és Hell- man a következ® igen egyszer¶ protokollt találta ki: 2.1 konstrukció (DieHellman kulcscsere) Adva van az paraméter. 50 1� biztonsági

� algoritmussal el®állít egy �-edrend¶ � ciklikus csoportot és annak egy � generátorelemét: (�, �, �) ← �(1� ). Egyenletes eloszlás szerint választ egy véletlen � ← Z� elemet, és kiszá� mítja a ℎ1 = � elemet, végül üzenetet küld Bobnak 1. Aliz: egy véletlen polinomidej¶ Aliz Bob : (�, �, �, ℎ1 ). 2. Bob: fogadja Aliz üzenetét, választ egy véletlen � ← Z� elemet, kiszá� � mítja ℎ2 = � és �� = ℎ1 értékét, végül üzenetet küld Bobnak: Bob Aliz : ℎ2 3. Aliz: fogadja Bob üzenetét, kiszámolja �� = ℎ�2 értékét. A protokoll lényege, hogy az Aliz és Bob közt zajló beszélgetést passzívan hallgató támadó ismeri (�, �, �, ℎ1 , ℎ2 ) elemeit, azonban ha ezekre a CDH- probléma nehéz, nem tudja kiszámolni a �� = ℎ�2 = (� � )� = � �� = (� � )� = ℎ�1 = �� értéket, amely Aliz és Bob közös kulcsa lesz a további

kommunikációhoz. Ennél több is igaz! Végezzük el azt a kísérletet a hallgatózó támadóval, hogy miután végighallgatta Aliz és Bob kulcscsere-kommunikációját, kap egy 1 1 valószín¶séggel egy véletlen bitsorozat, valószín¶séggel a kulcsot, mely 2 2 �� = �� kulcs. A támadó el®nye a kulcscsereprotokollal szemben �(�), ha 12 t®l �(�)-nel eltér® valószín¶séggel el tudja találni, hogy melyik a valódi kulcs Biztonságosnak fogjuk nevezni a Die-Hellman kulcscserét, ha bármely � hallgatózó támadóra ez az el®ny elhanyagolható. Ha a DDH probléma nehéz, akkor a Diffie-Hellman kulcscsere protokoll biztonságos egy hallgatózó jelenlétében. 2.2 tétel E protokollt szellemessége ellenére nem használják, mert ugyan a passzív hallgatózó ellen véd, de nem véd az aktív támadó ellen, aki képes Aliz és Bob üzeneteit fogadni, és magát Aliz számára Bobnak, Bob számára Aliznak kiadni. E támadás neve

man-in-the-middle Tehát e támadás tömören leírva: 1. Aliz: (�, �, �) ← �(1� ), � ← Z� , ℎ1 = � � , Aliz 2. Támadó: Támadó: (�, �, �, ℎ1 ). � ← Z� , ℎ� = � � , �� = ℎ�1 51 Támadó 3. Bob: (�, �, �, ℎ� ). Bob: � ← Z� , ℎ2 = � � , �� = ℎ�� = � �� Bob 4. Támadó: ℎ2 Támadó: � ← Z� , ℎ� = � � , �� = ℎ�1 = � �� , �� = ℎ�1 = � �� Támadó 5. Aliz: ℎ� Aliz: �� = ℎ�� = � �� . Így a Támadónak van Alizzal és Bobbal is egy-egy közös kulcsa, a köztük lév® kommunikációt kedvére módosíthatja magát Aliz felé Bobnak, Bob felé Aliznak kiadva. 2.2 Aszimmetrikus rejtjelező egyirányú kiskapu-permutációból El kell oszlatnunk egy közkelet¶ tévedést! Az egyirányú kiskapufüggvények önmagukban nem használhatók titkosításra úgy, hogy az egyirányú függvény a rejtjelez®, a

kiskapu-információ a titkos kulcs és a függvény inverze a dekódoló. De más nehézségekkel is szembe kell nézni nyílt kulcsú rejtjelez® konstrukciójakor. 1. Egy aszimmetrikus rejtjelez® E függvénye nem lehet determinisztikus, hisz az azonnal tönkreteszi a szemantikai biztonságot: ha a támadó is- E�� (�� ) értékeket is, így el tudja dönteni, hogy melyikük egyezik meg a � = E�� (�� ) kriptoszöveggel. Tehát E-nek véletlen algoritmusnak kell lennie! meri az �0 és �1 sztringeket, akkor ki tudja számolni az 2. Mivel az egyirányú kiskapufüggvények determinisztikusak, ha bel®lük akarunk aszimmetrikus rejtjelez® E algoritmust konstruálni, az argu- mentumuknak kell véletlennek lennie, tehát nem az üzenetre kell ®ket alkalmazni, hanem vagy egy véletlenül választott számra kell ®ket alkalmazni, vagy az üzenetek mellé véletlen üzenetet kell paddingbe tenni. 3. Abból, hogy az � egyirányú kiskapufüggvény

nehezen invertálható, nem következik, hogy az � = � (�) nem szerezhet® meg. Valahogy az �-r®l az � �-r®l semmi információ E nem determinisztikus! ismeretében az Így az sem elég, hogy ismeretén keresztül megszerezhet® információt is el kell rejteni, amihez ugyancsak a véletlent lehet segítségül hívni! 52 Els® próbálkozásként próbáljunk meg egy egyirányú kiskapu-permutációt használva rejtjelez®t konstruálni, melyben a tökéletes biztonságot nyújtó time pad one (OTP) is visszaköszön. 2.3 konstrukció (Aszimmetrikus rejtjelez®) Legyen (� TDP , �, � −1 ) az 1.31 de- níció szerinti kiskapu-permutációk egy családja. Deniáljuk a Π = (�, E, D) aszimmetrikus kulcsú, az 1.12 deníciónak megfelel® rejtjelez®t a következ®képp: 1. � : (�, �, �� ) ← � TDP (1� ), azaz választunk az egyirányú kiskapu-permutációk családjából egy (�, �) indexpárt, és megadjuk az

értelmezési tartományt. � választ egy � : �� �� hash függvényt, és publikálja a �� = (�, �� , �) nyílt kulcsot. A titkos kulcs az �� = (�, ��−1 ) lesz 2. E: � ← �� , E�� (�) = (�� (�), �(�) ⊕ �), �� × �� . 3. D: D�� (�1 , �2 ) = �(��−1 (�1 )) ⊕ �2 . Könnyen ellen®rizhet®, hogy tehát E�� : �� × �� D�� E�� (�) = �, ugyanis � = ��−1 (�1 ) és �(�) ⊕ �2 = �. Látható, hogyan épül e konstrukcióba korábban szerzett tudásunk: az egyirányú függvényt egy véletlenül választott elemre használjuk. E ponton folytathatnák a rejtjelezést úgy is, hogy a nyílt szöveget az OTP-hez hasonló módon � ⊕ �-mel rejtjeleznénk. nem itt és most kéne az �-et Ez tökéletes biztonságot nyújtana, ha is átadni. Azt csak úgy tudjuk átadni, hogy elhanyagolható eséllyel megszerezhet®, ezt nyújtja az

egyirányú �� kiskapu- permutáció. Csakhogy láttuk, az egyirányú permutációk nem biztonságosak abban az értelemben, hogy semmi információ ne lenne megszerezhet® az argumentumáról, azaz jelen esetben �-r®l. (Pl. láttuk, az RSA-függvény értékéb®l megmondható az argumentumának Jacobi-jele.) Ezért az � használata sem nyújt elég biztonságot az OTP-ben való használathoz, ezért egy véletlen függvénnyel el kell rejteni még azt a kevés információt madó megszerezhet róla. Erre szolgál a � �-r®l, amit egy tá- hash-függvény. Világos, hogy az egész rendszer biztonsága az egyirányú kiskapu-permutáció biztonságától (az inverz kiszámításának nehézségét®l) és a hash függvény véletlenszer¶ségét®l függ. 53 Véletlen orákulum A véletlen orákulum modell kriptográai rendszerek, protokollok biztonságának megfogalmazásában és bizonyításában segít. Azt fejezi ki, hogy a rendszer az adott

biztonsággal rendelkezik, amennyiben a véletlen orákulumot helyettesít® függvény valóban elég véletlenszer¶ módon m¶ködik. E fogalom használata azért terjedt el, mert egyrészt ∙ a mai kriptográai rendszerek nagy részének biztonsága nem bizonyítható precízen, mivel olyan számelméleti feltevésekre épül, amelyek mindmáig bizonyítatlanok, másrészt ∙ számtalan olyan kriptográai protokoll született/születik, amelyben kés®bb valaki biztonsági rést talál, azaz kiderül, hogy a rendszer könnyen támadható, de a támadás nem a bizonyítatlan számelméleti feltevések valamelyikének összeomlására épül, hanem egyszer¶en a konstrukció más elemei voltak rosszul kitalálva. Mindezek miatt nagy szükség van arra, hogy valahol a precízen, minden kétséget kizáróan bizonyított biztonság és a megérzésre biztonságos között találjunk olyan matematikailag precízen bizonyítható állításokat, amelyek pontosan

megfogalmazzák a bizonyított biztonság feltételeit. E feltételek egyike a nyílt kulcsú titkosításban használt makacs számelméleti probléma nehézsége! Világos, amint egy ilyen problémára találnak hatékony algorit- must, a rá épül® kriptográai rendszerek összeomlanak. A másik fontos, és gyakran el®forduló feltétel, az alkalmazott véletlen függvények, tipikusan a hash függvények közelsége a valódi véletlenhez. E feltétel kikerülésére használjuk a véletlen orákulum alkalmazását Ez úgy képzelhet® el, hogy van egy olyan képzeletbeli résztvev®je a protokollnak, aki minden neki küldött számra válaszul küld egy véletlen följegyez, így ha kés®bb ugyanaz az laszul ugyanazt az �-et � � számot, azonban minden üzenetváltást � érkezik, mint egyszer már korábban, vá- küldi. Mintha mindent följegyezne, és minden válasz el®tt megnézné a nagykönyvben, hogy nem kapta-e már valakit®l korábban ugyanezt a

számot. A véletlen orákulum modell legf®bb gyengéje, hogy a valóságban a véletlen orákulum helyén egy hash függvény van, amely nem csak hogy determinisztikus, de többnyire a támadó el®tt ismert, ezért el®re tudhatja annak válaszát bármely bemenetre, s®t elemezheti annak programkódját is! Mindennek ellenére mára alapvet®vé vált, hogy a kriptográai protokollok biztonsága legalább ilyen szinten bizonyítva legyen. A nyílt kulcsú titkosítás fönti deníciójáról a következ® tétel bizonyítható: 54 Amennyiben az egyirányú kiskapu-permutációk (� TDP , �, � −1 ) családjában az inverz kiszámítása a kiskapu-információ ismerete nélkül nehéz, és a 2.3 konstrukcióban definiált Π = (�, E, D) rejtjelezőben � -t véletlen orákulummal helyettesítjük, akkor Π szemantikailag biztonságos. Egyszerűen fogalmazva: a fenti rejtjelező szemantikailag biztonságos a véletlen orákulum modellben. 2.4 tétel Bizonyítás.

Megmutatjuk, hogy ha a véletlen orákulum modellben létezik egy olyan � véletlen polinomidej¶ algoritmus, mely nem elhanyagolható valószín¶séggel cáfolja Π szemantikai biztonságát, akkor létezik olyan hatékony ℬ algoritmus is, mely nem elhanyagolható valószín¶séggel invertálja � -et, azaz � nem egyirányú. Megmutatjuk tehát, hogy ha van olyan �, melyre ⃒ ⃒ ⃒ ⃒ 1 indCPA indCPA Adv�,Π (�) = ⃒⃒P[Exp�,Π (�) = 1] − ⃒⃒ = �(�) 2 nem elhanyagolható, akkor van olyan ℬ algoritmus, melyre P[� (ℬ(1� , �, �)) = � (�)] > �(�). � helyébe fogja jelölni (RO a random oraculum E bizonyításhoz magunk deniálunk egy orákulumot, melyet a helyettesítünk. Ezt az algoritmust ℋRO kifejezésb®l). Legyen tehát �0 és �1 a két üzenet, E�� (�� ) = (�1 , �2 ), ahol � egy véletlen bit. melyekre Az � |�0 | = |�1 |. algoritmus az Legyen ExpindCPA �,Π (�) nyílt szöveg

megkülönböztethetetlenségi kísérlet közben sokszor meghívja a � -t, vagyis e modellben lefuttatja a A ℋRO ℋRO algoritmust. algoritmus egy listában följegyez minden hozzá beérkez® ket, ennek a listának a neve RL lesz, míg a visszaadott ℋRO (�) � érté- értékeket egy másik, HL nev¶ listába jegyzi. Így valóban orákulumként fog tudni viselkedni, hisz emlékezni fog minden korábbi hívására Ha véletlenül egy olyan � -et RO kap, melyre ℋ (�) = � , és � még nem szerepel az RL listában, akkor olyan értéket fog visszaadni, melyre a az �1 (�1 , �2 ) pár véletlenszer¶en vagy az �0 vagy valamelyikének titkosított változata lesz. Egyébként mindig véletlen választ ad, tehát valóban véletlen orákulumként viselkedik. ℬ algoritmus legalább � valószín¶séggel Megbecsüljük annak valószín¶ségét, hogy � sikeres Végül meg kell mutatnunk, hogy a megtalálja � inverzét. 55

ℬ(1� , �, �) global RL, HL, ℎ function ℋRO (�) �=1 function (az RL és HL listák aktuális hossza ℎ) InRL = FALSE while if � 6 ℎ AND NOT RL[�] = � then InRL = TRUE InRL do else �=�+1 end end if then return HL[�] InRL end if � (�) = � then � ← {0, 1} (egy � = �2 ⊕ � � véletlen bit) else � ← �� (egy véletlen elem) end ℎ=ℎ+1 RL[ℎ] = � HL[ℎ] = � end function main �1 = � �2 ← � � ℎ=1 ExpindCPA �,Π (�) for � = 1 to ℎ do if � (RL[�] = � then return RL[�] end end return „nem sikerült invertálni” end end 6. algoritmus: Az � algoritmus pszeudokódja, melyet az kísérlet közben RO algoritmus, és benne a ℋ indCPA sokszor meghívhat az �,Π (�) inverzét kiszámító 56 � ℬ Exp lesz �0 �1 [︀ és P megkülönböztetésében: ExpindCPA �,Π (�) = 1 = [︀ ]︀ [︀ ]︀ −1 P ExpindCPA (�) ∈ �� · P � −1 (�)

∈ �� + �,Π (�) = 1 | � [︀ ]︀ [︀ ]︀ −1 P ExpindCPA (�) ̸∈ �� · P � −1 (�) ̸∈ �� �,Π (�) = 1 | � ]︀ Világos, hogy P ugyanis � −1 (�) [︀ −1 ExpindCPA (�) ̸∈ �� �,Π (�) = 1 | � ]︀ 1 = , 2 �1 és �1 [︀ ]︀ −1 P ExpindCPA (�) ∈ �� 6 1, �,Π (�) = 1 | � ismerete nélkül nem lehet választani és feltételezhetjük, hogy a kísérlet közül. Mivel 1 -nél nagyobb valószín¶séggel sikeres, azt 2 kapjuk, hogy [︀ ]︀ 1 + �(�) 6 P ExpindCPA �,Π (�) = 1 2 [︀ ]︀ 1 [︀ ]︀ 6 P � −1 (�) ∈ �� + P � −1 (�) ̸∈ �� 2 [︀ −1 ]︀ 1 6 P � (�) ∈ �� + . 2 Így [︀ ]︀ P � −1 (�) ∈ �� > �(�), � -et. A szük�, �� az � futási vagyis nem elhanyagolható valószín¶séggel sikerült invertálni séges lépések száma pedig polinomidej¶, hisz ha ideje, és � ℎ-szor �� + �(ℎ2 + ℎ�� ).

�� az hívja meg az orákulumot, akkor az invertálás futási ideje 2.3 OAEP – Optimal Asymmetric Encryption Padding E módszer nevét nem magyarítjuk, az OAEP rövidítést fogjuk használni. A padding általában egy sztring szükséges hosszúságúra való föltöltését jelenti valamilyen el®re megadott módon, pl. csupa 0-val. Kés®bb látni fogjuk, hogy a paddinget használhatjuk arra is, hogy az üzenetet kib®vítsük véletlen bitekkel, ezzel azt legalább részben véletlenszer¶vé téve. Az e fajta padding 57 � − �0 − �1 �1 bit � �0 bit bit 0000 � G H � − �0 �0 bit bit � � 4. ábra Az OAEP diagramja nem bizonyult teljesen biztonságosnak, a sztring egy része ugyan véletlen bitekb®l áll, de a másik felén lév® bitekre nyert információ a rendszer gyengéjét jelzi. Ezt küszöböli ki e szellemes, a Feistel-típusú rejtjelez® ötletére épít® megoldás. El®ször csak magát a

paddingelést mutatjuk meg, majd azt, hogy hogyan építhet® felhasználásával biztonságos nyílt kulcsú rejtjelez®. A 4. ábra az OAEP diagramja jól mutatja m¶ködését 2.5 definíció (OAEP) Az OAEP egy Feistel-típusú � nyílt szöveget egy � � algoritmus mely egy véletlen szöveggel és nullákkal kiegészít, majd a nyílt szöveget és a hozzáadott véletlen valamint 0 elemeket két véletlen orákulum véletlen elemekkel helyettesíti, de oly módon, hogy ezután e két orákulum meghívásával visszakaphatók is legyenek az eredeti elemek. Legyen � bithossza, és �0 a véletlen � � − �0 − �1 bites. bites a paddingelt szöveg hossza, ebb®l �1 a zérusok száma. Így az � : {0, 1}�0 {0, 1}�−�0 és � üzenet szám � : {0, 1}�−�0 {0, 1}�0 két véletlen orákulum (a gyakorlatban egyirányú függvények). A � algorit�−�0 −�1 mus bemenete az � ∈ {0, 1} sztring, kimenete egy

�-hosszú sztring, 58 az algoritmus lépései: � ← {0, 1}�0 � = � ‖ 0�1 ‖ � � = (� ‖ 0�1 ) ⊕ �(�) � = � ⊕ �(�) E � algoritmus eredménye tehát az (�, �) pár. Ebb®l visszanyerhet® � és � is az orákulumok segítségével: � = � ⊕ �(�) � ‖ 0�1 = � ⊕ �(�) Ezután bármely egyirányú kiskapu-permutációval kombinálva az OAEP-t egy nyílt kulcsú titkosítóhoz jutunk. 2.6 definíció (Aszimmetrikus rejtjelez® (OAEP + TDP)-b®l) Legyen (� az 1.31 deníció szerinti kiskapu-permutációk egy családja Π = (�, E, D) TDP , �, � −1 ) Deniáljuk a aszimmetrikus kulcsú 1.12 deníciónak megfelel® rejtjelez®t a következ®képp: 1. � : (�, �) ← � TDP (1� ), ahol �� és ��−1 mindketten {0, 1}� {0, 1}� függvények. � választ egy �0 és egy �1 számot, melyekre �0 + �1 < �, � �−�0 �−�0 valamint egy � : {0, 1} 0 {0,

1} és egy � : {0, 1} {0, 1}�0 hash függvényt, és publikálja a �� = (�, �� , �, �) nyílt kulcsot. A titkos −1 �−�0 −�1 kulcs az �� = (�, �� ) lesz. A nyílt szöveg � ∈ {0, 1} . 2. Az E algoritmus lépései: � ← {0, 1}�0 � = � ‖ 0�1 ‖ � � = (� ‖ 0�1 ) ⊕ �(�) � = � ⊕ �(�) � = E�� (�) = �� (� ‖ �) 3. A D algoritmus lépései: � = � ⊕ �(�) � ˆ = ��−1 (� ⊕ �(�)) 59 A D algoritmus e ponton ellen®rzi, hogy az � ˆ utolsó �1 bitje valóban 0-e, ha nem, ⊥-et ad vissza, a dekódolás sikertelen, egyébként � ˆ =�‖ 0�1 így E�� (�) megegyezik az ��−1 (� ⊕ �(�)) els® � − �0 − �1 bitjéb®l álló sztringgel. Bizonyítható, hogy e rejtjelez® megfelel® �0 megválasztása mellett sze- mantikailag biztonságos a véletlen orákulum modellben. Az ugyanakkor nem bizonyítható, hogy a

választott kriptoszöveg alapú támadás ellen is biztonságos lenne. Másrészt a gyakorlatban különösen fontos RSA esetére ez a biztonság is bizonyítható, nevezetesen az RSA-függvényre épül® ún. RSAOAEP két független véletlen orákulum esetén bizonyos � kitev®kre CCA- biztonságos. Erre az RSA-ról szóló részben visszatérünk 2.4 Hibrid rejtjelezők Az aszimmetrikus rejtjelez®k egyik komoly hátránya a szimmetrikusokkal szemben, hogy lényegesen lassabbak. Nagyobb szöveg titkosítására ezért praktikusabbnak t¶nik a szimmetrikus rejtjelez®k használata. A két rendszer el®nyeit ötvözik a hibrid rendszerek, amelyekben az egyirányú függvényt vagy az aszimmetrikus rejtjelez®t csak annak a kulcsnak a titkosítására és cseréjére használják, amellyel aztán az valódi üzenetet titkosítják egy szimmetrikus rejtjelez®vel. Két megoldást mutatunk, az els® csak a 23 konstrukció egy továbbfejlesztett változata, melyben az

aszimmetrikus rejtjelez® konstrukciójának részévé válik a szimmetrikus kulcsú, míg a második megoldásban két létez® rendszert ötvözünk, egy aszimmetrikusat és egy szimmetrikusat. 2.7 konstrukció (Hibrid aszimmetrikus rejtjelez® TDP-b®l) Tekintsük a (� TDP , �, � −1 ) az 1.31 deníció szerinti kiskapu-permutációk egy családját Deniáljuk a Π = (�, E, D) aszimmetrikus kulcsú, az 1.12 deníciónak megfelel® rejtjelez®t a következ®képp: 1. 2. � : (�, �, �� ) ← � TDP (1� ), azaz választunk az egyirányú kiskapu-permutációk családjából egy (�, �) indexpárt, és megadjuk az értelmezési tartományt. � választ egy � : �� �� hash függvényt, valamint egy szimmetris s s kus kulcsú Σ = (� , E , D ) rejtjelez®t, és publikálja a �� = (�, �� , �, Σ) −1 nyílt kulcsot. A titkos kulcs az �� = (�, �� ) lesz (︀ )︀ E: � ← �� , E�� (�) = �� (�), Es�(�)

(�) , tehát a szimmetrikus kulcsú rejtjelez® kulcsa a �(�) érték lesz, ahol � egy véletlen elem. 60 3. D: � = �(��−1 (�1 )), D�� (�1 , �2 ) = Ds� (�2 ). D�� E�� (�) = �, ugyanis az üzenethez mind kó−1 doláskor, mind dekódoláskor az � = �(�) = �(�� (�1 ) szimmetrikus kulcsot Könnyen ellen®rizhet®, hogy használtuk. Ha valamilyen fejlett, kinomult szimmetrikus és aszimmetrikus rejtjelez®k állnak rendelkezésünkre, egyszer¶bb, ha a kett® összeolvasztásával konstruálunk új hibrid rendszert. 2.8 konstrukció (Hibrid rejtjelez®) Legyen Π = (� a , Ea , Da ) egy aszim- Σ = (� s , Es , Ds ) egy szimmetrikus kulcsú rejtjelez®. Az * tetsz®leges � ∈ {0, 1} sztring. Deniáljuk a Π = (�, E, D) metrikus kulcsú, és üzenet egy aszimmetrikus kulcsú rejtjelez®t a következ®képp: 1. � : (��, ��) ← � a (1� ), 2. Az E algoritmus lépései: ∙ � ← {0, 1}� ,

∙ �1 ← Ea�� (�), �2 ← Es� (�), így 3. A E�� (�) = (�1 , �2 ). D algoritmus lépései: ∙ � = Da�� (�1 ), ∙ � = Ds� (�2 ), azaz D�� (�1 , �2 ) = �. Egyszer¶ számítás mutatja, hogy elegend®en hosszú üzenet esetén a hibrid rendszer egyrészt nyújtani tudja az aszimmetrikus rendszer funkcionalitását és annak el®nyeit, másrészt a szimmetrikus rendszer hatékonyságát. Bizonyítható az is, hogy ha Π és Σ a hibrid rendszer is. 61 szemantikailag biztonságosak, akkor 3. Nyílt kulcsú rejtjelezők 3.1 RSA Az RSA a legelterjedtebb, legtöbbet vizsgált nyílt kulcsú titkosító rendszer. Ron Rivest, Adi Shamir és Leonard Adleman publikálta 1977-ben, a rendszer az ® neveik kezd®bet¶it tartalmazza. RSA rejtjelező A korábbiakban részletesen tárgyaltuk az RSA-függvényt, és az egyirányúsága elleni támadásokat. Ugyancsak a korábbi fejezetek alapján könnyen készíthetünk az

RSA-függvényb®l nyílt kulcsú rejtjelez®t Most azonban el®ször egy olyan ötletet mutatunk, amely történetileg is az els® valódi aszimmetrikus kriptorendszer alapját képezte. 3.1 konstrukció (RSA véletlen paddinggel) Legyen az üzenet 1. �(�) � ∈ {0, 1} �(�) < 2� − 1, ahol . � : (�, �, �) ← � RSA (1� ), �� = (�, �), �� = (�, �). 2. E: � ← {0, 1}ℓ(� )−�(�)−1 , E�� (� ) = (� ‖ �)� mod � , * olyan, hogy (� ‖ �) ∈ Z� , 3. D: D�� (�) = (�� mod � Bár azt sejtenénk, hogy ha utolsó �(�) ahol � választása bitje). �(�) ≈ �, pl. �(�) = �� valamilyen � < 2 kons- tansra, akkor a 3.1 konstrukció szemantikailag biztonságos, ezt eddig nem sikerült bizonyítani. Csak annyit tudunk, hogy ha �(�) = �(log �), akkor a konstrukció szemantikailag biztonságos. Egy hasonló, kissé kinomultabb 8 konstrukció került a PKCS

#1 v1.5 standardba A biztonsága mindmáig annak sincs bizonyítva, de miután egy ötletes kriptoszöveg alapú támadással sikerrel járt ellene Daniel Bleichenbacher, a PKCS #1 v2 standardba már a bizonyítottan biztonságos OAEP padding került, amit korábban már bemutattunk. CCA-biztonságú RSA A 2.3 konstrukció RSA-függvényre alkalmazott speciális esetét kiemeljük, mint olyat, amely már CCA-biztonságú, legalábbis a véletlen orákulum modellben. 8 PKCS = Public-Key Cryptography Standards, melyeket az RSA Security Inc., ma RSA Security LLC bocsát ki és gondoz. A #1 standard maga az RSA 62 3.2 konstrukció (RSA egy hash-függvénnyel, FergusonSchneier-RSA) Legyen � � = SHA256 ∘ SHA2569 , és Σ = (� s , Es , Ds ) rejtjelez®. Deniáljuk a Π = (�, E, D) aszimmetri- egy hash-függvény, pl. egy szimmetrikus kulcsú kus kulcsú rejtjelez®t a következ®képp: 1. � : (�, �, �) ← � RSA (1� ), �� = (�, �), �� =

(�, �), � = ⌈log(� + 1)⌉, � ← [0, 2� − 1], � = �(�) 2. E: E�� (�) = (�� mod �, Es� ), 3. D: � = ��1 mod � , � = �(�), D�� (�1 , �2 ) = D� (�2 ). Ferguson és Schneier az � = 3 értéket javasolja digitális aláíráshoz és az � = 3 értéket rejtjelezéshez. Ezért természetesen a gcd(3, (� − 1)(� − 1)) = 1 és a gcd(5, (� − 1)(� − 1)) = 1 feltételeknek is fönn kell állniuk. A PKCS #1 v2 standardba került RSA részletes ismertetésére itt nincs lehet®ség, de a lényege bemutatható. Az OAEP leírásában megadott két független hash függvény helyett a protokollban MGF (ún. on function ) mask generati- szerepel, ami egy fajta hash függvény, ahol az output mérete is rugalmasan változtatható. függvényeket használnak. Konstrukciójukhoz gyakran szabványos hash Counter-módú konstrukciójának biztonsága bi- zonytalan. A PKCS standardok nyelvében az oktett (octet )

egyszer¶en 8-bites bájtot jelent, az oktett sztring bájtok egymásutánját jelenti. Általában hexadecimális formában vannak megadva Mi egyszer¶en bájtot írunk helyette A lényeg, a standardban minden adat valahány bájtos, tehet bitben mért hossza 8-nak egész számú többszöröse. A PKCS #1 v2.2 egy egyszer¶sí- tett változatát megadjuk az alábbiakban. Az egyszer¶sítés abból áll, hogy a konverziós részek és a hibaüzenetek részletezését, továbbá néhány apróbb technikai részt kihagyunk vagy kissé leegyszer¶sítünk. Az RSA-ban használt OAEP-változatot az 5. ábrán szemléltetjük 3.3 definíció (RSA-OAEP, a PKCS #1 22 egyszer¶sített változata) Az algoritmusban használt jelölések: EM az OAEP kimenete H hash függvény 9 A SHA256 egy 256-bites értéket adó szabványos hash függvény, mely a ma ismert legerősebbek egyike. 63 DB = lHash PS 01 seed 00 MGF MGF EM = 00 maskedSeed maskedDB 5. ábra Az RSA-ban használt

OAEP diagramja 64 � HLen L MGF H kimenetének hossza bájtban opcionális címke maszkot generáló függvény (változó hosszú hash) Az üzenet egy tetsz®leges niáljuk a 1. Π = (�, E, D) � ∈ {0, 1}8MLen sztring (MLen bájt hosszú). De- aszimmetrikus kulcsú rejtjelez®t a következ®képp: � : (�, �, �) ← � RSA (1� ), �� = (�, �), �� = (�, �). 2. Az E algoritmus bemenete a onális � �� nyílt kulcs, az � üzenet és egy opci- címke. Az algoritmus (a standardban RSAES-OAEP a neve) lépései: lHash = H(�) ha � üres, értéke el®re meg van adva PS = 00 . 0 összesen ℓ(� ) − MLen − 2HLen − 2 DB = lHash ‖ PS ‖ 0�00 ‖ � bájt seed ← {0, 1}8HLen maskedDB = DB ⊕ MGF(seed, ℓ(� ) − HLen − 1) maskedSeed = seed ⊕ MGF(maskedDB, HLen) EM = 0�00 ‖ maskedSeed ‖ maskedDB E�� (�[, �]) = (EM)� mod � . 3. A D algoritmus bemenete a opcionális � �

kriptoszöveg, a titkos �� kulcs és az címke. Az algoritmus lépései: EM = �� mod � = � ‖ maskedSeed ‖ maskedDB seed = maskedSeed ⊕ MGF(maskedDB, HLen) DB = maskedDB ⊕ MGF(seed, ℓ(� ) − HLen − 1) = lHash’ ‖ PS ‖ 0�00 ‖ � D�� (�, [, �]) = �. Természetesen, ha hiányzik az 0�01 bájt, ha lHash’ ̸= lHash, ha � ̸= 00, akkor a dekódolás sikertelen. A PKCS #1 2.2 CCA-biztonságát Fujisaki, Okamoto, Pointcheval és Stern bizonyították. Egyrészt az OAEP-re épül® nyílt kulcsú rejtjelez®k CCA-biztonsága nem áll fenn, Shoup bizonyította, hogy ha az egyirányú 65 kiskapu-permutáció invertálása ugyan nehéz, de részlegesen nem, akkor az OEAP CCA-biztonsága nem bizonyítható. Másrészt viszont az OAEP CCAbiztonságos, ha a részleges invertálás is nehéz Ezt sikerült az RSA esetén bizonyítani. ha egy � Némi óvatosságra int, hogy a CCA-biztonság bizonyításában, támadó � id®ben

� eséllyel sikeres az RSA-OAEP ellen, akkor az 2 18 2 RSA inverz sikerének esélye � /2 , és az algoritmus � ideig fut. Tehát e bizonyítás alapján elvileg nem elképzelhetetlen, hogy könnyebb támadni az RSA-OAEP ellen, mint az egyirányú RSA-függvényt invertálni. (Ez csak elvi lehet®ség, semmi jel nem mutat arra, hogy ilyen támadás létezne.) 3.2 ElGamal és ECC A Certicom nev¶ cég fontos szerepet játszik a diszkrét logaritmusra épül® kriptográai  legf®képpen az elliptikus görbékre épül®  rendszerek elméletének kidolgozásában, szabványosításában, szabadalmazásában és terjesztésében. Legalább 30 szabvány f¶z®dik a nevükhöz A Certicom 1998-ban alapított egy Standards for Efficient Cryptography Group (SECG) nev¶ cso- portot, melynek tagjai közt olyan cégek találhatóak, mint Entrust, Fujitsu, NIST, Pitney Bowes, Unisys, Visa. A diszkrét logaritmus probléma, pontosabban a DieHellman-probléma nehézségére épül®

rejtjelez®k kiindulópontja az ElGamal rendszer. Az ElGamal rejtjelező Taher Elgamal (nevét szokás ElGamal vagy El Gamal formában is irni, de maga az Elgamal alakot preferálja) egyiptomi származású kriptográfus. Mindennek ellenére a róla elnevezett rejtjelez®t a széles körben elterjedt formában ElGamal-nak fogjuk írni. 3.4 konstrukció (ElGamal rejtjelez®) Legyen � group az 1.22 kísérletben deniált, ciklikus csoportot generáló algoritmus. Aszimmetrikus rejtjelez®t deniálunk a következ®képp: 1. 2. � : (�, �, �) ← � group (1� ), majd választunk egy véletlen � ← Z� elemet, � és kiszámoljuk ℎ = � értékét. A nyílt kulcs �� = (�, �, �, ℎ), a titkos kulcs �� = (�, �, �, �). E: � ← Z*� , � ∈ �, E�� (�) = (� � , ℎ� · �). 66 D: 3. Jelölje (�1 , �2 ) az E�� (�) kimenetét, ekkor D�� (�1 , �2 ) = Könnyen ellen®rizhet®, hogy D��

E�� (�) = �, �2 . ��1 ugyanis �2 ℎ� · � (� � )� · � � �� · � = = = = �. ��1 (� � )� (� � )� � �� Fontos eleme e rejtjelez®nek az az egyszer¶ megoldás, hogy a nyílt szöveg meg van szorozva egy  a DDH-probléma nehézsége esetén  véletlennek tekinthet® elemmel. Ha pedig ′ egy tetsz®leges � elemére � ∈� egy véletlen elem, akkor a P[� · � = � ′ ] = P[� = �−1 · � ′ ] = vagyis itt is arról van szó, hogy ha elküldeni, akkor az �·� � csoport 1 , |�| � -t nem a rejtjelezett szöveggel együtt kéne tökéletes biztonságot nyújtana. Így bizonyítható az alábbi tétel: Ha a DDH-probléma nehéz, akkor a 3.4 konstrukcióban megadott ElGamal rejtjelező szemantikailag biztonságos. 3.5 tétel Csoport generálása az ElGamal számára Kérdés, hogy generálunk olyan csoportot, amelyben könnyen találunk generátorelemet! Els® jelölt a Z*� , mely

ciklikus, van hatékony algoritmus egy generátorelemének megtalálására és e csoportban a diszkrét logaritmus problémát nehéznek hisszük. Céljainknak mégsem fog e csoport megfelelni, mivel egyrészt rendje nem prím, másrészt  mint azt nem nehéz belátni  e csoportban a döntési Die Hellman-probléma (DDH) nem nehéz! Ezért másik csoport után kell néz- nünk. Kézenfekv® megoldás lasztani. Z*� helyett annak egy megefelel® részcsoportját vá- Ha a kvadratikus maradékok (azaz a négyzetelemek) csoportját választjuk, akkor egy (� − 1)/2-elem¶ részcsoportot kapunk, mivel négyzet- elemek szorzata és inverze is négyzetelem. Ha ráadásul azaz � = 2� + 1 alakú, ahol � � biztonságos prím, is prím, akkor e csoport már prímrend¶. Ráadásul generátorelemet is könny¶ benne találni, hisz minden egységt®l 67 * különböz® eleme generátorelem. Így elég egy � ← Z� elemet választani, ha 2 2 � mod � ̸=

1, akkor � = � mod � egy generátorelem. �-t és � -t úgy választjuk, hogy ℓ(�) = � + 1, ℓ(�) = �. Így az üzenetek is egy � -elem¶ halmazból vehet®k, praktikusan � ¯ ∈ {1, 2 . , �} Ezek az elemek viszont nincsenek �-ben, ezért négyzetre kell ®ket emelni. Az � = � ¯ 2 megfelel® lesz az algoritmus számára. Kérdés már csak az, hogy dekódolunk. Miután a D algoritmus visszaadja �-et, abból négyzetgyököt vonunk Z� -ben. A két négyzetgyök összege �, �−1 ] intervallumba. Mindenzt egy így ki tudjuk választani, melyik esik az [1, 2 A biztonsági paraméter függvényében tehát példán szemléltetjük: 3.6 példa Legyen � mellett � is � = 359, � = 2� +1, ahol � = 179 (a példa szépségéért itt biztonságos prím). A Z� = Z359 csoport egy � = 179-edrend¶ elemét megkapjuk egy tetsz®leges (egységt®l különböz®) elem négyzetre eme2 lésével, legyen a � csoport egy generátora � =

5 = 25. Legyen a titkos kulcs az 53 ∈ Z179 , így a publikus kulcs �� = (359, 179, 25, 2553 mod 359) = (359, 179, 25, 340). Legyen az üzenet az {1, 2, . , 179} halmaz egy eleme, mondjuk � ¯ 2 Így � = 103 mod 359 = 198 ∈ �. Legyen a véletlen elem � = 138 = 103. ∈ Z179 , így a rejtjelezett üzenet: (25138 mod 359, 340138 · 198 mod 359) = (187, 235). A visszafejtéshez a titkos kulcsot használva � = 235 · 187−53 mod 359 = 198. 198 négyzetgyökei ±198 �+1 4 mod � = ±19890 mod 359 = ±256 mod 359 = {256, 103} Mivel e két szám közül 103 < 179, ezért Elliptikus görbére épülő rejtjelező 103 az üzenet. Az elliptikus görbékre épül® rejtje- lez®k konstrukciójának használata mögött az a tény rejlik, hogy a diszkrét * logaritmus problémára a Z� -gal ellentétben nem ismeretes szubexponenciális algoritmus. Így az ElGamal-rendszerek valamilyen változatát elliptikus görbéken érdemes megvalósítani. Ez

annyi el®nyt ad az elliptikus görbékre 68 épül® kriptográai rendszereknek, hogy ma ezeket tekinthetjük a leghatékonyabbnak. Az ECIES (Elliptic Curve Integrated Encryption Scheme) meglehet®sen bonyolult rendszer. Kiváló kriptográfusok alkotása, Abdalla, Bellare és Rogaway, majd Shoup munkája után nyerte el ma használt alakját Itt most csak egy leegyszer¶sített változatát ismertetjük. (�, �) an alak használható, azonban �-tengelyre, ezért � ismeretében csak két � érték jöhet szóba. Ha (�, �) az egyik pontja a görbének, akkor (�, � − �) a másik, és mivel � páratlan, ezért � és � − � mindig különböz® paritású (ha nem 0). Ezért �� -nal jelölve � paritását, a pontokat az (�, �) ∈ Z� ×Z� helyett a kb. felényi (�, �� ) ∈ Z� × Z2 alakban tárolhatjuk Egy pont ilyen módon A görbe pontjainak tárolására az tudjuk, hogy a görbe szimmetrikus az való tömörítése nagyon

egyszer¶, de a tömör alakból való visszaszámolás is egyszer¶en és hatékonyan számolható. 3.7 konstrukció (ECIES  leegyszer¶sített változat) Legyen fölötti ℰ � egy Z� elliptikus görbét generáló algoritmus, mely az elliptikus görbe cso- portban talál egy � -adrend¶ ciklikus � részcsoportot, melyet egy � pont által reprezentált elem generál. Aszimmetrikus rejtjelez®t deniálunk a következ®képp: 1. � : (ℰ, �, �, �, � ) ← � group (1� ), ahol ℓ(�) > �. � ← Z*� a titkos azaz �� = (�). � = �� az ℰ egy másik pontja, a publikus kulcs kulcs, �� = (ℰ, �, �, �, �, �). 2. E: � ← Z*� , � ∈ Z� , E�� (�) = (��, � · �� mod �), ahol 3. �� = (�� , �� ), és �� ̸= 0. D: Jelölje (�1 , �2 ) az E�� (�) (�� , �� ) = � · �1 jelöléssel kimenetét, ahol D�� (�1 , �2 ) = �1 ∈ ℰ , �2 ∈ Z*� .

Ekkor az �2 mod �. �� Biztonsági szerepe nincs, hogy számolás közben a pontot tömörített vagy tömörítetlen formájában kezeljük. 69 � � = (0, 1) 6 7 8 9 10 0 1 2 3 4 5 � = (3, 8) (�) � 2 = �3 + � + 1 14-pontú elliptikus görbe egy 7-pontú része, melyen a pontm¶velet Z7 -tel izomorf csoportot ad. A görbe � csoporthoz nem tartozó pontjait 6. ábra A egy halvány színnel jelöltük. 3.8 példa A 2 ábra harmadik görbéje 14-pontú, csoportjának 7-elem¶ részcsoportját a (9) egyenletben megadtuk, itt felidézzük: Z7 ∼ = � = {�, (3, 8), (6, 6), (0, 1), (0, 10), (6, 5), (3, 3)}. � = 11, � = 7, � = (3, 8). Legyen a titkos kulcs �� = 3, így � = 3� = (0, 1). Legyen az üzenet � = 4 ∈ Z*11 . A titkosításhoz * válasszunk egy véletlen elemet: � = 2 ∈ Z7 . Ezzel A paraméterek tehát: �� = 2 · (3, 8) = (6, 6), tehát �� = 3, �� = 2 · (0, 1) = (3, 3), így (��, � · �� mod

11) = ((6, 6), 1). (�1 , �2 ) = ((6, 6), 1) párt, és a titkos kulcsot, ami 3, (�� , �� ) = 3 · (6, 6) = (3, 3), tehát A dekódoláshoz vegyük a így �2 1 mod � = mod 11 = 4 �� 3 4. (Ha számolás közben a pontok tömör formáját használjuk, � = (3, 0), � = (0, 1), 2� = (6, 0), 2� = (3, 1).) tehát az üzenet akkor 70 3.3 Összehasonlítások Megismerve az RSA rejtjelez®t, az ElGamal rejtjelez®t, valamint annak elliptikus görbéken megvalósított változatát, egy rövid összefoglalást adunk ezek m¶ködésének hatékonyságáról. A biztonsági szint az � biztonsági pa- raméter értékét jelenti. A szimmetrikus kulcsú rejtjelez®k lényegében ezzel azonos, vagy esetleg néhány bittel kisebb biztonságot el tudnak érni, azaz a feltöréshez �-ben exponenciális idej¶ algoritmus kell. Az elliptikus gör- békre épül® kriptorendszerek a leghatékonyabbak, az els® generációs RSA és ElGmal rendszerek csak jóval

nagyobb kulcshossz esetén nyújtanak azonos biztonságot. Ugyanakkor még ma is óvatosságból sokan döntenek az RSA mellett, mivel a mögött már több évtizedes tapasztalatok gy¶ltek össze, az elliptikus görbe kriptográa pedig a mögötte lév® összetettebb matematikai módszerek és fogalmak miatt nagyobb bizonytalanságban tartja a felhasználók egy részét. Biztonsági szimmet- szint rikus ECC RSA/DH Meddig véd? 80 80 160 1024 2010 112 112 224 2048 2030 128 128 256 3072 2040 192 192 384 7680 2080 256 256 512 15360 2120 1. táblázat Kulcsméretek összehasonlítása (forrás: Certicom Research, Elliptic Curve Cryptography, SEC 1, 2009-05-21, v20) E fejezetben a gyakorlatban ma használt két egyértelm¶en legelterjedtebb rendszerre koncentráltunk. Megjegyzésekben azonban jeleztük, hogy mely más megoldások lehetségesek, és hogy azok miért nem terjedtek el. Igye- keztünk a modern kriptográa szemléletmódjával

közelíteni a nyílt kulcsú kriptográa e két legfontosabb példájához. Ez azt jelenti, hogy világos fogalmunk van arról, hogy e rendszerek milyen biztonsági szintet nyújtanak, és hogy azok pontosan milyen matematikai feltételek esetén állnak fenn. Megközelítésünk az volt, hogy a makacs számelméleti problémák felsorolása után a bel®lük képzett egyirányú függvények és kiskapu-permutációk segítségével általános konstrukciókat adtunk nyílt kulcsú rejtjelez®kre. Így azt is meg tudtuk mutatni, hogy speciálisan miért épp az RSA-függvényre épül® ma- 71 radt máig is az egyik legfontosabb rejtjelez® (pl. a mögötte lév® tapasztalat, és a bizonyított CCA-biztonsága miatt), másrészt láthattuk azt is, hogy e pillanatban az ismert matematikai támadási lehet®ségek adta keretek közt az elliptikus görbékre épül® rendszerek nyújtanak egy adott biztonsági szintet a leghatékonyabban. 72 Tárgymutató (�,

�)-biztonság 17 aszimmetrikus rejtjelez® 20, 53 biztonság szemantikai 19, 21 tökéletes 16 kulcsolt 35 hash függvény 34 hibrid rejtjelez® 60 kiskapu-függvény 32 lehallgató (eavesdropper) 20 biztonságos prím 49 Merkles puzzle 50 CCA-biztonság 22 moduláris hatványozás 8 CPA-biztonság 21 moduláris inverz 11 csoport 9 DieHellman-problémák 28 DieHellman hash függvény 36 DieHellmann függvény 34 moduláris négyzetgyökvonás 26 moduláris négyzetreemelés 33 nehéz problémák 23 OAEP 57 Die-Hellman kulcscsere 50 diszkrét logaritmus 27, 34 Rabin-probléma 26 RSA-függvény 33 ECIES 69 RSA probléma 24, 26 egyirányú függvény 31 RSA rejtjelez® 62 egyirányú kiskapufüggvény 32 egyirányú kiskapupermutáció 32 szemantikai biztonság 19, 21 ElGamal rejtjelez® 66 szimmetrikus rejtjelez® 15 elhanyagolható függvény 18 elliptikus görbe pontm¶velet 45 elliptikus görbék 42 er®s prím 49 faktorizáció 24 félcsoport 9 op, ops

17 TDF 32 TDP 32 tökéletes biztonság 16 ütközésálló 35 vakítás 40 véletlen orákulum 54 gy¶r¶ 10 hash függvény 73