I. Vajda, Feladattár megoldásokkal. Tartalom:

I. Vajda, 2005 Feladattár megoldásokkal

Tartalom: Bonyolultságelméleti alapok Bonyolultsági osztályok Bonyolultságelmélet primitívek: OWF, PRG, PRF, PRP Eloszlások polinomiális megkülönböztetése Rejtjelezés Szimmetrikus kulcs biztonság fogalmak biztonságos rejtjelezési módok Aszimmetrikus kulcs biztonság fogalmak bizonyítás véletlen orákulum modellben biztonságos rejtjelező algoritmusok Hitelesség Kriptográfiai lenyomatkészítés (hash függvény) MAC Digitális aláírás Egyéb

1

Bonyolultságelméleti alapok Bonyolultsági osztályok F1: Tekinsük az összetett számok faktorizációját, mint BPP nyelv eldöntési problémát. A Rabin-Miller primtesztet véletlen polinomiális idejű M Turing gépként tekintve, adja meg a döntési pontosságot! [L={összetett szám}. x egy egész szám. M(x)=1, ha M összetett szám inputra dönt, M(x)=0, ha M prímszám inputra dönt. P(M(x))=1) ≥ 3/4, ha x∈L, illetve P(M(x))=0)=1, ha x∉L.]

F2*. Bizonyítsuk be, hogy BPP osztály definíciójában 2/3 valószínűségi konstans szerepel. Legyen M véletlen polinomiális idejű Turing gép

1 1 döntési + 2 p (| x |)

pontossággal, ahol p(.) egy polinom, továbbá x az M inputja.. Mutassa meg, hogy M alapján konstruálható egy M' gép, amelynek pontossága legalább 2/3! [M' futtasson O(p(|x|)2) példányt M gépből, azonos x inputtal. Az outputok alapján végezzen majoritásos döntést. Használja a Csebisev-egyenlőtlenséget. Legyen yi az i-edik gép outputja:

⎛1 n ⎞ ⎛1 n ⎞ ⎜ ⎟ P⎜ n ∑ yi > 1 / 2 ⎟ = P⎜⎜ n ∑ yi − E ( yi ) > 1 / 2 − E ( yi ) ⎟⎟ ⎝ i =1 ⎠ ⎝ i =1 ⎠ ⎛ n ⎞ ⎛ n ⎞ 1 − P⎜⎜ 1n ∑ yi − E ( yi ) ≤ δ ⎟⎟ ≥ 1 − P⎜ 1n ∑ yi − E ( yi ) ≤ δ ⎟ ⎜ ⎟ ⎝ i =1 ⎠ ⎝ i =1 ⎠ ahol δ = 1 / 2 − E ( yi ) = 1 / 2 − (1 / 2 + 1 / p ( n)) = −1 / p (n) < 0. A Csebisev- egyenlőtlenség felhasználásával

⎛ 1 − P⎜ ⎜ ⎝ =1−

Így

1 n

σ y2i ⎞ ∑ yi − E ( yi ) ≤ δ ⎟⎟ > 1 − 2 δ ⋅n i =1 ⎠ n

(1 / 2 + 1 / p (| x |)(1 / 2 − 1 / p (| x |)

n = p(| x |) 2

δ 2 ⋅n

1 ⎛⎜ p (| x |) 2 ⎞⎟ =1− −1 ⎟ n ⎜⎝ 4 ⎠

választással 2/3 feletti valószínűség adódik. ]

2

Bonyolultságelmélet primitívek: OWF, PRG, PRF, PRP F1*. Az alábbi feladat három részfeladata együttesen az bizonyítja, hogy bizonyítást adni biztonságos szimmetrikus kulcsú kriptorendszerre legalább olyan nehéz feladat, mint a P≠NP algoritmuselméleti alapproplémára bizonyítást adni. Más szavakkal biztonságra vonatkozó bizonyításunk nem bizonyított feltételen alapul, s "legtöbb amit tehetünk" az az, hogy lehetőleg minél "erősebben sejtett" nehéz feladatra alapozzuk a feltételünket, mint például az egész számok faktorizációjának problémájára! Vezessük le a következő bizonyítási láncot: PRF→PRG→OWF→{P≠NP}: a.) Mutassuk meg, hogy ha létezik egyirányú függvények f1 , f 2 ,... együttese, akkor P≠NP. b.) Ha G : {0,1}n → {0,1}2 n egy (t (n), ε (n)) -biztonságú PRG (azaz amelyet tetszőleges t(n) erőforráskorlátú támadó legfeljebb ε (n) megkülönböztetéssel tud támadni), akkor

f ( x, y ) = G ( x), | x |=| y |= n egy olyan egyirányú függvény (t (n), ε (n) + 2 − n ) -biztonságú. c.) Ha F : {0,1}n x{0,1}n → {0,1}n , (t (n), q (n), ε (n)) -biztonságú PRF, ahol q>1 az orákulumkérések számának korlátja, akkor létezik egy (t (n), ε (n)) -biztonságú hosszkétszerező PRG. [a.) A bizonyítás lényege a következő: egy NP bonyolultság-osztálybeli L nyelvet konstruálunk. Ha tudnánk konstruálni egy polinomiális idejű algoritmust a nyelv eldöntésére, akkor az egyirányú függvény tudnánk polinomiális időben invertálni. Ez viszont ellentmondana az egyirányúság tulajdonságnak, következésképp P≠NP: Legyen L = {{a, b, f n ( x), n} | ∃y : a ≤ y ≤ b, f n ( y ) = f n ( x)} . Nyilván L∈NP, hiszen bármely inputra - így egy tanúra is - definició szerint polinomiális időben kiszámítható egy egyirányú függvény outputja. Tegyük fel, hogy L∈P. Ez azt jelentené, hogy egy tanút polinomiális időben tudnák találni, ami azt is jelentené, hogy az egyirányú függvény polinomiális időben tudnánk invertálni. Azonban az egyirányú függvények együttese polinomiális idejű algoritmussal nem invertálható. Így mivel L∈NP, de L∉P, következik, hogy P≠NP. b.) Tegyük fel, hogy tetszőleges, t(n) erőforráskorlátú M megkülönböztető algoritmusra

| P[ M (G (U n )) = 1] − P[ M (U 2 n ) = 1] |< ε (n) Indirekt bizonyításként, tegyük fel, hogy létezik olyan, t(n) erőforráskorlátú Z invertáló algoritmus, amelyre P[ f ( Z ( f (U n ))) = f (U n )] > ε (n) + 2 − n . Z alapján konstruáljunk egy Z' algoritmust, amelyre Z'(y)=1, ha Z ki tudja számítani y inverzét, azaz ha G(Z(y))=y, egyébként legyen Z'(y)=0. Így P[ Z ' (G (U n )) = 1] > ε + 2 − n . Nyilván P[ Z ' (U 2 n ) = 1] ≤ 2 − n , ugyanis már annak a valószínűsége is csak 2 n / 2 2 n = 2 − n hogy az r a G egy lehetséges outputja (és Z az outputoknak is csak töredékét képes invertálni). Innen az alábbi ellentmondásra jutunk:

3

| P[ Z ' (G (U n )) = 1] − P[ Z ' (U 2 n ) = 1] |> ε (n) . c.) Legyen G ( x) = Fx (0) || Fx (1) . Indirekt bizonyításként tegyük fel, hogy G(x) nem (t,ε)biztonságú PRG, azaz létezik Z algoritmus, amelyre

| P[ Z (G (U n )) = 1] − P[ Z (U 2n ) = 1] |> ε Ekkor belátható, hogy F nem lehet (t,q,ε)-biztonságú PRF, azaz ellentmondásra jutunk. A Z algoritmust felhasználó Z' algoritmus célja F megkülönböztetése a megfelelő dimenziójú H 2 n véletlen függvénytől: Z' kétszer fordul az O orákulumhoz, u=(Un,0) illetve v=(Un,1) kéréssel, s ha O=F, akkor c1=FUn(0) és c2=FUn(1) válaszokat, míg ha O= H 2 n , akkor c1= H 2 n (u) és c2= H 2 n (v) válaszokat kapja. Ezután futtatja Z algoritmust (c1,c2) inputtal, amelynek válasza alapján a fenti egyenlőtleségnek megfelelően >ε sikerrel meg tudja különböztetni a kétféle esetet.

]

Egyirányú függvény: OWF F1: Legyen flen(x)=y, az x input bitben mért hosszát y bináris számként megadó függvény. Egyirányú-e ez a függvény, ha az invertáló algoritmus időkorlátja a.) poli(|flen(x)|) b.) poli(|x|) [a.) Igen (formálisan). Mivel |flen(x)|=log2|x|, ezért, nem lenne olyan algoritmus, amely invertálni lenne képes flen(x) függvényt poli(|flen(x)|) időben - egyszerűen nem lenne ideje arra, hogy kiírja az input bitjeit. b.) Nem. Az flen(x) leképezés triviálisan invertálható poli(|x|) időben.]

F2: Egy Z "invertáló" algoritmus véletlenszerűen választ egy inputot. Mekkora a siker valószínűsége, ha a.) f permutáció b.) f konstansba képezi le azonos hosszú inputjait. [a.) 1/2n, b.) 1]

F3. Formálisan adja meg a következő problémákon alapuló egyirányú függvény jelöltek definícióját: a.) egész szám faktorizáció, b.) véletlen lineáris kód dekódolása, c.) részhalmaz-összeg feladat. d.) diszkrét logaritmusképzés e.) négyetgyökvonás mod n [ a.) f(x,y)=x⋅y, ahol |x|=|y|; b.) f(G,x,d)=(G, xG+e(d)), ahol G a véletlen generátor mátrix, x az üzenet-vektor, e(i) egy véletlen, ≤d Hamming-súlyú hiba-vektor;

4

c.) f ( x1 , x2 ,..., xn , I ) = ( x1 , x2 ,..., xn , ∑ xi ) , ahol | x1 |=| x2 |= ... =| xn | és I ⊆ {1,2,..., n} . i∈ I

...]

F4. Igazolja vagy cáfolja a következő állítást: ha f(x) egy erősen egyirányú függvény, akkor g(.) függvény g(x,p)=

(f(x),p), ha p log2|x| számú zérussal kezdődik (x,p), egyébként

is erősen egyirányú függvény marad, ahol |x|=|p|=n,. [Nem igaz, mivel g(.) legalább 1-1/n valószínűséggel invertálható.]

F6. Formálisan adja meg a következő egyirányú függvénykolleciók (jelöltek) definícióját, taglalva az (I,D,F) algoritmushármast: a.) RSA függvényre , b.) Rabin függvényre, c.) diszkrét logaritmus (DLP) problémára alapozva. [O.G. 54-57] F7. Formálisan adja meg az RSA csapda egyirányú permutációt. [...] F8*. Igazolja vagy cáfolja, hogy a következő, a Gráf Izomorfizmus nehéz problémára épülő függvény egyirányú-e. Legyen f GI (G, π ) = (G, πG ) , ahol G egy irányítatlan gráf, π egy permutáció, amely átnevezi a gráf csúcsait, azaz (π (u ), π (v)) egy él a πG gráfban a.cs.a., ha (u,v) él a G gráfban. [Nem egyirányú. Például a csúcsok fokszám-statisztikájából kiindulhatunk az izomorfia feltérképezéséhez ... ]

F9. Adja meg az f (c, x) = (0, x), c ∈ {0,1}, x ∈ {0,1}* függvény keménybit leképezését. [ b (c, x ) = c ]

