Úvod Perfektní bezpečnost Šifrovací systémy Redundance 3. Dopřejme si jistoty neboli trochu teorie Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 1. října 2021 O Úvod do problematiky Uvod Šifrovací systémy Perfektní bezpečnost Redundance Mnozí lidé používají svoji inteligenci k zjednodušení, mnozí k zesložitění (Erich Kästner) Úvod Perfektní bezpečnost Šifrovací systémy Redundance Mnozí lidé používají svoji inteligenci k zjednodušení, mnozí k zesložitění (Erich Kästner) Fl V této kapitole se pokusíme vytvořit teoretický základ pro naše dřívější úvahy. Zejména vymezíme pojem "perfektní bezpečnosti" šifrovacího systému. \S I I \S I X L I ty Q Šifrovací systémy • Teoretické základy □ t3 Úvod Perfektní bezpečnost Šifrovací systémy Redundance retické základy Podle našich předchozích představ si dohodnou odesílatel a příjemce nějaký klíč a zašifrují s ním zprávu. Správný pohled na věc se od této představy jemně odlišuje. Podle našich předchozích představ si dohodnou odesílatel a příjemce nějaký klíč a zašifrují s ním zprávu. Správný pohled na věc se od této představy jemně odlišuje. Budeme nyní uvažovat systémy, které sestávají z nějaké množiny zpráv, příslušných kryptogramu a klíčů. V případě, že bychom následující myšlenky chtěli provést zcela precizně, museli bychom se držet axiomatiky; pro naše účely však bude lepší vysvětlení pojmů pomocí typických příkladů. Podle našich předchozích představ si dohodnou odesílatel a příjemce nějaký klíč a zašifrují s ním zprávu. Správný pohled na věc se od této představy jemně odlišuje. Budeme nyní uvažovat systémy, které sestávají z nějaké množiny zpráv, příslušných kryptogramu a klíčů. V případě, že bychom následující myšlenky chtěli provést zcela precizně, museli bychom se držet axiomatiky; pro naše účely však bude lepší vysvětlení pojmů pomocí typických příkladů. Takovýmto typickým příkladem množiny zpráv je sbírka matematických knih v knihovně sekce matematika týkajících se kódování. Získáme pak šifrovací systém, pokud budeme navíc uvažovat všech 312 afinních šifer s příslušnými kryptogramy. Úvod Perfektní bezpečnost Šifrovací systémy Redundance Teoretické základy II Získáme pak šifrovací systém, pokud budeme navíc uvažovat všech 312 afinních šifer s příslušnými kryptogramy. Pro jiný případ stačí vzít všechna slova cizího původu vyskytující se v tomto textu, všech 26 aditivních posouvacích šifrování a výsledné kryptogramy. Úvod Perfektní bezpečnost Šifrovací systémy Redundance retické základy Zaveďme následující označení. Pomocí písmene M (message) označíme množinu všech zpráv, C (cryptogram) množinu všech kryptogramu (obvykle se jedná o řetězce nad konečnými abecedami Z1 a Z2) a K (key) množinu všech klíčů. Zaveďme následující označení. Pomocí písmene M (message) označíme množinu všech zpráv, C (cryptogram) množinu všech kryptogramu (obvykle se jedná o řetězce nad konečnými abecedami Z1 a Z2) a K (key) množinu všech klíčů. Šifrovacím systémem (kryptosystémem) pak nazýváme trojici (M, K, C) spolu s dodatečným předpokladem, že existují funkce (neboli algoritmy) e a d takové, že eMxK^C a dCxK^M a že pro všechna (M, K) e M x K platí: cř(e(M, K), K) = M. Úvod Perfektní bezpečnost Šifrovací systémy Redundance retické základy Zejména tedy pro každý klíč K máme invertibilní funkci (transformaci) fK : M C tak, že fo(M) = e(M,K) a fK-\fK(M)) = M. Úvod Perfektní bezpečnost Šifrovací systémy Redundance retické základy Zejména tedy pro každý klíč K máme invertibilní funkci (transformaci) fK : M -> C tak, že fK(M) = e(M,K) a fK-\fK(M)) = M. Systém {fi<)KeK Je nazýván šifrovací algoritmus. Úvod Perfektní bezpečnost Šifrovací systémy Redundance Teoretické základy IV Zejména tedy pro každý klíč K máme invertibilní funkci (transformaci) fK : M C tak, že fK{M) = e{M,K) a fK-\fK{MI)) = M. Systém (f^KeK Je nazÝván šifrovací algoritmus. Key generator M Encryptor e C = e(M. K) Decryptor d —._^ —^ l^Enem^ Úvod Perfektní bezpečnost Šifrovací systémy Redundance retické základy Výše uvedená definice byla formulována praotcem modern kryptografie Claudem E. Shannonem. Úvod Perfektní bezpečnost Šifrovací systémy Redundance retické základy Výše uvedená definice byla formulována praotcem moderní kryptografie Claudem E. Shannonem. Uveďme dvě triviální pozorování: O Je možné, že dvě různé transformace převádí tutéž zprávu Úvod Perfektní bezpečnost Šifrovací systémy Redundance T( retické základy Výše uvedená definice byla formulována praotcem moderní kryptografie Claudem E. Shannonem. Uveďme dvě triviální pozorování: O Je možné, že dvě různé transformace převádí tutéž zprávu najeden kryptogram. Q Skutečnost, že transformace je invertibilní, implikuje M < ICL • Komunikační kanál • Ekvivokace • Příklady • Vlastnosti • Skládání kryptosystémů Q Perfektní bezpečnost • Bezpečný systém Úvod Perfektní bezpečnost Bezpečný systém Příklady Šifrovací systémy Redundance Komunikační kanál Vlastnosti Bezpečný systém I Ekvivokace Skládání Nyní víme, co je šifrovací systém. Těžištěm tohoto odstavce je podání definice a popisu bezpečného šifrovacího systému. Úvod Perfektní bezpečnost Bezpečný systém Příklady Šifrovací systémy Redundance Komunikační kanál Vlastnosti Bezpečný systém I Ekvivokace Skládání Nyní víme, co je šifrovací systém. Těžištěm tohoto odstavce je podání definice a popisu bezpečného šifrovacího systému. Intuivně řečeno znamená "perfektní bezpečnost", že Mr. X nemá žádnou šanci zvětšit své znalosti o systému, i kdyby měl k dispozici všechno vědění a všechnu počítačovou kapacitu světa. Úvod Perfektní bezpečnost Bezpečný systém Příklady Šifrovací systémy Redundance Komunikační kanál Vlastnosti Bezpečný systém I Ekvivokace Skládání Nyní víme, co je šifrovací systém. Těžištěm tohoto odstavce je podání definice a popisu bezpečného šifrovacího systému. Intuivně řečeno znamená "perfektní bezpečnost", že Mr. X nemá žádnou šanci zvětšit své znalosti o systému, i kdyby měl k dispozici všechno vědění a všechnu počítačovou kapacitu světa. Předpokládejme nyní, že máme šifrovací systém (M, K, C) a že Úvod Perfektní bezpečnost Bezpečný systém Příklady Šifrovací systémy Redundance Komunikační kanál Vlastnosti Bezpečný systém I Ekvivokace Skládání Nyní víme, co je šifrovací systém. Těžištěm tohoto odstavce je podání definice a popisu bezpečného šifrovacího systému. Intuivně řečeno znamená "perfektní bezpečnost", že Mr. X nemá žádnou šanci zvětšit své znalosti o systému, i kdyby měl k dispozici všechno vědění a všechnu počítačovou kapacitu světa. Předpokládejme nyní, že máme šifrovací systém (M, K, C) a že (a) Pí je pravděpodobnost, že je odeslána zpráva Mh 1 < / < n = \M\ \ tyto pravděpodobnosti se nazývají a priori (nebo teoretické) pravděpodobnosti a jsou přirozeně každému dobrému kryptoanalytikovi známy. Úvod Perfektní bezpečnost Bezpečný systém Příklady Šifrovací systémy Redundance Komunikační kanál Vlastnosti Bezpečný systém I Ekvivokace Skládání Nyní víme, co je šifrovací systém. Těžištěm tohoto odstavce je podání definice a popisu bezpečného šifrovacího systému. Intuivně řečeno znamená "perfektní bezpečnost", že Mr. X nemá žádnou šanci zvětšit své znalosti o systému, i kdyby měl k dispozici všechno vědění a všechnu počítačovou kapacitu světa. Předpokládejme nyní, že máme šifrovací systém (M, K, C) a že (a) Pí je pravděpodobnost, že je odeslána zpráva Mh 1 < / < n = \M\ \ tyto pravděpodobnosti se nazývají a priori (nebo teoretické) pravděpodobnosti a jsou přirozeně každému dobrému kryptoanalytikovi známy. (b) pravděpodobnost, že je použit klíč Kj je kj a výběr klíče nezávisí na zprávě, která je přenášena. Úvod Perfektní bezpečnost Bezpečný systém Příklady Šifrovací systémy Redundance Komunikační kanál Vlastnosti Bezpečný systém II Ekvivokace Skládání Tato dvě rozdělení pravděpodobností indukují rozdělení pravděpodobností na množině možných kryptogramu, kde pro jistý kryptogram C, řekněme Cu, je pravděpodobnost, že "náhodný" kryptogram C je roven kryptogramu Cu, určena vztahem kde v sumě na pravé straně sčítáme přes všechny dvojice zpráva-klíč (Mh Kj) takové, že e(Mh Kj) = Cu. Úvod Perfektní bezpečnost Bezpečný systém Příklady Šifrovací systémy Redundance Komunikační kanál Vlastnosti Bezpečný systém II Ekvivokace Skládání Tato dvě rozdělení pravděpodobností indukují rozdělení pravděpodobností na množině možných kryptogramu, kde pro jistý kryptogram C, řekněme Cu, je pravděpodobnost, že "náhodný" kryptogram C je roven kryptogramu Cu, určena vztahem kde v sumě na pravé straně sčítáme přes všechny dvojice zpráva-klíč (Mh Kj) takové, že e(Mh Kj) = Cu. Výše uvedené lze přeformulovat následovně pomocí pojmu náhodné veličiny. Úvod Perfektní bezpečnost Bezpečný systém Příklady Šifrovací systémy Redundance Komunikační kanál Vlastnosti Bezpečný systém III Ekvivokace Skládání Mějme tři náhodné veličiny M, K, C tak, že O jev M = Mj znamená, že byla odeslány zpráva e M, Úvod Perfektní bezpečnost Bezpečný systém Příklady Šifrovací systémy Redundance Komunikační kanál Vlastnosti Bezpečný systém III Ekvivokace Skládání Mějme tři náhodné veličiny M, K, C tak, že Q jev M = Mj znamená, že byla odeslány zpráva e M C) jev K = Kj znamená, že byl pro šifrování vybrán klíč Úvod Perfektní bezpečnost Bezpečný systém Příklady Šifrovací systémy Redundance Komunikační kanál Vlastnosti Bezpečný systém III Ekvivokace Skládání Mějme tři náhodné veličiny M, K, C tak, že © jev M = Mj znamená, že byla odeslány zpráva e M, C) jev K = Kj znamená, že byl pro šifrování vybrán klíč Kje K a Q) jev C = Ca znamená, že byl zachycen kryptogram Úvod Perfektní bezpečnost Bezpečný systém Příklady Šifrovací systémy Redundance Komunikační kanál Vlastnosti Bezpečný systém III Ekvivokace Skládání Mějme tři náhodné veličiny M, K, C tak, že © jev M = Mj znamená, že byla odeslány zpráva e M, C) jev K = Kj znamená, že byl pro šifrování vybrán klíč Kje K a O jev C = Ca znamená, že byl zachycen kryptogram Cu e C. Zejména tedy O P(M = Mj)=pj Úvod Perfektní bezpečnost Bezpečný systém Příklady Šifrovací systémy Redundance Komunikační kanál Vlastnosti Bezpečný systém III Ekvivokace Skládání Mějme tři náhodné veličiny M, K, C tak, že Q jev M = Mj znamená, že byla odeslány zpráva e M C) jev K = Kj znamená, že byl pro šifrování vybrán klíč Kje K a O jev C = Ca znamená, že byl zachycen kryptogram Cu e C. Zejména tedy © P(M = M,) = p,- a © P(K = Kj) = P(K = Kj\M = Mj) = kj pro všechna / a všechna y. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál 1 Připomeňme, že výše uvedená situace je analogická situaci v teorii kódování pro případ zdroje bez paměti. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál 1 Připomeňme, že výše uvedená situace je analogická situaci v teorii kódování pro případ zdroje bez paměti. Přitom považujeme zdroj za proud symbolů jisté konečné abecedy. Zdroj má obvykle nějaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál 1 Připomeňme, že výše uvedená situace je analogická situaci v teorii kódování pro případ zdroje bez paměti. Přitom považujeme zdroj za proud symbolů jisté konečné abecedy. Zdroj má obvykle nějaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Tento náhodný mechanismus může být poměrně dost komplikovaný, ale my se budeme pro okamžik soustředit na následující opravdu speciální a jednoduchý příklad. Připomeňme, že výše uvedená situace je analogická situaci v teorii kódování pro případ zdroje bez paměti. Přitom považujeme zdroj za proud symbolů jisté konečné abecedy. Zdroj má obvykle nějaký náhodný mechanismus, který je založen na statistice situace, která je modelovaná. Tento náhodný mechanismus může být poměrně dost komplikovaný, ale my se budeme pro okamžik soustředit na následující opravdu speciální a jednoduchý příklad. Značí-li Xj Mý symbol vytvořený zdrojem, dohodneme se pak, že, pro každý symbol ay, pravděpodobnost P(X, = ay) = pj je nezávislá na / a tedy je nezávislá na všech minulých nebo v budoucnosti vyslaných symbolech. «fl>«»><»> Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál II Jinak řečeno, X1, X2,... je právě posloupnost identicky distribuovaných, nezávislých náhodných veličin. Takovýto zdroj nazveme zdrojem s nulovou pamětí nebo zdrojem bez paměti a jeho entropie H je definována jako kde sčítáme přes množinu j takových, že py > 0. Jinak řečeno, X1, X2,... je právě posloupnost identicky distribuovaných, nezávislých náhodných veličin. Takovýto zdroj nazveme zdrojem s nulovou pamětí nebo zdrojem bez paměti a jeho entropie H je definována jako kde sčítáme přes množinu j takových, že py > 0. Připomeňme, že jsou-li X1,..., Xm náhodné proměnné takové, že každá z nich nabývá pouze konečně mnoha hodnot, lze pak považovat X = (X1,..., Xm) za náhodný vektor a definovat souhrnou entropii X1,..., Xm jako H(X) = -^2p(xu...,xm) • \og2p(xu...,xm), (3.1) k kde p(x1,..., xm) = P(X| = x1, X2 = x2j..., Xm = x^). Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál III Předpokládejme dále, že X je náhodná proměnná na pravděpodobnostním prostoru Q a A je událost z Q. Nabývá-li X konečné množiny hodnot {a, : 1 < / < rn}5 je přirozené definovat podmíněnou entropii náhodné proměnné X určenou událostí A jako m H(X\A) = -Y,P(X = ak\A)logP(X = ak\A). Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál III Předpokládejme dále, že X je náhodná proměnná na pravděpodobnostním prostoru Q a A je událost z Q. Nabývá-li X konečné množiny hodnot {a, : 1 < / < rn}5 je přirozené definovat podmíněnou entropii náhodné proměnné X určenou událostí A jako m H(X\A) = - P{X = ak\A)\ogP{X = ak\A). /c=1 Úplně stejně, je-li Y jiná náhodná proměnná nabývající hodnot bk (1 < k < m), definujeme podmíněnou entropii náhodné proměnné X určenou náhodnou proměnnou Y jako H{X\Y) = Y/H{X\Y = bj)P{Y = bJ). i Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál IV Považujeme H(X\Y) za entropii náhodné proměnné X určenou jistou hodnotou Y zprůměrovanou přes všechny hodnoty, jichž může / nabývat. Uvod Perfektní bezpečnost Bezpečný systém Příklady Šifrovací systémy Redundance Komunikační kanál Vlastnosti Ekvivokace Skládání Komunikační kanál IV Považujeme H{X\Y) za entropii náhodné proměnné X určenou jistou hodnotou Y zprůměrovanou přes všechny hodnoty, jichž může / nabývat. Diskrétní kanál bez paměti\e charakterizován vstupní abecedou z-i = {a-i,..., am} vstupních znaků, výstupní abecedou z2 = {ď-i ,..., bn} výstupních znaků a maticí P kanálu í P11 021 012 022 01n-1 02n-1 0m-11 0m-12 V 0m1 0m2 01 n 02n PA77— 1 A7— 1 P/T7—1 H Pmn-Á P m n ) Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál V Způsob používání kanálu je následující: každá posloupnost , L/2,..., un) symbolů ze vstupní abecedy Z1 na vstupu se převede na posloupnost , v2,..., vN) téže délky symbolů z výstupní abecedy Z2 na výstup tak, že P(vk = bj\uk = ai) = Pij (1 < / < m, 1 < j < n), a to nezávisle pro každé /c, 1 < k < N. Uvod Šifrovací systémy Perfektní bezpečnost Redundance ezpečný systém munikační kanál Způsob používání kanálu je následující: každá posloupnost , L/2,..., un) symbolů ze vstupní abecedy Z1 na vstupu se převede na posloupnost , v2,..., vN) téže délky symbolů z výstupní abecedy Z2 na výstup tak, že P(vk = bj\uk = ai) = Pij (1 < / < m, 1 < j < n), a to nezávisle pro každé /c, 1 < k < N. Implicitně je ve výše uvedeném obsaženo, že pro každé /. 1 < i < m platí j Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál VI Matice P s nezápornými hodnotami taková, že součet prvků v každém řádku je roven 1, se nazývá stochastická matice, v teorii náhodných procesů mluvíme o matici přechodu markovského řetězce. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál VI Matice P s nezápornými hodnotami taková, že součet prvků v každém řádku je roven 1, se nazývá stochastická matice, v teorii náhodných procesů mluvíme o matici přechodu markovského řetězce. Kapacita komunikačního kanálu je míra jeho schopnosti přenášet informaci. Formální definice je motivována níže uvedeným: Předpokládejme, že máme diskrétní kanál bez paměti se vstupní abecedou Z1 = {a-i,..., am}, výstupní abecedou $Z2 = ,..., bn} a maticí P kanálu p = [p7y] = p(by obdrženo a, odesláno). Uvod Šifrovací systémy Perfektní bezpečnost Redundance ezpečný systém munikační kanál Přidáme-li k tomuto kanálu zdroj S bez paměti, který vysílá symboly a^,..., am s pravděpodobnostmi p1,..., pm, pak výstup kanálu můžeme považovat za zdroj J bez paměti, který vysílá symboly ,..., bn s pravděpodobnostmi q1 ,..., qn, kde Qy = YjI=-\ p{bj obdrženo|a, odesláno)P(a, odesláno) Uvod Šifrovací systémy Perfektní bezpečnost Redundance ezpečný systém munikační kanál Přidáme-li k tomuto kanálu zdroj S bez paměti, který vysílá symboly ,..., am s pravděpodobnostmi p1,..., pm, pak výstup kanálu můžeme považovat za zdroj J bez paměti, který vysílá symboly ,..., bn s pravděpodobnostmi q1 ,..., qn, kde Qy = YJJU P(Pj obdrženo|a, odesláno)P(a, odesláno) Jsou-li U a V dva náhodné vektory, definujeme informaci o U poskytnutou V jako číslo /(U|V) = H(U)-H(U|V). Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál VII Jinak řečeno, /(U|V) vyjadřuje množství nejistoty o U odstraněné V. Totiž, množství informace, průměrně obsažené v jednom znaku zprávy, je entropie vstupního rozdělení H(S) = - S/P/log p,. Při přenosu diskrétním kanálem se ztratí informace H{S/J) = -J2píj\oqpíj ij průměrně najeden znak. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál VII Jinak řečeno, /(U|V) vyjadřuje množství nejistoty o U odstraněné V. Totiž, množství informace, průměrně obsažené v jednom znaku zprávy, je entropie vstupního rozdělení H(S) = - S/P/log p/. Při přenosu diskrétním kanálem se ztratí informace H{S/J) = -J2píj\oqpíj ij průměrně najeden znak. Zbývá pak H(S) - H{S/J) přenesené informace. Jestliže entropii počítáme v bitech a známe průměrnou dobu r, kterou kanál spotřebuje na přenos jednoho znaku, je rychlost přenosu ,fc\*\ H{S)-H{S/J) l{S\J) = ——-——- bitu za sekundu. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál VIII Často se za jednotku času volí jeden přenos znaku a potom l{S\J) = H(S) - H{S/J) bitů za jednotku času. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál VIII Často se za jednotku času volí jeden přenos znaku a potom l{S\J) = H(S) - H(S/J) bitů za jednotku času. Informace o S podaná pomocí J je pak rovna l{S\J) = H{S) - H{S\J) = H(S) + H{J) - H{S, J) a je to funkce, která závisí pouze na pravděpodobnostním rozdělení q^,...,qma maticí kanálu P. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál IX Proto je přirozené definovat kapacitu C kanálu jako maximální rychlost přenosu, tedy C = sup l{S\J), (3.2) kde supremum je bráno přes všechny zdroje bez paměti S, nebo, ještě přesněji, nad všemi možnými rozděleními pravděpodobností (p1,..., pn). Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Komunikační kanál IX Proto je přirozené definovat kapacitu C kanálu jako maximální rychlost přenosu, tedy C = sup l{S\J), (3.2) kde supremum je bráno přes všechny zdroje bez paměti S, nebo, ještě přesněji, nad všemi možnými rozděleními pravděpodobností (p1,..., pn). V dalším tedy můžeme považovat M za zdroj bez paměti s šifrovací funkcí e, přičemž klíče slouží jako komunikační kanál. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Ekvivokace 1 Základním pojmem je pojem klíčové ekvivokace zavedený Shannonem H(K|C). Ten nám měří průměrnou nejistotu, která nám zůstává po zachycení kryptogramu C. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Ekvivokace 1 Základním pojmem je pojem klíčové ekvivokace zavedený Shannonem H(K|C). Ten nám měří průměrnou nejistotu, která nám zůstává po zachycení kryptogramu C. Podobně budeme definovat ekvivokaci zpráv jakožto H(M|C). Občas budeme psát S = (M, K, C) a budeme značit H(S) klíčovou ekvivokaci H(K|C). Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Ekvivokace 1 Základním pojmem je pojem klíčové ekvivokace zavedený Shannonem H(K|C). Ten nám měří průměrnou nejistotu, která nám zůstává po zachycení kryptogramu C. Podobně budeme definovat ekvivokaci zpráv jakožto H(M|C). Občas budeme psát S = (M, K, C) a budeme značit H(S) klíčovou ekvivokaci H(K|C). Náhodná proměnná zpráv má pak entropii zpráv H(M) = -J^p/logp/. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Ekvivokace II Jsou-li po řadě K a C náhodné proměnné klíčů a kryptogramu, jsou pak klíčová entropie H(K) a entropie kryptogramu definovány jakožto «(K)=- E P(K = K/)logP(K = Kil H(C)=-E^(C = Cy)logP(C = Cy), kde sumace je prováděna přes všechny možné klíče K\ a všechny možné kryptogramy C,. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Ekvivokace II Jsou-li po řadě K a C náhodné proměnné klíčů a kryptogramu, jsou pak klíčová entropie H(K) a entropie kryptogramu definovány jakožto «(K)=- E P(K = K/)logP(K = Kil H(C)=-E^(C = Cy)logP(C = Cy), kde sumace je prováděna přes všechny možné klíče K\ a všechny možné kryptogramy Cy. Následující vlastnost ekvivokace vyjadřuje tu skutečnost, že daleko více nejistoty je spjato s klíčem než se zprávou. ^mmiiiiiiiiiiiiiiiiiiiiiiiiiiM Klíčová ekvivokace je určena ekvivokací zprávy vztahem H(K|C) = H(M|C) + H(K|M,C). Uvod Šifrovací systémy Perfektní bezpečnost Redundance ezpečný systém munikační kanál Příklady Vlastnosti Skládání Důkaz. Připomeňme základní identitu pro entropii H(X\Y) = H{X, Y) - H(Y). Můžeme tedy psát H(M|C)=H(M,C) - H(C) =H(M, K, C) - H(K|M, C) - H(C) Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Ekvivokace III Důkaz. Připomeňme základní identitu pro entropii H(X\Y) = H(X, Y) - H(Y). Můžeme tedy psát H(M|C)=H(M,C) - H(C) =H(M, K, C) - H(K|M, C) - H(C). Nyní tedy i H(K|C)=H(K,C)-H(C) =H(M, K, C) - H(M|K, C) - H(C). Uvod Šifrovací systémy Perfektní bezpečnost Redundance ezpečný systém munikační kanál Příklady Vlastnosti Skládání Důkaz. Připomeňme základní identitu pro entropii H(X\Y) = H{X, Y) - H(Y). Můžeme tedy psát H(M|C)=H(M,C) - H(C) =H(M, K, C) - H(K|M, C) - H(C) Nyní tedy i W(K|C)=H(K,C)-H(C) =H(M, K, C) - W(M|K, C) - H(C). Ale W(M|K,C) = 0. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Ekvivokace IV Příklady Vlastnosti Skládání Pokračování důkazu. Totiž, jakmile je znám kryptogram C a klíč K, je jednoznačně určena i zpráva M a tedy míra neurčitosti je nulová. Tedy H(K|C) = H(M,K,C)-H(C), což, porovnáno s výše uvedeným, nám dává dokazovanou identitu. I Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Ekvivokace IV Příklady Vlastnosti Skládání Pokračování důkazu Totiž, jakmile je znám kryptogram C a klíč K, je jednoznačně určena i zpráva M a tedy míra neurčitosti je nulová. Tedy H(K|C) = H(M,K,C)-H(C), což, porovnáno s výše uvedeným, nám dává dokazovanou identitu. I Důsledek 3.2 Klíčová ekvivokace je alespoň tak velká jako ekvivokace zprávy. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Ekvivokace V Příklady Vlastnosti Skládání Lemma 3.3 Pro každý kryptosystém (M, K, C) platí H(K,C) = H(M) + H(K). Důkaz. Protože náhodné veličiny K a M jsou nezávislé, víme, že H(M) + H{K) = H(M, K). Stačí tedy ověřit, že H(C,K) = W(M,K). Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Ekvivokace V Příklady Vlastnosti Skládání Lemma 3.3 Pro každý kryptosystém (M, K, C) platí H(K,C) = H(M) + H(K). ' Důkaz._ * Protože náhodné veličiny K a M jsou nezávislé, víme, že H(M) + H(K) = H(M, K). Stačí tedy ověřit, že H(C,K) = H(M,K). Protože H(MK, C) = 0 a H(C|K, M) = 0, máme H(M|K,C) = H(M,K,C) - H(K,C) = 0 H(C|K,M) = H(C, K, M) - H(K, M) = 0. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Ekvivokace V Příklady Vlastnosti Skládání Lemma 3.3 Pro každý kryptosystém (M, K, C) platí H{K,C) = H(M) + H(K) Důkaz. Protože náhodné veličiny K a M jsou nezávislé, víme, že H(M) + H(K) = H(M, K). Stačí tedy ověřit, že H(C,K) = H(M,K). Protože H(M|K,C) = 0 a H(C|K,M) = 0, máme H(M|K,C) = H(M,K,C) H(C|K,M) = H(C,K,M) Tedy i H(C, K) = H(M, K). I H(K,C) = 0 H(K,M) = 0 ^0 0,0 Uvod Šifrovací systémy Perfektní bezpečnost Redundance ezpečný systém munikační kanál Důsledek 3.4 Pro každý kryptosystém (M, K, C) platí H(C\K) = H(M\K), H{C, K) = H(M, K) a H(M) < H{C) Uvod Šifrovací systémy Perfektní bezpečnost Redundance ezpečný systém munikační kanál Důsledek 3.4 Pro každý kryptosystém (M, K, C) platí H{C\K) = H(M\K), H(C, K) = H(M, K) a H(M) < H(C). Důkaz. Stačí ověřit poslední nerovnost. H(M) + H(K) = H(M, K) = H(C, K) < H(C) + H(K) tj. H(M) < H(C). I Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Příklady 1 Příklad 3.5 O Předpokládejme, že "zprávy" v M jsou písmena slov nějaké (německé) knihy; pravděpodobnost zprávy je pak četnost odpovídajícího písmene; v případě písmene e je pakp{é) « 0.174. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Příklady 1 Příklad 3.5 O Předpokládejme, že "zprávy" v M jsou písmena slov nějaké (německé) knihy; pravděpodobnost zprávy je pak četnost odpovídajícího písmene; v případě písmene e je pakp{é) « 0.174. O Nyní předpokládejme, že "zprávy" v M jsou dvojice za sebou následujících písmen slov nějaké (německé) knihy; pravděpodobnost zprávy je pak četnost odpovídajícího bigramu. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Příklady 1 Příklad 3.5 O Předpokládejme, že "zprávy" v M jsou písmena slov nějaké (německé) knihy; pravděpodobnost zprávy je pak četnost odpovídajícího písmene; v případě písmene e je pakp{é) « 0.174. O Nyní předpokládejme, že "zprávy" v M jsou dvojice za sebou následujících písmen slov nějaké (německé) knihy; pravděpodobnost zprávy je pak četnost odpovídajícího bigramu. Představme si nyní, že Mr. X zachytil kryptogram C. Aby ho byl schopen analyzovat, může {alespoň teoreticky) vyzkoušet všechny zprávy a vždy určit pravděpodobnost toho, že kryptogram C vznikl zašifrováním zprávy M. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Označme pak tyto pravděpodobnosti Pc(M) = P(M\C); mluvíme pak o a posteriori (nebo pozorovaných) pravděpodobnostech. Uvod Šifrovací systémy Perfektní bezpečnost Redundance ezpečný systém munikační kanál Označme pak tyto pravděpodobnosti Pc(M) = P(M|C); mluvíme pak o a posteriori (nebo pozorovaných) pravděpodobnostech. O Buď M stejné jako ve výše uvedeném příkladu (a); jako algoritmus budeme uvažovat posouvací šifry se všemi 26 možnými klíči. Uvažme, že každé písmeno kryptogramu C má tutéž šanci, že odpovídá určitému písmenu zprávy; např. v 17,4% případů vznikne C ze, v 9,8% případů vznikne z n, atd. Jinak řečeno, pro každý kryptogram C platí pc(M) = p(M) pro každou zprávu M. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Příklady III Příklad 3.7 <3) Nyní předpokládejme, že každá zpráva v M sestává z prvních 100 písmen každé strany prvního dílu slovníku das große Brockhaus. Algoritmus nechť opět sestává z posouvacích šifer. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Příklady III Příklad 3.7 <3) Nyní předpokládejme, že každá zpráva v M sestává z prvních 100 písmen každé strany prvního dílu slovníku das große Brockhaus. Algoritmus nechť opět sestává z posouvacích šifer. Pro každou zprávu M je její pravděpodobnost ^, malé, ale stále ještě kladné číslo. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Příklady III Příklad 3.7 O Nyní předpokládejme, že každá zpráva v M sestává z prvních 100 písmen každé strany prvního dílu slovníku das große Brockhaus. Algoritmus nechť opět sestává z posouvacích šifer. Pro každou zprávu M je její pravděpodobnost ^, malé, ale stále ještě kladné číslo. Protože je relativně snadné prověřit, zda určitý kryptogram pochází z určité zprávy (rozdělení písmen v kryptogramu musí přesně odpovídat rozdělení písmen ve zprávě), je Pc(M) rovno buď jedné nebo nule. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Příklady III Příklad 3.7 <3) Nyní předpokládejme, že každá zpráva v M sestává z prvních 100 písmen každé strany prvního dílu slovníku das große Brockhaus. Algoritmus nechť opět sestává z posouvacích šifer. Pro každou zprávu M je její pravděpodobnost ^, malé, ale stále ještě kladné číslo. Protože je relativně snadné prověřit, zda určitý kryptogram pochází z určité zprávy (rozdělení písmen v kryptogramu musí přesně odpovídat rozdělení písmen ve zprávě), je Pc(M) rovno buď jedné nebo nule. To znamená obzvlášť, že pro každý kryptogram je pc{M)^p{M). J (J L j y L - J ■ L J ^3 q, ^ Uvod Šifrovací systémy Příklady III Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Příklady Vlastnosti Skládání Příklad 3.8 (Pokračování) i Proberme tuto skutečnost podrobněji: Předpokládejme, že kryptoanalytik Mr. X zjistí, že pro jistou zprávu M je Pc(M) > p(M). Pak by věděl, že kryptogram C vznikl s vysokou pravděpodobností ze zprávy M. Uvod Šifrovací systémy Příklady III Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Příklady Vlastnosti Skládání Příklad 3.8 (Pokračování) i Proberme tuto skutečnost podrobněji: Předpokládejme, že kryptoanalytik Mr. X zjistí, že pro jistou zprávu M je Pc(M) > p(M). Pak by věděl, že kryptogram C vznikl s vysokou pravděpodobností ze zprávy M. Tzn., že by se analýzou něco nového naučil. To ale nesmí při perfektním systému nastat. Uvod Šifrovací systémy Příklady III Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Příklady Vlastnosti Skládání Příklad 3.8 (Pokračování) i Proberme tuto skutečnost podrobněji: Předpokládejme, že kryptoanalytik Mr. X zjistí, že pro jistou zprávu M je Pc(M) > p(M). Pak by věděl, že kryptogram C vznikl s vysokou pravděpodobností ze zprávy M. Tzn., že by se analýzou něco nového naučil. To ale nesmí při perfektním systému nastat. V případě, že by bylo Pc(M) < p(M), pak by Mr. X věděl, že kryptogram C vznikne s velmi malou pravděpodobností ze zprávy M. I v tomto případě by si Mr. X rozšířil svoje znalosti. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Vlastnosti 1 Můžeme tedy definovat: Šifrovací systém (M, K, C) poskytuje perfektní bezpečnost, jestliže pro každý kryptogram C platí pc{M) = p{M) pro každou zprávu M. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Vlastnosti 1 Můžeme tedy definovat: Šifrovací systém (M, K, C) poskytuje perfektní bezpečnost, jestliže pro každý kryptogram C platí pc{M) = p{M) pro každou zprávu M. Jinak řečeno, šifrovacího systém (M, K, C) je perfektní, pokud jsou a priori pravděpodobnosti rovny pravděpodobnostem a posteriori (viz příklad (c)). Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Vlastnosti 1 Můžeme tedy definovat: Šifrovací systém (M, K, C) poskytuje perfektní bezpečnost, jestliže pro každý kryptogram C platí pc{M) = p{M) pro každou zprávu M. Jinak řečeno, šifrovacího systém (M, K, C) je perfektní, pokud jsou a priori pravděpodobnosti rovny pravděpodobnostem a posteriori (viz příklad (c)). Posouvací šifry jsou perfektní, jestliže operují nad jednotlivými písmeny. Mr. X se pak může namáhat jak chce; písmena kryptogramu jsou totiž zcela náhodně rozdělena. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Vlastnosti II Chceme-li perfektnost šifrovacího systému vyjádřit pomocí náhodných proměnných M a C, je systém perfektní právě tehdy, když M a C jsou nezávislé. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Vlastnosti II Chceme-li perfektnost šifrovacího systému vyjádřit pomocí náhodných proměnných M a C, je systém perfektní právě tehdy, když M a C jsou nezávislé. Z toho bezprostředně plyne, že šifrovací systém (M, K, C) poskytuje perfektní bezpečnost, jestliže pro každou zprávu M platí pM(C)=p(C) pro každý kryptogram C. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Vlastnosti III Věta 3.9 Kryptosystém (M, K, C) je perfektní právě tehdy, když H((M|(C) = H((M). Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Vlastnosti III Příklady Vlastnosti Skládání Věta 3.9 Kryptosystém (M, K, C) je perfektní právě tehdy, když H((M|(C) = H((M). Důkaz. Z teorie informace je známo, že H(M|C) = H(M) právě tehdy, když M a C jsou nezávislé náhodné proměnné Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Vlastnosti III Příklady Vlastnosti Skládání Věta 3.9 Kryptosystém (M, K, C) je perfektní právě tehdy, když H((M|(C) = H((M). Důkaz. Z teorie informace je známo, že H(M|C) = H(M) právě tehdy, když M a C jsou nezávislé náhodné proměnné tj. to je právě tehdy, když se jedná o perfektní kryptosystém. I Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Vlastnosti III Příklady Vlastnosti Skládání Věta 3.9 Kryptosystém (M, K, C) je perfektní právě tehdy, když H((M|(C) = H((M). Důkaz. Z teorie informace je známo, že H(M|C) = H(M) právě tehdy, když M a C jsou nezávislé náhodné proměnné tj. to je právě tehdy, když se jedná o perfektní kryptosystém. I Ptejme se nyní, jak můžeme rozpoznat, kdy je šifrovací systém perfektní či nikoliv. K tomu si dokážeme několik jednoduchých kritérií. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Vlastnosti IV 1. Kritérium Je-li šifrovací systém (M, K, C) perfektní, pak každá zpráva s odpovídajícím klíčem může být zobrazena na libovolný kryptogram. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém omunikační kanál 1. Kritérium Je-li šifrovací systém (M, K, C) perfektní, pak každá zpráva s odpovídajícím klíčem může být zobrazena na libovolný kryptogram. Proč platí toto kritérium? Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Vlastnosti IV 1. Kritérium Je-li šifrovací systém (M, K, C) perfektní, pak každá zpráva s odpovídajícím klíčem může být zobrazena na libovolný kryptogram. Proč platí toto kritérium? Uvažme zprávu M a kryptogram C. Protože (M, K, C) je perfektní, platí Pc(M) = p(M). V každém šifrovacím systému je p(M) > 0, protože každá zpráva se vyskytuje s kladnou pravdepodobností. Dohromady obdržíme Pc(M) > 0. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Vlastnosti IV Příklady Vlastnosti Skládání 1. Kritérium Je-li šifrovací systém (M, K, C) perfektní, pak každá zpráva s odpovídajícím klíčem může být zobrazena na libovolný kryptogram. Proč platí toto kritérium? Uvažme zprávu M a kryptogram C. Protože (M, K, C) je perfektní, platí Pc(M) = p(M). V každém šifrovacím systému je p(M) > 0, protože každá zpráva se vyskytuje s kladnou pravdepodobností. Dohromady obdržíme Pc(M) > 0. To znamená, že existuje klíč, pomocí kterého se zašifruje M do C. (Kdyby žádný takový klíč neexistoval, nutně bychom měli, že pc(M) = 0.) Tím je dokázáno první kritérium. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Vlastnosti IV 1. Kritérium Je-li šifrovací systém (M, K, C) perfektní, pak každá zpráva s odpovídajícím klíčem může být zobrazena na libovolný kryptogram. Proč platí toto kritérium? Uvažme zprávu M a kryptogram C. Protože (M, K, C) je perfektní, platí Pc(M) = p(M). V každém šifrovacím systému je p(M) > 0, protože každá zpráva se vyskytuje s kladnou pravdepodobností. Dohromady obdržíme Pc(M) > 0. To znamená, že existuje klíč, pomocí kterého se zašifruje M do C. (Kdyby žádný takový klíč neexistoval, nutně bychom měli, že Pc(M) = 0.) Tím je dokázáno první kritérium. Toto kritérium je velmi užitečné - v "negativním smyslu": Umožní nám rozhodnout, že jisté systémy nejsou perfektní. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Vlastnosti V Bezpečný systém Komunikační kanál Ekvivokace Příklady Vlastnosti Skládání 2. Kritérium Je-li šifrovací systém (M, K, C) perfektní, pak platí: Ml < ICI < IKI Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Vlastnosti V 2. Kritérium Je-li šifrovací systém (M, K, C) perfektní, pak platí: IMI < ICI < IKI. Důkaz. Zřejmě |M| < |C|. Proč platí j O | < |K|? Uvažme libovolnou, pevně zvolenou zprávu M a zašifrujme ji pomocí všech možných klíčů z LU, P(C = C,\M = Mk) ■ P(M = Mk) Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Vlastnosti VII Důkaz - 3. Kritérium. Stačí zřejmě ověřit, že pro každou zprávu M, platí P(M = Mj\C= Cj) = P(M) pro každý kryptogram Cy. Z Bayesova vzorce máme P(M = Mj\C = Cj)= P(C = Ci\M = Mi). P(M = Mi) Z[% P(C = Cj\M = Mk) ■ P(M = Mk) P(M= M j) = = EÍc1 P(M = Mk) " Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Vlastnosti VII Příklady Vlastnosti Skládání Důkaz - 3. Kritérium. Stačí zřejmě ověřit, že pro každou zprávu M,- platí P(M = M/l C = Cj) = P(M) pro každý kryptogram Cy. Z Bayesova vzorce máme P(M = M,\C = Cj)= P(Q = Oi\M = M,) ■ P(M = Mi) EÍ2i P{C = Cj\M = Mk) ■ P(M = Mk) --P(M = Mj) = p{M = Mjl E/c=i P{M = Mk) neboť P(C = Cj\M = Mk) = nezávisle na jak. I Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Vlastnosti VIII Na základě třetího kritéria lze přirozeným způsobem konstruovat perfektní šifrovací systémy (čtyřem klíčům a jím příslušným transformacím odpovídají různě šrafované šipky). Uvod Šifrovací systémy Perfektní bezpečnost Redundance ezpečný systém munikační kanál Přirozeným způsobem, jak zvýšit bezpečnost šifrování, je vzít různé systémy a kombinovat je. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Příklady Vlastnosti Skládání Skládání kryptosystémů I Přirozeným způsobem, jak zvýšit bezpečnost šifrování, je vzít různé systémy a kombinovat je. Dvě takovéto metody navržené Shannonem jsou stále základem mnoha praktických kryptosystémů. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Příklady Vlastnosti Skládání Skládání kryptosystémů I Přirozeným způsobem, jak zvýšit bezpečnost šifrování, je vzít různé systémy a kombinovat je. Dvě takovéto metody navržené Shannonem jsou stále základem mnoha praktických kryptosystémů. Jedná se o vážený součet a součin kryptosystémů. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Skládání kryptosystémů II a Vážený součet: Jsou-li Si a S2 dva kryptosystémy se stejným prostorem zpráv M = = M2 a 0 < p < 1, je pak jejich vážený součet pS-i + (1 - p)S2 kryptosystém určený následným výběrem: použijeme Si s pravděpodobností p a S2 s pravděpodobností 1 - p. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Bezpečný systém Komunikační kanál Ekvivokace Příklady Vlastnosti Skládání Skládání kryptosystémů II a Vážený součet: Jsou-li Si a S2 dva kryptosystémy se stejným prostorem zpráv M = = M2 a 0 < p < 1, je pak jejich vážený součet pS-i + (1 - p)S2 kryptosystém určený následným výběrem: použijeme Si s pravděpodobností p a S2 s pravděpodobností 1 - p. Má-li tedy Si klíče K^...,Kms pravděpodobnostmi použití p, pro klíč Kj a S2 má klíče K\, ...,Křns pravděpodobnostmi použití p- pro klíč Kj, má pak kryptosystém pS-i + (1 - p)S2 m + n klíčů /C|,..., Km, K\,...,Křns pravděpodobnostmi použití pp, pro klíč Kj as pravděpodobnostmi použití (1 -p)p- pro klíč Kj. a Vážený součet: Jsou-li Si a S2 dva kryptosystémy se stejným prostorem zpráv M = = M2 a 0 < p < 1, je pak jejich vážený součet pS-i + (1 - p)S2 kryptosystém určený následným výběrem: použijeme Si s pravděpodobností p a S2 s pravděpodobností 1 - p. Má-li tedy Si klíče K^...,Kms pravděpodobnostmi použití p, pro klíč Kj a S2 má klíče K\, ...,Křns pravděpodobnostmi použití p- pro klíč Kj, má pak kryptosystém pS-i + (1 - p)S2 m + n klíčů /C|,..., Km, K\,...,Křns pravděpodobnostmi použití pp, pro klíč Kj as pravděpodobnostmi použití (1 -p)p- pro klíč Kj. Tento postup lze přirozeně rozšířit na více než dva systémy. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Skládání kryptosystémů III • Součin: Druhý způsob kombinování kryptosystémů Si a S2 je to, že nejprve použijeme na naši zprávu kryptosystém Si a potom aplikujeme S2 na výsledný kryptogram. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Skládání kryptosystémů III • Součin: Druhý způsob kombinování kryptosystémů Si a S2 je to, že nejprve použijeme na naši zprávu kryptosystém Si a potom aplikujeme S2 na výsledný kryptogram. Abychom toto mohli provést, musí být nutně C^ c M2. Pak můžeme definovat součin jako S-|*S2. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Skládání kryptosystémů III • Součin: Druhý způsob kombinování kryptosystémů Si a S2 je to, že nejprve použijeme na naši zprávu kryptosystém Si a potom aplikujeme S2 na výsledný kryptogram. Abychom toto mohli provést, musí být nutně Ci c M2. Pak můžeme definovat součin jako Si*S2. Jsou-li klíče Kí,..., Km s pravděpodobnostmi použití p, pro klíč Kj v kryptosystémů Si a S2 má klíče K\,...,K'n s pravděpodobnostmi použití p- pro klíč Kj, má pak kryptosystém Si*S2 m.n klíčů (Kh Kj) s pravděpodobnostmi použití p,p-. • Součin: Druhý způsob kombinování kryptosystémů Si a S2 je to, že nejprve použijeme na naši zprávu kryptosystém Si a potom aplikujeme S2 na výsledný kryptogram. Abychom toto mohli provést, musí být nutně C^ c M2. Pak můžeme definovat součin jako S-|*S2. Jsou-li klíče Kí,..., Km s pravděpodobnostmi použití p, pro klíč Kj v kryptosystémů Si a S2 má klíče K\,...,K'n s pravděpodobnostmi použití p- pro klíč Kj, má pak kryptosystém Si*S2 m.n klíčů (Kh Kj) s pravděpodobnostmi použití p/p-. Poznamenejme, že skutečně efektivních klíčů může být méně, protože některé se složených transformací mohou splývat. Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Skládání kryptosystémů IV Poznamenejme, že evidentně platí následující: Úvod Perfektní bezpečnost Šifrovací systémy Redundance B K E ezpečný systém Příklady omunikační kanál Vlastnosti kvivokace Skládání Skládání kryptosystémů IV Poznamenejme, že evidentně platí následující: Jsou-li Si, S2 a S3 kryptosystémy tak, že níže uvedené operace jsou definovány, 0(/' y)logp(/,y), / j kde p(ij) jsou odhadnuté výskyty symbolů (/,/) a my ignorujeme dvojice symbolů s nulovou pravděpodobností (např. Qq)- Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Podobně obdržíme He < H2E = -1 £ J>(/' y)logp(/,y), / j kde p(ij) jsou odhadnuté výskyty symbolů (/,/) a my ignorujeme dvojice symbolů s nulovou pravděpodobností (např. Qq)- Následující tabulka nám ukazuje přehled odhadů entropií pro 26- a 27-písmennou anglickou abecedu. 26-ti písmenná abeceda 27-ti písmenná abeceda 4.70 4.76 "h 4.14 4.03 3.56 3.32 he 3.30 3.10 Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Jiný přístup nalezení odhadu entropie je založený na četnosti slov. Považujme angličtinu za konečný jazyk skládající se ze slov i/i/i,..., wN, jež se vyskytují nezávisle s pravděpodobnostmi Pí, • • • ,P/v- Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Jiný přístup nalezení odhadu entropie je založený na četnosti slov. Považujme angličtinu za konečný jazyk skládající se ze slov 1/1/1,..., wN, jež se vyskytují nezávisle s pravděpodobnostmi Pí, • • • ,P/v- Pak slovní entropie Hw je určena vztahem n Hw = -J2pjlogpj. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Jiný přístup nalezení odhadu entropie je založený na četnosti slov. Považujme angličtinu za konečný jazyk skládající se ze slov i/i/i,..., wN, jež se vyskytují nezávisle s pravděpodobnostmi Pí, • • • ,P/v- Pak slovní entropie Hw je určena vztahem n Hw = -J2pjlogpj. /=1 Shannon navrhl, že pak entropii symbolů HE lze aproximovat jakožto HE = Hw/w. kde w je průměrná délka slova v angličtině.^ Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity K tomuto přístupu lze mít následující výhrady: • Slova použitá v angličtině nejsou nezávislá a slovní entropie je spíše odhad slovní entropie prvního řádu. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity K tomuto přístupu lze mít následující výhrady: • Slova použitá v angličtině nejsou nezávislá a slovní entropie je spíše odhad slovní entropie prvního řádu. • Podíl slovní entropie a průměrné délky slova je velmi hrubá aproximace a je nejlépe ji nahradit vhodnou nerovností. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity K tomuto přístupu lze mít následující výhrady: • Slova použitá v angličtině nejsou nezávislá a slovní entropie je spíše odhad slovní entropie prvního řádu. • Podíl slovní entropie a průměrné délky slova je velmi hrubá aproximace a je nejlépe ji nahradit vhodnou nerovností. Abychom vyčíslili slovní entropii, použijme pravidlo navržené lingvistou G. K. Zipfem (1935). Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity K tomuto přístupu lze mít následující výhrady: • Slova použitá v angličtině nejsou nezávislá a slovní entropie je spíše odhad slovní entropie prvního řádu. • Podíl slovní entropie a průměrné délky slova je velmi hrubá aproximace a je nejlépe ji nahradit vhodnou nerovností. Abychom vyčíslili slovní entropii, použijme pravidlo navržené lingvistou G. K. Zipfem (1935). To tvrdí, že, pokud jsou slova přirozeného jazyka uspořádána v klesajícím uspořádání podle jejich pravděpodobností výskytu (pn pak označuje pravděpodobnost n-tého nejvýše pravděpodobného slova), dobrá aproximace těchto pravděpodobností je určena formulí Pn = A/n, kde A je nějaká konstanta závisející na danpfri J3?yq% , , , , t Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Ačkoliv Zipfův přístup byl kritizován, jeho pravidlo dobře funguje pro tak různé jazyky jako je hebrejština, starogermánština, křováčtina a norština. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Ačkoliv Zipfův přístup byl kritizován, jeho pravidlo dobře funguje pro tak různé jazyky jako je hebrejština, starogermánština, křováčtina a norština. Shannon použil Zipfovo pravidlo jakožto aproximaci pro angličtinu s konstantou >A = 0.1 a počtem slov M = 12366. Platí 12366 12366 1 E A, = 0.1 £1 = 1, a pak je slovní entropie Hw = 9.72 bitů na slovo. Protože střední délka w anglických slov je 4.5, obdržíme odhad pro H45 ~ 9.72/4.5 = 2.16 bitů na písmeno. Úvod Perfektní bezpečnost Šifrovací systémy Redundance Droximace jazyka Odhad redundance izyk jako zdroj Bod unicity Úvod Perfektní bezpečnost Šifrovací systémy Redundance Droximace jazyka Odhad redundance izyk jako zdroj Bod unicity V každém anglickém textu jsou nejčastěji se vyskytujícími slovy the, and, of, to, be, a, in, I, a that. V textu je spousta dalších slov, která se nevyskytují tak často. Uvod Šifrovací systémy Perfektní bezpečnost Redundance jroximace jazyka k iako zdro Odhad redundance Bod unicity Proveďme nyní následující výpočet: oo Hw = ^2H(W: \ W\ = k)P(\W\ = k) /c=1 kde W je "náhodný' slovní výstup a | W\ označuje délku (nebo počet písmen) výstupu W. Uvod Šifrovací systémy Perfektní bezpečnost Redundance jroximace jazyka k iako zdro Odhad redundance Bod unicity Proveďme nyní následující výpočet: oo HW = ^2H(W: \ W\ = k)P(\W\ = /c), /c=1 kde W je "náhodný' slovní výstup a | W\ označuje délku (nebo počet písmen) výstupu W. Tedy Hw = Z?=iH(X,X2...Xk)P(\W\ = k) < Eľ=i^(X)P(|w/| = /c), kde H(X) je entropie symbolů HE a nerovnost bezprostředně vyplývá ze základní identity H{U, V) tj- Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Je známo, že zdroj s entropií H má v abecedě |Z| jednoznačně dešifrovatelné zakódování s minimální průměrnou délkou slova l(n) typického řetězce o n symbolech, přičemž l(n) « nH/log|Z Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Je známo, že zdroj s entropií H má v abecedě |Z| jednoznačně dešifrovatelné zakódování s minimální průměrnou délkou slova l(n) typického řetězce o n symbolech, přičemž l(n) « nH/log|Z Představíme-li si redundanci jako míru zbytečných symbolů (v procentech), je přirozeněji definovat následujícím přirozeným způsobem: l{n) ~ n(1 - fí/100). Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Je známo, že zdroj s entropií H má v abecedě |Z| jednoznačně dešifrovatelné zakódování s minimální průměrnou délkou slova l(n) typického řetězce o n symbolech, přičemž l(n) « nH/log|Z Představíme-li si redundanci jako míru zbytečných symbolů (v procentech), je přirozeněji definovat následujícím přirozeným způsobem: l{n) ~ n(1 - fí/100). Z výše uvedeného pak obdržíme R= 1 - H/log2|Z uvažujeme-li redundanci jako číslo mezi 0 a 1. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Přesný odhad redundance je obtížný; odhady zřejmě závisí na vybraném textu. Pokud je ale text zcela náhodný, bude jeho redundance rovna 0. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Přesný odhad redundance je obtížný; odhady zřejmě závisí na vybraném textu. Pokud je ale text zcela náhodný, bude jeho redundance rovna 0. Uveďme následující příklad Bible Měsíčník Hi 4,086 4,152 2,397 2,824 R 0,413 0,285 w 4,060 4,653 Zajímavější je studium identických pasáží Bible přeložených do různých jazyků. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Zajímavější je studium identických pasáží Bible přeložených do různých jazyků. Zatímco samojština je jazyk s pouze 16 písmeny, z nichž 60% tvoří samohlásky, ruština před rokem 1917 používala abecedu o 35 písmenech. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Zajímavější je studium identických pasáží Bible přeložených do různých jazyků. Zatímco samojština je jazyk s pouze 16 písmeny, z nichž 60% tvoří samohlásky, ruština před rokem 1917 používala abecedu o 35 písmenech. Srovnání viz v následující tabulce: Angličtina Ruština Samojština Hi 4,114 4,612 3,370 H-\2 2,397 2,395 2,136 R 0,413 0,474 0,372 w 4,060 5,296 3,174 Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Shannon odhadl, že entropii angličtiny lze redukovat najeden bit na písmeno, což by nám dávalo řádově redundanci asi 75%. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Shannon odhadl, že entropii angličtiny lze redukovat najeden bit na písmeno, což by nám dávalo řádově redundanci asi 75%. Tento odhad je však nutno interpretovat s jistou opatrností. Například výše uvedené neznamená, že můžeme rekonstruovat zprávu, ve které jsou písmena smazána s pravděpodobností §. Přesný způsob mazání je také důležitý. Úvod Perfektní bezpečnost Šifrovací systémy Redundance Jc Droximace jazyka Odhad redundance izyk jako zdroj Bod unicity Entropie a redundance V Shannon odhadl, že entropii angličtiny lze redukovat najeden bit na písmeno, což by nám dávalo řádově redundanci asi 75%. Tento odhad je však nutno interpretovat s jistou opatrností. Například výše uvedené neznamená, že můžeme rekonstruovat zprávu, ve které jsou písmena smazána s pravděpodobností §. Přesný způsob mazání je také důležitý. Jsou-li písmena smazána s pravděpodobností 0,5, pak například zpráva MATHEMATICS IS BEAUTIFUL může být obdržena ve tvaru MTMASSBUFL; a tedy by bylo opravdu obtížné získat zprávu pouze z narušeného textu. i □ i Bylo dokázáno, že kritická hodnota je p ~ 0,25 a pro vyšší hodnotu je obdržení původní zprávy nemožné. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Bylo dokázáno, že kritická hodnota je p ~ 0,25 a pro vyšší hodnotu je obdržení původní zprávy nemožné. Jinak řečeno, ačkoliv je teoreticky možné zkrátit vytištěný text na čtvrtinu jeho současné délky, náhodné zkrácení není vhodný způsob, jak toho dosáhnout. Je nám ale jasné, že velkou redukci lze obdržet smysluplným zakódováním. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Bylo dokázáno, že kritická hodnota je p ~ 0,25 a pro vyšší hodnotu je obdržení původní zprávy nemožné. Jinak řečeno, ačkoliv je teoreticky možné zkrátit vytištěný text na čtvrtinu jeho současné délky, náhodné zkrácení není vhodný způsob, jak toho dosáhnout. Je nám ale jasné, že velkou redukci lze obdržet smysluplným zakódováním. Např., lze bez obtíží akceptovat pravdivost následujících tvrzení: • Vynecháme-li nějaké písmeno z textu, lze ho zpětně zrekonstruovat. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Bylo dokázáno, že kritická hodnota je p ~ 0,25 a pro vyšší hodnotu je obdržení původní zprávy nemožné. Jinak řečeno, ačkoliv je teoreticky možné zkrátit vytištěný text na čtvrtinu jeho současné délky, náhodné zkrácení není vhodný způsob, jak toho dosáhnout. Je nám ale jasné, že velkou redukci lze obdržet smysluplným zakódováním. Např., lze bez obtíží akceptovat pravdivost následujících tvrzení: • Vynecháme-li nějaké písmeno z textu, lze ho zpětně zrekonstruovat. • Vynecháme-li všechny samohlásky z textu, lze text zpětně zrekonstruovat. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Oba tyto případy jsou příklady suboptimálního zakódování a vezmeme-li redundanci angličtiny mezi 75% a 50%, dostaneme, že entropie HE splňuje 1.19 0 : H{K\CN) = 0}, tj. H(Mu) + H(K) - H(Cu) = 0. Úvod Perfektní bezpečnost Šifrovací systémy Redundance roximace jazyka Odhad redundance lyk jako zdroj Bod unicity Předpokládejme, že platí následující: Přirozený jazyk, ve kterém šifrujeme, má tu vlastnost, že je dán vhodný odhad H(MN) jako H(MN) ~ A/H, kde H je entropie jednoho symbolu jazyka; Úvod Perfektní bezpečnost Šifrovací systémy Redundance roximace jazyka Odhad redundance lyk jako zdroj Bod unicity Předpokládejme, že platí následující: O Přirozený jazyk, ve kterém šifrujeme, má tu vlastnost, že je dán vhodný odhad H(MN) jako H(MN) ~ A/H, kde H je entropie jednoho symbolu jazyka; O kryptosystém má tu vlastnost, že všechny sekvence délky N symbolů mají stejnou pravděpodobnost jakožto kryptogram; jinak řečeno H(CN) ~ N\og\Z\. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity To není nevhodný požadavek: každý dobrý kryptosystém by měl mít tuto vlastnost. Z výše uvedeného obdržíme UH+H(K)- l/log|I| = 0, tj- Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity To není nevhodný požadavek: každý dobrý kryptosystém by měl mít tuto vlastnost. Z výše uvedeného obdržíme UH + H(K) - L/log|Z| = 0, tj- U = H(K) \og\Z\ - H Obvykle se rovněž předpokládá, že každý klíč můžeme vybrat se stejnou pravděpodobností a to znamená, že U = kde H je entropie symbolu zdroje. log|K log|Z - H Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Připomeňme, že existuje těsný vztah mezi bodem unicity kryptosystému a redundancí jazyka, ve kterém se přenáší zpráva. Úvod Perfektní bezpečnost Šifrovací systémy Redundance roximace jazyka Odhad redundance lyk jako zdroj Bod unicity Připomeňme, že existuje těsný vztah mezi bodem unicity kryptosystému a redundancí jazyka, ve kterém se přenáší zpráva. Přitom redundance R jazyka s entropií H je určena vztahem Úvod Perfektní bezpečnost Šifrovací systémy Redundance roximace jazyka Odhad redundance lyk jako zdroj Bod unicity Připomeňme, že existuje těsný vztah mezi bodem unicity kryptosystému a redundancí jazyka, ve kterém se přenáší zpráva. Přitom redundance R jazyka s entropií H je určena vztahem R= 1 - H log | Z a tedy U = log|K log|l q log | Z - H R\og\Z Úvod Perfektní bezpečnost Šifrovací systémy Redundance roximace jazyka Odhad redundance lyk jako zdroj Bod unicity Připomeňme, že existuje těsný vztah mezi bodem unicity kryptosystému a redundancí jazyka, ve kterém se přenáší zpráva. Přitom redundance R jazyka s entropií H je určena vztahem R= 1 - H log | Z a tedy U = log|K log|l q log | Z - H R\og\Z Zejména pak má-li jazyk nulovou redundanci, je pro každý kryptosystém splňující 1 a 2 bod unicity nekonečno. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Příklad 4.1 Předpokládejme, že šifrujeme pomocí jednoduché substituce tak, že máme právě 26! klíčů. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Příklad 4.1 Předpokládejme, že šifrujeme pomocí jednoduché substituce tak, že máme právě 26! klíčů. Uvaž ujeme-li log 26 = 4,7 a entropii anglického jazyka HE rovnu 2 bitům na symbol, obdržíme U = log 26 88,4 4.7-2 2.7 -32. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Příklad 4.1 Předpokládejme, že šifrujeme pomocí jednoduché substituce tak, že máme právě 26! klíčů. Uvaž ujeme-li log 26 = 4,7 a entropii anglického jazyka HE rovnu 2 bitům na symbol, obdržíme U = log 26 88,4 4,7-2 2,7 -32. Jinak řečeno, při výše uvedené entropii anglického jazyka jsme obdrželi hodnotu bodu unicity rovnu 32 symbolům. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity To pak celkem souhlasí s empirickým pozorováním Shannona (1949), který tvrdí, že pro bod unicity "lze ukázat, že leží mezi krajními body 20 a 30. S 30 písmeny existuje téměř vždy jediné řešení pro kryptogram tohoto typu a s 20 můžeme najít nějaký počet řešení." Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity To pak celkem souhlasí s empirickým pozorováním Shannona (1949), který tvrdí, že pro bod unicity "lze ukázat, že leží mezi krajními body 20 a 30. S 30 písmeny existuje téměř vždy jediné řešení pro kryptogram tohoto typu a s 20 můžeme najít nějaký počet řešení." Podobným způsobem Friedman (1973) tvrdí, že "Prakticky každý příklad 25 nebo více charakterů reprezentujících monoabecední zašifrování smysluplné zprávy v angličtině lze snadno vyřešit". Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity V roce 1977 M.E. Hell-man navrhl alternativní a přitažlivé rozšíření výše zkoumaného přístupu. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity V roce 1977 M.E. Hell-man navrhl alternativní a přitažlivé rozšíření výše zkoumaného přístupu. V tomto modelu je prostor zpráv rozdělen do dvou disjunktních podmnožin. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity V roce 1977 M.E. Hell-man navrhl alternativní a přitažlivé rozšíření výše zkoumaného přístupu. V tomto modelu je prostor zpráv rozdělen do dvou disjunktních podmnožin. První podmnožina obsahuje 2HN smysluplných či typických zpráv, přičemž každá z těchto zpráv má a priori pravděpodobnost 2-hnm meaningful messages l^|/v _ 2hn meaningless messages 2' > \i\n = 2hon cryptograms Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Zbývající zprávy nemají v našem jazyku smysl a mají pravděpodobnost 0. Zároveň budeme předpokládat, že klíče jsou použity nezávisle na zprávě a se stejnou pravděpodobností. Uvod Šifrovací systémy Perfektní bezpečnost Redundance aproximace jazyka Odhad redundance azyk jako zdroj Bod unicity Zbývající zprávy nemají v našem jazyku smysl a mají pravděpodobnost 0. Zároveň budeme předpokládat, že klíče jsou použity nezávisle na zprávě a se stejnou pravděpodobností. Je-li C kryptogram, označme Z (C) počet dvojic (M, K) takových, že zpráva M je smysluplná a e(Mh Kj) = C, pak nepřítel, který zachytí C, bude v pochybách o použitém klíči. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Zbývající zprávy nemají v našem jazyku smysl a mají pravděpodobnost 0. Zároveň budeme předpokládat, že klíče jsou použity nezávisle na zprávě a se stejnou pravděpodobností. Je-li C kryptogram, označme Z (C) počet dvojic (M, K) takových, že zpráva M je smysluplná a e(Mh Kj) = C, pak nepřítel, který zachytí C, bude v pochybách o použitém klíči. Je-li \Z(C)\ > 1, je kryptogram C zašifrován pomocí šifrování s falešným klíčem. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Zbývající zprávy nemají v našem jazyku smysl a mají pravděpodobnost 0. Zároveň budeme předpokládat, že klíče jsou použity nezávisle na zprávě a se stejnou pravděpodobností. Je-li C kryptogram, označme Z (C) počet dvojic (M, K) takových, že zpráva M je smysluplná a e(Mh Kj) = C, pak nepřítel, který zachytí C, bude v pochybách o použitém klíči. Je-li \Z(C)\ > 1, je kryptogram C zašifrován pomocí šifrování s falešným klíčem. Položme s(C) = max{[Z(C)-1],0}. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Očekávaná hodnota s(C), totiž Š=J>(C)P(C), CeC nám odhaduje očekávaný počet šifrování s falešným klíčem. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Očekávaná hodnota s(C), totiž Š=5>(C)P(C), CeC nám odhaduje očekávaný počet šifrování s falešným klíčem Ale je okamžitě vidět, že š = z - 1, kde ž=^Z(C)P(C) = ^Z2(C)/2^|K CeC CeC protože z definice modelu pro každý kryptogram C platí P(C) = Z(C)/2A/H|K Úvod Perfektní bezpečnost Šifrovací systémy Redundance Droximace jazyka Odhad redundance izyk jako zdroj Bod unicity Přitom evidentně Ez(c) = 2 CeC Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Přitom evidentně ^Z(C) = 2""|K|. CeC Aplikujeme-li na výše uvedené jednoduché lemma tvrdící, že pro všechna x, splňující n /=i máme n J>f >a2/n, ;'=1 Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Přitom evidentně ^Z(C) = 2NH\K CeC Aplikujeme-li na výše uvedené jednoduché lemma tvrdící, že pro všechna x, splňující n /=i mame n Y,*i>a2/n. /=1 a tedy obdržíme Z > (2NH|K|)7(|C|2/V"|K|) = 2/v"|K|/|C nh Úvod Perfektní bezpečnost Šifrovací systémy Redundance roximace jazyka Odhad redundance lyk jako zdroj Bod unicity Můžeme pak vyslovit následující ' Věta 42_' Za předpokladu platnosti výše šifrování s falešným klíčem od š > (2NH uvedeného je očekávaný počet hadnut jako K|/|C|)-1. Úvod Perfektní bezpečnost Šifrovací systémy Redundance roximace jazyka Odhad redundance lyk jako zdroj Bod unicity Můžeme pak vyslovit následující ' Věta A12_1 Za předpokladu platnosti výše šifrování s falešným klíčem od š > (2NH uvedeného je očekávaný počet hadnut jako K|/|C|)-1. Píšeme-li nyní K = 2H^K\ C = 2NH° = \T\N, kde HQ je entropie jazyka, lze výše uvedenou větu přepsat jakožto g > 2NH+h(k)-nh0 _ -j přičemž pravá strana je rovna nule přesně v bodu unicity. Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Příklad 4.3 l Předpokládejme, že šifrujeme pomocí Vigenerova šifrování otevřený text délky 100 klíčem délky 80 tak, že máme anglickou abecedu s 26 písmeny Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Příklad 4.3 l Předpokládejme, že šifrujeme pomocí Vigenerova šifrování otevřený text délky 100 klíčem délky 80 tak, že máme anglickou abecedu s 26 písmeny Víme, že H0 = 4,7 = log 26 a H = HE - 1,5 bitů, H(/C) = 80-log26 = 376, Uvod Šifrovací systémy Perfektní bezpečnost Redundance Aproximace jazyka Jazyk jako zdroj Odhad redundance Bod unicity Příklad 4.3 l Předpokládejme, že šifrujeme pomocí Vigenerova šifrování otevřený text délky 100 klíčem délky 80 tak, že máme anglickou abecedu s 26 písmeny Víme, že H0 = 4,7 = log 26 a H = HE ~ 1,5 bitů, H(/C) = 80-log26 = 376, Obdržíme pak průměrně alespoň 2376+100 (1,5-4,7) _ 2376-320 ^ 2 56 různých šifrování s falešným klíčem pro kryptogram o 100 písmenech.