kryp1

19. ledna 2010 v 0:33
Kryptologie - přednáška 01

Základní pojmy

- Kryptologie - věda o šifrování a utajování zpráv.
- Kryptografie - je to věda, která se zabývá tvorbou šifer. Změní obsah zprávy, ale neukrývá jej.
- Kryptoanalýza - zabývá se luštěním šifer.
- Steganografie - zabývá se ukrýváním zpráv. Nezmění obsah zprávy, ale snaží se jej ukrýt.

Kryptologie = Kryptografie + Kryptoanalýza + Steganografie

Otevřený text (OT) ==> Kodér (zakódování) ==> Šifrovaný text (ŠT) ==> Dekodér ==> Otevřený text
==> tzv přenosový kanál (je velkým problémem a slabinou - poruchy, šumy,...)

- Veřejný klíč - je to klíč, který dáváme veřejnosti k dispozici v rámci dané aplikace.
- Privátní klíč - (soukromý) je k dispozici pouze majiteli nebo konkrétní osobě v rámci dané aplikace.
- Tyto dva klíče tvoří tzv. "klíčový pár"
- Abeceda textu - je to množina všech znaků, ze kterých je vytvořena zpráva (jakákoliv diakritika, symboly, malá velká písmena,...)
- Statistická charakteristika textu (frekvenční analýza) - souvisí s tzv. četností výskytu znaků v abecedě textu. Každý jazyk na světě má jinou četnost výskytu znaků v abecedě. Každý jazyk také včetně nářečí. Dají se tím prolomit šifry nebo se dá přijít na to, o který typ šifry se jedná.

Historie

- první šifry - obrázky v jeskyních
- 500 př. n. l. - ATBASH - první šifra (jednoduchá substituční šifra založená na otočené abecedě).
- 400 př. n. l. - Řecko - první transpoziční šifry a stenografie.
- 50 př. n. l. - Řím - Caesarova šifra (posun v abecedě o 3).
- 4. století - Indie - Kamasutra (utajená komunikace).
- 10. století - Arabie - objev frekvenční analýzy.
- 13. a 14. století - Substituční šifry.
- 15. a 16. století - První návrhy šifer s heslama.
- 19. století - Prolomení šifer s heslama, rozvoj telegrafu, první mechanické přístroje.
- 1. a 2. světová válka - Komplikované šifry a mechanické přístroje (Enigma).
- 1969 - Shannonova teorie kódování a informace, rozvoj počítačů.
- 1973 - Objev kryptologie s veřejným klíčem.
- Od 90. let - Rozvoj kvantové kryptografie
- později rozvoj šifrování na principech teorie chaosu, fraktální geometrie, AI (Artificial Intelligence).


Dělení podle přenosu hesla

Symetrická
(tzv. neveřejná kryptografie) Pro šifrování i dešifrování se používá jeden jediný klíč. Výhodou je jednoduchost dešifrovacího algoritmu a také rychlost. Nevýhodou je však nutnost přenosu klíče. Při komunikaci s více stranami je nutností velké množství klíčů.

Asymetrická
(tzv. veřejná kryptografie) Využívá klíčový pár. Pro zašifrování veřejný klíč a pro dešifrování klíč privátní. Je důležité, aby z veřejného klíče nebylo možné poznat klíč privátní. Výhodou je předávání klíčů a to, že pro více uživatelů není potřeba více klíčů. Nevýhodou však jsou velké výpočetní nároky, nízká rychlost a nutnost kontrolovat a zabezpečit veřejný klíč.

Hybridní kryptografie
Propojuje symetrickou a asymetrickou kryptografii. Tzn. Vezme výhody z jedné a snaží se potlačit nevýhody druhé. Např. Asymetrickou přenese heslo a data přenese symetrickou.

Základní rozdělení šifer

- klasické (konvenční) šifry - staré šifry typu tužka papír
- kód - je to nahrazení určité skupiny slov nějakými znaky (hieroglyfické písmo, východní grafické písmo)
- šifra
- transpoziční - mění se pořadí znaků, ale jejich význam zůstává zachován
- substituční - pořadí znaků je konstantní, nemění se, ale mění se význam znaků
- monoalfabetické - znaková sada je použita pouze z jedné abecedy znaků
- polyalfabetické - je použito více znakových sad, pro dešifrování je pak potřeba znát heslo nebo klíč
- polygrafické - pro dešifrování znaků je potřeba např. Grafická závislost, matice, vektory
- mechanické šifry - pracují na principu hejblat (ozubená kolečka, lehké výpočetní algoritmy) např. Enigma
- moderní šifry - (křemíkový základ) pracují na základu výpočetní techniky
- asymetrické - viz. výše
- symetrické - viz. výše
- blokové - šifry se zpracovávají po částech (blocích)
- proudové - šifra se zpracovává v jednom celku (proudu)

