Informatika | Informatikai biztonság » Fábián Zoltán - Haladó algoritmusok

1. oldal, összesen: 13 Haladó algoritmusok By UFO (http://doksi.hu) BMF-NIK, IV. félév (2005) 1. Gráfok 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 5 - 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 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 0 1 0 0 1 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 2. oldal, összesen: 13 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 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 3. oldal, összesen: 13 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ő; //most hagyjuk el idő := idő + 1 eljárás vége 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 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. 4. oldal, összesen: 13 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ú élből A 2 D 1 E (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 külön B F halmazból valók, ezért nem alakul ki kör) 7 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) 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 1. Induljunk O-ból (tetszőleges) D O: OA=4 {O,A} A 7 2. O: OC=5 1 5 6 {O,A,B} A: AB=1 4 3. O: OC=5 6 O B T A: AD=7 1 B: BC=2 {O,A,B,C} 2 5 4 8 4. A: AD=7 {O,A,B,C,E} B: BE=4 E C: CE=5 C 5 5. A: AD=7 B: BD=5 E: ED=1 {O,A,B,C,D,E} {O,A,B,C,D,E,T} 6. D: DT=6 2 E: ET=8 5. oldal, összesen: 13 2. Titkosítások Cél: az adatok

védelme o Területei: pénzügy, Internet, levelezés (a tartalomtól függően) o Tárgya: kutatási eredmények, személyes adatok, vizsgakérdések, ügynöklista o Különböző szintű titkosításokra van szükség; de ma már mindenki elérheti a legfejlettebb titkosítási módszereket is o ami nem nyilvános, vagyis nem használható mások számára is, azt nem fogadjuk el, mivel nem állta ki a feltörések próbáját (pénzért mindent) Módszerek Szteganográfia, avagy a Rabszolga-módszer - Egy rabszolga segítségével A és B pontok között valósítunk meg kommunikációt. A rabszolga haját leborotváljuk, a fejbőrére applikáljuk az üzenetet, majd egy kis idő elteltével (minek úgy sietni), amikor már a haja eléggé megnőtt, elküldjük B-nek. A vevő leborotválja (a haját), s ezzel máris dekódolta az üzenetet. (Encryption - Decryption) - Általánosságban: a titkosság az üzenethordozón és a módszeren múlik Törése (lehallgatása): - C

elkaphatja az üzenethordozót, és a módszer ismeretében lehallgatja az üzenetet - Ha sok ember megy ugyanazzal az üzenettel, egyet észrevétlenül le lehet lehallgatni, hiszen a vevő nem tudja, hogy eredetileg hány rabszolgát küldtek - Jobb sokat küldeni úgy, hogy csak egy hordozza az üzenetet - Tipikus példa: Egy bmp fájlban az intenzitásbitek megváltoztatása, ami szemmel nem látható mértékű változást eredményez, azonban mégis információt hordoz. Az eredmény pedig különbségképzéssel állítható elő - Megjegyzés: az Internet forgalmának legnagyobb részét a multimédiás anyagok jelentik Nyílt üzenet titkosítása – a magánhangzók cseréje - A betűk és pl. a pontok száma között egyértelmű megfeleltetés van - Egy magyar nyelvű szövegből, ha a fele betűt eltávolítjuk, még érthető marad az üzenet. A redundancia csökkentésével a titkosított üzenet egyre nehezebben dekódolhatóvá válik BALKÉZ Nyílt üzenet

titkosítása – Őrtornyok JOBBKÉZ - A kommunikáló őrtornyok tetején egy-egy ember található, akik 1 2 3 4 két fáklya segítségével üzennek egymásnak. A kódolást egy 1 A B C D mátrix jelenti. Pl Balkéz-Jobbkéz sorrenddel: Fekalofil = 2-2, 22 E F G H 1, 3-3 3 I J K L Törése (lehallgatása): 4 M N O P - Egy megfigyelő könnyen lehallgathatja az üzenetet, azonban igen nehezen tudja feltörni próbálgatással, mert NxN lehetőség van! - A feltörés egyetlen módja, ha gyakoriság-elemzést hajtunk végre. Ennek alapja, hogy minden nyelvben megfigyelhető az egyes betűk gyakorisága. A magyarban a leggyakoribb betűk, a ’szóköz’ és az ’e’; így az egyes fáklyajelzések gyakoriságából következtethetünk, hogy az adott szimbólum melyik betűt jelenti. - Ez a feltörés azonban kivédhető, ha a dekódoló mátrixot rendszeresen változtatják a kommunikáló felek. De a lehallgató nem jön rá, hogy a kódmátrix megváltozott 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) • • • 6. oldal, összesen: 13 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 - 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 titkosított üzenet: A B C D A B C D A Nyílt üzenet amit titkosítani akarunk B C D A B + KulcsKulcsKulcsKulcsKulcsKulcsKulcsKulcs C D A B C 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. 7.

