IN-201 Bevezetés az informatikába

Forrás: http://www.doksi.hu

IN-201 Bevezetés az informatikába 1. fejezet Információelmélet

Kógelmann Gábor főiskolai docens Informatikai Intézet 203 - as szoba

Ez a dokumentum elektronikus formában saját célokra szabadon másolható, terjeszthető. A nem kereskedelmi jellegű alkalmazásokhoz, változtatások nélkül és a forrásra való hivatkozással


MEDFK Informatikai Intézet

Információelmélet

2

használható. Minden más terjesztés és felhasználás esetében a szerző / tulajdonos engedélyét ki kell kérni. Ennek a szövegnek a dokumentumban mindig benne kell maradnia!

1. Az információelmélet alapfogalmai Az információelmélet legjelentősebb művelői Az alapok megteremtői: • C. E. Shannon The Mathematical Theory of Communication Bell System Technical Journal, 27, 1948 (A hírközlés matematikai elmélete) • N. Wiener A Bell Telephone Laboratories munkatársai: ("Az információ- és kódoláselmélet szülőhelye") • C. E. Shannon • R. W. Hamming • B. McMillan A Massachusetts Institute of Technology munkatársai: • N. Wiener • D. Huffman • M. Fano A részletes matematikai bizonyítást végzők: • B. McMillan • J. Wolfowitz • A. Feinstein

1.1 Az információ fogalma és tulajdonságai • Az információ anyaghoz kötődik. • A kapcsolat adat formában valósul meg. • Az anyag amihez az adat kötődik ; Adathordozó. Definíció: Az adat bármilyen hír, közlemény, amit felfogunk, érzékelünk. Az információ a nekünk új ismeretet hozó jelek tartalmi jelentése. Az adat a formai, az információ a tartalmi oldalát jelenti ugyanannak a közleménynek. Példa: Holnap elmész az informatika órára? • Igen elmegyek az informatika órára. • Igen elmegyek. • Elmegyek. • Igen.

Kógelmann Gábor / infelm.doc




3

• El. Az információ legfontosabb tulajdonságai: • Az információ mennyiség nem szükségszerűen változik az információt hordozó jelek számával. • A kétszer adott közleménynek nincs kétszeres mennyiségű információértéke. • Egyidejűleg több egyed részére kiadott információból mindenki ugyanannyi információt nyerhet. • Az információ nem osztódik. • Azonos közleményt különböző jelekkel is rögzíthetünk, ez nincs hatással az információ tartalomra. • Azonos jelek más összefüggésben más információt hordozhatnak.

1.2 Az információ átadási folyamat Az információ átadás elemei:

Adó

Csatorna

Vevő

Az adó feladatai: • A hírek, közlemények kialakítása • Kódolás, a csatorna igényei szerint A vevő feladatai: • Dekódolás • A hírek, közlemények felhasználása A csatorna lehet: • Térbeli adatátviteli csatorna • Időbeli adatátviteli csatorna • A csatornának minimálisan kétféle jelet kell átvinnie. • Az ilyen csatornát bináris csatornának nevezzük. • Egy kettes számrendszerbeli számjegy a bit. ( binary unit, binary digit ) Egyben ez az információmennyiség alapegysége is.





1.3 A kódolási eljárás Alapfogalmak: • Forrás-ABC • Közlemény • Kód-ABC (Csatorna-ABC) • Kódközlemény

A kódolási eljárás: • Olyan utasítás, amely minden lehetséges közleményhez hozzárendel egy kódjelekből álló sorozatot a kódközleményt. • A gyakorlatban a forrás-ABC minden betűjéhez hozzárendelünk egy kódjelekből álló sorozatot - az illető betű kódját-, és a továbbítandó közlemény kódközleményét az egyes betűk kódjainak egymás után írásával állítjuk elő. • Általában azonos hosszúságú kódokat alakítunk ki.

A kódolással szemben támasztott követelmények: • Alkalmas legyen minden közlemény egyértelmű leképzésére. • Tömör legyen. (Gazdaságosság!) • A csatorna képes legyen a jelek továbbítására.

Kódolni csak akkor lehet, ha rendelkezésre áll: • A kód-ABC • A kódképzés szabálya • Formai (szintaktikai) • Értelmezési (szemantikai) A kódolás általában többszörös. (Például a telefon)

1.4 Jelkészlet A kódolható forrás-ABC betűk számát meghatározza: • A kód-ABC jeleinek száma • A kódszó hossza Definíció: A kód-ABC és meghatározott hosszúságú jelsorozat mellett továbbítható forrás-ABC betűk számát jelkészletnek nevezzük.


4




Ha a kód-ABC decimális, akkor a jelkészlet: Decitek száma 1 2 3 stb.

Jelkészlet 10 = 10 10 x 10 = 100 10 x 10 x 10 = 1000

Ha a kód-ABC bináris, akkor a jelkészlet: Bitek száma

Jelkészlet

1 2 3 stb.

2=2 2x2=4 2x2x2=8

Általánosságban:

V =mn

Ahol: V - jelkészlet m - a kód-ABC jeleinek száma n - a kód hossza A jelkészlet exponenciálisan nő a jelsorozat hosszával. Példa: m = 2;

n = 8;

V=?

V = m n = 2 8 = 256 A kérdés általában az, hogy (m) jelű kód-ABC esetén milyen hosszúságú (n) jelsorozatot kell a csatornán továbbítani, hogy a rendszer minden lehetséges állapotát kifejezhessük.

V = mn

Mindkét oldal m alapú logaritmusa

logm V = n logm m

n=

logm V logm m

Mivel a logaritmus alapjának logaritmusa egy, ezért:

n = logm V


5




A továbbiakban jelölje df az adott kódrendszerben előforduló forrás-ABC jelek számát.

nsz = logm df

,illetve bináris csatorna esetén

nsz = log2 df

[bit] Ahol: nsz - a szükséges bitek száma df - a forrás-ABC jeleinek száma

Ha a számológépén csak tizes alapú logaritmus számolható, akkor a kapott értéket szorozni kell: 3.3219 - el. Egy jel átlagos információ tartalma:

I=

nsz log2 df = n n

I=

1

n

log2 d f

[bit/bit] Ahol: n - a kód tényleges hossza df - a forrás-ABC jeleinek száma

Ez a Hartley - féle összefüggés. Példa: df = 6;

m = 2;

I=?

nsz = log2 df = log2 6 = 2.58 → 3 n=3 2.58 I= = 0.86 3

[bit] [bit/bit]

Azonos előfordulási valószínűséget feltételezve, minél nagyobb egy rendszer jelkészlete, annál kisebb egy-egy állapot bekövetkezésének valószínűsége. A valószínűség jelölése: p p = 0 Lehetetlen esemény p = 1 Biztos esemény Ha a rendszer egyes állapotainak bekövetkezési valószínűsége azonos, akkor:


6



p=


1

azaz:

df

df =

7

1

p

Vagyis az átlagos információ mennyiség azonos valószínűség mellett így is kifejezhető:

I=

1

n

log2

1

p

1 = − log2 p

n

(Az előző folytatása)

Példa:

1 6 1 1 1 I = − log2 = − ( −2.58) = 0.86 3 6 3

p=

[bit/bit]

1.5 Az entrópia Valós rendszerekben az egyes szimbólumok előfordulási valószínűsége általában nem azonos, így információ tartalmuk sem azonos. Az információ tartalom és az előfordulás valószínűsége fordított arányban van egymással. Az egyes szimbólumok pi valószínűséggel jelennek meg, ahol: df

∑ pi = 1

i =1

(Azaz 100 %)

A független események együttes előfordulásának törvényszerűségét felhasználva, Shannon szerint a következő formulával számolható az átlagos információ tartalom: df

H = − ∑ pi log2 pi i =1

[bit/szimbólum]

Miután ez formailag hasonló mint a Maxwell-Boltzmann gázelméletében az ideális gáz entrópiáját leíró egyenlet, ezért Shannon ennek az összefüggésnek is az entrópia nevet adta.





8

