Programozás | Programozás-elmélet » Fábián Zoltán - BMF-NIK Államvizsga Tételek, Szoftvertervezés, 2006

BMF-NIK Államvizsga Tételek Szoftvertervezés (2006) 10. Dinamikus adatszerkezetek 1 (Bináris fa, láncolt lista, B-fa, alkalmazási esettanulmányok, előnyök, hátrányok) LÁNCOLT LISTA Az egyirányú láncolt lista Ez egy nagyon egyszerű dinamikus adatszerkezet, amely egy eleje mutatóból, és rekordokból áll. A rekordok azonos típusúak: egy tartalom mezőből és egy következő mutatóból állnak. Attól, hogy a mutatók egyértelműen meghatározzák a végighaladás sorrendjét, az adatok a memóriában összevissza helyezkednek el. Az utolsó elem nil-re mutat Ez jelzi a láncolt lista végét. A tömbbel összehasonlítva Új elem felvétele egyszerű, mert csak két mutatót kell beállítani. Törölni is gyorsan lehet: a törlendő előtti elem mutatóját a következőre állítjuk, őt pedig felszabadítjuk. Hátránya a tömbhöz képest: átlagosan n/2 lépésben találunk meg egy elemet, mert csak szekvenciálisan tudunk keresni egy rendezetlen listában.

Akkor érdemes láncolt listát használni, ha az elemek mennyisége változik, mert a memória dinamikusan foglalható. Rendezni nem érdemes, mert az elemek közvetlen elérése nem valósítható meg, és csekély sebességnövekedést eredményez. Műveletek Lista létrehozása type Pelem=^Elem; Elem=record tartalom: integer; kovetkezo: Pelem; end; Itt megengedett, hogy előbb használjuk a típus (Elem), mint deklarálva lenne. Eleje:=nil; //nem hagyható el Lista bejárása P:=eleje; //segédváltozó While p<>nil do begin Kiir(P^.nev); P:=P^.kov; End; Új elem felvétele Lehetséges az elejére beszúrni vagy rendezett lista esetén egy megfelelő helyre. (előbb egy keresési feladat) Láncol listában nem tudunk visszalépni, ezért tárolni kell az előző címét. Elejére szúrás New(Q); //elem létrehozása Q^.tart:=x; //tartalommal való feltöltés Q^.kov:=eleje; //beláncolás az eleje mutató elé Eleje:=Q; //Q lesz az eleje a listának 1. oldal, összesen: 37

Rendezett beszúrás Elejére: ha az első elemnél kisebb a beszúrandó, vagy üres a lista. Középre: meg kell keresni az elem helyét. Végére: ha nagyobb, mint az utolsó. Lánc végére szúrás While p^.kov<>nil do P:= P^kov; P^.kov:=R; R^kov:=nil; //a végéig lépkedés //beláncolás, vége nil Keresés Szekvenciálisan végignézzük, amíg meg nem találjuk a keresett eleme(ke)t. Törlés Először egy keresés, aztán kiláncolás. Strázsa-technika Alapelv: definiálható két olyan elem (max és min), amelyek a lánca berakható elemek intervallumának széleit képezik. Ezek a megállási feltételek. Így a lista soha nem lesz üres, az ebből származó problémák megoldódtak. Kör adatszerkezet A lista utolsó eleme nem nilre, hanem egy másik lista elejére mutat. A másik lista vége pedig ennek az elejére. Így csak a belépési pontot kell megjegyezni. A kétirányú láncolt lista Visszafelé is van mutató, oda-vissza is tudunk lépkedni.

Rendezettségnél jól használható. 4. Bináris Fa (adatszerkezet, haszna, alkalmazási példák) felépítés, bejárások, törlés, gyakorlati Adatszerkezet A fa egy összefüggő körmentes gráf, tehát bárhonnan bárhová el lehet jutni rajta. Irányított, mert van egy gyökérpontja és ágai is A gyökérpontba nem megy él, csak innen indulhat ki. A bináris fa egy dinamikus (és rekurzív) adatszerkezet. Egy-egy levélpontja áll egy tartalom mezőből, egy bal –és egy jobb mutatóból. Felépítése: Az első elemfelvételnél a gyökérponthoz viszonyítva balra tesszük az elemet ha a gyökérnél kisebb, és jobbra, ha nagyobb. A többi elemfelvételnél ugyanígy először a gyökérponthoz viszonyítunk, majd elmegyünk az egyik irányba. Ha itt van már elem, azzal is összehasonlítjuk az új elemet, és elrakjuk annak a megfelelő oldalára. Elfajult eset: ha növekvő sorrendben vesszük fel az elemeket, egyágú bináris fát kapunk, amellyel a bináris

fa már értelmét veszti, hiszen egy ilyen fában átlagosan n/2 lépésben találunk meg egy elemet, ellentétben a kiegyensúlyozott fával, amelyben egy keresés átlagosan log2N ideig tart. 17 8 5 Például ilyen fa esetén az elemek felvitelének egy lehetséges sorrendje: 17, 8, 5, 9, 20, 40. De nem tudhatjuk mindig biztosan, hogy az elemeket milyen sorrendben vették fel. 20 9 40 Bejárások 2. oldal, összesen: 37 InOrder (bal, gyökér, jobb); PreOrder (gyökér, bal, jobb); PostOrder (bal, jobb, gyökér). Az In/Pre/Post a gyökér feldolgozásának idejére utal InOrder procedure InOrder(p: pelem); //param.-ként kapott gyökér begin if P<>nil then begin //megállási feltétel InOrder(P^.bal); //rekurzív hívások Kiír(P^.tart); //Tevékenység InOrder(P^.jobb); end; end; A rekurzív hívás mindig eltárolja, hogy P hova mutatott. Működése: az összes bal oldali elemet feldolgozza, mielőtt a gyökérre kerülne a sor. Rendezett, növekvő listát

állít elő. Az előbbi példa esetén: 5, 8, 9, 17, 20, 40. Ha csökkenő, rendezett listát szeretnénk, felcseréljük a bal mutatót a jobbra. PreOrder procedure PreOrder(p: pelem); begin if P<>nil then begin Kiír(P^.tart); PreOrder(P^.bal); PreOrder(P^.jobb); end; end; Az ezzel a módszerrel kapott lista alapján a fa rekonstruálható. (Ha ilyen sorrendben vesszük fel az elemeket egy új, üres fába) A példa alapján: 17, 8, 5, 9, 20, 40. PostOrder procedure PostOrder(p: pelem); begin if P<>nil then begin PostOrder(P^.bal); PostOrder(P^.jobb); Kiír(P^.tart); end; end; Először a levélelemeket dolgozza fel. A fa felszabadítása így lehetséges Ha paraméterként nem a gyökérelemet kapja, hanem egy levélpontot, akkor az ez alatti elemeket szabadítja fel, beleértve a levélelemet is. (A részfatörlő algoritmust lásd az 5 tételben) A példa alapján: 5, 9, 8, 40, 20, 17. Keresés A rekurzív újrahívások során az algoritmus mindig elmegy balra, vagy

jobbra, aszerint, hogy kisebb vagy nagyobb a keresett elem az éppen vizsgáltnál. A megállás a tevékenység végrehajtása után következik be, mivel nem történik újabb rekurzív eljáráshívás. Egy elem törlése Cél: egy elem törlése minimális munkával. A levélelemeket könnyű törölni, mert nincs alattuk semmi. Dispose(p) után a „szülő” elem mutatóit nil-re állítjuk. 3. oldal, összesen: 37 Az egy leszármazottal rendelkező elemeket is könnyű törölni: kiláncolás. Nehéz törölni azokat az elemeket, amelyeknek két leszármazottjuk van, mert feltétel a fa tulajdonságainak megtartása. Ebben az esetben a törlendő elem bal oldali részfájának legjobboldalibb elemével kell felülírni a törlendő elemet. Sorrendben ez a kisebb a törlendőnél Az eljárás hívása: Torol(törlendő, gyökér). Bináris Fa és Típusos Fájl Összekapcsolás Cél: nagyobb adatmennyiség gyors elérése háttértárról, a keresés megvalósítása log2N

lépésben. Módszer: Legyen egy név szerint rendezett típusos fájl. Ebben a logaritmikus keresés használható. Hátránya, hogy csak egy szempont szerint lehet egy időben rendezett a fájl (fizikailag). Új elem felvétele, törlése a rendezettség megtartásának kényszere miatt lassú. B-fa (alapvető szabályok, új elem felvitel, keresés, törlés) A bináris fa hátrányai • Ha rendezett adatokat feszünk fel, akkor egy része elfajulhat, a keresés lelassul • Ha sok adatot szeretnénk tárolni a fában, lehetséges, hogy nem fér el a memóriában. Ekkor lemezen kéne tárolni: a lemezről olvasás sokkal lassabb A B-fa (Bayer, 1972) A B-fákban a csúcsoknak sok gyerekük lehet, akár több ezer is. A B-fák elágazási tényezője sokkal nagyobb, mint a bináris fáké, ezért magasságuk lényegesen kisebb. Ha a B-fa egy X csúcsa N[X] kulcsot tartalmaz, akkor az X-nek N[X]+1 gyereke van. Ha a B-fákban egy kulcsot keresünk, akkor (N[X]+1)-féle választásunk

lehet, mert a keresett kulcsot N[X] kulccsal hasonlítjuk össze. A B-fa magassága a benne lévő csúcsok számának növelésekor csak a csúcsszánok logaritmusával nő. Tulajdonságai • A kitöltöttségi faktor (a redundáns adatok száma) 50%-nál jobb a Bfa esetében • Egy lemez-szektorba bele kell férjen a fa egy mezejének tartalma, így pl. a BlockRead eljárással gyors adatkezelés valósul meg • Minden lap legfeljebb 2n tételt tartalmaz (n jelenti a B-fa rendjét) • Minden lapon -a gyökérlapot kivéve- legalább n tétel van • Egy lap lehet levél (utód nélküli) vagy n+1 utóddal rendelkezik, ahol n a kulcsok száma • Minden levél-lap ugyanazon a szinten helyezkedik el 4. oldal, összesen: 37 19.3 ábra Egy 2 magasságú B-fa, amelynek több, mint egymilliárd kulcsa van. Mindegyik belső csúcsnak és levélnek 1000 kulcsa van Az 1 mélységben 1001 csúcs van, a 2 mélységben több, mint egymillió levél található. Minden x csúcsban n[x],

