A szimmetrikus titkosítás s első generáci

A szimmetrikus titkosítás első generációja és az alkalmazott transzformációk alaptípusai Tóth Mihály [email protected] előadása habilitációja tudományos kollokviumán

a Miskolci Egyetemen 2005 június 1-én.

Hová sorolható ez az előadás és amiről szó lesz. • Az ME Informatikai képzését és kurzusait áttekintve • A mesterséges intelligencia alkalmazásaihoz lehet leginkább besorolni. • Szót ejtek az ún. első generáció – kommunikációs, rejtési és titkosítási vonatkozásairól, – miért nem volt különösebben érdekes a titkosítás és miért a rejtés, – hogyan kötődött mindez az akkori kommunikációs technikákhoz és példákat is mutatok ezekre,

• Végül szó lesz az első generációra jellemző kétféle alap-transzformációról. 2005. június 1.

Tóth Mihály habilitációs előadása a Miskolci Egyetemen

2/36

A didaktikai módszerről • Alapvetően induktív • Példaként néhány ténylegesen alkalmazott módszert mutatok be, • amelyekből következtetéseket kellene levonnia a hallgatóságnak. • A módszerek bemutatása után kérdéseket teszek fel és • Szeretném, ha ezekre a hallgtóság adná meg a válaszokat. 2005. június 1.


3/36

Források • A téziseimben felsorolt szakirodalmi forrásokon és • elsősorban oktatási célra készült írásaimon valamint a bemutatóimon kívül • az ebben az anyagban bemutatott, képek és táblázatok forrása részben néhány webkikötő, a scannelt anyagoké pedig: Fred B. Wrixon: Codes Ciphers … c. könyve. Kiadta: Black Dog & Leventhal Publisers Inc. NY 1992. ISBN: 1-57912-040-7 2005. június 1.


4/36

Rejtés és/vagy titkosítás • 2000-2500 évvel ezelőttől: rejtés (szteganográfia) – Pl. betűk észrevétlen megjelölése ártatlannak látszó (fedő) szövegben. (tűjelek, láthatatlan tinták…)