Definíció: Az entrópia nem más, mint a rendszerben lévő határozatlanság (rendezetlenség) mértéke. Bizonyítható, hogy a maximális értékét akkor veszi fel, ha minden állapot bekövetkezési valószínűsége azonos, vagyis ha:

pi =

1

df - a forrás-ABC jeleinek száma

df

akkor: df

df

1

i =1

i =1

df

Hmax = − ∑ pi log2 pi = − ∑

log2

1

df

=

=−

1 1 1 1  log2 + log2 +......+ log2  = df  df df df 

=−

df 1 1 log2 = − log2 = log2 d f df df df

Ez éppen megegyezik a df jelű forrás-ABC kódolásához szükséges kód-ABC jelek számával. Az entrópia néhány fontos tulajdonsága: • Az entrópia negatív értéket nem vehet fel. (Szemléltetés: Kétállapotú rendszer entrópia változása a valószínűség függvényében.) • Az entrópia invariáns az állapotok sorrendjére nézve. • A magára hagyott rendszerben az entrópia csak nőhet. • Az entrópia csökkentése csak energia (idő, pénz stb.) befektetés útján lehetséges. Ha a rendezettség nő: • Az entrópia csökken • A stabilitás csökken • A stabil rendszerek teljesen rendezetlenek.





1.6 A redundancia Definíció: Ha egy rendszer átlagos entrópiáját (H) elosztjuk a rendszerben elképzelhető maximális entrópiával (Hmax), akkor a közlemény tömörségi tényezőjéhez jutunk. (Hatásfok)

T=

H Hmax

Ebből a redundancia, más szóval a terjengősség: (Relatív redundancia)

R=

Hmax − H H = 1− = 1− T Hmax H max

(Abszolút redundancia : Hmax - H) Ha a szimbólumok előfordulási valószínűsége azonos, vagy az entrópia meghatározhatatlan, akkor a következő formulával szokás számolni:

R=

log P − logU logU = 1− log P log P Ahol: U - A felhasznált kombinációk száma P - A lehetséges kombinációk száma

• A rendszerek tervezésénél mindig figyelembe veendő. • Teljesen redundancia mentes rendszer csak hibátlan (,zaj nélküli) csatorna esetén tervezhető. • A redundancia célszerű felhasználásával védekezni lehet a csatorna zajok káros hatása ellen. Példák: 1.

(Az előző folytatása)

df = 6;

R = 1−

m = 2;

n = 3;

R=?

logU log2 6 2.58 = 1− = 1− = 0.14 → 14% log P log2 8 3


9




2. A beszédkor ~32 hangból álló ABC-t használunk. df = 32 Ha minden hang azonos valószínűséggel fordulna elő, akkor:

Hmax = log2 d f = log2 32 = 5

[bit/hang]

A valóság: • Nem minden hang előfordulási valószínűsége azonos. • Az egymás utáni hangok nem függetlenek. ("Emlékezettel rendelkező forrás", Markov-forrás) • A tényleges entrópia (H) közelítőleg 2 bit/hang Tehát:

R = 1−

H 2 = 1 − = 0,6 → 60% Hmax 5

• Azaz, minden 10 kimondott hangból 4 hordoz információt. • Az angol ABC 26 betűből áll. (Szóközzel 27). Ha minden betű független és egyenlően valószínű volna, akkor a Hmax = log2 26 = 4.64 bit/betű. Ha a valószínűséget figyelembe vesszük, akkor a Hmax = 4.3 bit/betű. • Shannon szerint a nyomtatott angol szöveg redundanciája kb. 75%. Az informatikai rendszerekben cél a redundancia minél alacsonyabb szinten tartása.

1.7 Adatátvitel a csatornán Definíció: A csatornakapacitás a rendszerben átvihető információ maximuma. (Shannon szerint) Zajmentes rendszerek esetén ez akkor érhető el, ha minden jel előfordulási valószínűsége azonos.

C = log2 d f


[bit/jel]

10




11

A "bit/jel" helyett használható a "bit/másodperc" is. Ehhez azonban szükség van az egyes jelek átviteléhez szükséges idő fogalmára. Ha például minden jel időtartama t (s), akkor a másodpercekre vonatkozó csatornakapacitás:

1

1

Ct = C = log2 d f t t

[bit/s]

Ha a jelek átviteli ideje nem egyezik, az összefüggés a következőképpen alakul, ha ti az i-edik jel átvitelének időtartama: df

Rt =

− ∑ pi log2 pi i =1

df

[bit/s]

∑ pi t i

i =1

Rt az információátvitel sebessége. Néhány jellemző csatornakapacitás: • RS232 Soros port 9600 bit/s • Párhuzamos port 100.000 bit/s • Ethernet hálózat 10.000.000 bit/s





12

2. A kódrendszerek elméleti alapjai A kódhozzárendelést kódolási eljárásnak nevezzük. A kódolás szabályait kódrendszerbe kell foglalni. Egy kódrendszer akkor gazdaságos, ha minél kevesebb jelből álló kódközleménnyel továbbítja az adó által megfogalmazott közleményt a vevő részére. A kódolásnak-dekódolásnak egyértelműnek kell lennie.

2.1 A zaj nélküli csatornák kódjai Definíció: Az a csatorna zajmentes, melynél a vevő által vett kódjel mindig ugyanaz, mint amit az adó a csatornán elindított. A zajnélküli csatornák kódjainak csoportosítása: • Állandó hosszúságú kódok • Betűnkénti kódolás • Blokkonkénti kódolás • Változó hosszúságú kódok • Kódszó vége jellel • Kódszó vége jel nélkül

2.1.1 Állandó hosszúságú kódok Ennél a kódolás módnál minden kódszó hossza azonos. Használata akkor célszerű, ha a forrás-ABC betűk előfordulási valószínűsége azonos vagy közel azonos. A gyakorlatban leginkább használt kódolás mód.

2.1.1.1 Betűnkénti kódolás Jellemzői: • Egyszerű kódolás-dekódolás. • Egyetlen feltétel, hogy a forrás-ABC egyes betűinek kódszava legalább egy pozíción különbözzön. • Legalább annyi kódot (kódszót) kell kialakítani, mint ahány betű a forrásABC - ben van. Tehát: Ahol: dk ≥ df dk - a kódok száma df - a forrás-ABC jeleinek száma





13

Példa: Csatorna-ABC 2 jel; Forrás-ABC 9 jel, akkor a kódban 4 kódjelet kell alkalmazni, mert 4 kódjellel 16 kódot tudunk ábrázolni, azaz a dk > df teljesül. A szükséges kódjelek száma:

V = m n ≥ df

összefüggésből kiindulva,

logm df ≤ n < logm df + 1

,ahol n egész szám.

Ha a forrás-ABC jelszáma nem egész hatványa a csatorna-ABC jelszámának, a kódolás redundáns. Példa: df = 5;

m = 2;

n=?

log2 5 = 2.32 ≤ n < log2 5 + 1 = 3.32 Tehát a szükséges kódhossz n = 3 bit/betű. A kódrendszer redundanciája:

R = 1−

log2 U log2 5 2.32 = 1− = 1− = 0.23 → 23% log2 P log2 8 3

2.1.1.2 Blokkonkénti kódolás Jellemzői: • A forrás-ABC betűcsoportjaihoz rendelünk kódokat. • Akkor kapunk jó eredményt (Kis redundanciát): • Ha a forrás-ABC kevés jelből áll • Ha a közlemény hossza az (N) blokkhossz többszöröse A forrás-ABC jelkészlete: A, B, C, D. A blokkhossz: N = 3. Akkor a blokkok: AAA, AAB, AAC, ...... A kombinatorika szerint

d fN = 4 3 = 64 különböző blokk képezhető.

Ezzel a kódolással a betűnkénti kódolás redundanciája csökkenthető.





A szükséges kódjelek száma:

dk ≥ dfN

azaz,

V = m n ≥ d fN

ebből a kódok jelhossza:

N logm df ≤ n < N logm df + 1

ahol n egész szám.

Példa: df = 5;

m = 2;

N=3

n=?

3 log2 5 = 6.96 ≤ n < 3 log2 5 + 1 = 7.96 Tehát: n = 7

