Základy kryptologie

Základy kryptologie

Definice kryptologie. Historický přehled utajovacích metod.

Šifry: záměnné, transpoziční, heslové, strojové.

Shannonova teorie bezpečnosti šifer.

Difúze a konfúze. Klasifikace tříd složitosti algoritmů.

Prvočísla důkazy prvočíselnosti, rozklad na prvočinitele, prvočísla v kryptografii.

Generace náhodných bitů metody generování náhodných bitů, testování kvality posloupností náhodných bitů, využití posloupností náhodných bitů v kryptografii.

Kryptografie neboli šifrování je nauka o metodách utajování smyslu zpráv převodem do podoby, která je čitelná jen se speciální znalostí.

Slovo kryptografie pochází z řečtiny – kryptós je skrytý a gráphein znamená psát.

Někdy je pojem obecněji používán pro vědu o čemkoli spojeném se šiframi jako alternativa k pojmu kryptologie.

Kryptologie zahrnuje kryptografii a kryptoanalýzu, neboli luštění zašifrovaných zpráv.

Základní pojmy

Šifra nebo šifrování budeme označovat kryptografický algoritmus, který převádí čitelnou zprávu neboli prostý text na její nečitelnou podobu neboli šifrový text.
Klíč je tajná informace, bez níž nelze šifrový text přečíst.
Symetrická šifra je taková, která pro šifrování i dešifrování používá tentýž klíč.
Asymetrická šifra používá veřejný klíč pro šifrování a soukromý klíč' pro dešifrování.
Hašovací funkce je způsob, jak z celého textu vytvořit krátký řetězec, který s velmi velkou pravděpodobností identifikuje nezměněný text.
Certifikáty a elektronický podpis jsou softwarové prostředky, které umožní šifrování textu.

Starší sestrou kryptografie je steganografie neboli ukrývání zprávy jako takové.

Sem patří různé neviditelné inkousty, vyrývání zprávy do dřevěné tabulky, která se zalije voskem apod.

V moderní době lze tajné texty ukrývat například do souborů s hudbou či obrázky namísto náhodného šumu.

Šifry: záměnné, transpoziční, heslové, strojové.

Substituční (záměnné) šifry
Substituční šifra obecně spočívá v nahrazení každého znaku zprávy jiným znakem podle nějakého pravidla.

Posun písmen
Caesarova šifra je pojmenovaná po Juliu Caesarovi, který ji pravděpodobně používal jako první.
Každé písmeno tajné zprávy je posunuto v abecedě o pevný počet pozic.
Šifra je z dnešního pohledu velmi snadno luštitelná, protože je jen málo možných klíčů.
Ve své době ale představovala nevídanou metodu a osvědčila se velmi dobře.

Příklad tabulky záměny, s použitím slova VESLO jako klíče:

Vigenèrova šifra

Jedná se o speciální případ polyalfabetické šifry.

Vigenèrova šifra používá heslo, jehož znaky určují posunutí otevřeného textu a to tak, že otevřený text se rozdělí na bloky znaků dlouhé stejně jako heslo a každý znak se sečte s odpovídajícím znakem hesla. Vigenèrova šifra způsobuje změny pravděpodobnosti rozložení znaků a tím podstatně znemožňuje kryptoanalýzu na základě analýzy četnosti znaků v textu.

Příklad s použítím slova HESLO jako klíče k zašifrování:

otevřený text

klíč

šifrový text

Vernamova šifra

je anglicky často nazývaná one-time pad, v českém překladu jednorázová tabulková šifra.

Jde dosud o jedinou známou šifru, o níž bylo exaktně dokázáno, že je nerozluštitelná.

Podobně jako Vigenèrova šifra i tahle spočívá ve sčítání písmen otevřeného textu a hesla, avšak heslo je blok náhodně zvolených dat o stejné velikosti jako je otevřený text.

Pokud jsou splněny podmínky zcela náhodného klíče o stejné délce jako zpráva sama (a není použit opakovaně), je tato šifrovací metoda absolutně bezpečná.

Délka klíče však pro běžné účely použití této metody zpravidla znemožňuje, metoda se používá hlavně pro velice specializované účely, např. tzv. horká linka spojující za dob studené války Moskvu a Washington používala Vernamovu šifru. D

Transpoziční šifry

Transpozice neboli přesmyčka spočívá ve změně pořadí znaků podle určitého pravidla.

