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 . 6 Z� és a moduláris hatványozás . Z*� és a moduláris inverz . 8 Kínai maradéktétel . 1.2 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 . 11 Tökéletes biztonság . Számítási biztonság  aszimptotikus megközelítés 1.3 6 . 34 A DieHellman hash függvény . 36 Támadások az RSA-függvény ellen . 36 Amikor � kicsi . 37 Kis � közös üzenettel . 37 Hastad támadása . 37 Amikor � kicsi . 38 Amikor � kicsi  gyökös támadás . 39 . 39 Közös modulus 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 . Merkle's 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 � az � egész � -nel való osztási maradéka � ≡ � (mod � ) az � és � egészek � -nel való osztási maradéka azonos Z� az � -nel való osztás maradékosztályainak additív csoportja (vagy gy¶r¶je) Z*� az � -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 � karakterlánc hossza bináris ábrázolásban az � 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 � (ciklikus csoport- kulcsgenerátor, függvénygenerá- diszkrét logaritmus, 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 (� = �� ) ciklikus csoportot 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 az xx 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 � halmazból értékadás, melyben � értéke egy véletlen algoritmus eredménye � = � (�) ‖ ⊕ � -t cél/feltétel/körülmény mellett 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(�, �) jelöli (az angol gratest common divisor kifejezésb®l). Ez az a legnagyobb pozitív egész, mely � és � mindegyikének osztója Ha a két szám egyike 0, 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 � zérus voltának ellen®rzése, � abszolút értékének és � mod � é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 � és � legnagyobb közös osztója if � = 0 then return |�| 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, � ⩾ � > 0 output: ((gcd(�, �), �, �), ahol gcd(�, �) = �� + �� if � | � then return (�, 0, 1) else � = ⌊ �� ⌋, � := � mod � (ez az � = �� + � maradékos osztás) (�, �, �) = gcdx(�, �) return (�, �, � − ��) end end 2. algoritmus: Kib®vített euklideszi algoritmus 1.1 példa Kövessük végig a 2 algoritmust gcdx(40, 18) kiszámításán! Megoldás. 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), 40 = 2 · 18 + 4, 18 = 4 · 4 + 2, � = 2, � = 4 � = 4, � = 2 (6) (5) (4) (�, �, �) = (2, −4, 9) (�, �, �) = (2, 1, −4) (�, �, �) = (2, 0, 1) Eszerint tehát

