Perfektní autentizace libovolně dlouhých zpráv

Rok / Year: 2013

Svazek / Volume: 15

Číslo / Issue: 1

Perfektní autentizace libovolně dlouhých zpráv Perfect authentication of arbitrarily long messages Karel Burda [email protected] Fakulta elektrotechniky a komunikačních technologií VUT v Brně

Abstrakt: Kryptosystémy s perfektní autentizací zajišťují nejvyšší míru autentičnosti zpráv, avšak doposud známé techniky jsou použitelné jen pro krátké zprávy. V tomto článku je navržen algoritmus, který zajišťuje perfektní autentizaci zpráv o libovolné délce. K prokázání bezpečnosti navrženého algoritmu je odvozen a následně použit přístup založený na vlast-nostech použité kryptografické funkce. Navržený algoritmus vyžaduje jednorázový unikátní klíč, jehož délka je rovna součtu délky zprávy a délky pečeti.

Abstract: Cryptosystems for perfect authentication provide the highest measure of message authentication; however, the currently known techniques are usable for short messages only. In this paper, a method which provides perfect authentication of arbitrarily long messages is proposed. The security of the method is proved by an analysis of the properties of the authentication function. The method proposed requires a one-time unique key whose length is equal to the sum of the message length and the tag length.

VOL.15, NO.1, FEBRUARY 2013

Perfektní autentizace libovolně dlouhých zpráv Karel Burda Fakulta elektrotechniky a komunikačních technologií VUT v Brně Email: [email protected]

Abstrakt – Kryptosystémy s perfektní autentizací zajišťují nejvyšší míru autentičnosti zpráv, avšak doposud známé techniky jsou použitelné jen pro krátké zprávy. V tomto článku je navržen algoritmus, který zajišťuje perfektní autentizaci zpráv o libovolné délce. K prokázání bezpečnosti navrženého algoritmu je odvozen a následně použit přístup založený na vlastnostech použité kryptografické funkce. Navržený algoritmus vyžaduje jednorázový unikátní klíč, jehož délka je rovna součtu délky zprávy a délky pečeti.

asymetrických kryptosystémů se pečeť obvykle označuje jako digitální nebo také elektronický podpis. Případný útočník může na systém autentizace zpráv v zásadě útočit dvěma způsoby. První útok se nazývá útok vložením zprávy („impersonation attack“) a druhým útokem je útok substitucí zprávy („substitution attack“) [3]. V případě útoku vložením zprávy útočník odešle příjemci B podvodnou zapečetěnou zprávu (Z, P) a předpokládá, že ji příjemce akceptuje jako zprávu od odesílatele A. V případě útoku substitucí zprávy útočník zapečetěnou zprávu (Z, P) odeslanou odesílatelem A zachytí a nahradí ji zprávou (Z´, P´). Opět předpokládá, že příjemce nahrazenou zprávu akceptuje jako zprávu od odesílatele A. Pravděpodobnost úspěšného útoku vložením zprávy budeme značit pI a pravděpodobnost úspěšné substituce zprávy označíme pS. Na jejich základě je pak ještě definována pravděpodobnost úspěšného podvodu pD, která je definována následovně: pD  maxpI , pS . (1) Tato pravděpodobnost vyjadřuje celkovou úroveň bezpečnosti použitého systému autentizace zpráv. Čím je hodnota pD menší, tím je systém autentizace zpráv bezpečnější. Pokud mají pečeti délku m bitů, tak nejmenší možná hodnota této pravděpodobnosti je 2-m. Tato dolní hranice hodnoty pD je dána skutečností, že útočník má vždy možnost pro svoji zprávu odhadnout ze všech N = 2m možných pečetí správnou pečeť s pravděpodobností úspěchu 1/N. O autentizačních kryptosystémech s uvedenou vlastností říkáme, že zajišťují perfektní („perfect“) nebo také nepodmíněnou („unconditional“) autentizaci zpráv. Druhým extrémem jsou autentizační kryptosystémy s pD = 1, tj. útočník má teoreticky možnost podvádět příjemce s naprostou jistotou. Typicky se jedná o asymetrické autentizační kryptosystémy, u kterých existuje možnost, že útočník ze známého veřejného klíče VK odvodí soukromý klíč SK a tak bude moci podepisovat zprávy jménem odesílatele A. Bezpečnost těchto kryptosystémů spočívá na předpokladu, že odvození SK z veřejného VK je výpočetně nemožné. Vzhledem k tomu, že tématem článku je perfektní autentizace, tak se v dalším omezíme jen na posuzování bezpečnosti symetrických autentizačních kryptosystémů. K analýze bezpečnosti autentizačních kryptosystémů byla analogicky k teorii utajení [4] vybudována teorie autentizace [5]. Obě tyto teorie jsou založeny na teorii informace a k analýze vlastností kryptosystémů se využívají veličiny jako je entropie zpráv, klíčů a kryptogramů nebo pečetí. Výhodou popsaného přístupu je vysoká obecnost, ale nevýhodou je jeho obtížná aplikace pro konkrétní kryptosystém. Z tohoto důvodu je v článku navržen nový přístup, který je založen na analýze vlastností pečetící funkce.