azaz az x-ben levő kulcsok száma is látható. Beszúrás A B-fa t minimális fokszáma 3, ezért egy csúcsnak legfeljebb 5 kulcsa lehet. Azokat a csúcsokat, amelyeket a beszúrás alatt módosítottunk, halványabban sötétítettük. (a) A példában szereplő fa kezdeti állapota (b) A B beszúrásának az eredménye; ez egy egyszerű eset, egy levélbe kellett 5. oldal, összesen: 37 beszúrni. (c) Az előző fába egy Q kulcsot szúrtunk be Az RSTUV csúcs két részre bomlott, az RS és az UV csúcsokra, a T a gyökércsúcsba ment, és a Q a baloldali új csúcsba (RS-be) került. (d) Az előző fába egy L kulcsot szúrtunk be. A gyökércsúcsot fel kellett bontani, mivel már telített volt, így a B-fa magassága eggyel nőtt. Ezután az L kulcsot a JK-t tartalmazó levélbe szúrtuk be. (e) Az előző fába az F kulcsot szúrtuk be Az ABCDE csúcsot szétvágtuk, és ezután az F kulcsot a jobboldali új csúcsba (DE-be) szúrtuk be. Törlés 6. oldal, összesen:

37 A B-fa minimális fokszáma t = 3, így a csúcsoknak (a gyökércsúcsot kivéve) nem lehet kettőnél kevesebb kulcsa. A módosított csúcsokat kevésbé sötétítettük be (a) A 197(e) ábrán látható B-fa (b) Az F törlése Ez az leset: egy egyszerű törlés a levélből. (c) Az M törlése Ez a 2a eset: L-t, ami az M megelőzője, felvisszük az M helyére. (d) A G törlése Ez a 2c eset: A G-t levisszük, és elkészítjük a DEGJK csúcsot, majd a G-t kitöröljük ebből a csúcsból. (e) A D törlése Ez a 3b eset: a rekurziót nem lehet levinni a CL csúcsba, mivel annak csak 2 kulcsa van, ezért a P-t kell levinni, egyesíteni a CL-t és a TX -et a CLPTX csúcsba; ezután a D törölhető a levélből (1. eset) (e) A (d) után a fa gyökércsúcsát töröljük, ezzel a fa magassága eggyel csökken. (f) A B törlése Ez a 3a eset: A C elfoglalja a B helyét, E pedig a C pozícióját. 1. Ha a k kulcs az x csúcsban van, és x egy levél, akkor az x kulcsot

töröljük az x-ből. 2. Ha a k kulcs az x csúcsban van, és x a fa egy belső csúcsa, akkor a következőket kell végrehajtani: a. Ha y az x-nek gyereke, y tartalmaz egy k-t megelőző kulcsot, és y-nak legalább t kulcsa van, akkor keressük meg az y gyökércsúcsú részfában a k-t közvetlenül megelőző k kulcsot. Rekurzívan töröljük k-t, és helyettesítsük k-t k -vel az x-ben. (A k megkereséséhez és törléséhez egy lefelé haladó menet elegendő.) b. Szimmetrikusan, ha a z gyerek következik az x-beli k után, és z-nek legalább t kulcsa van, akkor keressük meg a z gyökércsúcsú részfában a k-t közvetlenül követő k kulcsot. Rekurzívan töröljük k -t, és helyettesítsük k -t k -vel az x -ben. (A k megkereséséhez és törléséhez egy lefelé haladó menet elegendő.) c. Egyébként, ha mind y -nak, mind z -nek csak t - 1 kulcsa van, akkor egyesítsük k-t és a z kulcsait y-ba, úgy, hogy x-ből töröljük a k-t és a z-re mutató pointert.

Ekkor y -nak 2t - 1 kulcsa lesz Ezután szabadítsuk fel z -t és rekurzívan töröljük k -t az y -ból. 7. oldal, összesen: 37 3. Ha a k kulcs nincs benne az x belső csúcsban, akkor határozzuk meg annak a megfelelő részfának a ci[x] gyökércsúcsát, amelyben a k biztosan benne van, ha egyáltalán benne van k a fában. Ha ci[x] -nek csak t - 1 kulcsa van, akkor hajtsuk végre a 3a. vagy a 3b pontban leírtakat, mivel biztosítani kell azt, hogy annak a csúcsnak, amelyre lelépünk, legalább t kulcsa legyen. Ezután a műveletet az x megfelelő gyerekén rekurzióval befejezhetjük. a. Ha ci [x] -nek csak t- 1 kulcsa van, de van egy testvére, melynek t kulcsa van, akkor vigyünk le ci[x]-be egy kulcsot x-ből, a ci[x] közvetlen baloldali vagy jobboldali testvérétől pedig vigyünk fel egy kulcsot x-be, és vigyük át a megfelelő gyereket a testvértől a ci [x] -be. b. Ha c2 [x] -nek, és a ci [x] minden testvérének t - 1 kulcsa van, akkor egyesítsük ci -t

az egyik testvérével, és utána vigyünk le egy kulcsot x -ből ebbe az egyesített csúcsba, ez a kulcs lesz az egyesített csúcs középső kulcsa. Mivel egy B-fában a kulcsok többsége levelekben van, valószínű, hogy a törlés műveletek nagy része levelekből töröl kulcsot. Ekkor a B-FábóL-TÖRÖL eljárás a fában lefelé haladó, egymenetes, visszalépés nélküli procedúra. Azonban, ha egy belső csúcsból kell egy kulcsot törölni, az eljárás egy lefelé haladó menetben megy le a fában, de utána visszatér abba a csúcsba, ahonnan egy kulcsot törölt, azért, hogy ezt a megelőző vagy követő kulccsal helyettesítse (2a. és 2b eset) 11. Dinamikus adatszerkezetek 2 (Gráfok Ábrázolási módok Bejárási módszerek. Feszítőfa algoritmusok Problémák, feloldási lehetőségek) Gráf • • • • • • Csúcsok és élek halmaza: G (V,E) Lehetnek benne körök (probléma: ezeket nem láthatjuk előre bejáráskor) Negatív kör: végtelen

ciklusú optimális útkeresés Típusok: irányított (nyíllal) és irányítatlan, súlyozott (költség) és súlyozatlan Tipikus gyakorlati példa: úthálózat, térképek Előfordulhat, hogy egy súlyozott gráf esetén a rövidebb út nagyobb költséggel jár. Pl emelkedőn kell felmennünk autóval vagy arról közeledik a világvége Gráfok ábrázolási módjai • A számítógép számára le kell írni a gráfokat (átlátható megjelenítés; zoom, grab lehetősége) o Szomszédsági lista (láncolt lista) o Csúcsmátrix Szomszédsági lista: - irányított gráfnál csak azt írjuk fel, akit valahonnan el lehet érni 1 2 - súlyozott esetén egy költséggel is kiegészítjük a listát - Tárolásra vonatkozó módszerek: o láncolt lista o láncolt lista a láncolt listában (minden listaelemből egy új lista indul, mátrixszerűen) o Egy tömbbe felvesszük a lista első elemeire mutató mutatókat (gyorsabb elérés) o Tárigény: N db eleje mutató + az élek

száma - Előnyök: o hatékony és tömör tárolás kevés él, sok csúcs esetén 8. oldal, összesen: 37 5 - o könnyű eldönteni, hogy két él szomszédos-e Hátrányok: o nehéz meghatározni, hogy két tetszőleges pontot összeköt-e él (lineáris keresés, lassú) Csúcsmátrix: 1 2 3 4 5 1 0 1 0 0 1 2 1 0 1 1 0 3 0 1 0 1 0 4 0 1 1 0 0 5 1 0 0 0 0 - Tulajdonságai: o irányítatlan gráf esetén a mátrix a főátlóra szimmetrikus o irányított esetén nem szimmetrikus - Tárolás: o csak a főátló alatti vagy feletti elemeket kell tárolni o Súlyozatlan gráf esetén 1 bit elég (igaz / hamis) o Súlyozott esetén pedig közvetlenül a táblázatba írjuk a súlyokat o Tárigény: NxN (táblázat) - Előnyök: o sok él esetén hatékony tárolás - Hátrányok: o nehéz eldönteni, hogy két él szomszédos-e Bejárási algoritmusok Szélességi bejárás • • • Cél: szélességi sorrendben bejárni a gráfot o egy kezdőpontból indulva o a

kezdőponttól való távolság függvényében o minden csúcsot egyszer érintve Ha a gráf nem összefüggő, egy pontból kiindulva nem érhető el minden csúcs Eredménye o egy fa (összefüggő, körmentes gráf) o nem egyértelmű, más megoldás is lehet Algoritmus 9. oldal, összesen: 37 Szélességi Keresés (G, s) Ciklus minden U∈V [G] – S kezdőpont minden csúcsra //V[G] : a csúcsok halmaza Szín(U) := fehér D(U) := végtelen //a kezdőponttól való távolság π (U) := NIL //az előző elemet jelenti: ahonnan jöttünk D(S) := 0 //a kezdőpont π (S) := NIL //a kezdőpont előtt nincs senki Q := {sor, amit kiinduló állapotban S-re állítunk} //FIFO adatszerkezet Ciklus amíg Q nem üres U := ElsőElem (Q) Ciklus minden V∈ Szomszéd(U) //U minden szomszédjára Ha (Szín (V) = fehér) Akkor Szín (V) := szürke d(V) := d(U) +1 π(V) := U //a V csúcsba az U-ból jöttünk SORBA (Q, V) //’Szín(S) := szürke’ nem kell, mivel a végén fekete lesz,

addig nem bántjuk elágazás vége Ciklus vége SORBÓL (Q) //kivesszük az első elemet a sorból, Szín (Q) := fekete // mivel a fenti ciklus már feldolgozta Ciklus vége Ciklus vége Szélességi keresés vége Magyarázat o Fehér: olyan csúcs, amelyet még nem érintettünk o Szürke: olyan csúcs, amelyet már érintettünk, de van olyan szomszédja, amit még nem o Fekete: minden szomszédját és őt magát is feldolgoztuk o Lehet, hogy maradt fehér, de amit valaha elértünk, az fekete lett Útkiíró eljárás: (Egy láncolt lista fordított sorrendű kiíratása, eredménye egy erdő) o Az összes π elsőbbségi listához helyes megoldást ad. Eljárás UtKiir (G, S, V) //két csúcs között megtalálja az utat Ha (V = S) akkor Print S //végeztünk, megállási feltétel Különben Ha (π (V) = nil) akkor Print „nincs út S és V között” //megállási feltétel Különben UtKiir(G, S π(V)) Print V különben vége Különben vége UtKiir vége 10. oldal,