Například tak, že otevřený text je zapsán do tabulky po řádcích a šifrový text vznikne čtením sloupců téže tabulky.

Transpoziční mřížka

Tabulka, v níž jsou některá políčka vystřižena a do těchto je vpisován otevřený text.

Po zaplnění všech políček je tabulka otočena o 90° a postup se opakuje.

Tuto šifru použil Jules Verne ve své knize Matyáš Sandorf (Nový hrabě Monte Christo).

Jsou možné i jiné tvary tabulky než čtverec. Například lze použít šestiúhelník se šestiúhelníkovými políčky, který se 5× otáčí o 60°.

Klíčem této šifry je rozložení vystříhaných políček.

Příklad transpoziční mřížky (horní strana je označena červeně pro snazší orientaci a použití)

Šifrování strojem
Použití mechanických a elektronických strojů přineslo do šifrování zcela nové možnosti.
Zejména proto, že stroje jsou schopny velkého počtu opakování určitého úkonu v krátkém čase.

Enigma
Německo za 2. světové války používalo k utajování zpráv mechanický stroj Enigma, který prováděl poměrně složité operace se vstupním textem, ale zároveň se dal poměrně snadno ovládat.
Poláci ovšem ještě před vypuknutím války pracovali na prolomení šifry a jejich zjištění byla později nedocenitelná pro spojenecké armády.
Šifra byla již během války zlomena a poskytovala tak německé straně pouze falešný pocit bezpečí.
Nutno ovšem dodat, že prolomení Enigmy bylo ve své době možné pouze díky nevhodným a nedostatečně propracovaným postupům při jejím používání jako byly např. nevyužití maximálního možného zabezpečení poskytovaného propojovací deskou (Steckerbrett), opakování tříznakového klíče na začátku každé zprávy, snadno odhadnutelné fráze v textu apod.
Pokud je Enigma používána správně, není rozluštění jejich zpráv triviální záležitostí ani při použití dnešní výpočetní techniky.
Enigma měla původně 3 rotory, které se otáčely, podobě jako mechanické počítadlo a každý měl jinak propojené vstupní a výstupní kontakty, tím se měnil průběh proudu a i výsledné písmeno zašifrovaného textu.
Později začalo ponorkové námořnictvo používat čtyřrotorové Enigmy a stroj byl zdokonalován i zaváděním dalších prvků (Uhr Box a. j.).

Shannonova teorie bezpečnosti šifer

Všechny klasické šifry (s jedinou výjimkou Vernamovy šifry) mají tu vlastnost, že čím delší je šifrový text, tím snazší je šifru rozluštit.

Shannonova teorie vysvětluje, proč tomu tak je.

Vzdálenost jednoznačnosti (Unicity Distance = UD)
- Intuitivně můžeme posoudit, proč delší šifrový text poskytuje více informací o otevřeném textu.
- Použijeme-li jednoduchou záměnu, pak ze šifrového textu o délce jednoho písmene U nemůžeme usoudit vůbec nic o příslušném otevřeném textu.
- Ze šifrového textu o dvou písmenech UV už můžeme usoudit, že příslušný otevřený text není složený ze dvou stejných písmen.
- Máme-li smysluplný otevřený text v přirozeném jazyce o délce dejme tomu 500 písmen, pak si lze těžko představit, že by mohla existovat nějaká permutace písmen, která by jej opět proměnila v jiný smysluplný text v otevřeném jazyce.
- Proto k šifrovému textu o 500 písmenech může existovat nejvýše jeden smysluplný text v přirozeném jazyce, který nějakou jednoduchou záměnou vede k tomuto šifrovému textu.
- Nejmenší délka šifrového textu, ke kterému existuje jednoznačně určený smysluplný otevřený text, se nazývá vzdálenost jednoznačnosti.
- Vzdálenost jednoznačnosti je pro každou šifru jiná.
Entropie
- Základem Shannonovy teorie je pojem entropie.
- Entropie zhruba řečeno vyjadřuje, kolik informace je v nějaké zprávě.
- Máme-li v dotazníku vyplnit rubriku pohlaví, odpověď ženské nebo mužské obsahuje informaci velikosti jednoho bitu, nikoliv 48 bitů, kolik potřebujeme k jejímu zápisu pomocí ASCII kódu.
- Tuto informaci totiž můžeme také zakódovat jako 0 - mužské, 1 - ženské.
- Informaci o velikosti jednoho bitu ovšem nese pouze v případě, že ji pokládáme v situaci, kdy o pohlaví dotazované osoby předem nic nevíme.
- Na setkání dobrovolnic armády spásy nám neposkytne informaci vůbec žádnou.

