KRYPTOGRAFIE OKOLO NÁS

Karel Burda

Vydavatel:

CZ.NIC, z. s. p. o.

Milešovská 5, 130 00 Praha 3

Edice CZ.NIC

www.nic.cz

1. vydání, Praha 2019

Kniha vyšla jako 24. publikace v Edici CZ.NIC.

ISBN 978-80-88168-50-8

© 2019 Karel Burda

Toto autorské dílo podléhá licenci Creative Commons BY-ND 3.0 CZ

(https://creativecommons.org/licenses/by-nd/3.0/cz/), a to za předpokladu, že zůstane zachováno označení autora díla a prvního vydavatele díla, sdružení CZ.NIC, z. s. p. o. Dílo může být překládáno a následně šířeno v písemné či elektronické formě, na území kteréhokoliv státu.

— Karel Burda

Kryptografie
okolo nás

— Edice CZ.NIC

Předmluva vydavatele

Předmluva vydavatele

Vážení čtenáři,

tím, jak se náš běžný život čím dál více přesouvá do online světa internetu, nabývá kryptografie na důležitosti. Do elektronického světa je nutné promítnout řešení problémů v reálném světě již alespoň částečně vyřešených, jako je zajištění soukromí při komunikaci, prokazování totožnosti komunikujících stran nebo autenticity vyměňovaných zpráv. Toto všechno a mnohem více pomáhá vyřešit právě kryptografie.

Vzhledem k tomu, že internet vznikal převážně na akademické půdě, nevnímali jeho průkopníci výše uvedené problémy jako klíčové, a tak spousta protokolů stojících v samotných základech internetu získávala důležité bezpečností prvky se značným zpožděním. Ještě větší urychlení v tomto směru přineslo odhalení praktik tajných služeb v posledních letech. Přestože použití kryptografie jako nástroje není možné z principu morálně posoudit, nelze ignorovat, že bývá nezřídka zneužívána k páchání trestné činnosti. Nechtěně se tak stává bitevním polem, na kterém se utkávají internetoví architekti a vývojáři aplikací na jedné straně a bezpečnostní složky nebo celé vlády na straně druhé. Bez ohledu na to, jak tato bitva dopadne, je určitě užitečné získat přehled o tom, kde všude se můžeme ve světě internetu s kryptografií setkat. A takový přehled vám zaručeně poskytne právě tato kniha.

Autor Karel Burda, vysokoškolský pedagog na VUT v Brně, touto knihou volně navazuje na své předchozí publikace a popisuje v ní celou řadu internetových technologií a protokolů, které kryptografii využívají. Osobně se s mnoha z nich setkávám při své práci denně. Jako příklad bych jmenoval DNSSEC (rozšíření protokolu DNS o kryptografické zajištění autenticity DNS odpovědí), v jehož rozšíření a tedy počtu zabezpečených domén jsme v ČR světovými lídry, nebo podporu nejmodernějšího autentizačního protokolu OpenID Connect službou mojeID, kterou u nás využívá přes 600 000 lidí.

Ať už knihu přečtete od začátku do konce, nebo pouze nalistuje část obsahující protokol, který vás nejvíce zajímá, jsem přesvědčen, že získané informace vám umožní pohybovat se po internetu s mnohem větší důvěrou a jistotou.

Jaromír Talíř, CZ.NIC

Praha, 1. listopadu 2019

Úvod

Úvod

První kryptografické techniky (tzv. šifry) vznikly prakticky vzápětí po vzniku písma, neboť jejich účelem bylo utajit obsah písemných zpráv před nepovolanými čtenáři. Historicky nejstarším známým důkazem o praktickém využití kryptografie je hliněná destička ze starověké Mezopotámie z období asi 1.500 let před naším letopočtem, na níž je uveden šifrovaný popis technologie výroby glazurované keramiky. Zpočátku se v šifrách používaly jednoduché záměny znaků ve zprávě (tzv. substituce), nebo se ve zprávě měnilo pořadí znaků (tzv. transpozice). Postupně se však ukázalo, že z bezpečnostních důvodů je zapotřebí šifrovací postupy kombinovat a komplikovat. Šifry se tak stávaly stále složitějšími a k jejich použití, analýze a návrhu se proto začala používat matematika. V minulém století se také zjistilo, že matematické metody lze použít nejen k utajování obsahu zpráv, ale rovněž k prokazování původu doručených zpráv. Z původně jednoduchých šifrovacích technik se tak nakonec vyprofilovala kryptografie jako věda, která se zabývá konstrukcí a aplikací matematických metod pro utajování obsahu a prokazování původu přenášených zpráv.

Kryptografie primárně vznikla k ochraně zpráv během jejich přenosu, a tak až donedávna byly její doménou přenosové systémy. Praxe však ukázala, že pomocí kryptograficky chráněných zpráv lze velmi efektivně zajistit vysokou úroveň bezpečnosti mnoha dalších systémů, jako například systémů řízení přístupu, systémů elektronických plateb apod. S aplikacemi kryptografie proto přicházíme do styku každodenně, avšak všeobecné povědomí o tom, jak fungují, je nízká. Je to dáno zejména tím, že uvedené aplikace jsou poměrně složité.

Vzhledem ke složitosti a rozsáhlosti kryptografických aplikací budeme v této knize abstrahovat od různorodosti účelově stejných funkcí. To znamená, že celý soubor kryptografických funkcí, které jsou z hlediska svého účelu stejné, budeme reprezentovat jedinou obecnou funkcí. Nebudeme tak například rozlišovat, zda se šifrování provádí proudovou či blokovou šifrou, jakými algoritmy a případně v jakých režimech. Tímto přístupem si zjednodušíme situaci natolik, že nám pak k popisu naprosté většiny kryptografických aplikací postačí sedm elementárních kryptografických funkcí a jeden generátor. Konkrétně se jedná o:

• šifrovací (ENC) a k ní komplementární dešifrovací (DEC) funkci,

• pečetící (PCT) a k ní komplementární verifikační (VER) funkci,

• hešovací funkci (HSF),

• Diffie-Hellmanovu funkci (DHF),

• odvozovací funkci (ODF),

• generátor nepředvídatelných čísel (GEN).

Uvedený přístup umožní čtenáři rychle a efektivně porozumět principu fungování celé řady velmi různorodých kryptografických aplikací. Zaplatí za to určitými zjednodušeními, ale úplnější a detailnější informace se případný zájemce může dozvědět z odkazované literatury.

Struktura knihy je následující. Po tomto úvodu následuje kapitola Základy kryptografie, kde se čtenář podrobněji seznámí s výše uvedenými elementárními kryptografickými funkcemi. Zbytek knihy je věnován popisu kryptografických aplikací, s nimiž se potkáváme v běžném životě. Jsou rozděleny celkem do tří kapitol. V kapitole Přenosové systémy jsou vysvětleny kryptograficky zabezpečené protokoly, jejichž primárním účelem je zajistit bezpečný přenos zpráv. Příkladem jsou protokol TLS, který používáme kupříkladu v internetovém bankovnictví, nebo protokoly komplexu WPA, kterými se zabezpečují rádiové přenosy ve Wi-Fi sítích. V kapitole Přístupové systémy jsou popisovány protokoly k prokázání identity osob (např. Kerberos) a k řízení přístupu osob buď k síťovým službám (např. RADIUS), nebo do fyzických prostor (elektronická kontrola vstupu). Poslední kapitola s názvem Platební systémy je věnována platebním protokolům, jejichž účelem je elektronický převod peněz mezi účty uživatelů (např. protokoly pro platební karty či kryptoměna Bitcoin).

1 Základy kryptografie

1 Základy kryptografie

Jak již bylo uvedeno kryptografie je věda, která zkoumá matematické metody utajování obsahu i prokazování původu přenášených zpráv. Zprávou přitom budeme rozumět číselnou posloupnost, v níž je veřejně známým kódem zakódována informace. V praxi se zpravidla jedná o texty, obrázky a případně příkazy v podobě posloupností dvojkových číslic (tzv. bitů).

Autor zprávy (tzv. původce) svoji zprávu předává vhodným přenosovým systémem (typicky přes počítačovou síť) zamýšlenému příjemci (tzv. adresátovi). Z kryptografického hlediska mají běžně používané přenosové systémy charakter tzv. veřejného přenosového kanálu, což znamená, že ke kanálu mají kromě původce a adresáta přístup i jiné (tzv. neoprávněné) osoby. Některé z těchto osob usilují o čtení, resp. pozměňování přenášených zpráv, a tak je nazveme útočníky. Kryptografické techniky umožňují původci a adresátovi zajistit ochranu přenášených zpráv před uvedenými hrozbami. V případě utajování obsahu zpráv nejsou útočníci schopni zjistit, jaké zprávy jsou v přenosovém kanálu předávány (tzv. důvěrnost zpráv). A v případě prokazování původu zpráv si je adresát schopen ověřit, zda přijatá zpráva skutečně pochází od udávaného původce, tj. zda tato zpráva nebyla během přenosu případným útočníkem nějakým způsobem pozměněna, či dokonce nebyla celá podvržena (tzv. autentičnost zpráv).

Zabezpečená komunikace mezi původcem a adresátem je definována kryptografickým protokolem. Základ kryptografického protokolu tvoří datové jednotky, což jsou bloky bitů, které si mezi sebou původce s adresátem vyměňují. Každý typ datové jednotky má svoji určenou strukturu a svůj význam. Kromě různých typů datových jednotek je součástí protokolu i sada pravidel, jimiž se výměna datových jednotek mezi původcem a adresátem (v protokolu se nazývají strany) řídí. Kromě dvoustranných protokolů existují i vícestranné protokoly, což jsou protokoly, kde se výměna datových jednotek uskutečňuje mezi více subjekty. Reprezentantem vícestranného protokolu jsou například platební protokoly, na nichž se kromě plátce a příjemce zúčastňuje také banka plátce a banka příjemce.

Než přejdeme k základním kryptografickým funkcím, tak si zde ještě vysvětlíme operaci, která se nazývá zřetězení. Vstupem operace zřetězení jsou dva bitové bloky x a y, přičemž výstupem je blok z, který vznikne připojením bloku y na konec bloku x. Formálně budeme uvedenou operaci značit

z = x ∥ y.

Pokud máme například dva bloky x = 00 a y = 101, tak z = x ∥ y = 00 ∥ 101 = 00101.

Na závěr této podkapitoly si ještě domluvíme typografické konvence, které v této knize použijeme. Jednotlivá písmena v základním řezu budou reprezentovat strany (např. strana A) a řetězce písmen v základním řezu budou vyjadřovat funkce (např. šifrování ENC). Písmena či jejich řetězce v kurzívě pak budou označovat proměnné (např. zpráva Z nebo blok ukončení zprávy UZ).

1.1 Utajovací kryptosystémy

Účelem utajovacích kryptosystémů je zajistit důvěrnost zpráv, což v praxi znamená utajení obsahu těchto zpráv před neoprávněnými osobami. Již jsme si uvedli, že zpráva (např. text či obraz) je číselná posloupnost, ve které jsou veřejně známým kódem zakódovány informace. K utajení obsahu zpráv (tedy k utajení zakódovaných informací) se zprávy Z převádějí na tzv. kryptogramy. Kryptogram C je číselná posloupnost, která je tzv. pseudonáhodná. To znamená, že kryptogram se jeví jako náhodná posloupnost čísel, avšak ve skutečnosti náhodnou posloupností není. Kryptogram je oproti zprávě veřejný, tj. je přístupný i neoprávněným osobám. Jeho pseudonáhodný charakter však způsobuje, že případní útočníci nejsou schopni jej převést zpět do podoby původní zprávy. Pouze oprávněná osoba, která zná tajný číselný parametr, je schopna provést konverzi kryptogramu na původní zprávu a z ní pak zakódované informace zjistit.

Strukturu utajovacího kryptosystému (nebo-li šifry) ilustruje obr. 1.1. Strana A (odesílatel) přivede svoji zprávu Z na vstup tzv. šifrovací funkce, kterou v dalším budeme označovat zkratkou ENC (z anglického „encrypting“). Tato funkce přiřazuje každé vstupní číselné posloupnosti Z právě jednu pseudonáhodnou posloupnost C. Z bezpečnostních důvodů musí v každém kryptosystému existovat velké množství použitelných šifrovacích funkcí (tzv. rodina funkcí) a konkrétní použitou funkci (tj. konkrétní přiřazení) pak definuje parametr KE, který se nazývá šifrovací klíč. Přiřazení kryptogramu C vstupní zprávě Z pro danou hodnotu klíče KE se nazývá šifrování a formálně je budeme vyjadřovat vztahem

C = ENC(Z, KE).

Obrázek 1.1: Struktura utajovacího kryptosystému

Odesílatel odešle kryptogram C veřejným kanálem k adresátovi B. Během tohoto přenosu se ke kryptogramu mohou dostat i neoprávněné osoby, avšak pouze oprávněný adresát B zná hodnotu tajného parametru KD, který se nazývá dešifrovací klíč. Pomocí tohoto parametru nastaví tzv. dešifrovací funkci DEC („decrypting“) tak, aby byla inverzní k šifrovací funkci ENC. Na výstupu dešifrovací funkce se proto objeví původní zpráva Z. Formálně budeme proces dešifrování zapisovat vztahem

Z = DEC(C, KD).

Funkce ENC a DEC jsou obvykle veřejně známy (často jsou dokonce standardizovány). Požaduje se po nich, aby bez znalosti dešifrovacího klíče KD nebylo prakticky možné ke kryptogramům C zjistit jim odpovídající zprávy Z. Další požadavek vyplývá ze skutečnosti, že dešifrovací klíč často slouží k dešifrování více kryptogramů. Proto se po funkcích ENC a DEC ještě požaduje, aby ze znalosti různých dvojic zpráva a odpovídající kryptogram nebylo prakticky možné odvodit hodnotu používaného dešifrovacího klíče KD.

Utajovací kryptosystémy se dělí na symetrické a asymetrické (viz obr. 1.2).

Obrázek 1.2: Symetrický (vlevo) a asymetrický (vpravo) utajovací kryptosystém

U symetrických kryptosystémů platí, že zjistit hodnotu dešifrovacího klíče ze znalosti hodnoty klíče šifrovacího je prakticky možné. Z tohoto důvodu se musí utajovat hodnoty obou klíčů, přičemž obvykle platí, že tyto klíče jsou stejné, tj. KD = KE = K, kde K se nazývá tajný klíč. Symetrické kryptosystémy jsou rychlé, a tak se využívají k šifrování velkých objemů dat. Nevýhodou symetrických kryptosystémů je skutečnost, že bezpečné doručení klíče K komunikující protistraně je vzhledem k tajnému charakteru klíče komplikované.

U asymetrických kryptosystémů naopak platí, že určení hodnoty dešifrovacího klíče ze znalosti hodnoty klíče šifrovacího je prakticky nemožné. Z tohoto důvodu je pak nutné utajovat pouze hodnotu dešifrovacího klíče. Adresát B si nejprve stanoveným postupem vytvoří dvojici šifrovací a dešifrovací klíč. Tato dvojice se odvozuje z velkých náhodných čísel, a tak pravděpodobnost, že dva uživatelé vytvoří stejnou dvojici klíčů, je prakticky rovná nule. Dešifrovací klíč je tajný a je znám pouze jeho tvůrci B (tzv. soukromý klíč SKB strany B). Hodnotu šifrovacího klíče tvůrce daného kryptosystému zveřejní (tzv. veřejný klíč VKB strany B). Platí tak, že KD = SKB a KE = VKB. Adresátovi B potom může zasílat kryptogramy kdokoliv, bez nutnosti si s ním šifrovací klíč předem sjednat. Nevýhodou je, že asymetrické kryptosystémy jsou pomalé, a tak se používají k šifrování dat o malých objemech. Typicky se jedná o klíče pro symetrické kryptosystémy a o hesla.

1.2 Autentizační kryptosystémy

Účelem autentizačních kryptosystémů je garantovat adresátům původ doručených zpráv (tzv. autentičnost zpráv) [1]. Zpravidla se jedná o autorství zprávy, případně lze garantovat i další atributy původu zprávy, jako je čas nebo místo jejího vzniku. Princip autentizačních kryptosystémů je takový, že odesílatel spolu se zprávou Z odesílá i krátkou číselnou posloupnost P, která umožní adresátovi původ zprávy ověřit.

Strukturu autentizačního kryptosystému ilustruje obr. 1.3. Odesílatel A přivede svoji zprávu Z na vstup tzv. pečetící funkce, kterou budeme označovat zkratkou PCT. Zmíněná funkce přiřazuje každé vstupní číselné posloupnosti Z jednu z mnoha možných výstupních posloupností P. Posloupnost P nazveme pečeť. Konkrétní přiřazení pečetí jednotlivým zprávám se nastavuje pomocí tajného parametru KP, jenž nazveme pečetící klíč. Proces přiřazení pečeti P vstupní zprávě Z budeme nazývat pečetění a formálně jej budeme vyjadřovat vztahem

P = PCT(Z, KP).

Obrázek 1.3: Struktura autentizačního kryptosystému

Dvojici (Z, P) nazveme zapečetěná zpráva. Odesílatel zapečetěnou zprávu odešle veřejným kanálem k adresátovi zprávy, přičemž během tohoto přenosu ji mohou neoprávněné osoby nahradit falešnou dvojicí (Z´, P´). Adresát B zná správnou hodnotu parametru KV (tzv. verifikační klíč), který definuje verifikační funkci VER. Přijatá zpráva Z spolu s její pečetí P jsou přivedeny na oba vstupy této funkce, v důsledku čehož výstupní hodnota W, kterou nazveme autentizační indikátor, má hodnotu buď 0, nebo 1. Verifikační funkce je konstruována tak, že pokud je pro danou zprávu pečeť správná, tak autentizační indikátor W = 1. V takovémto případě adresát zprávu Z akceptuje jako autentickou. V opačném případě, tj. když W = 0, adresát přijatou zprávu vyhodnotí jako podvodnou. Verifikaci budeme formálně zapisovat vztahem

W = VER(Z, P, KV).

Funkce PCT a VER jsou obvykle veřejně známy. Požaduje se po nich, aby bez znalosti pečetícího klíče KP nebylo prakticky možné ke zprávám Z určit správné pečeti P. Pečetící klíč je zpravidla používán vícenásobně, tj. jeden pečetící klíč slouží k pečetění mnoha různých zpráv. Proto se také požaduje, aby ze znalosti různých dvojic zpráva a odpovídající pečeť nebylo prakticky možné odvodit hodnotu používaného pečetícího klíče KP.

Stejně jako utajovací, tak i autentizační kryptosystémy se dělí na symetrické a asymetrické (viz obr. 1.4). U symetrických kryptosystémů platí, že zjistit hodnotu pečetícího klíče ze znalosti hodnoty klíče verifikačního je prakticky možné. Proto se musí utajovat hodnoty obou klíčů, přičemž obvykle platí, že tyto klíče jsou stejné, tj. KP = KV = K, kde K se nazývá tajný klíč. Pečeti symetrických autentizačních kryptosystémů se v anglicky psané literatuře označují mnoha různými zkratkami (MAC = „Message Authentication Code“, MIC = „Message Integrity Check“ nebo ICV = „Integrity Check Value“). Výhodou symetrických kryptosystémů je, že jsou rychlé, a proto se využívají při pečetění velkých množství zpráv. Jejich nevýhodou je opět fakt, že bezpečné doručení klíče K komunikující protistraně je vzhledem k tajnému charakteru klíče komplikované.

Obrázek 1.4: Symetrický (vlevo) a asymetrický (vpravo) autentizační kryptosystém

U asymetrických kryptosystémů naopak platí, že určení hodnoty pečetícího klíče ze znalosti hodnoty klíče verifikačního je prakticky nemožné. Z tohoto důvodu je tak nutné utajovat pouze hodnotu pečetícího klíče. Původce A si stanoveným postupem vytvoří dvojici pečetící a verifikační klíč. Uvedená dvojice se odvozuje z velkých náhodných čísel, a tak pravděpodobnost, že dva uživatelé vytvoří stejnou dvojici klíčů, je prakticky rovná nule. Pečetící klíč je tajný a je znám pouze jeho tvůrci (tzv. soukromý klíč SKA strany A). Hodnotu verifikačního klíče tvůrce daného kryptosystému zveřejní (tzv. veřejný klíč VKA strany A). Platí tedy, že KP = SKA a KV = VKA. Autentičnost zpráv od strany A potom může ověřovat kdokoliv, bez nutnosti si s ním předem sjednat verifikační klíč.

Další velmi významnou předností autentizačních asymetrických kryptosystémů oproti symetrickým je skutečnost, že soukromý klíč SKA zná pouze původce zprávy. A protože SKA nelze ze znalosti veřejného VKA určit, tak správné pečeti dokáže vytvářet pouze strana A. Tato vlastnost způsobuje, že pečeti asymetrického autentizačního kryptosystému vykazují vlastnosti klasického ručního podpisu, kdy podpis dokáže vytvořit pouze jediná osoba a zároveň pravost tohoto podpisu může ověřit kdokoliv. Z tohoto důvodu se pečeti P u asymetrických kryptosystémů nazývají digitálními podpisy („Digital Signature“), soukromý klíč SKA se nazývá podpisový klíč a funkce PCT se nazývá podpisová funkce. Nevýhodou podpisových kryptosystémů oproti autentizačním symetrickým kryptosystémům je, že jsou pomalé.

1.3 Generátory nepředvídatelných čísel

Generátory nepředvídatelných čísel jsou zařízení určená ke generování posloupností čísel, které se neoprávněným osobám jeví jako náhodné posloupnosti. To konkrétně znamená, že číselné hodnoty v generované posloupnosti mají stejnou pravděpodobnost výskytu a jednotlivá čísla posloupnosti se jeví, že jsou navzájem nezávislá. V kryptografii je tento typ generátorů používán zejména ke generování klíčů a ke generování unikátů (tj. čísel, jimiž se individualizuje vykonání a tedy i výstup kryptografické funkce). Jsou rovněž i základní komponentou tzv. proudových šifer. Vygenerování nepředvídatelného čísla N budeme formálně vyjadřovat

N = GEN.

Generátory nepředvídatelných čísel klasifikujeme na náhodné a pseudonáhodné (viz obr. 1.5). Náhodné generátory (obr. nahoře) generují svá čísla na základě nějakého náhodného fyzikálního děje (např. tepelný šum). Měřením se zjišťuje aktuální hodnota náhodné veličiny a výsledky měření se vhodnou konverzní funkcí g převádějí na čísla pro výstup generátoru. Výstup těchto generátorů je tak skutečně náhodný („true random number generator“). Oproti tomu pseudonáhodné generátory („pseudorandom number generator“) generují svá čísla pomocí vhodného stavového automatu (obr. dole). Stavový automat je hardwarová (např. posuvný registr), nebo datová struktura (např. číslo), která může nabývat více stavů (např. obsah registru, nebo velikost čísla). Stavový automat se nejprve nastaví podle tajné náhodné hodnoty (tzv. semeno) do výchozího stavu. Pomocí přechodové funkce f se aktuálnímu stavu pokaždé přiřadí nový následující stav, a tak automat postupně prochází všemi určenými stavy. Speciální konverzní funkce g přitom každému aktuálnímu stavu automatu přiřazuje číslo, které je výstupem generátoru. Chování pseudonáhodného generátoru je tedy zcela deterministické, tj. oprávněné osoby, které znají funkce f, g a semeno, dokáží vygenerovat tutéž posloupnost čísel. Požaduje se však, aby neoprávněná osoba došla statistickým testováním vygenerované posloupnosti k závěru, že daná posloupnost je náhodná.

Obrázek 1.5: Generátor náhodných (nahoře) a pseudonáhodných (dole) čísel

1.4 Hešovací funkce

Hešovací funkce HSF je kryptografická funkce (viz obr. 1.6 vlevo), která číselnému argumentu D (nebo-li vzoru) o prakticky libovolné délce (jednotky bitů až trilióny triliónů bitů) přiřazuje tzv. heš H, což je číselná hodnota o pevně stanovené délce (typicky o délce 256 až 512 bitů). Formálně budeme tuto funkci zapisovat

H = HSF(D).

Od hešovací funkce se vyžadují dvě specifické vlastnosti, které se nazývají jednosměrnost a bezkoliznost. Jednosměrnost (obr. uprostřed) znamená, že určení hodnoty heše H je pro zadaný vzor D výpočetně snadné, avšak určení hodnoty vzoru D ze znalosti jeho heše H je prakticky nemožné. Bezkolizností (obr. vpravo) se rozumí, že je prakticky nemožné nalézt nějakou dvojici různých vzorů D1 a D2 takovou, aby jejich heše byly stejné. V této souvislosti je zapotřebí si uvědomit, že počet číselných posloupností libovolné délky (tj. počet vzorů) je vždy větší než počet posloupností jediné možné délky (tj. hešů). Z toho pak plyne, že mnoho vzorů musí mít stejný heš (tzv. kolize). Požaduje se však, aby nalezení kolize bylo prakticky nemožné.

Obrázek 1.6: Hešovací funkce a její vlastnosti

Jak v dalším uvidíme, tak jednosměrnost a bezkoliznost předurčuje hešovací funkce pro širokou škálu aplikací. Kromě vlastního samostatného nasazení jsou i důležitou komponentou zejména autentizačních kryptosystémů.

1.5 Diffie-Hellmanova funkce

Základním stavebním kamenem hojně využívaného Diffie-Hellmanova (zkráceně DH) protokolu je funkce, kterou nazveme Diffie-Hellmanova funkce (DHF). Uvedenou funkci (přesněji zobrazení) lze definovat pomocí různých typů konečných grup, avšak my se ve výkladu omezíme na číselné grupy s operací násobení. Tato operace nám dovoluje definovat mocnění, kdy například V·V·V = V3, přičemž výchozí V i výsledné V3 jsou čísla dané grupy. Abychom nemuseli vysvětlovat modulární aritmetiku, tak použijeme notaci bez operace modulo, čímž bude vysvětlení vlastností funkce DHF principiálně srozumitelné i čtenářům, kteří tuto operaci neznají. Podle avizované notace je pro argument V a tajný parametr a výstupní hodnotou Diffie-Hellmanovy funkce hodnota

A = DHF(V, a) = Va.

B = DHF(V, b) = Vb.

Ze všeobecně známých vlastností mocnin pak pro Diffie-Hellmanovu funkci vyplývá, že

DHF(B, a) = Ba = (Vb)a = Vb·a = (Va)b = Ab = DHF(A, b).

Obrázek 1.7: Schéma Diffie-Hellmanova protokolu

– semena.