összesen: 37 Mélységi bejárás o d(U): U elérési ideje; ezen időpont előtt a csúcs színe fehér o f(U): o U elhagyásának ideje o D(U) és f(U) között a csúcs színe szürke o F(U) után a csúcs színe fekete MK (G) //MK : mélységi keresés, G : gráf Ciklus minden U∈V (G) csúcsra Szín (U) := fehér //nem előd fa, hanem diszjunkt fák π (U) := NIL idő := 0 //az elérés, illetve az elhagyás ideje Ciklus vége Ciklus minden U∈V (G) csúcsra Ha szín(U) = fehér akkor MK Bejár (U) Elágazás vége Ciklus vége Eljárás vége Bejáró eljárás: MK Bejár (U) Szín (U) := szürke d(U) := idő; //most értük el, az elérés időpontja idő := idő +1 Ciklus minden V∈ Szomszéd(U)–ra Ha (szín (U) = fehér) akkor π (V) := U MK Bejár (V) //itt addig előáll egy újabb fa, amíg minden fekete nem lesz (erdő) Elágazás vége Ciklus vége Szín (U) := fekete f(U) := idő; idő := idő + 1 eljárás vége //most hagyjuk el Feszítőfa algoritmusok

Minimális feszítőfák Adott egy G irányítatlan, összefüggő, súlyozott gráf. A G gráf egy feszítőfája tartalmazza G összes csúcsát, valamint az élek egy olyan részhalmazát, amelyre teljesül az, hogy a keletkező gráf összefüggő, és nem tartalmaz kört. Nyilvánvalóan ilyen fából több is lehet A minimális feszítőfa probléma az, hogy meg kell találni a minimális összsúlyú feszítőfát. Ha súlyozatlan gráfról van, akkor nyilván mindegyik feszítőfa összsúlya ugyanakkora, mégpedig V-1. Tehát ezentúl feltesszük azt, hogy a gráf súlyozott. 11. oldal, összesen: 37 A minimális feszítőfa növelése: A minimális feszítőfa algoritmusok mohó jellegűek. Az algoritmus működés közben mindig az egyik minimális feszítőfa egy részét tartja nyilván. Ezt a feszítőfát nyilván előre nem ismerjük, viszont egy tétel alapján biztosak lehetünk abban, hogy ez valóban minimális feszítőfa. Minden lépésben meghatározunk egy

(u,v) élt, amely még nem része az aktuális feszítőfa-kezdeménynek, viszont ha hozzávesszük, akkor továbbra is teljesülni fog az, hogy van olyan minimális feszítőfa, amelynek része a most keletkezett fa. Az ilyen élt biztonságos élnek nevezzük, mivel a feszítőfa-kezdeményhez hozzávéve továbbra is feszítőfa-kezdemény marad, nem rontja el azt. Algoritmus: MFF() A=üres while az A nem feszítőfa keressünk egy biztonságos (u,v) élet A-ra nézve A=A U {(u,v)} return A A biztonságos (u,v) él keresésekor ilyen él biztosan létezik, mivel feltétel az volt, hogy A része egy minimális feszítőfának. Az algoritmus legérdekesebb része, hogy hogyan ismerjük fel a biztonságos éleket, és hogyan találunk egy ilyet hatékonyan. A Kruskal algoritmus Egy erdőt fogunk addig élekkel bővíteni, amíg fát nem kapunk. Alapból a gráf minden egyes pontja külön fát alkot, tehát nincs él az erdőben. A főciklus minden egyes lépésében kiválasztjuk a

legkisebb súlyú olyan élet, amely két különböző fát köt össze. Ehhez könnyedén találunk olyan vágást, amely kielégíti a tétel feltételeit, tehát az biztonságos él lesz. Ezért ezzel az éllel bővítjük az erdőt Ezt addig ismételjük, amíg kész nem lesz a fa Kruskal(G) //G egy n szögpontú, súlyozott, irányítatlan gráf T := {üres halmaz} Ciklus i:=1-től n-1-ig e := {a legkisebb súlyú él, amelynek hozzávételével nem alakul ki kör} T := T u {e} //T a minimális feszítőfa Ciklus vége Kruskal vége Példa Induljunk az egyik legkisebb súlyú A 2 D 1 E élből (tetszőleges): 1. BC=1 {B,C} 5 2 3 4 2 4 2. DE=1 {B,C} {D,E} 3 O C 6 T 3. CF=1 {B,C,F} {D,E} 4. AD=2 {B,C,F} {A,D,E} 6 1 2 5. ET=2 {B,C,F} {A,D,E,T} 1 6. AC=2 {A,B,C,D,E,F,T} (A és C B F külön halmazból valók, ezért nem 7 alakul ki kör) 7. FT=2, AB=3, DC=3, EC=4 (kör alakulna ki) OC=4 {O,A,B,C,D,E,F,T} (jó, készen van) 12. oldal, összesen: 37 A Prim algoritmus Ebben az

esetben egy fát bővítünk addig, amíg nem kapjuk meg az eredeti gráf egy feszítőfáját. Egy tetszőleges pontból indulunk ki; kezdetben csak ebből az egy pontból fog állni a fa. Prim(G) //G egy n szögpontú, súlyozott, irányítatlan gráf T := {a legkisebb súlyú él a kezdőpontból} Ciklus i := 1-től n-2-ig e := {a legkisebb súlyú él, amely szomszédos egy T-beli éllel, és n.ak kör hozzávételével} T := T u {e} Ciklus vége Példa A 7 1 4 5 6 O B 2 5 C D 6 4 5 T 1 8 E 2 1. Induljunk O-ból (tetszőleges) O: OA=4 {O,A} 2. O: OC=5 A: AB=1 {O,A,B} 3. O: OC=5 A: AD=7 B: BC=2 {O,A,B,C} 4. A: AD=7 B: BE=4 {O,A,B,C,E} C: CE=5 5. A: AD=7 B: BD=5 E: ED=1 {O,A,B,C,D,E} 6. D: DT=6 {O,A,B,C,D,E,T} E: ET=8 12. Konvencionális rejtjelrendszerek (Caesar Vigenere Egyszerű helyettesítés A módszerek ismertetése és fejtésük) Caesar módszer - A HAL egyes betűi eggyel jobbra eltolva: IBM (2001 Űrodüsszeia) - Adott egy abc, és egy szám. Ez utóbbi

szám a kulcs, amely az eltolás mértékét jelenti Törése: • A feltörés az angol abc-ből adódó 26 lehetőség kipróbálásával lehetséges. Ezután szövegelemzés, szótár segítségével dekódolható. Kiválasztjuk azt a megoldást, amelyben értelmes szavak találhatók • A szöveg hosszától függ, hogy van-e több lehetséges értelmes üzenet (2 karakterig nem fejthető vissza, 3-tól már igen) • A feltörés másik módja a betűgyakoriság-statisztika használata. Jól definiált statisztikák vannak a betűgyakoriságra vonatkozóan. De ez nyilvánvalóan függ a szöveg típusától (mese, doktori disszertáció) • Összevetjük az általunk készített statisztikát a nyelvhez tartozó statisztikával. A leggyakoribbakat és a legritkábbakat kivesszük, ezek valószínűleg ugyanazokat a betűt jelölik az eredeti nyelven és a kódolt szövegben. • Más statisztikák is léteznek: adott betű után milyen betűk következnek tipikusan

Vigenere-módszer 13. oldal, összesen: 37 - Alapja egy táblázat, amely esetében máig megoldatlan, hogy hányféleképpen lehet kitölteni. Minden sorban egy betű csak egyszer szerepelhet - A nyílt üzenetünk és az ismétlődő kulcs egyes betűi határozzák meg a megfelelő titkosított betűt. Ezt minden karakterpárra elvégezve adódik a A B C D titkosított üzenet: A B C D A B C D A B Nyílt üzenet amit titkosítani akarunk C D A B C + KulcsKulcsKulcsKulcsKulcsKulcsKulcsKulcs Titkosított üzenet D A B C D Például – Kódolás (vízszintes + függőleges): BABA + CDABCDAB AACC Például – Dekódolás • adott oszlop kiválasztása a kulcs betűje alapján, • majd ebből az oszlopból kiválasztjuk a kódolt üzenet betűjét. • az ezt a sort jelképező betű lesz az eredeti betű: AACC - CDAB BABA Megjegyzések: - A titkosság a táblázat ismeretén és a kulcson múlik - A xor B xor B = A (kizáró vagy) - A kulcsot nem ismeri a támadó, különben

ő lenne a célszemély Megfejtés kulcs nélkül: - Brute-force: az összes kulcsot kipróbáljuk o 1 betűs: 26 lehetőség o 3 betűs: 26x26x26 = kb. 18000 sor o k betűs: 26k - Ha a rejtett üzenetben két ugyanolyan betűt látunk, az nem feltétlenül ugyanazt a betűt jelenti a nyílt üzenetben (lásd a példát). - Se a betűgyakoriságot, se a szógyakoriságot nem tartja meg - A kulcs mérete nagyon fontos. Az egy-egy megfeleltetést a kulcs elrontja A betűk rákövetkezése is sérül Törés a kulcshossz ismeretében: - Tegyük fel, hogy tudjuk kulcs hosszát. Így feloszthatjuk a titkosított szöveget kulcshossznyi részekre. Ezekben az egyes betűk ugyanahhoz a kulcsbetűhöz kell, hogy tartozzanak. A gyakoriságvizsgálatot ezekre az i-edik elemekre végezzük úgy, mint a Caesar módszernél. A módszer ismét a próbálgatás, de most nincs olyan sok lehetőség. 14. oldal, összesen: 37 Hogyan lehet rájönni a kulcs hosszára? - Betűgyakoriság-vizsgálatot