gcdx(40, 18) = (2, −4, 9), azaz gcd(40, 18) = 2 és 2 = −4 · 40 + 9 · 18. Z� é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 � 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 � -nel való osztási maradékot, hisz az alkalmazásokban tipikusan � és � 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 exponenciá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 1341 mod 53 értékét! Megoldás. 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, � ∈ Z� a hatványozás alapja, � ∈ Z+ a kitev® output: �� mod � if � = 1 then return � 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ó eredmény mod 53 1 13 = (13)2 = (10)2 13 = (28)2 = (42)2 = (15)2 13 = 13 = 169 ≡ 1300 ≡ 784 ≡ 1764 ≡ 2925 ≡ 13 10 28 42 15 10 10 101 1010 10100 101001 Minden részletszámítás 3000 alatt maradt, és a 6 bináris jegyb®l álló kitev® mellett 7 szorzás és 5 maradék kiszámolására volt szükség. 1341 mod 53 = 10. 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űt 2 alkot). Nem fog zavart okozni, ha a Z� e két m¶veletét is az egészeknél használt m¶veleti jelekkel fogjuk jelölni, tehát e jelöléssel például Z5 -ben számolva 2 + 3 = 0, 2 · 3 = 1. Z� egy másik reprezentációjához jutunk, ha elemeivel azt a maradékosztályt jelöljük, amelynek az adott szám is tagja. jük, e rövid bekezdés alatt Hogy a zavart elkerül- Z� elemeit szögletes zárójelbe tesszük, tehát Z� := {[0], [1], . , [� − 1]}, ahol [�] = {. , � − 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 következ®képp deniálhatók: [�]+[�] := [�+� 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 � 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®. Bár a fenti algoritmus gyengéje, hogy tovább számol, ha egy részhatvány 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 jeleket is fölsoroljuk, ekkor Z� egy halmaz, ⟨Z� , +⟩ az additív csoport, ⟨Z� , ·⟩ a multiplikatív félcsoport és ⟨Z� , +, ·⟩ a gyűrű. E jelölések használatára nem lesz szükségünk, ha szükséges, meg fogjuk mondani, melyik struktúrára gondolunk. 10 Z*� és a moduláris inverz Az � elem � modulus szerinti moduláris inverzén azt a 0 és � közé es® � számot értjük, melyre �� ≡ 1 (mod � ). Moduláris inverz csak � -hez relatív prím � számokra létezik, azaz ha gcd(�, � ) = 1. Ekkor a kib®vített euklideszi algoritmus szerint létezik olyan � és � egész, 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 bizonyítja, hogy

minden lépésben fennáll az ��� ≡ �� (mod � ) összefüggés (mod � ), ami �2 folyamatosan csökkenése miatt véges sok lépésen belül vagy az �2 = 1 vagy az �2 = 0 (� = 1, 2), így az algoritmus végén ��2 ≡ �2 értéket eléri. function inv(�, � ) input: � ∈ Z, � ∈ Z+ , � > 1 output: � 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 �2 mod � end 4. algoritmus: Moduláris inverz kiszámolása Mint láttuk, Z� 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 11 Például Z*5 = {1, 2, 3, 4}, Z*12 = {1, 5, 7, 11}, Z*14 = {1, 3, 5, 9, 11, 13}. * Általában, ha � prím, akkor Z� = {1, 2, . , � − 1} Z*� elemeinek száma �(� ), ahol � az Euler-féle fí függvény. Ha � törzstényez®s alakja � = ��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 szorzata, azaz � = �� , ekkor �(� ) = (� − 1)(� − 1). Annak, hogy minden � -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 3 invertálható. * A Z� csoport ciklikus, ha � egy páratlan prím

hatványa. Több prím* osztóval rendelkez® � esetén Z� 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 � és � relatív prímek, és e megoldás egyértelm¶

modulo � = �� , nevezetesen (︀ )︀ � = �(� −1 mod �)� + �(�−1 mod �)� mod �, (1) 3 Az előző lábjegyzetben bevezetett jelölést használva írhatjuk, hogy ⟨Z* , ·⟩ csoport. � 12 mod � a � moduláris inverze a � modulus szerint, míg �−1 mod � a � moduláris inverze modulo � . Annak ellen®rzése, hogy ez valóban megoldás, ahol � −1 behelyettesítéssel ellen®rizhet®, hisz �(� −1 mod �)� ≡ � (mod �) �(� −1 mod �)� ≡ 0 (mod �) �(�−1 mod �)� ≡ 0 (mod �) �(�−1 mod �)� ≡ � (mod �). Tekintsük a következ® � leképezést: � : Z� Z� × Z� ; � ↦ (� mod �, � mod �). (2) Annak ellen®rzése, hogy az (1) egyenletbeli � az egyetlen megoldás mod � , épp azzal ekvivalens, hogy � bijekció, és adott (�, �) párhoz az (1) képlettel rendelt �, 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 (�, �) pár is, melyre a kongruenciarendszer nem lenne megoldható. Szemléltessük ezt egy egyszer¶ példán, legyen � = 3, � = 5. Ekkor a Z15 és a Z3 × Z5 elemei közt � 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) 3 ↔ (0, 3) 9 ↔ (0, 4) 13 ↔ (1, 3) 4 ↔ (1, 4) 8 ↔ (2, 3) 14 ↔ (2, 4) A táblázatba az elemeket a Z3 × Z5 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 1.3 tétel (Kínai maradéktétel) 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� . 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 A Z� ×Z� elemei közti m¶veletek deníciói természetes módon, az (�, �)+ (�, �) = (� + �, � + �) és az (�, �) · (�, �) = (� · �, � · �) képletekkel vannak 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 (a) 13+7 mod 15, (b) 13·7 mod 15, (c) 137 mod 15 értékeket, mind Z15 -ben, mind Z3 × Z5 -ben számolva! Megoldás. Az � -re és inverzére vonatkozó képleteket fogjuk használni, de a fenti táblázatban ellen®rizhetjük is az eredményeket. � (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). 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 � biztonsági paraméter A polinom idej¶ algoritmusokból álló

(�, E, D) 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. � ← 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 3. � = D� (�), azaz a polinom idej¶ determinisztikus D algoritmus � -hoz és �-hez (|�| + |�|-ben polinom id®ben) hozzárendel egy � sztringet. 4. Minden �, � által generált � és tetsz®leges � esetén fönnáll az 2. 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 � sztringek ℳ

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 Tökéletes biztonság Egy rejtjelez®t tökéletesen biztonságosnak nevezünk, ha � ismeretében semmilyen információt nem tudhatunk meg �-r®l. E fogalomnak 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 eredete: indistinguishability under chosen-plaintext attack ) 1. 1.7 definíció (Tökéletes biztonság) A Σ = (�, E, D) szimmetrikus kulcsú rejtjelez® tökéletesen biztonságos, ha bármely korlátlan számítási kapacitással rendelkez® � algoritmus el®nye a Σ rejtjelez®vel szemben 0, azaz ⃒ ⃒ Adv ⃒ ⃒ 1 ⃒ = 0. ExpindCPA (�) = 1] − �,Σ 2⃒ indCPA ⃒ �,Σ (�) = ⃒P[ A denícióbeli Adv (az advantage szóból) jelölés azt a valószín¶séget je- lenti, amekkora valószín¶séggel � különbséget tud tenni �0 és �1 közt csak �-t ismerve. A tökéletes biztonság azt jelenti, hogy � el®nye a Σ rejtjelez®vel szemben 0, még akkor is, ha � korlátlan számítási

kapacitással rendelkezik. 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. 1.8 tétel (Shannon tétele) Legyen Σ = (�, E, D) egy szimmetrikus kulcsú rejtjelező a (�, ℳ, �) hármas fölött. 1. Ha Σ tökéletesen biztonságos, akkor |ℳ| ⩽ |�|, é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 � való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. Egy � algoritmus polinom * inputra az idej¶, ha létezik egy olyan � polinom, hogy bármely � ∈ {0, 1} �(�) algoritmus �(|�|) lépésben véget ér, ahol |�| az � hosszát jelöli. Az � 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 tudjuk, 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 � > �� , akkor 0 ⩽ �(�) < 1 . �(�) 1 −� −2 −3 −1000 függvények nem elhanyagolhatók, míg a 2 , Az � , � , � ,

6 � −�4 +2 √ 3−� , 2− � , �− log � függvények elhanyagolhatók. 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 kulcsú rejtjelez®t szemantikailag biztonságosnak nevezzük, ha bármely véletlen polinom idej¶ � támadó el®nye a Σ rejtjelez®vel szemben elhanyagolható, azaz bármely � algoritmushoz van olyan elhanyagolható � függvény, hogy Adv ⃒ ⃒ Exp indCPA ⃒ �,Σ (�) = ⃒P[ ⃒ ⃒ 1⃒ indCPA �,Σ (�) = 1] − ⃒ ⩽ �(�). 2 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 � biztonsági paraméter A polinom idej¶ algoritmusokból álló Π = (�, E, D) hármasró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 � bit hosszú) sztringet, �� lesz a nyílt, �� 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 − �(�)