F10. Igazoljuk, hogy egy f(x) függvény b(x) keménybit leképezése kiegyenlített, azaz a | P(b(U n ) = 0) − P(b(U n ) = 1) | differencia elhanyagolhatóan kicsi. [Ha b nem kiegyenlített, s mondjuk 1 értéket nem elhanyagolhatóan gyakrabban veszi fel, akkor Z' keménybit kiszámító algoritmus outputja legyen konstans 1, azaz Z'(f(x))=1, tetszőleges x esetén. Ezen Z' algoritmus nem elhanyagolható valószínűséggel kiszámolja a keménybitet.]

F11. Mutasson példát olyan f : {0,1}* → {0,1}* függvényre, amely triviálisan nem OWF, ugyanakkor van keménybitje. [f(x)=0|x|]

5

F12. Legyen g ( x1 , x2 ) = f ( x1 ) || f ( x2 ), f : {0,1}n → {0,1}n alakú gyengén egyirányú függvény. Tegyük fel, hogy Z támadó a g függvényt az z=(x1,x2) inputok közül az x1 koordináta lehetséges értékei <1/4 részéhez tartozó outputra nem tudja az inverzet képezni, míg az x2 koordináta tetszőleges értékéhez tartozó outputok esetén tudja invertálni. Adjon meg egy olyan algoritmust, amely tetszőlegesen nagy valószínűséggel képes invertálni az f függvényt. [Véletlen r1 értékre számított y=f(r1) legyen Z' inputja. Z' kisorsol egy véletlen r2 értéket, majd

meghívja Z algoritmust (y,f(r2)) inputtal. Ezt m alkalommal végezve >1-(3/4)m valószínűséggel Z' kiszámítja az f-1(y) inverzet.]

F13*. Egyirányú függvény akkor és csak akkor létezik, ha létezik C(1n) és D(1n) n-bitre képező algoritmuspár (randomizált polinomiális algoritmusok párja), amelyek output eloszlása polinomiálisan megkülönböztethetetlen, továbbá amelyekre q=P{C(1n) és D(1n) output halmazok metszete}≤2n/2. (Az állítás egy informálisabb megfogalmazása: Egyirányú függvény akkor és csak akkor létezik, ha létezik két, hatékonyan mintavételezhető eloszlás, lényegében diszjunkt tartóval, amelyek polinomiálisan nem megkülönböztethetők egymástól) (Megjegyzés: C(1n), D(1n) jelölés értelme a következő: C és D algoritmusok 1n inputot kapnak, belül véletlen elmeket sorsolnak, számításokat végeznek és kiadnak egy outputot. Ebben az értelemben C(1n), D(1n) az outputot is jelöli - hiszen megadtuk a inputot -, azaz kimeneteiken megjelenő valószínűségi változót. Amikor C(1n), D(1n) eloszlásról beszélünk, akkor ezen valószínűségi változók eloszlását értjük alatta.)

[→Ha létezik egyirányú függvény, akkor konstruálható biztonságos G : {0,1}n / 2 → {0,1}n PRG is. Legyen C(1n) output véletlen, s így az output eloszlása statisztikailag egyenletes, továbbá legyen D(1n) output a G által generált. G definíciója szerint a két eloszlás megkülönböztethetetlen, továbbá q≤2n/2. ←Tegyük fel, hogy a két eloszlás megkülönböztethetetlen, s tartóik a fenti értelemben diszjunktak. Legyen C(1n) ismét véletlen leképezés. Ha D(1n) algoritmus r, |r|=m véletlen elemet használ egy outputja kiszámításához, definiáljunk egy f : {0,1}m → {0,1}n leképezést f(r)= D(1n) módon. Legyen továbbá I egy invertáló algoritmus f leképezéshez, valamint Z algoritmus az alábbi: Legyen u az f képterének (D output terének) egy eleme. Z(u)=1, ha f(I(u))=u, azaz ha I algoritmus ki tudta számítani u egy ősképét, egyébként legyen Z(u)=0. Tegyük fel, hogy P ( Z ( D(1n )) = 1) = P( f ( I ( f (r )) = f (r )) ≤ ε , ahol ε nem elhanyagolható. Mivel C(1n) véletlen leképezés, ezért P ( Z (C (1n )) = 1) < 1 / 2 n / 2 , ugyanis Z a C(1n) outputhalmazának csak azon töredékén belül invertálhat sikeresen, amely metsződik D(1n) outputjával. Innen

P( Z ( D(1n )) = 1) − P( Z (C (1n )) = 1) > ε − 1 / 2 n / 2 azaz C(1n) és D(1n) eloszlások megkülönböztethetők ( ε − 1 / 2 n / 2 nem alhanyagolható), amivel ellentmondásra jutottunk az állítás feltételével. Következésképp f biztonságos OWF.]

6

F14. Legyen f : Σ* → Σ* egy egyirányú függvény, és legyen g : Σ* → Σ* egy polinomiálisan kiszámítható függvény. a.) Tekintsük az < f , g > függvényt, ahol < f , g > ( w) = f ( w) || g ( w) . Mutassuk meg, hogy g választható úgy, hogy bármely f esetén < f , g > nem egyirányú. b.) Egyirányú-e az f D g , illetve az g D f összetett függvény? c.) Tegyük fel, hogy Σ = {0,1} és mindkét függvény (f és g) hossztartó. Egyirányú-e az f ⊕ g : w → f ( w) ⊕ g ( w) függvény? d.) Ha létezik f egyirányú függvény, mutassuk meg, hogy létezik olyan f’ egyirányú függvény, amelyhez létezik polinomiális idejű Z algorritmus, amely ki tudja számítani w paritását f'(w) ismeretében. [ a.) g(w)=w b.) Nem, pl. legyen g(w)=0 tetszőleges w esetén. Igen. Indirekt bizonyítás. Ha g D f nem lenne egyirányú, akkor g leképezés lehetne azon Z algoritmus első lépése, amely algoritmus f inverzét nem elhanyagolható valószínűséggel számolná. c.) Nem, pl. f=g. d.) f ' ( w) = f ( w) || w1 + ... + w|w| ]

F15. Legyen f : Σ* → Σ* egy hossztartó egyirányú függvény, és legyen g : Σ* → Σ* egy hossztartó, polinomiálisan kiszámítható függvény. Mutassuk meg, hogy az alábbi függvény egyirányú: ( f , g ) : x || y → f ( x) || f ( y ) [Indirekt. Ha (f,g) nem egyirányú, akkor létezik Z algoritmus, amelyhez létezik p polinom, hogy legalább 22n/p(n) számú (2n bites) inputhoz tartozó output invertálható. Vegyük észre, hogy ebből következik, hogy az f függvény vonatkozásában legalább 2n/p(n) számú (n bites) inputhoz tartozó output invertálható, ami ellentmond f egyirányúságának..]

7

PRG

F1*. Igazoljuk, hogy az álvéletlen generátor outputja nem lehet valódi véletlen. [jegyzet részben]

F2*. Mutassunk konstrukciót arra az esetre, amikor a.) egy PRG (álvéletlen generátor) 1-1 értelmű leképezés, illetve arra is, amikor ez nem áll fenn, azaz b.) egy PRG különböző input értéket (véletlen magot) azonos outputba (álvéletlen sorozatba) képez le. [a.) Legyen G : {0,1}n → {0,1}n +1 , s tekintsük a Blum-Micali-Yao konstrukciót, azaz egy F : {0,1}n → {0,1}n biztonságos egyirányú permutációval képezzük le a véletlen magot, majd hosszabbítsuk meg egy bittel, amit F keménybitje szolgáltat. b.) Legyen G ': {0,1}n −1 → {0,1}n +1 egy biztonságos PRG, s legyen G(x,b)=G'(x), ahol b egy bit ((x,0) és (x,1) ugyanabba az G'(x) outputba képződik, s így G' nem 1-1 értelmű). Azt kell még belátni, hogy G is biztonságos PRG. Induljunk ki a PRG definíciójából és alkalmazzuk a feltételes valószínűség technikát b=0 illetve b=1 feltételekkel. ]

F3*. Definíció szerint G egy PRG, ha {G (U n )}n∈N és {U l ( n) ) n∈ N polinomiálisan megkülönböztethetetlenek. Bizonyítsuk be, hogy G (U n ) bithossza elhanyagolhatóan kicsi valószínűséggel nem l(n), azaz P[| G (U n ) |≠ l (n)] valószínűség elhanyagolható (nben). [Indirekt. Ha az állítás nem lenne igaz, létezne hosszmérést végző Z megkülönböztető algoritmus: Z inputja w, amely vagy a generátor egy kimenete vagy egy l(n) hossszú véletlen sorozat. Z algoritmus p(n) alkalommal kisorsol véletlen magot, majd generáltatja G-vel hozzájuk az outputot. Méri az outputok hosszának minimumát. Ha ez a minimum kisebb, mint |w|, akkor Z(w)=1 (arra dönt, hogy w a generátor egy outputja volt), egyébként a Z(w)=b, ahol b pénzfeldobás bit. Formálisan analizálja Z megkülönböztető erejét!].

F4. A klasszikus, egy bittel (a keménybittel) hossznövelő PRG konstrukciójánál az f egyirányú függvény f(s) outputjához toldjuk a b(s) keménybitet: f(s)b(s) az output. Igazoljuk, hogy ha b(s)f(s) outputot képzünk, szintén PRG-t kapunk. [Tekinsük a PRG definicióját, s vegyük figyelembe, hogy a sorrendcsere egy polinomiális lépés.]

F5. Legyen G egy PRG, továbbá h egy polinomiális időben számítható permutáció. Igazoljuk, hogy G'(s)=G(h(s)), illetve G''(s)=h(G(s)) is PRG. [G'-höz: h(s) eloszlása egyenletes, ha s eloszlása egyenletes, továbbá G' polinomiális időben kiértékelhető marad.

8

G"-höz: A PRG definícióját tekintsük. h(U l (n) ) és U l (n) eloszlása azonos (egyenletes), így

| P( Z [h(G ( s ))] = 1) − P ( Z [h(U l ( n) )] = 1) |=| P( Z ' (G ( s )) = 1) − P( Z ' (U l ( n) ) = 1) | különbséget tekintjük, ahol Z'=Z°h. Ha tehát Z megkülönböztető algoritmus lenne G'' PRG esetén, akkor Z' megkülönböztető algoritmus lenne G PRG esetén. Továbbá G" polinomiálisan kiszámítható. (Vegyük észre, hogy itt nem használtuk ki, hogy h permutáció.) ]

F6. Legyen G egy PRG l(n)=n+1 hossznöveléssel. Legyen G'(s) az a leképezés, amelyet G p(|s|) számú iteratív alkalmazásával nyertünk: G ' ( s ) = G p (|s|) ( s ) , G ( 0 ) ( s ) = s, G ( i +1) ( s ) = G (C (G (i ) ( s ))) , ahol C csonkoló leképezés az n+1 bites argumentuma n bitjét veszi rögzített n pozíción (azaz 1 bitet elhagyunk). Igazoljuk, hogy G'(s) is PRG! (i ) [Teljes indukcióval. Tegyük fel, hogy G (U n ) álvéletlen eloszlású, ami i=1 esetén teljesül Ekkor G (i +1) ( s ) = G (C (G ( i ) ( s ))) is álvéletlen eloszlású, ellenkező esetben G (C (.)) leképezés (i ) megkülönböztető lenne, azaz megkülönböztetné az G (U n ) és az U n +1 eloszlást.] F7. Igazoljuk, hogy az álvéletlenség implikálja a predikálhatatlanságot. [Ha Z algoritmus egy sikeres prediktor lenne, akkor konstruáljunk Z' algoritmust, amely sikerrel megkülönbözteti az álvéletlen sorozatot a véletlentől: ha Z predikciója helyes, akkor Z'=1, egyébként a Z'=0. Továbbá használjuk fel, hogy Z 1/2 valószínűséggel képes csak helyesen predikálni véletlen sorozat esetén.]

F8*. Igazoljuk, hogy a predikálhatatlanság implikálja a álvéletlenséget. [A indirekt bizonyítás fő lépései: 1.Legyen a két extrém hibrid a véletlen illetve az álvéletlen elem. Ha megkülönböztethető, akkor - hibrid technikával igazolva - létezik két szomszédos hibrid, amelyek szintén megkülönböztethetők, olyan l(n) bites bináris v.v. pár, amelyek közül az egyiknek k bites prefixe, a másiknak k-1 bites prefixe az álvéletlen sorozat megfelelő prefixe, míg a suffixek pénzfeldobás bittel vannak feltöltve. 2. Ezen két hibridből kiindulva, igazoljuk, hogy az álvéletlen prefix k-adik bitje predikálható. A bizonyításnak ezen része használhatja az 1-1 értelmű OWF függvényre alapuló 1 bittel hossznövelő standard bizonyítás technikai lépéseit.]

F9. Legyen G egy PRG, amelyre | G ( w) |=| w |2 , ∀w ∈ {0,1}* (azaz négyzetesen hossznövelő). Használjuk ezen PRG-t kulcsfolyamgenerátorként szimmetrikus kulcsú rejtjelezésben a szokásos mod 2 összegző módon. Lehetséges-e, hogy egy támadó felmutat m0, m1 üzenetpárt, ahol az üzenetek n 2 bit hosszúak, amelyre | P[ D (G (U n ) ⊕ m0 ) = 1] − P[ D (G (U n ) ⊕ m1 ) = 1] |≥ 1 / q (n) , azaz a megfelelő rejtjeles szövegek megkülönböztethetők.

9

[Tekintsük a P[ D (U 2 n ) = 1] valószínűséget, amely a PRG definíciója alapján a fenti két valószínűség egyikétől sem lehet "távol". Alklamazzunk bebővítést és háromszög egyenlőtlenséget.]

PRF F1. Igazoljuk ellenpéldával, hogy miért nem helyes az alábbi definíció egy PRF-re: Fn egy PRF, ha létezik M Fn polinomiális idejű orákulumos gép, az alábbi átlagos pontossággal képes becsülni az Fn outputját 1 1 P ( M Fn (U n ) = Fn (U n )) < |Fn | + p ( n) 2 tetszőleges p(n) polinomra, s elegendően nagy n-re (M természetesen nem küldheti saját inputját kérésként az Fn orákulumhoz. [Legyen F'n egy PRF, amelyből ellenpélda Fn úgy képezhető kis módosítással, hogy Fn a 0n inputot konstans outputba képezze le, míg a többi inputot az F'n leképezésnek megfelelően. Fn nyilván nem PRF, de rendelkezik a fenti, átlagosan becsülhetetlen tulajdonsággal.]

F2*. Igazoljuk ellenpéldával, hogy miért nem helyes az alábbi alternatív konstrukció PRF-re: f s ( x) = Gσ n (...(Gσ 2 (Gσ 1 ( x))...)

ahol s = σ 1...σ n . Azaz x és s szerepe felcserélésre került a standard konstrukcióhoz képest. [Igazoljuk először, hogy ha létezik PRG, akkor létezik olyan is amelyre G (0 n ) = 0 2 n . Ugyanis indirekcióval könnyen látható, hogy a PRG tulajdonság nem változik akkor, ha egy PRG két inputjához tartozó outputot megcseréljük. Ha ezt már beláttuk, akkor ezen PRG esetén a feladatbeli konstrukció az s magtól függtelenül zéró inputra zéró outputot ad, azaz nem lehet PRF.]

F3. Zárakat gyártunk, amelyeken olvasható az SN azonosító szám, míg a zár C kombinációját titkosan kell kezeljük. A kombinációt egy n bites szó azonosítja. Hogyan járjunk el a C kombináció megválasztásánál, ha a feltételek a következők: 1. az SN nyilvános azonosító alapján ne legyen kitalálható, 2. ha az ügyfél a kombinációt később elfelejti, azt közölnünk kell tudnunk vele, 3. minimalizálni szeretnénk az [sorozatszám, kombináció] párokkal kapcsolatos biztonsági tárolási igényt ha a.) élhetünk az egyirányú függvények létezésének feltételezésével

10

b.) az ügyfelek hipohonderek, félnek, hogy esetleg kiderül, hogy P=NP, ezért csak feltétel nélküli biztonság garantálását fogadják el. [a.) C=Fk(SN), ahol Fk biztonságos PRF (álvéletlen függvény). A biztonsági tárigény a k kulcs mérete, azaz konstans, s nem nő az eladott zárak darabszámával. (Megj. Fk nem kell, hogy permutáció, azaz rejtjelező leképezés legyen!) b.) Ekkor R valódi véletlen függvény szükséges: C=R(SN). Más szavakkal függetlenül sorsolt 'jelszavak' adják a kombinációkat.]