[bit/blokk]

Egy forrásbetűre jutó kódhossz:

n' =

n 7 = = 2.33 N 3

[bit/betű]

A redundancia:

log2 U log2 d fN log2 5 3 R = 1− = 1− = 1− = log2 P log2 m n log2 27 = 1−

6.96 = 0.006 → 0.6% 7


14




15

2.1.2 Változó hosszúságú kódok Akkor alkalmazzuk, ha a forrás-ABC jelek előfordulási valószínűsége nem azonos. Célszerűen ebben az esetben a gyakrabban előforduló forrás-ABC jelekhez rövidebb kódokat rendelünk, mint a ritkábban előfordulókhoz. Morse-kód (részlet): A E Q .. --.p= 0.0642 0.1031 0.0008 Az alkalmazott jelek: pont, vonás, szünet A vonás három pontnyi, a szünet egy pontnyi időt vesz igénybe.

stb....

Az átlagos kódhossz: 6.0 [jel/betű]. (Ha valóban a valószínűség szerint kódolták volna, akkor csak 5.55 [jel/betű] ). A változó hosszúságú kód esetén is a kódrendszernek egyértelműen dekódolhatónak kell lennie. Példa: A=1

B=10

C=11

1 0 1 1 1 1 0 A bitsorozatot a vevő B A C B többértelműen dekódolhatja. B C A B B A A A B Nem lehet egyértelműen megállapítani az egyes kódszavak hosszát (végét). A megoldás: • Külön kódvége jel alkalmazása. • Morse-kód. • A gyakorlatban a bináris csatornánál nem alkalmazható. • Olyan kódrendszer, ahol az egyes kódszavak vége, kódszó vége jel nélkül is megállapítható. A változó hosszúságú kódok átlagos kódhossza (A kód "költsége"): df

ná tl = ∑ pi ni i =1

Ahol: nátl - átlagos kódhossz df - a forrás-ABC betűszáma pi - az i-dik betű előfordulásának valószínűsége ni - az i-dik kód hossza





16

A feladat, olyan egyértelműen dekódolható kód szerkesztése, ahol az átlagos kódhossz a lehető legkisebb értékű. Az irreducibilis kódok (és egyben az egyértelműen dekódolható kódok) átlagos kódhosszának alsó határa: (Bizonyítás nélkül)

ná tl ≥

H log m

Ahol: H - a forrás (közlemény) entrópiája m - a kód-ABC jeleinek száma

A kód hatásfoka:

η=

H ná tl log m

Az egyértelműen dekódolható kód hatásfoka nem lehet nagyobb mint 100 %. Optimális kód, az adott körülmények között maximális hatásfokú, egyértelműen dekódolható kód.

2.1.2.1 Irreducibilis kódok Vizsgáljuk meg az egyértelmű dekódolhatóság kritériumát! Legyen: A=01 C=101

B=10 D=0111

A kódközlemény pedig: 0 1 1 0 0 1 1 0 1 A B A C Ez látszólag egyértelműen dekódolható (legalábbis a fenti konkrét kódközlemény esetén). Biztosak csak akkor lehetnénk, ha minden lehetséges kódközleményt hasonlóképpen megvizsgálnánk. Ez a gyakorlatban megoldhatatlan feladat. A megoldás a kódfa alkalmazása. Segítségével egyértelműen dekódolható változó hosszú kódok szerkeszthetők, illetve ellenőrizhetők. A kódfa egy elfektetett fa-struktúra, ahol az élek iránya meghatározza az egyes kódjelek értékét. • Felfelé = 1 • Lefelé = 0





17

Az előző kódrendszer kódfája: D C B A

Nézzünk egy másik kódrendszert: A=0 B=10 C = 110 D=111 kódfája: D

Ág C Él B Csomópont

A

Az első kódfán a B kódjához hozzáírva egy egyest kapjuk meg a C-t, és az A-hoz két egyest írva a D-t. A másik kódfánál után írással nem kapunk új kódot. Definíció: Az egyértelmű dekódolhatóság nem szükséges, de elégséges feltétele, hogy a kódrendszerben használt egyes kódszavak kiegészítése további kódjelekkel ne eredményezzen újabb kódszavakat Az előbbi feltételt kielégítő kódot nevezzük irreducibilis kódnak. (vagy prefix kódnak) Következtetések: • Minden állandó hosszúságú kódrendszer irreducibilis. • Nem csak az irreducibilis kódokat lehet egyértelműen dekódolni.





18

• Irreducibilis kód szerkesztésére a kódfa akkor is használható, ha a csatorna nem bináris. Ebben az esetben a kódfa minden csomópontjából a csatorna-ABC jelszámának megfelelő élt kell indítani. A legrövidebb kódok érdekében a kódfa minden lehetséges elágazását ki kell használni. Feladat: df = 5; pA = 0.3; pD = 0.1;

m = 2; pB = 0.25; pE = 0.1

pC = 0.25;

Szerkesszünk irreducibilis, változó hosszúságú kódot! E

D C B

A

A=0 C=101


B=100 D=110

E=111




Az irreducibilis kód szerkeszthetőségének vizsgálata: Példa: n = 3; m = 2; df = 4 A=11 B=10 C=001 D=000

A

B

C D A.

Az egyes kódokhoz tartozó kódfa ágakat minden lehetséges módon egészítsük ki a maximális ághosszra. Az eredeti kódfa egy n i hosszúságú ágát

m n − n féle képpen lehet kiegészíteni n ághosszúságúra. i

B.

A kiegészítéssel nyert összes kódfaág: df

∑m

n − ni

Ahol:

i =1

n - a maximális kódhossz ni - az i. kód hossza C.

Erre teljesülnie kell a következő egyenlőtlenségnek: df

∑m

n − ni

i =1 df

∑m

i =1

≤ mn Mindkét oldal osztva mn-el

− ni

≤1

Az így nyert összefüggés a Kraft-Fanó féle egyenlőtlenség. Segítségével meghatározható, hogy adott (felvett) kódhosszúságok mellett lehet-e irreducibilis kódot szerkeszteni.


19




Példák: 1. n1 = 3 és n2 = n3 = n4 = 2; m=2 ? Lehet-e irreducibilis kódot szerkeszteni.

2 −3 + 3 ⋅ 2 −2 =

7 <1 8

Tehát lehet.

2. n1 = n2 = 3 és n3= n4 = n5 = 2; m=2 ? Lehet-e irreducibilis kódot szerkeszteni.

2 ⋅ 2 −3 + 3 ⋅ 2 −2 =


8 =1 8

Tehát még épp lehet.

20




21

2.1.2.2 Optimális hosszúságú kód szerkesztése Optimális hosszúságú kód szerkesztésével többen foglalkoztak. E fejezetben a talán legegyszerűbb, és ugyanakkor a legjobb hatásfokot elérő Huffman-féle szerkesztésmódról lesz szó. Az optimális hosszúságú kód kritériumai: • A nagyobb valószínűségű betű kódja rövidebb, mint a kisebb valószínűségűé. (Esetleg egyenlő) • A kisebb hosszúságú kód minden variációs lehetősége ki van használva. • A kódfa ágain a csatorna jelek számával megegyező elágazás van, kivéve az utolsó csomópontokat. A

A B

C Nincs elágazás

B D

C D

Irreducibilis, de nem optimális

Irreducibilis és optimális

Huffman szerint a szerkesztés menete a következő: • A forrás-ABC legkisebb valószínűségű betűinek összevonásával egyre egyszerűbb kód kialakítására vezetjük vissza a feladatot, egészen addig, míg az optimális megoldás triviális nem lesz. • Ezután az összevont betűcsoportoknak és betűknek a lehető legrövidebb kódot adjuk, miközben a betűcsoportokat fokozatosan (visszafelé haladva) felbontjuk. • A szerkesztést célszerű táblázatos formában végrehajtani. • A táblázat forrás-ABC oszlopában az egyes forrás-ABC betűket előfordulásuk csökkenő sorrendjében kell feltüntetni.





22