(4) összefüggés, ahol � elhanyagolható. Az E és D algoritmusokra föltehet®  ami a gyakorlatban is megeshet , hogy a dekódolás valamilyen ok miatt meghiúsul, ekkor a D algoritmus egy megkülönböztetett jelet küld (a kriptográai irodalomban a ⊥ 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®, � olyan al(1) (2) goritmus, melyet két különböz® állapotában hívunk meg, ezeket � és � jelöli, és amely közben polinom sokszor meghívhatja E�� -t. ∙ (��, ��) ← �(1� ) ∙ (�0 , �1 ) ← �(1) (1� , ��, E�� ), ahol �0 , �1 ∈ ℳ, és |�0 | = |�1 |. ∙ � ← {0, 1} egy véletlen bit, � ← 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¶ � támadó el®nye a Π rejtjelez®vel szemben elhanyagolható, azaz bármely � algoritmushoz van olyan elhanyagolható � függvény, hogy ⃒ ⃒ Adv Exp indCPA ⃒ �,Π (�) = ⃒P[ Szokás az ⃒ ⃒ 1⃒ indCPA �,Π (�) = 1] − ⃒ ⩽ �(�). 2 ExpindCPA �,Π

(�) kísérletet kicsit másként deniálni. Ekkor Exp 2- ′ argumentumos, második argumentuma a � bit, és kimenete a � bit, azaz �′ = ExpindCPA �,Π (�, �). Ekkor, az � algoritmus Π-vel szembeni el®nyére a fenti denícióbelivel lényegé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 �,Π (�) választott kriptoszöveg alapú támadás (CCA)). 1.15 kísérlet ( Π = (�, E, D) 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 E�� és a D�� algoritmust, utóbbit anélkül, hogy magát az �� -t is megkapná. Legyen ∙ (��, ��) ← �(1� ) ∙ (�0 , �1 ) ← �(1) (1� , ��, E�� , D�� ), ahol �0 , �1 ∈ ℳ, és |�0 | = |�1 |. ∙ � ← {0, 1} egy véletlen bit, � ← E�� (�� ). ∙ �′ ← �(2)

(�, E�� , D�� ), ahol tehát � (2) továbbra is hozzáfér a D�� algoritmushoz, egyedül csak a D�� (�) függvényhívásra nincs lehet®sége. ′ 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) aszimmetrikus 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¶ � támadó el®nye a Π rejtjelez®vel szemben elhanyagolható, azaz bármely � algoritmushoz van olyan elhanyagolható � függvény, hogy ⃒ ⃒ ⃒ 1 ⃒⃒ CCA CCA ⃒ Adv�,Π (�) = ⃒P[Exp�,Π (�) = 1] − ⃒ ⩽ �(�). 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 Π egy Σ szimmetrikus rendszerre cserélend®, és a (��, ��) pár a közös � 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). � egy polinomidej¶ algoritmus, 1.17 kísérlet ( mely a biztonsági paraméter függvényében el®állít két �-bites számot és azok szorzatát. A két szám � függvényében elhanyagolható valószín¶séggel nem prím. � egy algoritmus, mely egy számpárt ad vissza: ∙ (�, �, � ) ← �(1� ) ∙ (�′ , � ′ ) ← �(� ) ′ ′ ExpFactor �,�

(�) = 1, ha � � = � , egyébként = 0. 23 1.18 definíció Azt mondjuk, hogy a faktorizáció nehéz, ha bármely véletlen polinomidej¶ � algoritmushoz létezik olyan elhanyagolható �(�) függvény, hogy Factor AdvFactor �,� (�) = P[Exp�,� (�) = 1] ⩽ �(�). 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 ismert � 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 szorzata. * * � Könnyen igazolható, hogy az � : 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 (�� )� = ��� ≡ �1+��(� ) (mod � ) ≡ �(��(� ) )� (mod � ) ≡ �1� = �. (mod � ) Kérdés, hogy határozható meg � 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 � moduláris inverzének kiszámítására pedig van polinomidej¶ algoritmusunk. A nehézséget az okozza, hogy �(� )-et meghatározni épp oly nehéz, mint faktorizálni � -et Ha ugyanis ismerjük � tényez®it, akkor polinom id®ben ki tudjuk

számolni a �(� ) = (� − 1)(� − 1) értéket, ha pedig ismerjük � és �(� ) értékét, akkor az � = �� �(� ) = (� − 1)(� − 1) egyenletrendszerb®l meghatározható � és � , nevezetesen a � = �/� helyettesítés után a második egyenletb®l a másodfokú �2 − (� − �(� ) + 1)� + � = 0 24 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 gyököt visszaadó függvény ismeretében faktorizálni tudná � -et. A függvény inverze egyszer¶ �-edik hatványozás modulo � . Ez az eljárás az RSA-függvény esetén kb. négyszer olyan gyors algoritmusra cserélhet®

Legyen �� = � mod � − 1, és �� = � mod � − 1. Mivel �(�) = � − 1 és �(�) = � − 1, ezért � � ≡ � �� (mod �) és � � hasonlóképp � ≡ � � (mod �), és a kínai maradéktétel szerint az a kínai maradéktétel alkalmazásával. � ≡ � �� (mod �) �� (mod �) �≡� egyértelm¶en megoldható, nevezetesen az (1) képletet használva (︀ )︀ � = � �� (� −1 mod �)� + � �� (�−1 mod �)� mod �, ahol a �� , �� , � −1 (5) mod � és �−1 mod � mind el®re számolhatók. Szemléltetésül lássunk egy példát. 1.19 példa Legyen � = 11, � = 17, így � = 187 és �(� ) = 160 Legyen −1 � = 3 és � = 16. Számítsuk ki az � = ��,� (�) és az ��,� (�) é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 1101011, ezért a moduláris hatványozás a 3. algoritmusa szerint 12 darab 187-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). � egy véletlen polinomidej¶ algo- 1.20 kísérlet ( ritmus, mely a biztonsági paraméter függvényében el®állít két �-bites prímszámot, azok � szorzatát, egy �(� )-hez relatív prím � számot és azt a � * számot, melyre �� ≡ 1 (mod �(� )). Az � algoritmus egy Z� -beli számot 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] ⩽ �(�). 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 (mod �), ugyanis ha van olyan �, hogy �2 ≡ � (mod �), 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)/2 (�−1)/2 (±� (�+1)/4 )2 ≡ � (�+1)/2 (mod �) ≡ � (�−1)/2 � (mod �) ≡ � (mod �) Legyen tehát � és � ≡ 3 (mod 4), és � = �� . Ekkor az �2 ≡ � (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 �). Azt látjuk, hogy az � modulusú négyzetre emelés inverze könnyen számolható, ha ismerjük � prímtényez®s felbontását. Meglep® módon a négyzetgyö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 kriptorendszer 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 Legyen � egy tetsz®leges � -elem¶ ciklikus csoport, 0 2 �−1 és � egy generátoreleme, azaz � elemeinek halmaza {� = 1, �, � , . , � }. group egy véletlen ExpDlog �,� (�), diszkrét logaritmus kísérlet). � 1.22

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, mely csoportban a m¶velet hatékonyan számolható. Az � algoritmus egy �-beli elemet ad vissza. 27 ∙ (�, �, �) ← � 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] ⩽ �(�). 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 � -adrend¶ ciklikus csoportot, és annak egy � generátorelemét. Az � algoritmus egy �-beli elemet ad vissza ∙ (�, �, �) ← � group (1� ), ahol ℓ(�) = �,