PRP F1*. A csapda permutáció lényegében egy egyirányú permutáció. Mint egy nyilvános kulcsú rejtjelező modellje, a csapda permutáció tulajdonság választott nyílt szövegű támadás (nyilvános kulcs ismeretében orákulum nélkül is tudunk választott nyílt szövegű támadást indítani) elleni védettséget garantálja. Ezen feladat célja annak igazolása, hogy amennyiben létezik (G,F,I) csapda permutáció, akkor létezik erős álvéletlen permutáció is (Informálisan: ha létezik cpa-biztonságos nyilvános kulcsú rejtjelező, akkor létezik cca-biztonságos szimmetrikus kulcsú rejtjelező is.) A feladat összetett, ezért megoldási segítséget adunk hozzá: A biztonságos csapda permutáció léte implikálja az egyirányú függvény létezését. Egyirányú függvényből kiindulva, konstruálható álvéletlen permutáció, s így létezik olyan E(k,x) algoritmus, amely k véletlen választása mellett álvéletlen permutáció az x input vonatkozásában. Jelölje D(k,x) a kapcsolatos inverzet. Ezen (E,D) álvéletlen permutáció és a (G,F,I) csapda permutációt kaszkádba kötésével generáljuk a kívánt (G',F',I') permutációt: legyen F ' ((k,k'),x)=E(k,F(k',x)) ( k ' , sk ' ← G publikus, titkos kulcspár mellett F(k',x) a kódoló és I(sk',y) a dekódoló transzformáció.) Továbbá - értelemszerűen - legyen I'((k,sk'),z)=I(sk',D(k,z)), azaz F': x → F(k',.) → E(k,.) → z I': z → D(k,.) → I(sk',.) → x G' generálja k,k',sk' kulcshármast: a k',sk' párt G felhasználásával, míg k kulcsot véletlenszerűen választva.

Igazoljuk, hogy a fenti módon generált (G',F',I') álvéletlen permutáció és csapda permutáció is egyben, ahol a publikus kulcs (k,k') a titkos (csapda) kulcs sk'.)

[ (G',F',I') csapda permutáció: (indirekt): ha Z algoritmus (k,k') ismeretében z=F'((k,k'),x) inputból ki tudná számítani x ősképest, akkor tudnánk Z' algoritmust konstruálni, amely invertálni képes F(k',.) leképezést is: egy y=F(k',x) input esetén Z' véletlenszerűen választ egy k kulcsot, majd F'((k,k'),x) (=E(k,y)) inputtal meghívja a Z algoritmust, amely kiszámítja y ősképét az sk' titkos csapda kulcs nélkül, s ez ellentmondana annak, hogy F csapda permutáció. (G',F',I') álvéletlen permutáció: (indirekt): ha Z algoritmus meg tudná F' permutációt különböztetni véletlen permutációtól, akkor tudnánk olyan Z' algoritmust konstruálni, amely képes megkülönböztetni E permutációt a véletlen permutációtól:

11

Z' hozzáfér az O, O-1 orákulumokhoz (amely vagy az E, D vagy pedig a véletlen permutáció és inverze, π , π −1 pár). Z' szimulálja Z környezetét, az F' és I' orákulumokat. Z' meghívja G publikusan elérhető kulcsgenerátor, s generál k ' , sk ' ← G véletlen kulcspárt. O kérés: amikor Z egy x kérésre F'((k,k'),x) választ vár, Z' x inputtal előbb kiszámítja v=F(k',x) értéket, majd ezt mint kérést elküldi O orákulumnak, s annak O(v) válaszát küldi Z' végülis el Z kérésére válaszként. O-1 kérés: amikor Z egy z kérésre I'(sk',z) választ vár, Z' z inputtal előbb kiszámítja kiszámítja w=I(sk',z) értéket, majd ezt mint kérést elküldi O-1 orákulumnak, s annak O-1 (w)) válaszát küldi Z' végülis Z kérésére válaszként. Amikor (O, O-1)=(E,D) akkor Z az F',I' leképezésnek megfelelő válaszokat kapja, míg amikor (O, O-1)=( π , π −1 ) akkor Z - könnyen láthatóan - az véletlen permutációnak és inverzének megfelelő válaszokat kapja (ti. F egy permutáció és π D F , π −1 D I = π ' , π ' −1 ).]

Eloszlások megkülönböztetése

F1. Valószínűségi változók két sorozata, X = { X n }n∈N és Y = {Yn }n∈N polinomiális időben megkülönböztethetetlen, ha tetszőleges Z∈BPP algoritmus, tetszőleges p(.) polinom és elegendően nagy n esetén | P( Z ( X n ) = 1) − P( Z (Yn ) = 1) |<

1 p ( n)

Mutassuk meg, hogy ha X ' = { A( X n )}n∈N és Y ' = { A(Yn )}n∈N v.v. sorozatok is polinomiális időben megkülönböztethetetlen, ha tetszőleges A∈BPP algoritmus esetén. [Indirekt bizonyítás. Ha az állítás nem lenne igaz, akkor létezne Z'∈BPP megkülönböztető algoritmus X', Y' párra, de akkor Z=Z'°A megkülönbözteti X,Y párt, ami ellentmondás.]

F2. Valószínűségi változók két sorozata, X = { X n }n∈N és Y = {Yn }n∈N legyen variációs távolságban közeli, s legyen f : {0,1}* → {0,1}* tetszőleges függvény. Mutassuk meg, hogy X ' = { f ( X n )}n∈N és Y ' = { f (Yn )}n∈N v.v. sorozatok is közeliek variációs távolságban. [Ha két eloszlás atomjai azonos részhalmazát öszevonjuk a variációs távolság nem változik. Tetszőleges függvény hatása egymás utáni ilyen összevonási műveletekkel képezhető, végiglépve a függvény értékkészletének elemein.]

F3. Mutassuk meg, hogy a variációs távolság egy ekvivalens definíciója az alábbi: X = { X n }n∈ N és Y = {Yn }n∈ N variációs távolságban közeli, a.cs.a., ha tetszőleges S ⊆ {0,1}* esetén Δ S (n) =| P( X n ∈ S ) − P (Yn ∈ S ) | elhanyagolhatóan kicsi n-ben.

12