oldal, összesen: 13 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 2 száma, míg SA a szövegben előforduló ’A’ karakterek ⎛ i N⎞ ⎛ i N⎞ L = ⎜ S A − ⎟ + . + ⎜ S Z − ⎟ számát jelöli. n⎠ n⎠

⎝ ⎝ o Ha minden betűből ugyanannyi lenne, akkor egyenletes 2 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 L nagy lesz, ha eltaláltuk a hosszt, illetve kicsi, ha nem o Megjegyzés: ez a támadási módszer csak akkor alkalmazható, ha a rejtett üzenet a kulcsnál sokkal hosszabb A véletlen átkulcsolás módszere (= one time pad) (Vernan, 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. Vigeneremó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 X 1 = Y1 − Y2 + X 2 8. oldal, összesen: 13 Feladatok: - 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 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. X2 Ha a nyílt üzenetekben egy adott pozíción ugyanaz a betű volt, akkor a kulcs ugyanannyiadik karakterét adjuk hozzá, így az eredmény is ugyanaz lesz. - X1, X2 értelmes szövegek. Ha nem ugyanaz a kulcs, egyenletes eloszlást kapunk Y1 - Annak is van valószínűsége az adott nyelvben, hogy egy adott pozíción milyen Y2 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 is mérhető, hogy X1-ben és X2-ben ugyanazon a helyen ugyanaz a betű van. P(A)2 N ( P A2 . A . A . Q . Q + . + P Z2 ) Transzpozíciós titkosítás N Y I L T U Z E N E T 3 5 2 1 6 4 3 5 2 1 6 4 L I N Y T N E U T Z E - - - Vegyük a nyílt üzenetet, amit titkosítani szeretnénk, majd válasszunk egy blokkméretet (n) és egy jó permutációt. Pl n = 6 Bontsuk n hosszú blokkokra az üzenetünket, majd használjuk a permutációt (pl. 3,5,2,1,6,4 – ez a kulcs-információ): amilyen szám van alatta, annyiadik helyre fog kerülni a betű a blokkon belül. Értelmes szöveget akarunk feltörni Megjegyzések: o A kulcsok száma: n! o A betűgyakoriság megmarad o Szomszédságok vizsgálata: betűátmenet-gyakoriság o Adott nyelven milyen valószínűséggel kezdődnek bizonyos szavak o Olyan adatot szeretnénk,

amely megadja, hogy az első pozíció után valószínűleg melyik pozíció következik o Ha ránézünk egy betűre, és az utána következők statisztikája adott, akkor vesszük minden blokkból az első két karaktert, megnézzük, hogy ezek statisztikája ugyanaz-e. Törése: 1 2 3 4 1 min 2 min 3 4 9. oldal, összesen: 13 1 L T [i, j ] = ∑ − log P(Ymj | Ymi ) L m=1 1 L T [1,2] = ∑ − log P(Ym 2 | Ym1 ) L m=1 L: a blokkok száma, i,j = a mátrix i-edik oszlopának j-edik sora. A képlet a mátrix egy elemét számolja ki. P-hez a statisztikabeli értéket írjuk be. Ha a sorból kiválasztjuk a legkisebb elemeket, akkor megkapjuk a permutációnk inverzét. Így tér el a legjobban az egyenletes eloszlástól. Ha nem találjuk el, akkor az egyenletes eloszlás miatt nem működik a statisztika. o A szükséges műveletek száma n!-sal szemben, mindössze: n x n x L. o o o o 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) 10. oldal, összesen: 13 Támadási típusok - A támadó elhelyezkedése szempontjából: o Passzív támadó: a támadó csak lehallgatja a csatornát o Aktív támadó: a támadó képes beépülni a kommunikációba, az üzenet elküldése rajta keresztül történik. o Shamir módszer: A ráteszi a lakatot, elküldi B-nek, ő is rárakja a lakatját, visszaküldi Anak.

A leveszi a saját lakatját, elküldi, ekkor már csak B lakatja van rajta B leveszi, elolvassa. Háromszor utazik az adat A lakat lehet tetszőleges, de bizonyos minimális feltételeknek meg kell felelnie. Az adat mindig titkosítva utazik Pl • 1. üzenet: X xor KA • 2. üzenet: X xor KA xor KB • 3. üzenet: X xor KB • De: X xor KA xor X xor KA xor KB xor X xor KB = X • Ezért csak akkor használható, ha különböző titkosítási módszereket alkalmazunk o Ennél a postás a probléma: valaki B-nek adhatja ki magát. o A nem tudja eldönteni, hogy a válaszban érkező kétlakatos üzenetet valóban B küldte-e. A postás aktív támadóként képes megjelenni. o A gyakorlatban mégis alkalmazható: A addig nem veszi le a kulcsot, ameddig B vissza nem igazolta, hogy az előző megérkezett. A csak egyszer hajlandó levenni a lakatot A kölcsönös információ nulla, mivel az azonos kulcs használatának valószínűsége nulla. - Mit tételezünk fel a támadóról?