Példa: Készítsünk optimális hosszúságú kódot Huffman módszerével, az alábbi adatok ismeretében! pA = 50 % ; pB = 10 % ; pC = 9 % pD = 25 % ; pE = 6 %

A redukálási lépések Forrás ABC

p%

kód

p%

kód

p%

kód

p%

A

50

0

50

0

50

0

50

0

D

25

10

25

10

25

10

50

1

B

10

110

10

110

25

11

C

9

1110

15

111

E

6

1111

A szerkesztett kódrendszer kódfája:

E A=0 B = 110 C = 1110 D = 10 E = 1111

C B D A


kód




23

2.2 A zajos csatornák kódrendszere A gyakorlatban használatos adatátviteli csatornák döntő többsége zajos. A használhatóság érdekében olyan kódrendszereket kell kialakítani, ahol a hiba felismerhető, esetleg javítható.

2.2.1 Zajos csatornák kódrendszerének elmélete Csak bináris állandó hosszúságú kódokat vizsgálunk. Példa: Egy berendezést bináris kóddal akarunk be, illetve kikapcsolni. 1 = Bekapcsolás 0 = Kikapcsolás Ha feltételezzük, hogy a hiba valószínűsége: p = 0.01, akkor minden 100. parancs lesz téves. Amennyiben növelni akarjuk a biztonságot, akkor a következő kódrendszert alakíthatjuk ki: 111 = Bekapcsolás 000 = Kikapcsolás A kódrendszert a biztonság érdekében redundánssá tettük. "A független események együttes bekövetkezésének valószínűsége" tétel alapján a hiba valószínűsége:

0.01∗0.01∗0.01 = 10 −6 Tehát minden egymilliomodik parancs lesz hibás. A redundancia kihasználása: • Csak a három nullát, illetve három egyest fogadjuk el jóként, és minden más esetben hibát jelzünk. • Ha a kódközleményben két kódjel azonos, akkor a harmadikat javítjuk a túlsúlyban lévőre. 101 → 111 ; 001 → 000 Javítás esetén minden 10000. parancs lesz hibás. Adó = 111 → Vevő = 001 → Javítás = 000 Tehát a hibajavítás azonos redundancia mellett kisebb biztonságot ad mint a hibajelzés.





24

Egy kódrendszer hibajelző, hibajavító képessége annál nagyobb, minél jobban eltérnek egymástól a kódok. A hibavédelmi képességet nem a redundancia nagysága, hanem a kódok különbözőségének mértéke, a Hamming távolság határozza meg. Példa a meghatározására: 000 111 1 1 1 Az eltérő helyek. A Hamming távolság:

D = 3.

Felhasználása: • Ha a felderítendő hiba száma (e), akkor a minimális Hamming távolság: D=e+1 • Ha a javítandó hiba száma (t), akkor a minimális Hamming távolság: D = 2t + 1 • Ha hibajelzést és hibajavítást együtt szeretnénk, akkor: D = 2t + e + 1 Itt (e) a javított hibán felüli jelzett hiba.

2.2.2 Ismertebb hibavédelmi kódok Az előbbi pontban láttuk mennyinek kell lennie hibajelzés, illetve hibajavítás esetén a minimális Hamming távolságnak, most már csak az a kérdés hogyan tudunk ilyen feltételeket kielégítő kódrendszert tervezni.

2.2.2.1 Paritásos kód Az eredeti kódszót egy további, úgynevezett paritásjeggyel egészítjük ki. • Páratlan paritás: 11111 a paritásbit 10100 a paritásbit • Páros paritás: 11111 a paritásbit 10100 a paritásbit • • • •

0 1 1 0

A minimális Hamming távolság: D=2 Nyolc bitre a redundancia: R = 11% A kereszthibák jelzésére nem alkalmas. A leggyakrabban használt hibavédelmi kód.





2.2.2.2 Aránykód A kódszavak mindegyikében azonos számú egyes, és -állandó hossz mellettnulla fordul elő. • Tipikus példa: "Három a hétből" 0100101 ; 1010100 stb... • A minimális Hamming távolság: • A jelkészlet:

D=2

 n n! 7! 5040 V =  = = = = 35  k  ( n − k )! k ! (7 − 3 )! 3 ! 24∗6 Ahol: n - a kódszó hossza k - az egyesek száma • Redundancia:

R = 1−

log2 U log2 35 5.13 = 1− = 1− = 0.27 → 27% log2 P log2 128 7

2.2.2.3 Korrelációs kód Az elsődleges kód minden bitjéhez két bitet rendelünk a következő szabályok szerint: Ha az elsődleges kódjel értéke 1 akkor 10 Ha az elsődleges kódjel értéke 0 akkor 01 Példa: 1 0 1 0 1 1 0 0 1 1 0 0 1 10

Az elsődleges kód A korrelációs kód

• A minimális Hamming távolság: D=2 • A redundancia: R = 50% • A kereszthibák zömét fel lehet tárni.

2.2.2.5 Inverz kód Az elsődleges kódhoz ugyanannyi ellenőrző bitet kapcsolunk, mint amennyi az eredeti kódszóban volt.


25




26

Ha az elsődleges kódban az egyesek száma páratlan, akkor az ellenőrző bitek változatlanul ismétlik a kódot. 101010

,akkor

101010 101010

Ha az elsődleges kódban az egyesek száma páros, akkor az ellenőrző bitek az elsődleges inverzét veszik fel. 101110

,akkor

101110 010001

• A minimális Hamming távolság: (Ha az eredeti kódszó minimum 4 bit) • A redundancia:

D=4 R = 50%

2.2.2.5 Hamming kód A kódszóban többszintű paritásellenőrzést végzünk. A paritásbitek elhelyezkedése meghatározza az értéküket is. Ha az adatátvitel hibás, akkor a paritásbitekhez rendelt érték meghatározza a hibás kódpozíciót. A paritásbitek kettő hatványainak helyére kerülnek. Kódpozíciók P1 P2 P4

1 2 3 4 P P =P + + + + +

5 6 7 = = = + + + + + + +

stb...

P - a paritásbitek helye = - az elsődleges kód helye + - a paritás ellenőrzésbe bevonandó pozíciók Px - paritás szintek (Az index a paritásbit értéke) Példa: Az eredeti kód: 10111 Készítsük el páros paritással a Hamming kódját! Kódpozíciók

7 8 9 1 P 1 P1 1 1 P2 1 P4 1 P8 1 1 A Hamming kód 1 1 1 0 0 1 1 1 1


1 2 3 4 5 6 P P1 P 0 1 1 1 0 1 1 1 0 0 1

páratlan páratlan páros páratlan




27

Ha a vevő a fenti bitsorozat helyett a következőt vette: 1 1 1 0 0 0 1 1 1, akkor az ellenőrzés és a hibajavítás módja az alábbi: Kódpozíciók P1 P2 P4 P8

1 2 3 4 5 6 1 1 1 0 0 0 1 1 0 1 1 0 0 0 0

7 8 9 1 1 1 1 1 1 1 1 1

hibátlan hibás hibás hibátlan

A hiba helyét a paritásszintekhez rendelt értékek összeadásával kapjuk meg: 2 + 4 = 6. pozíció. A helyes kódközleményhez jutunk, ha az előbbi pozíción lévő bit inverzét vesszük. • A minimális Hamming távolság: D=3 • A kódrendszer egy hiba javítására képes. • Két bit együttes hibájánál a javítás téves eredményt ad. • A Hammig távolság növelhető egy vezér paritás bittel, akkor egy hibát javító, és még egyet jelző kódrendszert kapunk.





28

3. Adatszervezés A számítógépi programok utasításai döntően valamilyen adatra vonatkozó műveletet hajtanak végre. Az adatnak a műveletvégzés idején a memóriában kell lennie, azaz valamilyen "szabványos" formátumban a memóriában kell tárolni. Az adatok felhasználási területük szerint a következő csoportokba sorolhatók: • Numerikus • Logikai • Karakteres Az informatikában a megszokott tizes számrendszer mellett még további három számrendszerrel találkozhatnak: Kettes (bináris) Számjegyek: 0 , 1 Jelölés: 101011102 Tizenhatos (hexadecimális) Számjegyek: 0 - 9 , A , B , C , D , E , F Jelölés: 1AF316 Nyolcas (oktális) Számjegyek: 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 Jelölés: 17328