[→ S * = {x : PD ( x) > PD ' ( x)} jelöléssel ∑ PD ( x) −PD ' ( x) = V ( D, D' ) . x∈S *

← S = S1 ∪ S 2 , S1 ⊆ S *, S 2 ⊆ S * ,

| PD ( S ) − PD ' ( S ) |=| PD ( S 1 ) − PD ' ( S 1 ) + PD ( S 2 ) − PD ' ( S 2 ) | ≤| PD ( S 1 ) − PD ' ( S 1 ) | + | PD ( S 2 ) − PD ' ( S 2 ) | ≤| PD ( S * ) − PD ' ( S * ) | + | PD ( S * ) − PD ' ( S * ) |= 2 ⋅ V ( D, D' ) ]

F4. Igazoljuk, hogy ha két vv. sorozat statisztikailag közel van, akkor algoritmikus megkülönböztethetőség szempontjából is közel van. (megj. az állítás megfordítása nem igaz) [lásd a jegyzetben]

13

Rejtjelezés Szimmetrikus kulcsú rejtjelezés Bal-vagy-jobb biztonság: LOR

F1. Bizonyitsuk be, hogy ha egy Ek szimmetrikus kulcsú rejtjelező lor-cpa biztonságú, akkor biztonságos kulcsvisszafejtő támadással szemben is. [Indirekt. Tegyük fel, hogy Z támadó vissza képes fejteni Ek kulcsát. Z alapján egy Z'O LOR-CPA támadó konstruálható, ahol O a bal-jobb orákulum: 1. Z(O(m,m)) → k' 2. If Dk'(O(m1,m2)) = m1, akkor Z' outputja 1, egyébként 0. Legyen B={k' helyes}:

| P( Z 'balO = 1) − P ( Z ' jobbO = 1) | =| [ P( Z 'balO = 1 | B) − P( Z ' jobbO = 1 | B)] ⋅ P( B) + [ P( Z 'balO = 1 | B) − P( Z ' jobbO = 1 | B)] ⋅ P( B) |

=| [1 − 0] ⋅ P( B) + [2 − n − 2 − n ] ⋅ P( B) |= P( B) = ΔkfE ( Z ) , azaz Ek nem lenne LOR-CPA, ami ellentmond a feltételünknek.]

F2. Bizonyitsuk be, hogy ha egy Ek szimmetrikus kulcsú rejtjelező (t,q,μ,ε) lor-cpa biztonságú, akkor egyúttal (t,q,μ,ε) pr-cpa biztonságú is. [Indirekt. Tegyük fel, hogy létezik Z támadó, amely > ε hatékonysággal fejti a rejtett szöveget. Z alapján egy Z'O > ε hatékonyságú lor-cpa támadó konstruálható: Z'=1, ha Z (O(m1, m2)) = m1 , egyébként Z'=0, s ahol O a bal-jobb orákulum.]

F3*. Igazolja vagy cáfolja a következő állítást: Ha létezik ind-cpa biztonságú (E,D,G) publikus kulcsú rejtjelező, akkor létezik lor-cpa biztonságú szimmetrikus kulcsú rejtjelező is. (Segítség: Az állítás igaz. A bizonyítás lényege: ha létezik IND-CPA biztonságú publikus kulcsú rejtjelező, akkor létezik biztonságos egyirányú függvény (OWF). Ha létezik biztonságos egyirányú függvény, akkor OWF→PRG→PRF→PRP implikáció láncolat alapján igaz az állítás. A kérdéses OWF a következőképp állítható elő: a kulcspár-generáló algoritmus r véletlen elem felhasználásával előállítja (pk,sk) kulcspárt. Az egyirányú függvény F(r)=pk, azaz a r inputból a pk publikus kulcsot előállító leképezésről belátható, hogy egyirányú (lényegében: a publikus kulcs alapján a titkos kulcs nem állítható elő, ti. r alapján generálható lenne). Legyen az (E,D,G) publikus kulcsú rejtjelező (t,ε)-IND-CPA-biztonságú. Ha tD illetve tG a D illetve G algoritmusok futási ideje, akkor beláthatjuk, hogy F egy (t',ε/2)-biztonságú OWF, ahol t'=t-tD-tG-O(1). )

14

[A bizonyítás indirekt. Tegyük fel, hogy létezik olyan Z algoritmus, amelyre

P[ F ( Z ( F (r )) = F (r )] = r

[ F ( A( pk )) = pk ] > ε

P

( pk , sk ) ← G

Z alapján egy Z' IND-CPA megkülönböztető támadás hajtható végre (E,D,G) publikus kulcsú rejtjelező ellen >ε sikervalószínűséggel, azaz |

P

( pk , sk )←G

[ Z ' ( E ( pk , m0 ), pk ) = 1] −

P

( pk , sk )←G

[ Z ' ( E ( pk , m1 ), pk ) = 1] |> ε

A Z' algoritmus a következő: legyen m1 ≠ m2 egy tetszőleges, rögzített üzenetpár. Z'(c,pk): 1. (pk',sk')=G(Z(pk)) 2. Ha pk=pk' ha Dsk ' (c) = m0 , akkor Z'(c,pk)=1, egyébként Z'(c,pk)=0. 3. Ha pk≠pk', akkor Z' outputja b véletlen bit. P

( pk , sk )←G

+

=

=

[G ( Z ( pk )) ≠ ( pk , sk ' ) ∩ b = 1]

P

[G ( Z ( pk )) = ( pk , sk ' ) ] +

P

[ F ( Z ( pk )) = pk ' ) ] +

( pk ,sk )←G

( pk ,sk )←G

[G ( Z ( pk )) = ( pk , sk ' ) ∩ Dsk ' ( E pk (m0 )) = m0 ]

1 ⋅ [G ( Z ( pk )) ≠ ( pk , sk ' ) ] P 2 ( pk ,sk )←G

1 ⋅ [G ( Z ( pk )) ≠ ( pk , sk ' ) ] P 2 ( pk ,sk )←G

1 ⋅ [G ( Z ( pk )) ≠ ( pk , sk ' ) ] P 2 ( pk ,sk )←G

P

( pk , sk )←G

P

[ Z ' ( E ( pk , m1 ), pk ) = 1] =

( pk , sk )←G

=0+

P

( pk , sk )←G

P

( pk , sk )←G

>ε +

+

[ Z ' ( E ( pk , m0 ), pk ) = 1] =

P

( pk , sk )←G

[G ( Z ( pk )) = ( pk , sk ' ) ∩ Dsk ' ( E pk (m1 )) = m0 ]

[G ( Z ( pk )) ≠ ( pk , sk ' ) ∩ b = 1]

1 ⋅ [G ( Z ( pk )) ≠ ( pk , sk ' ) ] P 2 ( pk ,sk )←G

Blokk kódolási módok biztonsága

F4. Igazolja, hogy az ECB mód nem LOR-CPA biztonságos! [Tekintse az m1, m2 üzenetpárt , ahol m1=[u,u], m2=[u,v], u és v különböző üzenetblokkok.]

15

FF. Igazolja, hogy a CBC mód nem LOR-CPA biztonságos! [Két kéréssel fordulunk a LOR-CPA orákulumhoz: az [R1=(r1,r2), m1=(u,u)] üzenetpárral és az [R2=(r3,r4), m1=(u,v)] üzenetpárral, ahol ri , u,v üzenetblokkok méretűek, ri blokkok véletlenek. A Z megkülönböztető algoritmus rejtett szövegek első blokkjának azonosságát vizsgálja a két kérés alapján.]

Aszimmetrikus kulcsú rejtjelezés Biztonság fogalmak Szemantikai biztonság: SS

F1*. Tekintsük egy (G,D,E) publikus kulcsú rejtjelezőt. A szemantikai biztonság ((t,ε)ss) fogalmának tekintsük, az Z' szimulátor tS(n) futási ideje (ereje) szempontjából tekintett két változatát, ahol Z' futási ideje v1.) tS(n) nem korlátozott (tetszőlegesen nagy lehet) v2.) tS(n)≤ tZ(n)+p(n), ahol a Z támadó tZ(n) futási idejére tZ(n) ≤ t(n), továbbá ahol p(n), t(n) polinomok. a.) Igazoljuk, hogy v2-(t,ε)-ss ⇒ v1-(t,ε)-ss ! b.) Igazoljuk, hogy v1-(t,ε)-ss ⇒ v2-(t',2ε)-ss (ahol t'=t-O(n)) ! [a.) állítás igazolása triviális az erőforrásviszonyok kapcsán. b.) állítás igazolását két lépésben végezzük: v1-(t,ε)-ss ⇒ (t,ε)-ind-cpa, majd (t,ε)-ind-cpa⇒ v2(t',2ε)-ss igazolásával. Az első lépésben vegyük észre, hogy mivel Z' nem kap információt az üzenettel kapcsolatban ezért véletlen sejtésnél jobban nem tud eljárni, következésképp Z' futási idő lehetőségei nem játszanak szerepet. Az ss biztonság definíciójában X={m0,m1}, P(m =mi)=1/2, i=1,2, g(mi)=i helyettesítéseket alkalmazva az ind-cpa biztonság definíciójára jutunk. A második lépésben indirekt módon bizonyítsunk: igazoljuk, hogy ha van egy Z támadó, amely v2-(t',2ε)-ss -törő, akkor a rejtjelező nem lehet (t,ε)-ind-cpa biztonságú, azaz tudunk mutatni egy (t,ε)-ind-cpa, üzenet-megkülönböztető támadót. Tegyük fel tehát indirekt módon, hogy létezik olyan Z támadó (≤t' futási idővel), hogy tetszőleges X üzeneteloszlás, g függvény és tetszőleges Z' szimulátor mellett

P

m∈X ( pk , sk )←G

[ Z ( E ( pk , m), pk ) = g (m)] >

P

[ Z ' ( pk ) = g (m)] + 2ε

m∈X ( pk , sk )←G

Definiáljuk az Z' szimulátort a következőképp: G kulcsgeneráló algoritmustól kapott véletlen (pk,sk) kulcspár felhasználásával Z' előállítja a zérus üzenet E(pk,0) kódolását, majd futtatja Z algoritmust [E(pk,0),pk] inputtal, s Z outputja, Z(E(pk,0),pk) legyen Z' outputja is. Így

16

[ Z ( E ( pk , m), pk ) = g ( m)] −

P m∈X ( pk ,sk )←G

[ Z ( E ( pk ,0), pk ) = g ( m)] > 2ε

P m∈X ( pk ,sk )←G

amelynek alapján léteznie kell olyan m=m' üzenetnek amelyre,

[ Z ( E ( pk , m' ), pk ) = g ( m' )] − [ Z ( E ( pk ,0), pk ) = g ( m' )] > 2ε P P ( pk ,sk )←G ( pk ,sk )←G Vezessük be az m0=0, m1=m' , u=g(m') jelöléseket. Definiáljuk egy Z* ind-cpa támadót a következőképp: ha Z outputja u, akkor Z* outputja 1, egyébként Z*outputja 0. Ezzel

P

( pk , sk ) ←G i∈{0 ,1}

1/ 2

[ Z * ( E ( pk , mi ), pk ) = i ] =

P

( pk , sk )←G

[ Z ( E ( pk , m1 ), pk ) = u ] + 1 / 2{1 −

P

( pk , sk ) ←G

[ Z ( E ( pk , m0 ), pk ) = u )]} > 1 / 2 + ε

]

Üzenet megkülönböztetés biztonság: IND

F1. Tekintsük egy (G,D,E) publikus kulcsú rejtjelezőt, amely IND-CPA biztonságú. Definiáljuk (G',D',E') publikus kulcsú rejtjelezőt a következőképp: E ' ( x) = (b || E ( x)) , ahol b egy véletlen bit, továbbá D' (b || y ) = D( y ) . Igazoljuk, hogy (G',D',E') is IND-CPA biztonságú! [Indirekt bizonyítás. Alkalmazza a redukció technikáját!]

F2. Tekintsük egy (G,D,E) publikus kulcsú rejtjelezőt. Tekintsük az IND-CCA2 biztonság következő gyengébb IND-CCA0 változatát: a Z támadó a Dsk dekódoló orákulum helyett egy olyan O orákulumhoz fér hozzá, amely egy (y,x) kérdés esetén "igaz" választ adja, ha Dsk(y)=x, egyébként a válasza "hamis". Z az inputját (megoldandó feladatát) nem küldheti kérésként az orákulumhoz. Az IND-CCA0 biztonság erősségében nyilván IND-CPA és IND-CCA2 közötti. Szeparáljuk az IND-CCA0 és IND-CPA biztonságot: Igazoljuk, hogy amennyiben létezik IND-CPA biztonságú (G,D,E) publikus kulcsú rejtjelező, akkor létezik (G',D',E') publikus kulcsú rejtjelező is, amely IND-CPA, de nem IND-CCA0 biztonságú! [Tekintsük az F1.feladat konstrukcióját. Ahhoz, hogy egy rejtjelező ne legyen IND-x biztonságos, léteznie kell egy olyan Z megkülönböztető algoritmusnak és hozzá egy m0 , m1 , m0 ≠ m1 üzenetpárnak, amit meg tud különböztetni a rejtjelezettjeik alapján. A (G',D',E') nem IND-CCA0 biztonságú, mivel létezik olyan ZO algoritmus, amely tetszőleges ilyen üzenetpárt tökéletesen megkülönböztet: legyen Z inputja y'=b||E(m0) rejtjeles szöveg. Z képezi az ettől különböző, de

17

azonos üzenetre dekódolódó y''=b⊕1||E(m0) rejtjeles szöveget, majd az alábbi két kérést küldi az O orákulumnak: (y'', m0) és (y'', m1). Adott esetben O válasza az első kérésre "igaz" a másodikra "hamis" lesz, amelyre az első esetben Z outputja 1 a második esetben 0. Innen már könnyen látható, hogy Z megkülönböztető képessége tökéletes, a megkülönböztetés valószínűsége 1 |

P

( pk , sk )←G

[ Z O ( E ' ( pk , m1 ), pk ) = 1] −

P

( pk , sk )←G

[ Z O ( E ' ( pk , m0 ), pk ) = 1] | = 1

]

F3.A rejtjelezett hálózati üzeneteket kriptográfiai ellenőrzőösszeggel is védjük. Rejtjelzésre Goldwasser-Micali-RSA (GM-RSA) algoritmust használunk. Rejtjelezés előtt ideális lenyomatot illesztünk a szöveghez. A kapcsolatos hash függvény egy véletlen orákulum, egy publikusan elérhető G véletlen szűkítő leképezés. A G orákulumhoz a támadó is hozzáfér. Hasonlóan a támadó hozzáfér egy O orákulumhoz, amelyet kérdezhetünk egy y rejtett szöveggel: az O az "igaz" választ ad, ha y ellenőrzőösszege helyes, egyébként O a "hamis" választ adja. Jelölje ezt a támadási környezetet CC00. IND-CC00 biztonságos-e a rendszer? (Megjegyzés: egy protokoll biztonsági hibája lehet az, hogy ACK visszajelzést csak akkor küld, ha helyes az ellenőrzőösszeg. Az ACK léte vagy nem léte a publikus csatorna lehallgatásával megállapítható. Azaz a fenti támadási környezet reális is lehet.) [Nem biztonságos. A GM-RSA rejtjelezés bitenként történik, ezért y=E(m||G(m))= E(m)E(G(m)). A ZG,O támadó képezi y alapján E(m)E(G(m0)) és E(m)E(G(m1)) változatot, amelyet kérésként elküld O orákulumnak (küldheti, mivel különböznek y-tól). Az O válasza alapján egyértelműen el tudja dönteni, hogy m=m0 vagy m=m1, azaz Z megkülönböztető képessége tökéletes.]

F4*. Legyen (G,F,I) biztonságos csapda permutáció és b() a keménybitje. Ismeretes tétel, hogy E(pk,m)=(F(pk,r),b(r)⊕m) az m egy 1 bites üzenet IND-CPA biztonságú rejtjelezése, ahol r rejtjelezésenként sorsolt véletlen elem. IND-CCA2 biztonságú-e ez a rejtjelezés? [Igen. Indirekt bizonyításul tegyük fel, hogy létezik Z támadó, amelyre

P

[ Z O ( pk , ( F ( pk , r ), b(r ) ⊕ m)) = m] > 1 / 2 + ε ,

( pk , sk ) ←G r, m

ahol a O a CCA2 szerinti dekódoló orákulum. A trükk a következő: c=b(r)⊕m jelöléssel

P

[c ⊕ Z O ( pk , ( F ( pk , r ), c)) = b(r )] > 1 / 2 + ε

( pk , sk ) ←G r, c

Ennek alapján Z felhasználásával egy olyan Z' támadó konstruálható, amely töri a csapda permutációt. A csapda permutáció törés (keménybit-kiszámítás) feladatot redukáljuk az E rejtjelező törés feladatra a következőképp: Z' inputja [F(pk,r),pk], outputja z=c⊕ZO(pk,( F(pk,r),c)), ahol c véletlen bit, amit Z' sorsol. A fenti egyenlőtlenség alapján z legalább 1/2+ε valószínűséggel a keménybitettel azonos.

18

Egy pontot még tisztázni kell. Z' permutáció-törő csak az I orákulumhoz fér, ugyanakkor neki a Z rejtjelező-törő számára annak környezetét, így az O dekódoló orákulumot is szimulálni kell tudnia. Ezt az I felhasználásával teszi az alábbi módon: O(y||m)=b(I(y)) ⊕m (b(.) publikus). ]

F5. Legyenek (G,D,E) és (G',D',E') publikus kulcsú rejtjelezők IND-CPA biztonságúak. Igazoljuk hogy a (G*,D*,E*) kétszeres rejtjelezés: y=E'(E(x)), x=D(D'(x)) is IND-CPA biztonságú. [Indirekt. Tegyük fel, hogy Z IND-CPA töri (G*,D*,E*) rejtjelezőt. Z felhasználásával egy olyan Z' támadó konstruálható, amely IND-CPA töri (G,D,E) rejtjelezőt. Z' inputja E(pk,mi). Z' a G' felhasználásával generál (pk',sk') kulcspárt (megj: a kulcspár-generátor és a rejtjelező publikusak, azaz ahhoz mindig hozzáférhet). Ennek felhasználásával előállítja az E'(pk',(E(pk,mi)) kétszeresen rejtjelezett szöveget, amely Z inputjául szolgál. Mivel Z IND-CPA törő, Z outputja (0/1) lesz Z' outputja is egyben, és Z' ereje Z megkülönböztető erejével azonos lesz.]

F6. Igazolja, hogy IND-CPA biztonság implikálja az alábbi állításokat: a.) pk ismeretében nehéz feladat sk kiszámítása, b.) rejtett szöveg ismeretében nehéz feladat a nyílt szöveg első bitjének kiszámítása. [Indirekt. Tegye fel, hogy a feltételezett következmény nem igaz, s mutassa meg, hogy ezesetben a rejtjelező sem lehet IND-CPA.]

F7. Mutassuk meg, hogy az El-Gamal nyilvános kulcsú rejtjelezés Zp csoportban (mod p szorzócsoportban, ahol p prim) nem IND-CPA biztonságú. Megj: Az El-Gamal rejtjelező egy q méretű G= csoportban a következő: titkos kulcs: x, ahol x a G egy véletlenül választott eleme nyilvános kulcs: X=gx kódolás EX(M): c=(Y,KM), ahol K=Xy=gxy , Y=gy, y a G egy véletlenül választott eleme dekódolás Dx(c): K=Yx, M=(KM)K-1 [Segítség: A következő számelméleti ismereteket használhatjuk fel. Zp csoportban két elem szorzata csak akkor kvadratikus maradék (qr), ha mindkét szorzandó qr. Továbbá könnyű számítás annak eldöntése, hogy egy elem kvadratikus maradék-e, ui. d ( p −1) / 2 =+1, ha d kvadratikus maradék, illetve -1 ellenkező esetben.] [Legyen m0 qr, m1 nem qr. Ha K qr, akkor, ha KM qr, akkor M=m0, míg, ha KM nqr, akkor M=m0. Ha K nqr, akkor, ha KM qr, akkor M=m1, míg, ha KM nqr, akkor M=m1. ]

19

F8. Mutassuk meg, ha a DDH probléma nehéz egy G csoportra, akkor a G csoportot használó El-Gamal rejtjelező IND-CPA. (Megj: CDH (Computational Diffie-Helmann) probléma: adott (gx,gy), kiszámítandó: gxy DDH (Decisional Diffie-Helmann) probléma: adott (gx,gy,gz), eldöntendő, hogy z=xy teljesül-e.) [a.) indirekt: Z IND-CPA támadó pénzfeldobás valószínűséggel sikeres csak, ha z véletlen, ennél sikeresebb, ha z nem véletlen. Következésképp, Z' futtatja Z-t: Z' által szimulált kódoló orákulum az M kérésre a c=(Y,KM) rejtett szöveggel válaszol, ahol K=gz , Y=gy. Z' úgy dönt, hogy (gx,gy,gz) DH-hármas, ha Z sikeres. P(Z'=1|DH-hármas)- P(Z'=1|nem DH-hármas)=(1/2+ε)-1/2=ε ahol ε nem elhanyagolható, ami ellentmond DDH probléma sejtett nehézségének. b.) direkt: ha Z DDH-törő, akkor Z' fel tudja használni arra, hogy megkülönböztesse, hogy ( X=gx, Y=gy, (gxymb)/m0)) vagy ( X=gx, Y=gy, (gxymb)/m1)) hármasok melyike DH-hármas, s ennek alapján dönt b értékére.]

F9. Mutassuk meg, hogy az El-Gamal rejtjelezés (def. F7.-ben) nem IND-CCA2, azaz adaptív választott szövegű támadás ellen védtelen. (Megj: IND-CCA2 biztonság: A támadó m0, m1 párt küld a "kódoló orákulum"-nak, amely egy - a támadó által nem látott - véletlen b bit alapján mb üzenetet rejtjelezi, s a rejtjelezett c blokkot adja vissza a támadónak. A támadó ezután a dekódoló orákulumnak küldhet kéréseket, kivéve a c blokkot. Végül egy b' bináris döntést hoz, s ha b=b', akkor sikeres a megkülönböztető támadás.) [Legyen c=(Y,Kmb). A támadó tetszőlegesen választ g≠1 csoportelemet, s a dekódolónak elküldi a c'=(Y,Kgmb) rejtjelezettet (nyilván c'≠c), amelyre a m'=g⋅mb dekódolt üzenet kapja, ahonnan m'/g osztással dekódolja mb üzenetet, s ezáltal 1 valószínűséggel sikeres.]

F10. folytatás (IND-CCA2 biztonságú rejtelező): Az El-Gamal rejtjelezés nem INDCCA2, mivel sikeresen manipulálható a rejtett szöveg (lásd F9.feladat). Cramer-Shoup kódolás az El-Gamal kódolás egy ebből a szempontból tökéletesített változata, s ezzel egyúttal a ma ismert legkisebb számításigényű bizonyítottan INDCCA2 biztonságú rejtelező, amely a DDH probléma - sejtett - nehézségét feltételezi. Az alábbiakban kisebb részfeladatokra tördeljük a Cramer-Shoup bizonyítás gondolatmenetét. Az alapvető gondolat az, hogy akadályozzuk meg a rejtjeles szöveg észrevétlen manipulálhatóságát, amelyhez v hitelesítő elem alkalmazunk. A dekódoló először ellenőrzi ezen v hitelesítő elem helyességét, s csak siker esetén dekódolja az üzenetet. Ezzel kizárja, hogy a támadó nem a kódoló orákulum kimenetéről érkező (azaz érvényes kódolt szöveget küldhessen a dekódolónak). (A hitelesítő elem generálásához, s a rejtjeles szöveg előállításához különböző kulcselemeket használunk. )

20

Ha a támadó nem kaphat érvényes kódolt szövegre outputot a dekódolótól, akkor csak a nyilvános kulcs ismeretében általa is generálható érvényes rejtjeles szövegekre támaszkodhat a támadása során (azaz lényegében visszaszorítjuk az IND-CPA körülmények közé a lehetőségeit illetően, ahol one time pad fejtés nehézség elé állítjuk). Először megadjuk a kód definícióját: kulcs generálás: Legyenek g1 , g 2 ∈ G, x1 , x2 , y1 , y2 , z ∈ Z q véletlen elemek. A x

x

y

y

nyilvános kulcs: ( g1 , g 2 , c = g1 1 g 2 2 , d = g1 1 g 2 2 , d = g1z , H ) , ahol H UOWHF titkos kulcs: ( x1 , x2 , y1 , y2 , z ) . kódolás: Legyen m ∈ G az üzenet, s válasszunk r ∈ Z q véletlen elemet. A rejtett szöveg (u1 , u 2 , e, v ) , ahol

u1 = g1r , u 2 = g 2r , e = h r m , α = H (u1 , u 2 , e) , v = c r d rα dekódolás: Adott egy (u1 , u 2 , e, v ) rejtett szöveg (input), a dekódoló először ellenőrzi a v hitelesítő elem helyességét az ( x1 , x2 , y1 , y 2 ) titkos kulcselemek és a publikus H hash transzformáció felhasználásával: képezi α = H (u1 , u 2 , e) lenyomatot, majd ellenőrzi az alábbi egyenlőség fennállását: x +y α x +y α

u1 1 1 u 2 2 2 = v Ha nem áll fenn az egyenlőség, akkor outputja "visszutasítva", ellenkező esetben elvégzi az alábbi műveletet, amivel dekódolja az üzenetet: m = e / u1z A bizonyítás az szokásos indirekt gondolatmenet: tegyük fel, hogy Z támadó sikeres IND-CCA2 támadó, akkor felépíthető egy Z' támadó, amely nem elhanyagolható sikerrel oldja a DDH problémát, s ezzel ellentmondásra jutunk. A Z' támadó Z számára szimulálja a kódolót és a dekódolót, amelyeket Z orákulumként használhat azon megszorítással, hogy a törésre kapott (rejtett szöveg) inputját nem küldheti kérésként a dekódoló orákulumnak. Z' inputja ( g1 , g 2 , u1 , u 2 ) ∈ Z q , s azt kell megállapítania, hogy ez a négyes véletlen választás (R világ), vagy u1 = g1r , u 2 = g 2r (D világ). Ezen inputra építve rejtett szöveget generál Z IND-CCA2 kódtörő számára, úgy hogy frissen generálja kulcsparamétereket lefuttatva a kulcsgenerátort. Vizsgáljuk meg azt, egy támadó csak elhanyagolható sikerrel képes csaló (u1' , u 2' , e' , v' ) rejtett szöveget generálni, azaz amely nem érvényes kódolt szöveg a fenti kódolás szabályai szerint, de a dekódolóbeli ellenőrzésen mégis sikerrel átjut. [

21

Tegyük fel először, hogy a D világban vagyunk. A támadó nem ismeri az ( x1 , x2 , y1 , y 2 ) titkos kulcselemeket, de azt tudja, hogy a következő 3 egyenletből álló rendszert elégítik ki (illetve a harmadikat ki kellene elégíteni, ahhoz hogy a dekódoló hiteles elem ellenőrzőjét becsapja): 1. log g c = x1 + wx 2 1

(nyilvános kulcs alapján)

2. log g d = y1 + wy 2 1

(nyilvános kulcs alapján)

' ' ' ' 3. log g v' = r1 x1 + wr2 x2 + αr1 y1 + αr2 wy 2 (csaló dekódoló input alapján) 1 ' ' ' ' ahol log g g 2 = w , log g u1 = r1 , log g u 2 = wr2 , r1 ≠ r2 . Ha a kódolót használja a támadó, 1 1 1 akkor egy

log g1 v = rx1 + wrx2 + αry1 + αrwy 2 (kódoló output alapján) alakú egyenletre jut, ami az első két egyenlettel lineársian függő, így a kódoló kérdezése nem juttatja a titkos kulcslemekkel kapcsolatban a támadót. Természetesen ezen lineáris alakban nem áll rendelkezésére, mivel a diszkrét logaritmusképzés nehéz feladat, de ezen rendszer konkrét megoldása nem is szükséges a bizonyításhoz. Ez három egyenlet négy ismeretlennel. Gondolatban átrendezve, elimináljuk a harmadik egyenletből például az x2, y2 ismeretleneket az első két egyenlet felhasználásával, s eredményül log g v ' = ax1 + by1 alakú egyenletre jutunk. A 1

támadó nem ismeri a titkos kulcselemeket, ezért annak valószínűsége, hogy ezen utóbbi egyenlőség fennáll 2 (s v' elfogadásra kerül, mint "helyes" hitelesítő elem), q / q = 1 / q , ami elhanyagolhatóan kicsi. Tegyük fel először, hogy az R világban vagyunk. Ekkor az 1. log g c = x1 + wx 2 (nyilvános kulcs alapján) 1 2. log g d = y1 + wy 2 (nyilvános kulcs alapján) 1 3. log g v = r1 x1 + wr2 x2 + αr1 y1 + αr2 wy 2 (kódoló output alapján) 1 ' ' ' ' 4. log g v' = r1 x1 + wr2 x2 + αr1 y1 + αr2 wy 2 (csaló dekódoló input alapján) 1 Három esetet különböztetünk meg. ' ' ' a.) (u1 , u 2 , e ) = (u1 , u 2 , e), v ≠ v' Ez nem lehetséges, mivel a hitelesítő leképezés függvény. ' ' ' a.) (u1 , u 2 , e ) ≠ (u1 , u 2 , e), α ≠ α ' Ez esetben a fenti egyenletrendszer együtthatómátrixa determinánsa nemzérus (ellenőrizzük!), ezért csak egyetlen ( x1 , x2 , y1 , y 2 ) kulcselem négyes mellett van megoldása. Mivel a kulcslemek véletlenek a támadó számára, így a siker valószínűsége - a fenti egyenletreszer kielégülése - elhanyagolható valószínűségű. ' ' ' a.) (u1 , u 2 , e ) ≠ (u1 , u 2 , e), α = α ' Ez nem lehetséges nem elhanyagolható gyakorisággal, mivel ez ütközés előállítását jelentené, s ellentmondana annak, hogy H hash függvényt UOWHF családból választottuk. ]

22

Bizonyítás véletlen orákulum modellben F1. Legyen R : {0,1}n → {0,1}3n véletlen függvény egy publikus véletlen orákulum: az orákulum mindenki által - így a támadó által is - hozzáférhető, ugyanazon inputra ugyanazon outputot adja (függvény), különböző inputokra független, az output térben egyenletesen választott outputot ad. Mutassuk meg, hogy ebben a modellben létezik (t , t / 2 n ) biztonságú álvéletlen generátor! (Emlékezetőül: G R : X → Y egy (t , ε ) -biztonságú PRG, ha | P[ Z R (G R ( x)) = 1] − P[ Z R ( y ) = 1] |≤ ε

tetszőleges legfeljebb t erőforrás-igényű ZR megkülönböztető algoritmus esetén, ahol x ← r X és y ← r Y , ahol v ← r V azt jelöli, hogy v a V halmaz egy véletlen eleme. A valószínűséget x,y,R véletlen választása, s Z esetleges véletlen elemei felett számoljuk.) [A GR generátorként közvetlenül az R orákulumot használjuk: x ← r {0,1}n mag esetén a generátor outputja legyen R(x). A Z támadó feladata, hogy erőforráskorlátja mellett minél jobban megkülönböztesse R(x) valószínűségi változó eloszlását az y ← r {0,1}3n valószínűségi változó eloszlásától. Ha Z t darab kérést, x1 , x2 ,..., xt kéréseket küldi az R orákulumnak, amelyre az R( x1 ), R ( x2 ),..., R( xt ) választ kapja, a következő két vektor valószínűségi változó kell megkülönböztetnie: U = [ R( x), R( x1 ), R( x2 ),..., R( xt )] és V = [ y, R( x1 ), R( x2 ),..., R( xt )] . U és V valószínűségi változók eloszlása csak akkor különbözik, ha ∃i , hogy xi = x , mivel R véletlen függvényként azonos inputra azonos outputot ad, különböző inputra pedig független outputot. Z kimenetén 1 jelenik, ha az input vektorában van két azonos elem. Jelölje B a ∃i, xi = x eseményt, amellyel tehát P[ Z ( R( x)) = 1 | B] = P[ Z ( y ) = 1 | B] . Továbbá annak valószínűsége, hogy a Z számára ismeretlen, és a PRG üzemeltetője által véletlen magként választott x megegyezik valamely általa választott kéréssel nyilván felülről becsülhető az unió becslési technikával P ( B ) ≤ t / 2 n módon. Innen elemi valószínűségszámítási lépésekkel:

| P[ Z R (G R ( x)) = 1] − P[ Z R ( y ) = 1] | =| P[ Z R (G R ( x)) = 1 | B] ⋅ P( B) + P[ Z R (G R ( x)) = 1 | B] ⋅ P( B) − P[ Z R ( y ) = 1 | B] ⋅ P( B) − P[ Z R ( y ) = 1 | B] ⋅ P( B) |

=| P[ Z R (G R ( x)) = 1 | B] − P[ Z R ( y )) = 1 | B] | ⋅P( B) ≤ P( B) ≤ t / 2 n .

F2. Legyen R : {0,1}n → {0,1}3n egy véletlen orákulum. Mutassuk meg, hogy ebben a modellben létezik (t ,2t / 2 n ) biztonságú egyirányú függvény! (Emlékezetőül: F R : X → Y egy (t , ε ) -biztonságú egyirányú függvény, ha P[ f R ( Z R ( f R ( x))) = f R ( x)] ≤ ε

23

tetszőleges, legfeljebb t erőforrás-igényű ZR invertáló algoritmus esetén, ahol x ← r X , ahol valószínűséget x, R véletlen választása, s Z esetleges véletlen elemei felett számoljuk.) [f egyirányú függvényként az R orákulumot használjuk. Z inputja y=f(x). Mivel f véletlenszerűen választott, ezért Z nem tehet jobbat, mint véletlenszerűen választ egy elemet az inputok teréből. A feladat annak a valószínűségnek a kiszámítása, hogy olyan x' elemet választ, amelyre f(x')=y. Ez az esemény bekövetkezik, ha A={x'=x} vagy ha B{x'≠x: f(x')=y}. Mivel P(A)=1/2n illetve P(B)=1/3n, ezért t invertálási kisérlet (orákulum kérés) esetén - unió felső becsléssel t (1 / 2 n + 1 / 3n ) < 2t / 2 n adódik az ε értékére.]

F3. Mutassuk meg, hogy az alábbi aszimmetrikus kulcsú rejtjelezés IND-CPA biztonságú véletlen orákulum modellben: E G ( x) = f (r ) || G (r ) ⊕ x ahol f csapda permutáció, r véletlen elem a permutáció input-teréből, x a nyílt szöveg (rejtjelezendő üzenet), G véletlen generátor, amelyhez outputja üzenet méretű, s amelyhez orákulum hozzáférése van a támadónak is. Ez a rejtjelezés tehát hossznövelő transzformáció. (Például f RSA leképezés, G egyirányú hash leképezésből implementált.) [Intuitiven: Akkor tudjuk csak az üzenetről dekódolni (pontosabban róla az a priori ismertnél többet megtudni), ha először r ősképet elő tudjuk állítani, mivel r ismerete nélkül, G(r) véletlen bitvektor, azaz x one time pad rejtjelezett. Formálisan:Indirekt. Tegyük fel, hogy létezik egy Z sikeres megkülönböztető támadó, s mutassuk meg, hogy ezesetben konstruálható Z' támadó, amely adott y esetén, ahol y f outputja sikerrel elő tudja állítani annak ősképét, azaz sikerrel invertálja f egyirányú csapda permutációt. Z' szimulálja Z környezetét. Z előállít egy (x1,x2) üzenetpárt, amelyre Z' egy y'=y||R "rejtjelezett" szöveget ad vissza Z számára, ahol y az invertálandó f-output, R egy véletlen elem. Z' figyeli, hogy Z milyen orákulum kérésekkel fordul G orákulumhoz. Ha ez a kérések között szerepel r, amelyre f(r)=y, akkor Z' outputja r. Legyen B ezen utóbbi esemény, azaz Z' sikerének eseménye.

1 / 2 + ε = P[ Z si ker es | B]P[ B] + P[ Z si ker es | B ]P[ B] ≤ 1 ⋅ P[ B] + P[ Z si ker es | B] ≤ P[ B] + 1 / 2 ahol Z' sikervalószínűsége - az indirekt feltételezés szerint nem elhanyagolható - ε (ha Z nem kérdez rá r inputtal G orákulumra, akkor nincs esélye G(r) kitalálására, azaz 1/2 valószínűséggel lehet csak sikeres). Következésképp P[B]≥ε, ami ellentmond f tulajdonságának.]

24

Hitelesség MAC

F1. Biztonságos-e következő MAC protokoll: ECB módon rejtjelezzük az üzenet blokkjait, s rejtjeles blokkokat adjuk össze (mod 2), amely összeg legyen a MAC? [Könnyen látható, hogy ez a hitelesítési mód tökéletesen rossz. Vegyünk egy M=[x,x] üzenetet, amely 2 blokk hosszúságú, s mindkét blokkja azonos (x). Nyilván a csupa zérus blokk lesz a MAC értéke. Következésképp, ha M még nem szerepelt üzenetként (az adott kulcs használata óta), a támadás a MAC biztonsági modellben sikeres: Δmac F (0,0, m, t ) = 1 ].

F2. Az F1.feladatbeli MAC számítást bonyolítsuk annyival, hogy az üzenet blokkjait külön-külön rejtjelezzük, és rejtjelezés előtt egy, üzeneten belüli blokk-sorszámmal látjuk el. Biztonságossá tettük-e ezáltal a protokollt? [Három MAC kérés alapján a támadó ki tud számítani egy hiteles (M,MAC) párt egy korábban nem szerepelt M üzenetre. Kérjük ugyanis a MAC-ot [x,y], [x,y'], [x',y] üzenetekre, amelyeket összeadva megkapjuk a MAC-ot [x',y'] üzenetre. Következésképp mac (3,0, m, t ) = 1 .] Adv F

25

Kriptográfiai lenyomatkészítés (hash függvény) 1. Univerzális hash függvény, univerzális egyirányú hash függvény (UOWHF)

Azt mondjuk, hogy egy h : KxX → Y egy ε 2-univerzális hash leképezés, ha páronként független az alábbi módon: | Pk ←K [hk ( x) = u, hk ( y ) = v] − 1 / | Y |2 |≤ ε tetszőleges x, y ∈ X , u , v ∈ Y , x ≠ y mellett, továbbá h(.,.) hatékonyan kiszámítható, valamint tömör leírása létezik, ami azt jelenti, hogy leírható legfeljebb poly(n⋅m) bittel, ahol |X|=n, |Y|=m. F1. a.) Mutassuk meg, hogy h A, b ( x) = Ax + b, x ∈ {0,1}n , A ∈ {0,1}n ⋅ m , b ∈ {0,1}m , ε=0 2univerzális hash leképezés, azaz 2

⎛ 1 ⎞ PA,b [hA,b ( x) = u, hA,b ( y ) = v] = ⎜ m ⎟ ⎝2 ⎠ n tetszőleges x, y ∈ {0,1} , u , v ∈ {0,1}m , x ≠ y mellett. b*.) Mutassuk meg, hogy az állítás érvényben marad akkor is, ha A mátrix véletlen Toeplitz-mátrix (Ai,j= Ai+1,j+1). [a.) Az x és y bináris vektorok egyeseinek megfelelő indexhalmaz legyen Ix és Iy. Legyen B=Ix\Iy, C=Iy\Ix, D=Ix∩Iy. Ezen halmazok elemeit tekintsük oszlopindexnek, s képezzük a nekik megfelelő oszlopok mod 2 összegeit, rendre UB, UC ,UD. Ezzel három egymástól független véletlen bináris vektorra jutunk (A b vetort a metszetbe vonjuk be.) Segédállításként lássuk be, hogy UB⊕UC és UD⊕UC független vv.v.-k. b.)... ]

F2. Mutassuk meg, hogy hα , β ( x) = a ⋅ x + b, a, b, x ∈ GF ( p), p prim , leképezés ε=0 2univerzális hash leképezés. [P1(x,u) és P2(y,v) két különböző pont egy ax+b egyenest határoz meg, azaz egy a,b együttható párt, amely pár kisorsolásának valószínűsége 1/q2. ]

F3. Mutassuk meg, hogy hk ( x) = x ⊕ k , x, k ∈ {0,1}n , leképezés ε=1/2n 2-univerzális hash leképezés. [ Pk ← K [h( x) = u , h( y ) = v] ≤ Pk ← K [h( x) = u ] = Pk ← K [k = x ⊕ u ] = 1 / 2 n felhasználásával.]

F4. Tekintsük a hk ( x) = x ⊕ k , x, k ∈ {0,1}n , leképezés ε=1/2n 2-univerzális hash leképezést (előző feladat). (t = ∞, q = 2, 100 ⋅ ε ) -biztonságú PRF-e ez a leképezés?

26

[Nem. hk (x) ugyanis q=2 darab input (x) kéréssel gyakorlatilag tökéletesen megkülönböztethető az R : {0,1}n → {0,1}n véletlen leképezéstől (k paramétert véletlenül választjuk): Legyen Z algoritmus a következő: Z=1, ha x=0 illetve x=1 inputra az O orákulum O(0) illetve O(1) választ adta, és O(0)⊕O(1)=1, ellenkező esetben Z=0. Ezzel

P( Z h = 1) − P( Z R = 1) = 1 − 1 / 2 n .]

F6*. Egy h : KxX → Y ε=0 2-univerzális hash leképezést tekintsünk. Igazoljuk a standard tétel alapján, hogy tetszőleges S ⊆ {0,1}m output részhalmazt tekintve, a hash leképezések 2 −(b − m + log 2 | S |) δ −2 töredékét kivéve teljesül az alábbi egyenletesség az output (lenyomat)

eloszlására: P( h( X n ) ∈ S ) ∈ (1 ± δ ) ⋅

|S | 2m

ahol Xn az input v.v.. [A standard bizonyítás technikáját (Csebisev egyenlőtlenség) alkalmazhatjuk kis módosítással a h( X n ) ∈ S esemény indikátorára.]

27

2. Standard hash függvények

F.1. Mutassuk meg, hogy az iterációs függvény “erejénél” nem nagyobb a hash függvény “ereje”, azaz az előbbire végrehajtható hatékony támadás kiterjeszthető a hash függvény elleni hatékony támadássá. (Ugyanakkor egy erős iterációs függvényt lehet rosszul iterálni.) Tekintsük a CRHF tulajdonságot! [F.1. Ha az iterációs függvény pl. nem CRHF tulajdonságú, s ezért elõ tudunk állítotani olyan M1 ,M1 ’ párt amelyre h(H0 , M1)= h(H0 , M1’), akkor nyilván Hash(H0 , [M1,m])= Hash(H0 , [M1’,m]) tetszõleges m üzenet esetén.]

F.2. Egy iterációs hash függvény esetén mutassuk meg, hogy m,m’, H0 H0’: Hash(H0,m)=Hash(H0’,m’) pszeudo ütközés elõállítása nem nehéz feladat. [F.2. Hash(H0,[M1M2])=h(h(H0, M1) M2)= Hash(H0’, M2), ahol H0’= h(H0, M1) (Megj.: MDmegerõsítés esetén ez a támadás nem végrehajtható).]

F.4. Tekintsünk egy ideális H hash függvényt, amely n bit méretű hash értéket ad, s tekinthetjük véletlenszerűnek a leképezést. Mutassuk meg, hogy az ütközéshez szükséges számítások várható értékére jó közelítés 2n/2. (Segítség: Tekintsen t különbözõ inputot, s a hozzájuk tartozó hash értéket. Az input párokra kapott hash értékek azonosságához rendeljen 0/1 értékû indikátort. Adja össze ezen indikátor valószínûségi változókat, számítsa ki a várható értéket, s állítsa be 1 közeli értékre a várható ütközésszámot a t adjusztálásával.) [F.4. Tekintsük az m1, m2, ... , mt inputokat, s vezessük be az Xij indikátort, amely 0, ha H(mi)≠ H(mj), egyébként pedig 1 értékû. A valószínûségi modellünk alapján az {Xij =1} esemény valószínűsége 2-n, következésképpen E[Xij ]= 2-n. Az összes különböző párok vonatkozásában számítva az indikátor összegek (X) várható értékét kapjuk, hogy E [X ] = ΣiΣj i≠j E[Xij ] = t2/2n+1. E [X ] = 1 értékhez t=2n/2 adódik.]

F.5. Igazoljunk hash függvény tulajdonságokat: a.) az egyszerű modulo-32 ellenőrzőösszeg (32 bites szavak 32 bites összege) nem egyirányú (nem őskép-ellenálló). b.) az f(x)=x2-1 mod p (p prím) leképezés nem OWHF. c.) az f(x)=x2 mod pq (p és q “nagy” prímek) leképezés OWHF, de nem 2RHF. d.) az f(x,k)= Ek (x) (E a DES kódolás) leképezés d1.) (x,k) párban nem OWHF, d2.) nem OWHF x -ben, ha k ismert, d3.) OWHF k -ban, ha akár x és f(x,k) is ismert, illetve választott [F.5.

28

b.) modulo p szerinti gyökvonás ismert, “könnyű” feladat c.) (+x) 2= (-x) 2 ]

F.6. a.) Igazolja, hogy a hash függvények CRHF tulajdonságból következik 2RHF tulajdonság. b.) Igazolja, hogy egy hash függvény CRHF tulajdonságból nem következik az OWHF tulajdonság. Tekintse a 1 || x

, ha x bitmérete n

0 || g(x)

, egyébként

h(x)= függvényt, ahol g(x) {0,1}∞→{0,1}n CRHF. Igazolja, h(x) felhasználásával, hogy egy hash függvény CRHF tulajdonsága még nem garantálja az OWHF tulajdonságot. [F.6. a.) Indirekt. Ha nem lenne 2RHF, akkor egy x, H(x) párhoz találnánk egy olyan másik x’ inputot, amelynek lenyomata szintén H(x) lenne. Ezzel azonban előállítottunk olyan (x,x’) input párt, amelynek azonos a lenyomata, azaz ütközők. b.) h(x) ütközés-ellenálló, mivel: - ha az input mérete nem n, akkor 0 bittel kezdődő lenyomatunk van, ellenkező esetben 1 bittel kezdődő, - nem lehet az input pár mindkét tagjának mérete n, ami a h(x) alakjából triviális, - nem lehet az sem, hogy az input pár mindkét tagjának mérete n-től különböző, mivel g(x) ütközés-ellenálló. Ugyanakkor h(x) nyilván nem OWHF, hiszen az 1 bittel kezdődő lenyomatok midegyikéhez triviálisan ismert az őskép (azaz az 1 bitet követő bitsorozat).]

F.7. Adja meg az OWHF, CRHF, 2RHF tulajdonságok egymáshoz való viszonyát! [F.7.

OWHF CRHF 2RHF

Az egyes hash függvény tulajdonságok viszonya

29

] F.8. Tekintsük a Hi = h(Hi-1 ; Mi ) = EMi(Hi-1)

(x.2)

iterációs függvényû lenyomatkészítő eljárást (H0 publikus inicializáló érték), ahol E.(.) szimmetrikus kulcsú blokk rejtjelező. Mutassa meg, hogy ezen lenyomatkészítő OWHF! (Segítség: Alkalmazza a születésnapi paradoxonon alapuló középen találkozás támadást, kettévágva üzenetblokk-sorozatot; egyik oldalról H0-tól elõre iterálva, a másik oldaról a H hash értéktõl visszafelé iterálva!) [F.8. Tekintsünk egy tetszés szerinti - például csalárd - üzenetet (azaz üzenetblokkok sorozatát). Vágjuk két részre az üzenetet, s mindkét részének állítsuk elõ 2n/2 számú variációját (variációk elõállítására lásd az 1.1. feladatot). H0-tól elõre iterálva állítsuk elõ az elsõ részhez tartozó hash értéket. Másfelõl - felhasználva az E kódoló transzformáció invertálhatóságát - H hash értéktõl visszafelé iterálva állítsunk elõ ugyancsak 2n/2 számú blokkot a második rész variációira. Vegyük észre, hogy az üzenetblokk ismeretében Hi-1 = DMi(Hi) leképezéssel iterálhatunk visszafelé, i=r,r-1,... . Nagyobb, mint 50% az esélye annak, hogy a két iterációs irány illeszkedik valamely variensen. ]

F.9. (hatástalan dimenziónövelés) n bites hash lenyomatot képező r-iterációs iretatív hash függvényből n’=2n bites lenyomatot képzőt szeretnénk előállítani olyan módon, hogy a két utolsó iteráció eredményét konkatenáljuk azaz Hr-1||Hr 2n bites lenyomatot használunk az n bites Hr helyett. Megfelelő-e ez a fajta megerősítési ötlet a születésnapi támadás sikerének csökkentésére? [F.9. Nem, mivel a kapott hash függvény ellen 2n’/2 -nél kisebb számításigényű születésnapi ütközéses támadás továbbra is végrehajtható. Ugyanis elegendő csak magára az n bites Hr-1 -re végrehajtani ezt a támadást, hiszen ha m=[M1, M2, ... , Mr-1 ] , m’=[M’1, M’2, ... , M’r-1 ] üzenetpárra ütközés áll elő Hr-1 -re, akkor Mr -rel meghosszabbítva m és m’ üzeneteket, előáll az ütközés Hr -re is, s így Hr-1||Hr -re is. Ezért a nevezett támadás 2n'/4 számításigényű maradt, tehát a dimenziónövekedés nem hatékony. ]

F.10. a.) (hatásos dimenziónövelés) Bizonyítsa be, hogy ha H_1 és H_2 ütközés-ellenálló (CRHF), akkor a konkatenáció művelettel kapott H’=H_1 || H_2 hash függvény is CRHF. b.) Egy g: {0,1}2n→{0,1}n segédfüggvényel H’’=g(H_1 || H_2) dimenzió vissszaszûkítést végrehajtva egy az eredeti H_1 és H_2 komponens függvények input-output dimenziójának megfelelõ hash függvényre jutunk (lásd az x.ábrát). Milyen elõnyei lehetnek egy ilyen konstrukciónak? (Javasoljon egy g segédfüggvényt.)

30

m

H_1

H_2

g

x.ábra: Hash függvények kaszkádosítása [F.10. a.) Indirekt. Ha lenne m, m’ üzenetpár, amelyre ütközés állna elő a H’ hash függvény outputján, akkor az nyilván ütközést jelentene a komponens H_1 , H_2 hash függvények vonatkozásában is, ami e feltételeknek ellentmondana. ] [b.) Ahhoz, hogy az outputon ütközés álljon elő két különböző m, m’ inputtal, az kell hogy g(H_1(m),H_2(m)) és g(H_1(m’),H_2(m’)) megegyezzenek. Ha mindkét komponens vonatkozásában ugyanazon m,m’ párra tudnánk ütközést előállítani, akkor ez teljesülne. Heurisztikusan gondolkodva két “független” leképezés vonatkozásában ezen egyszerre történő ütköztetés összeszorozná a komponensenkénti ütköztetés feladat sikervalószínűségét (véletlenül sorsolva a párokat az inputon). Így egy erősebb függvényt kombinálhatunk. ]

F.12. (Damgard-Merkle megerősítés) Tegyük fel hogy van egy h kompressziós függvényünk ütközés-ellenálló tulajdonsággal. Igazoljuk, hogy ha az m=[M1, M2, ... , Mr1 ] üzenetet kiegészítjük egy Mr blokkal, amely - pl. a magasabb helyiértékek felé igazítva - tartalmazza az m üzenet bithosszát nulla bitekkel kiegészítve egész blokkhosszra, a h kompressziós függvényre épülõ iterációs hash függvény is CRHF. [F.12. Indirekt bizonyítással tegyük fel, hogy van m,m’ pár amelyre azonos a hash lenyomat. Tekintsük a következő két esetre bontást: az egyik eset, az amikor m és m’ azonos bithosszú, illetve amikor eltérő bithosszú. Az első esetben m=[M1, M2, ... , Mr ] , m’=[M’1, M’2, ... , M’r ] párra áll elõ azonos output: az redik üzenetblokk azonos (az azonos bithosszot tartalmazza), ezért h CRHF tulajdonsága miatt ez csak úgy lehetséges, ha a közbensõ, r-1-dik iterációs lépés outputja is azonos; ha az r-1 -edik üzenetblokk is azonos, akkor h CRHF tulajdonsága miatt ez ismét csak úgy lehetséges, ha a közbensõ, r-2 -dik iterációs lépés outputja is azonos s.í.t.. Ha a j-edik blokk az elsõ különbözõ visszafelé számolva - a két üzenetben, akkor ellentmondásra jutunk, mivel ezen lépésben ütközés állna elõ a kompressziós függvényre. A második esetben m=[M1, M2, ... , Mr ] , m’=[M’1, M’2, ... , M’R ] párra áll elõ azonos output, ahol az utolsó üzenetblokkok különbözők (az különböző bithosszot tartalmazzák). Mivel a r-edik

31

üzenetblokk különbözõ, ezért semmiképp sem állhatott elõ ütközés az outputon, ellenkező esetben h CR tuladonságával kerülnénk ellentmondásba].

F.13. Ha a hash függvény üzenet inputjának bithossza nem lenne üzenetblokk egész számú többszöröse, akkor teljes hosszra kell kiegészíteni (padding). Tegyen javaslatot a kiegészítésre, azon két esetet figyelembe véve, hogy az adási és vételi fél is ismeri az eredeti üzenet-bithosszat (pl. rögzített), illetve , ha ez nem áll fenn. [F.13. Ha megállapodott az üzenet eredeti bithossza, akkor nullákkal kiegészítés a szokásos. Ellenkező esetben egy 1-es, és nullák lehet a megoldás (azaz ...xxx 10...000), mivel így a egyértelműen megállapítható az eredeti üzenetvég. Ha teljes blokkhosszú az eredetei üzenet vagy egy bittel kevesebb, akkor ezen második módszer egy teljes plusz blokkal történő kiegészítésre vezet.]

32

MAC CBC-MAC (Message Authentication Code)

F.14. Mutassa meg, hogy a CBC-MAC nem védett választott szövegû támadás ellen! (H: Mutassa meg, hogy két n bites - azaz 1 blokk méretû - üzenetbõl konstruálható megfelelõ 2n bites üzenet!) F.14. A támadó kér egy-egy MAC lenyomatot egy m1 és egy m2 egy blokk méretű üzenetre. Eztán elõállítja az m=[m1, z ], z= MACk(m1) ⊕ m2 két blokk méretû üzenetet, amelyre MACk(m) = Ek ( Ek ( m1 ) ⊕ z ) = Ek ( Ek ( m1 ) ⊕ Ek ( m1 ) ⊕ m2 ) = MACk(m2) Tehát a támadó - a k kulcs ismerete nélkül - elõ tudott állítani MAC lenyomatot egy új m üzenethez. Ugyanakkor vegyük újra észre, hogy m második blokkja a támadó által gyakorlatilag nem kontrollálható véletlen blokk.

F.15. Mutassa meg, hogy a CBC-MAC nem védett választott szövegû támadás ellen akkor sem, ha úgy kívánjuk megerõsíteni, hogy a MAC számítás elõtt kiegészítjük az üzenetet egy olyan blokkal, amely az üzenet hosszát tartalmazza! A támadó képességérõl azt teszzük fel, hogy üzeneteire MAC lenyomatot kaphat, de a k kulcsot nem ismeri. F.15. Legyen M1, M2 és M3 három darab egy blokk méretû üzenet. A támadó kér MAC lenyomatot az M1, M2 üzenetekre, azaz kap Bi =Ek (Ek (Mi )⊕1), i=1,2 lenyomatokat, ahol 1 az üzenet blokkban kifejezett mérete. Eztán lenyomatot kér az m= [M1 ,1,M3] 3 blokk méretû üzenetre, azaz kap egy B=Ek ( Ek ( Ek ( Ek ( M1) ⊕ 1 ) ⊕ M3 ) ⊕ 3 ) = Ek ( Ek (B1 ⊕ M3 ) ⊕ 3 ) Könnyen látható azonban, hogy m’=[M2,1,z], z=B1⊕B2⊕M3 üzenetre szintén B lenyomatot kap a támadó: Ek ( Ek ( Ek ( Ek ( M2) ⊕ 1 ) ⊕ z ) ⊕ 3 ) = Ek ( Ek ( B2 ⊕ B1 ⊕ B2 ⊕ M3 ) ⊕ 3 ) = B.

F.16. Tekintsük az alábbi integritásvédelmi kódolást, ahol a rejtjelezés és MAC kombinációját használjuk: Ek( m|| MACk’(m) )

(x.3)

Legyen CBC módú mind rejtjelezés, mind a MAC számítás, ahol az egyik funkcióra IV, k míg a másikra IV’, k’ inicializáló vektor, kulcs páros kerül alkalmazásra. Van-e veszélye annak, ha IV=IV’, k=k’ “egyszerűsítő” választással élünk? Mi a tanulság? [ F.16. A CBC mód lépéseit végiggondolva közvetlenül látható, hogy az (x.3) kódolás eredménye Ek(m+IV)|| Ek(0), az üzenettől függetlenül, azaz semmiféle integritásvédelmet nem kapunk! A tanulság az, hogy az (x.3) alakú kódolásnál mindenképpen eltérő kulcsot kell alkalmazni a kétféle funkcióra. Például DES alkalmazása esetére k’ kulcsra egy szokásos választás a k kulcs minden második félbájtjának komplementálása.]

33

F.17. Mutassa meg, hogy a CBC-MAC hashing nem teljesíti az egyirányúság követelményét (k kulcsot ismerõ fél számára)! (Segítség: Mutassa meg, hogy n-bites üzenetblokkok tetszõleges véges sorozatát - a k kulcs ismeretében -kiegészíthetjük úgy egy további blokkal, hogy elõre megadott CBCMAC blokk álljon elõ!) [F.17. Legyen A egy tetszőlegesen választott MAC. Előállítható olyan üzenet, amelynek ez a lenyomata: legyen m üzenet m=[M1, M2, ... , Mr ] , azaz Mi üzenetblokkok r hosszúságú sorozata, amelyre MACk(m) CBC-MAC blokkot kaptuk. Ha egy r+1-dik üzenetblokkot Mr+1 = Dk(A) ⊕ MACk(m) szerint választjuk, könnyen ellenõrizhetõ, hogy m’=[M1, M2, ... , Mr+1] üzenetre hosszúságú sorozatára az elõírt MACk(m) blokkot kapjuk. Tehát, a k kulcsot ismerõ vételi oldal könnyen elõállíthat tetszõleges számú üzenetblokksorozatot, amelynek a lenyomata egy elõre megkívánt érték, tehát a CBC-MAC hashing nem teljesíti az egyirányúság követelményt. Ugyanakkor vegyük azt is észre, hogy bár a konstruált sorozat elsõ r blokkját tetszés szerinti csalárd tartalmúra beállíthatja, az r+1 -dik blokk tartalma már véletlenszerûen alakul. ]

MAC kulcsolt hash függvény felhasználásával

F.18. Egy MAC leképezést iterációs MDC alapján készítünk olyan módon, hogy a.) az m üzenetet egy k kulcsblokk prefix-szel bővítjük, b.) az m üzenetet egy k kulcsblokk suffix-szel bővítjük, c.) k blokkot alkalmazzuk, mind prefixként mind suffixként. Helyes-e a konstrukció, azaz nem ad-e támadási lehetőséget? [F.18. a.) Sajnos “könnyen” támadható. Ha ugyanis m üzenethez H(k||m) lenyomatot megfigyeljük, ahol k a kulcsblokk prefix, akkor egy tetszőleges y blokkal kiegészített x||y üzenethez az iterációs eljárás miatt nyilván H(H(k||m),y) alapján könnyen kiszámolhatjuk a lenyomatot a k kulcs ismerete nélkül. Az sem segít, ha az eljárás a bithossz suffix trükköt alkalmazza, mivel ekkor a bithossz is az üzenet részeként tekinthető, s a fenti generálás megismételhető.

b.) Sajnos ez esetben pedig a születésnapi támadás alkalmazható. A támadó 2n/2 komplexitással előállít m,m’ üzenetpárt, amelyre az MDC outputra ütközést állít elő (n bites a lenyomat). Ehhez nem szükséges a titkos k suffix ismerete. Ezután legálisan megszerez az m üzenetre egy a feladat szerinti generálású MAC(m)= MDC(m||k) lenyomatot. Az iterációs MDC lenyomatkészítés miatt nyilván képes előállítani helyes MAC lenyomatot m’ üzenetre is, hiszen MAC(m’)= MDC(m’||k)= MDC(m||k)= MAC(m). c.) Ha a k blokkot alkalmazzuk, mind prefixként mind suffixként akkor a két mondott támadást ötletében megakadályozzuk. ]

34

F.19. Ha mind a titkosság mind pedig az adatintegritás biztosítása szükséges egy lehetséges módszer a rejtjelezés és az MDC együttes alkalmazása azaz Ek( m || MDC(m) )

(x.1)

kódolás. A rejtjelezés funkció esetleges gyengesége esetén mind a titkosság, mind az integritásvédelem sérül. a.) Adjunk erre példát! b.) Képezzük az MDC-t olyan módon, hogy az üzenetblokkokat XOR összeadással összeadjuk, továbbá a rejtjelezés legyen CBC módú. Helyes-e az védelemnek ez a módja? c.) Segít-e a b.) -beli problémán az, ha az MDC egyszerû, lineáris CRC. [F.19. a.) Additív kulcsfolyamos retjelezést alkalmazása esetén ismert nyílt szövegű támadás során fennáll a lehetősége a kulcsfolyam rekonstruálásának, eztán módosítva a nyílt szöveget, hozzáillesztve a megfelelő MDC-t, s újra takarva a kulcsfolyammal sikeres támadást hajthatunk végre. b.) Nem. Ezen kódolás védtelen az üzenetblokkok teszőleges permutációjára, sőt arra is ha páros számú tetszés szerinti blokkot (!) beillesztünk. c.) Igen, lehet. Ugyanis, ha elegendően erős a rejtjelezés, a támadó nem képes a rejtett szöveg módosítását úgy végrehajtani, hogy ahhoz illesszen megfelelő MDC-t. ]

