Kryptografie včera, dnes a zítra Jan Paseka O čem to dnes bude n Úvod do problematiky, motivace n Historie n Symetrické šifrování n Asymetrické šifrování n Digitální podpis n Šifrovací algoritmy n PGP, kvantová kryptografie Základní pojmy (1) n Kryptologie věda zabývající se šiframi n Kryptografie část kryptologie zabývající se převedením srozumitelné zprávy do nesrozumitelné podoby a zpět (šifrování a dešifrování textu) n Kryptoanalýza část kryptologie zabývající se odhalením klíče, čili umožněním čtení zašifrované zprávy Základní pojmy (2) n Šifrování (encryption) proces, při kterém převedeme podle určených pravidel otevřený text na šifrový text (cipher text) n Dešifrování (decryption) opačný proces k šifrování n Klíč posloupnost, může být rozdílný pro šifrování a dešifrování n Útok na šifru, lámání šifry zkoušení všech možných klíčů Proč šifrovat? n Bankovnictví n Multimédia -- DVD, CD, SAT TV n Firemní korespondence, Obyčejný mail = pohlednice n odchozí dráty, routery, SMTP servery, POP3 server n konkurence, váš obchodní partner, znuděný hacker, admin, který dostal výpověď, někdo, koho jste naštval n vyzrazení dat, modifikace dat n Pokud je tajnost zprávy závislá na utajení algoritmu šifrování, je to VŽDY špatně n Současné algoritmy šifrování jsou obecně známé a tajnost zprávy závisí pouze na tajnosti klíče Proč šifrovat? n Kryptologie, která byla dříve výsadou tajných služeb, armád a diplomacie, se stává během posledních deseti let věcí veřejnou a současně i výnosným obchodem. Zahajuje svoje masové tažení za všemi uživateli výpočetní techniky. Pojmy jako státní informační systém, e-business, e-commerce, e-obchodování, elektronický notář, kvalifikovaný certifikát, ochrana osobních dat a další se stanou samozřejmou součástí našeho jazyka a jejich realizace je možná právě díky kvalitním kryptografickým produktům a právnímu zajištění. Nejstarší šifry, historie n Skytála (transpoziční šifry) Před 2500 lety používala vláda ve Spartě následující metodu pro přenos tajné zprávy pro své generály: odesilatel a příjemce museli mít oba tzv. skytálu: byly to dva válce o přesně stejném průměru. Odesilatel navinul úzkou pergamenovou pásku spirálovitě okolo své skytály a napsal pak podle délky svou zprávu na pásku. Po odmotání pásky mohla zprávu číst jen ta osoba, která měla skytálu stejného rozměru -- doufejme, že to byl pouze příjemce. Nejstarší šifry, historie n Caesarova šifra (posouvací šifry) římský vojevůdce a státník Gaius Julius Caesar (100-44 př. n. l.). Existují také [Caesarovy dopisy] Cicerovi a známým o věcech, v kterých psal tajným písmem, pokud něco muselo být důvěrně sděleno. Tzn. změnil pořadí písmen tak, že nešlo zjistit jediné slovo. Pokud někdo chtěl toto rozluštit apoznat obsah, musel dosadit čtvrté písmeno abecedy, tedy D, za A, a podobně toto provést se zbývajícími písmeny. My můžeme ale posunout abecedu o libovolný možný počet míst. Protože se naše abeceda sestává z 26 písmen, existuje právě 26 takových šifrování - mluvíme o posouvacích neboli aditivních šifrách. Nejstarší šifry, historie n počátek dvacátého století století - prudký rozvoj, telegraf V současnosti leží hlavní úloha kryptografie v utajování elektronické komunikace. Krátce poté, co Samuel F. B. Morse v roce 1845 veřejně předvedl telegraf, objevily se obavy před vyzrazením posílaných zpráv. Co se stane, kdyby někdo zcizil telegrafní pásku? Co zabrání nepoctivému telegrafnímu úředníkovi ve zkopírování zprávy a jejímu případnému vyzrazení? Odpověd spočívala v kódování tajným kódem, který nemohl rozluštit nikdo jiný než oprávěný příjemce. Význam kryptografie dále stoupl s objevem radiové komunikace a s jejím použitím ve válkách. Bez použití kryptografie by mohl nepřítel velmi snadno zachytit zprávy, vysílané z fronty nebo na frontu. Nejstarší šifry, historie n počátek dvacátého století století - prudký rozvoj, telegraf Vstup USA do I. světové války byl důsledkem vyluštění obsahu šifrového telegramu -- dnes známého jako tzv. Zimmermannův telegram, kde německý ministr zahraničí Zimmermann v telegramu mexické vládě vyzývá Mexiko k válce proti USA. Slibuje v ní mexické straně podporu a územní zisk. Britové telegram zachytili, rozluštili jej a předali USA. Poté, co se prezident Wilson s obsahem telegramu seznámil, svolává Kongres. Ten 2.4.1917 schvaluje vstup USA do války proti Německu. Tento akt rozhodujícím způsobem změnil poměr sil na evropském bojišti. Nejstarší šifry, historie n Vernamova šifra n Je to asi jediná šifrovací metoda, jejíž bezpečnost je matematicky dokazatelná. Její princip spočívá v tom, že se zpráva zakóduje pomocí stejně dlouhé náhodné posloupnosti (klíče), čímž získá charakter zcela náhodného sledu znaků. Takový klíč může být pochopitelně použit pouze jednou (proto se této metodě v angličtině říká také one time pad) a musí být skutečně náhodný a nekorelovaný. Bez znalosti klíče nelze zprávu rozluštit. Jinými slovy, pravděpodobnosti všech možných výsledků jsou stejné. Neoprávněný luštitel má stejnou šanci dostat Shakespearovy sonety jako třeba daňové zákony. Opakované použití klíče nebo jeho části, či jakákoli pravidelnost v něm mohou dát luštitelům určitou šanci. Nejstarší šifry, historie n Vernamova šifra n Jak šifrování a dešifrování probíhá, ukazuje následující jednoduchý příklad. Používáme-li např. abecedu o 26 znacích, potřebujeme jako klíč sekvenci náhodných čísel z intervalu 0 až 25 (odesílatel i příjemce musí mít pochopitelně stejný klíč). Při šifrování se prostě posuneme v abecedě o patřičný počet míst (daný odpovídající hodnotou klíče) vpřed, při dešifrování vzad. n V případě binárně kódované zprávy je situace ještě jednodušší. Klíč má podobu náhodné posloupnosti nul a jedniček (stejně dlouhé, jako je zpráva), kterou můžeme získat třeba házením mincí. Při šifrování i dešifrování se bity zprávy a klíče jednoduše sečtou modulo 2 (operace XOR): n Zpráva Klíč Šifra n 1 1 0 11ŕ 0 n 1 0 1 n 1 1 0 10ŕ 1 n 0 0 0 n 0 0 0 01ŕ 1 n 0 1 1 n 0 1 1 00ŕ 0 Nejstarší šifry, historie n do konce 50.let mnoho šifrovacích strojů (Enigma, Navajos) Tento stroj způsobil zavedení počítačů do kryptografie a je základním kamenem pro pochopení způsobu práce moderních šifrovacích programů. Mezi velmi úspěšné kryptografické stroje použité během II. sv. války se dají zařadit tzv. Code-talkers (film Windtalkers)--- příslušníci indianského kmene Navajo. Často používané výrazy měly přímo definovaný kód v navajštině, u ostatních slov bylo jejich každé písmeno při šifrovánínahrazeno anglickým slovem (z pevně definované sady), na toto písmeno začínajícím a to bylo posléze převedeno do Navajštiny (buď jako ekvivalent nebo opis původně v tomto jazyce neexistujícího slova). Díky pečlivě volenému kódovaní slov nebylo toto šifrování během války prolomeno ani přesto, že Japonci mohli využít příslušníka kmene Navajo pro překlad zachycených termínů Nejstarší šifry, historie Nejstarší šifry, historie Nejstarší šifry, historie Nejstarší šifry, historie Nejstarší šifry, historie n Obrázek Enigmy Nejstarší šifry, historie n 50.-60. léta rozvoj počítačů, kryptografie pro veřejnost (banky) Tato epocha je charakteristická 2 pracemi od Claude Elwood Shannona. V časopise Bell Systém Technical Journal v roce 1948 a 1949 otiskuje články "Matematická teorie sdělování" a "Sdělovací teorie tajných systémů". Prvý z článků dal vznik teorii informací, druhý článek pojednával o kryptologii v termínech informační teorie. Pojetí nadbytečnosti (redundancy) je hlavním termínem, který Shannon zavedl. Nejstarší šifry, historie n 1973 - požadavky na algoritmus na ochranu neutajovaných dat n DES - Data Encryption Standard Tento algoritmus byl vyvinut firmou IBM a v roce 1977 se stal veřejným standard pro ochranu informací, nikoliv však pro ochranu informací utajovaných. DES nešifruje písmena, nýbrž symboly 0 a 1, a to 64 naráz (v případě, že používáme DES k zašifrování obyčejného textu, musí být písmena nejdřív přeložena do řetězce bitů. Vývoj DES navazuje na vývoj šifrovacího algoritmu Lucifer od Thomase Watsona. Aktivní délka klíče je 56 bitů, hlavní prvky, které chrání šifrový text před útoky analytiků, jsou tzv. S-boxy. V roce 1976 byla uspořádána NBS (Národní úřad pro standardizaci) dvoudenní konference k diskuzi o DES. n množství šifer (symetrické i asymetrické), PGP Export šifer n Spojené státy považují šifrovací technologie za druh zbraně, a zbraně se samozřejmě neexportují jen tak ledaskam. Export šifer n I když se to na první pohled může zdát trochu nelogické, je koneckonců pravda, že rozluštění japonských šifer výrazně ovlivnilo průběh druhé světové války, takže i k tomu mají i pádný důvod. Export šifer n USA si ale zároveň uvědomují, že používání těchto technologií bude mít v blízké budoucnosti zásadní význam pro rozvoj elektronického obchodu a pravděpodobně i veškerého ostatního podnikání. Export šifer n Zlomové roky 1999--2000 n Již se neobjevují slabé šifrové systémy, které ještě v polovině 90. let byly předkládány veřejnosti jako bezpečné (např. Crypt, Rot13, SuperKey, N-Code). n V produktech Microsoftu (Word, Excel), Lotusu, WordPerfectu se však stále používají nekvalitní šifrové systémy, které lze lehce rozbít. Postupně je Microsoft sice nahrazuje za kvalitní šifru, ale z důvodu vývozních omezení je oslabuje úpravou klíče na délku pouhých 40 bitů. n Takto úmyslně upraveným algoritmům se říká slabá kryptografie. Mimo území USA a Kanady se tak stále v těchto produktech nacházejí slabé šifrové produkty. Export šifer n Zlomové roky 1999--2000 n Toto je ovšem výhodná situace pro evropské komerční firmy, které se snaží obsadit evropský trh svými produkty. Americké velké firmy se snaží donutit vládu USA k omezení vývozních restrikcí, ale ta neustupuje. n Komerční produkty vybavené kvalitními symetrickými algoritmy (např. 3DES, CAST, RC4, Twofish) a asymetrickými algoritmy (RSA, algoritmy na bázi diskrétního algoritmu, algoritmy na bázi eliptických křivek) se začínají vyrábět a vyvážet nejen v Německu, Francii, Anglii, Finsku, ale i u nás. n Česká firma Decros úspěšně vyváží své produkty nejen do Evropy, ale i do Asie. Květen 1999 je pro Českou republiku určitým ohodnocením naší vyspělosti v této oblasti. Výbor IACR v roce 1997 rozhodl, že konference Eurocrypt 1999 se bude konat v Praze. Export šifer n Zlomové roky 1999--2000 n V létě 1999 německá vláda vydává prohlášení, ve kterém jasně proklamuje, že na dobu dvou let ruší všechny restrikce v používání silné kryptografie a dává celému světu najevo, že chce zaujmout rozhodující pozici v evropském trhu s kryptografií. n Tlak amerických firem, které přicházejí o miliony dolarů, nakonec slaví úspěch. V listopadu 1999 dochází k prvnímu uvolnění vývozních restrikcí a další uvolnění následuje v lednu 2000. S konečnou platností je tak uvolněn export šifrovacích algoritmů ze Spojených států (včetně zdrojových textů). n V lednu 2000 byl také zahájen 3 letý projekt NESSIE (New European Schemes for Signature, Integrity, and Encryption) programu IST Evropské komise. Jednotlivé moduly budou vytvářeny na základě veřejných návrhů a rovněž tak vyhodnocení těchto návrhů proběhne otevřenou a transparentní cestou. Symetrické šifrování Symetrické šifrování n jeden klíč pro šifrování i dešifrování n DES, 3DES, CAST, IDEA, Blowfish n Výhody: rychlost hodí se pro data, která nikam nejdou (harddisk) n Nevýhody: předání klíče počet klíčů (10000 členů = 50 milionů klíčů, 5 miliard lidí = 12 500 000 000 000 000 000 klíčů) DES, 3DES n Data Encryption Standard n 1975, IBM n NSA srazila klíč ze 128 na 56 n není moc bezpečný n spec. stroj na zlomení DESu průměrně 3,5 hod v ceně cca. 1 mil. USD n 3DES protáhne jedna data algoritmem třikrát - zašifrování nyní probíhá takto: zpráva se zašifruje pomocí algoritmu DES a klíče K1, odšifruje se pomocí klíče K2 a opět se zašifruje pomocí klíče K3 (resp. v jiné verzi klíčem K1). Délka klíče se tak vlastně 3x (resp.2x) prodloužila a toto řešení se tímto stalo odolné proti útoku hrubou silou. IDEA n International Data Encryption Algorithm n 1990, Xuejia Lai a James Massey n Švýcarsko n klíč 128 bitů n implementována v rámci SSL n není známo, že by byla rozluštěna metodou hrubé síly AES n V roce 1997 NIST vypisuje veřejnou soutěž na vytvoření nového komerčního standardu pro symetrické šifrování. n Novým standardem se stal AES (Advanced Encryption Standard). AES má být 128bitová bloková šifra, musí podporovat klíče délky 128, 192 a 256 bitů. Je určen pro všechny typy aplikací a nasazení (klasický software pro PC, terminály pro elektronickou komerci, čipové karty). n Algoritmus není patentován a vítěz dostává odměnu "zlatý vavřín kryptologie". Asymetrické šifrování Asymetrické šifrování n veřejný klíč + privátní klíč n RSA, Diffie-Hellman, DSS n Výhody: odpadá předávání klíčů menší počet klíčů n Nevýhody: "pomalost" (asi 1000x pomalejší) Digitální podpis Digitální podpis n autenticita podpis přesvědčí adresáta, že jste dokument skutečně podepsal. n nezfalšovatelnost nikdo jiný váš podpis neumí napodobit. n jednorázovost použití podpis nelze vzít a přenést na jiný dokument. n nezměnitelnost dokumentu po podpisu už nelze provádět v textu žádné změny. n nepopiratelnost nemůžete prohlásit, že jste dokument nepodepsal, když je vámi podepsaný Digitální podpis Hashovací funkce n funkce, která vyrobí vzorek jakéhokoli souboru (textu) n výstupem je vzorek (hash, figerprint, otisk) o pevné délce, závislý na všech bitech původního souboru (textu) n MD5 -- Message Digest Algorithm 5 n SHA-1 -- Secure Hash Algorithm 1 Praxe (1) Praxe (2) RSA n Ron Rivest, Adi Shamir a Len Adleman (1977) n Založen na neschopnosti lidí faktorizovat velká čísla n Asymetrické šifrování RSA n V roce 1997 byl uveřejněn článek Jamese Ellise z britské CESG (Communications -- Electronics Security Group), nazvaný "The history of Non-Secret Encryption" , ve kterém jeho autor popisuje, jak princip asymetrické kryptografie (jím nazývaný jako Non-Secret Encryption, NSE) objevil už v roce 1970. Dále uvádí, že speciální variantu RSA objevil jeho kolega Clifford Cocks v roce 1973. RSA (Algoritmus RSA) I. Zvolíme abecedu A. II. Text převedeme do číselné formy a rozdělíme na bloky stejné délky. Číselné vyjádření konkrétního bloku označíme x. III. Zvolme N, součin dvou hodně velkých prvočísel (500 místných), tedy N = p*q. Musí platit 1<=x