3.1 Alapműveletek különböző számrendszerekben Átalakítás decimálisból binárisba: 51.7510 110011.112 51 / 2 25 12 6 3 1 0

1 1 0 0 1 1

Átalakítás binárisból hexadecimálisba: 1 0110 0010.0012 162.216


1 1

75 * 2 50 00




Összeadás (Bin): 1011101101 101110 + 11011 11001101102

749 46 + 27 82210

Kivonás (Bin): 1011101101 - 11011111 10000011102

749 - 223 52610

Kivonás komplemens szám segítségével (Bin): 1011101101 - 11011111 = ? 0011011111

Egyes komplemense: 1100100000 Kettes komplemense: + 1 1100100001

1011101101 + 1100100001 110000011102 Átalakítás decimálisból hexadecimálisba: 51.7510 33.C16 51 / 16 3 0

75 * 16 12 00

3 3

Átalakítás hexadecimálisból binárisba: 33.C16 11 0011.112 Összeadás (Hex): 1AF + 3A 1E916

431 + 58 48910

Kivonás (Hex): 2BA - 1E2 D816

698 - 482 21610


29




30

Kivonás komplemens szám segítségével (Hex): 2BA - 1E2 = ? 1E2

Komplemense: +

E1D 1 E1E

2BA + E1E 10D816

3.2 Adattípusok A konkrét adattípusok ismertetése előtt érdemes még néhány fogalommal megismerkedni. • Bájt (Byte) A számítógépek legkisebb címezhető egysége. A memóriában nyolc egymás melletti bit. • Félszó (Half Word) A memória két egymás melletti bájtja. (PC esetén nincs értelmezve) • Szó (Word) PC esetén két egymás melletti bájt. Nagygép esetén négy egymás melletti bájt. • Duplaszó (Double Word) PC esetén négy egymás melletti bájt. Nagygép esetén nyolc egymás melletti bájt. • Zónarész, Magas (High) bitek Egy bájt balról számolt négy bitje. (Tetrád) • Számrész, Alacsony (Low) bitek Egy bájt jobbról számolt négy bitje. Egy bájt értéke tehát a következő formában adható meg: 1110 10102 = EA16 Zónarész Számrész High Low

3.2.1 A nagygépek adattípusai A megközelítés az IBM kompatibilis nagygépek Assembly programnyelve felől. Az adatdefiniálás szintaktikája: [név] DC [név] DS

t[Ln]'.........' t[Ln]

[név] - A memóriaterület szimbolikus neve




DC DS t Ln '....'


-

Memória foglalás és kezdőérték Memória foglalás Adat típus (C, X, B ....) Adat hossz (n = 1 - 256 bájt) Konstans érték

Karakterek definiálása (C) • A karakterek ábrázolása az EBCDIC (Extended Binary Coded Decimal Interchange Code) kódrendszerben történik. Név KC1 KC2 KC3 KC4

DC DC DC DC

Definíció CL6'241' C'11' C'* ABCD' CL3'1234'

Memória tartalom F2F4F1404040 F1F1 5C40C1C2C3C4 F1F2F3

Hexadecimális érték definiálása (X) • Az aposztrófok között hexadecimális érték lehet Név KX1 KX2 KX3

DC DC DC

Definíció X'2A' XL4'31B' XL1'AB2'

Memória tartalom 2A 0000031B B2

Bináris érték definiálása (B) • Az aposztrófok között bináris számjegy lehet Név KB1 KB2

DC DC

Definíció B'11' BL2'10101'

Memória tartalom 03 0015

Fixpontos bináris szám félszóban (H) • • • • •

Csak egészértéket tud tárolni A kettedespont a szám után Hossz nem adható meg, mindig 2 bájt A negatív számok kettes komplemens formában A bináris aritmetika számol vele

Név

Definíció


Memória tartalom

31



KH1 KH2 KH3 KH4 KH5 KH6

DC DC DC DC DC DC


H'1000' H'003' H'-1' H'32767' H'-32768' H'0'

32

03E8 0003 FFFF 7FFF 8000 0000

A számábrázolási tartomány: - 215 + 215 - 1 - 32768 + 32767 Fixpontos bináris szám szóban (F) • A hossza mindig négy bájt • Egyebekben egyezik az előzővel Név KF1 KF2

DC DC

Definíció F'1' F'-1'

Memória tartalom 00000001 FFFFFFFF

A számábrázolási tartomány: 31 + 231 - 1 -2 Több mint ± 2 milliárd Pakolt (Tömörített) szám (P) • A decimális számjegyek négy biten bináris formában ábrázolva • A jobbszélső négy bit az előjel kódja C, F - Pozitív a szám D - Negatív a szám • A maximális hossz 31 decimális számjegy • A decimális aritmetika számol vele Név KP2 KP3 KP4

DC DC DC

Definíció P'-11' PL1'123' PL3'-12'

Memória tartalom 011D 3C 00012D

Egyszeres pontosságú lebegőpontos szám (E) • Minden szám felírható lebegőpontos formában: ±m * r ±e • Ahol m a mantissza, r a számrendszer alapszáma (radixa), e a kitevő (exponens) • Hexadecimális számrendszerben tehát: ±m * 16±e • A törtszámok is ábrázolhatók, hossza négy bájt





33

• Tudományos, gazdasági számításokhoz • A lebegőpontos aritmetika használja A lebegőpontos számábrázolás részei: 31 30

-

24 23

Me Exponens (ek)

-

0 bit

Mantissza (m)

Me - A mantissza előjele: + esetén 0 - esetén 1 Az átalakítás lépései példán bemutatva: a. A decimális szám átalakítása hexadecimálissá 26.7510 1A.C16 b. Normalizálás 2 1A.C 0.1AC * 16 c. Az exponens korrigálása ek = e + 64 = 2 + 64 = 6610 = 4216 d. Ábrázolás 0 1000010 0001 1010 1100 0000 0000 0000 4 2 1 A C 0 0 0 Név KE1 KE2 KE3

DC DC DC

Definíció E'26.75' E'-32.125' E'0.5'

Memória tartalom 421AC000 C2202000 40800000

A számábrázolási tartomány: ± 10−79 − ± 10+75 A pontossága: 5 - 6 decimális jegy Duplapontosságú lebegőpontos szám (D) • A hossza nyolc bájt, a szám pontossága nő • Egyebekben egyezik az előzővel





34

3.2.2 A személyi számítógépek (IBM PC) adattípusai Karakterek ábrázolása • Az ASCII kódrendszert használja (American Standard Code for Information Interchange) • 7 bites, 8 bites változat • Nemzeti karakterkészletek (437, 852, 1250, CWI kódlapok) • 0 - 31 Nem nyomtatható jelek Egész típusú adatok ábrázolása • Fixpontos bináris típus • Szavas egész (2 bájt) • Dupla egész (4 bájt) • Hosszú egész (8 bájt) • Ábrázolás, mint a nagygép esetén • Binárisan kódolt decimális típus (BCD) • Hossza mindig tíz bájt • Jobbra igazítva • Az első biten az előjel ( + = 0 ; - = 1 ) • A decimális érték négy biten kódolva • Matematikai társprocesszor, vagy legalább 486DX processzor Valós típusú adatok ábrázolása Alapjaiban megegyezik a nagygépnél ismertetett lebegőpontos számábrázolással. A különbségek: • Az ábrázolás alapszámrendszere bináris • Az exponens 8, 11, 15 bit, típustól függően • A normalizálás formája ±1.m * 2±e alakú • IEEE 754 szabvány • Egyszeres pontosságú lebegőpontos szám (Single precision)

31 30

-

23 22

Me Exponens (ek)

-

0 bit

Mantissza (m)

Me - A mantissza előjele: + esetén 0 - esetén 1





35