Difúze a konfúze.

Důvod proč historické šifry jsou luštitelné přímo ze šifrového textu je ten, že text u nich příliš přímočaře odráží statistické charakteristiky otevřeného textu.

Shannon navrhl dvě metody, jak tomu zabránit - difúzi a konfúzi.

Difúze rozprostírá statistické charakteristiky otevřeného textu do delších úseků šifrového textu.

Difúzi docílíme zobrazením znaků otevřeného textu do jednoho znaku šifrového textu přepisem c(n) = (o(n-s+1) + o(n-s+2) + ... + o(n)) mod 26

Jednoduchá záměna ponechává zcela nepozměněny vazby mezi hláskami, neboť jejich četnosti zůstávají stejné v šifrovaném jako v otevřeném textu.

Velmi dobrá difúze je dosažena, když jakákoliv redundance v otevřeném textu je rozprostřena do celého šifrového textu.

Konfúze činí vztah mezi statistickými vlastnostmi šifrového textu a klíčem co nejsložitější a nejobsažnější (tj. zahrnující co největší části šifrového textu a klíče).

Klasifikace tříd složitosti algoritmů.

Třída úloh P
- lze je řešit deterministickým TS s časovou náročností, kterou můžeme vyjádřit polynomiální funkcí vzhledem k velikosti vstupu algoritmem
Třída úloh NP
- lze řešit nedeterministickým TS s časovou náročností, kterou můžeme vyjádřit polynomiální funkcí vzhledem k velikosti vstupu algoritmem.
- A pokud máme řešení, toto lze verifikovat v polynomiálním čase
Třída úloh NPC (NP-Complete)
- složité problémy, které jsou na sebe redukovatelné v polynomiálním čas, ale pokud máme řešení, lze toto verifikovat v polynomiálním čase
Třída úloh NPH (NP-Hard)
- všechny NPC, ale i složitější, kde ani verifikace není proveditelná v polynomiálním čase
Třída úloh U (Undecidable problems)
- obsahuje problémy, pro které je dokázáno, že neexistuje algoritmus, který by je řešil¨

Prvočísla důkazy prvočíselnosti, rozklad na prvočinitele, prvočísla v kryptografii.

Prvočísla jsou přirozená čísla větší než 1, která jsou beze zbytku dělitelná pouze jedničkou a samo sebou.

Celá čísla větší než 1, která nejsou prvočíslem se nazývají složená.

Prvočísel je nekonečně mnoho.

Rozložení prvočísel

Každé složené číslo lze jednoznačně vyjádřit jako součin prvočísel.

Proces rozkladu čísla na jeho prvočíselné činitele (prvočinitele) se nazývá faktorizace.

Např. 24 = 2^3 * 3

Zjištění počtu prvočísel mezi 1 a x je velice blízký funkci x/ln (x).

Toto se používá pro odhad pravděpodobnosti výskytu velkých prvočísel při jejich tvorbě pomocí náhodného generování velkých čísel.

Velká prvočísla jsou potřeba v kryptografii pro PKC algoritmus RSA.

Eratosthenesovo síto

metoda určí všechna prvočísla menší nebo rovná n.

Postup:

napište řadu všech přirozzených čísel (2,3,4,5,6,7,8,9,10,...,n)

počínaje 4 vyškrtněte všechny násobky čísla 2 (2,3,5,7,9,11,13,15,17,....,n)

dále vyškrtneme všechny násobky čísla 3 větší než 3 (2,3,5,7,11,13,17,19,23,25,...,n)

pokračujeme pořád dále až do √n a vyškrtneme tím všechna neprvočísla
tato metoda je na první pohled nepraktická pro velká n

Prvočísla v kryptografii

Prvořadou úlohu hrají prvočísla v oblasti asymetrických šifer.

Nejznámější asymetrická šifra RSA stojí a padá se složitostí faktorizace čísel

Protože digitální podpis založený na asymetrických šifrách je v současné době jediná bezpečná instance elektronického podpisu, mají prvočísla a faktorizace dopad i na tuto oblast