végzünk minden i-edik betűre. Ha nem találjuk el a jelszót, akkor egyenletes eloszlást kapunk. Ha eltaláljuk, nem egyenletes az eloszlás. - Az XOR használatára rá lehet jönni, de ha táblázattal alkalmazzuk, akkor sokkal nehezebben törhető - A Brute-force gyakorlatilag nem alkalmazható, mert o nagy számításigény (k kulcs) o Túl sok előálló lehetséges eredmény, amit ellenőrizni kellene - Feltörés: ha a támadó egyedül a kulcs hosszát nem ismeri, de egyébként a módszerről mindent tud, akkor: o Meg kell határoznia a kulcs hosszát o Majd ennek ismeretében statisztikai módszerekkel, betűgyakorisággal törheti fel a szöveget o L szórásnégyzet o N: az üzenet teljes hossza, n a lehetséges karakterek 2 száma, míg SA a szövegben előforduló ’A’ karakterek  i N  L =  S A −  + . +  S Zi számát jelöli. n   o Ha minden betűből ugyanannyi lenne, akkor 2 egyenletes eloszlást kapnánk. Z  N  i o Négyzetre

emelés: egy átlagtól való eltérést ∑ S −  szeretnénk, ezért nem akarunk negatív számokat látni, j = A j n amelyek kiolthatnák a többieket o Amikor eltaláltuk a kulcs hosszát, az eredmény nagyon nagy vagy nagyon kicsi lesz, vagyis nem egyenletes eloszlású o Ha rosszul tippeltük meg a kulcs hosszát, azzal az egyes statisztikákat elrontjuk, így az nem őrzi meg az adott betű tulajdonságát o Pl. egy betűből sok volt, de mindig más hosszal toltuk el, ezért az eloszlás elromlott, egyenletessé vált o Megjegyzés: ez a támadási módszer csak akkor alkalmazható, ha a rejtett üzenet a kulcsnál sokkal hosszabb Egyszerű helyettesítés - Minden nyílt betűnek megfelel egy rejtjeles - Olyan, mint a transzpozíciós, csak a kulcshossz 256 (vagy 26) - Törése: o Az első néhány statisztikailag biztos betű (szóköz, e, t, a) meghatározása o Szótár alapján az olyan szavak keresése, amelyekben az imént megtalált betűk adott helyen

vannak o Pl. a statisztika után előállt egy félig dekódolt szó: A T A A o A szótárból kikeressük az összes olyan 9-betűs szót, amelyikben a második, negyedik, hetedik helyen A áll, a harmadikon T, stb. o Az ilyen szavakból egyet ráillesztünk, majd megyünk tovább, hiszen felfedtünk megint egy pár új betűt. o Ha rossz szót illesztettünk rá, egy idő után kiderül. Ekkor backtrack - Törése 2: o Mint a transzpozíciós esetében, betűrákövetkezéssel, 256 (26) kulcshosszal 15. oldal, összesen: 37 N −  n 2 13. Elméletileg fejthetetlen titkosítási módszerek (Elméleti alapok A Vernam módszerek ismertetése és kritikai elemzése.) A véletlen átkulcsolás módszere (= one time pad) (Vernam, 1920) Kulcs: egyenletes eloszlású véletlen karaktersorozat: - Az eredmény eloszlása is egyenletes lesz, mivel mindig véletlennyivel toljuk el a karaktereket - Ez a módszer elméletileg törhetetlen, mivel irreálisan nagy

számítógép-kapacitás birtokában sem fejthető meg - Gyakorlati titkosság: irreálisan nagy számítógép-kapacitás birtokában megfejthető (Pl. Vigenere-módszer) - Törés: nincs módszer arra, hogy az előállt ’tört’ üzenetek sorozatából kiválasszuk azt, amelyik ténylegesen elhangzott Problémák a módszerrel: - a kulcs nagyon hosszú: n - a kulcs nem jegyezhető meg, ezért tárolni kell. A törés könnyebbé válik - Gyakorlati feloldása: a kulcsállomány pl. egy kép lehet, ami megegyezés alapján valamelyik publikus szerveren van. (A bejövő adatforgalmat figyelni nehéz) - A kimenőt viszont lehet figyelni, így észrevehetik, hogy zagyvaság van a szövegben - A kulcs tárolása, továbbítása okozza a nehézséget Alkalmazásakor hibákat lehet elkövetni, pl. többször használjuk ugyanazt a kulcsot: o Ha a titkosító elmondja, amit egyszer már titkosítottak, o És megvan a hozzá tartozó titkosított üzenet, a képlet szerint törhető X 1 +

k = Y1 X 2 + k = Y2 X 1 − X 2 = Y1 − Y2 Feladatok: X 1 = Y1 − Y2 - Rájönni, hogy két üzenetet ugyanazzal a kulccsal kódoltak - Ha ezt tudjuk, akkor fejtsük meg a szöveget: o Valószínű szövegrészek keresése: vannak gyakran előforduló szavak, mint pl. névelők, kötőszavak; illetve nagyjából tudjuk, hogy miről szól az anyag, így könnyebb gyakori szavakat találni. o Kétirányú kiterjesztés: megsejtjük az egyik részt, ezért megnézzük, hogy a megsejtett szó felhasználásával értelmes üzenet keletkezik-e a másik titkosított üzenetben o Az egyiket feltételezzük, a másikat ez alapján be tudjuk írni, a képlet alapján. Így már kevesebb próbálkozásra van szükség. Ha a másik értelmes lesz, visszavezetjük az előzőre, s így tovább. Például, ha a második szó egy részét ismerjük, következtetünk az első rész hiányzó részére a képlettel. o Ha az üzenetnek van valamilyen protokoll szerinti struktúrája, amit ismerünk

(pl. JELENTEM-mel kezdődik), akkor könnyebb a következtetés o Ha az egyik üzenet hosszabb, a kilógó részről semmit sem tudunk 16. oldal, összesen: 37 + X2 Hogyan lehet rájönni, hogy ugyanaz a kulcs? - Ha több üzenetet fogunk el, az esélyünk megnő, a kétirányú kiterjesztés az eddigi érthetetlen részeket értelmezheti X1 - Kivéve, ha az üzenetekből egyik-másik szándékosan zagyvaság - Invariáns tulajdonság, amit megtart ez a módszer: a betűk egymás alattiságát. Ha a nyílt üzenetekben egy adott pozíción ugyanaz a betű X2 volt, akkor a kulcs ugyanannyiadik karakterét adjuk hozzá, így az Y1 eredmény is ugyanaz lesz. - X1, X2 értelmes szövegek. Ha nem ugyanaz a kulcs, egyenletes Y2 eloszlást kapunk. - Annak is van valószínűsége az adott nyelvben, hogy egy adott pozíción milyen betű van. - A két dolog összefügg: betűgyakoriság, és az egymás után következőség - Adott pozícióban A betűből P(A) darab van. Annak a

valószínűsége hogy X1-ben és X2-ben ugyanazon a helyen ugyanaz a betű van. P(A)2 . A . A . Q . Q is mérhető, 2 . N ( PA + + PZ2 ) Tökéletes titkosítás - Ha a nyílt és a rejtett üzenet kölcsönös információja nulla, vagyis semmilyen kapcsolat sincs a kettő között; és ez bizonyítható is. Ilyen a ’one time pad’ módszer λ ( y ) =| x ∈ X , x értelmes ∃k ∈ K , amire E ( x, k ) = y | - - - Meg kell adnunk, hogy a rejtett üzenet hányféle forrásból keletkezhetett, különböző kulcsok felhasználásával. Ha k1kn kulcsokkal megyünk végig, akkor különböző E(x2, k2) állítja elő az y-t. A λ szemszögéből olyan rejtjelrendszer jó, ami az y-okra sok x-et ad meg. Ekkor a Brute Force nehezen használható. - Probléma: egy konkrét y-tól függ. Akkor jó a rejtjelrendszer, ha a legkisebb lambdája is nagy. Ez a függvény nehezen számolható Koordinátarendszerben ábrázolva nagyon változó függvény keletkezik. Akkor nem

jó, ha például egy-egy megfeleltetés van. - Egyértelműségi pont: M0 = log 2 | k | , log 2 | x | − H (ζ ) o Ahol log2|K| a kulcshalmaz elemszáma, log2|x| a nyílt halmaz elemszáma (abc) és H(ξ) a forrásentrópia (a nyelvre jellemző érték) o M0 azt mondja meg, hogy az üzenet elméletileg hány karakterig fejthetetlen. De ez nem azt jelenti, hogy ennél hosszabb már megfejthető. o Pl. Caesar módszer esetén: 26 lehetséges eltolási érték és 2 karakter hosszú üzenet esetén nem garantált a fejthetetlenség. (H(ξ)=13) o Amikor egy betűnek pontosan egy másik felel meg, akkor 26! lehetséges kulcs van. Kiszámolva kb. 230 karakter alatt nem fejthető - Transzpozíciós titkosítás esetén: N 10 50 M0 6,4 70 - Véletlen átkulcsolás módszere esetén: az üzenetnél hosszabb üzenet sem lenne fejthető. (H(ξ)=1,3) 17. oldal, összesen: 37 14. DES (Shannon keverő transzformációja A DES módszer ismertetése és kritikai elemzése.) DES (Data

Encryption System, 1977, IBM) - 56 bites kulcs, 256 kulcsméret - 64 bites üzenet -> 64 bites üzenet - A DES gyorsan számolható, ezért célszámítógépeket készítettek hozzá. Korábban ez volt az előnye, ma ez már hátránynak tekinthető. - Algoritmus (19 lépés): o 1. Felcserélés (a középen kettévágott üzenet 32 bites részeinek felcserélése) o 2. Lavina-hatás (Xleft XOR f(XRi, Ki)) o 3.17 o 18, 19 felcserélés - Az f függvény működése a) 32 bit kiterjesztése 48 bitre b) 48 bit XOR kulcs c) 8 db, egyenként 6 bites részre bontja az üzenetet, s ezeket egy S dobozba vezeti. S-ből 4 bit jön ki d) 8 x 4 bit = 32 bit - Az S doboz működése szorosan összekapcsolódik a kiterjesztéssel, de pontos leírása titkos - 1 millió dolláros célgéppel pár óra alatt törhető - 3DES = 112 bit Produkciós titkosítónak az olyan titkosító eszközöket nevezzük, amelyek kettő vagy több eltérő elvű művelet kombinálásával szolgáltatják