Az átalakítás lépései példán bemutatva: a. A decimális szám átalakítása binárissá 26.7510 11010.112 b. Normalizálás 11010.11 1.101011 * 24 c. Az exponens korrigálása ek = e + 127 = 4 + 127 = 13110 = 8316 d. Ábrázolás 0 10000011 10101100000000000000000 4 1 D 6 0 0 0 0 A számábrázolási tartomány: ± 10−38 − ± 10+38 A pontossága: 6 - 7 decimális jegy • Dupla pontosságú lebegőpontos szám (Double precision)

63 62

Me

-

52 51

Exponens (ek)

-

Mantissza (m)

Me - A mantissza előjele: + esetén 0 - esetén 1 A korrigált exponens: ek = e + 1023 A számábrázolási tartomány: ± 10−308 − ± 10+308 A pontossága: 15 - 16 decimális jegy • Kiterjesztett pontosságú lebegőpontos szám (Extended precision) A teljes hossz 80 bit, amiből 1bit mantissza előjel, 15 bit az exponens, és 64 bit a mantissza. A korrigált exponens: ek = e + 16385 A számábrázolási tartomány: ± 10−4932 − ± 10+4932 A pontossága: 18 - 19 decimális jegy


0 bit




36

4. Algoritmusos adatvédelem A jogosulatlan adathozzáférést a következő módszerekkel akadályozhatjuk meg: • Fizikai • Ügyviteli (TÜK) • Algoritmusos

4.1 A rejtjelezés helye és szerepe a titokvédelemben A rejtjelezés szükségletét az állam kialakulása tette szükségessé. A bizalmas adatokat, információkat ma mint állam- és szolgálati titkokat ismerjük. Ma a katonai és diplomácia titok mellett mind nagyobb jelentőséget kap a privát szféra titokvédelme is. Például pénzügyi információk, egészségügyi vagy életrajzi, személyi adatok lehetnek érzékenyek, azaz ezek jogtalan megszerzése súlyos anyagi és erkölcsi károk okozására adhat alkalmat. A rejtjelezéssel kapcsolatos nyilvános kutatások a hetvenes évek közepétől egyre növekvő iramban folynak. A rejtjelezés alatt a következő tevékenységeket értjük: • A rejtjelező eszköz (algoritmus) elkészítése • A titkosítás (rejtjelezés) gyakorlati elvégzése • A rejtjelfejtés A rejtjelezés helyett ma inkább az angolból meghonosodott kriptológia szó használatos. Ennek két ága van,a kriptográfia és a kriptoanalízis. A kriptográfia olyan módszerekkel foglalkozik, amelyek biztosítják az üzenetek (tárolt adatok) titkosságát, védettségét, vagy hitelességét. A kriptoanalízis a titok - általában illetéktelen - megfejtésére ("feltörésére") tartalmaz eljárásokat.

4.2 Kommunikáció és rejtjelezés Ismeretes, hogy az adó közleményt (üzenetet) küld a vevő részére. Nyílt szövegnek nevezzük az üzenetet akkor, ha az elvileg bárki számára megérthető formájú. A rejtjeles szöveg az, amit a rejtjelező eljárás során kapunk eredményül. Írott szövegek rejtjelezésére a következő lehetőségek adódnak: • A nyílt szöveg betűinek sorrendjét valamilyen módon megváltoztatjuk, összekeverjük. Ezt a módszert transzpozíciónak nevezzük.





37

• A nyílt szöveg betűit, vagy betűcsoportjait egy előre meghatározott módon más jellel, vagy jelcsoporttal helyettesítjük. Ez a módszer a helyettesítő eljárás. • Alkalmazhatjuk a két módszert együtt is, akkor kombinált eljárásról beszélünk. A kommunikáció rendszerében a titok üzenet formájában jelenik meg. Ennek alapján a titokvédelem formája lehet: • Eltitkolhatjuk magát a kommunikációt. (Mind az adó és a vevő, mind pedig az üzenet és a csatorna titkos.) • Az előbbi módszer nem mindig használható, a titokvédelem a kommunikációnak csak bizonyos elemeire korlátozódik. • Az üzenetet titkos csatornán továbbítjuk, vagy tároljuk. Ide tartozik a Titkos ÜgyiratKezelési rendszer (TÜK) is. • Amennyiben az üzenetet nyilvános csatornán továbbítjuk, akkor az üzenetet rejtjelezni kell, amelynek során törekedni kell az adott nyelv statisztikai, nyelvi sajátosságainak elfedésére. A legtöbb államban a rejtjelezéshez kötődő tevékenységet rendeletek szabályozzák, és megfelelő szervek koordinálják.

4.3 A rejtjelezés rövid története Ókori emlékek • A magánhangzókat különböző számú pontokkal helyettesítették. • Egy könyvben, vagy iratban a titkos üzenetnek megfelelő betűket húzták alá, az eredetivel azonos sorrendben. • Polibüosz a betűket egy négyzettáblába rendezte és a sorokat és az oszlopokat megszámozta. Így minden betűnek két szám felelt meg. • Julius Caesar az ábécé betűit néggyel ciklikusan eltolta ( A => E, Y => C ), és az így kapott betűkkel helyettesítette a nyílt szöveg betűit. Természetesen az ilyen rejtjelezés megfejtése nagyon egyszerű. A középkor • Főként az egyházon belüli levelezésnél használták. • Kialakul a kód és többábécés betűnkénti helyettesítés módszere. Az újkor • Vigenere többábécés önkulcsolásos eljárása: Nyílt szöveg: Kulcsszó: Rejtjeles szöveg:


ALGOR ITMUS OSADA... + LA JOS LLPC J TEBWB L LPCJ TEBWB HWBZB




38

Egy kulcsszót (a példánkban: LAJOS) hozzáadunk a nyílt szöveg azonos hosszúságú szegmenséhez, majd az így kapott kulccsal tovább rejtjelezünk. Az összeadás eredménye az ún. Vigenere táblából olvasható ki. • Rejtjelező gépek, a többábécés rejtjelezések gépesítésére. Tipikus eszköz az ún. Baseries féle rejtjelező: Egy henger kerületére tetszőleges sorrendben 25 gyűrű húzható, amely kevert sorrendben az ábécét tartalmazza. Az egyik alkotó mentén beállítható a nyílt szöveg 25 karakteres szegmense, majd egy másik mentén leolvasható a rejtjeles szöveg. Az utolsó 60 év • A legelterjedtebb a kódkönyv használata. • A németek ENIGMA rejtjelező gépe. • Napjaink szabványa a DES algoritmus. (Data Encryption Standard) • Nyilvános kulcsú titkosítás, RSA algoritmus. (Rivest-Shamir-Adleman, 1978.)

4.4 Klasszikus rejtjelező eljárások Ebben a pontban áttekintjük a klasszikusnak tekinthető rejtjelező eljárásokat, és ahol a terjedelem engedi, utalunk a fejtés lehetséges módszerére is. A CAESAR-féle rejtjelezés • A rejtés betűeltolással történik. • Ha ismerjük a rejtés algoritmusát (jelen esetben az "eltolás"), akkor különösebb nehézség nélkül próbálkozással megfejthető. • Ha csak azt tudjuk, hogy betűhelyettesítéses eljárásról van szó, akkor már legalább három négybetűs minta kell az egyértelmű visszaállításhoz. Az egyszerű helyettesítés • Egyszerű helyettesítésnél minden betűt különböző, előre meghatározott, jellel helyettesítünk. • A vevőnek ismernie kell a helyettesítés módját. • Minden rejtjelezés permutációnak fogható fel, azaz a lehetséges kulcsok száma: 26! = 4 * 1026 , illetve 31 betűs magyar ábécét feltételezve 31! = 8.2 * 1033





39