1 Úvod Autentizace zpráv je poměrně mladá [1] kryptografická technika, s jejíž pomocí si příjemci ověřují, zda přijatá zpráva nebyla při svém transportu od odesílatele k příjemci pozměněna. Princip spočívá v tom (viz obr. 1), že odesílatel A ke zprávě Z připojí blok dat P, který závisí na zprávě Z a na tajném klíči KP [2]. Formálně tuto skutečnost vyjádříme vztahem P = Q(Z, KP), přičemž P nazveme analogicky s autentizační technikou listinných dokumentů pečeť a funkci Q budeme nazývat pečetící funkce. Odesílatel pak zapečetěnou zprávu, tj. dvojici (Z, P) zašle příjemci. V důsledku akcí útočníka je příjemci obecně doručena zpráva (Z´, P´). Příjemce B disponuje ověřovacím klíčem KV a pomocí verifikační funkce V(Z´, P´, KV) provede ověřovací výpočet. Výstupem verifikační funkce V je výrok, že zpráva Z´ je, či není autentická.

Obrázek 1: Princip autentizace zpráv. V případě symetrického autentizačního kryptosystému platí, že odesílatel i příjemce sdílejí náhodně zvolený klíč K = KP = KV. V případě asymetrického autentizačního kryptosystému platí, že odesílatel vlastní soukromý (tzv. podepisovací) klíč SK a příjemce disponuje veřejným (tzv. ověřovacím) klíčem VK. Podle našeho obrázku tedy platí, že KP = SK a KV = VK. U symetrických autentizačních kryptosystémů se pečeť nazývá různě. Nejčastěji je označována jako MAC („Message Authentication Code“), ale lze se setkat i s řadou dalších označení jako je MIC („Message Integrity Check“), HMAC („Hashed MAC“), ICV („Integrity Check Value“) atd. V případě

5