F.20. r számú üzenetblokkot tekintünk. Az üzenetblokkok XOR összege legyen az MDC. Az r üzenetblokkot CBC illetve OFB módban rejtjelezzük, így kapunk r rejtjelezett blokkot, s ehhez r+1-dik blokként suffixként adjuk az MDC blokkot. Mutassa meg, hogy a.) CBC esetén a rejtjelezett blokkok sorrendjének átrendezését, illetve tetszőleges blokk páros számú beillesztését b.) OFB esetén ezenfelül tetszőleges olyan rejtjelezett blokk cserét, amelynél a rejtjelezett blokkok XOR összege változatlan marad, az MDC vételi oldali ellenőrzése nem tud jelezni! [F.20. Közvetlen ellenőrzéssel.] F.21. Ha a rejtjelzés funkció a (x.1) alakú kódolásnál csak az MDC alapú integritásvédelem kiegészítõ funkciója - azaz azt védi egy hiteles csatornát nyújtva - , akkor nem javasolt a (x.1) használata. Ehelyett közvetlenül a MDC-t védhetjük rejtjelezéssel, tehát (x.1) helyett az alábbi kódolást használjuk: ( m || Ek(MDC(m) )

(x.2)

Milyen tulajdonsággal kell ezesetben az MDC-nek rendelkeznie?

35

[F.21. Ütközés ellenállónak kell lennie, hiszen előállítva m,m’ MDC- ütközésre vezető üzenetpárt, m “nem gyanús” üzenetre kérve az (x.2) kódolást Ek(MDC(m)) = Ek(MDC(m’)) miatt x’ üzenetre is ismert az ellenőrzőösszeg. ]

Digitális aláírás

A digitális alírás biztonsága: Egy (G,S,V) nyilvános kulcsú aláíró séma (t,q,ε)biztonságú, ha bármely Z S k BPP algoritmus esetén, amely az Sk aláíró-orákulumnak q kérdést tehet fel, t ideig futhat, annak a valószínűsége, hogy outputján előállít egy új (orákulumtól nem kérdezett) [üzenet, aláírás]-párt lefeljebb ε, azaz P

[V pk (m' , y ' ) = 1, ahol (m' , y ' ) ← Z S k ( pk )] ≤ ε

( pk , k ) ← G

tömörebben P

[V pk ( Z S k ( pk )) = 1] ≤ ε

( pk , k ) ← G

ahol G :véletlen → PK , K , a kulcsgeneráló algoritmus S : Kx{0,1}* → Y , az aláíró algoritmus V : PKx{0,1} * xY → {0,1} , az aláírást ellenőrző algoritmus PK, K , a nyilvános illetve titkos kulcsok tere F1. (egyszerű RSA aláírás, plain RSA) Az egyszerű RSA aláírást tekintsük, azaz az RSA alapú legfeljebb egy blokk méretű M üzenet ( M ∈ ( Z / nZ ) * ) S(M)=Md (mod n) aláírása esetén kihasználhatjuk támadásra az aláíró algoritmus homomorf tulajdonságát: azaz S ( M 1 ⋅ M 2 ) = S ( M 1 ) ⋅ S ( M 2 ) (mod n). Hogyan? [Az aláíró orákulumtól kérjünk aláírást például M1=2, illetve M2=2M üzenetekre, amelynek alapján előállíthatjuk az M üzenethez tartozó aláírást. Miért?]

F2. (egyszerű RSA aláírás) Lehetséges-e a fenti biztonság definíciónak megfelelően sikerrel támadni egyszerű RSA aláírást anélkül, hogy az aláírás orákulumhoz fordulnánk kéréssel, azaz q=0 esetben? [Igen. Tetszőleges y ∈ ( Z / nZ ) * aláírása az M=ye mod n üzenetnek, ehhez a támadáshoz csak nyilvános kulcsot használjuk.]

F3. (hash alkalmazása, hash and sign) M üzenet és h hash függvény esetén az S(M)=(00...00||h(M))d (mod n)

36

aláírást alkalmazzuk, ahol a zérusokkal teljes blokkra kiegészítést a legnagyobb helyiértékeken alkalmazzuk. Mutassuk meg, hogy az algoritmus továbbra is támadható marad, ha a.) h függvény nem egyirányú, b.) h homomorf tulajdonságú: azaz h( M 1 ⋅ M 2 ) = h( M 1 ) ⋅ h( M 2 ) . [a.) Határozzunk meg egy M ' ≠ M ősképet h(M) ismeretében. b.) Alkalmazzuk az F1. feladatbeli támadást.]