• A fejtés mégsem lehetetlen, ha felhasználjuk az adott nyelvben rejlő statisztikai valószínűséget, illetve azt a tényt, hogy bizonyos betűk nem állhatnak egymás után. Többábécés eljárások • Példa a már ismertetett klasszikus Vigenere tábla. • Statisztikai módszerekkel ez a szöveg is viszonylag egyszerűen megfejthető. • Jobb módszer a véletlen átkulcsolás (One time pad). Ebben az esetben minden üzenethez új, az előzőktől független, sorsolt kulcsszöveget használnak, amit az adó és a vevő "abszolút" megbízható csatornán cserél ki egymással. A kulcs hossza megegyezik a nyílt szöveg hosszával. Az egymás utáni kulcsbetűk egymástól teljesen függetlenek, azaz az ábécé bármelyik betűje azonos valószínűséggel fordul elő. Matematikai egzaktsággal bizonyítható, hogy elméletileg is fejthetetlen. Transzpozíció • A blokkrejtjelezés kategóriájába sorolható. A blokkon belüli nyílt betűk sorrendjének megváltoztatásával állítják elő a rejtjeles szöveget. • Egy 50 karakteres blokk esetén a lehetséges permutációk közelítő száma: 50! = 1.7 * 1063 • Javaslói a teljes kipróbálás lehetetlenségére hivatkoztak. • A részleges kipróbálás elvét használva azonban megfejthető. Kódkönyvek • Főként a diplomáciai levelezésben használták. • Ezzel a módszerrel a továbbított szöveg hatékony tömörítése is elérhető. • Példaként egy részlet az első világháborúig használt "háromjegyű" katonai kódkönyvből: A adag........956 állomás....538 ....

B berak.......507 biztos.......835

C cirkáló....794 csapat....945

4.5 A rejtjelezési séma és az algoritmikus támadás A sémának három alapeleme van: • A nyílt szöveg. • Az algoritmus működtetéséhez szükséges kulcs. • Az eredményül kapott rejtjeles szöveg.





40

Az algoritmikus támadás: • A támadó (behatoló) célja a nyílt szöveg megszerzése. • Feltételezzük a támadóról, hogy ismeri a kódoló dekódoló algoritmust, csupán a kulcs ismeretlen számára. • A gyakorlatban a kulcs, az amit kívánatos sűrűn cserélni, míg az algoritmust hosszabb ideig lehet használni. • A támadás két alapmódszere: • Passzív • Aktív • A passzív támadás esetén (lehallgatás) a támadó a nyilvános csatornán haladó üzenet birtokába jut. Amennyiben az üzenetek ismeretében sikerül a megfejtés, akkor azt mondjuk, hogy sikerült feltörni a rejtjelező algoritmust. • Az aktív támadás esetén a támadó beékelődik a csatornába és az üzenet kivonására, kicserélésére törekszik. • Az aktív támadásokat algoritmikus módszerekkel nem akadályozhatjuk meg, azonban megfelelő kriptoprotokollok alkalmazásával és hitelesség ellenőrzéssel észlelhetjük. • Egy üzenet titkossága az jelenti, hogy csak a legális partner számára rekonstruálható annak nyílt tartalma. Shannon szerint létezik: • Feltétel nélküli titkosság és • Gyakorlati titkosság Az előbbi azt jelenti, hogy bármekkora számítási kapacitás is áll rendelkezésünkre, a rejtjelezés feltörhetetlen. (Például a véletlen átkulcsolás.) A gyakorlati titkosság esetén irreális nagyságú számítási kapacitásra van szükség. • A hitelesség azt jelenti, hogy az üzenetet olyan személy generálta, aki a kulcs legális birtokosa.

4.6 Kriptográfiai protokollok A titkosító rendszer (cryptosystem) két fő komponenst tartalmaz: egyrészt a kódoló dekódoló transzformációkat, másrészt kriptográfiai protokollokat. A kriptográfiai protokolltervezés komponensei: • Kulcskiosztás • Üzenethitelesítés • Partnerhitelesítés • Digitális aláírás • Titokmegosztás





41

Kulcskiosztás Feltesszük, hogy A, B, C, ... felhasználók kötődnek egy-egy terminálhoz és közülük tetszőleges pár tud egymással és a kulcskiosztó központtal kommunikálni. Az ilyen rendszer három kulcsot használ: • a kiosztóközpont mesterkulcsát (MK), • a felhasználói terminálkulcsokat (TKA, TKB, ...) • a kapcsolatkulcsot (SK). A központ mesterkulcsával kódolva tárolják az egyes terminálkulcsokat. Amikor A és B kapcsolatba akar lépni, mindketten kérnek egy kapcsolatkulcsot. Ezt az SK kulcsot a központ a terminálok saját kulcsával titkosítva küldi meg mindkét felhasználónak. A felhasználók az SK kulcsot saját kulcsuk ismeretében dekódolhatják, és megkezdheti az egymás közötti adatcserét. Az SK kulcsot sűrűn aktualizálják. Üzenethitelesítés Ha a támadónak módjában áll, hogy az adatátvitel során meghamísíthassa az adott szöveget, akkor ez ellen egy kriptográfiai ellenőrző összeg képzésével lehet védekezni. A vevő amennyiben az ellenőrző összeget hibásnak találja, akkor vagy csatorna zajra, vagy idegen behatolóra gyanakodhat, és nem fogadja el a dekódolt üzenetet. Partnerhitelesítés A kapcsolat felvételekor a partnerek minden kétséget kizáróan szeretnének megbizonyosodni arról, hogy valóban a kívánt személy-e a partnerük. A rendszerbeli felhasználók a hitelesítés szempontjából megbízhatónak tekintik a központjukat, és erre építik a hitelesítési protokolt. A kommunikációt csak akkor kezdik meg, ha a vevő egyértelműen meggyőződött az adó személyéről. Egy előző kapcsolatfelvétel visszajátszása elleni védelem érdekében a hitelesítési eljárásban fontos szerepe játszik egy minden esetben újragenerált véletlenszám. Digitális aláírás Az üzenet és partnerhitelesítés csak a kommunikáció időtartamára és a partnerek számára nyújt hitelesítési lehetőséget. A digitális aláírás azonban az üzenetváltás után, és harmadik személy számára is lehetőséget biztosít a hitelesítésre. A digitális aláírás protokollok a következő feladatot oldják meg: • Az aláírás generálása (az üzenetküldő végzi). • Az aláírás ellenőrzése (a vevő által). • A hitelességgel kapcsolatos viták tisztázása harmadik személy előtt.





42

A harmadik eset akkor fordulhat elő, ha az aláíró szeretne letagadni egy általa küldött üzenetet, vagy vita tárgya lehet, hogy a címzett saját céljainak megfelelően módosította-e az üzenetet. A digitális aláírás utánozni kívánja a valódi aláírást, ezért megköveteli a következő tulajdonságokat: • Legyen könnyen generálható • Ne legyen az egyik okmányról a másikra áthelyezhető (hamisítható), azaz csak a tulajdonos generálhassa. • "Bárki" képes legyen ellenőrizni hitelességét A digitális aláírásnak van egy nagyon fontos tulajdonsága, nevezetesen, hogy szerves része az aktuális üzenetnek, azaz üzenetfüggő. Titokmegosztás Minden algoritmus esetén szükség van valamilyen titkos adatra (titkos kulcs), amelyet már nem véd valamilyen újabb titkosító transzformáció. Ezért az ilyen titkos adat védelmét másfajta védelemre kell bízni. Lehetséges valamilyen fizikai védelem alá helyezni. Például memorizálás, páncélszekrény stb... Létezik azonban egy másik lehetőség is. A módszer úgy igyekszik "feldarabolni" a titkot N személy között, hogy abból tetszőlegesen választott K személy együttesen tudja csak rekonstruálni az eredeti értéket, de K-nál kevesebb erre sohase legyen képes. Ezt a módszert nevezzük titokmegosztásnak.

4.7 Korszerű titkosító algoritmusok Ez a pont kizárólag arra vállalkozik, hogy a rendelkezésre álló módszereket felvázolja. Nem tér ki a konkrét megvalósítás (implementálás) ismertetésére. A DES (Data Encryption Standard) eljárás Az IBM fejlesztésének tekinthető, 1977. óta az Egyesült Államok Szabványügyi Hivatalának FIPS-PUB-46 jelű szabványa. Az ún. blokktitkosítók családjába tartozik. Ennek a módszernek az a lényege, hogy a nyílt szöveget egyenlő hosszúságú blokkokra tördelik, és blokkonként titkosítják. Amennyiben szükséges, az utolsó töredék blokkot egy előre definiált értékkel töltik ki. A blokkok hossza a gyakorlatban legalább 50 bit, annak érdekében, hogy a tulajdonképpen helyettesítéses módszer megfejtése minél nehezebb legyen.





