Ľahký úvod do šifrovania

Ľahký úvod do ľahkého úvodu do šifrovania

Tento workshop bude prevažne teoretický. Jeho cieľom je priblížiť záujemcom princípy šifrovania. Hneď na začiatok však podotýkam, že moderná kryptografia (veda zaoberajúca sa šifrovaním) je veľmi komplikovaná a prešpikovaná matematikou, na akú ste na stredných školách pravdepodobne nenarazili. To čo si ukážeme s cieľom pochopiť princíp, nemožno preto považovať za vrchol kryptografie.

Keď už sme začali tými definíciami, tak v tom budeme ešte chvíľu pokračovať:

• Šifrovanie(kryptografia): oblasť zaoberajúca sa utajovaním informácií. Teda informáciu zakódujeme tak, aby bola skrytá pred zrakmy nepovolaných aby ju dokázal dešifrovať len povolaný.
• kryptoanalýza: Veda zaoberajúca sa lúštením šifier. Samozrejme máme na mysli lúštenie bez znalosti šifrovacieho kľúča, často aj bez znalosti o tom, aký šifrovací algoritmus (postup) bol použitý pri šifrovaní
• Kryptológia: Pojem zastrešujúci obe oblasti (kryptografiu a kryptoanalýzu)
• Správa: Nejaký text, ktorý budeme šifrovať
• kľúč: tajná informácia, ktorá je potrebná na zašifrovanie správy, resp na dešifrovanie zašifrovanej správy
• šifrovací algoritmus: Postup ktorý použijeme pri prevode správy na "tajnú" (zašifrovanú) správu

Substitučné šifry

Aká šifra vám napadne, ak sa pokúsite nejakú vymyslieť? Myslíte si, že braillovo písmo možno považovať za šifru? Možno povedať, že požiadavky na šifru spĺňa, ibaže ňou zašifrované texty dokáže dešifrovať každý, kto vie braillovo písmo.

Ako by ste popísali algoritmus na šifrovanie resp dešifrovanie textu zašifrovaného do braillovho písma?

Asi najjednoduchší popis je: Jednotlivé písmená v správe nahradíme podľa nasledujúcich pravidiel:

• a->1
• á->16
• b->12
• c->14
• č->146,
• ...

Ak by sme chceli takto "formálne" popísať proces dešifrovania, povedali by sme, že pri dešifrovaní treba pravidlá aplikovať "z prava doľava".

Zákerná otázka: Ako by ste dešifrovali nasledujúcu postupnosť?

12345

Vidíte ten problém s nejednoznačnosťou? Ako by ste ho vyriešili?

Vyššie popísanú šifru (braillovo písmo) môžme zaradiť medzi takzvané substitučné šifry. Ide o šifry, pri ktorých nahrádzame každé písmeno (alebo skupinu písmen) iným písmenom (alebo skupinov písmen). Braillovo písmo je pre nás čo ho poznáme veľmi jednoducho dešifrovateľná šifra. Vedeli by sme vymyslieť substitučnú šifru, ktorá by bola naozaj tajná? Čo by ste povedali na nasledovný algoritmus:

kľúč: nejaké číslo medzi 1 a 19375 ;)

Správa: Text bez diakritiky

Algoritmus: každé písmeno správy posunieme v abecede tak, že k jeho pozícii v abecede pripočítame kľúč.

Napríklad správa: "ahoj" kľúč: 3, tajná správa: dkrm

Zákerná otázka: ako by ste šifrovali text, ktorý obsahuje písmeno x,y, alebo z? pomôcka: z+1=a

Skúste si sformulovať algoritmus pre dešifrovanie cézarovej šifry (tak sa táto jednoduchá šifra volá).

Asi nieje ťažké predstaviť si, že takúto šifru dokážeme "rozbiť" aj bez znalosti kľúča. Napadá vám ako na to? Pomôcka: uvedomte si, že rôznych kľúčov síce existuje na prvý pohľad veľa (devetnásť tisíc čosi), ale takých ktoré dávajú pri použití šifrovacieho algoritmu rôzne výstupy je veľmi málo.