eredményüket. Ezek az algoritmusok nagyobb biztonságot kínálnak, mint műveleteik külön-külön. Ha azonos elvűeket kötünk sorba, előfordulhat, hogy azok egymás hatását kioltják (OTP azonos kulccsal), vagy csak feldolgozási időt, a biztonságot nem növelik. Egyik speciális eset a helyettesítő-keverő hálózat, mely helyettesítéseket (S-doboz) és keveréseket (P-doboz) végez egymás után. A lavinahatás megvalósítását a kiterjesztés lépése biztosítja: ez a bemeneti 32 bitből 48-at készít úgy, hogy 16 kiválasztott bitet lemásol és megdupláz. Ebből következik, hogy ha a függvény bemenetén változás történik, az két helyen is kifejti hatását. A kiválasztott bitek úgy helyezkednek el, hogy egy-egy ilyen duplázott bit kettő S-doboz bemenetére megy. Összefoglalás Maga a szabvány a DES (Data Encryption Standard) nevet viseli; ez a betűszó terjedt el a módszer egészére vonatkozóan annak ellenére, hogy az algoritmusnak a

szabványban más neve van (DEA). Az alapvető elvárások az algoritmussal szemben a következők voltak: Nyújtson magas szintű biztonságot Egyszerű felépítésű, könnyen érthető legyen A biztonság csak a kulcstól függjön, ne az algoritmustól Gazdaságosan alkalmazható legyen elektronikus eszközökben is (hardveres úton) A fentiek tükrében eredetileg kitűzött 128 bites kulcs- és blokkméretet az NSA (National Security Agency) lecsökkenttette 64 bitre sokak szerint azért, hogy az így titkosított üzeneteket az USA nemzetbiztonsági hivatala még fel tudja törni, de más szervezet már ne. A végső kulcsméret további 8 bit ellenőrzési célokra történő lefoglalását követően 56 bit lett, amellyel gyakorlatilag az eredeti kulcstér 99%-át eldobták. 18. oldal, összesen: 37 Az algoritmust 1975-ben hozták nyilvánosságra, s hamarosan nagyon gyors hardveres implementációk is megjelentek, ezért széles körben elterjedt a polgári élet minden

területén. Érdekes, hogy minősített adatok védelmére már akkor sem ajánlotta az amerikai kormányzat. A DES algoritmus működése nagy vonalakban: Az első lépésben a kulcstól függetlenül a 64 bites bemenet bitjeit összekeveri Az iterációs lépések mindegyike két darab 32 bites értékként értelmezi a bementére adott adatot, s ennek megfelelően két darab 32 bites kimenetet ad Az utolsó előtti lépésben a két 32 bites részt felcseréli A maradék 16 lépés működése egységes és mindegyik paramétere, a kulcsból származtatott érték, a körkulcs (Ki) A DES napjainkig a kriptográfusok egyik kedvenc témája. Elvi módot ugyan nem sikerült találni a feltöréshez, azonban 1990-ben az Eli Biham és Adi Shamir által bevezetett differenciális kriptoanalízis segítségével a DES feltöréséhez szükséges 255 brute-force műveletigényét 238 művelet körülire csökkentették [2]. Megjelenésekor a DES ereje pont abban rejlett, hogy

célhardverrel gyorsan megvalósítható volt. Ma már ez hátránynak tekinthető, hiszen elég, ha 1998-ban Michael Wiener által kifejlesztett Deep Crack DES törő célgépre gondolunk. A mai elérhető technológia segítségével a DES egy 1 millió dolláros célgéppel mintegy 1 óra alatt feltörhető. 15. Nyilvános kulcsú titkosítás (Alapelv RSA módszer Hitelesítési lehetőségek Nagy prímszámok.) A nyilvános kulcsú titkosítások alapelvei A nyilvános kulcsú rendszerekben minden résztvevő két kulcsot birtokol: egy nyilvános kulcsot és egy titkos kulcsot. Az üzenetet a titkos kulccsal lehet megfejteni, amennyiben a nyilvános kulccsal kódolták, és fordítva. Ennek tükrében a rejtjelezett üzenetet csak az tudja elolvasni, akinek birtokában van a titkos kulcs – vonatkozik ez a feladóra is, ha visszakapja az eredetileg általa elküldött üzenetet. A nyilvános kulcsú titkosításokat hitelesítésre is használhatjuk, kiaknázva azon

tulajdonságukat, hogy a titkosító algoritmus működik a nyilvános kulccsal, illetve a megfejtő algoritmus is működik a titkos kulccsal. A címzett a következőképpen tudja ellenőrizni az üzenet küldőjét: 1. Küldés előtt a feladó a saját titkos kulcsával kódolja az üzenetet Ezzel olyan átalakítást végez az üzeneten, amire senki más nem képes. 2. A következő lépésben az előbbi eredményt titkosítja a címzett nyilvános kulcsával, ezzel elérve, hogy az üzenet ne utazzon védtelenül. 3. A címzett saját kulcsával és a megfejtő algoritmussal kibontja a csomagot, feloldva ezzel az üzenet védelmét. 4. A kapott eredményt pedig a küldő nyilvános kulcsával alakíthatja olvasható, kódolatlan formára. A fenti folyamat során a feladó biztos lehet abban, hogy az általa elküldött csomagot csak a címzett képes elolvasni, hiszen az mindig védve utazott. A címzett pedig biztos lehet abban, hogy az üzenet valóban a feladótól érkezett,

hiszen a feladó titkos kulcsával kódolt üzenetet egyedül a nyilvános kulcs nyitja. Mivel a publikus kulcsokat egyáltalán nem kell védeni, létrehozhatunk egy nyilvános, telefonkönyvhöz hasonló kulcstárat, amely a résztvevők nyilvános kulcsait tartalmazza (n 19. oldal, összesen: 37 darabot). Így bárki tud üzenetet küldeni a kulcstárban szereplőknek, minden előzetes egyeztetés nélkül. A kulcstárból ugyanezzel a módszerrel juthatunk hozzá a kívánt résztvevő nyilvános kulcsához: a szerver aláírja saját titkos kulcsával a „kulcsot”, mi pedig a szerver nyilvános kulcsával bizonyosodunk meg az üzenet hitelességéről. Ezeket a lekért publikus kulcsokat a helyi gépünkön is tárolhatjuk, egyedül arra kell ügyelnünk, hogy a helyi adatok mindig szinkronban legyenek a szerveren tároltakkal [2]. Az RSA algoritmus elméleti háttere A nyilvános kulcsot használó módszerek gyakran a nagy prímszámok szorzásán, s az így létrejövő

még nagyobb szám prímtényezőkre bontásának nehézségén alapulnak. Az RSA biztonságát is ez a probléma adja. A kis Fermat-tétel kimondja, hogy ha egy a számot egy p prímhatványra emelünk, akkor az eredmény p-vel való osztás utáni maradékaként visszakapjuk az eredeti a számot. Ez természetesen csak akkor működik, ha p nagyobb, mint a, különben az osztás során a-t is elosztanánk, s más maradékot kapnánk. A fenti tétel általánosabb formáját Euler fogalmazta meg, miszerint: a Φ (n ) ≡ 1(mod n ) , ha a és n relatív prímek, azaz nincs más osztójuk, csak és kizárólag az 1. Ha az n helyére prímszámot választunk, akkor egyértelműen adódik a Φ (n ) = n − 1 összefüggés, hiszen egy prímszámhoz minden más szám relatív prím. Prímszámot választani azért is előnyös, mivel ilyen esetben minden n-nél kisebb számra működik a tétel. Ahhoz azonban, hogy több felhasználó számára is lehetővé váljon a rendszer

használata, n-t két prímszám szorzataként érdemes definiálni (p és q). Így az új modulus n = pq, a kitevő pedig ed = k(p-1)(q-1)+1. Ekkor azt kapjuk, hogy a ed ≡ a mod pq , ahol ed ≡ 1 mod( p − 1)(q − 1) . Legyen a nyilvános kulcs az (e, n) számpáros, a titkos kulcs pedig a (d, n) páros. Ekkor a támadónak Ф(n) kiszámolásához n prímtényezős felbontására lenne szüksége, azaz p-re és qra. Mi azonban ezt a két számot úgy választjuk meg, hogy n hatalmas legyen, majd eldobjuk az előállításhoz szükséges számokat. A tudomány mai állása szerint egy ekkora szám prímtényezős felbontása reménytelen feladat [2]. Az RSA algoritmus A titkosításhoz az üzenetet először számokká alakítjuk úgy, hogy a számok (blokkok) mindegyike kisebb legyen, mint n. Ezt például úgy tehetjük meg, hogy minden karakter helyére az ASCII kódját írjuk, majd átszámítjuk egy másik számrendszerbe. Az így nyert üzenetdarabokat a képletünkben az a

helyére helyettesítjük be, majd az egyes m számokból (üzenetekből) az M = m e mod n képlettel előállítjuk a rejtjelezett M üzenetet, ami az m = M d mod n képlet alapján lehet megfejteni. 20. oldal, összesen: 37 Az algoritmus elnevezése a tervezők nevének első betűit őrzi: Rivest, Shamir, Adleman. Az RSA algoritmust 1977-ben szabadalmaztatták, azonban ez a védelem 2000-ben lejárt, így bárki liszenszdíj-mentesen készíthet RSA algoritmuson alapuló hardver- vagy szoftvereszközt. A kulcsgenerálás lépései tehát a következők: 1.) Véletlenszerűen válasszunk két elég nagy, legalább 100 jegyű prímszámot Legyen ez P és Q. 2.) Ekkor N = PQ és Ф(n) = (P-1)(Q-1) 3.) Válasszunk egy véletlen E számot úgy, hogy relatív prím legyen Ф(n)-re 4.) Keressünk egy olyan D-t, amelyre ED = 1 mod Ф(n) teljesül Egy példán keresztül illusztrálva pedig: 1.) Legyen ez P = 17 és Q = 23 2.) Ekkor N = PQ = 391 és Ф(n) = (P-1)(Q-1) = 352 3.) Legyen

E = 21 Ekkor (21, 352) = 1 teljesül 4.) Legyen D = 285, mert 285 x 21 mod 352 = 1 5.) Az elküldendő üzenet legyen „T”, amelynek az ASCII kódja 84 Ez kisebb, mint 391, ezért megfelelő. 6.) A titkosított üzenet így: 8421 mod 391 = 135 Ezt kell elküldeni 7.) A fogadó oldalon pedig a 135285 mod 391 = 84 számítással áll elő az eredeti üzenet A példában használt értékek a gyakorlatban természetesen nem alkalmazhatók, mivel az N számot még fejben is gyorsan prímtényezőkre lehet bontani. Ezután pedig előállítható Ф(n), majd inverzszámítással D is. Ha azonban két többszáz-jegyű prímszámot választunk, akkor az előálló N prímtényezős felbontása a mai eszközökkel lehetetlen feladat [2]. Az RSA algoritmus megfelelő paraméterezése Az RSA a DES-hez hasonló blokkos titkosító algoritmus, a blokkok méretét n határozza meg. Az algoritmusban E és D szerepe felcserélhető, ezért az RSA alkalmas digitális aláírásra is. A gyakorlati