Při konstrukci proudových šifer se využívají jako jeden ze stavebních kamenů registry se zpětnou vazbou. Konkrétně lineární registry se zpětnou vazbou, jejichž délky jsou prvočísla. Tato prvočísla mají výhodné a teoreticky dobře popsatelné vlastnosti.

Generace náhodných bitů metody generování náhodných bitů, testování kvality posloupností náhodných bitů, využití posloupností náhodných bitů v kryptografii.

Generátor náhodných bitů (RBG)

zařízení sestrojené k produkci posloupnosti statisticky nezávislých a rovnoměrně rozdělených binárních náhodných veličin
RBG má splňovat
- rovnoměrnost
- - pravděpodobnost nuly a jedničky = 0,5
- nezávislost měřítka
- - co platí pro celou posloupnost musí platit i pro libovolnou podposloupnost
- konzistenci
- - chování generátoru nezávisí na vstupní hodnotě - seed

Použití RBG v kryptografii

Přímé šifrování náhodným helsem (Vernamova šifra)
- One-time pad - jediný absolutně bezpečný systém
Generování klíčů pro
- symetrické šifry
- asymetrické šifry
Generování dat pro vytváření elektronických podpisů
- zvláštní případ použití asymetrických šifer

Rozdělení RBG

Fyzikální generátory
- produkují true-random posloupnosti (TRBG)
- pracují na základě náhodných fyzikálních procesů
- podle typu je dělíme na
- - fundamentálně náhodné
  - - radioaktivní rozpad
    - tepelný šum v tranzistorech
    - dopad světelného kvanta
  - prakticky náhodné
  - - Ruleta
    - losovací zařízení loterií (např. Sportka)
- Výhody pro kryptografii
- - maximální bezpečnost
  - naprostá neopakovatelnost
- Nevýhody pro kryptografii
- - pomalost generace
  - problémy při technické realizaci zařízení
Generátory algoritmické (DRBG)
- produkují pseudo-random posloupnosti
- posloupnost se počítá deterministickým algoritmem založeným na nějaké jednosměrné funkci
- použité algoritmy
- - hashovací funkce (SHA-1, MD-5)
  - blokové šifry (DES, 3-DES, AES)
  - proudové šifry
- Výhody pro kryptografii
- - vysoká rychlost generování
  - cenově nejlevnější realizace
- Nevýhody pro kryptografii
- - nižší bezpečnost
  - periodicita
  - při špatně zvoleném sestavení i možnost opakování
Generátory smíšené
- spojení true a pseudo-random generátoru
- používá se na zlepšení pravděpodobnostních charakteristik u fyzikálních generátorů
- Výhody pro kryptografii
- - všechny výhody true-random a navíc vysoká rovnoměrnost četnosti znaků
  - ideální pro použití v kryptografických aplikacích (generování klíčů)
- Výhody pro kryptografii
- - pomalost generování
  - nevhodné pro online šifrování

Testování posloupností

Q:Proč by měla být jedna konečná náhodná posloupnost lepší než-li druhá?

A: Použijeme-li jako heslo k zašifrování náhodnou posloupnost s relativní četností nuly 99,999%, protivník si ji hned přečte.
Pokud jich bude 90%, protivník ji také vyluští.
Při relativní četnosti 50,00001% mu však nepomohou ani všechna počítače světa

Klasické testy

test frekvence (frequency test)
test n-tic (serial, poker test)
test serií (run test)
test rozložení sérií
autokorelační test (autocorrelation test)
univerzální test - Maurer & Coron
spektrální test

Testovací baterie

každý z testů testuje nějakou vlastnost, kterou by měla mít kryptologicky kvalitní náhodná posloupnost znaků.

Proto se tyto testy shlukují do tzv. baterií, aby posloupnost testovaly komplexně.

Testovací baterie používané pro kryptografické účely:

FIPS 140-2 (NIST USA)
- mezinárodní standard na kvalitu kryptografických zařízení od 2001 (předtím FIPS 140-1)
- obsahuje i baterii statistických testů na generátory binárních posloupností pro kryptografické účely
- Použité testy:
- - test frekvence
  - poker test pro K=4
  - testy sérií pro L=1,...,6
  - test na nevýskyt extrémně dlouhé série (L>33)
- Hodnocení generátoru nastaveno na hladinu významnosti 0.0001
NIST Statistical Test Suite
DIEHARD
CRYPT-XS
VANAD