∙ �, � ← Z� ∙ � ← �(�, �, �, � � , � � ) CDH �·� ExpCDH �,� group (�) = 1, ha � = � , egyébként Exp�,� group (�) = 0. 28 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] ⩽ �(�). 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 � group ugyanaz, mint el®bb, az � algoritmus pedig adjon vissza egy � 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 létezik olyan elhanyagolható � függvény, hogy � � � � �·� ⃒ ⃒ AdvDDH �,� group (�) = P[�(�, �, �, � , � , �) = 1] − P[�(�, �, �, � , � , � ) = 1] ⩽ �(�), ⃒ ⃒ 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¶ � Az világos, hogy ha a diszkrét log probléma � probléma is. Az állítás megfordítása nem igaz, van olyan � csoport, melyben 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. 1.27 definíció Legyen � : �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] ⩽ �(�), ⃒ ⃒ 29 ahol �, � ← Z� , � ← �, azaz ezek egyenletes eloszlás szerint

véletlenül választott 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 � algoritmus egy �-beli elemet ad vissza, miután � -szor meghívja az � függvényt 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 létezik olyan elhanyagolható � függvény, hogy IDH AdvIDH �,� (�) = P[Exp�,� (�) = 1] ⩽ �(�). 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 könny¶ kiszámolni � (�)-et, de egy � = � (�) érték ismeretében nehéz olyan � -t találni, melyre � (�) = � . 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. Ezek is egyirányúak, viszont van egy olyan információ � -r®l, melynek birtokában már könny¶ � -et invertálni, illetve egy elem valamely ®sképét megkeresni. Természetesen ehhez a plusz információhoz nem lehet könnyen hozzájutni csak � ismeretében, de könny¶ ilyen � függvényt létrehozni a kiskapu-információval együtt. A formális dení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¶ ℱ algoritmus, hogy bármely �-re ℱ(�) = � (�); 2. nehezen invertálható, azaz tetsz®leges �-re, az � = � (�), � = ℓ(�) jelölések mellet, tetsz®leges véletlen polinomidej¶ � algoritmushoz, mely * a biztonsági paraméter és � függvényében egy {0, 1} -beli elemet ad vissza, létezik olyan elhanyagolható � függvény, hogy P[� (�(1� , �)) = � (�)] ⩽ �(�). 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¶ � algoritmushoz, mely a biztonsági paraméter és � függvényében egy � � -beli elemet ad vissza, létezik olyan elhanyagolható � függvény, hogy P[�� (�(1� , �)) = �� (�)] ⩽ �(�). −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 (�)) = �. �� minden � -ra bijekció, egyúttal �� = ℛ� , akkor a (�, �, � −1 ) hár� mast egyirányú kiskapu-permutációnak nevezzük. Ilyenkor �(1 ) kimenete (�, �, �� ). Ha Az egyirányú kiskapu-függvény, illetve kiskapu-permutáció angol nevéb®l származó rövidítések TDF (oneway trapdoor function ), illetve TDP (oneway trapdoor permutation ). 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 � ̸= � � . Meglep® módon azt nem tudjuk, hogy � ̸= � � -b®l következik-e egyirányú függvény létezése. Azokra hogy � � a problémákra, amelyekre a legfontosabb egyirányú kiskapufüggvények épülnek, az sincs bizonyítva, hogy � � -teljesek lennének, azt sejtik, hogy ezek � ̸= � � esetén egy � � -köztes (� � -intermediate) osztályba tartoznak. Érdekes 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 � számokra van értelmezve, és amelyben a � és � prímek kiválasztása �-t®l determinisztikusan függ, de mivel nincs gyakorlati kriptográai alkalmazása, ismertetését mell®zzük. Az RSA-függvény Ha az RSA-probléma nehéz, akkor az 1.20 RSA-kísér- letben deniált � 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üggvé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 Legyen � és � ≡ 3 (mod 4), és � = �� . Amennyiben a faktorizációs probléma nehéz, akkor az �� (�) = �2 mod � 33 függvény egyirányú kiskapufüggvény. Nem invertálható, a kiskapu-információ az � 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 Ha a diszkrét logaritmus probléma az 1.22 kísérlet- ben deniált � generátorra nézve nehéz, akkor a � -adrend¶, � által generált � ciklikus csoportbeli exponenciális függvény, azaz az � : Z� �; � ↦ � � leképezés 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 DieHellmanféle ötlettel ilyen is