a) A támadó birtokában Ek(x1) és Ek(x2) van. (Encryption, kulcs, üzenet) b) A támadó birtokában [x1, Ek(x1)] [x2, Ek(x2)] párjai vannak, vagyis a nyílt és a rejtett üzenet párjai. c) XÆ Ek(x), ismeri az algoritmust, tetszőleges nyílt üzenetből rejtettet tud előállítani d) Képes ennek még az inverz függvényét is előállítani. X = Dk(y) - Csak az fogadható el, amely a d)-nek is ellenáll, vagyis az algoritmust sem mutatja meg. Definíció: Lavinahatás: A bemenet egy bitjének megváltoztatása a kimenet legalább fele bitjét megváltoztatja. Ha ez nem teljesül, akkor a próbálkozások során lehet látni, hogy egyre közelebb vagy távolabb kerülünk-e a megoldáshoz. Ha a lavinahatás érvényesül, akkor az üzenet csak egy kicsit más, mégsem tudja a feltörő, hogy jó irányba halad-e a próbálgatáskor. - 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 11. oldal, összesen: 13 Nyilvános kulcsú titkosítások A B - Alapötlet: használjunk két kulcsot. Az egyik a nyilvános (KN), a másik a titkos kulcs (KT). y = E ( x, K NB ) - Létrehozunk egy nyilvános kulcstárat, ami a nyilvános kulcsokat és tulajdonosaikat

tartalmazza: [A, KN] [B, KN]. Ez csak olvasható B B y = D ( E ( x , K ), K ) N T 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 titkos kulcsot A B csak A tudja, ezért biztos, hogy az üzenet tőle érkezett. Ha az X A A előáll a képlettel, akkor az üzenet A-tól jött (kivéve, ha ellopták E ( D ( K T , x ), K N ) ⇒ x 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. AB A : E ( D( x, K TA ), K BN ) [ B ), K B ), K s B : B D( E ( D( x, K TA ), K N p T ] 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 y = EB ( x) = x eB mod mB egymás mellé írva kapja meg az üzenetet. 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 12. oldal, összesen: 13 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. 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ás a b1 K 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 ⎝

ln M ⎠ ⎝ ln N ⎠ 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. Nem igényel nagy számítási teljesítményt 2 Hatványozás: 2100 = 99db szorzás (n-1) ⎛ 2 2⎞ 8 ⎜ ⎟ 2 =⎜ 2 ⎟ 3db szorzás Hatékonyan: szorzásokra és négyzetre emelésekre vezetjük vissza ⎝ ⎠ a hatványozást. 7 3 2 = 2 ⋅ 2 ⋅ 2 3 5db szorzás 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) ( ) Titokmegosztás Módszerek: - N-ből n: A és B csak a titok egy részét ismeri. Együtt kellenek ahhoz, hogy pl az adminisztrátori funkciókat ellássák. Ha A meghal, a titoknak vége - Duplikálás: legyen több A és több B is. Ha túl sok ilyen páros van, egyre gyengébb a védelem - Bontsuk n részre a titkot: ekkor viszont n embernek

egyszerre kell jelen lennie a használatkor - N-ből k: n elemből 2 elég, hogy a titkot meghatározza. a) N-edfokú polinom esetén n+1 pont kell, hogy egyértelműen meghatározzuk. Egyirányú függvények - X-ből y könnyen kiszámolható, de visszafelé: a) az f inverze vagy nehezen számolható, vagy egy plusz információ birtokában könnyen (kulcsinformáció) b) illetve egyáltalán nem számolható 13. oldal, összesen: 13 - Gyakorlati hasznosítás: jelszótárolás a) Vesszük a jelszó betűinek ASCII kódjait, pl. JENO7, majd összeadjuk (Mondjuk kijön 507) Ez azért rossz, mert túl sok jelszó mutat ugyanarra a képezett értékre, több jelszóval is be lehet jutni a rendszerbe (megkönnyíti a próbálgatást). b) Nyitott algoritmusok: MD2, MD3, MD5. Elfogadott az SHA c) Működése: aa beírjuk a jelszavunkat, akkor a rendszer összehasonlítja a kiszámolt md5-öt a tárolttal. A lemezen pedig: felhasználónév + kódolt jelszó van tárolva - Diszkrét

hatványozás mint egyirányú függvény (van inverz, de nehezen számolható): a) Válasszunk egy nagy prímszámot, előkódoljuk az üzenetet: 1 és p-1 b) 26-os számrendszerben kiszámoljuk a számot, ez lesz a titkosított üzenet c) Primitív elem egy prímszám, ha a hatványai mind különböző számot adnak a megfelelő kitevőre emelve. (λ, λ2, λp-1) y = f ( x) = λ x mod p d) F(x) esetében nem jelenik meg a klasszikus kulcsfogalom. Inverze a diszkrét logaritmus lenne, amely nehezen számolható