Skúsme si teraz premyslieť, ako vymyslieť substitučnú šifru, ktorú by sme nedokázali rozbiť bez kľúča. Ideálne by bolo vymyslieť ju tak, aby sme mohli mať viac možností vyberať si kľúč. Tým by sme spôsobili to, že metóda ktorú sme použili na rozbíjanie cézara (mimochodom volá sa brute force attack - hrubá sila) nebude také ľahké použiť, pretože ak by sme chceli vyskúšať všetky možné kľúče, zabralo by nám to veľmi veľa času. Celkom priamočiara možnosť je povedať si, že kľúč je ľubovoľná 26 znakov dlhá postupnosť, ktorá hovorí, ktoré písmeno nahrádzame ktorým. Napríklad kľúč

abcdefghijklmnopqrstuvwxyz

Je vlastne neutrálny kľúč, ktorý nám text nemení, pretože a nahrádzame za a, b nahrádzame za b a pod.

Uvedomme si, že takýto šifrovací algoritmus nám dáva na výber z 26 faktoriál rôznych kľúčov, čo by mohlo byť už dosť veľa. Pre priblíženie množstva kľúčov ktoré by sme museli vyskúšať:

Naša zemeguľa má v súčasnosti 6 miliárd obyvateľov. Ak by sme ich všetkých ukecali, aby skúšali kľúče a nejako im ich rozdelili, potom, ak by každý dokázal vyskúšať milión kľúčov za sekundu, tak by túto "zákazku" pre nás dokončili za 2131 rokov.

Pozornému čitateľovy však pravdepodobne neunikol ani fakt, že nie každý kľúč je rovnako dobrý a niektoré sú naozaj zlé.

Vedeli by ste nejako všeobecne povedať, ktoré kľúče sú zlé a akým spôsobom by ste takú nekvalitu kľúča testovali? Je dobrých kľúčov dostatok?

Skúsme teraz predpokladať, že máme rozumný algoritmus, ktorý nám umožňuje pri voľbe kľúča vyberať z veľkej množiny rôznych dobrých kľúčov. Trúfli by sme si povedať, že ním zašifrovaná informácia je bez znalosti kľúča naozaj bezpečne utajená? Napadá vám nejaký spôsob, ktorý by sme ešte mohli zvoliť a uhádnuť, čo sa v tajnej správe skrýva?

Jedna z jednoduchých metód, ktorá je na jednoduché substitučné šifry použiteľná sa volá frekvenčná analýza. Vychádza z toho, že ak máme text v konkrétnom jazyku, tak vieme o každom písmene povedať, ako často sa v texte v priemere vyskytuje. Napríklad v slovenčine sa jednotlivé písmená anglickej abecedy vyskytujú s nasledujúcou frekvenciou (v percentách):

• a:11,4
• b:2,0
• c:3,5
• d:3,6
• e:8,1
• f:0,1
• g:0,2
• h:2,4
• i:7,4
• j:2,0
• k:4,0
• l:4,9
• m:3,2
• n:5,5
• o:9,8
• p:3,1
• q:0
• r:4,3
• s:5,3
• t:5,0
• u:3,4
• v:4,7
• w:0
• x:0
• y:2,5
• z:3,5

Ak vieme vyššie uvedené údaje a zároveň vieme, že šifra ktorú lámeme obsahuje text v slovenčine, zašifrovaný jednoduchou substitučnou šifrou, potom nám stačí spárovať znaky s písmenami abecedy podľa výskytu. Najčastejšie vyskytujúce sa bude pravdepodobne a, druhé najčastejšie bude o,...

Frekvenčná analýza sa zdá byť pomerne silný nástroj, nieje však všemohúca. Vyskúšajte vymyslieť nejakú modifikáciu substitučnej šifry, ktorá by frekvenčnej analýze odolala. Pomôcka: striedanie viacerých kľúčov?

Tých, ktorím sa to podarí asi nepoteší informácia, že napriek tomu, že sa dá vymyslieť substitučná šifra, ktorú nieje ľahké rozbiť pomocou frekvenčnej analýzy sú substitučné šifry v súčasnosti považované za ľahko rozbiteľné a preto sa v serióznej kriptografii nepoužívajú. Šifry ku ktorým vás "navádza" posledná pomôcka sa nazývajú polyalfabetické substitučné šifry a liekom na ne je tzv Kasiskeho metóda.

Transpozičné šifry

Kvalitatívne sú rovnako nafigu ako substitučné a fungujú nasledovne. Správu ktorú šifrujeme transpozičnou šifrou nedopĺňame novými znakmy, ale znaky ktoré v správe sú vymieňame podľa nejakých rozumných pravidiel. Najjednoduchšie čo nám všetkým pravdepodobne napadne je písanie slov odzadu (joha ľetatič), vymieňanie dvojíc písmen (hajoč titaľe),...