konstruálható bel®le. Diffie–Hellman függvény Tekintsük az 1.24 kísérletben deniált � által generált � -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, akkor az ��,�,�,ℎ : � �; ℎ� ↦ � � függvény egyirányú kiskapu-permutáció. A kiskapu-információ az � kite−1 � � � � � � v®, a függvény inverze az ��,�,�,� (�) = � , mely tehát � -hez a (� ) = (� ) = ℎ� elemet rendeli.5 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} . Fogalmazhatunk ú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 � objektumra vonatkozó valamilyen adatot a táblázat �(�)-edik cellájába tesz, ha az üres, ahol � a hash függvény. Nyilván akkor jó egy ilyen � függvény, ha ritkán fordul el® ütközés, azaz ritkán esik meg, hogy �(�) = �(�) két különböz® � és � 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ó � = (�, ℋ) párt értünk, ahol 1. � ←

�(1� ), 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 jelenti, hogy nehéz találni két olyan � és � sztringet, melyre �� (�) = �� (�). 1.33 definíció A � = (�, ℋ) hash függvény ütközésálló ha tetsz®leges véletlen polinomidej¶ � algoritmusra  melynek inputja a � által

generál 35 � kulcs, kimenete egy (�, �) pár , létezik olyan elhanyagolható � függvény, hogy P[�� (�) = �� (�)] ⩽ �(�). A denícióból egyrészt világos, hogy egy ilyen �� függvény szükségképpen egyirányú, másrészt ha ismerünk egy (�, �� (�)) párt, akkor nehéz megváltoztatni �-et úgy, hogy hash értéke, azaz �� (�) ne változzék (erre 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 � algoritmust. Legyen (�, �, �) ← �(1 ), legyen ℎ ← � ′ egy véletlen elem, és legyen � = (�, �, �, ℎ) a � = (� , ℋ) 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. 1.35 tétel Ha a diszkrét logaritmus probléma nehéz az 122 kísérletben de- finiált � algoritmusra nézve, akkor az 1.34 konstrukcióban megadott Diffie– Hellman hash függvény ütközésálló. 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 Kis � 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 � -ból � egy egészek fölött elvégzett egyszer¶ köbgyökvonással megkapható. 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: 1.36 tétel (Coppersmith, 1997) Legyen � pozitív egész, � ∈ Z[�] egy �- edfokú polinom, és � = � 1/�−� , 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. Mindennek ellenére van az

RSA-függvényre épül® rejtjelez®nek olyan implementációja, ahol � = 3, de így természetesen � garantáltan nem kicsi. Kis � közös üzenettel Az egyszer¶ség kedvéért legy � = 3, és legyen �1 , �2 , �3 három páronként 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 Az el®z® gyenge megoldás látszólag könnyen javítható, ha a közös � érték elé megkülönböztet® jelzést, paddinget teszünk, pl. legyen �� = (� · 2� + �)3 mod �� ,

� = 1, 2, 3 Meglep® módon ekkor is meghatározható � a �� é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. 1.37 tétel (Hastad) 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 �� (�) ≡ 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. Tekintsük az ��� ,�� 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ó, 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 rejtjelez®, kis � a dekódoló futási idejét csökkenti. Meglep® módon, csak az � és az � = �� szám ismeretében megszerezhet® a kiskapu-információ, azaz �, ha az kicsi 1.38 tétel (Wiener, 1990) Ha � = �� , � < � < 2� és � < 3 √ � , akkor � 1 4 és � ismeretében � polinom időben meghatározható. �

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, hogy egy adott � -elem¶ halmazba esik, akkor � -ben lineáris lépésben az � = � (�) értékb®l meghatározhatjuk �-et. Tegyük fel, hogy tudjuk, 0 ⩽ � < � � ö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. input: a nyilvános kulcs (�, �); a rejtett szöveg �; a szöveg hossza � output: �, ahol �� mod � = � és � hossza �. � ← ( 12 , 1) � = 2�� for � = 1 to � do �� = ��� mod � end � sort (�, �� )|�=1 a második elemek szerint for � = 1 to � do if �� mod � = �� valamelyik � -re then return � · � mod � 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 < �, � ⩽ 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 = �� , és ismerjük az ��,�� 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 � válasz erre is határozott nem! Az RSA-függvény egyirányú kiskapu-permutáció volta azonnal megsz¶nik, ha az �� = ��,�� (�)

értékeket relatív prím �1 és �2 kitev®vel is hozzáférhet®vé válnak. Mivel �1 és �2 relatív prímek, ezért létezik olyan � és � , hogy ��1 + ��2 = 1, így viszont ��1 ��2 = ���1 ���2 = ���1 +��2 ≡ �1 = � mod �. Megváltoztathatóság Ha csak annyit tudunk, hogy � = � (�) = � � mod � argumentuma egy olyan � érték, mely egy számadat, akkor megváltoztathatjuk � é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 � 5%-a egész szám, akkor 19 � � · ( 20 ) mod � dekódolás után 0.95�-et ad Implementációk elleni támadások 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 a dekódoló nem a kapott � -t emeli �-edik hatványra, hanem választ egy � � véletlen számot, és a � = �� 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. 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 �), de �¯� ̸≡ � (mod �). Ebb®l pedig következik, hogy gcd(�, � ¯� −�) = �. 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 2 és Tipikus alkalmazásokban e test az F� véges test, ahol � > 3 prím. 3 2 Legyen �, � ∈ F olyan, hogy 4� + 27� ̸= 0. Az � 2 = �3 + �� + � (6) egyenletet kielégít® (�, �) ∈ F × F pontok, valamint egy végtelen távolinak 7 3 2 nevezett � 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 3 Az � = � + �� + � egyenletb®l világos, hogy a függvény grakonja valós esetben 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 A projektív sík legyszer¶bben úgy modellezhet®, hogy a 3-dimenziós 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ározza meg. Minden [�, �, �] vektornak megfelel egy projektív pont, kivéve a nullvektort. Ha � ̸= 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 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 3 egyenletet tekintjük, akkor � ̸= 0 esetén, � -bel való leosztás után az (︂ )︂2 (︂ )︂3 (︂ )︂ � � � = +� +� � � � = �, �� = � helyettesítés után megegyezik a (7) egyenlettel. Ha viszont � = 0, akkor � -nek is 0-nak kell lennie, így a [0, �, 0] vektoroknak (� ̸= 0) megfelel® végtelen távoli pont is kielégíti a (8) egyenletet. Ezt a végtelen távoli pontot � -val jelöljük, és úgy tekintjük, hogy egyenlethez jutunk, ami az �

� 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 konja: 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¶ ciklikus), (�) 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 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 �-rel jelölve, a � és � összegén ennek �-tengelyre való tükörképét fogjuk jelölni. Ha � = �, akkor 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 együtthatójának −1-szerese), és mivel a másik két gyök �1 és �2 , ezért a A gyökök és együtthatók összefüggése szerint a gyökök összege harmadik �3 = � 2 − � 1 − �2 . Ha � + � koordinátás alakja (�3 , �3 ), akkor az egyenesen az (�3 , −�3 ) pont van, ahonnan �= −�3 − �1 , �3 − � 1 ahonnan �3 = �(�1 − �3 ) − �1 . 46 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: �+� =� � + � = �, azaz bármely (�, �) ∈ ℰ esetén (�, �) + � = (�, �) � − � = �, azaz bármely (�, �) ∈ ℰ pontra − (�, �) = (�, −�) Az utóbbi összefüggést az {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 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 � ⩽ |ℰ| ⩽ � + 1 + 2 �. A pontos érték a hatékony Schoof-algoritmussal számolható. Ha ℰ egy F� fölötti elliptikus görbe (� > 3), akkor a rajta deniált csoporthoz létezik két olyan �1 és �2 szám, hogy ⟨ℰ, +⟩ ∼ = Z�1 × Z�2 , 47 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. = �3 + � + 1 az egyenlete, 14 pontú, csoportja izomorf Z14 -gyel, egyik generátoreleme (1, 6): A harmadik elliptikus görbe, melynek � 2 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 2-elem¶, a másik 6-elem¶: ℰ∼ = Z2 × Z6 , ∼ Z2 = {�, (2, 0)}, Z6 ∼ = {�, (4, 2), (4, 9), (9, 0), (10, 5), (10, 6)}, és valóban, 2 | 12 é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ímfaktora, tehát � = ��1 + 1, ahol �1 nagy prím, és � pozitív egész, 2. (�1 − 1)-nek is van nagy prímfaktora, azaz �1 = ��2 + 1, ahol �2 nagy prím, és � pozitív egész, 3. � + 1-nek is van nagy prímfaktora, azaz � = ��3 − 1, ahol �3 nagy prím, és � pozitív egész. 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 kiszá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 � választandó, melyre � − 1 és � + 1 legnagyobb � prímfaktora 19 ki kell elégítse a log� (�) > feltételt. 20 49 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 � értékét. A közös kulcs �� lesz. A támadónak átlagosan a feladványok felét fel kell törnie, hogy megtudja, melyik az �-edik üzenet és ezzel megtudja a �� kulcsot. Diffie-Hellman kulcscsere 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 1� biztonsági paraméter. 50 1. Aliz: egy véletlen

polinomidej¶ � 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 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 CDHproblé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ó. 2.2 tétel Ha a DDH probléma nehéz, akkor a Diffie-Hellman kulcscsere protokoll biztonságos egy hallgatózó jelenlétében. 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 Támadó: (�, �, �, ℎ1 ). � � 2. Támadó: � ← Z� , ℎ� = � , �� = ℎ1 51 Támadó Bob: (�, �, �, ℎ� ). � � �� 3. Bob: � ← Z� , ℎ2 = � , �� = ℎ� = � Bob Támadó: ℎ2 � � � �� �� 4. Támadó: � ← Z� , ℎ� = � , �� = ℎ1 = � , �� = ℎ1 = � Támadó Aliz: ℎ� � �� 5. 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ó ismeri az �0 és �1 sztringeket, akkor ki tudja számolni az 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! 2. Mivel az egyirányú kiskapufüggvények determinisztikusak, ha bel®lük akarunk aszimmetrikus rejtjelez® E algoritmust konstruálni, az argumentumuknak 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 � = � (�) ismeretében az

�-r®l semmi információ nem szerezhet® meg. Így az sem elég, hogy E nem determinisztikus! Valahogy az �-r®l az � 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ó one time pad (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�� (�) = (�� (�), �(�) ⊕ �), tehát E�� : �� × �� �� × �� . 3. D: D�� (�1 , �2 ) = �(��−1 (�1 )) ⊕ �2 . −1 Könnyen ellen®rizhet®, hogy D�� E�� (�) = �, ugyanis � = �� (�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. Ez tökéletes biztonságot nyújtana, ha nem itt és most kéne az � -et is átadni. Azt csak úgy tudjuk átadni, hogy elhanyagolható eséllyel megszerezhet®, ezt nyújtja az egyirányú �� kiskapupermutá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 � -r®l, amit egy támadó megszerezhet róla. Erre szolgál a � 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 � számot, azonban minden üzenetváltást följegyez, így ha kés®bb ugyanaz az � érkezik, mint egyszer már korábban, válaszul ugyanazt az � -et 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 2.4 tétel Amennyiben az egyirányú kiskapu-permutációk (� TDP , �, � −1 ) csa- lá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. 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� , �, �)) = � (�)] ⩾ �(�). E bizonyításhoz magunk deniálunk egy orákulumot, melyet a � helyébe helyettesítünk. Ezt az algoritmust ℋ RO fogja jelölni (RO a random oraculum kifejezésb®l). Legyen tehát �0 és �1 a két üzenet, melyekre |�0 | = |�1 |. Legyen E�� (�� ) = (�1 , �2 ), ahol � egy véletlen bit. Az � algoritmus az 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 ℋRO algoritmust. RO algoritmus egy