43

A nyelvben rejlő statisztikai sajátosságok eltüntetésére a helyettesítés és a keverés (permutáció) kombinációját használják. A helyettesítést és a keverést a választott kulcsérték vezérli. A szabványos eljárás 64 bites blokkokkal, 56 bites kulccsal és 16 lépéses keverő transzformációval dolgozik. Szakemberek szerint ez a titkosítás már a 90-es években megfejthető lesz a választott nyílt szövegek módszerével. (A támadó maga választja meg a titkosítandó szöveget.) Azonban ehhez hatalmas számítási kapacitásra van szükség, ami adott esetben nem áll arányban a megfejtéssel nyerhető előnyökkel. Ebből a meggondolásból kiindulva, még hosszú ideig védhetjük adatainkat ezzel a titkosító módszerrel. A UNIX operációs rendszer crypt programja is a DES titkosítást használja.

Az RSA (Rivest-Shamir-Adleman, 1976.) eljárás A módszer a nyilvános kulcsú blokktitkosítók csoportjába tartozik. A nyilvános kulcs azt jelenti, hogy úgy lehet titkosan kezelt adatokat cserélni, hogy nincs szükség előzetes titkos kulcscserére. Az ilyen rendszerek két kulccsal rendelkeznek. Egy nyilvános kulccsal a kódoláshoz, és egy titkossal a dekódoláshoz. A felhasználók maguk generálhatják a kulcspárt, amelyikből a nyilvánost közzéteszik a titkosat maguk őrzik. A nyilvános kulcsokat (mint a telefonszámokat) egy mindenki számára hozzáférhető kulcstárban jelentetik meg. A módszerben a problémát a kulcsválasztás okozza, ugyanis kellően nagy prímszámokat kell választani. Kellően nagynak ma a legalább 100 jegyű prímszám számít. Ezeket adott esetben jó pénzért lehet megvásárolni, ismerve a prímszám előállítás nehézségeit. A. Shamirtól származik az az érdekes eljárás, amely minden előzetes kulcscsere nélküli titkos üzenetváltást tesz lehetővé. (Még nyilvános kulcs közzétételére sincs szükség!) A módszer elve szemléletesen a következő: Képzeljük el, hogy A egy lelakatolható ládába helyezi el az üzenetet, és a ládát lelakatolja saját kulcsával (1.lépés), majd elküldi B-nek. B nem is próbálkozik a fejtéssel, hiszen nem ismeri A kulcsát. Ellenkezőleg, még a saját lakatját is ráteszi, és visszaküldi A-nak. (2.lépés). A leveszi saját lakatját, és a ládát, amelyen már csak B lakatja van eljuttatja B-nek, aki ezután azt már könnyedén kinyithatja. (3.lépés)





44

E módszer egyetlen követelménye, hogy a kódoló transzformációpár kommutatív (felcserélhető) legyen. Látszólag megtaláltuk a tökéletes megoldást. Azonban a dolog mégsem ilyen egyszerű, ugyanis ez a protokoll teljesen ki van szolgáltatva az aktív támadásnak. A példát folytatva, tegyük fel, hogy a postás, akivel a ládát elküldtük, a 2. lépésben a saját lakatját teheti a ládára, és miután a 3. lépésben A leveszi saját lakatját, a postás (behatoló) tehát kinyithatja a ládát.

4.8 A számítógépes hálózatok adatvédelme Nyilván semmiféle problémát nem okoz, ha egy személyi számítógépet egy lezárt szobában egy személy kezel, és a külvilág felé nincs kapcsolata. A helyi hálózatok (LAN, Local Area Network), illetve egyáltalán a hálózatok, ki vannak téve az aktív és passzív támadásnak. A passzív támadás nem igényli a hálózat elemeinek fizikai elérését. A lehallgatás ebben az esetben az egyes elemek elektromágneses kisugárzásán alapul. Az aktív támadás során a támadó használja valamelyik hálózati elemet. Például a hálózati terminálhoz való illetéktelen hozzáférés, a csatorna megcsapolása, lehallgatása, vagy egy aktív csomópont elhelyezése. Ez utóbbi esetben maga is küldhet adatokat. A védelem fizikai eszközei: • A passzív támadás elkerülésére kisugárzásvédett kivitelű eszközök alkalmazása. (árnyékolt kábel). • Fizikai hozzáférés-védelem megvalósítása: • A terminálokat, csomópontokat tartalmazó helyiségek védelme. • Az eszközök megbontásvédett kivitele (riasztás, adatmegsemmisítés). • Intelligens azonosítókártyák használata. • Biometrikus hozzáférés-védelem. (ujjlenyomat, dinamikus aláírás, stb...) • Az algoritmikus hozzáférés-védelem (jelszóvédelem) • Kellően hosszú jelszó. • Többszöri próbálkozás esetén letiltás. • A gyanús események könyvelése. • A jelszó kódolt formában való továbbítása. • A jelszó gyakori cseréje.





45

4.9 Az elektronikus pénzátutalás védelme PIN azonosítók A készpénzkímélő vásárlás egyik eszköze a hitelkártya (credit card). A kártyán egy mágnesezhető hordozócsík azonosító információkat tartalmaz. A másik lehetőség az ügyfélkártya (debit card), amellyel az ügyfél a bankszámlájáról emelhet le összeget. A kártya kiállításakor az ügyfél egy személyazonosító számot kap (PIN Personal Identification Number). Ez egy titkos banki kulcs alapján áll elő, és a tulajdonosnak gondosan titkolnia kell. A pénzkiadó automatába helyezve a kártyát, az ügyfélnek be kell gépelnie a PIN kódot, amit a terminálként működő automata a kártyáról is leolvas, és a központi gép felé továbbít. A két érték egyezése után engedélyezi csak a pénz kivételét. Az PIN kódot és az egyéb adatokat a továbbítás előtt rejtjelezik. Az USA-ban erre a DES algoritmust használják. A rejtjelezés történhet hardveres és szoftveres úton is. A hardveres módszer nagyobb biztonságot nyújt, de drágább. MAC kód A pénzátutalás folyamatában egy hitelesítő záradékkal látják el az adatokat (MAC Message Authentication Code) A pénzátutalás az alábbi adatokat tartalmazza: • Dátum • Üzenetazonosító • Számlaszámok, összeg • Egyéb védendő üzenet (esetleges) • MAC (4 bájt) Az aktív memóriakártya (AMK) Angol elnevezése smart card (chip card). Egy számítógépet, RAM és ROM típusú memóriát tartalmaz. A csatlakozókon keresztül kapcsolatot tart a külvilággal. Hitelkártya méretű (85 x 54 mm). Alapvetően abban különbözik a hitelkártyától, hogy a kriptográfiai alapú hitelesítő párbeszéd után az AMK-ban lévő pénzösszeg helyben módosul. A gyártáskor minden kártyába egy kártyaazonosító szót helyeznek el, a hitelesség későbbi ellenőrzésére.





Egy gyárilag elhelyezett kulcs segítségével titkosítottan kerül a kártya RAM memóriájába a számlaszám és a PIN kód. A titkosítás módja itt is általában a DES. Valahány sikertelen próbálkozás után a kártya algoritmusa "letiltja magát", amit csak a kibocsátó bank tud hatástalanítani.


46




A felhasznált irodalom 1. G. Cullmann - M. Denis Papin - A. Kaufmann: A hír tudománya könyv Gondolat kiadó, Budapest 2. dr. Fercsik János: Informatika, Informatika és számítógép 1 könyv Műszaki Könyvkiadó, Budapest 3. Pető Ádám: Assembly alapismeretek könyv SZÁMALK Kiadó, Budapest 4. Nemetz Tibor - Vajda István: Algoritmusos adatvédelem könyv Akadémiai Kiadó, Budapest


47

IN-201 Bevezetés az informatikába

Recommend Documents