Substituční (transkripční) šifry

!!! Jsou založené na principu, že něco substituujeme !!! Substituujeme jednu abecedu znaků za druhou. Pořadí znaků se nemění. Množiny znaků by měly být stejné.

Rozdělení
- monoalfabetické - substituujeme jednu abecedu jednou abecedou (nepotřebujeme heslo, klíč)
- polyalfabetické - jednu abecedu substituujeme pomocí více abeced pomocí nějakého pravidla (vyžaduje heslo, klíč)
- polygrafické - po substituci se využívají nějaká grafická pravidla (i z lineární algebry)
Kryptologie - přednáška 02

Monoalfabetická substituce

- Pevný posun (např. Caesarova šifra)
- Caesarova šifra - znamenala posun v abecedě o tři znaky vpravo (A → D, B → E, … , Y → B, Z → A).
- ROT13 - představovala posun (rotaci) v abecedě o třináct znaků.
- Převrácená abeceda
- např. ATBASH (A → Z, B → Y, C → X, … , X → C, Y → B, Z → A).
- Lineární posun
- fce linearni posun ax+b mod 26 přestavuje základ pro vytvoření a luštění těchto šifer. Za a a b dosadíme libovolná celá čísla. Znaky abecedy označíme 0-25 (A → 0, B → 1, … , Z → 25). Za X poté dosadíme index daného písmena v abecedě a vypočítáme výraz. Vyjde nám číslo 0-25. Podle toho určíme daný znak v abecedě.
- Využití klíčového slova
- Zvolíme si klíčové slovo, které obsahuje každý znak pouze jednou. Toto slovo postavíme na začátek abecedy a za něj budeme psát znaky abecedy tak, že vynecháme ty znaky, které jsou již obsaženy v klíčovém slově.
Např. zvolíme si např. jako klíčové slovo "Petrklic"

Frekvenční analýza jazyka - Pomáhá při luštění monografických šifer. Podle statistik se v každém jazyce objevují každé znaky s různou četností. Když použijeme frekvenční analýzu, vytvoříme tzv. "histogramy", které nám udávají v grafickém podání (v %) četnost znaků v dané abecedě a nebo šifře. Porovnáme-li tedy vytvořené histogramy (jazyka a šifry) můžeme podle četnosti daných znaků určit, který znak patří danému znaku. Frekvenční analýza také pomáhá určit, zda se jedná o šifru substituční, nebo transpoziční. Kdyby totiž byly histogramy stejné, jednalo by se o šifru transpoziční. Je to proto, protože při transpozici se nemění znaky, ale pouze jejich pořadí.

Polyalfabetická substituce

Je založena na 26 monoalfabetických substitucích (každá abeceda je posunutá o jeden znak v abecedě). Polyalfabetická substituce využívá heslo (klíčové slovo). Při šifrování i dešifrování je nutná tabulka, tzv. Vigenerův čtverec, nebo tzv. tabulka RECTA. Tato tabulka je symetrická. Nezáleží tedy na přeházeni

souřadnic HESLO / TEXT. Pokud však zaměňujeme jednotlivé řádky nebo sloupce, máme v podstatě nekonečně mnoho možností šifrování.
Princip je takový, že napíšeme text a pod něj vložíme klíč, klíč je periodický (musí se stále opakovat pod celým textem). Poté bereme písmena z textu a klíče jako souřadnice šifrovaného textu. Zde již nefunguje frekvenční analýza. V momentě, kdy zjistíme délku hesla není již těžké šifru rozluštit.
Klíč musí opět každý znak obsahovat pouze jednou.

… otevřený text
… zvolený, periodicky opakovaný klíč

Polygrafická substituce

- Playfair (anglický čtverec)
- byla založena na tabulkovém grafickém principu (tabulka 5 x 5). V této tabulce se do každé kolonky doplnil znak abecedy. Jelikož má tabulka pouze 25 kolonek bylo ustanoveno, že každá abeceda spojila málo používaný znak s jiným. Např. česká abeceda spojila W a V do V, anglická I a J do I. Nejprve do tabulky vložíme klíčové slovo, poté abecedu bez znaků obsažených v