F4. (PKCS1) M üzenet és h hash függvény esetén az S(M)=(1FF...FF00||h(M)d) (mod n) aláírást alkalmazzuk, azaz a hash and sign módszerbeli zérusokkal való feltöltés helyett 1FF...FF00 feltöltést alkalmazzuk. Miért nem működik ekkor az F3. feladatnál alkalmazható támadás? (Támadás még nem ismeretes, de valószínűsíthető.) F5. (Full Domain Hash, FDH támadása véletlen orákulum modellben) FDH esetén a hash függvény outputjának mérete megegyezik az RSA blokkméretével (azaz nem annak szokásosan - töredéke). A támadó hozzáfér ezen hash függvényt modellező véletlen függvényként működő H publikus véletlen orákulumhoz, amelyhez legfeljebb t kérést intézhet (egy orákulum kérés 1 időegységet emészt fel). Ezenkívül továbbra is hozzáfér az S aláíró orákulumhoz, amelyhez legfeljebb q kérést intézhet. Tegyük fel, hogy az RSA (t,ε)-biztonságú csapdapermutáció. Mutassuk meg, hogy az FDH a.) (t,0,ε)-biztonságú b.) (t,q,tε)-biztonságú nyilvános kulcsú aláíró séma. [Indirekt bizonyítások: tegyük fel, hogy az FDH nem az adott biztonságú, azaz létezik Z algoritmus, amely a legalább a megadott valószínűséggel töri az aláíró algoritmust, s mutassuk meg, hogy ezesetben az RSA is törhető: azaz konstruálni tudunk egy Z' algoritmust, amellyel egy adott z RSA-rejtett blokkot dekódolni tudunk. a.) Z' algoritmus a Z algoritmusnak H orákulumhoz szánt kérését H' hash orákulum-szimulátorhoz küldi, e amely szimulátor működése a következő. Legyen Z i-edik kérése mi, amelyre H ' ( mi ) = ri z (mod n) n válasz érkezik, i=1,2,...,t, ahol ri ← R {0,1} véletlen elem. Z számára H és H' output eloszlása megkülönböztethetetlen, így azonos a Z kapcsolatos - aláírás-törő - sikergyakorisága. Z - valamilyen módon - a feltételezésünknek megfelelő gyakorisággal ki tudja számolni valamelyik válasz dekódoltját, e d d azaz Z outputja, sikere esetén [ mi , ( ri z ) = ri z (mod n)] , amelyből Z' először mi alapján előveszi ri véletlen elemet (képes rá, hiszen ő futtatja a H' szimulátort, s így annak minden részletéhez hozzáfér), majd egy moduláris osztással előállítja z rejtett szöveg zd dekódoltját, amivel ellentmondásra jutottunk. Mivel Z' a.cs.a. sikeres, amikor Z sikeres, így a két sikervalószínűség is azonos. (Megjegyezzük, hogy Z' úgy is működhetne, ha először kisorsolna egy j, 1 ≤ j ≤ t sorszámot véletlenszerűen, majd amikor Z j-edik orákulumkérését kezelné Z', a H' szimulátor válasza z, más kérések esetén véletlen (azaz H válaszát továbbítja egy kérés kivételével, amikor azt kicseréli z-re). Ekkor Z' sikervalószínűsége Z sikervalószínűségének t-edrésze lesz.)

37

b.) Z' először kisorsolna egy j, 1 ≤ j ≤ t sorszámot véletlenszerűen. A H' és S' szimulátorok működése legyen a következő: H'-höz intézett j-edik kérés esetén annak válasza z. Ha i ≠ j ,

H ' (mi ) = rie (mod n) , S ' (mi ) = ri (mod n) . Vegyük észre, hogy -szerencsére - a j-edik kérésnél kapott z válasszal Z' nem fordulhat S'-höz. ]