listában följegyez minden hozzá beérkez® � értéA ℋ RO (�) értékeket egy ket, ennek a listának a neve RL lesz, míg a visszaadott ℋ 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 (�1 , �2 ) pár véletlenszer¶en vagy az �0 vagy az �1 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. Végül meg kell mutatnunk, hogy a ℬ algoritmus legalább � valószín¶séggel megtalálja � inverzét. Megbecsüljük annak valószín¶ségét, hogy � sikeres 55 function ℬ(1� , �, �) global RL, HL, ℎ (az RL és HL listák aktuális hossza ℎ) function ℋRO (�) �=1 InRL = FALSE while � ⩽ ℎ AND NOT InRL do if

RL[�] = � then InRL = TRUE else �=�+1 end end if InRL then return HL[�] end if � (�) = � then � ← {0, 1} (egy véletlen bit) � = �2 ⊕ � � 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 � inverzét kiszámító ℬ algoritmus, és benne a ℋRO 56 algoritmus pszeudokódja, melyet az � sokszor meghívhat az kísérlet közben ExpindCPA �,Π (�) lesz �0 és �1 megkülönböztetésében: [︀ ]︀ P ExpindCPA �,Π (�) = 1 = [︀ ]︀ [︀ ]︀ −1 P ExpindCPA (�) ∈ �� · P � −1 (�) ∈ �� + �,Π (�) = 1 | � [︀ ]︀ [︀ ]︀ −1 P ExpindCPA (�) ̸∈ �� · P � −1 (�) ̸∈ �� �,Π (�) = 1 | � Világos, hogy [︀ ]︀ 1 −1 P ExpindCPA

(�) ̸∈ �� = , �,Π (�) = 1 | � 2 ugyanis � −1 (�) ismerete nélkül nem lehet választani �1 és �1 közül. Mivel [︀ ]︀ −1 P ExpindCPA (�) ∈ �� ⩽ 1, �,Π (�) = 1 | � és feltételezhetjük, hogy a kísérlet 1 -nél nagyobb valószín¶séggel sikeres, azt 2 kapjuk, hogy [︀ ]︀ 1 + �(�) ⩽ P ExpindCPA �,Π (�) = 1 2 [︀ ]︀ 1 [︀ ]︀ ⩽ P � −1 (�) ∈ �� + P � −1 (�) ̸∈ �� 2 [︀ −1 ]︀ 1 ⩽ P � (�) ∈ �� + . 2 Így [︀ ]︀ P � −1 (�) ∈ �� ⩾ �(�), vagyis nem elhanyagolható valószín¶séggel sikerült invertálni � -et. A szükséges lépések száma pedig polinomidej¶, hisz ha �� az �, �� az � futási ideje, és � ℎ-szor hívja meg az orákulumot, akkor az invertálás futási ideje �� + �(ℎ2 + ℎ�� ). 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 bit �1 bit � �0 bit 0000 � G H � − �0 bit �0 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ú � algoritmus mely egy � nyílt szöveget 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 � bites a paddingelt szöveg hossza, ebb®l �0 a véletlen � szám bithossza, és �1 a zérusok száma. Így az � üzenet � − �0 − �1 bites � : {0, 1}�0 {0, 1}�−�0 és � : {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 TDP , �, � −1 ) Deniáljuk a Π = (�, E, D) 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 szemantikailag 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: � : (�, �, �� ) ← � 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 (︀ )︀ s 2. E: � ← � � , E�� (�) = �� (�), E�(�) (�) , tehát a szimmetrikus kulcsú rejtjelez® kulcsa a �(�) érték lesz, ahol � egy véletlen elem. 1. 60 3. D: � = �(��−1 (�1 )), D�� (�1 , �2 ) = Ds� (�2 ). Könnyen ellen®rizhet®, hogy D�� E�� (�) = �, ugyanis az