klíčovém slově. Šifrovaný text rozdělíme na dvojice znaků. Pokud jsou ve dvojicích dva stejné znaky rozdělíme "x" např. ee = ex e, pokud máme lichý počet doplníme nakonec "x".


Platí tři pravidla:
1. Jestliže znaky (dvojice) leží na stejném řádku tabulky, zašifrují se o jeden znak vpravo (pokud jsme na konci tabulky, posouváme se na stejném řádku opět doleva).
2. Jestliže znaky v bigramu leží ve stejném sloupci, nahradíme je symbolem, který leží o jeden níže (jsme-li opět na konci tabulky posouváme se nahoru na její začátek, ovšem stále zůstáváme v jednom sloupci.
3. Jestliže leží každý na něčem jiném. Nahradíme je symbolem, který leží na stejném řádku, ale ve sloupci druhého písmena z dvojice ("ab" hledám a druhé je b, hledám b druhé je a).
- BIFID
- Vytvoříme opět tabulku 5 x 5 s tím, že první znaku v tabulce patří opět klíči, další jsou zbylé znaky abecedy. Prostě stejně jako u "anglického čtverce". Tabulku označíme souřadnicemi. Text rozdělíme po pěticích a vypíšeme souřadnice znaků (řádek x sloupec). Souřadnice pak vezmeme a napíšeme vedle sebe. Rozdělíme na dvojice čísel a vyhledáme souřadnice v tabulce (řádek x sloupec).

- Hillova šifra
- Nejdříve si zvolíme délku bloku zprávy (např. 3). Zvolíme matici stupně n, která nesmí být singulární (např. 3 x 3). Data pak zapíšeme jako vektor o délce n v rozmezí abecedy 0-25 (A=0, B=1, …, Z=25). Šifrovaný text pak vznikne na základě tohoto vzorce pokud vynásobením matice a vektoru vzniknou nějaká záporná čísla, přičteme k nim číslo 26.

Ostatní substituce

• Více šifer za jedno písmeno (tabulka 4x7, nebo-li jedno a dvoumístné šifry). Symboly, které jsou v prvním sloupci mají jen jednu souřadnici (proto jedno a dvoumístné). Souřadnice se nemohou přehodit a lehce zaměnit (jednoznačnost).

• Autokláv - šifra, která se snažila odstranit nevýhodu polyalfabetické šifry (Vigenerovi tabulky) s periodičností hesla (aby se stále neopakovalo). Klíčové slovo zde slouží pouze pro nastartování substituce.
◦ verze otevřený text (za klíčové slovo dáme šiforvaný text)
◦ verze otevřený text (za klíčové slovo dáme původní text)

• Homofoní substituce - zamlžení frekvenční analýzy, měla složitý klíč a ten byl založen na tom, že čím početnější byla četnost znaků, tím více způsoby se šifrovalo, obrovská pravděpodobnost chyby. Časem upadla.
• Využití nomenklátoru, klamačů a zkomolenin
◦ nomenklátor - zástupný symbol, který zastupuje něco, co se vyskytuje často (např. the zastupovalo x) tím se zkreslila frekvenční analýza.
◦ klamač - speciální symbol se zvláštním významem (např. x znamená ignoruj dalších 5 znaků, j říkalo např. smaž předcházející symbol apod.)
◦ zkomoleniny - např. dětská šišlavá řeč
• Knižní šifra - např. frekvence čísel 351456, která po domluvě znamená "třetí řada, pátá kniha, první stránka, čtvrtý řádek, páté slovo a šesté písmeno. Klíč musí být domluvený a předpokládá se, že oba majitelé mají stejná vydání knih.
Kryptologie - přednáška 03

Transpoziční šifry

- obecná transpozice v tabulce (používá se bez využití hesla)
- jednoduchá transpozice v tabulce s klíčem
- dvojitá transpozice (popř. se dvěma hesly)
- zubatka a ostatní.

Obecná transpozice v tabulce

V podstatě se jedná o to, že text jinak napíšeme a jinak přečteme. Příkladem může být text psaný do sloupců a čtený po řádcích.
Př. transpozice typu "zábradlí"
Př. Jednoduché transpozice v tabulkách:
Existují různé způsoby, v podstatě máme nekonečně mnoho možností. Druhá strana by však měla o způsobu jakým byla šifra provedena vědět.

Transpozice v tabulce s heslem

Pro šifrování využívá heslo (klíčové slovo). Sloupce jsou setříděny podle abecedního pořadí znaků v hesle. Získáme transponovaný text, který dešifrujeme poskládáním sloupců do klíčového slova.
text:
klíč:
Vytvoříme tabulku m x n, kde "m" jsou řádky tabulky (získáme je tak, že vydělíme délku textu klíčovým slovem a zaokrouhlíme nahoru). Délka klíčového slova musí být menší než délka znaků textu, aby byla vytvořena tabulka. A "n" označuje počet sloupců tabulky (počet prvků v klíčovém slově).

Zaokrouhlením nám v tabulce vzniknou prázdné znaky. Tyto prázdné znaky zaplníme libovolným textem.
text:
klíč:
Pak např. přečteme text po sloupcích a máme zašifrovaný text.
V případě, že heslo obsahuje více stejný znaků, tak záleží na pořadí znaků. Znaky řadíme podle abecedy a to tak, že je čteme od leva.

Jednoduchá transpozice v tabulce s dvěma hesly

V podstatě jde o stejný princip jako v předcházejícím případě, navazuje na to však ještě jedno heslo.
První klíčové slovo ovlivnilo sloupce, druhé tedy ovlivní řádky. Je důležitý aby druhé klíčové slovo mělo stejný počet znaků, klik má tabulka řádků.
Pokračování příkladu z předchozího:
druhé klíčové slovo:
Pak text přečteme opět např. po sloupcích.

Dvojitá transpozice s jedním heslem

Znamená, že všechno z předchozích příkladu se opakuje dvakrát s jedním klíčovým slovem. Při určování dalšího (druhého) klíčového slova už nesmíme doplňovat prázdné znaky (nevycházelo by to při dešifrování). Klíčové slovo musí tedy být buď stejně dlouhé, nebo musí vydělením (text/klíč) vyjít celé číslo. Toto je důležitá podmínka. Můžeme opět použít i stejné heslo jako poprvé.

Zubatka

Jde o tabulku m x n, kde m > n (kde m = délka textu / délka klíčového slova, n = klíčové slovo).
klíčové slovo:
Tabulku pak rozdělíme na zuby podle klíčového slova. Zapíšeme text a to tak, že nejprve vyplňujeme horní část tabulky a poté její spodní část. Text pak rozdělujeme podle délky hesla.

Ostatní (Kardanova mřížka)

Text zapíšeme do tabulky která se dělí 4. Např. 8x8 nebo 4x4. Máme šablonu, do které jsme vystříhali
m2 x 4 děr (díry v šabloně nesmí být symetrické), pak přikládáme šablonu a otáčíme s ní v tabulce a opisujeme znaky co jsou viděť.
- Text se zapisuje do tabulky a opět se z ní přes šablonu čte.
- Nebo přes šablonu zapisujeme do tabulky a pak čteme text.
Kryptologie - přednáška 04

Fraktální geometrie

Stručná historie

- 1872 - První fraktál Cantorova množina (diskontinuum)
- 1907 - Brownův pohyb (částice v kapalině opisuje určitou trajektorii - tento pohyb je tedy určitým typem fraktálu), Kochova křivka (říká, že sněhová vločka je fraktál)
- 1919 - Hausdorfova dimenze komplexních geometrických útvarů - definuje dimenzi mezi standardními dimenzemi. Standardní dimenze jsou 2D, 3D... a mezi nimi může např. být 2.3D apod.
- 1975 - První použití označení slovem Fraktál
- 1977 - Mandelbrotovy fraktály
- 1983 - Souvislost mezi fraktály a podivnými atraktory
- 1984 - Dynamika konečných atomů
- 1986 - Vznik IFS algoritmů
- 90. léta až do posud - Použití fraktálů k vysvětlení nejrůznějších otázek

Základní fraktály

- Cantorova množina - Nejstarší fraktál, který vznikne tak, že máme přímku, kterou rozdělíme na třetiny a prostřední část vymažeme a tak to pokračuje dál.

- Pythagorův strom - Vznikne tak, že sestavíme čtverec, nad nám vztyčíme rovnoramenný trojúhelník, na jeho přeponách opět nakreslíme čtverec a tak pokračujeme stále dal...

- Sierpinského trojúhelník - Vytváří se tak, že sestrojíme pravoúhlý rovnoramenný trojúhelník. Označíme středy jeho stran a sestrojíme v něm další trojúhelník a tak pokračujeme dal...

- Sierpinského čtverec - Čtverec rozdělíme na devět částí a smažeme prostřední, v těchto částech opět rozdělíme na devět částí a opět smažeme střed, atd...

- Kochova vločka (křivka) - Vezmeme úsečku a smažeme její střední část, v této části vztyčíme rovnoramenný trojúhelník, pokračujeme tak dále....


Definice fraktálu - Fraktál je objekt jehož geometrická struktura se opakuje v něm samém.

Fraktály jsou založeny na existenci metrických prostorů a ty na existenci množin a jejich prvků. Dělíme je:

- soběpodobné fraktály - zmenšená kopie mateřského tělesa je přesnou kopií, nevyskytují se v přírodě, jsou jen uměle vytvořeny
- soběpříbuzné fraktály - zmenšená kopie mateřského tělesa je podobná, tyto objekty se vyskytují hojně v přírodě (např. vítr ohne jednu stranu stromu jinak než druhou, oblaka, skály, pobřeží...)

Konstrukce fraktálů a fraktálních množin

Při konstrukci fraktálů používáme dva algoritmy IFS (Iterační funkční systémy) a TEA (Polynomické fraktály). IFS tvoří černobíle fraktály na základě afinních transformací. TEA tvoří barevné fraktály na základě iterace komplexních fcí.

IFS lez rozdělit ještě na dvě skupiny. HIFS (Hierarchický IFS) a Stochastický IFS (nebo-li hra chaosu).

afíní transformace (grafické transformace nad objektem)

Algoritmus IFS

Konstrukce fraktálů pomocí tzv. Afinních transformací (libovolná grafická transformace) nad objektem (mění polohu, tvar a velikost tohoto objektu).


kde definuje úhel otočení ve směru osy x
definuje úhel otočení ve směru osy y
definuje úhel škálování ve směru osy x
definuje úhel škálování ve směru osy y
definuje posun ve směru osy x
definuje posun ve směru osy y

Algoritmus HIFS

- Používání transformací s ohledem na uživatelsky zadané pravděpodobnosti pro každou transformaci.
- V podstatě je kombinací několika IFS v různých úrovních.
- Tvoří sobě příbuzné fraktály.
- Netvoří transformace jen z jednoho, ale sem tam i z jiného definování. Tvoří se podle nějaké pravděpodobnosti.
- Na rozdíl od následujícího přepíná mezi různými možnostmi, SIFS vynechává a to HIFS nedělá.

Stochastický IFS

- Používání koeficientů afinních transformací s ohledem na uživatelsky zadané pravděpodobnosti pro každý koeficient afinní transformace.
- Např. máme čtyři transformace a definujeme pravděpodobnosti 1, 2, 3 a 4. Některé sem tam vynecháváme. Dalo by se to přirovnat k evoluční mutaci v přírodě.

Juliovy a Mandelbrotovy množiny (základ pro TEA)

Juliovy množiny jsou vytvářeny pomocí iterace funkce komplexní paraboly. Zn+1=Z2n+C, kde Zn i C jsou body ležící v komplexní rovině. Počáteční hodnota Z0 je zvolená, C také a zůstávají po celou bodu konstantní.

Juliova množina je definovaná jako množina všech komplexních čísel Z0, po kterých posloupnost Zn nediverguje (neutíká do pryč).

Juliovy množiny tvoří hranice mezi body, ze kterých trajektorie uniká do nekonečna a body, jejichž trajektorie je omezená a tedy konverguje k nějakému pevnému bodu (či cyklické trajektorie).

Dělíme je na souvislé a nesouvislé (nesouvislé jsou když jsou černé plochy nespojené).
Příklady:


Mandelbrotova množina je speciálním případem Juliových množin, kdy Z0 je nulové a C vybíráme z černé množiny (pokud z černé získáme souvislou, jinak nesouvislou). Říkáme, že je katalogem Juliových souvislých množin.

Algoritmus TEA(Time Escape Algorithm)

Provádí dané iterace až do překročení hranice nebo do vyčerpání maximálního počtu iterací. Je založený na předpokladu úniku dané trajektorie ze zvolené oblasti, která je částí komplexní roviny. Volba barev závisí na každém různém uživateli. Pokud je trajektorie neustále v dané oblasti, tak se zadanému startovnímu bodu přiřadí černá barva.
Kryptologie - přednáška 05

Vlastnosti fraktálů

- Kontrakce - (stažení, smrštění) Transformace s kontrakcí ve fraktálním prostoru má za následek vznik zmenšeného původního tělesa. Na metrickém prostoru má za následek vzniku pevného bodu, limitního bodu, atraktoru...
- Kondenzace - (sražení) Umožňuje konstruovat fraktální skupiny ve fraktálním prostoru (vznik kondenzačních množin).

Fraktální dimenze (Hausdorfova - Besovicova dimenze)

Fraktální dimenze udává, jak moc dané těleso zaplňuje příslušnou dimenzi. Eukleidovská (klasická) dimenze je pouze limitním případem fraktální dimenze.

Fraktální dimenze říká, jak dané těleso zaplňuje určitý prostor (např. 2,8 je více prostorové než plošné, ale patří do obou).

Při zmenšování měřítka dochází ke zvyšování obvodu tělesa k nekonečnu (Richardsonův efekt). Je to rozdíl oproti klasické geometrii, bo když se blížíme stále blíž dostaneme se k nějaké limitní hranici.

Fraktální interpolace

Interpolace znamená prokládání nějakých dat křivkou (interpolujeme data). Eukleidovská interpolace znamená prokládání nějakými klasickými geometrickými tělesy (přímka, parabola, kruh...). Fraktální interpolace se provádí křivkou s fraktálním charakterem. Fraktální křivka je jedinečná (např. jako otisk prstu). Podle této jedinečnosti jsme pak schopni identifikovat např. přístroj, nebo metodu výroby...

Podobným pojmem je Extrapolace, tou dokážeme odhadovat budoucí vývoj.

Rekonstrukce fraktálů (inverzní fraktální problém)

Rekonstrukce fraktálů je proces, při němž je cílem nalézt koeficienty afinních transformací generující daný objekt. K nalezení používáme následující metody:

- Kolážový teorém - Využívá Hausdorfovu vzdálenost, jež udává rozdíl mezi originálním obrazcem a fraktálem s odhadnutými koeficienty (koláží).
- Evoluční algoritmy - Metoda optimalizace s využitím umělé inteligence - minimalizace rozdílu mezi originálem a fraktálem generovaným pomocí odhadovaných parametrů. (evoluční algoritmy jsou založeny na Darwinově evoluční teorii).

Fraktály v časových řadách - Eliotovy vlny

Bylo zjištěno, že celá řada jevů v pohledu časové křivky má fraktální charakter. V mnoha časových řadách vznikají fraktální prvky a nazýváme je Eliotovy vlny. Tyto vlny mají vlny mají dvě fáze - Impulzní (5 vrcholů) a Korekční (vyrovnávací, která má 3 vrcholy).

Fraktálová komprese

Využívá významu kolážové věty tzv. dekompozici obrazu (obrazově závislé a nezávislé metody). Nezávislé (je jedno jaký je obraz a pak jej rozsekáme na jiné části) a Závislé (zde jsou např. důležité podobnosti jako je barva, stín apod).
- Jacquinův kódovací algoritmus - založen na hledání podobností bloků. Hledáme zmenšené podobné prvky. Pak ukládáme informace o tom, jak je obraz podobný, natočený apod. Popíšeme do matice, uložíme do vektoru. Ten nám říká jaké jsou závislosti mezi bloky a jak jsou transformovány.

Fraktální šifrování

Převod písmen do matice afinních transformací. Šifrou jsou koeficienty afinních transformací. Data se dají zašumět, a to tak, že každý blok posuneme o milimetr. Text stále přečteme, ale čísla jsou pokaždé jiná (nefunguje tedy frekvenční analýza).

Úvod do Neuronových sítí

- Nazývány Artificial Neural Networks (ANN)
- Neuronová jednotka - má několik vstupů(x), váh (w), jednu přenosovou fci (TF), práh (b) a nakonec vyhodnotí výstup (Y).

Váhy jsou jakoby ladění (např. u dětí ukážeš banán, řekne pomeranč, pleštíš mu dokud neřekne banán, tzv proces učení). Máme vzorovou množinu, máme vstup, pokud vyhodí jinou než vzorovou, tak upravíme váhu, takto postupujeme dokud výstup nebude odpovídat vzorové množině.

- ANN - se skládá z neuronových jednotek.
- Neuronová síť se používá ke složitějším řízením (např. autopilot).
- Dá se naprogramovat i v excelu (ovšem v uvozovkách).

Neurofraktální šifrování

Využívá fraktální šifrování → např. máme znaky a a b každému přiřadíme náhodný binární vektor a neuronová síť nám jako výstup vrátí koeficienty posunutí (e, f).

Šifrou jsou tedy binární vektory a váhy sítě (tzv. dvojité šifrování).

Jak to funguje →
Výhodou je robustnost, bo při opakování znaků se sít učí pokaždé jinak (frekvenční analýza je tedy v pytlu). Velkou nevýhodou je však časová náročnost.
Kryptologie - přednáška 06

Moderní kryptologie

- Počátky moderní kryptologie
- 1917 - Vilbert Vernam - patentovaná nová proudová šifra, později známá jako "One-time Pad". Do teď je matematicky dokázáno, že je neprolomitelná.
- 1948 - Claude Elwood Shannon - byl zlomem v historii kryptografie. Pronesl: "Síla algoritmu spočívá na pilířích matematické složitosti a ne na tajnostech kolem něj."

Vernamova šifra (původní konvenční typ)

V podstatě se jednalo o upravenou Vigenerovu šifru. Spočívá v posunu každého znaku zprávy o náhodně zvolený počet míst v abecedě. To se prakticky rovná náhradě zcela náhodným písmenem a na tomto faktu je založen důkaz že je neprolomitelná.

!!! Použil se náhodný klíč (text), který je stejně dlouhý jako délka textu (Vigenerova šifra s náhodným heslem) !!!

Jednoduchý algoritmus → (Znak + klíč) mod 26 (znak, jako pořadí znaku v abecedě a u klíče stejně tak).
Dešifrování → (Znak - klíč) mod 26

Nepoužívá se → bo vyžaduje dostat klíč ke druhé straně (vyžadovala spolehlivého kurýra). Je silně nepraktické pokud je klíč stejně dlouhý jako text.

Vernamova šifra (moderní typ)

Operace XOR mezi náhodným klíčem s normálním rozložením a stejnou délkou jako šifrovaný text.

Výhodou je, že stejný algoritmus se dá použít pro zašifrování i dešifrování. Velmi velký klíč je běžně přenášen nenápadně pomocí zdánlivě nenápadných medií a zařízení.

XOR
Vstupy
Výstup
1
1
0
0
0
0
0
1
1
1
0
1

Velkou nevýhodou je, že každé heslo (klíč) se mohlo použít pouze jednou, tedy pro dvě zprávy se nepoužívá stejný klíč, protože jinak by se jednalo o knižní šifru, kvůli vlastnostem modulární aritmetiky a vlastnostem fce XOR.

Vlastnosti Ver. šifry:

- klíč je stejně dlouhý jako text
- klíč je dokonale náhodný (ne pseudonáhodný - tedy nepoužívá nějaký algoritmus) - vytvářejí ho např. tepelné změny
- klíč nelze použít opakovaně (náhodnost vypadne)
- frekvenční analýza je naprd
- útok hrubou silou je k ničemu (je téměř nekonečné množství klíče)

One-way functions (jednosměrné, jednocestné fce)

- Asymetrická kryptografie (dva klíče).
- Jsou to fce, kterou je snadné spočítat a všeobecně se věří, že je těžké ji invertovat bez dodatečné informace navíc.
- Jednosměrné fce s padacím zámkem (trap door) - př. poštovní schránka
- Míchání barev - smíchat barvy dohromady, ale pak už není možné zjistit z jakých.
- Telefonní seznam - snadno se hledá podle jména a adresy, ale hledat podle telefonního čísla je složitější, když chceme najít jméno a adresu.
- Násobení a zpětná faktorizace - není problém vynásobit, ale pak zjistit ze kterých čísel násobek vznikl.
- Diskrétní log. a exponenciál - je možné logarit. spojitou, ale ne diskrétní fci.
- Modulární aritmetika
asi priklady pro jednosměrné hešování(funkce) - Message-Diget algorithm (MD2, MD4, MDS), Secure Hash Algorith (SHA-1, SHA-2)
 

2 lidé ohodnotili tento článek.

Komentáře

1 xy xy | 30. března 2010 v 16:02 | Reagovat

dík

Nový komentář

Přihlásit se
  Ještě nemáte vlastní web? Můžete si jej zdarma založit na Blog.cz.
 

Aktuální články

Reklama