F6. (biztonságos one-time aláírás) Legyen f : {0,1}n → {0,1}n egy egyirányú permutáció. Az M ∈{0,1}m üzenet aláírásához generálunk véletlenszerűen 2m darab n bit méretű blokkot, amely a titokban tartunk (sk titkos kulcs), s ezen blokkok f leképezésével kapható 2m darab n bit méretű blokk alkotja a pk nyilvános kulcsot titokban tartunk, azaz sk = (r10 , r11 ,..., rm0 , rm1 ) , pk = ( f (r10 ), f (r11 ),..., f (rm0 ), f (rm1 )) Az M üzenet aláírását bitenként képezzük: Mi=0 aláírása ri0, Mi=1 aláírása ri1, azaz S sk ( M ) = (r1, M 1 ,..., rm, M m ) . Az V ellenőrző algoritmus az [ M , S sk ( M )] input, a pk nyilvános kulcs és f leképezés felhasználásával üzenetbitenként ellenőrzi az aláírás helyességét. a.) Mutassuk meg, hogy ha a támadó legalább két kéréssel fordulhat az aláíró orákulumhoz, továbbá m≥2, akkor teljes sikerrel támadja az aláírást, azaz létezik Z támadó, emelyre ε=1. b.) Mutassuk meg, hogy ha f (t,ε)-biztonságú egyirányú permutáció, akkor a fenti aláírás séma (t-O(1),1,2ε)-biztonságú. c.) Általánosítsuk b.) állítást tetszőleges m esetére. [

a.) Z aláírást kér a 0m és 1m üzenetekre, amivel a titkos kulcs birtokába jut. b.) Indirekt bizonyítás. Tegyük fel, hogy az aláírás séma (t-O(1),1,2ε)-törhető egy Z támadó által. Z' támadó egy y=f(x) inputra az x inverzet szeretné kiszámítáni. Z' a Z számára megkülönböztethetetlenül G és S helyett G' és S' szimulátorokat nyújtja. Z' kisorsol egy r n bites véletlen blokkot, majd feldob egy pénzt. Ha 0 a kimenetel, akkor G' outputja pk=(f(r),y), sk=(S(0)=r, S(1)=error), ha 1 a kimenetel, akkor G' outputja pk=(y,f(r)), sk=(S(0)=error, S(1)=r). Meghívja Z algoritmust, amely legfeljebb 1 kéréssel fordul az S orákulumot helyettesítő S' szimulátorhoz. Az invertálás sikervalószínűsége nyilván 1/2 azon esetekben, amikor Z sikeres.

]