üzenethez mind kó−1 doláskor, mind dekódoláskor az � = �(�) = �(�� (�1 ) szimmetrikus kulcsot 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. a a a 2.8 konstrukció (Hibrid rejtjelez®) Legyen Π = (� , E , D ) egy aszims s s metrikus kulcsú, és Σ = (� , E , D ) egy szimmetrikus kulcsú rejtjelez®. Az * üzenet egy tetsz®leges � ∈ {0, 1} sztring. Deniáljuk a Π = (�, E, D) 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 E�� (�) = (�1 , �2 ). 3. A 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 Σ szemantikailag biztonságosak, akkor a hibrid rendszer is. 61 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 �(�) < 2� − 1, ahol �(�) az

üzenet � ∈ {0, 1} . 1. � : (�, �, �) ← � RSA (1� ), �� = (�, �), �� = (�, �). 2. E: � ← {0, 1}ℓ(� )−�(�)−1 , E�� (� ) = (� ‖ �)� mod � , ahol � választása * olyan, hogy (� ‖ �) ∈ Z� , 3. D: D�� (�) = (�� mod � utolsó �(�) bitje). Bár azt sejtenénk, hogy ha �(�) ≈ �, pl. �(�) = �� valamilyen � < 2 konstansra, akkor a 31 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) s s s 9 Legyen � egy hash-függvény, pl. � = SHA256 ∘ SHA256 , és Σ = (� , E , D ) egy szimmetrikus kulcsú rejtjelez®. Deniáljuk a Π = (�, E, D) aszimmetrikus 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 mask generation function ) szerepel, ami egy fajta hash függvény, ahol az output mérete független hash függvény helyett a protokollban MGF (ún. 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) MLen sztring (MLen bájt hosszú). De- 8 Az üzenet egy tetsz®leges � ∈ {0, 1} niáljuk a Π = (�, E, D) aszimmetrikus kulcsú rejtjelez®t a

következ®képp: 1. � : (�, �, �) ← � RSA (1� ), �� = (�, �), �� = (�, �). 2. Az E algoritmus bemenete a �� nyílt kulcs, az � üzenet és egy opcionális � 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 bájt DB = lHash ‖ PS ‖ 0�00 ‖ � seed ← {0, 1}8HLen maskedDB = DB ⊕ MGF(seed, ℓ(� ) − HLen − 1) maskedSeed = seed ⊕ MGF(maskedDB, HLen) EM = 0�00 ‖ maskedSeed ‖ maskedDB E�� (�[, �]) = (EM)� mod � . D algoritmus bemenete a � kriptoszöveg, a titkos �� kulcs és az opcionális � címke. Az algoritmus lépései: 3. A 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. Némi óvatosságra int, hogy a CCA-biztonság bizonyításában, ha egy � 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¶ csoportot, 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: Jelölje (�1 , �2 ) az E�� (�) kimenetét, ekkor 3. D�� (�1 , �2 ) = �2 . ��1 Könnyen ellen®rizhet®, hogy D�� E�� (�) = �, 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 véletlen elem, akkor a � csoport ′ egy tetsz®leges � elemére P[� · � = � ′ ] = P[� = �−1 · � ′ ] = 1 , |�| vagyis itt is arról van szó, hogy ha � -t nem a rejtjelezett szöveggel együtt kéne elküldeni, akkor az � · � tökéletes biztonságot nyújtana. Így bizonyítható az alábbi tétel: 3.5 tétel Ha a DDH-probléma nehéz, akkor a 34 konstrukcióban megadott ElGamal rejtjelező szemantikailag biztonságos. 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 Z� helyett annak egy megefelel® részcsoportját választani. Ha a kvadratikus maradékok (azaz a négyzetelemek) csoportját választjuk, akkor egy (� − 1)/2-elem¶ részcsoportot kapunk, mivel négyzetelemek szorzata és inverze is négyzetelem. Ha ráadásul � biztonságos prím, azaz � = 2� + 1 alakú, ahol � 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. A biztonsági paraméter függvényében tehát �-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 példán szemléltetjük: 3.6 példa Legyen � = 359, � = 2� +1, ahol � = 179 (a példa szépségéért itt � mellett � is 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 � ¯ = 103. 2 Így � = 103 mod 359 = 198 ∈ �. Legyen a véletlen elem � = 138 ∈ 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 �+1 ±198 4 mod � = ±19890 mod 359 = ±256 mod 359 = {256, 103} Mivel e két szám közül 103 < 179, ezért 103 az üzenet. Elliptikus görbére épülő rejtjelező 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. A görbe pontjainak tárolására az (�, �) an alak használható, azonban tudjuk, hogy a görbe szimmetrikus az �-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 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 � egy Z� fölötti ℰ elliptikus görbét generáló algoritmus, mely az elliptikus görbe csoportban 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 kulcs, azaz �� = (�). � = �� az ℰ egy másik pontja, a publikus kulcs �� = (ℰ, �, �, �, �, �). 2. E: � ← Z*� , � ∈ Z� , E�� (�) = (��, � · �� mod �), ahol �� = (�� , �� ), és �� ̸= 0. 3. D: Jelölje (�1 , �2 ) az E�� (�) kimenetét, ahol �1 ∈ ℰ , �2 ∈ Z*� . Ekkor az (�� , �� ) = � · �1 jelöléssel D�� (�1 , �2 ) = �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 6. ábra A 14-pontú elliptikus görbe egy 7-pontú része, melyen a pontm¶velet egy Z7 -tel izomorf csoportot ad. A görbe � csoporthoz nem

tartozó pontjait 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), �� = 2 · (0, 1) = (3, 3), tehát �� = 3, így (��, � · �� mod 11) = ((6, 6), 1). A dekódoláshoz vegyük a (�1 , �2 ) = ((6, 6), 1) párt, és a titkos kulcsot, ami 3, így (�� , �� ) = 3 · (6, 6) = (3, 3), tehát �2 1 mod � = mod 11 = 4 �� 3 tehát az üzenet 4. (Ha számolás közben a pontok tömör formáját használjuk, akkor � = (3, 0), � = (0, 1), 2� = (6, 0), 2� = (3, 1).) 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 paramé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 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 véd? 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 Merkle's 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