alkalmazások során jelenleg a 2048-4096 bites modulosokat tekintjük biztonságosnak. Az RSA kulcsainak hosszát mindig a modulus n hossza határozza meg, hiszen n adja meg a feltörés bonyolultságát. A faktorizáció területén elért újabb eredmények (elliptikus görbe faktorizáció) miatt ajánlott közel azonos méretű prímszámokat felhasználni a kulcsok generálásához: például egy 1024 bites modulust célszerű két 512 bites prím alapján kiszámolni. Azonban vigyázni kell arra is, hogy a két szám ne kerüljön túl közel egymáshoz [2]. Az RSA algoritmus elleni támadások hatékonyságát sokak szerint növelheti az, ha a kulcs speciális tulajdonságokkal rendelkezik. Ilyen feltétel lehet, hogy a 23 bit a kulcsban „0”, vagy az utolsó 5 bit „1’ értékű legyen. Ezeket a kulcsokat gyenge kulcsoknak is nevezik (weak key) A támadó ekkor viszont egy feltételezésen alapuló megoldással próbálkozik, amely könnyen kudarcba fulladhat. Számos

vizsgálat eredményeképpen a prímeknek (P és Q) a következő tulajdonságokkal kell rendelkezniük akkor, ha erősek akarnak lenni (strong key) [4]: 1.) A választott prím (R) nagy, legalább 400-500 bit hosszú 2.) R - 1 legnagyobb prímosztója (R–) nagy 3.) R– - 1 legnagyobb prímosztója (R– –) nagy 4.) R + 1 legnagyobb prímosztója nagy A fő érv az erős prímek használatára Pollard faktorizáló algoritmusa volt, ezért az 1970-es évektől jó darabig a gyenge prímekből előállított RSA kulcsokat gyenge kulcsoknak 21. oldal, összesen: 37 tekintették, használatukat nem javasolták. 1985-ben azonban Lenstra kidolgozott egy olyan, elliptikus görbén alakuló eljárást, amely erős prímek használata esetén is ugyanolyan hatékony, egyedül a prímszámok közel egyforma hosszúsága okoz neki problémát. Rivest és Silverman mindezt egy 1998-ban publikált közös tanulmányukban foglalták össze [4]. Egyúttal megmutatták, hogy az erős

prímek használata felesleges, mert alkalmazásuk véd ugyan bizonyos faktorizálási módszerek és az iteratív támadás ellen, de nem véd azok általánosítása, Lenstra módszere ellen. Használatuk tehát nem baj, de nem is szükséges [2] Az RSA feltörése Az RSA feltöréséhez nem érdemes a brute-force módszerrel nekifogni, mivel már az elavultnak tekinthető 512 bites kulcsméret is kellő védelmet nyújt ellene. Ugyanezt a számot prímtényezőkre bontani azonban lényegesen könnyebb – de szintén nagyon erőforrás-igényes feladat. Az idők folyamán az egyes új módszerek és egyre gyorsuló számítógépek jelentős haladást tettek lehetővé a faktorizálás terén. Érdekes, hogy a feltört RSA kulcsok hossza és az eltelt évek között nagyjából lineáris kapcsolat van, ami valószínűleg annak köszönhető, hogy a számítási teljesítmény és az egyre nagyobb számok faktorizálásának erőforrás-igénye egyaránt exponenciálisan növekszik

[2]. Az RSA Laboratories által meghirdetett RSA Factoring Challenge keretében 2005. május 10-én vált nyilvánossá a legutóbbi, 200 digit hosszú szám sikeres faktorizálása [5]. Íme a versengés tárgya, a 200 digit hosszú RSA kulcs: 2799783391 1221327870 8294676387 2260162107 0446786955 4285375600 0992932612 8400107609 3456710529 5536085606 1822351910 9513657886 3710595448 2006576775 0985805576 1357909873 4950144178 8631789462 9518723786 9221823983 A fenti szám lényegesen kisebb a legnagyobb ismert prímszámtól, amely 9 152 052 digit hosszú, s a neve Mersenne-prím (M43) [1]. Ebből is látszik, hogy egy számról lényegesen könnyebb eldönteni, hogy prím-e, mint faktorizálni. [5] Bruce Schneier az egyik Cryptogram hírlevelében arról ír, hogy az 1024 bites RSA kulcsok egy 1 milliárd dolláros Bernstein-féle architektúrán alapuló célgéppel már néhány perc alatt faktorizálhatók. Ez nem is tűnik olyan horribilis összegnek annak fényében, hogy az

USA által rendszeresen fellőtt Sigint műholdak ára a 2 milliárd dollárhoz közelít. Ha Bernstein gépét megépítik, az összes népszerű protokoll, amely ma leginkább 1024 bites RSA kulcsokat használ (HTTPS, SSH, IPsec, PGP), mind kompromittálódik. A legtöbb neves kriptográfus szerint a fentiek miatt érdemes a rendszereinket átállítani a 2048 bites kulcsok használatára, hiszen nem tudhatjuk, hogy az NSA megépíttette-e már a Bernstein-féle gépet. A digitális szatellit-adásokat nem véletlenül védik már 4096 bites RSA kulcsok Európában [6] Hibrid kriptorendszerek A nyilvános kulcsú algoritmusok gyakorlati alkalmazása során nem az egész üzenetet kódolják például az RSA-val, mert nagyon lassú lenne. A hagyományos szimmetrikus kulcsú algoritmusok hardvermegoldásban átlagosan ezerszer gyorsabbak, de szoftveres megoldás esetén is legalább százszor [7]. Ezért az aszimmetrikus titkosítások nem alkalmasak hosszú üzenetek titkosítására.

A szokásos eljárás az, hogy az üzenetet egy gyorsabb, titkos kulcsú algoritmussal, az ehhez használt kulcsot pedig nyilvános kulcsú módszerrel titkosítják, és a kettőt együtt küldik el. Ez az egyszer használt kulcs a viszonykulcs (session key) Így dolgozik a PGP is: az RSA segítségével titkosítja a szimmetrikus kulcsot, majd a tömörített üzenet tényleges kódolása az IDEA/CAST algoritmussal történik. A tömörítés nemcsak az átviteli 22. oldal, összesen: 37 időt csökkenti, de lényegesen megnehezíti a mintakeresést, növeli az entrópiát és elrejti a nyílt szöveg jellemző tulajdonságait. A fenti borítékolásnak (enveloping) is nevezett módszernek azonban van egy igen nagy hátránya: a nyilvános kulcs hosszából származó előny, ami eddig a brute-force alkalmazását megakadályozta, elveszik. A támadó egyszerűen úgy kezeli a titkosított üzenetet, mintha az egész szimmetrikus kulcsú algoritmussal lenne kódolva, hiszen itt

most a nyilvános kulcsú algoritmus csak a kulcscserét segíti [2]. Mindezek fényében a hibrid kriptorendszerek biztonságát az alkalmazott szimmetrikus kulcsú algoritmus, és az aszimmetrikus kulcsú algoritmus együttesen határozzák meg. Az RSA algoritmus implementációját befolyásoló tényezők Az RSA algoritmus alapját a hatalmas prímszámok adják, így nyilvánvaló a szükséglet ilyen prímek előállítására vonatkozóan. Azonban jelenleg nem áll rendelkezésünkre olyan módszer, amely közvetlen módon lehetne meghatározni egy prímszámot, ezért az egyetlen esélyünk, hogy véletlenszerűen generálunk egy nagy számot, majd megnézzük, hogy prím-e. Ha viszont egy tetszőleges számról kell eldöntenünk, hogy prím-e, akkor egyetlen teljes biztonságos jelentő módszer adódik: végig kell néznünk az 1 és a szám négyzetgyöke közötti egész számok mindegyikét, hogy nem-e osztója a számunknak. Ezt a sorozatos osztást természetesen nem

tudjuk elvégezni, még az erasztothenészi szita segítségével sem, hiszen pontosan ennek megakadályozása a célja a hatalmas prímek alkalmazásának. Az egyetlen megoldásként a prímteszt algoritmusok kínálkoznak, amelyek tetszőleges biztonságú becslést képesek szolgáltatni arra vonatkozóan, hogy a vizsgált szám prím-e. Ilyen teszt a Fermat-teszt és a Solovay-Strassen-teszt, de jelenleg a legbiztosabb a Miller-Rabinteszt. Ha ezen a teszten a vizsgált szám százszor átmegy, akkor a szám már kellően összetett, ha nem is biztosan prím [2]. Bármelyik tesztet választjuk is, mindenképpen hatalmas számokon kell aritmetikai műveleteket elvégeznünk, ami természetesen a jelenleg elterjedt 32 bites, általános célú processzorokkal nem oldható meg adattípus-szinten. Így, ha ezen algoritmusok megvalósítására adjuk a fejünket, kénytelenek vagyunk egy ALU-t (Arithmetical Logical Unit) készíteni az általunk alkalmazott programozási nyelven, amely

egy karaktersorozatot számként értelmezve blokkosan képes a műveletek elvégzésére. Olyan ez, mint az általános iskolai matematika: a nagy számok összeadásához kisebb számokra kell bontanunk azokat, helyértékenként összeadnunk, majd a maradékot (átvitelt) kezelnünk. Összefoglalás Nyilvános kulcsú titkosítások - Alapötlet: használjunk két kulcsot. Az egyik a nyilvános (KN), a másik a titkos kulcs (KT). - Létrehozunk egy nyilvános kulcstárat, ami a nyilvános kulcsokat és tulajdonosaikat tartalmazza: [A, KN] [B, KN]. Ez csak olvasható lehet; illetve hatékonyan védeni kell. - Módszer: a megfejtéshez és a titkosításhoz különböző kulcsra van szükség (Encryption, Decryption) - Probléma: B nem tudja eldönteni, hogy az üzenetet kitől érkezett, mert bárki kikeresheti a nyilvános kulcsot a kulcstárból, és ezzel küldhet üzenetet B-nek. - Digitális aláírás: a titkos kulcsban elhelyezünk egy hitelesítésre alkalmas lenyomatot. A