VOL.15, NO.1, FEBRUARY 2013 a pro pravděpodobnost úspěšného vložení zprávy tak potom můžeme psát: NK 1 S pI    . (7) NK N  NK N K určení pravděpodobnosti pS úspěšné substituce zprávy zavedeme pojem afinita (příbuznost) svazků. Afinita AZP-YT je počet prvků množiny: (8) K ZPYT  K ZP  KYT , Z ,Y  Z , P, T  P , tj. jedná se o počet klíčů, které náleží jak do svazku klíčů KZP, tak i do svazku KYT. Vzhledem k disjunktnosti svazků jedné a téže zprávy Z, zcela samozřejmě platí, že AZP-ZT = 0. Při útoku substitucí zprávy útočník v přenosovém kanálu zachytí zapečetěnou zprávu (Z, P). Ze znalosti pečetící funkce může teoreticky zjistit, že byl použit některý z pečetících klíčů svazku KZP. Protože neví, který konkrétní klíč z tohoto svazku byl použit, tak pro svoji podvodnou zprávu Y vyhledá pečeť T takovou, aby svazek KYT obsahoval co nejvíce klíčů, které obsahuje i svazek KZP. Zapečetěnou zprávu (Y, T) pak útočník příjemci odešle. Pravděpodobnost úspěšné substituce je v tomto případě rovna pravděpodobnosti, že aktuální pečetící klíč K náležející do svazku KZP, se nachází také ve svazku KYT. Pro pravděpodobnost úspěšné substituce potom platí: A pS ZPYT  ZPYT . (9) S ZP Protože nás při posuzování bezpečnosti autentizačního kryptosystému opět zajímá nejhorší případ, tak pravděpodobnost pS úspěšné substituce zprávy budeme definovat: (10) pS  max{ pS ZPYT }, Z ,Y  Z , P, T  P.

2 Analýza vlastností pečetící funkce Analýzu bezpečnosti autentizačních kryptosystémů založíme na analýze vlastností pečetící funkce P = Q(Z, K). Základní veličiny související s pečetící funkcí uvádí obr. 2. Množina zpráv je označena jako Z a na obrázku jsou z této množiny uvedeny zprávy Z a Y. Množina pečetí je označena jako P a z ní jsou uvedeny pečeti P a T. Pečetící funkce Q přiřazuje pomocí klíče K každé zprávě Z pečeť P = Q(Z, K). Množinu klíčů, kterou je zprávě Z přiřazena pečeť P, označíme KZP. Tuto množinu klíčů budeme nazývat svazek klíčů, přičemž počet klíčů této množiny budeme značit SZP.

Obrázek 2: Pečetící funkce. Z každé zprávy vede k pečetím všech NK možných klíčů. Svazky klíčů vycházející z jedné zprávy Z jsou přitom navzájem disjunktní a zároveň jejich sjednocením získáme množinu K všech pečetících klíčů. Formálně tyto zřejmé skutečnosti můžeme pro každou zprávu Z zapsat: (2) K ZP  K ZT  , P, T  P

K

X P

ZX

 K.

Parametry svazků lze snadno zjišťovat u pečetících funkcích založených na algebraických strukturách. Jako příklad možností navrženého přístupu si uvedeme analýzu pečetící funkce podle [6], jejíž popis je uveden i ve [3]. Zmiňovaná pečetící funkce je definována pro konečné těleso GF(2m), kde m je délka pečeti v bitech. Zpráva Z o délce tm bitů je rozdělena na t bloků zi o délce m bitů, tj. můžeme psát, že: (11) Z  z1 , z2 ,, zt . Pečetící klíč K je dvojice náhodných čísel a a b, tj. K = (a, b). Délka každého z těchto tajných čísel je m bitů. Pečeť zprávy se pak vypočítává v tělese GF(2m) podle vztahu:

(3)

V případě, že útočník provede útok vložením zapečetěné zprávy (Z, P), tak bude úspěšný, pokud aktuální pečetící klíč K bude patřit do svazku KZP. Pečetící klíče jsou voleny náhodně a tak pravděpodobnost úspěchu útočníka je rovna podílu počtu klíčů SZP v daném svazku a celkového počtu klíčů NK, tj. můžeme psát: S p I ZP  ZP . (4) NK Uvedený vztah popisuje pravděpodobnost úspěšného vložení konkrétní zprávy (Z, P). Z bezpečnostního hlediska nás však zajímá nejhorší případ a tak budeme pravděpodobnost úspěšného vložení zprávy definovat: (5) pI  max{ pI ZP }, Z  Z , P  P.

t

P  b   a i  zi .

(12)

i 1

