A kiptográfia alapjai. Történet és alapfogalmak

2012.09.26.

A kiptográfia alapjai Dr. Tóth Mihály http://arek.uni-obuda.hu/~tothm/ Kutatók-Éjszakaja-2012

Történet és alapfogalmak • Mióta írások léteznek, azóta vannak titkos írások is. – Kezdetben, amíg kevesen tudtak írni/olvasni, nem igen volt szükség titkos írásokra. – Később már igen. A fejlettségi szintjeik szerint „generációkba” sorolhatók. – Az első két generációra a „kézi” módszerek voltak a jellemzők. (Itt és most mi az első generációba tartozó titkosírásokkal foglalkozunk.)

2012.szeptember

Kutatók Éjszakája: A titkos írásokról (Prof.Dr. Tóth Mihály)

2

1

2012.09.26.

Elnevezések és fogalmak (1) • A titkosítatlan szöveg neve nyílt szöveg szokásos jelölése: P (mint Plaintext) Természetesen van egy ábécéje. (Szimbólum készlet) • A titkosított szöveg szokásos elnevezése: kriptogram (C, mint Ciphertext.) Ehhez is tartozik legalább egy ábécé. • Magát a titkosítási folyamatot átalakításnak, idegen szóval transzformációnak nevezzük. (Régebben: sifrírozás és shiffre.) P → C 2012.szeptember


3

Elnevezések és fogalmak (2) • A kriptogram előállításához használt ábécék száma szerint vannak egy - és több- ábécés rendszerek. Mi itt és most csak egyábécés titkosítással foglalkozunk. • Valamikor úgy gondolták, hogy magát a titkosítási módszert kell titokban tartani. • Ezzel homlokegyenest ellenkezően ma a módszerek nyilvánosak, szabványosítottak és a titok a transzfomációhoz használt KULCS. • Minél nagyobb az alkalmazható kulcsok száma (az ú.n. kulcstér), annál biztonságosabb az adott kriptorendszer

2012.szeptember


4

2

2012.09.26.

A titkosítás két alapmódszere

A B C D E F Nem csak a Caesar-féle eltolásos,hanem a kevert ábécés módszer és sok más változatuk is létezik

Helyettesítés (betűnként) 2012.szeptember

D C E AF B Keverés (blokkonként)


5

A helyettesítési transzformáció egy archaikus, de alapvető eszköze (és módszere) az ú.n. Cézár kerék Ez esetben a kriptogram ábécé „véletlenül” ugyanazokat a betűket tartalmazza, mint a nyílt szöveg ábécé, de a betű gyakoriságok, persze, különbözőek.) Lényeges az ábécé betűsorrendje is. 2012.szeptember

Kutatók Éjszakája: A titkos írásokról (Prof. Dr. Tóth Mihály)

6

3

2012.09.26.

Szerepük és a megfejtés • Régen esküdtek arra, hogy csakis a helyettesítés az „igazi”. • A mai modern módszerek mind a helyettesítést (szubsztitúció), mind a keverést (transzpozíció vagy permutáció) vegyesen alkalmazzák. • Mi a következőkben egy helyettesítéses titkosítást és a megfejtés lehetséges módját mutatjuk be. 2012.szeptember


7

A megfejtéshez jó tudni • A nyílt szöveg nyelvét és az alkalmazott ábécét. (pl, tesz-e különbséget a kis- és a nagybetűk között, rendel-e kriptogram ábécé szimbólumot a szóközökhöz , soremeléshez és írásjelekhez, és hasonlókat.)

• Jó tudni azt is, hogy a nyílt szöveget milyen módszerrel titkosították. (Ez még akkor is jól jön, ha a kulcsot nem ismerjük.) 2012.szeptember


8

4

2012.09.26.