Trošku zaujímavejšie už možno vyzerá toto:

atjjehoenxottytjoat.

Trúfate si? Pomôcka: Skúste si správu zapísať do nejakého obdĺžnika napr v excely. Alebo inak, čo ak treba zo správy čítať vždy len každé k-te písmeno? Ako zistíte, že cesta ktorou sa uberáte pravdepodobne nieje dobrá?

Čo by ste vedeli povedať o transpozičných šifrách a frekvenčnej analýze? Pomôže nejako?

Napadajú vám nejaké zaujímavé spôsoby transpozičného šifrovania?

O transpozičných šifrách možno povedať, že ich rozbíjanie už nieje len manuálna práca. Na substitučné stačí použiť hrubú silu, alebo frekvenčnú analýzu v kombinácii s inými relatívne jednoduchými metódami. Pri transpozičných šifrách treba text nejako skúmať, pre odborníkov však ani takéto šifry niesú vážnym problémom.

Produkčné šifry

Ide o šifry, ktoré kombinujú vyššie spomenuté metódy šifrovania v snahe dosiahnúť vyššiu bezpečnosť. Takéto šifry sa už považujú v súčasnosti za bezpečné a používajú sa. Jednou z nich je napríklad dobre známy štandard AES, o ktorom ste už pravdepodobne počuli. Ide o šifru, ktorá je v súčasnosti považovaná za prakticky nerozbiteľnú. V praxi to znamená, že neexistuje metóda, ktorou by sa dala dešifrovať správa bez znalosti kľúča v rozumnom čase.

Pri v súčasnosti používaných šifrách sa veľkosť kľúča vyjadruje v bitoch a veľkosť kľúča samozrejme určuje aj silu šifry.

Zjednodušene možno povedať, že šifra je dobrá, ak pri nevedomosti kľúča neexistuje iná možnosť dešifrovania textu, ako postupne vyskúšať všetky prípustné kľúče. Z toho vyplíva, že čím dlhší kľúč, tým dlhšie nám môže trvať, kým vyskúšame všetky. Napríklad už spomínané AES existuje v 3 verziách. AES128 používa 128 bitový kľúč, AES192 používa 192 bitový a AES 256 používa až 256 bitový kľúč. ak by sme teda chceli hrubou silou zistiť obsah tajnej správy zašifrovanej algoritmom AES256, museli by sme "vyskúšať" 2 na 256 rôznych kľúčov.

2 na 256 je už naozaj obrovské číslo. Predstaviť si ho vám možno pomôže informácia, že má 77 cifier. Alebo ak by sme si zas pomohli predstavou so všetkými obyvateľmi zemegule, pri čom od poslednej zákazky všetci trochu potrénovali a teraz sú schopní vyskúšať miliardu kľúčov za sekundu a navyše by sme predpokladali, že takých zemí existuje milión, tak by musel každý obyvateľ každej zemegule skúšať celé tisícročia, pri čom počet tisícročí na obyvateľa vyjadruje 41 ciferné číslo.

Kritérium dĺžky kľúča však nieje jediné určujúce kvalitu šifrovacieho algoritmu. Dôležité sú aj nasledujúce vlastnosti:

• Ak šifrujeme nejakú správu podobnými kľúčmi (kľúče volajme podobné, ak sa od seba líšia len málo, napríklad 1234 a 1235) tak sa výsledky po zašifrovaní na seba nepodobajú (ak toto neplatí, tak asi dokážete vymyslieť útoky na šifrovací algoritmus)
• ani 2 podobné správy sa na seba po zašifrovaní rovnakým kľúčom nepodobajú
• Zašifrovaná správa pôsobí ako náhodná, teda po zašifrovaní by nemalo byť možné nájsť vo výsledných dátach "nejakú logiku", pretože z tej sa dá veľmi často veľa vykryptoanalyzovať
• Kolízie kľúčov: Algoritmus by nemal umožňovať to, aby existovalo viacero kľúčov, ktorými by sa dal pri šifrovaní jednej správy dosiahnúť rovnaký výsledok. Čím viac kolíznych kľúčov existuje, tým väčšiu šancu máme na uhádnutie kľúča hrubou silou.

Vernamova šifra