hitelesség igazolása: A B a titkos kulcsot csak A tudja, ezért biztos, hogy az üzenet E ( D( K TA , x), K NA ) ⇒ tőle érkezett. Ha az X előáll a képlettel, akkor az üzenet A- 23. oldal, összesen: 37 x tól jött (kivéve, ha ellopták a titkos kulcsát a gépéről). A nyilvános kulcsokat ki kell cserélni, a titkos kulcs viszont a gépen maradhat. A B A : E ( D( x, K TA ), K BN ) [ B B : B D( E ( D( x, K TA ), K N ), K TB ), K sp ] Rivest-Shamir-Adleman (RSA) titkosítás Lépései: 1. Kulcsválasztás a. Véletlenszerűen választunk P1, P2 prímszámokat, amelyek elég nagyok (~100+ jegyű) b. M = P1 * P2 és O(m)=(P1-1)(P2-1). Válasszunk egy véletlen e számot, ami relatív prím a [(P1-1), (P2-1)] pároshoz. c. e * d = 1 mod O(m), ahol 1 ≤ d ≤ O(m) 2. Központi nyilvántartás a. Betesszük KN(m,e)-t a nyilvános kulcstárba b. Az összes többit is: d, m, P1, P2, O(m) 3. Rejtjelező algoritmus a. A -> B(eB, mB) b. Előkódolja az üzenetet, Pl

ASCII kódok segítségével betűkből számokat csinál, ezeket pedig átszámítja egy másik számrendszerbe c. A rejtjelezést az előkódolt számokon végzi el d. Kiszámolja a számokat, és valamilyen módszerrel egymás mellé írva kapja meg az üzenetet. eB y = EB ( x) = x mod mB 4. Dekódolás a. B kap egy rejtjelezett üzenetet, amely 0 mB-1 számok sorozata (y1 y2) b. Ezen számok sorozatán történik a dekódolás c. x = DB ( y ) = y d B mod mB y d B = x eB ⋅d B = x Φ ( m )⋅h+1 = x d. (x1 xn) az előre megállapított módszerrel visszaalakítjuk, betűk sorozatává Törése: - A titkosság azon alapul, hogy m és e birtokában a támadó nem tudja kiszámolni O(m)-et, és ebből következően dB-t sem. Pl. ha m=15, akkor 15 = 3 x 5, a törés kész Töréséhez a kétszáz számjegyű szám prímtényezős felbontását kéne meghatározni. (prímfaktorizáció) Gyakorlati titkosságot valósít meg Többszáz jegyű prímszám előállítása -

Erasztothenészi szita: sorban felírjuk a számokat egymás után, majd a prímek többszöröseit kihúzzuk a listából. - Hagyományos módszer: n -ig vizsgáljuk, hogy n osztható-e prímszámokkal. Amint találunk egy prím osztót, megállunk: a szám nem prím. 24. oldal, összesen: 37 - A módszer nem igényli a valódi prímszámok használatát, de ettől csak biztonságosabb. Elég, ha a használt számok nagy valószínűséggel prímek n -ig vizsgálni? Miért elég N = A⋅ B A 〉 N B 〉 N A ⋅ B 〉 N ⇒ ellentmondás A Fermat-tétel b s −1 ≡ 1 mod s {50% az esélye, hogy s prím} b s −1 ≡/ 1 mod s {s biztosan nem prím !} Fermat − próba A Fermat − tétel k − szori alkalmazása b1  bn számokra, amíg az L valószínű ség eléggé kicsi nem lesz. L= 1 2k (k = 10 esetén L = 0,01) Valószínűségi prímtesztek: - Probléma: vannak olyan pszeudoprímek, amelyek teljesítik a próbát, mégsem prímek. - A b szám generálása:

válasszunk véletlenszerűen egy páratlan számot, amely 100 jegyű! a) végezzük el rajta a Fermat-próbát! b) két eredményünk lehet: kiállja vagy nem a próbát. Ha nem, akkor pl hozzáadunk 2-t. Megjegyzések: - Meddig lehet hozzáadni sorozatosan 2-t? Lehet egy olyan hézag, ahol jó sokáig nem találunk számot. Tetszőlegesen nagy hézag elképzelhető a számok között - M   N  Képlet: kb. (N / lnN) számú prím van n-ig Ha   > 1 , akkor nagy − - valószínűséggel lesz prím a hézagban. (Kb 100-200 szám átlagosan) alatt fel kell bukkannia egy prímnek a hézagban. Ha 140 próbálkozás után nincs prím, válasszunk egy teljesen másik számot. 2 Nem igényel nagy számítási teljesítményt 8 =  2 2 2  3db szorzás 100 2   Hatványozás: 2 = 99db szorzás (n-1)   Hatékonyan: szorzásokra és négyzetre emelésekre 7 3 2 = 2 ⋅ 2 ⋅ 23 5db szorzás vezetjük vissza a hatványozást. Nagy számokkal

való munka: a) Akkora méretekre bontjuk a számunkat, amelyekkel az aritmetikai egységünk még tud dolgozni, majd az átviteleket kezeljük (ALU) -  ln M   ln N  ( ) 16. Adatbázis szerverek szerveroldali programozása (Tárolt eljárások, triggerek használata. Adatok feldolgozása kurzorok segítségével) Tárolt eljárások létrehozása Általában: CREATE PROCEDURE <eljárásnév> [@param név típus] [WITH {RECOMPILE, ENCRYPTION}] AS {SQL utasítások | blokk} 25. oldal, összesen: 37 Példa: CREATE PROCEDURE Vkl (@vk VARCHAR(50)) AS SELECT nev FROM Hallgato WHERE nev LIKE ’/’ + @vk Futtatás: EXEC Vkl(30) Függvények Általában: CREATE FUNCTION() RETURNS típus érték BEGIN RETURN ertek END //ilyen típusú a visszatérési Kurzorok Általában: DECLARE nev [INSENSITIVE] [SCROLL] CURSOR FOR lekerdezes [FOR READ ONLY] [FOR UPDATE OF mező1, mező2, ] INSENSITIVE: érzéketlen arra, ha megváltoznak az adatok, miközben működik SCROLL:

engedélyezi az előre-hátra történő lépkedést Megnyitás: OPEN nev Adatok beolvasása: FETCH [NEXT | PRIOR | FIRST | LAST | RELATIVE n | ABSOLUTE n] FROM nev INTO változó1, változó2, @@FETCH STATUS - Ha 0  sikeres - Ha -1  túlszaladás - Ha -2  hiba (törölték) Kurzor lezárása: CLOSE nev 26. oldal, összesen: 37 Kurzor felszabadítása: DEALLOCATE nev Teljes példa: DECLARE @alma VARCHAR(50) FETCH NEXT FROM hkurzor INTO @alma WHILE @@FETCH STATUS = 0 BEGIN PRINT @alma UPDATE Hallgato SET nev=’1’ + @alma WHERE nev = @alma //vagy WHERE CURRENT OF hkurzor FETCH NEXT FROM hkurzor INTO @alma END CLOSE hkurzor DEALLOCATE hkurzor Példa: IF @alma LIKE ’%Béla’ DELETE FROM Hallgato WHERE CURRENT OF hkurzor Triggerek Trigger Megszorítás Meghatározott események bekövetkezése Mindig él esetén Tetszőleges művelet végrehajtható Visszautasítja a tranzakciót, ha megsérti a feltételt Szintaxis CREATE TRIGGER Név ON [táblanév | nézetnév] [WITH

ENCRYPTION] [FOR ALTER | INSTEAD] [INSERT, UPDATE] AS [IF UPDATE(mezőnév) AND | OR UPDATE(mező)] -- sql parancsok sorozata -- a deleted és az inserted táblák tartalmazzák a törölt / új adatokat Példa: ha a ’Zoli’ nevű hallgató ’5’-öst kap, akkor ROLLBACK Hallgato(nev, szul, anyja) 27. oldal, összesen: 37 Jegyek(nev, jegy) a.) CREATE TRIGGER Szivat ON Jegyek FOR INSERT, UPDATE AS IF EXITS ( SELECT * FROM inserted WHERE nev=’Zoli’ AND jegy=5) ROLLBACK --az egész tranzakciót visszavonja, bármi is volt még benne b.) CREATE TRIGGER Szivat2 ON Jegyek FOR INSERT AS UPDATE Jegyek SET jegy=1 WHERE nev=’Zoli’ AND jegy=1 c.) CREATE TRIGGER Szivat3 ON Jegyek INSTEAD OF INSERT AS INSERT INTO Jegyek SELECT nev, jegy FROM inserted WHERE NOT (nev=’Zoli’ AND jegy=’5’) d.) CREATE TRIGGER helytakarekos ON Jegyek FOR INSERT, UPDATE AS DECLARE @nev CHAR(50), @ee INT DECLARE a CURSOR FOR SELECT nev FROM inserted WHERE jegy=1 OPEN a FETCH a INTO @nev WHILE

@@FETCH STATUS=0 SET @ee = ( SELECT COUNT(*) FROM jegyek WHERE nev=@nev AND jegy=1) IF (@ee > 3) OR (@ee=2 AND @nev=’Zoli’) INSERT INTO Torlendo (nev, egyesek szama) VALUES (@nev, GETDATE(), @ee) FETCH a INTO @nev END CLOSE DEALLOCATE a 28. oldal, összesen: 37 idopont, 17. SQL optimalizálás (Költségalapú működésének bemutatása, elemzése.) és szabályalapú optimalizáció Lekérdezés-optimalizálók - szabályalapú: a lekérdezés formája alapján dönti el, hogyan futtatja le, az adatok figyelembe vétele nélkül - költségalapú: az adatbázisra vonatkozó statisztikák szerint próbál optimalizálni. A plusz információk miatt hatékonyabb. Gyakran jobban optimalizál, mint az ember Eszközei: 1. a táblák összekapcsolásának sorrendje 2. használjon-e indexeket, hasítófüggvényeket 3. mely táblákat töltse be a memóriába A B - 1 millió sor 5 sor - Optimalizálási tippek A.x = Bx szabályalapú: a megadott sorrendben végzi el