F7. Ha egy (G,S,V) aláíró séma biztonságos, továbbá ha egy tömörítő leképezés is biztonságos az ütközésmentesség szempontjából, mit mondhatunk a tömörítvényre alkalmazott S aláírást alkalmazó származtatott biztonságáról (G',S',V') aláíró séma biztonságáról? [A támadó kétféleképp lehet sikeres: vagy egy új üzenetet tömörít és aláír, vagy talál egy olyan új üzenetet, amely tömörítvénye egy ismert aláírású üzenettel ütköző. Az első eset sikergyakorisága az aláíró séma támadhatóságának sikergyakorisága, míg a második lehetőség sikergyakorisága az tömörítő leképezés támadhatóságának sikergyakorisága. Következésképp a két sikergyakoriság összegződik, tehát a (G',S',V') aláíró séma is biztonságos marad.]

38

MISC F1. Adjunk meg X,Y,Z valószínűségi változókat, hogy páronként függetlenek legyenek, de együtt függők. [X=U, Y=V, Z=U⊕V, ahol U és V véletlen bináris vektorok. ]

F2. Tekintsük az RSA algoritmust. Tegyük fel hogy létezik olyan Z algoritmus és p polinom, hogy létezik k0, hogy tetszőleges k≥ k0 és az összes n,e esetén

P[ Z (n, e, RSAn ,e ( x) = x] ≥ 1 / p (k ) ahol a valószínúség a véletlen x választás illetve Z algoritmus véletlen bitjei felett számítódik, továbbá n két k bites prim szorzata. Mutassuk meg, hogy létezik Z’ algoritmus, hogy tetszőleges q polinom esetén, létezik létezik k0, hogy tetszőleges k≥ k0 és az összes n,e esetén

P[ Z ' (n, e, RSAn ,e ( x) = x] ≥ 1 − 1 / q (k ) ahol a valószínúség a véletlen x választás illetve Z algoritmus véletlen bitjei felett számítódik. [A vak-aláírás technikát használva Z’ az y inputjához kontruáljon elegendő t számú véletlen inputot az inverzképző Z algoritmus számára, amelyek közül ha Z akár egyet is invertálni képes, akkor Z’ már ki tudja számítani y inverzét. Adja meg t darabszámot p és q ismeretében, s végezze el Z’ sikerének analízisét.]

F3. a.) Használható-e a szokásos RSA rejtjelezés e=2 nyilvános kulccsal, ha a támadó a legális partnerek kommunikációját megelőzően (s csak ekkor) általa hozzáférhetett a dekódolóhoz. b.) Használható-e a szokásos RSA rejtjelezés e=2 nyilvános kulccsal, ha egy lehallgató támadó a legális partnerek kommunikációját követően is hozzáférhetett a dekódolóhoz. a.) Nem. Már egy dekódoláskérés is ½ valószínűségű faktorizációt tesz lehetővé. b.) Nem. Vak-aláírás technikát használva támadható.

39