• A mai alkalmazásai: kereskedelmi, copy right információk elrejtése (képben, mozgó képben, hangfájlokban. Elektronikus vízjel. zjel • Igen fejlett technikák vannak rá, amelyek „kibírják” a fedő kép, hang szöveg… szerkesztését, másolását is. • A szteganográfia azonban más, mint a kriptográfia (jóllehet együtt is alkalmazhatók) 2005. június 1.


5/36

Egy példa a mai rejtési technikára A jobboldali képben Arany János: Toldi (első ének)

2005. június 1.


6/36

Mi határozza meg a kriptogenerációkat? Két dolog együttesen • Transzformációs módszerek

• Kommunikációs módszerek

Az első generáció betűt betűbe képez le (konvertál) 2005. június 1.

Kriptogram ábécé (szimbólumkészlet) Tóth Mihály habilitációs előadása a Miskolci Egyetemen

7/36

Kódolás vagy titkosítás (leképezés, transzformáció, konverzió) • A leképezés célja lehet – Illesztés a kommunikációhoz (s ekkor nem cél a titkosítás, sőt…) Ez a kódolás – Titkosítás, vagyis a beavatatlan számára érthetetlen üzenet előállítása.

2005. június 1.


8/36

Néhány példa a kódolásra (1) Sir Home Popham admirális vezette be az angol flottánál és a szárazföldön is a kétkarú szemafor jelzéseket, amilyeneket Napóleon is használt hírközlésre. (1808) Vegyük észre, hogy szimbólumokkal helyettesíti a nyílt ábécé betűit!

2005. június 1.


9/36

A

Nemzetközi, tengerészeti zászló-ábécé

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U 2005. június 1.

V

W

X

Y

Z


10/36

Egyezményes jelek helyettesítése Itt az „ábécé” mindössze hét jelből áll. (és egyáltalán nem titkos)

2005. június 1.


Pl. rendőri közlekedés irányítási jelek. 11/36

Kérdések (1)

Diszkrét elemek (szimbólumok) halmazai. Véges, megszámlálható Azonos rangú halmazok Kölcsönösen egyértelmű leképezés, amely táblázatokkal adható meg. Használhatjuk vajon a ezt a leképezést titkos írásokhoz is?

• Algebrai szempontból mik az ábécék? • Elemeik száma? • P és C viszonya? • A ϕ leképezés milyen tulajdonságokkal rendelkezik?

2005. június 1.


12/36

Sherlock Holmes pálcika figurái (Adventure of the dancing men)

„am here abe slaney come elsie”

Jelzi a szóközöket és ez igen nagy segítség a megfejtéshez. A gyakran ismétlődő betűknek megfelelő jelek is könnyen azonosíthatók. Betűgyakoriság-elemzés. Az arabok már Kr.u. 800-ban rájöttek 2005. június 1.


13/36

Stuart Mária titkos írása

Ezt is betűgyakoriság-analízissel fejtették meg és ez Stuart Mária fejébe került. 2005. június 1.


14/36

A Rózsakeresztesek titkosírása (XVII. sz.)

Van, aki ezt a fajta szimbolizmust geometriai titkosításnak nevezi, de azért ez is csak betűt betűvel helyettesít. 2005. június 1.


15/36

Polybius sakktáblája Igaz, hogy ez a titkosítás egy-egy nyíltszövegbetűt egy-egy kriptogram számpárba képez le, de ha a számpárokat egyetlen szimbólumnak tekintjük, akkor ez is csak monoalfabetikus leképezés. A megfejtőnek már az is gyanús lehet, hogy 5-nél nagyobb számjegyek nem fordulnak elő. (Börtön-távíró.)

P: görög történetíró Kr.e II. sz. Aeneas Tacticos Kr.e. 350-345. 2005. június 1.


16/36

A Toldi egyes betűinek gyakoriságai

Karaktergyakoriság %

A leggyakoribb 15 karakter 40,00 35,00 30,00 25,00 20,00 15,00 10,00 5,00 0,00 1

2

3

4

5

6

7

8

9 10 11 12 13 14 15 16

Karakterek csökkenő gyakoriság-sorrendben

szk, (15,4%); e, a, t, n, l, s, (32%); k, r,o, i, g, á, (17,2%); a maradék: 32,5% 2005. június 1.


17/36

Statisztikai próba a titkosítási módszer megtalálására • Ha a betűgyakoriság betűnként ugyanolyan, mint a nyílt szövegé, akkor uniliterális a titkosítás (permutációs). • Ha a gyakoriság-eloszlás ugyanolyan, mint a nyílt ábécéé, de más betűknél (vagy szimbólumoknál) jelentkezik, akkor unilaterális (egyszerű helyettesítés). • Ha a betűgyakoriság eloszlás „kiegyenesedik”, akkor valami más, pl. az egyik polialfabetikus módszert alkalmazták. • Az ilyen statisztikai eloszlás-vizsgálatra Friedman dolgozott ki módszert. (ϕ próba) 2005. június 1.


18/36

Egy egyszerű eszköz a helyettesítések (és a visszafejtések) elvégzésére: a Cézár kerék Ehhez már matematikai modell is rendelhető, nevezetesen a mod n összeadás ill. kivonás, ahol n az ábécé elemeinek a száma.

A leképezést általános esetben táblázattal adjuk meg. S boksz.

A nyílt szó Betű sorsz. A kulcs (H) Az összeg A mod 32 összeg A kriptogram 2005. június 1.


A B A C U S 0 2 0 3 25 23 9 9 9 9 9 9 9 11 9 12 34 32 9 11 9 12 2 0 H Í H J B A 19/36

Kérdések: • Mi az egyszerű, monoalfabetikus helyettesítés, mint titkosítás gyengéje?

Betűgyakoriság elemzéssel könnyen megfejthető.

Vajon miért?

Túl egyszerű a kulcs és kicsi a (kriptogram) ábécé elemszáma.

Hogyan lehetne ezen segíteni?

Bonyolultabb helyettesítő módszer kellene több ábécével és bonyolultabb kulccsal.

2005. június 1.


20/36

Egy egyszerű 4 ábécés rendszer

Az ún. Shadow rendszer, (az 1930-as évekből származó képregény) 2005. június 1.


21/36

Elvi megoldás a megfejtés megnehezítésére:

Az n elemű Vn halmaz

2005. június 1.

Injektív leképezés

Az m elemű Wm halmaz


22/36

Következtetések a monoalfabetikus helyettesítő leképezésekre (1) • A betűírások nyílt ábécéi mindössze 2-3-szor 10 betűből állnak. • Ha a kriptogram ábécé betűi is csak ugyanennyien vannak, akkor akár próbálgatással is könnyen visszafejthető a kriptogram. • A megfejtést segíti, hogy az egyszerű helyettesítés – ugyanazt a nyíltszöveg betűt mindig ugyanúgy helyettesíti, – megőrzi a nyílt szöveg betűinek a „szomszédosságát” 2005. június 1.


23/36

Következtetések a monoalfabetikus helyettesítő leképezésekre (2) • A megfejtés megnehezítésére irányuló törekvések: – Olyan leképezés, amely nem őrzi meg a „szomszédosságot”. (Ez is monoalfabetikus, de más transzformáció-típust alkalmazó rendszer.) – A kriptogram ábécék számának növelése, ami egészen máig végigvonul a kriptorend-szerek fejlődése/fejlesztése mentén. Ezek polialfabetikus rendszerek. – Monoalfabetikus, de extrém sok elemű ábécével dolgozó kriptorendszerek. (Pl. a nyíltkulcsú KrR.) 2005. június 1.


24/36

Létezik monoalfabetikus, de a szomszédosságot nem megőrző transzformáció már a kezdetektől: • mégpedig a keverés A B C D E F (permutáció). • Ehhez a nyílt szöveget fix hosszúságú ún. blokkokra tagoljuk, és • minden blokkban azonos szabályok D C E AF B szerint összekeverjük a betűket. (P boksz) Rövid blokkhossz (anagramma) esetén nem nehéz a megfejtés.

2005. június 1.


25/36

Példa Egy 64 bites blokk permutációs táblázata. (Ez itt éppen a DES ún. kezdeti permutációja.) 2005. június 1.


26/36

Következtetések a monoalfabetikus permutációs leképezésekre (1) • A permutáció nem változtatja meg a nyílt szöveg betűit. • A ϕ leképezés monoalfabetikus és a kriptogram ábécé ⎯ ϕ természetéből következően ⎯ azonos a nyílt ábécével. • Az ábécét nem kell előre kikötni. • A leképezés uniliterális. lis • A permutáció alapvetően más természetű leképezés, mint a helyettesítés. 2005. június 1.


27/36

A keverésnek is vannak egyszerű módszerei, úm: • Sorfolytonosan egy mátrixba írni a betűket és valamilyen más rendszerben kiolvasni. (Pl. oszlop folytonosan, átlósan…) • Titkosító „rács” alkalmazása nxn-es betűmátrixokra. (Demó.) • Vegyük észre, hogy a keverés mindig „blokkosított”. (Padding.) • A mai rendszerekben az S éa a P bokszokat egy rendszeren belül alkalmazzák. (Pl. az ún. iterációs rendszerekben, mint a DES, IDEA, AES, Twofish, Serpent, …) 2005. június 1.


28/36

A teljes keverési transzformáció

A 36 karakteres nyílt szövegblokk

2

4

6

14

16

18

26

28

30

8

10

12

20

22

24

32

34

36

7

9

11

19

21

23

31

33

35

1

3

5

13

15

17

25

27

29

A titkosított 36 karakteres szövegblokk, amely ugyanazokat a betüket tartalmazza, mint a nyílt szövegblokk 2005. június 1.

A négyzetrácsforgatásos keverési transzformáció eredő permutációs táblázata


29/36

Kérdések az egyszerű helyettesítő leképezésekkel kapcsolatban: • Megmarad-e a nyílt szöveg betűinek a „szomszédossága” a leképezés után is a ϕ képtartományában? • A „szomszédosság” megőrzése miatt nevezzük a monoalfabetikus helyettesítést unilaterális leképezésnek. • Egyik (nem túl jelentős) hátránya az, hogy a nyílt szöveg ábécéje kötött. • Van-e olyan leképezés, amely a szomszédosságot nem őrzi meg és az ábécéje sem kötött? 2005. június 1.


30/36

Továbbfejlesztés a polialfabetikus rendszerek felé: de Vigenere kódja • A XVI.-XVII. század fordulóján jelent meg a „látnok” kódja és 300 évig nem tudták megfejteni. (Babbage, XIX. sz.) • Nagyon egyszerűen bemutatható, hogy tulajdonképpen a Cézár kerék továbbfejlesztéséről van szó. (Demó.) • De Vigenere maga alkalmazta ehhez a modulo n összeadást és kivonást • Ami azóta is „visszakisért” a modern (aszimmetrikus) kriptorendszerekben. 2005. június 1.


31/36

Összefoglalás (1) • A titkosítás az ún. nyílt szöveget egy kriptogramba képezi le. • Fontos fogalom mind a nyílt szöveg, mind a kriptogram ún. ábécéje (vagy ábécéi). • Egy titkosítási módszert aszerint nevezünk egy, vagy több ábécésnek, hogy a kriptogramot hány ábécé segítségével hozzuk létre. • Eszerint vannak monoalfabetikus és polialfabetikus kriptorendszerek. 2005. június 1.


32/36

Összefoglalás (2) • A kriptorendszerek első generációjára az jellemző, hogy az ide tartozó kriptorendszerek monoalfabetikus rendszerek. rendszerek • Az első generáció alapvető leképezési módszerei: – a helyettesítés (szubsztitució, S) és – a keverés (permutáció, P)

• Az első unilaterális, lis a második uniliterális rendszer. 2005. június 1.


33/36

Az első generációs kriptorendszerek őstípusainak összevetése A B C D E F

D C E AF B Caesar-féle helyettesítési módszer Transzpozició (permutáció) (Unilateralis, Egyábécés rendszer) blokk-titkosítás (Uniliteralis, egyábécés rendszer) Tóth Mihály habilitációs előadása 2005. június 1.

a Miskolci Egyetemen

34/36

Következtetések • Az első kriptogeneráció egyik fő jellemzője, hogy az ide tartozó titkosítások monoalfabetikus rendszerek. • A megfejtést nagyon megkönnyítette a kriptogram ábécé betűinek kis száma. (Ezt a hátrányt aztán igyekeztek is megszüntetni.)

• Alapvető transzformációs módszerek voltak: – a helyettesítés és – a permutáció

• Ezeket aztán (továbbfejlesztve) megtalálhatjuk a legmodernebb kriptorendszerekben is. 2005. június 1.


35/36

Köszönöm a figyelmüket és interaktív közreműködésüket és várom az esetleges kérdéseiket

A szimmetrikus titkosítás s első generáci

Recommend Documents