Snadno můžeme zjistit, že počet pečetí N = 2m, počet klíčů NK = N 2 a počet zpráv NZ = N t. Počet klíčů S svazku je konstanta, která je rovna počtu pečetí N, tj. S = N. Je to dáno tím, že klíče svazku mezi libovolnou zprávou Z a pečetí P, můžeme určovat tak, že postupně volíme jednu ze všech N možných hodnot první poloviny klíče (tj. a) a k této polovině klíče jednoznačně určíme druhou polovinu klíče (tj. b) tak, že:

Z obou uvedených vztahů je zřejmé, že k minimalizaci hodnoty pI je zapotřebí, aby všechny svazky sestávaly ze stejného počtu klíčů. Z každé zprávy vedou svazky ke všem N pečetím, přičemž tyto svazky dohromady obsahují všech NK klíčů. Pro počet klíčů S jednoho svazku kryptosystému s minimální hodnotou pI pak zcela samozřejmě platí, že: N S K (6) N

t

b  P   a i  zi .

(13)

i 1

Z uvedené konstrukce klíčů mezi Z a P vyplývá, že hodnota a každého klíče svazku je unikátní číslo z N možných a hodnota b je jednoznačným důsledkem hodnot Z, P a a. Tím jsme dokázali, že každý svazek sestává z N klíčů. Pro afinitu A popsaného pečetícího kryptosystému platí, že A = t, což je počet bloků zpráv. Důkaz tohoto tvrzení je násle-

6

VOL.15, NO.1, FEBRUARY 2013 dující. Pro všechny společné klíče K = (a, b) svazků KZP a KYT platí následující soustava rovnic:

poskytující perfektní autentizaci (pD = 1/N) a systémy, ve kterých bezpečnost spočívá na výpočetní nemožnosti kryptoanalýzy (pD = 1). Je však zapotřebí si uvědomit, že mezi oběma uvedenými extrémy existuje celá řada autentizačních systémů s pD  (1/N, 1).

t

P  b   a i  zi , i 1

(14)

t

T  b   a i  yi .

3 Algoritmus perfektní autentizace zpráv

i 1

Ze druhé rovnice vyjádříme proměnnou b, dosadíme ji do první rovnice a po jednoduchých úpravách obdržíme rovnici: t

 a  z i

i 1

i

 yi   P  T .

Perfektní autentizaci zpráv poskytují autentizační kryptosystémy, u kterých pD = 1/N. S jedním takovým kryptosystémem jsme se již setkali v předchozí kapitole. Jednalo se o kryptosystém podle rovnice (12), kdy t = 1. Pečetící funkci pro tento případ můžeme přepsat do tvaru: P  b  a  Z, (20) kde P je pečeť, Z je zpráva a K = (a, b) je pečetící klíč, který musí být pro každou zprávu náhodný a unikátní. Proměnné a, b, Z a P jsou čísla o délce m bitů a operace jsou prováděny nad konečným tělesem GF(2m). Samozřejmě existují varianty tohoto kryptosystému i pro jiné typy konečných těles, ale ty zde popisovat nebudeme. Pro popsaný kryptosystém platí, že počet pečetí N = 2m, počet zpráv NZ = N, celkový počet klíčů NK = N 2, objem svazku S = N klíčů a afinita A = 1. Popsaný způsob autentizace nazveme jednorázová lineární autentizace. Perfektní autentizaci zpráv poskytují také pečetící kryptosystémy založené na tzv. ortogonálních polích („orthogonal arrays“) [7]. Ortogonální pole OA(N, NZ, A) je tabulka sestávající z (AN 2) řádků a NZ sloupců, kde pro každou dvojici sloupců platí, že prvky v těchto sloupcích tvoří v každém řádku dvojici, která se pro dané sloupce vyskytuje přesně v A řádcích tabulky. Každý sloupec tabulky reprezentuje jednu zprávu Z, každý řádek reprezentuje jeden klíč K a každý prvek tabulky reprezentuje pečeť P = Q(Z, K). Vzhledem k definici tabulky pak platí, že pro každou dvojici zpráv Z, Y (tj. pro každou dvojici sloupců) se stejné dvojice pečetí P = Q(Z, K) a T = Q(Y, K) nacházejí právě v A řádcích tabulky. Jinými slovy existuje A klíčů takových, že zprávám Z, Y přiřadí pečetící funkce Q pokaždé stejnou hodnotu pečetí P a T. Veličinu A jsme definovali jako afinitu svazků KZP a KYT. Nejprve byly publikovány pečetící kryptosystémy založené na ortogonálních polích s afinitou A = 1 [8]. Tyto kryptosystémy disponovaly klíči o objemu NK = N 2 klíčů a pro počet zpráv platilo, že NZ ≤ (N + 1). Později byly publikovány pečetící kryptosystémy pro větší počet zpráv [9], které jsou založeny na ortogonálních polích s A > 1. Pro tyto kryptosystémy platí, že NK = AN 2 a zároveň platí, že NK = NZ  (N  1) + 1. Z obou posledně uvedených vztahů lze odvodit, že NZ ≈ AN = S. Nevýhodou ortogonálních polí je skutečnost, že se poměrně složitě generují [10] a pro velký počet zpráv i klíčů jsou výsledné tabulky z hlediska svého objemu neakceptovatelné. Lze tedy konstatovat, že doposud známé autentizační kryptosystémy umožňují perfektní autentizaci jen pro krátké zprávy. V dalším je uveden návrh autentizačního kryptosystému, který zajišťuje perfektní autentizaci pro libovolně dlouhé zprávy. Navrhovaný kryptosystém bude opět vysvětlen ve variantě pro těleso GF(2m). Zpráva je dána jako posloupnost t bloků zi, přičemž každý tento blok je dlouhý m bitů. Můžeme tedy psát, že Z = z1, z2, ..., zt. Pokud délka zprávy není celistvým násobkem m bitů, tak ji lze na tento násobek doplnit standardními