az összehasonlítást. A elemein megy végig (lassú) költségalapú: felismeri, hogy B kisebb. B elemein megy végig (gyors) 1. A konstansokat előre számítsuk ki -- nem használ indexeket, mert bonyolult matematikai számításoknak hiszi az alábbiakat SELECT WHERE a > sin(90) * 5 / 2 2. A logikai kifejezéseket egyszerűsítsük a DeMorgan azonosságoknak megfelelően NOT (A=1 AND B=2) helyett A <> 1 OR B <> 2 3. Logikai kifejezések sorrendje az AND operátor használata során -- célszerű előre írni azt a kifejezést, amely nagyobb valószínűséggel hamis, így nem kell megvizsgálni a második kifejezést, ha az első hamis. (a leginkább megszorító feltétel legyen az első) SELECT WHERE atlag = 5 AND nev = ’Benjamin’ 4. Logikai kifejezések sorrendje az OR operátor használata során -- célszerű előre írni azt a kifejezést, amelyik a legnagyobb valószínűséggel igaz, a többit utána pedig csökkenő sorrendben. Ugyanez igaz az IN

kapcsolatra is: IN (5,4,3,2,1) A or B or C 29. oldal, összesen: 37 5. Logikai kifejezések kiértékelési sorrendje -- a leggyorsabban kifejthető legyen elöl, a leglassabb lekérdezés pedig leghátul SELECT nev FROM Hallgatok WHERE ( SELECT AVG(jegy) FROM Jegyek WHERE hnev = nev) = 5 AND Nev LIKE ’%Benjamin’ 5. A BETWEENIN operátor --Sebesség szerint növekvő sorrendben: WHERE jegy >= 4 AND jegy <= 5 IN (4,5) jegy BETWEEN 4 AND 5 Adatok beolvasásának módja a táblákból 1. Folytonos olvasás az adatok (rekordok) fizikai sorrendjében (blokkokat olvas be) akkor hatékony, ha a sok egymás mellett lévő adatot kell beolvasnunk 2. Indexelt beolvasás nem blokkokat, hanem egyetlen rekordot olvas be akkor hatékony, ha össze-vissza lévő elemeket kell beolvasni fűzött index: ha az indexek szerint fizikailag rendezett a fájl 3. Hasító függvények használata Egyedi indexek, pl. növekményes index (auto increment) Tökéletes hasítófüggvény: egyenletes

leképezés, kevés rés Egyéb hasítófüggvény: pl. csak körülbelül határozza meg a keresett elem helyét 4. Bitmap indexek használata BITMAP INDEX Példa: TÁBLA Név Béla Józsi Sanyi Laci Béla Sanyi Jegy 1 2 5 3 2 5 Sanyi-e vagy? 0 0 1 0 0 1 1-esed-e van? 1 0 0 0 0 0 5-ösöd-e van? 0 0 1 0 0 1 Indexek használata 30. oldal, összesen: 37 WHERE nev=’Sanyi’ AND jegy=5 - - AND kapcsolatot vizsgálunk a sorokra a következő bitmintával: 1 0 1 Ahol az eredmény igaz, ott egy keresett elem található WHERE T1.a = T2b 1. egyik táblán sincs index 2. csak A-n van index 3. csak B-n van index 4. mindkét táblán van index 5. A és B azonos indexben szerepel Az indexhasználat kikényszerítése 1. NULL értékek ne legyenek a lekérdezés eredményében (és a táblákban is) -- nem használ indexeket WHERE nev IS NOT NULL -- használ indexeket WHERE nev > ’AA’ 2. A nemegyenlőség vizsgálata --sorról sorra végigmegy, mert a nemJózsi sűrűbben

fordul elő WHERE nev <> ’Józsi’ -- használ indexeket WHERE (nev < ’Józsi’) OR (nev > ’Józsi’) 3. Összesítő függvények a.) --nem használ indexet SELECT COUNT(*) --ezzel az egy mezővel dolgozik, de ha van index, akkor azzal SELECT COUNT(neptunkod) b.) --nem használ indexeket, mert túl bonyolultnak ítéli a lekérdezést SELECT MIN(adat), MAX(adat) --használ indexeket SELECT MIN(adat) SELECT MAX(adat) c.) --HAVING helyett WHERE SELECT nev, AVG(szam) FROM Sz GROUP BY nev HAVING nev LIKE ’%Béla’ SELECT nev, AVG(szam) FROM Sz 31. oldal, összesen: 37 WHERE nev=’%Béla’ (GROUP BY nev) -- kötelező, de nincs plusz hatása d.) Urban Legend -- Tévhit: A SELECT COUNT(*) megoldásnál gyorsabb a SELECT SUM(1) 4. LIKE vs INDEX -- nem használ indexeket SELECT nev FROM Oktato WHERE szoba LIKE ’3%’ --használ indexeket, ha a szobaszámok háromjegyűek WHERE szoba >= ’300’ OR szoba <= ’399’ 5. Kifejezésekben ne használjunk

indexelt mezőt -- a hatarido indexelt mező, ne legyen azon az oldalon művelet WHERE hatarido + 5 < GETDATE helyett WHERE hatarido < GETDATE – 5 6. Indexválasztás --alaphelyzet SELECT * FROM T1, T2 WHERE T1.x = T2x --kikényszeríti az első index használatát SELECT * FROM T1, T2 WHERE T1.x > 0 AND T1x = T2x Felesleges indexek elhagyása – az index használat elkerülése Ne használjunk feleslegesen indexeket, mert: - az adatok módosítása lassabb lesz, mert az indexeket is módosítani kell - ha mindkét mezőn van index, kiveszi a barnákat, majd az 5-ösöket, s ezeknek veszi a metszetét. Lassabb, mintha csak az egyiken lenne index WHERE hajszin = ’barna’ AND atlag = 5 - a barnára ne használjon indexet (a matematikai művelet miatt): WHERE hajszin+’’ = ’barna’ Tábla-összekapcsolások, allekérdezések optimalizálása 1. Összekapcsolási feltétel megadása a. tranzitivitás 32. oldal, összesen: 37 WHERE A.x = Bx AND Ax = y b.

tranzitivitás WHERE A.x = y AND Bx = y Lépésszámok alakulása, ha A: 100-ból 10db x, és ha B:100-ból 5db x: - összekapcsolás + szűrés: 100 x 100 = 10.000 sor - szűrés + összekapcsolás: 10 x 100 = 1.000 sor - csak szűrés: 10 x 5 = 50 sor 2. Plusz információk felhasználása (A-ban kevesebb adat van) a. WHERE A.x = By AND By = Cz b. WHERE A.x = By AND Ax = Cz c. ha nem tudjuk, hogy melyikben van kevesebb adat WHERE A.x = By AND Ax = Cz AND By = Cz 3. Tábla-összekapcsolás vagy allekérdezés? a. SELECT nev, anyja FROM Hallgato WHERE nev IN (SELECT nev FROM Jegyek WHERE atlag=1) b. hátránya: rendezi a két táblát SELECT nev, anyja FROM Hallgato, Jegyek WHERE Hallgato.nev = Jegyeknev AND atlag=1 c. SELECT nev, anyja FROM Hallgato WHERE EXISTS ( SELECT nev FROM Jegyek WHERE Hallgato.nev = Jegyeknev atlag=1) AND 4. Rendezések elkerülése - Összekapcsolás - SELECT DISTINCT: ne használjuk - UNION, INTERSECT, EXACT a. Mely tankörökben van Béla nevű hallgató?

SELECT DISTINCT tankor FROM Tankor JOIN Hallgato ON (Tankor.szam = Hallgatoszam) WHERE nev LIKE ’%Béla’ b. Gyorsabb megoldás (egy rendezést megúszunk) SELECT tankor FROM Tankor WHERE EXISTS ( SELECT * FROM Hallgato WHERE Tankor.szam = Hallgatoszam AND nev LIKE ’%Béla’) 33. oldal, összesen: 37 18. Adatbázisok szinkronizációja (Adatbázisok összekapcsolásának módjai Szerepek, feladatok. Szinkronizációs eljárások) Elosztott adatbázisok kezelése Az elosztott adatbázisok több gépen helyezkednek el. Oka: - teljesítménynövelés egyszerűbb backup (másik szerver beállítása a döglött helyett) Formái: - azonnali szinkronizáció (online, valósidejű) [ritka] - laza integráció / késleltetett szinkronizáció (kellően valósidejű) o adott időközönként történik a szinkronizáció o hibatűrő: ha a távoli gép túlterhelt, a szinkronizációt el lehet halasztani o jól illeszkedik a lassú kapcsolatokhoz o a távoli gépen nem időszerű

adatok is megjelenhetnek (még nem volt frissítés) 34. oldal, összesen: 37 Megvalósítás: 1. Adattöbbszörözés Működése: - Az összes adatbázis ugyanazokat az adatokat tartalmazza - Az adatlekérés attól a szervertől történik, amelyik éppen szabad ADB . ADB1 ADBn webszerver 2. Adatok megosztása Központi TESCO ADB [100e] Budaörsi TESCO ADB [20e] . Pesti úti TESCO ADB [16e] Működése: - Az egyes helyeken különböző adatokra van szükség - A központi szerveren intelligens ügynök működik - Ha az alárendelt adatbázisokban változás történik, akkor bizonyos időközönként megtörténik a szinkronizáció (éjszaka) - Akkor előnyös, ha nincs mindig szükség a legfrissebb adatokra a központban - Hibatűrő, elosztott rendszer Komponensei: 1. Információkiadás (publisher) - Tárgya: a. teljes adatbázis b. teljes tábla c. vertikális és horizontális partíciók (sorok, oszlopok, mezők) d. nézettábla - jellemzői: a. bizonyos

időközönként vagy konkrét időpontban történik b. például minden éjszaka, vagy szerverterheléstől függően 2. Feliratkozó-kezelés (subscriber) a. Jogosultságok b. Háttérbeli folyamatok - naplózást figyeli process - adatterjesztést végző process 3. Terjesztés (distributor) a. helyi vagy távoli (topológia) b. konfliktuskezelő (egy időben egy helyen egy adat módosulhat) c. csak adatokat vagy a séma változásait is érinti? 35. oldal, összesen: 37 Lehetséges topológiák: 1. Központi információkiadó - kiegészíthető kétirányú kapcsolattal publisher distributor subscriber 2. Központi előfizető publisher distributor publisher publisher distributor 3. Központi információ-kiadó távoli adatterjesztéssel (adattárház) publisher distributor subscriber 4. Információ-kiadó előfizető (elosztott adattárház) publisher distributor dual mode distributor subscriber subscriber 5.

Egyesítő többszörözés - a módosításokat felküldik az előfizetők a szervernek - a szerver pedig leküldi azokat a többi előfizetőnek 36. oldal, összesen: 37 subscriber publisher distributor subscriber subscriber 37. oldal, összesen: 37