ide o šifru, o ktorej nieje ťažké dokázať, že je nerozlúštiteľná. Jej princíp je veľmi jednoduchý a funguje nasledovne:

• Kľúč musí byť rovnako dlhý ako správa a musí byť úplne náhodný
• správu šifrujeme tak, že jednotlivé písmená v abecede posúvame podobne ako pri cézarovej šifre, ibaže číslo ktoré pripočítavame k pôvodnej pozícii písmena v abecede je náhodné.

Teda napríklad:

správa: ahoj

kľúč: 1,8,15,10

výsledok: bpdt

Opäť však treba zdôrazniť, že kľúč musí byť úplne náhodný (v príklade vyššie nieje, je dokonca logický) a musí byť rovnako dlhý ako správa. Náhodnosťou pri tom nemyslíme len tak hocijakú náhodnosť. Napríklad náhodné generátory v počítačoch sa za dostatočne náhodné nepovažujú, pretože sú predvídateľné, čo je dôvodom, prečo sa nazývajú pseudo náhodné.

Ďalším závažným obmedzením je, že jeden kľúč nemôžme použiť na zašifrovanie viacerých správ. Viete prečo? Tí čo vedia isto s potešením uhádnu kľúč a zistia, čo obsahujú nasledujúce 2 správy oddelené čiarkou, alebo si aspon premyslia, akým spôsobom sa dá niečo také zistiť:

kqcs, ggus

Uvedomte si, že pokiaľ máme len jeden zašifrovaný text, tak nemáme najmenšiu šancu ho uhádnuť, pretože neexistuje spôsob, ako by sme mohli bez kľúča zistiť, či sme uhádli ten správny text. Napríklad tajná správa bvsn

môže byť slovo auto, zašifrované kľúčom 1,1,1,1, aj slovo noha, zašifrované kľúčom 14, 7, 11, 13, alebo hocijaké iné 4 znakové slovo ku ktorému si poľahky vymyslíme kľúč.

Ak však máme k dispozícii viacero textov zašifrovaných tým istým kľúčom, potom sa nám pri odhalení kľúča blýska na veľmi dobré časi, pretože máme čo porovnávať a to sa nám nehodí len pri zisťovaní, či sme našli správny kľúč, ale aj pri hľadaní kľúča.

Možno vám napadá, že pri hádaní kľúča pri dešifrovaní správy by sa mohol dať využiť aj fakt, že nami nájdený text je zmysluplný. Teda že by nám mohlo postačiť, ak sme našli kľúč, po použití ktorého nám zo zašifrovanej správy vypadlo niečo zmysluplné. Tu si treba uvedomiť, že toto by nám naozaj mohlo na niečo byť len v prípade, že bol text pred zašifrovaním zmysluplný, nie najprv zašifrovaný nejakou inou šifrou.

Vernamova šifra sa napriek svojim vlastnostiam v praxi príliš nepoužíva, pretože:

• Vygenerovať náhodný kľúč nieje jednoduché (viď vyššie)
• kľúč musí byť obrovský (rovnako dlhý ako správa) a ak by sme dokázali taký kľúč bezpečne preniesť k príjemcovi, ktorému sa chystáme posielať šifrovanú správu, tak by sme mu mohli tým istým kanálom poslať rovno tú správu

Simetrické a asimetrické šifry

Doteraz sme sa bavkali len so šiframi, pri ktorých sa používal na šifrovanie aj dešifrovanie jeden kľúč. Takéto šifry sú veľmi užitočné, no majú jednu veľkú nevýhodu. Na to aby sme cez ne mohli komunikovať sa musíme s príjemcom našich správ dohodnúť na kľúči tak, aby sa k nemu nedostal nik iný, čo nemusí byť vždy možné. Takéto šifry sa nazývajú simetrické a patria medzi ne napríklad twofish, serpent, blowfish, ale aj AES, aj všetky ostatné vyššie spomenuté šifry.

Našťastie však existujú aj takzvané asimetrické šifry. Tie využívajú kľúče 2 (pomenujme si ich x a y) a fungujú tak, že ak správu zašifrujeme kľúčom x, možno ju dešifrovať len kľúčom y a naopak, ak správu zašifrujeme kľúčom y, dešifrovať sa dá len s použitím kľúča x. vďaka tejto vlastnosti už nepotrebujeme tajný kanál na výmenu kľúčov. Ak si chcú napríklad Ondrej a Marek (zhoda mien s menami inštruktorov resetu pseudonáhodná) posielať tajné správy, tak postupujú nasledovne:

• každý si vygeneruje svoje kľúče x a y
• Navzájom si pošlú kľúč x (ten je verejný a ich vôbec netrápi, či sa k niekomu dostane alebo nie)
• ak chce Ondrej napísať Marekovi, tak správu zašifruje Marekovím kľúčom x a pošle ju Marekovi. Správu teraz dokáže dešifrovať iba Marek, pretože jediný kľúč, ktorým sa dá správa dešifrovať je Marekov y, ktorý nikomu neprezradil
• podobne Marek šifruje Ondrejovím x, aby tajné správy určené pre neho dokázal dešifrovať iba on s použitím svojho tajného y.

No a keď už majú tie svoje vygenerované kľúče a rozhodli sa, že svoje x budú považovať za verejné, tak môžu urobiť všetko pre to, aby sa ich verejné kľúče dostali k čo najviac ľuďom a začať používať elektronický podpis. Ten môže fungovať nasledovne:

• Marek napíše mail a k svojej nezašifrovanej verzii priloží aj ten istý mail, zašifrovaný svojim súkromným kľúčom Y (v bežnej praxy sa z praktických dôvodov šifruje len nejaký výťah z mailu, ktorý sa generuje špeciálnou hash funkciou)
• Ondrej dostane marekov mail, a chce si overiť, či ho poslal naozaj marek. Zoberie teda zašifrovanú verziu, dešifruje ju s použitím marekovho verejného kľúča x a porovná ho s nezašifrovaným textom mailu ktorý dostal. Ak sa nezašifrovaný text a to čo ondrej dostal po dešifrovaní zhodujú, tak mail podpísal marek, pretože jediný kto mohol mail zašifrovať tak aby sa dal dešifrovať marekovim verejným kľúčom musel byť marek, alebo niekto, kto marekovi ukradol súkromný kľúč.

Medzi populárne asimetrické šifrovacie algoritmy patria napríklad RSA, asymetriu využívajú aj nástroje ako gpg, ssl/tls,...

Asymetrické šifrovanie sa často používa aj pri zahájení komunikácie komunikácie chtivými na to, aby sa mohli tajne dohodnúť na kľúči, ktorý budú potom používať pri komunikácii šifrovanej nejakou symetrickou šifrou. Dobre známy protokol sa nazýva Diffie-Hellman key exchange protokol a principiálne funguje nasledovne:

• Ondrej napíše správu, strčí ju do truhlice a truhlicu zamkne vysiacim zámkom, od ktorého má kľúč len on. Zamknutú truhlicu pošle marekovi
• Marek dostane truhlicu, ktorú nedokáže odomknúť. Zamkne ju teda aj on, opäť vysiacim zámkom, od ktorého má kľúč zase prezmenu len on a pošle ju späť ondrovi
• Ondro dostane truhlicu, odomkne a odníme svoj vysiaci zámok a pošle ju marekovi
• marek truhlicu odomkne a prečíta si správu.

Na prvý pohľad sa zdá, že správu si môže po tom, ako ju ondro strčil do truhlice prečítať už len marek. Ak by sa však medzi nich priplietol Fero, ktorý by truhlicu na ceste zastavil, zavesil na ňu svoj vysiaci zámok a poslal ju späť ondrovi, ten by ani netušil, že nekomunikuje s marekom. Ak by Fero túto škaredosť dotiahol do konca a najprv by zúradoval celú komunikáciu s odosielateľom, prečítal by si správu a následne by sa tváril so svojim zámkom že je odosielateľ a komunikoval by s príjemcom, tak by sa to nazývalo man in the middle attack a na to aby sme jej dokázali predijsť, musia byť marek aj ondro schopní s istotou spoznať zámky (marek ondrov a naopak).

Čo sa nevošlo

Strašne veľa:

• trošku chaotický článok na roote poskytne základné informácie o jednosmerných šifrách,
• toto čítanie (prelistujte aj iné články) zase ozrejmí rozdiel medzi blokovou a prúdovou šifrou
• Pri diffie-hellmanovi som si pomohol týmto článkom
• Informácie prešpikované históriou kryptológie sa dajú nájsť aj na tejto stránke
• a samozrejme množstvo informácií nájdete na kryptografickom rozcestníku anglickej wikipedie