(15)

Zprávy Z, Y a pečeti P, T jsou pro každou zkoumanou dvojici svazků dány a tak jsme získali polynomickou rovnici pro proměnnou a stupně t. Uvedený typ rovnic má nejvýše t různých řešení. Protože veličiny Z, Y, P a T mohou nabývat všech možných hodnot, tak pro danou pečetící funkci zaručeně existuje nějaká dvojice svazků s t společnými klíči. V souladu s definicemi pravděpodobnosti úspěšných útoků pak pro analyzovaný autentizační kryptosystém platí, že pravděpodobnost úspěšného vložení: S N 1   pI  (16) NK N 2 N a pravděpodobnost úspěšné substituce zprávy: A  t (17) pS  max  ZPYT   .  S ZP  N Pro pravděpodobnost úspěšného podvodu pD nakonec platí: t pD  max pI , pS   . (18) N Z tohoto vztahu je zřejmé, že bezpečnost popsaného autentizačního kryptosystému závisí na délce zpráv. Pokud mají zprávu délku m bitů (tj. t = 1), tak je pravděpodobnost úspěšného podvodu pD rovna hodnotě 1/N = 2-m, což znamená, že se jedná o perfektní autentizaci zpráv. S prodlužováním zprávy pravděpodobnost úspěšného podvodu lineárně roste. V případě, kdy t ≥ N = 2m bude pD = 1, tj. útočník bude teoreticky schopen vkládat nebo substituovat některé zprávy se stoprocentní jistotou. Tato skutečnost je způsobena tím, že afinita některých dvojic svazků je rovna počtu klíčů v těchto svazcích. Jinými slovy nastane stav, kdy některé svazky různých zpráv budou stejné a útočník bude moci v rámci těchto svazků provádět substituci zpráv bez možnosti, aby příjemce tuto substituci zjistil. Konkrétně v případě popisované pečetící funkce platí následující. Mocniny a i pro nenulové hodnoty a tvoří v GF(2m) cyklickou podgrupu. Potom pro každou hodnotu a platí, že a N = a. Pečetící funkci z (12) pak můžeme zapsat jako: N

N 1

i 1

i 2