A megfejtési (feltörési) módszerek (1) • Egészen nyilvánvaló, hogy ha a titkosítási módszer ismert, akkor „csak” a kulcsot kell megtalálni. • Nyilvánvaló, hogy elvileg lehetséges lenne az összes lehetséges kulcsot kipróbálni, de • ha a kulcstér igen nagy (több billió kulcs is lehetséges), akkor ezt a leggyorsabb számítógépekkel sem lehet reális idő alatt megvalósítani. • Az összes lehetséges kulcs kipróbálását egyébként a nyers erő (brute force) módszerének nevezik 2012.szeptember


9

A megfejtési (feltörési) módszerek (2) • Az illegális (pl. a kulcs ismerete nélküli) feltörési kísérleteket támadásnak nevezik és ezekből sokféle van. • Széles körben elterjedt, pl. a kulcs (vagy „csak a személyi adatok, vagy egyes jelszavak) valamilyen ravasz módszerrel való kicsalogatása a támadás alanyától. (PIN kód, jelszó, QR kód) ( http://hu.wikipedia.org/wiki/QR-k%C3%B3d ) • Érdekes módon ezt az angol szakirodalom „Social Engineeringnek” nevezi és az emberek óvatlanságára, jóhiszeműségére épít. 2012.szeptember


10

5

2012.09.26.

A megfejtési (feltörési) módszerek (3) • Már a IX. században felfigyeltek arab tudósok arra, hogy a különböző betűk, különböző gyakorisággal fordulnak elő egy írott (nyílt) szövegben és ez segítséget nyújthat a betűhelyettesítéses titkosírások feltöréséhez. • A XVI. században ezen az elven fejtették meg Stuart Mária titkosírását és ez a megfejtés szó szerint a fejébe került. • Mindazonáltal nem lebecsülendők az első generációs , (helyettesítési és permutációs) titkosítási módszerek. 2012.szeptember


11

A megfejtési (feltörési) módszerek (4) • Egy ismeretlen kriptogram feltörését igyekszünk erre, vagyis a helyettesítéses titkosítás megfejtésére visszavezetni. • A feltörések egyébként nagyon hasonlítanak a rejtvény fejtéshez és általában több hipotézist is ki kell próbálnunk. (A mai, modern kriptorendszereknél azonban csak sokkal kifinomultabb, számítógépes támadásoknak lehet egyáltalán valami esélyük.) 2012.szeptember


12

6

2012.09.26.

A betűgyakoriság-analízis (1) • Eltekintve attól, hogy az angol ábécé nem használ ékezetes betűket (és pl. az aposztrofnak is jelentése van) • az angol és a magyar karakter-gyakoriságok nagyon hasonlóak. • Először is (hosszabb szövegben) biztosan a szavakat elválasztó szóközök a leggyakoribbak. (A rövid szövegek sokszor eltérnek ezektől a statisztikáktól). • Megbízhatóbb és reményteljesebb a megfejtés, ha minél hosszabb kriptogramok állnak a rendelkezésünkre. • A megfejtést éppen ezért is nehezíti, ha minél gyakrabban változtatják a kulcsot. 2012.szeptember


13

A betűgyakoriság-analízis (2) • A betűgyakoriság (letter frequency) analízishez rendelkezésre állnak kész programok, amelyek igénybe vehetők ehhez a szemináriumhoz tartozó webkikötőn. (Ld: http://arek.uni-obuda.hu/~tothm/ • A magyar nyelv betűgyakoriságához támpontot nyújthat pl. Arany János: Toldi c. elbeszélő költeményének betűstatisztikája (Ld. a köv. dián), de ettől eltér pl. a mai újságszövegek betűstatisztikája és a rövid szövegeké is. 2012.szeptember


14

7

2012.09.26.

Arany János: Toldi leggyakoribb karakterei A teljes szövegmennyiség valamivel több, mint 75 ezer A teljes szövegmennyiség karakter. valamivel több, mint 75 ezer A hisztogram sávjai az karakter. összes karakter százalékában A hisztogram sávjai az adják meg a gyakoriságokat. összes karakter százalékában adják meg a gyakoriságokat.

2012.szeptember


15

Egy helyettesítéses módszerrel titkosított kriptogram megfejtése • Segítségül: • A nyílt szöveg nyelve: magyar. • A kriptogram tartalmazza a szóközök (sp) szimbólumait is. • Az egyébként folytonos kriptogramot szokás 5-5 betűs csoportokra bontva megadni, de egy csoportbontás szóközei és sor-emelései nem számítanak. • A kriptogram aránylag rövid, ezért egyáltalán nem biztos, hogy a betűgyakoriság egyezik a hosszabb magyar szövegek statisztikájával. (Megfejthető egyáltalán? 2012.szeptember


16

8

2012.09.26.

A megfejtendő kriptogram a következő

2012.szeptember


17

A megfejtés logikája • Ha a nyílt szöveg szóközei is kódoltak, akkor azokat kellene először megfejteni, mert így tagolhatjuk (szavakra bonthatjuk) a kriptogramot és a rövid szavak nyílt megfelelőit nem nehéz kitalálni. (Éppen ezért nem is szokás a szóközökhöz kódot rendelni, hanem egybe írják a nyílt szöveget. (Itt nem.)

• Ne feledjük, hogy rövid a szöveg (összesen 56 betű), ezért a betűgyakorisága eltérhet pl. a Toldiétól. Valószínű, hogy van benne szóköz. (Szükség lehet több próbálkozásra!) 2012.szeptember


18

9

2012.09.26.

Az adott kriptogram gyakoriságstatisztikája

2012.szeptember


19

Hogyan jött ki? • Rövid szöveg lévén kézzel megszámoltuk. • Hosszabb szövegeknél ez nem megy. Vannak statisztika-készítő programok (1,2…n betűs „szavak” megszámolására), de • az ilyen programok nem tudnak az adott esetben előforduló „misztikus” szimbólumokkal dolgozni. • Viszont nem nehéz azokat más, a programok által is kezelhető ábécé elemeivé alakítani. • Már a korai helyettesítő (és keverő) titkosítások esetében is inkább a nyílt szöveg ábécéjét használták. 20 2012.szeptember


10

2012.09.26.

Megfejtés lépésenként. Az első próbálkozás • Ha a kriptogram leggyakoribb szimbólumát szóközökkel helyettesítjük, a következőt kapjuk

• Ez a helyettesítés alaposan tagolja a kriptogramot mégsem valószínű, hogy helytálló. (Az 1 és a 2 betűs szavak miatt.) 2012.szeptember


21

Megfejtés lépésenként. A második próbálkozás

• Próbálkozzunk a második leggyakoribb szimbólummal!

• Ez a helyettesítés olyan tagolást ad, amelyben két egybetűs „szó” is van és ráadásul azonosak. • Én az „A” határozott névelőre tippelnék, behelyettesíteném, majd kipróbálnám, hogy a 2012.szeptember Kutatók Éjszakája: A titkos írásokrólaz (Prof.Dr. Tóth Mihály) leggyakoribb szimbólum nem „E” kódja-e

22

11

2012.09.26.

A harmadik próbálkozás • Próbáljuk meg az eddig megtalálni vélt „E” és „A” betűk behelyettesítését.

Vegyük észre azt is, hogy a szöveg 3. és 4. szimbóluma azonos és a magyar nyelvben nem igen vannak kettős magánhangzók, tehát ez a szimbólum csak mássalhangzó kódja lehet. 2012.szeptember


23

A megfejtés további lépései • Az egész megfejtés leginkább rejtvény fejtésre hasonlít és a II. világháború alatt valóban rejtvényfejtőket (is) alkalmaztak kódfejtőknek. • A rövid szöveg lehetővé teszi a kézi megfejtést, de meg is nehezíti a dolgot, mert a betűstatisztika nagyon kevés információt ad. • Nyilvánvaló, hogy ha sikerül is a megfejtés, akkor sem kapjuk meg a kód kulcsát azokhoz a betűkhöz, amelyek nem is fordulnak elő a kódolt nyílt szövegben.

• Próbálják meg megfejteni! 2012.szeptember


24

12

2012.09.26.

A RÓZSAKERESZTESEK TITKOSÍRÁSÁNAK A KULCSA 2012.szeptember


25

Geometriai helyettesítés • F.B.Brixon Geometriainak nevezi ezt és a hasonló helyettesítéseket. • Betű helyettesítésről van szó, amit • nem csak a következőkben megadott módon • hanem más ábécé-beírással is (számos változatban) megvalósítható. • Ha a betűket helyettesítő szimbólumokhoz egy tetszőleges ábécé betűit rendeljük hozzá, • akkor a kész megfejtő programok is használhatók az ilyen titkosírás megfejtésére 2012.szeptember


26

13

2012.09.26.

A kód megszerkesztése és logikája

2012.szeptember


27

A betűket a rácsban elfoglalt geometriai helyükkel kódolják • Ebbe a „rácsba” 9×3=27 betűt írtunk be, azaz egy 27 betűs ábécé betűit. • Az angol ábécéhez ez több, mint elég. A magyar ábécéhez nem igazán elég • Tulajdonképpen mindegy, hogy az egyes mezőibe milyen sorrendben és milyen betűket írunk be. Ez sok változatot enged meg. 2012.szeptember


28

14

2012.09.26.

Lássuk a kódot magát! (1)

2012.szeptember


29

Lássuk a kódot magát! (2)

2012.szeptember


30

15

2012.09.26.

A szóköz (sp), mint speciális karakter • A szóköz egy nyílt szövegben a leggyakrabban előforduló „karakter”. • Emiatt nagyon megkönnyíti a kód feltörését. (A szöveg tagolása miatt.) • A (helyettesítéses) titkosírások esetében többnyire elhagyják. • Mi itt az első demo szöveg feltörésének a megkönnyítése céljából mégis használtuk. (A rózsakeresztesekkel ellentétben.) 2012.szeptember

A szóköz itt (kivételesen) használt kódja.


31

A Szabad Kőműves rend titkosírása • Lényegében ugyanazon az elven épült fel, mint a rózsakereszteseké. Csak kicsit más geometriával.

2012.szeptember


32

16

2012.09.26.

Stuart (skóciai) Mária titkosírása • Több száz más, szintén betű-helyettesítésen alapuló titkosírást is használtak. Pl. Stuart Mária titkosírását.

2012.szeptember


33

A példa-kriptogram feltöréséről • A betűstatisztikával való elindulás és a szöveg tagolása jó kezdet. Még ilyen rövid kriptogram esetén is ad néhány támpontot és betűt. • Mégis, ez a példa-kriptogram a jónéhány szingli szimbólumával nem megfejthető. • Egy hosszabb, magyar nyelvű, kevert ábécés kriptogram megfejtésére találhatnak példát a megadott webkikötőről letölthető elso_generacios_titkositasok.pdf c. jegyzet 30. oldalától 2012.szeptember


34

17

2012.09.26.

Ajánlott irodalom • Simon Singh: Kódkönyv. Park Könyvkiadó, Bp. 2007. ISBN: 9789635307982. (Nagyon olvasmányos) • Virasztó Tamás: Titkosítás és adatrejtés Netacademia Kft. Bp. 2004. ISBN 963 214 253 5 • David Kahn: The Codebrakers. Scribner, N.Y. 1967. ISBN:0-684-83130-9 (Több, mint 1100 oldalas alapmű - angolul) • Fred B. Wrixon:Codes & Ciphers. Black Dog Publ. ISBN:1-57912-040-7. (Ennek a prezentációnak alap-forrása - angolul) 2012.szeptember


35

KEVERÉSES (ÁTHELYEZÉSES =TRANSZPOZICIÓS V. PERMUTÁCIÓS)

TITKOSÍTÁSOK Betű-blokkokat titkosít. A nyílt szöveg ábécéjét és a betű-gyakoriságokat sem változtatja meg. 2012.szeptember


36

18

2012.09.26.

Egyszerű mátrixos transzpozíció Sorfolytonosan írják be a nyílt szöveget és oszlop-folytonosan olvassák ki a kriptogramot. Üres cellát nem hagynak. A kulcs:n. A kriptogram hossza mindig egy szorzat. Ez segíti a megfejtést is. A kriptogram kiolvasásához variálni lehet az oszlopok sorrendjét. A JBO szoftverek között van hozzávaló program. 2012.szeptember


37

Forgatható négyzetrács (1) Az 1. forgatási pozíció

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

2012.szeptember

Legyenek a nyílt szöveg betűi itt a természetes számok 1-től 36-ig. Az (itt) adott rács az első forgatási pozícióban kiválogatja a 2, 4, 6, 14, 16, 18, 26, 28, és 30 karaktereket. (Ezt a titkosítást írja le Verne Gyula a Sándor Mátyás c. regényében.) Árulkodó, hogy a kriptogram egy páros szám négyzete.


38

19

2012.09.26.

9 karakter kiválogatása a 2. forgatási pozícióban A nyílt szöveg második 9 karaktere 1 1

1 2

1 3

1 4

1 5

1 6

1 7

1 8

2. keverési transzformáció

1 0

2

4

6

14

16

18

26

28

30

8

10

12

20

22

24

32

34

36

a titkosított 36 karakteres blokknak a 2,4,6,...,26,28 30. helyeire kerül 2012.szeptember


39

Kommentárok (1) • A rácsot úgy kell megszerkeszteni, hogy minden egyes „válogató kivágás” csak egyetlen forgatási pizícióban válasszon ki egy meghatározott cellát. (Minden egyes cella csak egyszer legyen kiválasztva!) • Ha a nyílt szöveg rövidebb, mint a cellák száma, akkor jelentés nélküli, véletlen karakterekkel kell az üresen maradt cellákat kitölteni. • Ha a négyzetes mátrix sorai (és oszlopai) páratlan számúak, akkor a közepén lesz egy cella, amelyet mindegyik forgatási pozíció kiválaszt. 2012.szeptember


40

20

2012.09.26.

Kommentárok (2) • Az először bemutatott n-oszlopos mátrixszal való transzpozíció elég könnyen megfejthető. Nehezíthető, ha az oszlopok sorrendjét is változtatjuk a kiolvasáshoz. Árulkodó, hogy a kriptogram karakterszáma egy n×m-es szorzat. Ügyeljünk rá, hogy egyik se’ legyen prímszám. • Nem kell hozzá előre megadott ábécé és a nyílt szöveg betű-gyakoriságát sem változtatja meg egyik transzpozíciós módszer sem. 2012.szeptember


41

Kommentárok (3) • A (forgatható) négyzetrácsos keverés mellett más, geometriai alapú keverések is léteznek. Ezeket talán kissé nehezebb megfejteni, mint az n-oszlopos mátrixos keverést, de ma már nem gond. • A transzpozíció és a helyettesítés (szubsztitúció) egymás után, vegyesen is alkalmazhatók és a modern titkosító rendszerek közül sok esetben ez valóban így is történik. 2012.szeptember


42

21

2012.09.26.

Végső következtetetések • Jóllehet mind a helyettesítést, mind a keverést PC (mint papír-ceruza) módszerrel is könnyen kezelhetőnek tekintjük és • nagyon sok, elég ravasz változatuk létezik, ma már mindegyik elég könnyen megfejthető, távolról sem erős kriptorendszerek. • Az alkalmazott „kézi” módszerek miatt soroltam ezeket az ú.n. első generációs kriptorendszerek körébe. 2012.szeptember


43

KÖSZÖNÖM, HOGY MEGHALLGATTAK Jó lenne, ha az elmondottak (és a megadott linkekről letölthető segédszoftverek igénybe vételével) kipróbálnák ezeket a titkosítási módszereket. Szívesen válaszolok a kérdéseikre, amelyeket később, e-mailen is feltehetnek. ([email protected]). 2012.szeptember


44

22

A kiptográfia alapjai. Történet és alapfogalmak

Recommend Documents