P  b   a i  zi  b  a  z1  z N    a i  zi .

(19)

Z tohoto zápisu je zřejmé, že zprávám Z = z1, z2, ..., zN1, zN a Y = y1, z2, ..., zN1, yN přiřadí pečetící funkce pro každý klíč totožnou pečeť P, pokud (z1 + zN) = (y1 + yN). Útočník tak může zprávu Z nahradit zprávou Y a příjemce nemá šanci tuto substituci zjistit. Výše uvedený příklad ilustroval skutečnost, že autentizační kryptosystémy zajišťují různou míru bezpečnosti zpráv. V současné době jsou autentizační systémy podle poskytované úrovně bezpečnosti zpráv obvykle klasifikovány na systémy

7

VOL.15, NO.1, FEBRUARY 2013 výplňovými technikami (např. [11]). Pečetící klíč je pro každou zprávu Z unikátní náhodná posloupnost bitů o délce (t + 1) bloků ki, přičemž délka každého bloku činí m bitů. Pro klíč K tedy můžeme psát K = k0, k1, k2, ..., kt. Pro pečeť P o délce m bitů pak platí vztah:

srovnatelné s metodou používanou pro perfektní utajení zpráv [4]. Z porovnání vlastností všech popsaných metod perfektní autentizace vyplývá, že metoda založená na ortogonálním poli má pouze teoretický význam. V případě lineárních metod autentizace je výhodnější navržená metoda, protože délka pečeti je m bitů oproti t∙m bitům v případě jednorázové varianty a délka klíče je (t + 1)∙m bitů oproti 2∙t∙m bitům.

t

P  k 0   k i  zi .

(21)

i 1

Popsaný způsob autentizace nazveme bloková lineární autentizace. Počet pečetí je v tomto případě roven hodnotě N = 2m, pro počet zpráv platí, že NZ = N t a pro počet klíčů můžeme psát, že NK = N t+1. Podobnými úvahami jako v předešlé kapitole můžeme dokázat, že počet klíčů svazku S = N t. Nyní si dokážeme, že pro afinitu v tomto kryptosystému platí, že A = N t–1. Pro společné klíče K = k0, k1, k2, ..., kt svazků vedoucích ze zprávy Z do pečeti P a ze zprávy Y do pečeti T platí následující soustava rovnic:

4 Závěr V článku je navržen algoritmus, který zajišťuje perfektní autentizaci zpráv o libovolné délce. K prokázání bezpečnosti navrženého algoritmu byly zavedeny pojmy svazek klíčů a afinita svazků. Pomocí těchto pojmů lze exaktně definovat pravděpodobnost podvodu a analyzovat tak bezpečnost použité pečetící funkce. Porovnáním s vlastnostmi doposud známých algoritmů pro perfektní autentizaci zpráv vyplývá, že navržený algoritmus je výpočetně méně náročný (pracuje s m bitovými čísly), prakticky použitelný pro autentizaci zpráv libovolné délky a z hlediska spotřeby klíče velmi efektivní (délka klíče je rovna součtu délky zprávy a délky pečeti).

t

P  k0   ki  zi , i 1 t

(22)

T  k 0   k i  yi . i 1

Je zřejmé, že pro dané Z, Y, P a T se jedná o soustavu n = 2 lineárních rovnic pro h = (t + 1) neznámých. Konkrétní řešení této soustavy lze získat tak, že (h – n) = (t – 1) proměnných zvolíme jak parametry. Potom tedy existuje N t–1 řešení uvedené soustavy, tj. ve dvojici svazků od různých zpráv se nachází nanejvýše A = N t–1 společných klíčů. Z výše uvedených parametrů potom pro pravděpodobnost úspěšného vložení zprávy vyplývá, že:

Literatura [1] GILBERT E., MACWILLIAMS F., SLOANE N. Codes which detect deception. The Bell System Technical Journal. 1974, 3, 405–424. ISSN 0005-8580. [cit. 17.12.2012]. Dostupné z: http://neilsloane.com/doc/detection.pdf. [2] OPPLIGER R. Contemporary Cryptography. London: Artech House, 2005. ISBN 1580536425. [3] PRENEEL B. Cryptographic Primitives for Information Authentication — State of the Art. In: Lecture Notes in Computer Science 1528. Berlin: Springer-Verlag, 1998, s. 50–105. ISBN ISBN 3-540-65474-7. [cit. 17.12.2012]. Dostupné z: https://www.cosic.esat.kuleuven.be/ publications/article-346.pdf [4] SHANNON C. E. Communication Theory of Secrecy Systems. Bell System Technical Journal. 1949, 4, 656–715. ISSN 0005-8580. [cit. 17.12.2012]. Dostupné z: http:// netlab.cs.ucla.edu/wiki/files/shannon1949.pdf. [5] SIMMONS G. J. A Survey of Information Authentication. Proceedings of the IEEE. 1988, 5, 603–620. ISSN 00189219. [6] MEHLHORN K., VISHKIN U. Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories. Acta Informatica. 1984, 4, 339–374. ISSN 0001-5903. [7] STINSON D. R. Combinatorial Designs: Constructions and Analysis. New York: Springer-Verlag, 2004. ISBN 0387-95487-2. [8] STINSON D. R. The combinatorics of authentication and secrecy codes. Journal of Cryptology, 1990, 2, 23–49. ISSN 0933-2790. [9] STINSON D. R. Combinatorial characterizations of authentication codes. Designs, Codes and Cryptography. 1992, 2, 175-187. ISSN 0925-1022. [10] GOPALAKRISHNAN K., STINSON D. R. Applications of Orthogonal Arrays to Computer Science. In: Proceedings of ICDM 2006. Hong Kong, 2006, s. 149–164. ISBN

S Nt 1 (23)  t 1  NK N N a pro pravděpodobnost úspěšné substituce zprávy platí: pI 

A  N t 1 1 (24) pS  max  ZPYT   t  . N  S ZP  N Pro pravděpodobnost úspěšného podvodu pD tak nakonec máme: 1 p D  max p I , pS   , (25) N z čehož plyne, že navržený autentizační kryptosystém zajišťuje perfektní autentizaci zpráv. Nyní porovnejme vlastnosti všech tří způsobů perfektní autentizace pro případ dlouhých zpráv. Označme délku zprávy LZ = t∙m bitů. V případě jednorázové lineární autentizace je délka klíče LK rovna dvojnásobku délky zprávy (tj. LK = 2∙LZ) a délka pečeti L je rovna délce zprávy, tj. L = LZ. Autentizace zpráv o délce např. 106 bitů je tak z důvodu délky pečeti a délky klíče značně nepraktická. V případě autentizace založené na ortogonálním poli jsme si již uvedli, že počet sloupců tabulky je roven počtu zpráv NZ = 2t∙m ≈ A∙N, kde N = 2m je počet pečetí. Počet řádků tabulky je roven hodnotě NK = A∙N 2 ≈ NZ ∙N = 2(t+1)∙m. Uvedená metoda autentizace tedy vyžaduje tabulku o formátu NK  NZ = 2(t+1)∙m  2t∙m. Pro délku pečeti např. m = 128 bitů je vytvoření takové tabulky výpočetně nemožné. Pro autentizaci metodou blokové lineární autentizace je délka klíče (t + 1)∙m bitů, tj. LK = LZ + m a veškeré operace se provádějí s čísly o délce m bitů. Nároky této metody jsou tak

8

VOL.15, NO.1, FEBRUARY 2013 0-7695-2702-7. [cit. 17.12.2012]. Dostupné z: http://www. cs.ecu.edu/~gopal/icdm-pubver.pdf [11] Secure Hash Standard. FIPS PUB 180-1. Gaithersburg: National Institute of Standards and Technology, 1993. [cit. 17.12.2012]. Dostupné z: http://www.itl.nist.gov/fipspubs /fip180-1.htm

9